数据结构（C语言描述）——顺序表的定义与实现

定义

线性表的顺序存储是指在内存中用地址连续的一组存储单元顺序存放线性表的数据元素。通常，这种存储结构的线性表称为顺序表。顺序表的特点是逻辑上相邻的数据元素在内存中的存储位置也是相邻的。

顺序表的实现

静态分配的实现

由于顺序表中所有数据存储的位置相邻，我们自然会想到C语言中拥有相同特征的数组。顺序表的静态分配正是利用数组来实现的。

#defineMAX100//宏定义顺序表最大长度的大小typedefintElemType;//规定顺序表的数据类型为inttypedefstructSqList{ElemType data[MAX];//用数组来存储数据intlength;//定义顺序表的已使用长度}SqList;

上述代码是对顺序表静态分配的声明，下面是初始化。

voidInitList(SqList*l)//输入顺序表的地址{for(inti=0;i<MAX;i++){//将顺序表中所有元素都赋为0l->data[i]=0;}l->length=0;//将顺序表的现有长度设为0}

顺序表的静态分配通过数组来实现，这种方法十分方便，但同时也有着不可忽视的缺点：顺序表的最大长度在定义之后就无法改变，在实际使用场景中可能会出现空间冗余或是空间不足的情况。所以，就引出了我们下面要讲的顺序表的动态分配。

动态分配的实现

#defineInitSize10//设初始长度为10typedefintElemType;//规定顺序表数据类型为inttypedefstructSqList{ElemType*data;intMaxSize;//最大长度intlength;//现使用长度}SqList;SqList*InitList(){SqList*l=(SqList*)malloc(InitSize*sizeof(ElemType));//申请内存空间l->length=0;//使用长度为0l->MaxSize=InitSize;//将最大长度设为初始长度returnl;//返回顺序表的地址}

利用动态内存分配的方式，我们可以实现对顺序表最大长度进行更改。

voidIncreaseSize(SqList*l,intlen){ElemType*q=(ElemType*)malloc((l->MaxSize+len)*sizeof(ElemType));//为新的数组申请内存空间for(inti=0;i<l->length;i++){q[i]=l->data[i];//将原数组中数据一一复制到新数组中}free(l->data);//释放原数组的内存空间l->data=q;//令顺序表指向新数组l->MaxSize+=len;//改变最大长度的值}

我们可以看到，虽然动态分配的方式可以改变数组的长度，但是每次改变长度都需要把原数组中的所有数据复制到新数组中，消耗的时间比较大，所以在实际应用环境中我们需要根据具体要求来选择。

顺序表的基本操作及其实现

因为顺序表的实现有两种方式，且两种方式的基本操作的实现有较多相似，所以本文以静态分配举例来讲述顺序表的基本操作及其实现。

顺序表的插入

在顺序表中插入新元素和在数组中插入新元素一个道理，需要先将插入位置后的所有数据后移一位，在放入新元素。

intInsertElem(SqList*l,intpos,ElemType e){if(pos<1||pos>l->length+1||l->length==MAX){//判断非法数据以及顺序表是否被填满return0;}for(inti=l->length-1;i>=pos-1;i--){//将插入位置后的元素一次后移l->data[i+1]=l->data[i];}l->data[pos-1]=e;//插入新元素l->length++;//顺序表长度加1return1;}

顺序表的删除

这和插入一个原理

intDeleteElem(SqList*l,intpos,ElemType*e){if(pos<1||pos>l->length){return0;}*e=l->data[pos-1];for(inti=pos-1;i<l->length-1;i++){l->data[i]=l->data[i+1];}l->length--;return1;}

顺序表的按位查找

ElemTypeGetElem(SqList*l,intpos){returnl->data[pos-1];//直接返回相应数组下标的值}

顺序表的按值查找

intLocateElem(SqList*l,ElemType e){for(inti=0;i<l->length;i++){if(l->data[i]==e){//寻找匹配项returni+1;}}return0;}

顺序表的遍历输出

voidTravelList(SqList*l){for(inti=0;i<l->length;i++){printf("%d\n",l->data[i]);}}

以上就是本文所介绍的顺序表的定义与实现，如有错误和不足欢迎指出。