类C语言实现顺序表中的基本操作

自己在学习数据结构中(DS)写得程序，和大家一起分享，可能存在不足和缺漏的地方，感谢大家的指正和理解。

首先是一些变量的声明（typedef），然后是定义顺序表的类型（里面含有数组（存储数据元素）和表长），再接下来是对线性表SqList进行的增删改查，最后是自己的测试样例（针对于插入和删除）。

代码展示：

#define MAXSIZE 100
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2typedef int Status;
typedef int ElemType;#include <iostream>
using namespace std;
typedef struct
{ElemType *elem;int length;
}SqList;		//定义顺序表的类型//顺序表的初始化
Status InitList(SqList &L)
{//构造一个空的顺序表LL.elem = new ElemType[MAXSIZE];		//为顺序表分配一个大小为MAXSIZE的数组空间if(!L.elem) exit (OVERFLOW);		//存储分配失败L.length=0;							//空表的长度为0return OK; 
}//销毁线性表 
void DestroyList(SqList &L)
{if(!L.elem) delete L.elem;			//释放存储空间 
}//清空线性表L
void ClearList(SqList &L)
{L.length = 0;						//将线性表的长度置为0 
} //求线性表的长度
int GetLength(SqList L)
{return (L.length);
}//判断线性表是否为空
int IsEmpty(SqList L)
{if(L.length == 0)	return 1;else return 0;
} //顺序表的取值
Status GetElem(SqList L, int i, ElemType &e)      
{if(i<1||i>L.length) return ERROR;	//判断i值是否合理，若不合理，返回ERRORe = L.elem[i-1];					//elem[i-1]单元存储第i个元素return OK; 						
}//顺序表的查找 
int LocateElem(SqList L, ElemType e)
{//在线性表L中查找值为e的数据元素，返回其序号（是第几个元素）for(int i=0; i<L.length; i++){if(L.elem[i]==e)	return i+1;		//查找成功，返回序号return 0;							//查找失败，返回0 } 
} //顺序表的插入
Status ListInsert(SqList &L, int pos, ElemType e)
{	//1.判断插入位置是否合法 if(pos<1||pos>L.length+1)	return ERROR;//2.判断当前存储空间是否满 if(L.length==MAXSIZE)	return ERROR;//3.将数组中最后一个至第pos个位置的元素依次向后移动，空出第pos个位置//（pos=n+1时无需移动） //4.将要插入的新元素e 放入到第pos个位置//5.表长加1 for(int i=L.length-1; i>=pos-1;i--) L.elem[i+1]=L.elem[i];				//插入位置及之后的元素后移 L.elem[pos-1] = e;			//将新元素e放到第pos个位置 L.length++;					//表长加1 return OK;
}//顺序表的删除
Status	ListDelete(SqList &L, int i)
{//在顺序表L中删除第i个元素，i的合法取值范围：1<=i<=L.lengthif((i<1)||(i>L.length))		return ERROR;	//i值不合法for(int j=i; j<=L.length-1; j++)L.elem[j-1]=L.elem[j];		//被删除元素之后的的元素前移L.length--;					//表长减1return OK; 
} int main()
{SqList L;//线性表初始化(空的线性表)InitList(L);//插入测试样例 ListInsert(L,1,1);ListInsert(L,2,2);ListInsert(L,3,3);ListInsert(L,4,4);ListInsert(L,5,5);//看能否插入成功//输出这个线性表ListInsert(L,1,100);//上述的运行结果：100 1 2 3 4 5 //测试删除元素：ListDelete(L,4);	//100 1 2 4 5for(int i=0; i<L.length; i++){cout<<L.elem[i]<<" ";}
}

操作的说明：初始化，销毁，清空，求表长，判空，取值代码比较简短，理解起来容易一点，其中取值便是利用了数组的随机存取性质，因为你给定一个下表，数组便能对应到其元素，因此算法时间复杂度为O（1）。

接下来我对查找，插入，删除进行相应的算法描述和对应的时间复杂度分析。

时间复杂度分析时引入平均查找长度的概念（ASL），它是在查找时，为了确定元素在顺序表中的位置，需要和给定值进行比较的数据元素个数的期望值。

$ASL=\sum piCi$

