顺序表

川长思鸟来 2023-06-29 12:59 1阅读 0赞

顺序表的定义与基本运算的实现

需要注意下面两个操作：

**插入操作：**

**　　**该运算在顺序表L的第*i*（1≤*i*≤ListLength(L)+1）个位置上插入新的元素*e*。如果i值不正确，则显示相应错误信息；否则将顺序表原来第*i*个元素及以后元素均后移一个位置，移动方向从右向左，如下图所示，腾出一个空位置插入新元素，最后顺序表长度增1。

![20200508230401555.png][]

时间复杂度和空间复杂度分析：

对于本算法来说，元素移动的次数不仅与表长L.length=n有关，而且与插入位置*i*有关:当*i*=*n*\+1时，移动次数为0；当*i*=1时，移动次数为*n*，达到最大值。在线性表L中共有*n*\+1个可以插入元素的地方。假设pi（=      ![2020050823074032.png][]    ）是在第*i*个位置上插入一个元素的概率，则在长度为*n*的线性表中插入一个元素时所需移动元素的平均次数为:

![20200508230726470.png][]

其中：an-1～ai-1（共*n*\-1-(*i*\-1)+1=*n*\-*i*\+1）个元素移动

因此插入算法的平均时间复杂度为O(*n*)。

**删除操作：**

**　　**该运算删除顺序表L的第*i*（1≤*i*≤ListLength(L)）个元素。如果*i*值不正确，则显示相应错误信息；否则将线性表第*i*个元素以后元素均向前移动一个位置，移动方向为从左向右，如下图所示，这样覆盖了原来的第*i*个元素，达到删除该元素的目的，最后顺序表长度减1。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70][]

对于本算法来说，元素移动的次数也与表长*n*和删除元素的位置*i*有关:当*i*=*n*时，移动次数为0；当*i*=1时，移动次数为*n*\-1。在线性表L中共有*n*个元素可以被删除。假设pi（pi=     ![20200508231133812.png][]）是删除第i个位置上元素的概率，则在长度为*n*的线性表中删除一个元素时所需移动元素的平均次数为:

=![20200508231148775.png][]

其中：ai～an-1（共n-1-i+1=n-i个元素）均前移一个位置

因此删除算法的平均时间复杂度为O(*n*)。

将文件保存为：sqlist.cpp，以便后续调用。

详细代码如下：

#include<stdio.h>
    #include<malloc.h>
    #define MaxSize 100
    typedef int ElemType;
    //顺序表的类型定义 
    typedef struct{
    	ElemType data[MaxSize];
    	int length;
    }SqList;
    //建立顺序表 
    void CreateList(SqList *& L, ElemType a[], int  n){
    	L = (SqList *)malloc(sizeof(SqList));
    	for (int i = 0; i < n; i++)
    		L->data[i] = a[i];
    	L->length = n;
    }
    //初始化线性表 本算法的时间复杂度为O(1) 
    void InitList(SqList  * & L){
    	//初始化线性表，只需要将其长度设置为0即可
    	L = (SqList *)malloc(sizeof(SqList));
    	L->length = 0;
    }
    //销毁线性表 本算法的时间复杂度为O(1) 
    void DestroyList(SqList *&L){
    	//释放线性表L的内存空间
    	free(L);
    }
    //判断线性表是否为空 本算法的时间复杂度为O(1) 
    bool ListEmpty(SqList *L){
    	return (L->length == 0);
    }
    //求线性表的长度 本算法的时间复杂度为O(1) 
    int ListLength(SqList *L){
    	return (L->length);
    }
    //输出线性表   本算法的时间复杂度为O(L->length) 
    void DisplayList(SqList * L){
    	if (ListEmpty(L))
    		return;
    	for (int i = 0; i < L->length; i++)
    		printf("%2d", L->data[i]);
    	printf("\n");
    }
    //求线性表中某个数据元素的值 本算法的时间复杂度为O(1) 
    bool GetElem(SqList * L, int i, ElemType & e){
    	if (i<1 || i>L->length)
    		return false;
    	e = L->data[i - 1];
    	return true;
    }
    //按元素值查找 本算法的时间复杂度为O(L->length) 
    int LocateElem(SqList * L, ElemType e){
    	int i = 0;
    	while (i < L->length && L->data[i] != e)
    		i++;
    	if (i >= L->length)
    		return 0;
    	else
    		return i + 1;
    }
    //插入顺序表的元素 本算法的时间复杂度为O(n) 
    bool ListInsert(SqList *& L, int i, ElemType e){
    	if (i<1 || i>L->length + 1)
    		return false;
    	i--;//将顺序表的逻辑序号转化为物理序号
    	for (int j = L->length; j > i; j--)
    		L->data[ j ] = L->data[ j- 1];//将元素后移一个位置
    	L->data[i] = e;//插入元素e
    	L->length ++;//顺序表的元素增加1
    	return true;
    }
    //删除顺序表的元素  本算法的时间复杂度为O(n) 
    bool ListDelete(SqList *& L, int i, ElemType &e){
    	if (i<1 || i>L->length)
    		return false;
    	i--;//将顺序表的逻辑序号转化为物理序号
    	e = L->data[i];
    	for (int j = i; j < L->length;j++)
    		L->data[ j ] = L->data[ j + 1];//将元素左移一个位置
    	L->length--;//顺序表的元素增加1
    	return true;
    }

测试用例：

#include<stdio.h>
    #include"sqlist.cpp"
    //假设线性表以顺序表表示 
    int main(int argc,char * argv[])
    {
    	SqList *L;
    	ElemType e;
    	int a[]={1,3,1,4,2};
    	InitList(L);//初始化线性表
    	printf("ListLength(L)=%d\n",ListLength(L)); //输出线性表的长度
    	CreateList(L,a,5);//数组名代表数组元素的首地址 
    	printf("L:");
    	DisplayList(L);
    	printf("ListLength(L)=%d\n",ListLength(L)); //输出线性表的长度
    	printf("ListEmpty(L)=%d\n",ListEmpty(L));
    	GetElem(L, 3, e);
    	printf("e=%d\n",e);
    	printf("LocateElem(L,1)=%d\n",LocateElem(L,1));
    	ListInsert(L,4,5);
    	printf("L:");
    	DisplayList(L);
    	ListDelete(L,3,e);
    	printf("L:");
    	DisplayList(L);
    	DestroyList(L);
    	return 0;
    }

[20200508230401555.png]: https://img-blog.csdnimg.cn/20200508230401555.png
[2020050823074032.png]: https://img-blog.csdnimg.cn/2020050823074032.png
[20200508230726470.png]: https://img-blog.csdnimg.cn/20200508230726470.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200508231048788.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2MjYxNDIx,size_16,color_FFFFFF,t_70
[20200508231133812.png]: https://img-blog.csdnimg.cn/20200508231133812.png
[20200508231148775.png]: https://img-blog.csdnimg.cn/20200508231148775.png