数据结构-线性表的顺序表示

前言

本篇文章介绍线性表的基本概念，并使用顺序存储结构实现线性表。
本篇文章使用的程序设计语言为C语言，需要读者掌握C语言的指针、结构体和动态内存管理的知识。
如果您对C语言的指针不熟悉，请阅读https://blog.csdn.net/pyc68/article/details/135181228
如果您对C语言的结构体不熟悉，请阅读https://blog.csdn.net/pyc68/article/details/135211015
如果您对C语言的动态内存管理不熟悉，请阅读https://blog.csdn.net/pyc68/article/details/135737056

一、线性表

1.1 线性表的概念

概念：线性表是具有相同特性的数据元素的一个有限序列
$$\underbrace{(a_1,a_2,\cdots ,a_{i-1},a_i,a_{i+1},\cdots ,a_n)}$$

数据元素$a_1$称为线性表的起始结点
数据元素$a_n$称为线性表的终端结点
数据元素$a_{i-1}$称为数据元素$a_i$的直接前驱
数据元素$a_{i+1}$称为数据元素$a_i$的直接后继
下标$i$，称为数据元素的序号，表示数据元素在线性表中的位置，称为第$i$个数据元素$（1\le i\le n）$
$n$表示数据元素的总个数，即线性表的长度，当$n=0$时，称为空表；当$n>0$时，称为非空线性表

1.2 线性表的逻辑特征

在非空线性表中，线性表有以下特征

• 有且仅有一个起始结点$a_1$，它没有直接前驱，仅有一个直接后继$a_2$
• 有且仅有一个终端结点$a_n$，它没有直接后继，仅有一个直接前驱$a_{n-1}$
• 其余的内部结点$a_i（2\le i\le n）$都有且仅有一个直接前驱$a_{i-1}$和一个直接后继$a_{i+1}$

二、线性表的抽象数据类型

线性表的抽象数据类型定义如下：

ADT List
{数据对象: D={ai | ai属于数据元素集合,(i=1,2,...n,n ≥ 0)​};数据关系: S={<a(i-1),ai>| a(i-1),ai属于D(i=2,3,...,n)}基本操作:createNullList(&L)操作结果:创建一个空表destroyList(&L)初始条件:线性表L存在操作结果:销毁一个线性表LclearList(&L)初始条件:线性表L存在操作结果:将线性表L重置为一个空表isEmpty(L)初始条件:线性表L存在操作结果:判断线性表L是否为空表listLength(L)初始条件:线性表L存在操作结果:返回线性表L中的元素个数		getElem(L,i,&e)初始条件:线性表L存在，1<= i <= listLength(L)操作结果:用e返回线性表L中第i个数据元素的值locateElem(L,e,compare())初始条件:线性表L存在，compare()是数据元素判断函数操作结果:返回L中第1个与e满足compare()的数据元素的序号i(1 <= i <= listLength(L))若这样的数据元素不存在则返回0	priorElem(L,cur_e,&pre_e)初始条件:线性表L存在操作结果:若cur_e是L的数据元素，且不是起始结点，则用pre_e返回它的前驱结点否则操作失败，pre_e无意义nextElem(L,cur_e,&next_e)初始条件:线性表L存在操作结果:若cur_e是L的数据元素，且不是终端结点，则用next_e返回它的后继结点否则操作失败，next_e无意义				insertElem(&L,i,e)初始条件:线性表L存在，1<= i <= ListLength(L)+1操作结果:在线性表的第i个位置插入一个元素e，L的长度加1deleteElem(&L,i)初始条件:线性表L存在，1<= i <= listLength(L)操作结果:删除线性表的第i个元素，L的长度减1traverseList(&L,visited())初始条件:线性表L存在操作结果:依次对线性表中每个元素调用visited()}ADT List

三、线性表的顺序表示和实现

3.1 线性表的顺序表示

顺序表的顺序表示又称为顺序存储结构或顺序映像
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构

线性表$$(a_1,a_2,\cdots ,a_{i-1},a_i,a_{i+1},\cdots ,a_n)$$
顺序存储$$\underline{\overline{\cdots |a_1|a_2|\cdots |a_{i-1}|a_i|a_{i+1}|\cdots |a_n|\cdots }}$$
$a_1$的存储位置称为线性表的起始位置或基地址
线性表顺序存储结构占用一片连续的存储空间，知道某个元素的存储位置就可以计算其他元素的存储位置
假设线性表的每个元素占用$c$个存储单元，则第$i+1$个数据元素的存储位置和第$i$个数据元素的存储位置之间满足关系（用$loc(a_i)$表示数据元素的存储位置）$$loc(a_{i+1})=loc(a_i)+c$$
由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得出:
$$loc(a_i)=loc(a_1)+(i-1)\times c$$

