WHCSRL 技术网

数据结构笔记——线性表

目录

一、线性表的类型定义

二、顺序表

三、链表

1.单链表（线性链表）

2.循环链表

3.双向链表

一、线性表的类型定义

线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。线性表中的每个元素可以是一个数、一个符号甚至更复杂的内容，但是同一线性表中元素必定有相同的特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

除此之外，线性表一定满足线性结构的特点。

线性结构的特点：在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。

线性表有两种表示方式（存储方式）：一种是顺序结构存储，我们叫做顺序表；另一种是链式结构存储，我们叫做链表。这会在后面分别介绍。

线性表的基本操作：

  1. InitList(&L)        // 构造一个空的线性表L
  2. DestroyList(&L)        // 销毁已存在的线性表L
  3. ClearList(&L)        // 将L重置为空表
  4. ListInsert(&L, i, e)        // 在线性表L中的第i个位置插入新元素e
  5. ListDelete(&L, i, &e)        // 删除线性表L中的第i个元素，并用e返回其值
  6. IsEmpty(L)        // 判断L是否为空表
  7. ListLength(L)        // 返回线性表L中的数据元素个数
  8. LocateElem(L, e)        // 查找与给定值e满足特定关系的数据元素的位序，若不存在则返回0
  9. GetElem(L, i, &e)        // 用e返回线性表L中第i个数据元素的值

二、顺序表

顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。

假设线性表的每个元素占 l 个字节，那么根据顺序表的特性，可以得到第 i 个元素的地址和第 1 个元素的地址关系为LOC(a_i) = LOC(a_1) + (i - 1) * l

顺序表的图示结构：

接下来看看顺序表的代码实现：

1.存储结构：

  1. #define LIST_INIT_SIZE 100    // 线性表存储空间的初始分配量
  2. #define LISTINCREMENT 10    // 线性表存储空间的分配增量
  3. typedef struct{
  4. 	ElemType *elem;    // 存储空间基址
  5. 	int length;    // 当前长度
  6. 	int listsize;    // 当前分配的存储容量（以sizeof(ElemType)为单位）
  7. }SqList;

2.初始化操作：

  1. Status InitList_Sq(SqList &L){
  2.     // 构造一个空的线性表L
  3.     L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));    // malloc()为头文件stdlib.h下的分配地址函数
  4.     if(!L.elem) exit(OVERFLOW);    // 存储分配失败
  5.     L.length = 0;   // 空表长度为0
  6.     L.listsize = LIST_INIT_SIZE;    // 初始存储容量
  7.     return OK;
  8. } // InitList_Sq

时间复杂度：O(1)

3.销毁操作：

  1. void DestroyList_Sq(SqList &L){
  2.     // 销毁线性表L
  3.     if(L.elem) free(L.elem);    // 释放存储空间
  4. } // DestroyList_Sq

时间复杂度：O(1)

4.清空操作： 

  1. void ClearList_Sq(SqList &L){
  2.     // 将线性表L重置为空表
  3.     L.length = 0;    // 将线性表长度重置为0
  4. } // ClearList_Sq

时间复杂度：O(1) 

5.插入操作：

  1. Status ListInsert_Sq(SqList &L, int i, ElemType e){
  2.     // 在顺序线性表L中第i个位置之前插入新的元素e
  3.     // i的合法值为1<=i<=ListLength(L)+1
  4.     if(i < 1 || i > L.length + 1) return ERROR;    // i值不合法
  5.     if(L.length >= L.listsize){    // 当前存储空间已满，增加分配
  6.         newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));    // realloc()为头文件stdlib.h下的重新分配地址函数
  7.         if(!newbase) exit(OVERFLOW);    // 存储分配失败
  8.         L.elem = newbase;    // 新基址
  9.         L.listsize += LISTINCREMENT;    // 增加存储容量
  10.     }
  11.     q = &(L.elem[i - 1]);    // q为插入位置
  12.     for(p = &(L.elem[L.length - 1]); p >= q; --p) *(p + 1) = *p;    // 插入位置及之后的元素右移
  13.     *q = e;    // 插入e
  14.     ++L.length;    // 表长增1
  15.     return OK;
  16. } // ListInsert_Sq

