《数据结构与算法 C语言版》—— 2.2线性表的顺序表示与实现

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第2章，第2.2节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.2线性表的顺序表示与实现

2.2.1线性表的顺序表示

线性表的顺序存储是指在内存中用一组地址连续的存储单元依次存储线性表的数据元素，用这种存储方式存储的线性表称为顺序表。顺序表中数据元素之间的逻辑关系通过其“存储位置相邻”来表示，如图21所示。

如果顺序表的数据元素是按照递增或递减顺序存放的，则称其为有序顺序表。
假设线性表的每个数据元素需占用l个存储单元，其第一个元素的存储地址，即数组的基地址记为LOC(a1)，则线性表中第i个数据元素的存储地址LOC(ai)为
LOC(ai)=LOC(a1)+(i-1)*l
线性表中第i+1个数据元素的存储地址和第i个数据元素的存储地址之间具有以下关系：
LOC(ai+1)=LOC(ai)+l
由此可见，只要确定了线性表中第一个元素的存储位置，其他元素的存储位置就可以确定了，因此线性表的顺序存储结构是一种随机存取的存储结构。
由于高级程序设计语言中的数组具有随机存取的特性，因此，通常用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，因此在C语言中可采用动态分配的一维数组，描述如下：

//------------线性表的动态分配顺序存储结构-------------------
#define List_Size 100//线性表存储空间的初始分配量
#define ListIncrement 10//线性表存储空间的分配增量
typedef struct{
ElemType *elem;//存放线性表的数组基地址
int length;//线性表的当前长度
int listsize;//线性表当前分配的存储容量
}SqList;

2.2.2线性表的顺序实现

下面讨论在顺序存储结构下，线性表的基本操作是如何实现的。
1.顺序表的初始化
顺序表的初始化即构造一个空的线性表。设置length域的值为0表示线性表中没有元素，即为空表。算法描述如下：

void InitSqList(SqList &L){
L.elem=new ElemType［List_Size］;
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=List_Size;
}

2.建立顺序表
方法是依次将n个数据元素存入顺序表中。算法描述如下：

void CreateSqList(SqList &L,int n){//创建n个元素的顺序表
int i;
for(i=0;i<n;i++){
scanf("%d",&L.elem［i］);
L.length++;
}
}

3.销毁顺序表
该运算的结果是释放顺序表L占用的内存空间。算法描述如下：

void DeatroySqList(SqList &L){//销毁顺序表
delete L.elem;
}

4.插入操作
设线性表L=(a1,a2,…,ai－1,ai,ai+1,…,an)，在第i个位置插入x是指在第i-1个数据元素和第i个数据元素之间插入一个新的数据元素x，即L变为(a1,a2,…,ai－1,x,ai,ai+1,…,an)。
数据元素x的插入使得ai－1和ai的逻辑关系发生了变化，并且L的长度由n变为n+1。显然，插入位置i满足1≤i≤n+1。如果i=n+1，则只需将x插入到an之后即可；如果1≤i≤n，则需将an~ai依次向后移动一个位置，然后将x插入到空出的第i个位置。算法描述如下：

int SqListInsert(SqList &L,int i,ElemType x){
int j;
ElemType *p;
if(i<1||i>L.length+1)return ERROR;//插入位置不合法
if(L.length>=L.listsize){//当前存储空间已满，增加存储空间
p=(ElemType *)realloc(L.elem,(L.listsize+ListIncrement)*sizeof(ElemType));
if(!p)exit(OVERFLOW);
L.elem=p;
L.listsize=L.listsize+ListIncrement;
}
for(j=L.length-1;j>=i-1;j--)L.elem［j+1］=L.elem［j］;//插入位置之后的元素依次后移
L.elem［i-1］=x;//插入元素
++L.length;//表长增1
return OK;
}

下面对插入算法的时间复杂度进行分析。在顺序表中的某个位置插入一个数据元素，其时间主要消耗在移动元素上，而移动元素的个数取决于插入的位置和线性表的长度。
假设pi是在第i个位置插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的次数的期望值为
Eis=∑n+1i=1pi(n－i+1)
不失一般性，我们假设在线性表中的任何位置插入元素是等概率的，即pi=1n+1，则
Eis=∑n+1i=1pi(n－i+1)=∑n+1i=11n+1(n－i+1)=n2

所以，在顺序表中的插入操作约需移动一半的数据元素，其时间复杂度为O(n)。
5.删除操作
设线性表L=(a1,a2,…,ai－1,ai,ai+1,…,an)，删除第i个元素ai，则L变为(a1,a2,…,ai－1,ai+1,…,an)。删除ai使得ai－1、ai和ai+1的逻辑关系发生了变化，并且L的长度由n变为n-1。显然，删除的位置i满足1≤i≤n。如果i=n，则只需删除an即可；如果1≤i≤n-1，则需将ai+1~an依次向前移动一个位置。算法描述如下：

