当前位置： 首页 > news >正文

考研数据结构——线性表（顺序表链表）最全！含代码！

news 来源：原创 2024/5/13 15:04:35

目录

一、顺序表的基本操作

1.1 插入

1.2 删除

1.3 查找

1.3.1 按位查找

1.3.2 按值查找

二、链表

2.1 单链表

2.1.1定义

2.1.2 代码实现

2.1.3 创建单链表

2.1.3.1 不带头结点

2.1.3.2 带头结点

2.1.4 插入操作

2.1.4.1 带头结点的插入

2.1.4.2 不带头结点的插入

2.1.4.3 后插操作

2.1.4.4 前插操作

2.1.5 删除操作

2.1.5.1 按位序删除(带头结点)

2.1.5.2 指定结点删除(带头结点)

2.1.6 查找操作

2.1.6.1 按位查找

2.1.6.2 按值查找

2.1.7 单链表的建立

2.1.7.1 尾插法建立单链表

2.1.7.2 头插法建立单链表

考点：链表的逆置

2.2 双链表

2.2.1 双链表的定义

2.2.2 初始化双链表

2.2.3 双链表的插入

2.2.4 双链表的删除&清空双链表

2.2.5 双链表的遍历

2.3 循环链表

2.3.1 循环单链表

2.3.2 循环双链表

2.3.2.1 插入操作与双链表的差别

2.4 静态链表（考点较少，较少考察代码实现）

2.4.1 静态链表的定义

2.4.2 代码定义静态链表

2.4.3 基本操作的实现

2.4.3.1 初始化

2.4.3.1 查找

2.4.3.2 插入

2.4.4 优缺点

三、顺序表和链表的比较

3.1 对比

3.2 总结

本文所有图片均来自25王道考研数据结构课程截图。如需要pdf版本的笔记可以私我。

一、顺序表的基本操作

1.1 插入

#include<iostream>
using namespace std;
#define MAXSIZE 10		//定义最大长度typedef struct {int data[MAXSIZE];	//顺序表数组定义int length;			//顺序表的长度
}SqList;				//顺序表类型定义void ListInsert(SqList& L, int i, int e) {for (int j = L.length; j >= i; j--)L.data[j] = L.data[j - 1];		//第i个元素之后的元素全部往后移一位，从最后一位开始移动L.data[i - 1] = e;					//第i个元素的下标是i-1L.length++;							//链表长度+1
}//做一个测试
int main() {SqList L;		//声明一个顺序表L.length = 0;	//在声明一个顺序表的时候要把长度置为0，否则L.length可能是随机数。//向顺序表中插入数据元素，每插入一个元素要记得把表长+1for (int i = 0; i < 5; i++) {L.data[i] = i + 100;L.length++;}ListInsert(L, 3, 4);	//在位序3处插入元素4//输出结果for (int i = 0; i < L.length; i++)cout << L.data[i] << " ";return 0;
}

        顺序表的插入需要先将第i个节点之后的元素往后移一位，然后将要插入的元素插入进去。注意位序从1开始，数组下标从0开始，所以在for循环内的代码的数组内是“j-1”。

        插入元素的时候应该判断表是否已满，以及插入的位置是否合法。改进代码如下：

bool ListInsert(SqList& L, int i, int e) {if (i<1 || i>L.length)			//判断i的范围是否有效（i是位序，而位序从1开始）return false;if (L.length > MAXSIZE)			//数组长度大于最大长度，即数组已满return false;for (int j = L.length; j >= i; j--)L.data[j] = L.data[j - 1];		//第i个元素之后的元素全部往后移一位，从最后一位开始移动L.data[i - 1] = e;					//第i个元素的下标是i-1L.length++;							//链表长度+1return true;
}

时间复杂度：

  • 最好：O(1)

  • 最坏：O(n)

  • 平均：O(n)

1.2 删除

