线性表的数据结构笔记有哪些要点？

本文共计4457个文字，预计阅读时间需要18分钟。

学习之路，不断向上。文本已收录至我的GitHub仓库：DayDayUP：[github.com/RobodLee/DayDayUP](https://github.com/RobodLee/DayDayUP)，欢迎Star。下载请注明出处！链接：[https://blog.csdn.net/weixin_43461520/article/details/1](https://blog.csdn.net/weixin_43461520/article/details/1)

好好学习，天天向上

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐

链接：blog.csdn.net/weixin_43461520/article/details/123783563

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐

数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构），存储结构不同，运算的实现方式不同。

线性表指的是逻辑结构，可以采用顺序存储的顺序表或者链式存储的链表实现。

2.1 线性表的定义和基本操作 2.1.1 线性表的定义

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。除第一个元素（表头元素）外，每个元素都有且仅有一个直接前驱；除最后一个元素（表尾元素）外，每个元素有且仅有一个直接后继。

• 线性表的特点
  1. 表中元素的个数有限
  2. 表中元素具有逻辑上的顺序性，表中有其先后次序
  3. 表中元素都是数据元素，每个元素都是单个元素
  4. 表中元素的数据类型相同，每个元素占有相同大小的存储空间

2.1.2 线性表的基本操作

• InitList(&L)：初始化表。构造一个空的线性表。
• Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
• LocateElem(L , e)：按值查找操作。在表L中查找具有给定关键字值的元素。
• GetElem(L , i)：按位查找操作。获取表 L 中第i 个位置的元素的值。
• ListInsert(&L , i , e)：插入操作。在表L中的第 i 个位置上插入指定元素e。
• ListDelete(&L , i , &e)：删除操作。删除表L中第 i 个位置的元素，并用e返回删除元素的值。
• PrintList(L)：输出操作。按前后顺序输出线性表 L 的所有元素值。
• Empty(L)：判空操作。若 L 为空表，则返回 true，否则返回 false。
• DestroyList(&L)：销毁操作。销毁线性表，并释放线性表 L所占用的内存空间。

2.2 线性表的顺序表示

线性表的顺序存储又称顺序表，用一组地址连续的存储单元依次存储线性表中的数据元素。表中元素的逻辑顺序与其物理顺序相同。

2.2.1 插入

ListInsert(&L , i , e)：插入操作。在表L中的第i个位置上插入指定元素e。

typedef struct { int data[MaxSize]; //用静态数组存放元素 int length; //长度 } SqList; //在第i个位置插入元素e，下标为i-1 bool ListInsert(SqList &sqList, int i, int e) { //检查i的范围是否合理 if (i < 1 || i > sqList.length + 1) { return false; } //检查数组是否已满 if (sqList.length >= MaxSize) { return false; } //将第i个元素及之后的元素后移 for (int j = sqList.length; j > i; j--) { sqList.data[j] = sqList.data[j - 1]; } sqList.data[i - 1] = e; sqList.length++; return true; }

2.2.2 删除

ListDelete(&L , i , &e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

typedef struct { int data[MaxSize]; //用静态数组存放元素 int length; //长度 } SqList; //删除第i个元素，并将其赋值给给e，删除元素的下标为i-1 bool ListDelete(SqList &sqList, int i, int &e) { //检查i的范围是否合理 if (i < 1 || i > sqList.length) { return false; } e = sqList.data[i - 1]; //将第i个位置后的元素前移 for (int j = i; j < sqList.length; j++) { sqList.data[j - 1] = sqList.data[j]; } sqList.length--; return true; }

2.2.3 查找

• 按位查找

GetElem(L , i)：按位查找操作。获取表L中第i个位置的元素的值。

typedef struct { ElemType data[MaxSize]; //用静态数组存放元素 int length; //长度 } SqList; //和访问普通数组的方法一样，返回第i个元素 ElemType GetElem(SqList sqList, int i) { return sqList.data[i - 1]; }

• 按值查找

LocateElem(L , e)：按值查找操作。在表L中查找具有给定关键字值的元素。

typedef struct { ElemType data[MaxSize]; //用静态数组存放元素 int length; //长度 } SqList; //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SqList sqList, ElemType e) { for (int i = 0; i < sqList.length; ++i) { if (sqList.data[i] == e) { return i + 1; //数组下标为i的元素值等于e，返回其位序i+1 } } return 0; }

2.3 线性表的链式表示 2.3.1 单链表

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。对每个链表节点，除了存放元素自身的信息外，还需要存放一个指向其后继的指针。

定义

• 不带头节点

#define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //初始化一个不带头结点的空的单链表 bool InitList(LinkList &linkList) { linkList = nullptr; //空表，暂时还没有任何节点 return true; } int main() { LinkList linkList; InitList(linkList); return 0; }

单链表的第一个节点直接指向数据节点。写代码更麻烦，对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。

空表判断：L == NULL

• 带头节点

#include <cstdlib> #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //初始化一个带头结点的空的单链表 bool InitList(LinkList &linkList) { linkList = (LinkList) malloc(sizeof(LNode)); if (linkList == nullptr) { return false; //内存不足，分配失败 } linkList->next = nullptr; //头结点之后暂时还没有节点 return true; }

头结点不存储数据，即头结点的数据域data为空。

空表判断：L→next == NULL，写代码更方便。

插入

• 按位序插入（带头结点）

ListInsert(&L, i , e)：插入操作。在表L中的第i个位置上插入指定元素e。

#include <cstdlib> #include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //向第i个位置插入元素e，也就是在第i-1个元素后插入e bool ListInsert(LinkList &linkList, int i, ElemType e) { if (i < 1) { return false; //检查i是否合法 } LNode *p = linkList; //临时节点，指向当前扫描到的节点 int index = 0;//表示p当前指向第几个节点，初始为第0个节点也就是头结点 while (p != nullptr && index < i - 1) { //移动p，使其指向第i-1个节点 p = p->next; index++; } if (p == nullptr) { return false; } //在第i-1个节点后插入新节点 auto *t = new LNode; t->data = e; t->next = p->next; p->next = t; return true; }

平均时间复杂度：O(n)

• 按位序插入（不带头结点）

ListInsert(&L, i , e)：插入操作。在表L中的第i个位置上插入指定元素e。

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //初始化一个不带头结点的空的单链表 bool InitList(LinkList &linkList) { linkList = nullptr; //空表，暂时还没有任何节点 return true; } //向第i个位置插入元素e，也就是在第i-1个元素后插入e bool ListInsert(LinkList &linkList, int i, ElemType e) { if (i == 1) { //当插入的节点位置是第一个时，创建一个新节点放在linkList的前面 auto *s = new LNode; s->data = e; s->next = linkList; linkList = s; return true; } if (i < 1) { return true; //检查位序是否合法 } LNode *p = linkList; int index = 1;//当前指向第几个节点，初始指向第1个节点 while (p != nullptr && index < i - 1) { p = p->next; index++; } if (p == nullptr) { return false; } auto *s = new LNode; s->data = e; s->next = p->next; p->next = s; return true; }

相较于带头结点的方式而言，当插入的节点为第一个节点时，需要额外进行处理。

平均时间复杂度：O(n)

• 指定节点的后插操作

InsertNextNode(LNode *p , ElemType e)：在p节点后插入一个新节点

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //指定节点的后插操作 bool InsertNextNode(LNode *p, ElemType e) { if (p == nullptr) { return false; //检查p是否为空 } auto *s = new LNode; if (s == nullptr) { return false; //内存不足时可能分配失败 } s->data = e; s->next = p->next; p->next = s; return true; }

没有需要循环的地方，直接在指定节点后插入一个新的节点，时间复杂度为O(1)。

• 指定节点的前插操作

bool InsertPriorNode(LNode *p, ElemType e)：在p节点前插入一个新节点

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //指定节点的后插操作 bool InsertPriorNode(LNode *p, ElemType e) { if (p == nullptr) { return false; //检查p是否为空 } auto *s = new LNode; s->next = p->next; p->next = s; //新节点s连接到p之后 s->data = p->data; //将p中元素复制到s中 p->data = e; //p中元素覆盖为e return true; }

本来应该是在p节点之前插入s节点，现在在p节点之后插入s，然后将p的data与s中的data交换，相当于实现了在p节点之前插入s，由于是直接插入，没有循环遍历，所以时间复杂度为O(1)。

删除

• 按位序删除（带头结点）

bool ListDelete(LinkList &linkList , int i , ElemType &e)：删除第i个节点

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //删除第i个节点，并将删除节点的data赋值给e bool ListDelete(LinkList &linkList, int i, ElemType &e) { if (i < 1) { return false; //检查i是否合法 } LNode *p = linkList; //使p指向被扫描到的节点，初始指向头结点 int index = 0; //表示p当前指向第几个节点 while (p != nullptr && index < i - 1) { //使p指向第i-1个节点 p = p->next; index++; } if (p == nullptr || p->next == nullptr) { //检查p是否合法，检查第i个节点是否存在 return false; } LNode *q = p->next; //q指向待删除节点 e = q->data; p->next = q->next; free(q); return true; }

由于需要循环遍历到待删除节点的前一个节点，所以时间复杂度为O(n)。

• 指定节点的删除

bool DeleteNode(LNode *p)：删除节点p

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //删除节点p bool DeleteNode(LNode *p) { if (p == nullptr) { return false; } LNode *s=p->next; //代码有bug，如果p是最后一个节点，只能循环遍历到p的前驱节点，然后将p删除，但是时间复杂度就会变成O(n) p->data=s->data; p->next=s->next; return true; }

本来是删除节点p，现在将p的后继节点q的data值赋值给p，然后将q删除，间接实现的删除p，时间复杂度为O(1)，如果采用循环遍历的方式找到p的前驱节点，时间复杂度就会变成O(n)。

查找

• 按位查找

GetElem(L , i)：按位查找操作。获取表L中第i个位置的元素的值。

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //按位查找操作。获取表L中第i个位置的元素的值。 LNode *GetElem(LinkList &linkList, int i) { if (i < 1) { return nullptr; //检查i值是否合法 } LNode *p = linkList; //指向当前扫描到的节点 int index = 0; //表示p当前指向第几个节点 while (p != nullptr && index < i) { //使p指向第i个节点 p = p->next; index++; } return p; //如果p是null，则返回的是null }

循环遍历到指定位序的节点，所以平均时间复杂度为O(n)。

• 按值查找

LocateElem(L , e)：按值查找操作。在表L中查找具有给定关键字值的元素。

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //按值查找操作。在表L中查找具有给定关键字值的元素。 LNode *LocateElem(LinkList &linkList, ElemType e) { LNode *p = linkList->next; while (p != nullptr && p->data != e) { p = p->next; } return p; //如果p存在则返回p，反之返回null }

如果找到相应的节点则返回相应的节点，反之返回null。

由于是遍历查找，平均时间复杂度是O(n)。

建立

• 尾插法

LinkList List_TailInsert(LinkList &L)：尾插法建立单链表

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; LinkList List_TailInsert(LinkList &linkList) { linkList = new LNode; //建立头结点 linkList->next = nullptr; LNode *s; //临时节点 LNode *r; //尾指针 r = linkList; ElemType data; cin >> data; while (data != 9999) { //循环输入数据 s = new LNode; //建立一个新节点，将数据赋值给新节点的data，然后将新节点插在尾指针后 s->data = data; r->next = s; r = s; r->next = nullptr; cin >> data; } return linkList; }

尾指针r始终指向最后一个节点，循环输入数据，如果不为9999则表示链表还未结束，将输入的data 赋值给新节点的data域，然后将新节点插入到尾指针之后，再将尾指针指向新的节点。

由于是线性插入，所以时间复杂度是O(n)。

• 头插法

LinkList List_HeadInsert(LinkList &L)：逆向建立链表，每次都在头节点之后插入新的节点

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; LinkList List_HeadInsert(LinkList &linkList) { linkList = new LNode; linkList->next = nullptr; //初始化为空链表 LNode *s; //临时节点 LNode *h; //头结点 h = linkList; ElemType data; cin >> data; while (data != 9999) { s = new LNode; s->data = data; s->next = h->next; h->next = s; cin >> data; } return linkList; }

每次都在头结点之后插入新的节点，链表的顺序与输入数据的顺序相反，时间复杂度为O(n)。

一个重要的应用就是链表的逆置，需要翻转一个链表时，可以遍历旧的链表，然后使用头插法将依次将数据插入到头结点之后。

2.3.2 双链表

#include <iostream> using namespace std; #define ElemType int typedef struct DNode { ElemType data; DNode *prior, *next; } DNode, *LinkList; //p节点之后插入节点s bool InsertNextDNode(DNode *p, DNode *s) { s->next = p->next; if (p->next != nullptr) { p->next->prior = s; } p->next = s; s->prior = p; return true; } //删除p节点的后继节点 bool DeleteNextNode(DNode *p) { if (p == nullptr) { return false; } DNode *q = p->next; if (q->next != nullptr) { q->next->prior = p; } p->next = q->next; return true; }

双链表节点中有两个指针prior和next，分别指向其前驱节点和后继节点。

2.3.3 循环链表

• 循环单链表

在循环单链表中，表尾结点的next指针指向头节点。 从一个节点出发，可以找到其它任意一个节点。

#include <iostream> using namespace std; #define ElemType int typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; //初始化一个循环单链表 bool InitList(LinkList &linkList) { linkList = new LNode; if (linkList == nullptr) { return false; } linkList->next = linkList; //头结点的下一个节点指向自身，表示为空链表 return true; } //判断循环单链表是否为空 bool Empty(LinkList linkList) { //如果头结点的下一个节点指向自身，表示为空的链表 return linkList->next == linkList; } //判断节点p是否为循环单链表的表尾结点 bool isTail(LinkList linkList, LNode *p) { //如果p的下一个节点是头结点，则表示p是表尾结点 return p->next == linkList; }

• 循环双链表

表头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点。

#include <iostream> using namespace std; #define ElemType int typedef struct DNode { ElemType data; struct DNode *prior, *next; } DNode, *DLinkList; //初始化一个循环单链表 bool InitList(DLinkList &dLinkList) { dLinkList = new DNode; if (dLinkList == nullptr) { //内存不足，分配失败 return false; } dLinkList->prior = dLinkList; //头结点的 prior 指向自身 dLinkList->next = dLinkList; //头结点的 next 指向自身 return true; } //判断循环单链表是否为空 bool Empty(DLinkList dLinkList) { //如果头结点的下一个节点指向自身，表示为空的链表 return dLinkList->next == dLinkList; } //判断节点p是否为循环单链表的表尾结点 bool isTail(DLinkList dLinkList, DNode *p) { //如果p的下一个节点是头结点，则表示p是表尾结点 return p->next == dLinkList; } //在p节点之后插入s节点 bool InsertNextDNode(DNode *p, DNode *s) { s->next = p->next; p->next->prior = s; p->next = s; s->prior = p; } //删除p节点的后继节点q bool DeleteNextDNode(DNode *p) { if (p == nullptr) { return false; } DNode *q = p->next; p->next = q->next; q->next->prior = p; free(q); return true; }

码字不易，可以的话，给我来个点赞，收藏，关注

如果你喜欢我的文章，欢迎关注微信公众号 『 R o b o d 』

如果你喜欢我的文章，欢迎关注微信公众号 『 R o b o d 』

本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐

链接：blog.csdn.net/weixin_43461520/article/details/123783563

⭐⭐⭐⭐⭐转载请注明出处！⭐⭐⭐⭐⭐