大话数据结构-3.4 线性表的顺序存储结构 47- 高飞网

3.4 线性表的顺序存储结构 47

2015-12-07 12:14:05.0

线性表(List):零个或多个数据元素的有限序列。

ADT 线性表(List)
Data
    线性表的数据对象集合为(a1,a2,…,an),每个元素的类型为DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素an外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
    InitList(*L):			初始化操作,建立一个空的线性表
    ListEmpty(L):		若线性表为空,返回true,否则返回false
    ClearList(*L):			将线性表清空
    GetElem(*L,I,*e):		将线性表L中的第i个位置元素值返回给e
    LocateElem(L,e):		在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号,否则返回0表示失败。
    ListInsert(*L,i,e):		在线性表L的第i个位置插入元素e
    ListDelete(*L,I,*e):	删除线性表L中的第i个位置元素,并且e返回其值
    ListLength(L):		返回线性表的元素个数
假设La表示集合A,Lb表示集合B,求集合A与B的并集。

void union(List *La,List Lb) 
{
    int La_len,Lb_len,i;
    ElemType e;//声明与La和Lb相同个的数据元素e
    La_len = ListLength(La);//求线性表的长度
    Lb_len = ListLength(Lb);
    for(i=1;i<=Lb_len;i++)
    {   
        GetElem(Lb,i,e);//取Lb中第i个元素赋给e
        if(!LocateElem(La,e,equal))//La中存在和e相同数据元素
        {   
            ListInsert(La,++La_len,e);//插入
        }   
    }   
}


线性表的顺序存储结构

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

线性表的顺序存储结构的代码

/* 线性表的顺序存储结构 */
#define MAXSIZE 10          //存储空间初始分配量
typedef int ElemType ;      //ElemType类型根据实际情况而定,这里假设为
int
typedef struct 
{
    ElemType data[MAXSIZE]; //数组存储数据元素,最大值为MAXSIZE
    int length;             //线性表当前长度
}ArrayList;

线性表增删改查的完整代码

ArrayList.h
/* 线性表的顺序存储结构 */
#define MAXSIZE 10          //存储空间初始分配量
typedef int ElemType ;      //ElemType类型根据实际情况而定,这里假设为int
typedef struct 
{
    ElemType data[MAXSIZE]; //数组存储数据元素,最大值为MAXSIZE
    int length;             //线性表当前长度
}ArrayList;

#define OK 1
#define ERROR 0
typedef int Status;
/* 线性表通用操作  */
Status InitList(ArrayList *L);              //建立一个空的线性表L
Status ListEmpty(ArrayList L);              //若线性表为空返回true,否则返回false
Status ClearList(ArrayList *L);         //将线性表清空
Status GetElem(ArrayList L,int i,ElemType *e);          //将线性表L中第i个位置元素值返回给e
int LocateElem(ArrayList L,ElemType e);         //在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
Status ListInsert(ArrayList *L,int i,ElemType e);       //在线性表L中的第i个位置插入新元素e
Status ListDelete(ArrayList *L,int i,ElemType *e);      //删除线性表L中第i个位置元素,并用e返回值值
int ListLength(ArrayList L);            //返回线性表L的元素个数
ArrayList.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "ArrayList.h"

int main(void)
{
	ArrayList L;
	InitList(&L);
	printf("length==%d\n",L.length);
	if(ListEmpty(L))
	{
		printf("是空的\n");
		ListInsert(&L,0,3);
		ListInsert(&L,1,13);
		ListInsert(&L,2,23);
		ListInsert(&L,2,33);
		ListInsert(&L,4,43);
		ListInsert(&L,5,53);
		ListInsert(&L,6,63);
		ListInsert(&L,7,73);
		ListInsert(&L,8,83);
		ListInsert(&L,9,93);
		ListInsert(&L,10,103);
		ListInsert(&L,11,113);
		ListInsert(&L,12,123);
	}

	printf("遍历所有元素:");
	int len = ListLength(L);
	for(int i=0;i<len;i++)
	{
		printf("[%d]%d,",i,L.data[i]);		
	}
	printf("\n");

	ElemType e;
	GetElem(L,2,&e);
	printf("索引2位置的元素是:%d\n",e);

	printf("查找53的索引位置是:%d\n",LocateElem(L,53));

	printf("删除第6位后\n");
	ElemType ee;
	ListDelete(&L,6,&ee);	
	len = ListLength(L);
	for(int i=0;i<len;i++)
	{
		printf("[%d]%d,",i,L.data[i]);		
	}
	printf("\n");


	return 0;
}

//建立一个空的线性表L
Status InitList(ArrayList *L)				
{
	memset(L->data,0,sizeof(ElemType)*MAXSIZE);
	L->length = 0;
	return OK;		
}
//若线性表为空返回true,否则返回false
Status ListEmpty(ArrayList L)				
{
	return L.length==0;		
}
//将线性表清空
Status ClearList(ArrayList *L)			
{
	memset(L->data,0,sizeof(ElemType)*MAXSIZE);
	L->length = 0;
	return OK;		
}
//将线性表L中第i个位置元素值返回给e
Status GetElem(ArrayList L,int i,ElemType *e)			
{
	if(i<0||i>L.length)
	{
		printf("index 非法!\n");		
		return ERROR;
	}
	*e = L.data[i];
	return OK;		
}
//在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
int LocateElem(ArrayList L,ElemType e)			
{
	for(int i=0;i<L.length;i++)
	{
		if(e == L.data[i])
		{
			return i;
		}
	}
	return ERROR;		
}
//在线性表L中的第i个位置插入新元素e
Status ListInsert(ArrayList *L,int i,ElemType e)		
{	
	if(L->length>=MAXSIZE)
	{
		printf("线性表已满!\n");		
		return ERROR;
	}
	if(i<0||i>L->length)
	{
		printf("插入位置非法\n");
		return ERROR;
	}
	else if(i<L->length && L->length<MAXSIZE)
	{
		for(int j=L->length;j>i;j--)
		{//如果不在表尾往后移位
			L->data[j] = L->data[j-1];
		}
	}
	L->data[i] = e;
	L->length ++;
	return OK;		
}
//删除线性表L中第i个位置元素,并用e返回值值
Status ListDelete(ArrayList *L,int i,ElemType *e)		
{
	if(ListEmpty(*L))
	{
		printf("线性表已空!\n");		
		return ERROR;
	}
	if(i<0||i>L->length)
	{
		printf("删除位置非法\n");
		return ERROR;
	}
	*e = L->data[i];
	if(i<L->length)
	{
		for(int j=i;j<L->length-1;j++)
		{//往前移位
			L->data[j] = L->data[j+1];
		}
	}
	L->length --;

	return OK;		
}
//返回线性表L的元素个数
int ListLength(ArrayList L)			
{
	return L.length;		
}


线性表插入和删除的时间复杂度

最好的情况,插入和删除是最后一个元素,无需移动任何一个元素,时间复杂度是O(1);最坏的情况,插入和删除都是第一个元素,则所有的元素都得往后或往前移动,时间复杂度是O(n)。平均情况是(n-1)/2。即时间复杂度是O(n)。

顺序存储结构的优缺点

优点缺点

. 无须为表示表中元素之间的逻辑关系而增加额外的存储空间

. 可以快速地存储表中任一位置的元素

. 插入和删除操作需要移动大量的元素

. 当线性表长度变化时,无法确定存储空间的容量

. 造成存储空间的“碎片化”