#include<iostream>
using namespace std;
#define MAXSIZE 10		//定义最大长度typedef struct {int data[MAXSIZE];	//顺序表数组定义int length;			//顺序表的长度
}SqList;	bool ListDelete(SqList& L, int i, int& e) {if (i<1 || i>L.length)			//输入的删除位序不合法return false;e = L.data[i];					//用变量e存储要删除的元素for (int j = i - 1; j < L.length; j++) {L.data[j] = L.data[j + 1];	//后面的元素移动到前面覆盖}L.length--;						//循环结束后顺序表长度-1return true;
}int main() {SqList L;		//声明一个顺序表L.length = 0;//给顺序表一些初始元素for (int i = 0; i < 5; i++) {L.data[i] = i + 100;L.length++;}int e = -1;				//e用来带回删除的元素ListDelete(L, 1, e);cout << "删除位序为1的元素后" << endl;for (int i = 0; i < L.length; i++) {cout << L.data[i] << " ";}return 0;
}

函数解析：

  • 删除实际上是把位序 i 之后的元素全部往前依次移一位，覆盖掉位序 i 的元素；

  • 在 ListDelete 中，传入顺序表 L ，要删除的元素位序 i ，存放删除元素的空间 e；

  • 变量e是在ListDelete 函数外定义好的一个变量，主要是申请一片内存空间用来存放删除的元素，赋初值为 -1 ，并且变量 e 是引用类型，因为该变量要带到ListDelete 函数外作打印输出（实际操作中也需要告诉函数调用者这次删除的是哪个元素）；

  • 在函数内部先判断位序是否合法，然后再进行后续操作。

时间复杂度：

  • 最好：O(1)

  • 最坏：O(n)

  • 平均：O(n)

1.3 查找

1.3.1 按位查找

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

静态分配：

#define MAXSIZE 10		//定义最大长度
typedef struct {int data[MAXSIZE];	//顺序表数组定义int length;			//顺序表的长度
}SqList;				//顺序表类型定义
//按位查找
int GetInt(SqList& L, int i) {		//传入顺序表L和要查询的元素的位序ireturn L.data[i - 1];
}

动态分配：

        data的数据类型决定了data的一个数据在内存中占用多少内存空间；data是一个指向data在内存中存放位置的一大片连续存储空间的首位置，即data是一个指针。比如data的数据类型是“int *”类型，一个data数据占4个字节，而data刚开始指向内存中2000的位置，那么data[0]就是2000-2003这四个字节所存放的数据，data[1]就是2004-2007这四个字节所存放的数据。

        时间复杂度：O[1]

1.3.2 按值查找

        LocateElem(L,e):按值查找操作，在表L中查找等于e的元素。

typedef struct {int *data;			//只是动态分配数组的指针int MaxSize;		//顺序表的最大容量int length;			//顺序表的长度
}SqList;//按值查找(在顺序表L中查找第一个元素值等于e的元素的位序)
int LocateInt(SqList& L, int e) {for (int i = 0; i < L.length; i++) {if (L.data[i] == e)return i + 1;}return 0;
}

        因为返回的是所查找元素的位序，而i是数组下标，所以return i+1。只有基本数据类型可以使用“==”判断，如果是结构体等其他类型，不能用“==”直接判断。

时间复杂度：

  • 最好：O(1)

  • 最坏：O(n)

  • 平均：O(n)

二、链表

2.1 单链表

2.1.1定义

        和顺序表相比，单链表是链式存储而不是顺序存储，即在内存中是离散存储的，每个结点除了存放数据元素外还要存放指向下一个节点的指针；不需要大片连续空间，改变容量方便；但是不可随机存取，要耗费一定空间存放指针。

2.1.2 代码实现

typedef struct LNode {			//定义单链表的结点类型int data;					//每个结点存放一个数据元素struct LNode* next;			//指针指向下一个结点
}LNode, * LinkList;

        要表示一个单链表的时候，只需要声明一个头指针 L ，指向单链表的第一个结点，即头结点，就可以表示整个单链表。

        举例：

typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;LNode* GetElem(LinkList L, int i) {int j = 1;LNode* p = L->next;if (i == 0) return L;if (i < 1) return NULL;while (p != NULL && j < i) {p = p->next;j++;}return p;
}

        这里面在定义函数GetElem的时候用了LNode *，而在传入参数的时候使用了 LinkList，这两个本质上是一样的，但是LNode *强调是一个节点，而LinkList强调是一个链表。由于该函数返回的是一个节点p，所以在定义函数返回类型的时候使用LNode *；而传参L是一个链表，所以使用LinkList。

2.1.3 创建单链表