平均操作次数：E_ir = frac{1}{n + 1}sum_{i = 1}^{n + 1}(n - i + 1) = frac{n}{2}

时间复杂度：O(n)

6.删除操作：

  1. Status ListDelete_Sq(SqList &L, int i, ElemType &e){
  2.     // 在顺序线性表L中删除第i个元素，并用e返回其值
  3.     // i的合法值为1<=i<=ListLength(L)
  4.     if(i < 1 || i > L.length) return ERROR;    // i值不合法
  5.     p = &(L.elem[i - 1]);    // p为被删除元素的位置
  6.     e = *p;    // 被删除元素的值赋给e
  7.     q = L.elem + L.length - 1;    // 表尾元素的位置
  8.     for(++p; p <= q; ++p) *(p - 1) = *p;    // 被删除元素之后的元素左移
  9.     --L.length;    // 表长减1
  10.     return OK;
  11. } // ListDelete_Sq

平均操作次数：E_dl = frac{1}{n}sum_{i = 1}^{n}(n - i) = frac{n - 1}{2}

时间复杂度：O(n)

7.判断空表：

  1. int IsEmpty_Sq(SqList L){
  2.     // 判断线性表L是否为空
  3.     if(L.length == 0) return TRUE;    // 数据元素长度为0，返回1；反之返回0
  4.     else return FALSE;
  5. } // IsEmpty_Sq

时间复杂度：O(1) 

8.求长度操作：

  1. int ListLength_Sq(SqList L){
  2.     // 求线性表L的长度
  3.     return L.length;
  4. } // ListLength_Sq

时间复杂度：O(1) 

9.查找操作：

  1. int LocateElem_Sq(SqList L, ElemType e){
  2.     // 在顺序线性表L中查找第1个值与e满足compare()的元素的位序
  3.     // 若找到，则返回其在L中的位序，否则返回0
  4.     i = 1;    // i的初值为第1个元素的位序
  5.     p = L.elem;    // p的初值为第1个元素的存储位置
  6.     while(i <= L.length && !compare(*p++, e)) ++i;    // compare()为查找的条件
  7.     if(i <= L.length) return i;    // 若找到则返回数据元素的位序
  8.     else return 0;
  9. } // LocateElem_Sq

平均操作次数：E_{loc} = frac{1}{n}sum_{i = 1}^{n}i = frac{n + 1}{2}（其中n为顺序表中数据元素的个数）

时间复杂度：O(n)

10.取值操作：

  1. Status GetElem_Sq(SqList L, int i, ElemType &e){
  2.     // 用e返回顺序表L中第i个元素的值
  3.     if(i < 1 || i > L.length) return ERROR;    // 判断i的值是否合理
  4.     e = L.elem[i - 1];    // 将第i个元素值赋给e
  5.     return OK;
  6. } // GetElem_Sq

时间复杂度：O(1)

总结

顺序表的优点：

（1）存储密度大（结点本身所占存储量/结点结构所占存储量）

（2）可以随机存取表中任意元素

顺序表的缺点：

（1）再插入、删除某一元素时，需要移动大量元素

（2）浪费存储空间

（3）属于静态存储形式，数据元素的个数不能自由扩充

三、链表

链表是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

链表中每个数据都有两部分信息，一部分是自身元素的信息（数据域），另一部分是指示前继或后继的信息（指针域），这两部分组成的数据元素的存储映像称为结点。指针域中存储的信息称为指针或链。

1.单链表（线性链表）

单链表是每个结点只有一个数据域和一个指针域构成，且指针域指示后继结点的信息，尾元结点的指针为空（NULL）。

单链表的图示结构：

接下来看看单链表的代码实现：

