【数据结构】一文讲解线性表之次序表概念及其根本操作(附C语言源码) ...

1. 前文我们讲过数据结构的三个部分：数据、数据元素和数据结构以及数据结构的三要素：逻辑结构、物理结构和数据运算。现在我们从三个组成部分和三要素讲解

复制代码

线性表的定义和根本操作

定义

线性表是一个抽象的概念，一般具有相同数据类型的n(n>=0)个数据元素的有限序列，此中n为表长。（是不是感觉类似数组，但数组不是线性表，但也具有线性表的一些特性）
线性表指的是数据元素通过线性的逻辑结构连接的一种数据结构。
数据元素之间是线性关系，形如A->B->C…->N
根本概念

• 空表 n=0,线性表长度为0
  
• 位序 线性表中第i个数据元素
  
• 表头元素 线性表中第一个数据元素
  
• 表尾元素 线性表中最后一个数据元素
  
• 数据元素之间存在一对一的线性关系，即每个元素（除第一个外）有且仅有一个前驱，每个元素（除最后一个外）有且仅有一个后继。
  

根本操作

线性表的根本操作指的是几个根本的数据运算，一般都有如下几个操作：

• 建立表
  
• 初始化表
  
• 插入
  
• 删除
  
• 查找
  

下面就讲解一下线性表中的线性表中的次序表的概念以及根本操作
次序表

线性表定义了数据结构的逻辑结构为线性，而次序表则定义其物理结构为连续的，次序的线性表。即用次序储存的方式实现线性表（逻辑上相邻的元素在次序上也相邻）
次序表的建立与初始化

1. *******************************静态分配******************************************
2. // 定义线性表的最大长度
3. #define MAX_SIZE 100
5. // 定义线性表的结构体
6. typedef struct {
7.         ElemType data[MAX_SIZE]; // 存储数据的数组   数组的存储方式为顺序的
8.         int length; // 当前线性表的长度
9. } SeqList; //定义顺序表的名字
11. // 初始化线性表
12. void InitList(SeqList *L) {
13.         for(int i=0 ; i < MAX_SIZE ; i++) {
14.                 L.data[i] = 0 ;//初始化所有元素为0
15.         }
16.         L.length = 0; // 初始长度为0
17. }
19. **特别注意的是ElemType变量，它不是一个实际的数据类型，指代任意一种数据类型，例如int float double等**
21. 静态分配的顺序表长度固定，不可拓展，实际应用中不方便，我们更多采用动态分配创建顺序表
22. *******************************动态分配******************************************
23. // 定义线性表的默认最大长度
24. #define MAX_SIZE 100
26. // 定义线性表的结构体
27. typedef struct {
28.         ElemType *data;  // 指示动态分配的指针 ElemType表示任意数据类型(例如int)
29.         int length;      // 当前顺序表的长度
30.         int MaxSize;     //顺序表最大容量
31. } SeqList;
33. // 初始化线性表
34. void InitList(SeqList *L) {
35.         L.data=(ElemType *)malloc(MAX_SIZE*sizeof(ElemType));//分配连续空间
36.         L.length = 0; // 初始长度为0
37.         L.MaxSize = MAX_SIZE;     //顺序表最大容量
38. }
40. //增加动态数组的长度
41. void IncreaseSize(SeqList &L,int len){
42.         ElemType *p=L.data;
43.         L.data=(ElemType *)malloc((L.MAX_SIZE+len)*sizeof(ElemType));
44.         for(int i=0 ; i < L.length ; i++){
45.                 L.data[i]=p[i];
46.         }
47.         L.MaxSize=L.MaxSize + len;
48.         free(p);
49. }

复制代码

特别注意的是ElemType变量，它不是一个实际的数据类型，指代任意一种数据类型，例如int float double等
次序表的插入

1. //在顺序表L的第i个位置插入元素e
2. bool ListInsert(SeqList &L,int i,ElemType){
3.         if(i<1||i>L.length+1)                                                //判断i的范围是否在可插入范围内
4.                 return flase;                                                        //不在范围内插入失败
5.         if(L.length>=MaxSize)                                                //判断当前空间是否满了，满了则不能插入
6.                 return flase;                                                        //空间已满，插入失败
7.         for(int j = L.length ; j>=i ;j--){                        //将插入位置之后的元素后移
8.                 L.data[j]=L.data[j-i];
9.         }
10.         L.data[i-1]=e;                                                                //在i的位置插入元素e
11.         L.length++;                                                                        //顺序表长度+1
12.         return true;插入成功
13. }

复制代码

时间复杂度分析，时间复杂度一般关注最深层的代码，则为for循环中的移位代码。

• 最好情况 元素插入到次序表尾部，不需要移位则时间复杂度为O(1)
  
• 最坏情况 元素插入到次序表头部，需要将原有n个元素向后移动一位，时间复杂度为O(n)
  
• 均匀情况 新元素插入到每个位置的概率相等，可得均匀移位次数n/2，时间复杂度为O(n)
  

次序表的删除

1. //将表中的第i个元素删除
2. bool ListDelete(SeqList &L,int i){
3.         if(i<1||i>L.length+1)                                                        //判断i的范围是否在可插入范围内
4.                 return flase;                                                                //不在范围内，删除失败
5.         for(int j=i;j<L.length;j++){                                        //将删除元素后续的元素向前移
6.                 L.data[j-1]=L.data[j];
7.         }
8.         L.length--;                                                                                //顺序表长度-1
9.         return true;                                                                        //删除成功
10. }

复制代码

时间复杂度分析，时间复杂度一般关注最深层的代码，则为for循环中的移位代码。

• 最好情况 元素删除的是次序表尾部元素，不需要移位则时间复杂度为O(1)
  
• 最坏情况 元素删除的是次序表头部元素，需要将原有n-1个元素向前移动一位，时间复杂度为O(n)
  
• 均匀情况 新元素插入到每个位置的概率相等，可得均匀移位次数(n-1)/2，时间复杂度为O(n)
  

次序表的查找

按位查找

1. //按位查找-查找顺序表第i位的元素
2. ElemType GetElem(SeqList &L,int i){
3.         return L.data[i-1];
4. }

复制代码

时间复杂度分析，由于次序表的存储位置是连续的，因此按位查找可以直接索引取得，时间复杂度仅位O(1)；
按值查找

1. //按值查找，查找顺序表中e元素所在位置
2. int LocateElem(SeqList &L,ElemType e){
3.         for(int i=0;i<L.length;i++){
4.                 if(L.data[i]==e)
5.                         return i+1;
6.         }
7.         return 0
8. }

复制代码

时间复杂度分析，时间复杂度一般关注最深层的代码，则为for循环中的遍历代码。

• 最好情况 第一个元素为待查找元素，不需要后续遍历则时间复杂度为O(1)
  
• 最坏情况 最后一个元素为待查找元素，需要遍历n个元素，时间复杂度为O(n)
  
• 均匀情况 新元素插入到每个位置的概率相等，可得均匀移位次数(n+1)/2，时间复杂度为O(n)
  

次序表的特点

• 便于访问，能够立刻在O(1)的时间复杂度中找到待访问的值
  
• 数据集中，数据的物理位置相互贴近，且每个存储节点只存储数据
  
• 加长、插入、删除等操作复杂，需要大量平移元素位置
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。