3.2 基本操作的实现

基本操作的实现，在C语言使用函数表示基本操作
使用结构体类型定义一个线性表

//定义返回值状态码
#define SUCCESS 1
#define ERROR   0//这里假设元素的数据类型为char
typedef char ElemType;//定义一个线性表
struct SeqList {int MAXNUM;			//线性表的最大容量（元素个数）int n;				//线性表中实际的元素个数，n <= MAXNUMElemType* element;	//存放线性表元素,element[0],element[1]...element[n-1]
};//定义一个SeqList的指针类型
typedef struct SeqList* PSeqList;

由于线性表的基本操作较多，这里只介绍一些常见的操作，文章末尾提供了完整代码的gitee地址
由于是使用顺序存储结构实现线性表，此时可以称线性表为顺序表

1. 创建空顺序表
   step1:首先使用malloc()函数创建一个struct SeqList大小的空间
   step2:然后使用malloc()函数创建一个(sizeof(ElemType)*m)大小的空间
   step3:将MAXNUM设置为m，将n设置为0（表示当前顺序表为空）

   //2.1 创建一个空顺序表
   PSeqList createNullList_seq(int m)
   {PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList));if (NULL == palist)				//判断申请空间是否成功{printf("malloc Fail!\n");return NULL;}palist->element = (ElemType*)malloc(sizeof(ElemType) * m);if (NULL == palist->element)	{printf("malloc Fail!\n");free(palist);palist = NULL;return NULL;}palist->MAXNUM = m;palist->n = 0;return palist;
   }
   

2. 销毁顺序表
   由于这里使用malloc()创建SeqList结点，则需要使用二级指针才能完成

   //2.2 销毁一个顺序表
   void destroyList_seq(PSeqList* palist)
   {assert(*palist);assert((*palist)->element);free((*palist)->element);(*palist)->element = NULL;free(*palist);*palist = NULL;
   }
   

3. 顺序表的查找
   从表的一端开始，逐个进行比较。找到返回该元素的位置序号，否则返回ERROR（表示未找到）

   //2.6 查找与指定值e相同数据元素的位置
   int locateElem_seq(PSeqList palist, ElemType e)
   {assert(palist);int i = 0;for (i = 0; i < palist->n; i++)if (e == palist->element[i])return i + 1;            //i+1表示第几个元素，即element[i]return ERROR;
   }
   

   算法分析
   平均查找长度ASL(Average Search Length)：为确定数据元素在表中的位置，需要与给定值进行比较的关键字的个数的期望叫做查找算法的平均查找长度。
   对于n个数据元素的表，查找成功时$$ASL=\underset{i=1}{\sum ^n}{P}_i{C}_i$$
   $P_i$为第i个数据元素被查找的概率
   $C_i$找到第$i$个数据元素需要比较的次数
   顺序查找的平均查找长度:$$ASL=P_1+2P_2+\cdots +(n-1)Pn-1+n{P}_n$$
   根据以上得出被查找元素位置$i$与查找次数的关系$$C_i=i$$
   假设每个数据元素被查找的概率相等，有$n$个数据元素，则$$P_i=\frac{1}{n}$$
   那么可得，
   $$AS{L}_{ss}=\underset{i=1}{\sum ^n}{P}_i{C}_i=\frac{1}{n}\underset{i=1}{\sum ^n}i=\frac{n+1}{2}$$
   $其中\underset{i=1}{\sum ^n}i=\frac{n(n+1)}{2}$
   算法时间复杂度$T(n)=O(n)$
   算法空间复杂度$S(n)=O(1)$