2.1.3.1 不带头结点
typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;//初始化一个简单的空表
bool InitList(LinkList& L) {L = NULL;return true;
}void test() {LinkList L;		//声明一个指向单链表的指针//初始化一个空表InitList(L);
}

        在test函数中只是声明了一个指向单链表的指针，并没有创建一个结点；

        InitList函数中设置 L=NULL 是为了防止 L 创建的区域有遗留的脏数据。

2.1.3.2 带头结点
typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));	//分配一个头结点if (L == NULL)						//内存不足，分配失败return false;L->next = NULL;						//头结点之后暂时没有节点return true;
}void test() {LinkList L;		//声明一个指向单链表的指针//初始化一个空表InitList(L);
}

2.1.4 插入操作

2.1.4.1 带头结点的插入

        要想在第 i 个位置上插入元素e，首先要找到第 i-1 个结点的位置，将新结点插入其后。图示如下：

 

代码实现：

typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;//带头结点的单链表插入操作
bool ListInsert(LinkList& L, int i, ElemType e) {if (i < 1)return false;LNode* p;		//指针p指向当前扫描到的结点int j = 0;		//当前p指向的是第几个结点p = L;			//L指向头结点，头结点是第0个节点（不存数据）while (p != NULL && j < i - 1) {	//循环找到第i-1个结点p = p->next;j++;}if (p == NULL)		//i值不合法return false;LNode* s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}

函数解析

  • ListInsert函数中，ElemType是插入数据的数据类型；

  • 进入函数后先判断插入位置 i 是否合法，由于 i 是位序，从1开始，故 i<1 不合法；

  • 然后声明一个指针p指向当前扫描到的结点，整型 j 表示当前p指向的第几个结点，令p的初值为L，即头结点；

  • 之后进入while循环开始从头结点L处往后扫描，直到p指向NULL或者 j 的值大于等于 i-1 的值（i-1是要插入的位置）；

  • 退出循环后即找到了要插入的位置，p此时指向插入位置前的一个结点；

  • 接下来判断 p 的值是否为 NULL ，如果是NULL就说明 i 值不合法，即 i 值过大，超过了链表的长度。

  • 最后是最关键的三行代码，实现插入操作：先在新建结点s的data域中保存要插入的数据e，然后让s的指针指向插入结点前的结点p的next指针指向的下一个结点，即让s指向插入结点的下一个结点，最后让插入节点前的结点p的指针指向新建结点s。

2.1.4.2 不带头结点的插入

代码实现

typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;bool ListInsert(LinkList& L, int i, ElemType e) {if (i < 1)return false;if (i == 1) {LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = L;L = s;}LNode* p;		//指针p指向当前扫描到的结点int j = 1;		//当前p指向的是第几个结点p = L;			//L指向头结点，头结点是第1个节点（不存数据）while (p != NULL && j < i - 1) {	//循环找到第i-1个结点p = p->next;j++;}if (p == NULL)		//i值不合法return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}

代码解析

        不带头结点的链表实现插入操作时，要注意当在头结点位置插入时要单独写一段代码来实现（即i==1的那一段代码），另外注意设置j的值为1，表示刚开始p指向第1个结点而不是第0个。

2.1.4.3 后插操作

代码实现

//后插操作
bool InsertNextNode(LNode* p, ElemType e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)		//内存分配失败return false;s->data = e;		//用结点s保存数据es->next = p->next;p->next = s;		//将结点s连到p之后return true;
}

        给定结点p和数据e，实现在结点p之后插入数据e的操作。

        那么前面所实现的插入操作（以带头结点的插入为例）可以简化为：

typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;//带头结点的单链表插入操作
bool ListInsert(LinkList& L, int i, ElemType e) {if (i < 1)return false;LNode* p;		//指针p指向当前扫描到的结点int j = 0;		//当前p指向的是第几个结点p = L;			//L指向头结点，头结点是第0个节点（不存数据）while (p != NULL && j < i - 1) {	//循环找到第i-1个结点p = p->next;j++;}return InsertNextNode(p,e);		//实现在p结点后插入数据元素e的操作。//下面的是之前的操作，可以替换掉/*if (p == NULL)		//i值不合法return false;LNode* s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;*/
}
2.1.4.4 前插操作

        由于单链表只有指向后面结点的指针，所以如果要往前插入元素，我们无法找到前面的元素，即“看不到前面的元素”，也就无法插入。

方法一：

        可以通过传参时传入头指针L来找到整个链表，因为之前提到过头指针L表示的就是一整个链表，只要知道了头指针L就知道了整个链表，然后对链表进行循环查找p的前驱q，对q进行后插操作。时间复杂度为O(n)。

        但如果传参时没有给头指针，那这种方法就不可行。

方法二：

//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode* p, ElemType e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));if (s == NULL)		//分配内存失败return false;s->next = p->next;		//将s指向p的下一结点p->next = s;			//将p的下一结点设为s，即s为p的后继结点s->data = p->data;		//将p中的data保存到s中p->data = e;			//将新插入的数据e保存到p的data中return true;
}

        既然无法找到前驱结点，那就交换前后数据的位置，此名为“偷天换日”。时间复杂度为O(1)。