其中pi是查找第i个元素的概率，Ci是找到表中其关键字与给定值相等的第i个记录时，和给定值已经比较的关键字个数。

顺序表的查找：

（1）从第一个元素起，依次和e值比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1。

（2）若查找整个顺序表都没有找到，则查找失败，返回0。

算法分析：从顺序表的查找过程可见，Ci取决于所查元素在表中的位置。例如：查找表中第一个记录时，只需比较一次；而查找表中最后一个记录时，则需比较n次。一般情况下Ci=i。

假设每个元素的查找概率相等，即pi=1/n

则ASL=1/n $\sum$ i=(n+1)/2

由此可见，顺序表按值查找算法的平均时间复杂度为O（n)。

顺序表的插入：

（1）判断插入位置是否合法（pos的合法范围是1<=i<=n+1），若不合法则返回ERROR。

（2）判断顺序表的存储空间是否已满，若满则返回ERROR。

（3）将第n个至第pos个位置的元素依次向后移动一个位置，空出第pos个位置（pos=n+1时无需移动）。

（4）将要插入的新元素放入第i个位置。

（5）表长加1。

补充说明：上述算法没有处理动态的扩容，因此当表达到预设的最大空间时，则不能再插入元素。

算法分析：当在顺序表中某个位置插入一个数据元素时，其时间主要消耗在移动元素上，而移动元素的个数取决于插入元素发位置。

我们不妨设移动的元素的次数为x,给定插入的位置为i,长度为n的线性表总共可以插入的元素位置有n+1个。我们发现它们之间的关系是n+1=x+i。

当插入的位置n+1,我们对原数组不需要进行任何操作，移动次数x=0。

插入的位置为n时，我们需要将初始最后一个元素移动，腾出那个空间放e,前面的数据元素保持不变，移动次数x=1。

当插入的位置为1时，我们需要将所有的数据元素（n）个都要向后移动，腾出的第一个位置放新元素e。移动的次数x=n。

可能有人会问：为什么第一个位置的前面不可以插入元素？

在大多数编程语言中，数组是一种线性数据结构，它允许你存储一系列的元素，并通过索引来访问这些元素。数组的一个重要特性是它有固定的长度，一旦创建，其大小通常不能改变。这意味着你不能在数组的“第一个位置前面”插入元素，因为数组的第一个位置（索引为0的位置）已经是数组的开始。而我们可以在结尾插入元素。

为什么在对数组进行插入操作时，需要将数据元素往后挪动一个位置？

在对数组进行插入操作时，需要将数据元素往后挪动一个位置，这主要是因为数组是一种固定长度的数据结构，其元素在内存中是连续存储的。当你想在数组的某个特定位置插入一个新元素时，必须确保新元素能够找到合适的空间来存放，同时不覆盖或丢失原有元素的数据。

不失一般性，可以假定在线性表中的任何位置(n+1)插入元素都是等概率的，即Pi=1/n+1

根据ASL的公式：Eins =1/n+1 $\sum$ (n-1+1)=n/2

由此可见，顺序表插入算法的平均时间复杂度为O（n）。

顺序表的删除：

算法描述：

（1）判断删除位置i是否合法（1<=i<=n+1），若不合法返回ERROR。

（2）将第i+1个至第n个元素依次向前移动一个位置（i=n时无需移动）。

（3）表长减1。

算法分析：

当在顺序表中某个位置删除一个数据元素时，其时间主要消耗在移动元素上，而移动元素的个数取决于删除元素的位置。

不失一般性，可以假定在线性表中的任何位置上删除元素都是等概率的，即pi=1/n。

我们可以发现移动次数x=n-i。

当删除的位置i=n，移动次数x=0

i=n-1,x=1。

i=1,x=n-1(除第一元素外，剩下的n-1个元素往前移动一个位置)。

Edel=1/n $\sum$ (n-i)=(n-1)/2。

由此可见，顺序表删除算法的平均时间复杂度为O（n）。

顺序表可以随机存取任一元素，其存储位置可以用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入删除操作时，需要移动大量元素。另外由于数组有长度相对固定性的静态特性，当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。所有这些问题，都可以通过线性表的另一种表示方法——链式存储结构来解决。