1.存储结构：

  1. typedef struct LNode{
  2. 	ElemType data;    // 数据元素
  3. 	struct LNode *next;    // 指针元素
  4. }LNode, *LinkList;

2.初始化操作：

  1. Status InitList_L(LinkList &L){
  2.     // 初始化单链表L
  3.     L = (LinkList)malloc(sizeof(LNode));    // 生成头结点
  4.     L->next = NULL; // 头结点指针初始化为空
  5.     return OK;
  6. } // InitList_L

时间复杂度：O(1)

3.销毁操作：

  1. Status DestroyList_L(LinkList &L){
  2.     // 销毁单链表L
  3.     LNode *p;   // 或LinkList p;
  4.     while(L){   // 从头结点开始依次释放结点
  5.         p = L;
  6.         L = L->next;
  7.         free(p);    // 释放结点
  8.     }
  9.     return OK;
  10. } // DestroyList_L

时间复杂度：O(n)​​​​​​ 

4.清空操作：

  1. Status ClearList_L(LinkList &L){
  2.     // 清空单链表L
  3.     LNode *p, *q;   // 或LinkList p, q;
  4.     p = L->next;
  5.     while(p){    // 循环单链表，从首元结点开始释放结点
  6.         q = p->next;
  7.         free(p);
  8.         p = q;
  9.     }
  10.     L->next = NULL;    // 头结点指针变为空
  11.     return OK;
  12. } // ClearList_L

时间复杂度：O(n)

5.插入操作：

  1. Status ListInsert_L(LinkList &L, int i, ElemType e){
  2. 	// 在带头结点的单链线性表L中第i个位置之前插入元素e
  3. 	p = L; j = 0;
  4. 	while(p && j < i - 1){    // 寻找第i-1个结点
  5. 		p = p->next; ++j;
  6. 	}
  7. 	if(!p || j > i - 1) return ERROR;    // i小于1或者大于表长加1
  8. 	s = (LinkList)malloc(sizeof(LNode));    // 生成新结点
  9. 	s->data = e;    // 插入L中
  10. 	s->next = p->next;
  11. 	p->next = s;
  12. 	return OK;
  13. } // ListInsert_L

时间复杂度：查找部分O(n)，插入部分O(1)

6.删除操作：

  1. Status ListDelete_L(LinkList &L, int i, ElemType &e){
  2. 	// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值
  3. 	p = L; j = 0;
  4. 	while(p->next && j < i - 1){    // 寻找第i个结点，并令p指向其前驱
  5. 		p = p->next; ++j;
  6. 	}
  7. 	if(!(p->next) || j > i - 1) return ERROR;    // 删除位置不合理
  8. 	q = p->next;    // 删除并释放结点
  9. 	p->next = q->next;
  10. 	e = q->data;
  11. 	free(q);
  12. 	return OK;
  13. } // ListDelete_L

时间复杂度：查找部分O(n)，删除部分O(1)

7.判断空表：

  1. int IsEmpty_L(LinkList L){
  2.     // 判断链表L是否为空
  3.     if(L->next) return FALSE;   // 非空
  4.     else return TRUE;
  5. } // IsEmpty_L

时间复杂度：O(1)

8.求长度操作：

  1. int ListLength_L(LinkList L){
  2.     // 求单链表L的表长
  3.     LNode *p;
  4.     p = L->next;    // p指向首元结点
  5.     i = 0;
  6.     while(p){    // 遍历单链表，统计结点数
  7.         i++;
  8.         p = p->next;
  9.     }
  10.     return i;    // 返回结点数
  11. } // ListLength_L

时间复杂度：O(n)

9.查找操作：

  1. LNode *LocateElem_L(LinkList L, ElemType e){
  2.     // 在单链表L中查找满足条件compare()的数据元素
  3.     // 若找到则返回该数据元素的地址，否则返回NULL
  4.     p = L->next;
  5.     // int j = 0;    若要返回位序则定义一个j记数据的位置
  6.     while(p && !compare(p->data, e)){
  7.         p = p-> next;
  8.         // j++;
  9.     }
  10.     if(L->next != NULL) return p;    // 若要返回位序，则return j;
  11.     else return NULL;
  12. } // LocateElem_L