2.1.5 删除操作

2.1.5.1 按位序删除(带头结点)
//按位序删除（带头结点）
bool ListDelete(LinkList& L, int i, ElemType& e) {if (i < 1)return false;LNode* p;			//指针p指向当前扫描到的结点int j = 0;p = L;while (p != NULL && j < i - 1) {		//循环找到第i-1个结点p = p->next;j++;}if (p == NULL)return false;if (p->next == NULL)return false;LNode* q = p->next;		//令q指向被删除的结点e = q->data;			//用e返回被删除元素的值p->next = q->next;		//将*q结点从链中断开free(q);				//释放被删除节点的存储空间return true;
}

代码解析

        e是用来存放被删除节点的元素的，需要被带回到函数调用者那里，让调用者知道被删除的元素是什么，所以传参要用&类型。

        p经过循环之后指向被删除元素的前一个结点，所以我们实际删除的应该是p->next，即q结点。用e保存好q的data之后，将p的next指针直接指向他的下一结点（q）的下一结点（q->next），最后释放q的资源就完成了删除操作。

        最坏、平均时间复杂度：O(n)。

        最好时间复杂度：O(1)

2.1.5.2 指定结点删除(带头结点)

        和插入操作一样，要么传参时传入头指针L，循环找到要删除的结点p；要么按照“2.1.4.4 前插操作”里面的方法删除。下为后一种方法：

//删除指定结点p
bool DeleteNode(LNode *p) {if (p == NULL)return false;LNode *q = p->next;			//令q指向p的后继结点p->data = p->next->data;	//和后继结点交换数据域p->next = q->next;			//将q结点从链中“断开”free(q);					//释放后继结点的存储空间return true;
}

代码解析

        相当于把p结点的下一结点q的数据保存到p里面，然后删除q结点。即用q的数据覆盖p的数据。时间复杂度为O(1)。

        注意：如果要删除的结点p是最后一个结点，那么该代码第6行会出错。原因是 p是最后一个结点的话， p->next 此时是NULL，那么p->next->data就是NULL的数据域，这是不对的，会报空指针错误。如果这样，就只能从表头开始依次寻找p的前驱，时间复杂度为O(n)。

        这就体现了单链表的局限性：无法逆向检索，不太方便。

2.1.6 查找操作

2.1.6.1 按位查找

        获取表中第 i 个位置的元素的值。其实在前面的按位插入和按位删除操作中已经用过了按位查找相关的逻辑。

//按位查找（带头结点）
LNode* GetElem(LinkList L, int i) {if (i < 0)return NULL;LNode* p;int j = 0;p = L;while (p != NULL && j < i) {p = p->next;i++;}return p;
}

        如果 i 的值不合法，不论是过小还是过大（大于链表长度）都会返回 NULL。

        那么这样，结合前面"2.4.1.3 后插操作"的 InsertNextNode 函数，“按位插入”操作就可以写为如下代码，体会封装的好处：

//带头结点的单链表插入操作
bool ListInsert(LinkList& L, int i, ElemType e) {if (i < 1)return false;LNode* p = GetElem(L, i - 1);		//找到第i-1个结点return InsertNextNode(p, e);		//在p后插入新元素
}
2.1.6.2 按值查找
//按值查找，找到数据域为e的结点
LNode* LocateElem(LinkList L, ElemType e) {LNode* p = L->next;		//从第1个结点开始查找数据域为e的结点while (p != NULL && p->data != e)p = p->next;return p;
}

        找到后返回指针p，找不到的话返回NULL。平均时间复杂度为 O(n)。