int SqListDelete(SqList &L,int i){
int j;
if(i<1||i>L.length)return ERROR;//删除位置不合法
for(j=i-1;j<L.length-1;j++)L.elem［j］=L.elem［j+1］;//删除位置之后的元素依次前移
--L.length;//表长减1
return OK;
}

下面对删除算法的时间复杂度进行分析。删除算法的主要操作仍是移动元素，而移动元素的个数取决于删除的位置和线性表的长度。
假设qi是在第i个位置删除一个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的次数的期望值为
Edl=∑ni=1qi(n－i)
我们假设在线性表中的任何位置删除元素是等概率的，即pi=1n，则
Edl=∑ni=1pi(n－i)=∑n+1i=11n(n－i)=n－12

所以，在顺序表中的删除操作约需移动一半的数据元素，其时间复杂度为O(n)。
6.按值查找
线性表中按值查找是指在线性表中查找与给定值x相等的数据元素。其方法是：从第一个元素开始依次与x进行比较，直到找到一个与x相等的数据元素，并返回它在顺序表中的位序；若查遍顺序表都没有找到与x相等的数据元素，则返回ERROR。算法描述如下：

int LocateElem(SqList L,ElemType x){
int i=1;
while(i<=L.length&&L.elem［i-1］!=x)i++;
if(i<=L.length)return i;
else return ERROR;
}

查找算法的主要操作是比较元素。在查找成功的情况下，最好情况是要找的是第一个元素，比较次数是1；最坏的情况下是要找的是第n个元素，比较次数是n。如果查找第i个元素的概率是pi，找到第i个元素所需的数据比较次数为ci，则查找成功的平均期望值为∑ni=1pici。在等概率的情况下，平均期望值为∑ni=11ni=(1+n)/2。所以按值查找算法的时间复杂度为O(n)。

7.依次输出线性表中的所有元素

void DispSqList(SqList L){//输出顺序表
int i;
for(i=0;i<L.length;i++)printf("%d",L.elem［i］);
printf("\\\\n");
}

2.2.3顺序表的应用举例

例1将顺序表La=(a1,a2,…,ai－1,ai,ai+1,…,an)逆置。
解要想将La逆置，只需将第一个元素和最后一个元素交换，第二个元素和倒数第二个元素交换，以此类推，直到没有元素交换为止。算法描述如下：

void Contrary_Sq(SqList &La){//将顺序表逆置
int temp;
for(i=0;i<La.length/2;i++){
temp=La.elem［i］;
La.elem［i］=La.elem［La.length-1-i］;
La.elem［La.length-1-i］=temp;
}
}

例2设顺序表La中的数据元素递增有序。试编写算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
解从顺序表La中的最后一个元素开始与x进行比较，若该元素大于x，则将该元素后移一个位置，否则将x插入到该元素的下一个位置。算法描述如下：

int Insert_OrderSq(SqList &La,ElemType x){
int i;
ElemType *p;
if(La.length>=La.listsize){//当前存储空间已满，增加分配
p=(ElemType*)realloc(La.elem,(La.listsize+ListIncrement)*sizeof(ElemType));
if(!p)exit(OVERFLOW);
La.elem=p;
La.listsize=La.listsize+ListIncrement;
}
for(i=La.length-1;x<La.elem［i］&&i>=0;i--)La.elem［i+1］=La.elem［i］;
La.elem［i+1］=x;//插入元素x
++La.length;
return OK;
}

例3
有两个顺序表La和Lb，其元素均按从小到大升序排列。编写一个算法将它们合并成一个顺序表Lc，要求Lc的元素也是从小到大升序排列。
解1)初始化Lc为空表；2)分别从La和Lb中取得当前元素Laelem［i］和Lbelem［j］；3)若Laelem［i］≤Lbelem［j］，则将Laelem［i］插入到Lc中，并取La中的下一个元素；否则将Lbelem［j］插入到Lc中，并取Lb中的下一个元素；4)重复步骤3直至La或Lb中元素被取完为止；5)将La表或Lb表中剩余元素插入到Lc表中。算法描述如下：

void mergelist_Sq(SqList La,SqList Lb,SqList &Lc){//两个有序表的归并
int i,j,k;
InitSqList(Lc);
i=0;j=0;k=0;
while(i<Lalength&&j<Lblength){
if(Laelem［i］<=Lbelem［j］) Lc.elem［k++］=La.elem［i++］;
else Lc.elem［k++］=Lb.elem［j++］;
}
while(i<La.length)Lc.elem［k++］=La.elem［i++］;//将La中剩余元素插入到Lc中
while(j<Lb.length)Lc.elem［k++］=Lb.elem［j++］;//将Lb中剩余元素插入到Lc中
Lc.length=La.length+Lb.length;
}

由于上述算法的基本操作是元素赋值，所以算法的时间复杂度为O(La.length+Lb.length)。