数据结构：顺序表详解（C语言实现）

点滴：别给自己的懒惰找借口，今日事今日毕

本文纲领：

• 介绍顺序表的概念及其性质
• 基本运算：创建、初始化、销毁、判空、求表长、输出、获取元素、查找、插入、删除
• 用一个程序整体实现上面的部分重要运算

顺序表的理解

1. 线性表的顺序存储结构 简称为 顺序表（Sequential list），是线性表 最常用 的存储方式。
2. 顺序表把线性表中的所有元素 按照逻辑顺序 依次存储到一块连续的存储空间中，在顺序表中，两个逻辑上相邻的元素在存储位置上也相邻，所以称为 直接映射 。
3. 在 C/C++ 中，借助 数组 来实现顺序表，也就是说，用数组来存放顺序表的元素及其逻辑关系，数组的元素类型就是线性表的元素类型，数组的大小必须 大于等于 线性表的长度，否则该数组不能装下该线性表。
4. 声明顺序表时，定义一个 data数组 来存储表中的所有元素，以及定义 length整型变量 来存储表的 实际长度，采用 结构体类型 Sqlist 表示如下：

    #define Maxsize 50
    typedef struct{
   	ElemType data[Maxsize];
   	int length;
    } Sqlist;
   

顺序表的基本运算

1. 为简便运算，假设 ElemType 为 int 类型，可使用以下 自定义类型 语句：

    typedef int ElemType;
   

   注意，至少在本文算法中，顺序表元素的 逻辑序号 是从1开始的，而对应的顺序表的data[]元素的下标（又称 物理序号 ）是从0开始的。
2. 本文以顺序表指针来使用顺序表，用Sqlist *L来定义，用L->length来引用length域。
   • 采用顺序表指针主要是为了方便顺序表的释放算法设计，而在函数之间以顺序表指针的形式来传递参数更节省空间。
3. 创建顺序表：
   • 目标：将数组a[0...n-1]中的n个元素全部放到顺序表中。
   • 程序实现：

      void CreateList(Sqlist *&L, ElemType a[], int n){
      //从a中的n个元素建立线性表 
      	int i=0,k=0;	//i用于遍历数组a，k表示L中的元素个数 
     	L = (Sqlist *)malloc(sizeof(Sqlist));	//动态分配一个存放线性表的空间 
     	while(i<n){	//n代表数组a的长度，即让i遍历数组a的每一个元素 
     		L->data[k] = a[i];	//将数组中的元素放到L中 
     		k++; i++;
     	}
     	L->length = k;	//设置L的长度为k(k此时等于n) 
      }
     

     • 当创建完对应的顺序表 L 之后，需要回传给对应的实参，即 L 是输出型参数，所以需要在 L 前面加上引用符& 。
4. 初始化顺序表：InitList(&L)
   • 目标：构造一个空的顺序表。
   • 分析：实际上只需要将顺序表的 length 域设置为 0 即可。
   • 程序实现：

      void InitList(Sqlist *&L){
      	L = (Sqlist *)malloc(sizeof(Sqlist)); //为顺序表分配空间
      	L -> length = 0; //设置顺序表的长度为0
      }
     

     • 时间复杂度为 O(1)
5. 销毁顺序表：DestroyList(&L)
   • 目标：释放顺序表 L 占用的内存空间
   • 分析：此处的顺序表的空间是通过 malloc() 分配的，当不再使用此顺序表时务必调用此基本运算来释放存储空间，否则，尽管系统会自动释放顺序表指针变量L，但不会自动释放L所指向的存储空间，如此可能会造成内存泄漏。
   • 程序实现：

      void DestroyList(Sqlist *&L){
      	free(L);	//释放 L 所指向的顺序表空间
      }
     

     • 时间复杂度为 O(1)
6. 判断是否为空表：ListEmpty(L)
   • 目标：返回一个布尔值表示 L 是否为空表，若 L 为空表就返回 true，否则返回 false.
   • 程序实现：

      bool ListEmpty(Sqlist *L){
      	return (L->length == 0);
      }
     

     • 时间复杂度为 O(1)
7. 求顺序表的长度：ListLength(L)
   • 目标：返回顺序表的长度
   • 分析：实际上只需要返回 length 域的值即可
   • 程序实现：

      int ListLength(Sqlist *L){
      	return (L->length);
      }
     

     • 时间复杂度为 O(1)
8. 输出顺序表：DispList(L)
   • 目标：依次显示 L 中各元素的值
   • 程序实现：

      void DispList(Sqlist *L){
      	for(int i=0; i<L->length; i++){ //遍历顺序表输出各元素值
      		printf("%d, ",L->data[i]);
      	}
      	printf("\n");
      }
     

     • 时间复杂度为 O(n)，其中 n 为元素个数
9. 求顺序表中指定 逻辑序号 的元素值：GetElem(L, i, &e)
   • 目标： 给定序号 i ，输出表中的第 i 个元素值，没有则返回 false
   • 程序实现：

      bool GetElem(Sqlist *L, int i, ElemType &e){
      	if(i<1 && i>L->length) //此时序号i不合法
      		return false;
      	e = L->data[i-1]; //注意逻辑序号与物理序号的区别
      	return true;
      }
     

     • 时间复杂度为 O(1)