2.1.7 单链表的建立

        共有两种方法：头插法和尾插法。只探讨带头结点的情况。

步骤：

  1. 初始化一个单链表

  2. 每次取一个数据元素，插入到表尾/表头

2.1.7.1 尾插法建立单链表

        首先初始化单链表在“2.1.3.2 带头结点”有讲，初始化的代码如下：

typedef struct LNode {			//定义单链表的结点类型int data;			//每个结点存放一个数据元素struct LNode* next;	//指针指向下一个结点
}LNode, * LinkList;bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));	//分配一个头结点if (L == NULL)						//内存不足，分配失败return false;L->next = NULL;						//头结点之后暂时没有节点return true;
}void test() {LinkList L;		//声明一个指向单链表的指针//初始化一个空表InitList(L);
}

        如果想实现尾插法，就要定义一个函数 ListInsert(LinkList &L,int i,ElemType e) ，然后通过如下伪代码来实现：

while循环{每次取一个数据元素e;ListInsert(L,length+1,e)插到尾部;length++;
}

        如果按照之前的插入操作（2.1.4.1），每次找插入位置都循环遍历一次链表L来找到第 i-1个节点做插入的话，时间复杂度为O(n²)，耗时太多。因此可以设置一个尾指针 r ，让其指向链表 L 的最后一个结点，当我们需要使用尾插法插入一个新的数据元素时，只需要对 r 这个结点实现后插操作。

        尾插法代码实现（包括用户输入）：

//尾插法
LinkList List_TailInsert(LinkList& L) {int x;									//设置插入元素数据类型为int型L = (LinkList)malloc(sizeof(LNode));	//申请一块内存空间，建立头结点L->next = NULL;							//初始化空链表LNode* s, * r = L;						//声明两个指针，s是新插入的元素，r指向尾节点scanf("%d", &x);						//用户输入插入的数据while (x != 9999) {						//设置一个判定条件s = (LNode*)malloc(sizeof(LNode));	//为s结点申请内存空间s->data = x;						//s的数据域存放x的值r->next = s;						//连接s和前面的链表r = s;								//尾指针r指向新插入的结点，即永远保持r为尾节点scanf("%d", &x);					//继续接收用户传参}r->next = NULL;							//尾指针的指针域指向NULLreturn L;
}
2.1.7.2 头插法建立单链表

        头插法实际上就是对头指针 L 的后插操作，即对指定结点实行后插操作，需要用到前面“2.1.4.3 后插操作”里面的代码。while循环里就是后插操作实现的步骤。

//头插法
LinkList List_HeadInsert(LinkList& L) {LNode* s;int x;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;			//初始化空链表scanf("%d", &x);while (x != 9999) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d", &x);}return L;
}
考点：链表的逆置

链表逆置问题：将链表的元素倒序排列
可以使用头插法解决。用一个指针依次取链表L中的元素，然后使用头插法插到L后面，实现链表逆置。

void listReverse(linkedList &L)
{node *p,*s;				//声明两个指针，p指向当前需要改变位置的结点，s用来保存p实现头插法操作p = L->next;			//p刚开始指向第1个节点（L为第0个结点）L->next = NULL;			//把L的下一个结点置为空，防止脏数据while(p){				//循环条件  当p不为空时s = p; 				//让s复制pp = p->next;		//p指针指向下一结点，即下一个需要进行头插操作的结点s->next = L->next; 	//把s后面连到L原来指向的下一结点，即s此时为第1个节点（L为第0个节点）L->next = s;		//L指向s，把L和s链接起来，完成一次头插操作}
}

详细解释：链表逆置详细讲解（图文）-CSDN博客

2.2 双链表

        与单链表比较：单链表无法逆向检索，有时候不太方便；双链表可以双向检索，存储密度更低一些。

2.2.1 双链表的定义

typedef struct DNode {				//定义单链表的结点类型int data;						//每个结点存放一个数据元素struct DNode* prior, * next;	//prior指向前驱结点，next指向后继结点
}DNode, * DLinklist;

2.2.2 初始化双链表