时间复杂度：O(n)

10.取值操作：

  1. Status GetElem_L(LinkList L, int i, ElemType &e){
  2. 	// L为带头结点的单链表的头指针。
  3. 	// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
  4. 	p = L -> next; j = 1;    // 初始化，p指向第1个结点，j为计数器
  5. 	while(p && j < i){    // 顺指针向后查找，直到p指向第i个元素或p为空
  6. 		p = p->next; ++j;
  7. 	}
  8. 	if(!p || j > i) return ERROR;    // 第i个元素不存在
  9. 	e = p->data;    // 取第i个元素
  10. 	return OK;
  11. } // GetElem_L

时间复杂度： 查找部分O(n)，取值部分O(1)

11.头插法创建单链表

  1. void CreateList_H(LinkList &L, int n){
  2. 	// 逆位序输入n个元素的值，建立带表头结点的单链线性表L
  3. 	L = (LinkList)malloc(sizeof(LNode));
  4. 	L->next = NULL;    // 先建立一个带头结点的单链表
  5. 	for(i = n; i > 0; --i){
  6. 		p = (LinkList)malloc(sizeof(LNode));    // 生成新结点
  7. 		scanf(&p->data);    // 输入元素值
  8. 		p->next = L->next;    // 插入到表头
  9. 		L->next = p;
  10. 	}
  11. } // CreateList_H

时间复杂度：创建 n 个元素的表为O(n)，每次插入元素为O(1)

12.尾插法创建单链表

  1. void CreateList_R(LinkList &L, int n){
  2.     // 正位序输入n个元素的值，建立带表头结点的单链表L
  3.     L = (LinkList)malloc(sizeof(LNode));
  4.     L->next = NULL;    // 先建立一个带头结点的单链表
  5.     r = L;
  6.     for(i = 0; i < n; ++i){
  7.         p = (LinkList)malloc(sizeof(LNode));    // 生成新结点
  8. 		scanf(&p->data);    // 输入元素值
  9. 		p->next = NULL;
  10. 		r->next = p;    // 插入到表尾
  11. 		r = p;    // 指向新的尾元结点
  12.     }
  13. } // CreateList_R

时间复杂度：创建 n 个元素的表为O(n)，每次插入元素为O(1)

2.循环链表

循环链表是每个结点只有一个数据域和一个指针域构成，且指针域指示后继结点的信息，尾元结点的指针域指示头结点（或首元结点）的信息。

循环链表有两种表示形式：

第一种是用头指针表示，那么表示如图所示：

这种方法查找a_1的时间复杂度为O(1)，但查找a_n的时间复杂度为O(n)，实用性较低；

第二种是用尾指针表示，表示如图所示：

这种方法查找不管是查找a_1还是a_n时间复杂度都是O(1)，实用性较高。

循环链表的大部分操作都与单链表类似，这里就不再赘述了，可以自行进行分析。

3.双向链表

双向链表是每个结点只有一个数据域和两个指针域构成，指针域指示前驱结点和后继结点的信息，头结点的前驱指针为NULL，尾元结点的后继指针为NULL。

双向链表的图示结构：

双向循环链表的图示结构：

这里重点来看双向（循环）链表存储结构和双向循环链表的插入、删除操作：

1.存储结构：

  1. typedef struct DuLNode{
  2. 	ElemType data;    // 数据元素
  3. 	struct DuLNode *prior;    // 指向前驱的指针
  4. 	struct DuLNode *next;    // 指向后继的指针
  5. }DuLNode, *DuLinkList;

