sqlist

线性表的顺序结构

数据结构第⼀章（线性表的顺序结构）

线性表是数据结构中最简单最基本的数据结构，其所表⽰的结构是线性结构，也是数据结构中最常⽤、最重要的形式之⼀。

顺序表

所谓顺序表就是⽤⼀组地址连续的储存单元按顺序存储线性表中的数据结构，这说明只要知道顺序表的⾸地址和每个数据元素所占存储单元

的个数，就可求出任何⼀个元素的地址，⽽且求每个元素的所需的时间是相同的，这就使得顺序表具有按数据的序号进⾏随机存储的特点。

线性表的顺序存储结构类型定义如下：

(静态存储）

#defineMaxSize100//线性表存储空间的最⼤增量

typedefstruct{

ElemTypedata[MaxSize];//存储空间基址，数组指针data指⽰线性表的基地址

intlength;//线性表的当前长度

}SqList;

不过由于线性表的长度并不确定，所需要的最⼤存储空间因问题的不同⽽不同，⽽且有的时候很难估算，所以常常使⽤动态分配的指针⽅式

来表⽰顺序存储结构。

动态顺序结构描述如下：

#defineListInitSize100//线性表的初始⼤⼩

#defineListIncrement10//线性表存储空间的分配增量

typedefstruct{

ElemType*data;//存储空间基地址，由data表⽰

intlength;

intMaxSize;//当前分配的存储最⼤容量

}SqList;

注意：

1.C语⾔中数组的下标是从0开始的，使⽤时注意下标范围；

2.是注意数据元素的下标访问⽅式和指针访问⽅式的区别。例如，若L是SqList类型的顺序表，则表中第i

个数据元素是[i-1]或L.*(data+i-1)

下⾯是顺序表的⼀些基本操作

1.初始化顺序表

StatusInitList_Sq(SqList&L)//构造⼀个空的链表

{

=(ElemType*)malloc(ListInitSize*sizeof(ElemType));//分配存储单元

if(!)

returnOVERFLOW//存储分配失败

=0;//线性表的长度为0

e=ListInitSize;//初始存储容量

returnOK;

}

2.线性表清空

voidClearList(SqList&L)//清除线性表L中的所有元素，使之成为⼀个空表

{

if(!=NULL)//线性表⾮空，将长度置为0

=0;

}

3.查找定位

intSearchList(SqListL,ElemTypeX)

//在线性表中查找x相等的值，找到则返回该元素在表中的位置，否则返回-1

{

inti=0;

while(i<&&[i]!=x)

i++;//找到位置

if(i<)

returni+1;//成功找到

el

return-1;//没找到

}

4.遍历

voidTraver(SqListL)

{

inti=0;

if(!)

exit(0);

for(inti=0;i<;i++)

printf("%d",[i]);

printf("n");

}

5.插⼊元素

StatusInrtList(SqList&L,inti,ElemTypee)

{//在顺序线性表L中第i个位置之前插⼊新的元素e

if(i<1||i>+1)//检查i值的有效性，⽆效时直接返回

return-1;

if(>=e){//检查空间，如果当时存储空间已满，则增加分配

newba=(ElemType*)realloc(,(e+ListIncrement)*sizeof(ElemType));

if(!newba)//储存空间失败

return-1;

=newba;//储存成功，赋新基址

e+=ListIncrement;//修改表的存储容量

}

for(intj=-1;j>=i;j--)

[j+1]=[j];//插⼊位置之后逐次向后移动（注意这⾥要从后往前循环）

[i-1]=e;//插⼊e

++;//表长加1

return1;

}

6.删除元素

StatusDeleteList(SqList&L,inti,ElemType&e)

{//删除顺序线性表L中的第i个元素，如果该元素存在，⽤e返回其值

if(i<1||i>)//检查i值的有效性，⽆效时直接返回

return0;

e=[i-1];//将被删除元素的值赋给e

for(intj=1;j<=;j++)

[j-1]=[j];//被删除元素之后的元素逐个前移

--;

return1;

}

在上述实现的典型操作算法中，除查找、遍历、插⼊和删除外，算法的时间复杂度都是O(1)。

对于遍历算法，因为是把所有元素访问了⼀遍，所以对于有n个元素的线性表来说，执⾏次数为n，时间

复杂度为O(n)。

同样地，对于插⼊算法与删除算法的时间复杂度也为O(n)。