10. 按元素值查找：LocateElem(L, e)
    • 给定元素 e，查找表中第一个与 e 相等的元素的逻辑序号，返回逻辑序号，没有则返回 0
    • 程序实现：

       int LocateElem(Sqlist *L, ElemType e){
       	int i=0;
          while( i<L->length && L->data[i]!=e )
          	i++;
          if( i>=L->length )	//表示没有此元素
          	return 0;	//返回0
          else	//否则即为有此元素
          	return i+1;	//返回其逻辑序号
       }
      

      • 时间复杂度为 O(n)
11. 插入数据元素：ListInsert(&L, i, e)
    • 目标：在第 i 个位置 (1<= i <=n+1)上插入元素 e ，若 i 不合法则返回 false ，否则插入元素并返回 true。
    • 程序实现：

       bool ListInsert(Sqlist *&L, int i, ElemType e){
       	int j;
       	if(i<1 || i>L->length+1) //i不合法
       		return false;
       	i--; //将逻辑序号转化为物理序号，方便操作
       	for(j=L->length; j>i; j--){ //从最后往前，依次将元素后移一位，刚好空出第i个
       		L->data[j] = L->data[j-1];
       	}
       	L->data[i] = e; //将元素 e 填入第 i 个位置
       	L->length++; //L的长度加1
       	return true;
       }
      

      • 时间复杂度为 O(n)
12. 删除数据元素：ListDelete(&L, i, &e)
    • 目标：删除第 i 个位置( 1<=i<=n )的元素，若 i 不合法，则返回 false，否则就删除元素并返回 true 。
    • 程序实现：

       bool ListDelete(Sqlist *&L, int i, ElemType &e){
       	int j;
       	if( i<1 || i>L->length ) //如果i不合法
       		return false;
       	i--; //将逻辑序号转化为物理序号，方便之后操作
       	e = L->data[i]; //e代表的是删除的哪个元素
       	for( j=i; j<L->length-1; j++ ){ //从i到最后一个元素，所有的元素都往前移一位
       		L->data[j] = L->data[j+1];
       	}
       	L->length--; //删除之后，顺序表的长度减1
       	return true;
       }
      

      • 时间复杂度为 O(n)

整体实现：创建、输出、销毁

 /*目标：
 将已知数组num[n]中的元素移到顺序表的数组data[]中，并完成基本运算
 */
 #include<stdio.h>
 #include<stdlib.h>
 #define Maxsize 50 //数组的最大长度

 typedef struct { //结构声明 
	int data[Maxsize]; //待接收元素的数组 
	int length;	//数组的长度 
 } Sequence;

 Sequence List; //定义结构变量，变量名为List 
 Sequence *Sqlist; //定义结构指针为Sqlist,即Sqlist可以指向任意Sequence类型的变量

 //创建顺序表
 void CreateList(Sequence *&L, int ret[], int max);
 /* 详细说明一下这里的 'Sequence *&L'
   可以这样想：现在已经在主函数里面实现了用 'Sqlist->length'代表data[]的长度
   我们需要做的是在 CreateList()函数中也弄出一个和Sqlist有着相同功能的即可
   对比一下，那么之前我们是如何定义Sqlist的呢？现在我们只是照猫画虎地在参数列表里面这样做即可
   之后的如何实现参数对应以此类推
 */
 //输出顺序表
 void DispList(Sequence *M);
 //销毁顺序表
 void  DestroyList(Sequence *&N);

 int main() {
	Sqlist = &List; //将Sqlist指向List变量
	//输入数组
	int num[Maxsize];
	for (int i = 0; i < 5; i++) {
		scanf("%d", &num[i]);
	}
	//创建顺序表
	CreateList(Sqlist, num, 5);
	//输出顺序表
	DispList(Sqlist);
	//销毁顺序表
	DestroyList(Sqlist);
	return 0;
 }

 //创建顺序表
 void CreateList(Sequence *&L, int ret[], int max) {
	//传参数分别为: 用L接收List的地址,用ret[]接收num[],用max接收数组长度n 
	int i = 0, k = 0;
	L = (Sequence *)malloc(sizeof(Sequence)); //动态分配一个存放顺序表的空间
	while (i < max) { //max代表数组ret的长度，即让i遍历数组ret[]的每一个元素 
		L->data[k] = ret[i];	//将数组中的元素放到L中
		k++; i++;
	}
	L->length = k; //设置L的长度为k(k此时等于n)
	printf("%d,%d\n", L->data[0], L->length);
 }
 //输出顺序表
 void DispList(Sequence *M) {
	printf("\nThe length is %d\n", M->length);
	for (int i = 0; i < M->length; i++) { //遍历顺序表输出各元素值
		printf("%d, ", M->data[i]);
	}
	printf("\n");
 }
 //销毁顺序表
 void  DestroyList(Sequence *&N) {
	//传参为：用L接收List的地址 
	free(N); //释放 L 所指向的顺序表空间
 }