//初始化双链表
bool InitDLinkList(DLinklist& L) {L = (DNode*)malloc(sizeof(DNode));if (L == NULL) return false;L->prior = NULL;		//头结点的prior永远指向NULLL->next = NULL;			//头结点之后暂时还没有节点return true;
}//判断双链表是否为空
bool Empty(DLinklist L) {if (L->next == NULL)return true;		//头结点的后继结点为空，表示双链表为空elsereturn false;
}void test() {DLinklist L;InitDLinkList(L);		//初始化一个双链表
}

2.2.3 双链表的插入

        将s插入到p的后面：

//1.插入操作（有问题）
bool InsertNextDNode(DNode* p, DNode* s) {s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;
}//2.插入操作（没问题）
bool InsertNextDNode(DNode* p, DNode* s) {if(p==NULL || s==NULL)return false;s->next = p->next;if(p->next != NULL)			//当p有后继结点的时候才执行这条语句p->next->prior = s;s->prior = p;p->next = s;
}

        图示是代码3-6行的执行，从右往左依次“绿黄蓝红”的顺序一一对应。对于1号代码，在执行第4行的语句的时候，如果p->next==NULL，即p没有后继结点的话，那就会报“空指针”异常。可以改为2号代码，只有当p有后继结点的时候才执行这条语句，连接p的后继结点的前驱结点和s的后继结点。此时执行效果如下：

2.2.4 双链表的删除&清空双链表

//双链表的删除（删除p结点）
bool DeleteNextDNode(DNode* p) {if (p == NULL)			//p不合法return false;DNode* q = p->next;		//找到p的后继结点qif (q == NULL)			//如果p没有后继结点，也不合法return false;p->next = q->next;	if (q->next != NULL)	//q结点不是最后一个结点q->next->prior = p;free(q);				//释放结点空间return true;
}//清空双链表
void DestoryList(DLinklist& L) {//循环释放各个数据节点while (L->next != NULL)DeleteNextDNode(L);free(L);		//释放头结点L = NULL;		//头指针指向NULL
}

2.2.5 双链表的遍历

//后向遍历
while (p != NULL) {//对结点p做响应操作，如打印输出p = p->next;
}//前向遍历
while (p != NULL) {//对结点p做响应操作，如打印输出p = p->prior;
}//前向遍历（跳过头结点）
while (p->prior != NULL) {//对结点p做响应操作，如打印输出p = p->next;
}

        双链表不可以随机存取，按位查找、按值查找操作都只能用遍历的方法实现，所以时间复杂度都是O(n)。

2.3 循环链表

2.3.1 循环单链表

//声明一个单链表
typedef struct LNode{int data;			//每个节点存放一个int型数据元素struct LNode* next;	//指针指向下一结点
}LNode, * LinkList;//初始化一个循环单链表
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));		//分配一个头结点if (L == NULL)		//内存不足，分配失败return false;L->next = L;		//头结点的next指向头结点自己return true;
}//判断一个循环链表是否为空
bool Empty(LinkList L) {return L->next == L;		//如果头结点L的next指向他自己，就说明循环链表为空
}//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode* p) {return p->next == L;		//如果p的next指向头结点，就说明p是循环单链表的表尾结点，反之不是
}

2.3.2 循环双链表

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

//定义循环双链表
typedef struct DNode {int data;struct DNode* prior;struct DNode* next;
}DNode, * DLinkList;//初始化一个空的循环双链表
bool InitDLinkList(DLinkList& L) {L = (DNode*)malloc(sizeof(LNode));if (L == NULL)return false;L->prior = L;		//L的前驱结点指向本身L->next = L;		//L的后继结点指向本身return true;
}//判断循环双链表是否为空
bool Empty(DLinkList L) {return L->next == L;	//如果头指针的后继结点指向他自己，就说明为空，反之不是。
}//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinkList L, DNode* p) {return p->next == L;
}
2.3.2.1 插入操作与双链表的差别

        在“2.2.3 双链表的插入”小节提到过如下插入方式：

//1.插入操作
bool InsertNextDNode(DNode* p, DNode* s) {s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;
}

        当时在双链表中是有问题的，原因是当插入的元素是表尾元素时，第4行代码中的 p->next 是指向 NULL 的，没有前驱结点 prior ，会报空指针异常。

        但在循环双链表中，该代码是正确的，自行体会。删除操作同理。

2.4 静态链表（考点较少，较少考察代码实现）

2.4.1 静态链表的定义