4. 顺序表的插入
   顺序表的插入运算是指在表中的第$i(1\le i\le n+1)$个位置上，插入一个新结点e，使长度为$n$的顺序表变成长度为$n+1$的顺序表
   $$(a_1,\cdots ,a_{i-1},a_i,\cdots ,a_n)⟶(a_1,\cdots ,a_{i-1},e,a_i,\cdots ,a_n)$$
   算法思想：
   step1:判断插入位置$i$是否合法（合法值$1\le i\le n+1$）
   step2:判断顺序表的存储空间是否已满，若满则返回ERROR
   step3:将第n至第i个位置的数据元素依次向后移动一个位置，空出第$i$个位置
   step4将要插入的新元素$e$放入第$i$个位置
   step5:表长加1，插入成功返回SUCCESS
   代码实现如下:

   //2.7 在指定位置插入一个数据元素
   //假设插入位置为i,插入到第i个位置，即插入到下标为i-1的位置
   int insertElem_seq(PSeqList palist, int i, ElemType e)
   {assert(palist);if (i < 1 || i > (palist->n + 1))return ERROR;if (palist->n == palist->MAXNUM)return ERROR;int j = 0;for (j = (palist->n - 1); j >= (i - 1); j--)    //将下标为i-1以及后面的元素往后移动palist->element[j + 1] = palist->element[j];palist->element[i - 1] = e; //将下标为i-1的位置放入epalist->n += 1;    //顺序表元素个数+1return SUCCESS;
   }
   

   插入算法的分析：
   算法时间主要消耗在数据元素移动的操作上
   假设顺序表中有n个数据元素，那么
   插入位置$i=1$时，移动元素的次数为n
   插入位置$i=2$时，移动元素的次数为n-1，…
   插入位置$i=n+1$时，移动元素的次数为0
   根据以上得出插入位置$i$和数据元素移动次数的关系$$C_i=n+1-i$$
   设每个位置被插入的概率相同，插入位置为$n+1$个，则$$P_i=\frac{1}{n+1}$$
   那么可得，
   $$\begin{array}{rl}\underset{i=1}{\sum ^{n+1}}{P}_i{C}_i=\frac{1}{n+1}\underset{i=1}{\sum ^{n+1}}(n+1-i)& =\frac{1}{n+1}(n+\cdots +1+0)\\ & =\frac{1}{n+1}\frac{n(n+1)}{2}\\ & =\frac{n}{2}\end{array}$$
   算法时间复杂度$T(n)=O(n)$
   算法空间复杂度$S(n)=O(1)$

5. 顺序表的删除
   顺序表的删除运算是指将表的第$i$个数据元素删除，是长度为$n$的顺序表变成长度为$n-1$的顺序表
   $$(a_1,\cdots ,a_{i-1},a_i,a_{i+1},\cdots ,a_n)⟶(a_1,\cdots ,a_{i-1},a_{i+1},\cdots ,a_n)$$
   算法思想：
   step1:判断删除的位置$i$是否合法（合法值$1\le i\le n$）
   step2:将第$i+1$至第n位的数据元素依次向前移动一个位置
   step3:表长减1，删除成功返回SUCCESS
   代码实现

   //2.8 在指定位置删除一个数据元素
   //假设删除位置为i,删除第i个位置，即删除下标为i-1位置的元素
   int deleteElem_seq(PSeqList palist, int i)
   {assert(palist);if (i < 1 || i > palist->n)return ERROR;int j = 0;for (j = i; j <= palist->n-1; j++)palist->element[j - 1] = palist->element[j];  //将下标为i以及后面的元素往前移palist->n -= 1;  //顺序表元素个数-1return SUCCESS;
   }
   

   删除算法的分析：
   算法时间主要消耗在数据元素移动的操作上
   假设顺序表中有n个数据元素，那么
   删除位置$i=1$时，需要往前移动n-1次
   删除位置$i=2$时，需要往前移动n-2次，…
   删除位置$i=n$时，需要往前移动0次
   根据以上得出删除位置和数据元素移动次数的关系$$C_i=n-i$$
   设每个位置被删除的概率相同，删除位置为$n$个，则$$P_i=\frac{1}{n}$$
   那么可得，
   $$\begin{array}{rl}\underset{i=1}{\sum ^n}{P}_i{C}_i=\frac{1}{n}\underset{i=1}{\sum ^n}(n-i)& =\frac{1}{n}(n-1+\cdots +1+0)\\ & =\frac{1}{n}\frac{n(n-1)}{2}\\ & =\frac{n-1}{2}\end{array}$$
   算法时间复杂度$T(n)=O(n)$
   算法空间复杂度$S(n)=O(1)$

3.3 线性表的顺序表示的优缺点

• 优点
  存储密度大（结点本身所占存储量/结点结构所占存储量）
  可以随机存取任意一个数据元素，即可以根据基地址计算其他数据元素的存储位置后进行存取
• 缺点
  在插入、删除一个数据元素时，需要进行数据元素移动操作，时间复杂度较高
  属于静态存储形式，数据元素个数不可随意扩充，一次性申请一块sizeof(ElemType)*MAXNUM大小的存储空间，当数据元素的个数等于MAXNUM时，无法再进行插入新的数据元素；当数据元素的个数小于MAXNUM时，又会剩余存储空间，导致存储空间的浪费。

线性表的顺序表示适合对数据元素进行大量的随机存取操作，但不适合进行大量的插入、删除操作。

总结

完整代码:https://gitee.com/PYSpring/data-structure/tree/master