2.插入操作：

  1. Status ListInsert_DuL(DuLinkList &L, int i, ElemType e){
  2.     // 在带头结点的双链循环线性表L中第i个位置之前插入元素e
  3.     // i的合法值为1<=i<=表长+1
  4.     if(!(p == GetElemP_DuL(L, i)))    // 在L中确定插入位置
  5.         return ERROR;    // p = NULL，即插入位置不合法
  6.     if(!(s == (DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
  7.     s->data = e;
  8.     s->prior = p->prior; p->prior->next = s;
  9.     s->next = p; p->prior = s;
  10.     return OK;
  11. } // ListInsert_DuL

时间复杂度：O(1)

3.删除操作：

  1. Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e){
  2.     // 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1<=i<=表长
  3.     if(!(p == GetElemP_DuL(L, i)))    // 在L中确定删除位置
  4.         return ERROR;    // p = NULL，即插入位置不合法
  5.     e = p->data;
  6.     p->prior->next = p->next;
  7.     p->next->prior = p->prior;
  8.     free(p);
  9.     return OK;
  10. } // ListDelete_DuL

时间复杂度：O(1)

总结

链表的优点：

（1）能灵活地分配内存空间

（2）插入或删除元素效率高，每次操作仅需O(1)的时间

链表的缺点：

（1）不像数组一样通过下表读取元素，而是每次都要从表头开始一个一个读取

（2）查询第k个元素需要O(k)的时间

推荐阅读

Python 函数动态参数值设为 None 的意义_TEDxPY的博客

本文整理自《Effective Python 编写高质量 Python 代码的 59 个有效方法》第 20 条：用 None 和文档字符串来描述具有动态默认值的参数参数的默认值，只会在程序加载模块并读到本函数的定义时评估一次。对于{} 或 [ ] 等动态的值，可能会导致奇怪的行为。对于以动态值作为实际默认值的关键字参数来说，应该把形式上的默认值写为 None，并在函数的文档字符串里描述该默认值所对应的实际行为。例1例如：from time import *from datetime import

【靶点突破】网易云换肤方案探讨

【靶点突破】网易云换肤方案探讨老方案网易云音乐换肤方案原理动手实现一个网易云换肤方案的demo动手打造换肤方案的轮子黑白夜模式切换  Hello,大家好，我是Ellen,这是Android靶点突破系列文章，旨在帮助你更加了解Android技术开发的同时，把业务做到精致。思考自己的职业生涯，想成为怎样的技术人，想追求怎么样的生活。至尊宝脚踏七彩祥云娶了紫霞，希望你也能成为她的自尊宝。| from Ellen缘言1.老方案  app的换肤老方案基本都是通过拿到控件对象，进行动态修改

openwrt strongswan IPSec IKEV2_季春贰柒的博客

前言：文章是作者基于一段时间的学习成果而写的，主要是为了记录下搭建VPN的过程以及遇到的一些麻烦错误，方便之后继续学习或者使用。当然如果能帮到一些读者自然是更好的。鉴于本人水平有限，文章之中难免会出现错漏不足之处，恳请批评指教、留言讨论。学习过程中在网友文章中发现此图，诚不我欺（手动狗头）。0.准备俩台openwrt系统路由器、一部手机（安卓、苹果都行略有差别后续会说到）、阿里云服务器、1.安装strongswan这一步网上随意搜索就可以看到许多保姆级别教程，写得很详细。如果你实在懒得搜，轻移贵

cad2016珊瑚_预测有马的硬珊瑚覆盖率

cad2016珊瑚What’s the future of the world’s coral reefs? 世界珊瑚礁的未来是什么？ In February of 2020, scientists at University of Hawaii Manoa released a study addressing this very question. The models they devel...

:signal-handler (1523582415) Received SIGINT scheduling shutdown...

linux下安装redis---解决redis-cli不能正常使用Linux中进入redis客户端，报链接超时Could not connect to Redis at 127.0.0.1:6379: Connection timed out Redis使用守护进程启动sentinel并指定其日志目录正常redis-server可以通过配置文件来指定守护进程启动以及指定日志路径，但sentinel...