1.静态链表与单链表作比较：

  • 单链表的各个结点离散地分布在内存中的各个地方；静态链表会分配一整块连续的内存空间来存放各个结点，各个结点不一定连续但都在这一块内存中。

  • 单链表的结点由数据元素和指针组成；静态链表的结点由数据元素和数组下标（游标）组成。

  • 单链表中的指针指向下一元素的地址；静态链表的游标充当指针，指向下一元素的下标。

  • 单链表表示表尾元素的方式是让 p->next=NULL ；静态链表表示表尾元素的方式是让游标为 -1 。

2.计算静态链表数据元素的地址：

        假设静态链表中每个结点的数据元素大小为4B，每个游标4B（每个结点8B），设起始地址为 addr 。那么数组下标为 i 的元素的地址为：addr+i*8。

        例如数组下标为2的元素的地址为：addr+2*8。

2.4.2 代码定义静态链表

//定义一个静态链表
//方式1：
#define MaxSize 10		//静态链表的最大长度
typedef struct Node {int data;			//存储数据元素（类型可变）int next;			//下一个元素的数组下标
};void test() {struct Node a[MaxSize];		//数组a是一个静态链表
}//方式2：课本上给出的方式
#define MaxSize 10		//静态链表的最大长度
typedef struct Node {int data;			//存储数据元素（类型可变）int next;			//下一个元素的数组下标
}SLinkList[MaxSize];void test() {SLinkList a;		//数组a是一个静态链表
}

        给出了两种方式，第一种方式比较容易想到，但第一种定义数组a容易被误会成一个 Node 型的数组，而非一个静态链表；第二种方式相当于重命名了“struct Node”，和之前单链表中的 LinkList 意义相同，定义出来的 a 本身就是一个数组，表示一个静态链表。

2.4.3 基本操作的实现

2.4.3.1 初始化

        把 a[0] 的 next 设为 -1，表示 a[0] 是最后一个结点；另外把其他的结点的 next 设为 -2 或其他特殊数字（不能是正整数，因为正整数用来做数组下标了）来表示这个结点是空的。（为什么这么设置在“2.4.3.2 插入”讲）

2.4.3.1 查找

        从头结点出发挨个往后遍历结点，直到找到某个位序的结点（注意不是找到某个下标的结点，位序是指各个结点在逻辑上的顺序，即第几个，而数组下标指的是各个结点在物理上的顺序）。时间复杂度为O(n)。

        如上图，数组下标为2的结点e1的位序为1，因为头指针指向它；同样的，e1指向的e2（数组下标为6）的位序为2；以此类推。

2.4.3.2 插入

插入位序为 i 的结点：

  • 找到一个空结点，存入数据元素；

  • 从头结点出发找到位序为 i-1 的结点；

  • 修改新结点（第 i 个节点）的 next 为前一个结点（第 i-1 个结点）的 next ；

  • 修改前一个结点的 next 为新插入结点的数组下标；

  • 将被删除节点的 next 设置为 -2，表示该结点的位置已经没有数据了。

        注意：在插入操作时我们需要找到一个空结点，但是在计算机看来，所有的内存都有数据，只是有些是“脏数组”，于是我们需要在定义静态链表的时候把空结点的数组下标（即next）设为 -2 或其他特殊数字（不能是正整数，因为正整数用来充当数组下标了）来表示这个结点是没有数据元素的，可以作插入操作。

2.4.4 优缺点

优点：增删操作不需要大量移动元素。

缺点：不能随机存取，只能从头结点开始依次往后查找；且容量固定不可变。

所以现在几乎不用静态链表，使用场景为：不支持指针的低级语言或数据元素数量固定不变的场景。

三、顺序表和链表的比较

对于一个数据结构，我们应该关注数据结构的三要素：

  • 逻辑结构；

  • 物理结构/存储结构；

  • 数据的运算/基本操作

3.1 对比

顺序表链表
逻辑结构线性结构线性结构
存储结构优点：支持随机存取、存储密度高； 缺点：大片连续空间分配不方便，改变容量不方便优点：离散地小空间分配方便，改变容量方便； 缺点：不可随机存取，存储密度低。
基本操作

1.创建：需要预先分配大片连续空间。静态分配容量不可改变，动态分配容量可改变但需要移动大量元素，时间代价高。

2.销毁：修改lengt=0，从逻辑上把顺序表标记为一个空表。此时如果是静态分配，系统会自动回收空间；如果是动态分配（malloc），就需要手动free。malloc和free一定是成对出现的。

3.增删：插入/删除元素要将欧旭元素都后移/前移。时间复杂度为O(n)，时间开销主要来自移动元素。

4.查找 ：按位查找O(1)；按值查找O(n)。若表内元素有序，则可在O(log2(n))时间内找到

1.创建：只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展。

2.销毁：依次对每个结点做free操作。

3.增删：插入/删除元素只需要修改指针即可。时间复杂度为O(n)，时间开销主要来自查找目标元素。相同数量的数据元素情况下，查找的时间开销一定比移动的时间开销小得多，代价更低。

4.查找：按位查找O(n)；按值查找O(n)。无论有序无序都要从头结点开始依次遍历。

3.2 总结

顺序表链表
弹性（可扩容）×√
增删×√
查找√×

表长难以预估、经常要增删元素——链表

表长可预估、查询操作较多——顺序表

相关文章：

  • Oracle PL/SQL Programming 第9章：Numbers 读书笔记
  • 6.如何判断数据库搜索是否走索引？
  • 还是了解下吧，大语言模型调研汇总
  • php 对接IronSource海外广告平台收益接口Reporting API
  • vue3项目实战-第六章-登录页（表单校验/模板适配/Pinia管理用户数据/持久化存储）
  • 大数据是如何嗅探和捕捉我们的偏好的
  • el-select 选择后获取key 和label的值
  • Wireshare捕获接口中没有本地连接
  • 解决在命令行中输入py有效，输入python无效，输入python会跳转到microsoft store的问题| Bug
  • wayland(xdg_wm_base) + egl + opengles 渲染使用纹理贴图的旋转 3D 立方体实例(十三)
  • JavaSE（上）-Day7
  • 什么是委托，委托的本质是什么？
  • 爱奇艺 CTR 场景下的 GPU 推理性能优化
  • LeetCode 热题100 链表专题解析
  • ElasticSearch第二章(ES8.X的使用)
  • 8年软件测试工程师感悟——写给还在迷茫中的朋友
  • Apache的80端口被占用以及访问时报错403
  • CEF与代理
  • Docker下部署自己的LNMP工作环境
  • ES6 ...操作符
  • ES6 学习笔记（一）let，const和解构赋值
  • Github访问慢解决办法
  • JavaScript标准库系列——Math对象和Date对象（二）
  • jquery cookie
  • KMP算法及优化
  • MySQL Access denied for user 'root'@'localhost' 解决方法
  • python docx文档转html页面
  • Python打包系统简单入门
  • v-if和v-for连用出现的问题
  • WordPress 获取当前文章下的所有附件/获取指定ID文章的附件(图片、文件、视频)...
  • 不用申请服务号就可以开发微信支付/支付宝/QQ钱包支付！附：直接可用的代码+demo...
  • 从零开始的无人驾驶 1
  • 猴子数据域名防封接口降低小说被封的风险
  • 基于Dubbo+ZooKeeper的分布式服务的实现
  • 聊聊flink的BlobWriter
  • 如何合理的规划jvm性能调优
  • 山寨一个 Promise
  • 《码出高效》学习笔记与书中错误记录
  • MyCAT水平分库
  • Spring第一个helloWorld
  • 你学不懂C语言，是因为不懂编写C程序的7个步骤 ...
  • #git 撤消对文件的更改
  • #传输# #传输数据判断#
  • $Django python中使用redis, django中使用(封装了),redis开启事务(管道)
  • (delphi11最新学习资料) Object Pascal 学习笔记---第5章第5节（delphi中的指针）
  • （附源码）ssm旅游企业财务管理系统 毕业设计 102100
  • (免费领源码）Python#MySQL图书馆管理系统071718-计算机毕业设计项目选题推荐
  • （五）大数据实战——使用模板虚拟机实现hadoop集群虚拟机克隆及网络相关配置
  • (转)关于pipe()的详细解析
  • （转）甲方乙方——赵民谈找工作
  • （转载）（官方）UE4--图像编程----着色器开发
  • .“空心村”成因分析及解决对策122344
  • .NET Core WebAPI中使用Log4net 日志级别分类并记录到数据库
  • .net 发送邮件
  • .NET中两种OCR方式对比