前言

好的,一刻也没有为了顺序表的学习结束而感到回味无穷,接下来让我们有请下一个选手——链表的登场。

同为线性结构的链表与顺序表之间相差的可不止一点半点,在使用场景上也是千差万别。

介绍

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

链表分为单链表、循环链表以及双向链表。下面我会一个个进行解释。

单链表

单链表的定义和表示

单链表是一种线性数据结构,其中每个元素(称为节点)包含两个部分:数据域和指向下一个节点的指针。在单链表中,最后一个节点的指针通常设置为 NULL,表示链表的结束。这种结构使得单链表非常适合动态的数据集合,因为它不需要连续的内存空间,并且插入和删除操作相对高效。单链表是由表头唯一确定,因此单链表可以用头指针的名字来命名,若头指针名是L,则把链表称为表L。

这里放一个单链表的逻辑状态图和存储结构图方便理解

存储结构:

这个图中展现了单链表存储结构的特点不需要连续的存储空间,这也是和前面的顺序表不同的一点,顺序表需要占用一块连续的存储空间。指针为数据元素之间逻辑关系的映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,这种存储结构为非顺序映像或链式映像。

逻辑状态:

在这个图中,可以看出前一个节点的指针域指向与它有逻辑关系的下一个结点存储地址,在使用链表时,关心的只是它所表示的线性表中数据元素之间的逻辑顺序,而不是每个数据元素在存储器中的实际位置。

由此可见,单链表可由头指针唯一确定。具体实现为:

typedef struct LNode {
	ElemType elem;     //结点的数据域
	struct LNode* next;//结点的指针域
}LNode, * LinkList;        //LinkList为指向结构体LNode的指针类型

这里定义的是单链表中每个结点的存储结构,它包括两部分:存储结点的数据域 elem ,其类型用通用的类型标识符ElemType表示(例如,如果用链表表示之前在顺序表中的图书信息,只需将ElemType替换为定义的Book数据类型即可);存储后继结点位置的指针域next,其类型指向结点的指针类型LNode*;

这里再详细解释一下这句 struct LNode *next。这是个指针,指向的是struct LNode这种类型的指针,那么struct LNode这种类型有是什么类型呢?这种类型又包括这样的两个成员的一个指针,这种是用自己来定义自己,本来定义一个类型叫struct LNode,然后我这个里面的成员struct LNode *next有是这个类型,这种定义方式叫做嵌套的定义。

LNode指的是一个结点而*LinkList就是指向这种结构结点的一个指针类型,我们再来定义的时候就不需要加*号了,就比较方便,比如说头结点L,我们可以用LNode *L指向这种结点的一个指针,也可以直接用LinkList L更加简单,因为LinkList本身就是指向这种类型的一个指针。定义结点指针p通常使用LNode *p的方式,而不是LinkList p的方式

接下来讲一下前边一直在提到的头结点,首元结点,头指针的概念,同时也防止把这三个概念混淆。

头结点 (Header Node)

  • 定义:头结点是位于链表最前端的一个特殊节点,它并不存储实际的数据元素,而是作为一个辅助节点存在。
  • 作用
    • 便于对链表的操作,比如在链表头部插入或删除节点时,不需要单独处理空链表的情况。
    • 可以统一操作,使得算法更加简洁。
  • 特点:头结点的 data 域通常不使用,而它的 next 指针指向真正的第一个数据节点(即首元结点)。

首元结点 (First Data Node 或 Head Element Node)

  • 定义:首元结点是指链表中第一个存储实际数据的节点。
  • 作用:它是链表中真正开始存放数据的地方。
  • 特点:在没有头结点的情况下,首元结点就是链表的第一个节点;如果有头结点,那么首元结点是头结点之后的第一个节点。

头指针 (Head Pointer)

  • 当链表为空时,头指针可能为 NULL,或者指向一个只含有头结点的链表。
  • 定义:头指针是一个指向链表起始位置的指针。它可以指向头结点(如果有的话),也可以直接指向首元结点。
  • 作用:通过头指针可以访问整个链表。
  • 特点
  • 如果链表有头结点,头指针通常指向头结点。
  • 如果链表没有头结点,头指针则直接指向首元结点。
  • 当链表为空时,头指针可能为 NULL,或者指向一个只含有头结点的链表。

讲完了头结点,首元结点,头指针的概念,补充一下为什么链表要增加头结点。

头结点的作用

(1)便于首元结点的处理

增加了头结点之后,首元结点的地址保存在头结点(也就是其“前驱”结点)的指针域中,则对链表的第一个数据元素的操作与对其他数据元素的操作相同,无需进行特殊处理。

这样解释可能还是不太好理解,那咱来点狠活儿!

假设我们有一个没有头结点的单链表,其结构如下:

+-------+      +-------+      +-------+
| head  | ----> | data: | ---->| data: | ----> ... ----> NULL
|  10    |      |  20   |      |  30   |
+---+---+      +---+---+      +---+---+
   |                  |             |
   v                   v            v
 (头指针/首元结点)  (第二个节点)  (第三个节点)

在这种情况下,head 指向的是第一个数据节点(即首元结点),如果我们要在链表头部插入一个新节点或者删除首元结点,我们需要特别处理 head 指针。例如,插入操作可能需要更新 head 的值。

现在考虑增加了一个头结点后的链表结构:

+------+      +-------+     +-------+      +-------+
| head | ---->| data:| ---->| data: | ---->| data: | ----> ... ----> NULL
| next |      |  N/A |      |  10   |      |  20   |
+------+      +---+---+     +---+---+     +---+---+
                   |            |               |
                   v            v               v
                 (头结点)     (首元结点)      (第二个节点)

在这个例子中,head 指向的是头结点,而头结点的 next 指针指向了首元结点(即第一个数据节点)。通过这种方式,头结点提供了一种统一的接口来处理链表的所有节点,包括第一个数据节点。因此,添加、删除等操作可以被编写得更加通用,而无需针对首元结点做特殊处理。

(2)便于空表和非空表的统一处理

当链表不设头结点时,假设L为单链表的头指针,它应该指向首元结点,则当单链表为长度n为0的空表时,L指针为空(判定空表的条件可记为:L==NULL)。

增加头结点之后,不需要再单独处理空链表的情况,因为即使链表为空,也有一个头结点存在,L->next 将会是 NULL。

这里举个例子

示例:在链表头部插入新节点

  • 无头结点时
    • 如果链表为空,则直接让 head 指向新节点。
    • 如果链表不为空,则需要创建新节点,并让它指向原来的 head,然后更新 head 为新节点。
  • 有头结点时
    • 创建新节点。
    • 让新节点的 next 指向头结点的 next
    • 更新头结点的 next 为新节点。

这个过程对于有头结点的链表来说是一致的,不管链表是否为空,都只需要改变头结点的 next 指针即可。

补充顺序表和线性表中new的区别

在C++中,L = new DNode;L.elem = new ElemType; 这两行代码涉及的是不同的内存分配操作,它们用于不同的数据结构和场景。

L = new LNode;
  • 用途:这行代码用于动态地创建一个 LNode 结构体实例,并将该实例的地址赋值给指针 L
  • 数据结构:适用于链表。
  • 含义LNode 是一个结构体,代表链表中的一个节点。每个节点包含数据域 elem 以及一个指针 next
  • 内存分配new LNode 分配了足够存储一个 LNode 结构体的内存空间,并调用默认构造函数(如果有)来初始化这个结构体。
L.elem = new ElemType;
  • 用途:这行代码用于动态地为顺序表中的元素数组分配内存。
  • 数据结构:适用于顺序表(即数组或基于数组实现的列表)。
  • 含义L 可能是一个结构体或类,其中包含一个 ElemType 类型的数组 elem,用于存储顺序表中的元素。new ElemType 通常会分配一个固定大小的数组。
  • 内存分配new ElemType[capacity] 分配了一个可以存储 capacity 个 ElemType 元素的数组,并返回指向第一个元素的指针。

总结

  • L = new LNode; 用于创建一个单独的链表节点,适用于链表等动态数据结构。
  • L.elem = new ElemType[capacity]; 用于创建一个数组,适用于顺序表等静态数据结构。

两者都使用了 new 关键字来进行动态内存分配,但它们分配的对象类型不同,一个是单个节点结构体,另一个是元素数组。在使用这些动态分配的内存时,记得在不再需要时通过 deletedelete[] 来释放内存,以避免内存泄漏。对于 new DNode 使用 delete,而对于 new ElemType[capacity] 使用 delete[]

单链表的基本操作

单链表的初始化

算法步骤

①生成新结点作为头结点,用头指针L指向头结点。

②头结点的指针域置空。

int InitList(LinkList& L) {
	L = new  LNode;
	L->next = NULL;
	return OK;
}

时间复杂度:O(1)。

单链表的取值

和顺序表不同,链表中逻辑相邻的结点并没有

算法步骤

①用指针p指针指向首元结点,用 j 做计数器初赋值为1.

②从首元结点开始依次顺着链域next向下访问,只要指向当前结点的指针p不为空(NULL),并且没有达到序号为 i 的结点,则循环执行以下操作:

  • p指向下一个结点。
  • 计数器 j 相应加1。

③退出循环时。如果指针p为空,或者计数器 j 大于 i ,说明指定的序号 i 值不合法(i 大于表长n或者小于等于0),取值失败返回ERROR;否则取值成功,此时 j= i时,p所指的结点就是要找的第 i 个结点,用参数 e 保存当前节点的数据域,返回OK。

int GetElem(LinkList L, int i, ElemType &e) {
	//在带头结点的单链表L中根据序号i获取元素的值,用e返回L中第i个数据元素的值
	LNode* p;
	p = L->next;  //初始化,p指向首元结点,计数器j初值赋为1
	int j = 1;
	while (p && j < i) {
		p = p->next; //p指向下一个节点
		j++;         //计数器j相应加1
	}
	if (!p || j > i) { //i值不合法i>n或≤0
		return ERROR;
	}
	e = p->elem;     //取第i个结点的数据域
	return OK;
}

时间复杂度:O(n)

  • 需要遍历链表直到找到匹配值的节点或到达链表末尾,最坏情况下是 O(n)。

单链表的查找

在链表中查找的方式有两种,一种是通过元素查找,一种是通过位置查找

咱先来说通过元素查找

算法步骤

①用指针p指向首元结点。

②从首元结点开始依次顺着链域next向下查找,只要指向当前结点的指针p不为空,并且p所指结点的数据域不等于给定值e,则循环执行以下操作:p指向下一个结点。

③返回p。若查找成功,p此时指向结点的地址值,若查找失败,则p的值为NULL。

LNode* LocateElem(LinkList L, ElemType e) {
	//在带头结点的单链表L中查找值为e的元素
	LNode* p;
	p = L->next;  //初始化,p指向首元结点
	while (p && p->elem != e) {  //顺链域向后查找,直到p为空或p所指结点的数据域等于e
		p = p->next; //p指向下一个结点
	}
	return p;     //查找成功返回值为e的结点地址p,查找失败p为NULL
}

时间复杂度:O(n),其中 n 是链表中的节点数量。最坏情况下需要遍历整个链表。

接下来是通过位置查找

算法步骤

①从头结点开始遍历链表。
②使用一个计数器来记录当前访问的节点位置。
③当计数器达到目标位置时,返回当前节点。
④如果遍历到链表末尾还没有达到目标位置,则返回 NULL。

LNode* LocateElem(LinkList L, int pos) {
	LNode* p = L; // 从头结点开始
	int count = -1; // 计数器,从 -1 开始是因为头结点不存储数据

	while (p != NULL && count < pos) {
		p = p->next;
		count++;
	}

	if (p != NULL) {
		return p; // 找到了目标位置的节点
	}
	else {
		return NULL; // 超出了链表的长度
	}
}

时间复杂度:O(k+1),其中 k 是目标位置。最好的情况是 k 为 0,时间复杂度为 O(1);最坏的情况是 k 为 n-1,时间复杂度为 O(n)。

单链表的插入

链表的插入方式不同于顺序表,因为链表中每个结点的指针域都存储着下一个结点的地址,所以要在两个结点之间插入一个新的结点,需要修改前一个结点的指针域以及插入结点的指针域,这里来一张图片示意:

根据插入操作的逻辑定义,我们要先生成一个数据域为x的结点,之后修改结点a中的指针域,令其指向结点x,而结点x中的指针域应指向结点b,从而实现3个元素a、b以及x之间逻辑关系的变化。假设s为指向结点x的指针,则上述指针修改操作用语句描述即为:

s->next=p->next;
p->next=s;

算法步骤

①遍历链表直到达到目标位置的前一个结点。

②生成一个新结点*s。

③将新结点*s的数据域置为e。

④将新结点*s的指针域指向目标位置结点的后一个结点。

⑤将结点*p的指针域指向新结点*s。

int ListInsert(LinkList& L, int i, ElemType e) {
	//在带头结点的单链表L中第i个位置插入值为e的新结点
	LNode* p;
        p=L;
	int j = 0;
	while (p && (j < i - 1)) {//查找第i-1个结点,p指向该结点
		p = p->next;          
		j++;
	}
	if (!p || j > i - 1) {//i>n+1或者i<1
		return ERROR;
	}
	LNode* s;
	s = new LNode;//生成新结点*s
	s->elem = e;//将结点*s的数据域置为e
	s->next = p->next;//将结点*s的指针域指向结点
	p->next = s;//将结点*p的指针域指向结点*s
	return OK;
}

和顺序表一样,如果表中有n个结点,则插入操作中合法的插入位置有n+1个,即1≤i≤n+1。当i=n+1时,新结点则插在链表尾部。

时间复杂度:O(k+1),其中 k 是目标位置。最好的情况是 k 为 0,时间复杂度为 O(1);最坏的情况是 k 为 n-1,时间复杂度为 O(n)。

单链表的删除

要删除单链表中指定位置的元素,同插入元素一样,首先应该找到该位置的前驱结点。这里直接上图:

在单链表中删除元素b时,应该首先找到其前驱结点a。为了在单链表中实现元素a、b以及c之间逻辑关系的变化,仅需修改结点中a的指针域即可。假设p为指向结点a的指针,则修改语句为:

p->next=p->next->next;

在删除结点b时,除了修改结点a的指针域外,还要释放结点b所占的空间,所以在修改指针前,应该引入另一个指针q,临时保存结点b的地址以备释放。

算法步骤

①查找要删除的结点的前驱结点,并由指针p指向该结点。

②临时保存待删除的结点的地址在q中,以备释放。

③将结点*p的指针域指向的删除结点的的后继结点。

④释放结点的空间。

int ListDelete(LinkList& L, int i) {
	//在带头结点的单链表L中,删除第i个元素
	LNode* p;
	p = L;
	int j = 0;
	while ((p->next) && (j < i - 1)) {//查找第i-1个结点,p指向该结点
		p = p->next;
		j++;
	}
	if (!(p->next) || (j > i - 1)) {//当i>n或i<n时,删除位置不合理
		return ERROR;
	}
	LNode* q;
	q = p->next; //临时保存被删结点的地址以备释放
	p->next = q->next;//改变删除节点前驱结点的指针域
	delete q;//释放删除结点的空间
	return OK;
}

删除算法中的循环条件(p->next&&j<i-1)和插入算法中的循环条件(p&&(j<i-1))是有区别的。因为插入时的有效的位置为n+1个,而删除时的有效位置只有n个。

创建单链表

创建单链表类似于插入算法,根据结点插入位置的不同分为前插法和后插法。

前插法创建单链表

这里直接放图:

前插法是通过将新的结点逐个插入链表的头部即头结点之后来创建链表,每次申请一个新的结点,读入相应的数据元素值,然后将新结点插入到头结点之后。

算法步骤

①创建一个只有头结点的空链表。

②根据创建链表包括的元素个数n,循环n次执行以下操作:

  • 生成一个新结点*p;
  • 输入元素赋给新结点*p的数据域;
  • 将新结点*p插入到头结点之后。
void CreateList_H(LinkList& L, int n) {
	L = new LNode;
	L->next = NULL;
	LNode* p;
	for (int i = 0; i < n; i++) {
		p = new LNode;
		cin >> p->elem.no;
		p->next = L->next;
		L->next = p;
	}
}

时间复杂度:O(n)。

后插法创建单链表

这里依旧是直接放图:

是不是非常一目了然。后插法就是通过将新结点逐个插入链表尾部来创建链表。和前插法一样,每次申请一个新结点,读入相应的数据元素值。不同的是,为了使新结点能够插入表尾,需要增加一个尾指针指向链表的尾结点。

算法步骤

①创建一个只有头结点的空链表。

②尾指针r初始化,指向头节点。

③根据创建链表包括的元素个数n,循环n次执行以下操作:

  • 生成一个新结点*p;
  • 输入元素值赋给新结点*p的数据域;
  • 将新结点*p插入尾结点*r之后;
  • 尾指针r指向新的尾结点*p。
void CreateList_B(LinkList& L, int n) {
	//正位序输入n个元素的值,建立带表头节点的单链表L
	L = new LNode;
	L->next = NULL;
	LNode* r;
	r = L;
	LNode* p;
	for (int i = 0; i < n; i++) {
		p = new LNode;
		cin >> p->elem.no;
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

时间复杂度:O(n)。

打印单链表

算法步骤

①创建一个临时的指针变量temp,并将它指向链表头结点的下一个结点。

②使用一个while来循环遍历链表。循环的条件为temp不等于NULL,意味着还没有到达链表的表尾。

③打印当前的数据。

void PrintList(LinkList L) {
	LinkList temp = L->next; // 从头结点的next开始打印
	while (temp != NULL) {
		printf("%d ", temp->elem);
		temp = temp->next;
	}
	printf("\n");
}

补充一为什么要用一个临时指针变量temp。

  1. 保护原始链表结构:如果你直接使用L->next作为循环中的迭代器,那么在循环过程中你会不断地改变L->next的值。一旦你遍历到了链表的末尾,L->next就会指向NULL,这会导致你丢失了链表的起始位置,即无法再访问到链表的第一个元素。
  2. 避免修改输入参数:函数接收的是链表的头结点L。如果直接操作LL->next,那么在函数外部调用者可能会看到链表头被修改了,这是不希望发生的情况。使用temp可以在不影响原链表的情况下进行遍历。
  3. 保持代码清晰和可读性:通过引入一个临时变量temp来遍历链表,可以使代码逻辑更加清晰,更容易理解。它清楚地表明了你的意图是遍历整个链表,而不仅仅是操作链表的头部。
  4. 便于调试和维护:如果在未来你需要对这个函数进行调试或者修改,有一个明确的遍历指针会使得工作变得更加简单。你可以轻松地设置断点来检查当前遍历的位置,而不用担心影响链表本身的状态。

补充

这里补充一点,前面我们讲了单链表的存储结构为:

typedef struct LNode {
	ElemType elem;     
	struct LNode* next;
}LNode, * LinkList;        

聪明的你看到数据域ElemType elem,肯定就会联想到上一篇文章顺序表中的ElemType *elem,这个ElemType可以是任何数据类型,包括struct,一般来说,我们要定义一个书的单链表,我们会先定义一个书的结构体:

typedef struct {
	char no[50];//书的标号
	char title[50];//书的书名
	float price;//书的价格
}Book;

然后在用书的结构体代替ElemType

typedef struct LNode {
	Book elem;     
	struct LNode* next;
}LNode, * LinkList; 

这种形式一般是我们常用的形式,其数据域是Book这个结构体,还有一种定义书的信息的单链表的形式,就是把书的信息当作数据域,并且它自身可以形成一个链表节点。,具体形式如下:

typedef struct{
char no[50];
char title[50];
struct Book *next;
}Book,*LBook;

说一下它俩的区别:

  1. 数据与结构
    • 第一种 Book 结构体:既是数据容器也是链表节点,因为它包含了数据和指针。
    • LNode 结构体:是链表节点,包含了一个 Book 数据项和一个指向下一个节点的指针。
  2. 功能
    • 第一种 Book 结构体:可以直接用于构建一个简单的链表,每个节点都是一个 Book 实例。
    • LNode 结构体:用于构建一个更复杂的链表,每个节点包含一个完整的 Book 实例。
  3. 内存布局
    • 第一种 Book 结构体:包含三个字段:书号、书名和指向下一个 Book 的指针。
    • LNode 结构体:包含两个字段:一个 Book 实例和一个指向下一个 LNode 的指针。
  4. 使用场景
    • 第一种 Book 结构体:当你需要一个简单的链表来存储书籍信息时,可以使用这种结构体。
    • LNode 结构体:当你需要一个更复杂的链表结构,每个节点包含一个完整的 Book 实例时,应该使用这种结构体。

简而言之,第一种 Book 结构体可以单独形成一个简单的链表,而 LNode 结构体则更适合构建一个更复杂、更灵活的链表。

循环链表

循环链表是另一种形式的链式存储结构。说是另一种形式,但实际上就是单链表最后一个结点的指针域指向头结点,形成一个环。因此,从表中任意一个结点出发都可以找到表中的其它结点。

循环链表的操作和单链表基本一致,差别仅在于:当链表进行遍历时,判别当前指针p是否指向表尾结点的终止条件不同。在单链表中,判别条件为:

p!=NULL
或
p->next!=NULL

而循环链表的判别条件为:

p!=L
或
p->next!=L

在某些情况下,若在循环链表中设立尾指针而不设头指针,可使一些操作简化。例如,两个线性表合并成一个表时,仅需将第一个表的尾指针指向第二个表的第一个结点,第二个表的尾指针指向第一个表的头结点,然后释放第二个表的头结点。

补充

  1. 节点(Node):
    • 每个节点至少包含两个部分:存储的数据元素和一个指向下一个节点的引用。
    • 在循环链表中,每个节点的“下一个”指针总是指向另一个节点;即使是最后一个节点也不例外,它的“下一个”指针将指向头节点。
  2. 头节点(Head Node):
    • 通常用来标识链表的起始位置。在循环链表中,头节点同样作为访问整个链表的入口点。
    • 如果链表为空,则头节点可能为 null 或指向自身形成自环。
  3. 尾节点(Tail Node):
    • 尾节点是链表中的最后一个节点,在普通链表中它指向 null,但在循环链表中它指向头节点。
    • 由于循环性质,有时候我们不需要特别区分头尾节点来实现一些操作。
  4. 遍历:
    • 遍历循环链表时需要设置条件以避免无限循环。一种常见的方法是从任意节点开始遍历,并且跟踪已访问过的节点数或者使用一个额外的标志位来判断是否回到了起点。
  5. 插入/删除:
    • 插入和删除操作通常涉及到更新相邻节点的链接关系,确保循环特性不被破坏。
    • 特别地,在空链表中插入第一个节点时,这个节点同时作为头节点和尾节点,并且它的“下一个”指针应指向自己。

双向链表

双向链表是一种常见的线性数据结构,它与单向链表的主要区别在于每个节点不仅包含指向下一个节点的指针,还包含指向前一个节点的指针。这种设计使得在链表中既可以向前遍历也可以向后遍历,同时提供了更灵活的插入和删除操作。

这里写一个双向链表的存储结构:

typedef struct BuLNode {
	ElemType elem;
	struct DuLNode* prior;//指向直接前驱
	struct DuLNode* next;//指向直接后继
}DuLNode,*DuLinkList;

在双向链表中仅有插入和删除操作有较大的区别

双向链表的插入

算法步骤

①检查位置的合法性。如果i<=0,则插入位置不合法,返回错误。

②找到插入位置的前驱结点:

  • 使用一个指针 p 从头结点开始遍历,直到找到第 i-1 个节点(即要插入位置的前驱节点)。
  • 如果在遍历过程中发现 p 为空或者遍历次数超过 i-1,说明位置超出链表范围,返回错误。

③创建新节点:

  • 动态分配一个新的节点 s 并设置其数据域 elem 为 e
  • 如果内存分配失败,返回错误。

④更新指针:

  • 将新节点 s 的 next 指针指向原第 i 个节点(即 p->next)。
  • 如果原第 i 个节点存在,则将其 prev 指针指向新节点 s
  • 将新节点 s 的 prev 指针指向原第 i-1 个节点 p
  • 将原第 i-1 个节点 p 的 next 指针指向新节点 s
int InsertDList(DLinkList& L, int i, ElemType e) {
	if (i <= 0) {
		cout << "位置必须大于0" << endl;
		return ERROR;
	}
	DNode* p = L;
	int j = 0;
	while (p && (j < i - 1)) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		cout << "超出链表范围" << endl;
		return ERROR;
	}
	DNode* s = new DNode;
	if (s == NULL) {
		cout << "内存分配失败" << endl;
		return ERROR;
	}
	s->elem = e;
	s->next = p->next;
	if (p->next) {
		p->next->prev = s;
	}
	s->prev = p;
	p->next = s;
	return OK;
}

双向链表的删除

算法步骤

①找到要删除的结点:

  • 使用一个指针 p 从头结点开始遍历,直到找到第 i 个节点。
  • 如果在遍历过程中发现 p 为空或者遍历次数超过 i,说明位置超出链表范围,返回错误。

②保存被删除节点的数据:

  • 将被删除节点的数据域 p->elem 赋值给 e,这样调用者可以通过 e 获取到被删除的数据。

③更新指针:

  • 更新前驱节点的 next 指针,使其指向被删除节点的后继节点。
  • 如果被删除节点有后继节点,更新其 prev 指针,使其指向前驱节点。

④释放内存:

  • 删除节点后,释放该节点所占用的内存。
int DeleteDList(DLinkList& L, int i, ElemType& e) {
	if (i < 0) {
		cout << "位置必须大于0" << endl;
		return ERROR;
	}
	DNode* p = L;
	int j = 0;
	while (p && (j < i)) {
		p = p->next;
		j++;
	}
	if (!p || j > i) {
		cout << "位置超出范围" << endl;
		return ERROR;
	}
	e = p->elem;
	p->prev->next = p->next;
	if (p->next) {
		p->next->prev = p->prev;
	}
	delete p;
	return OK;
}

顺序表和链表的比较

顺序表(也称为数组)和链表是两种常见的线性数据结构,它们在存储方式、访问效率、插入删除操作等方面有着不同的特性和适用场景。下面从空间和时间复杂度等多个方面对这两种数据结构进行详细比较。

空间使用

顺序表:

  • 优点:由于所有元素连续存储,不需要额外的指针或引用信息,因此对于相同数量的数据,顺序表通常占用更少的空间。
  • 缺点:需要预先分配足够的内存空间。如果实际使用的空间小于分配的空间,则会造成浪费;反之,如果实际需求超过分配的空间,则需要重新分配更大的内存块,并复制原有数据,这可能会导致性能问题。

链表:

  • 优点:每个节点独立分配,可以根据需要动态扩展,不会造成空间浪费。
  • 缺点:每个节点除了存储数据外还需要额外的空间来存储指向下一个(以及前一个,在双向链表中)节点的指针,因此相对于顺序表会消耗更多的内存空间。

时间复杂度

访问元素:

  • 顺序表: O(1) - 可以直接通过索引快速访问任意位置的元素。
  • 链表: O(n) - 必须从头节点开始遍历到目标位置,平均情况下需要访问一半的节点。

插入/删除元素:

  • 顺序表:
    • 在末尾插入/删除: O(1)
    • 在中间或开头插入/删除: O(n),因为可能需要移动后续的所有元素。
  • 链表:
    • 在已知位置插入/删除: O(1),只需要修改前后节点的指针即可。
    • 在未知位置插入/删除: O(n),因为需要先遍历找到该位置。

其他考虑因素

缓存友好性:

  • 顺序表: 由于元素连续存储,访问时具有较好的局部性,可以充分利用CPU缓存,提高读取速度。
  • 链表: 节点分散存储,访问时可能导致缓存未命中,降低性能。

动态调整大小:

  • 顺序表: 固定大小,调整大小时可能涉及大量数据迁移。
  • 链表: 动态大小,易于扩展或收缩。

实现难度:

  • 顺序表: 实现较为简单,支持随机访问。
  • 链表: 实现相对复杂,特别是处理边界条件时。

应用场景

  • 顺序表适用于需要频繁随机访问且元素个数变化不大的场合。
  • 链表则更适合于经常需要插入删除操作且元素个数不确定的情况。

综上所述,选择哪种数据结构取决于具体的应用需求。例如,如果你的应用程序需要大量的插入和删除操作,同时对内存利用率有较高要求,那么链表可能是更好的选择。相反,如果应用主要关注快速查找特定元素或者执行批量操作,那么顺序表将是更优的选择。

具体实例

这次的具体例子没像上一篇顺序表给了两个例子,这次只写了一个例子,这个例子包含上面单链表的所有操作:

单链表

#include <iostream>
using namespace std;
typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100


typedef struct LNode {
	ElemType elem;//结点的数据域
	struct LNode* next;
}LNode,*LinkList;


//初始化
int InitList(LinkList& L) {
	L = new LNode;
	L->next = NULL;
	return OK;
}


//取值
int GetElem(LinkList L, int i, ElemType& e) {
	LNode* p;
	p = L->next;//初始化。p指向首元结点
		int j = 1;
		while (p && j < i) {
			p = p->next;
			j++;
		}
		if (!p || j > i) {
			//i值不合法
			return ERROR;
		}
		e = p->elem;
		return OK;
}

//查找 元素查找
LNode* LocateElem(LinkList L, ElemType e) {
	LNode* p;
	p = L->next;
	while (p && p->elem != e) {
		p = p->next;
	}
	return p;
}

//查找  位置查找
LNode* LocateElem1(LinkList L, int i) {
	LNode* p = L;
	int count = 1;
	while (p != NULL && count < i) {
		p = p->next;
		count++;
	}
	if (p != NULL) {
		return p;
	}
	else {
		return NULL;
	}
}

//前插法创建单链表
void CreateList_H(LinkList& L, int n) {
	L = new LNode;
	L->next = NULL;
	LNode* p;
	for (int i = 0; i < n; i++) {
		p = new LNode;
		cin >> p->elem;
		p->next = L->next;
		L->next = p;
	}
}
//后插法创建单链表
void CreateList_B(LinkList& L, int n) {
	//正位序输入n个元素的值,建立带表头节点的单链表L
	L = new LNode;
	L->next = NULL;
	LinkList r;
	r = L;
	LinkList p;
	for (int i = 0; i < n; i++) {
		p = new LNode;
		cin >> p->elem;
		p->next = NULL;
		r->next = p;
		r = p;
	}
}

//打印链表
void PrintList(LinkList L) {
	LinkList temp = L->next;//从头结点的next开始打印
	while (temp != NULL) {
		printf("%d ", temp->elem);
		temp = temp->next;
	}
	printf("\n");
}

//插入
int ListInsert(LinkList& L, int i, ElemType e) {
	//在带头结点的单链表L中第i个位置插入值为e的新结点
	LNode* p;
	p = L;
	int j = 0;
	while (p && (j < i - 1)) {//查找第i-1个结点,p指向该结点
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {//i>n+1或者i<1
		return ERROR;
	}
	LNode* s;
	s = new LNode;//生成新结点*s
	s->elem = e;//将结点*s的数据域置为e
	s->next = p->next;//将结点*s的指针域指向结点
	p->next = s;//将结点*p的指针域指向结点*s
	return OK;
}

//合并
void MergeList_L(LinkList& LA, LinkList& LB, LinkList& LC) {
	//已知单链表LA和LB的元素按值非递减排列
	//归并LA和LB得到新的单链表LC,LC的元素也按值非递减排列
	LNode* pa;
	LNode* pb;
	LNode* pc;
	pa = LA->next;  
	pb = LB->next;  
	LC = LA;        //用LA的头结点作为LC的头结点
	pc = LC;        //pc的初值指向LC的头结点
	while (pa && pb) {
		//LA和LB均未到达表尾,依次“摘取”两表中值较小的结点插入到LC的最后
		if (pa->elem <= pb->elem) {  //摘取pa的结点
			pc->next = pa;   //将pa所指结点链接到pc所指结点之后
			pc = pa;         //pc指向pa
			pa = pa->next;   //pa指向下一个结点
		}
		else {//摘取pb的结点
			pc->next = pb;   //将pb所指结点链接到pc所指结点之后
			pc = pb;         //pc指向pb
			pb = pb->next;   //pb指向下一节点
		}
	}
	pc->next = pa ? pa : pb; //将非空表的剩余段插入到pc所指结点之后
	delete LB;               //释放LB的头结点
}
int main() {
	LinkList L1 = NULL, L2 = NULL, L3 = NULL;
	int choice, position, value, n;
	Status status;
	ElemType e;
	bool isInitList = false;

	do {
		cout << "请选择操作:" << endl;
		cout << "1. 初始化链表" << endl;
		cout << "2. 插入元素" << endl;
		cout << "3. 打印链表" << endl;
		cout << "4. 创建链表(前插法)" << endl;
		cout << "5. 创建链表(后插法)" << endl;
		cout << "6. 查找元素" << endl;
		cout << "7. 位置查找" << endl;
		cout << "8. 合并链表" << endl;
		cout << "0. 退出" << endl;
		cin >> choice;

		if (!isInitList && (choice >= 2 && choice <= 8)) {
			cout << "请先初始化链表!" << endl;
			continue;
		}

		switch (choice) {
		case 1:
			status = InitList(L1);
			if (status == OK) {
				cout << "初始化链表成功!" << endl;
				isInitList = true;
			}
			break;
		case 2:
			cout << "请输入要插入的位置和元素: ";
			cin >> position >> value;
			status = ListInsert(L1, position, value);
			if (status == OK) {
				cout << "插入成功!" << endl;
			}
			else cout << "插入失败" << endl;
			break;
		case 3:
			PrintList(L1);
			break;
		case 4:
			cout << "请输入链表长度: ";
			cin >> n;
			CreateList_H(L1, n);
			break;
		case 5:
			cout << "请输入链表长度: ";
			cin >> n;
			CreateList_B(L1, n);
			break;
		case 6:
			cout << "请输入要查找的元素: ";
			cin >> e;
			if (LocateElem(L1, e) != NULL) {
				cout << "找到元素: " << e << endl;
			}
			else {
				cout << "未找到元素: " << e << endl;
			}
			break;
		case 7:
			cout << "请输入要查找的位置: ";
			cin >> position;
			if (LocateElem1(L1, position) != NULL) {
				cout << "找到位置: " << position << endl;
			}
			else {
				cout << "未找到位置: " << position << endl;
			}
			break;
		case 8:
			InitList(L2);
			cout << "请输入第二个链表的长度: ";
			cin >> n;
			CreateList_B(L2, n);
			MergeList_L(L1, L2, L3);
			L1 = L3; // 更新L1为合并后的链表
			break;
		case 0:
			cout << "程序结束" << endl;
			break;
		default:
			cout << "无效的选择,请重新输入" << endl;
		}
	} while (choice != 0);

	return 0;
}

同样,这个例子也不再过多解释,有看不懂的地方就去看上文单链表每个操作的解释,同时,这个例子也只是将这些操作汇总了,这个程序的健壮性也是没那么强,只是一个参考作用。

双向链表

#include<iostream>
using namespace std;
typedef int ElemType;
#define ERROR 0
#define OK 1
typedef struct DNode {
	ElemType elem;  //结点的数据域
	struct DNode* prev; //指向前驱结点
	struct DNode* next; //指向后继节点
}DNode,*DLinkList;

int InitDList(DLinkList& L) {
	L = new DNode;
	if (L == NULL) {
		cout << "内存分配失败" << endl;
		return ERROR;
	}
	L->next = L->prev = L; //头结点的前驱和后继都指向自己
	return OK;
}

//插入
int InsertDList(DLinkList& L, int i, ElemType e) {
	if (i <= 0) {
		cout << "位置必须大于0" << endl;
		return ERROR;
	}
	DNode* p = L;
	int j = 0;
	while (p && (j < i - 1)) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1) {
		cout << "超出链表范围" << endl;
		return ERROR;
	}
	DNode* s = new DNode;
	if (s == NULL) {
		cout << "内存分配失败" << endl;
		return ERROR;
	}
	s->elem = e;
	s->next = p->next;
	if (p->next) {
		p->next->prev = s;
	}
	s->prev = p;
	p->next = s;
	return OK;
}

//删除元素
int DeleteDList(DLinkList& L, int i, ElemType& e) {
	if (i < 0) {
		cout << "位置必须大于0" << endl;
		return ERROR;
	}
	DNode* p = L;
	int j = 0;
	while (p && (j < i)) {
		p = p->next;
		j++;
	}
	if (!p || j > i) {
		cout << "位置超出范围" << endl;
		return ERROR;
	}
	e = p->elem;
	p->prev->next = p->next;
	if (p->next) {
		p->next->prev = p->prev;
	}
	delete p;
	return OK;
}

//查找
DNode* LocateElem(DLinkList L, ElemType e) {
	DNode* p=L->next;
	while (p != L && p->elem != e) {
		p = p->next;
	}
	return (p == L) ? NULL : p;
}

//打印链表
void PrintDList(DLinkList L) {
	DNode* temp = L->next;
	while (temp != L) {
		cout << temp->elem << " ";
		temp = temp->next;
	}
	cout << endl;
}

//获取长度
int LengthDList(DLinkList L) {
	int length = 0;
	DNode* p = L->next;
	while (p != L) {
		length++;
		p = p->next;
	}
	return length;
}

//清空
void ClearDList(DLinkList& L) {
	DNode* p = L->next;
	while (p != L) {
		DNode* next = p->next;
		delete p;
		p = next;
	}
	L->next = L->prev = L;  // 重新初始化头结点
}

//尾部插入
int AppendDList(DLinkList& L, ElemType e) {
	DNode* s = new DNode;
	if (s == NULL) {
		cout << "内存分配失败!" << endl;
		return -1;
	}
	s->elem = e;

	// 找到链表的最后一个节点
	DNode* last = L->prev;
	last->next = s;
	s->prev = last;
	s->next = L;
	L->prev = s;

	return 0;
}

//头部插入
int PrependDList(DLinkList& L, ElemType e) {
	DNode* s = new DNode;
	if (s == NULL) {
		cout << "内存分配失败!" << endl;
		return -1;
	}
	s->elem = e;

	// 头结点的下一个节点
	DNode* first = L->next;
	L->next = s;
	s->prev = L;
	s->next = first;
	first->prev = s;

	return 0;
}

//按值删除
int DeleteByValue(DLinkList& L, ElemType e) {
	DNode* p = L->next;
	while (p != L && p->elem != e) {
		p = p->next;
	}
	if (p == L) {
		cout << "未找到要删除的元素: " << e << endl;
		return -1;
	}

	p->prev->next = p->next;
	if (p->next) {
		p->next->prev = p->prev;
	}
	delete p;

	return 0;
}

//反转链表
void ReverseDList(DLinkList& L) {
	DNode* p = L->next;
	DNode* q = NULL;
	while (p != L) {
		q = p->next;
		p->next = p->prev;
		p->prev = q;
		if (q == L) {
			L->next = p;
			p->prev = L;
		}
		p = q;
	}
}

//前插法创建双向链表
void CreateList_H(DLinkList& L, int n) {
	DNode* s;
	for (int i = 0; i < n; i++) {
		s = new DNode;
		if (s == NULL) {
			cout << "内存分配失败" << endl;
		}
		cin >> s->elem;
		s->next = L->next;  //新结点的next指向原头结点的next
		s->prev = L;        //新结点的prev指向头结点

		L->next->prev = s;  //原头结点的next的prev指向新结点
		L->next = s;
	}
}

//后插法创建双向链表
void CreateList_B(DLinkList& L, int n) {
	DNode* s;
	for (int i = 0; i < n; i++) {
		s = new DNode;
		if (s == NULL) {
			cout << "内存分配失败" << endl;
		}
		cin >> s->elem;
		s->next = L;  //新结点的next指向头结点
		s->prev = L->prev; //新结点的prev指向原尾结点

		L->prev->next = s; //原尾结点的next指向新结点
		L->prev = s;       //头结点的prev指向新结点
	}
}

int main() {
	DLinkList L;
	int choice, position, value, result,p;
	ElemType element;
	DNode* foundNode = NULL;  // 在这里声明和初始化 foundNode

	// 初始化双向链表
	if (InitDList(L) != OK) {
		cout << "初始化失败" << endl;
		return -1;
	}

	while (true) {
		cout << "\n双向链表操作菜单:" << endl;
		cout << "1. 插入元素" << endl;
		cout << "2. 删除元素(按位置)" << endl;
		cout << "3. 查找元素" << endl;
		cout << "4. 打印链表" << endl;
		cout << "5. 获取链表长度" << endl;
		cout << "6. 清空链表" << endl;
		cout << "7. 尾部插入" << endl;
		cout << "8. 头部插入" << endl;
		cout << "9. 按值删除" << endl;
		cout << "10. 反转链表" << endl;
		cout << "11. 头插法创建双向链表" << endl;
		cout << "12. 尾插法创建双向链表" << endl;
		cout << "0. 退出" << endl;
		cout << "请选择操作:";
		cin >> choice;

		switch (choice) {
		case 1:
			cout << "请输入插入的位置和元素:";
			cin >> position >> element;
			result = InsertDList(L, position, element);
			if (result == OK) {
				cout << "插入成功" << endl;
			}
			else {
				cout << "插入失败" << endl;
			}
			break;
		case 2:
			cout << "请输入要删除的位置:";
			cin >> position;
			result = DeleteDList(L, position, element);
			if (result == OK) {
				cout << "删除成功,被删除的元素是: " << element << endl;
			}
			else {
				cout << "删除失败" << endl;
			}
			break;
		case 3:
			cout << "请输入要查找的元素:";
			cin >> element;
			foundNode = LocateElem(L, element);  // 在这里使用 foundNode
			if (foundNode) {
				cout << "找到元素: " << foundNode->elem << endl;
			}
			else {
				cout << "未找到元素" << endl;
			}
			break;
		case 4:
			cout << "链表内容:";
			PrintDList(L);
			break;
		case 5:
			cout << "链表长度: " << LengthDList(L) << endl;
			break;
		case 6:
			ClearDList(L);
			cout << "链表已清空" << endl;
			break;
		case 7:
			cout << "请输入尾部插入的元素:";
			cin >> element;
			result = AppendDList(L, element);
			if (result == 0) {
				cout << "尾部插入成功" << endl;
			}
			else {
				cout << "尾部插入失败" << endl;
			}
			break;
		case 8:
			cout << "请输入头部插入的元素:";
			cin >> element;
			result = PrependDList(L, element);
			if (result == 0) {
				cout << "头部插入成功" << endl;
			}
			else {
				cout << "头部插入失败" << endl;
			}
			break;
		case 9:
			cout << "请输入要删除的元素:";
			cin >> element;
			result = DeleteByValue(L, element);
			if (result == 0) {
				cout << "按值删除成功" << endl;
			}
			else {
				cout << "按值删除失败" << endl;
			}
			break;
		case 10:
			ReverseDList(L);
			cout << "链表已反转" << endl;
			break;
		case 11:
			cout << "请输入链表的长度" << endl;
			cin >> p;
			CreateList_H(L, p);
			break;
		case 12:
			cout << "请输入链表的长度" << endl;
			cin >> p;
			CreateList_B(L,p);
			break;
		case 0:
			cout << "退出程序" << endl;
			return 0;
		default:
			cout << "无效的选择,请重新输入" << endl;
		}
	}
	return 0;
}

这个是双向链表的基本操作汇总,里面的操作大多和单链表相似,结合着双线链表的图还是很好理解的,这里讲一下我认为不太好理解的双向链表的反转操作:

反转双向链表的操作是将链表中的节点顺序完全颠倒过来。在双向链表中,每个节点都有一个 prev 指针指向前驱节点和一个 next 指针指向后继节点。反转链表时,我们需要交换这些指针的方向,使得原来的 next 指针变成 prev,原来的 prev 指针变成 next

这里给一个示例:

假设我们有一个双向链表 L,其内容为 1 <-> 2 <-> 3 <-> 4,现在我们要反转这个链表。以下是具体的步骤:

  1. 初始化
    • 双向链表 L1 <-> 2 <-> 3 <-> 4
    • p 从第一个实际节点 1 开始,q 初始化为 NULL
  2. 第一次迭代
    • p 指向 1q 保存 p->next 即 2
    • 交换 p 的 prev 和 nextp->next 指向 L(头结点),p->prev 指向 2
    • 移动 p 到 2
  3. 第二次迭代
    • p 指向 2q 保存 p->next 即 3
    • 交换 p 的 prev 和 nextp->next 指向 1p->prev 指向 3
    • 移动 p 到 3
  4. 第三次迭代
    • p 指向 3q 保存 p->next 即 4
    • 交换 p 的 prev 和 nextp->next 指向 2p->prev 指向 4
    • 移动 p 到 4
  5. 第四次迭代
    • p 指向 4q 保存 p->next 即 L(头结点)。
    • 交换 p 的 prev 和 nextp->next 指向 3p->prev 指向 L
    • 更新头结点的 next 指向 44 的 prev 指向 L
  6. 结果
    • 反转后的双向链表 L4 <-> 3 <-> 2 <-> 1

循环链表

#include <iostream>
using namespace std;

// 定义链表节点的数据类型
typedef int ElemType;
// 定义常量
#define OK 1
#define ERROR 0

// 定义循环链表的节点结构体
typedef struct CirNode {
    ElemType data; // 节点数据
    struct CirNode* next; // 指向下一个节点的指针
} CirNode, * CirLinkList; // 别名定义

// 初始化链表
int InitList(CirLinkList& L) {
    L = new CirNode; // 分配新的头节点
    L->data = 0; // 头节点数据初始化为0
    L->next = L; // 头节点指向自身形成循环
    return OK; // 返回成功标志
}

// 打印链表
void PrintList(CirLinkList L) {
    if (L == NULL || L->next == L) { // 如果链表为空或只有一个头节点
        cout << "链表为空" << endl;
        return;
    }
    CirNode* p = L->next; // 从第一个实际节点开始
    do {
        cout << p->data << " "; // 打印当前节点数据
        p = p->next; // 移动到下一个节点
    } while (p != L); // 当回到头节点时停止
    cout << endl; // 结束打印
}

// 前插法创建链表
void CreateList_H(CirLinkList& L, int n) {
    for (int i = 0; i < n; i++) {
        CirNode* s = new CirNode; // 创建新节点
        cin >> s->data; // 输入节点数据
        s->next = L->next; // 新节点插入到头节点之后
        L->next = s; // 更新头节点的next指针
    }
}

// 后插法创建链表
void CreateList_R(CirLinkList& L, int n) {
    CirNode* p = L; // 从头节点开始
    for (int i = 0; i < n; i++) {
        CirNode* s = new CirNode; // 创建新节点
        cout << "请输入第" << i + 1 << "个元素:";
        cin >> s->data; // 输入节点数据
        p->next = s; // 将新节点链接到当前节点之后
        p = s; // 移动到新节点
    }
    p->next = L; // 形成循环
}

// 查找元素
void Find(CirLinkList L, int e) {
    CirNode* p = L->next; // 从第一个实际节点开始
    do {
        if (p->data == e) { // 如果找到目标元素
            cout << "找到元素" << e << endl;
            return;
        }
        p = p->next; // 移动到下一个节点
    } while (p != L); // 当回到头节点时停止
    cout << "未找到元素" << e << endl; // 未找到则输出提示
}

// 清理链表
void FreeList(CirLinkList& L) {
    if (L == NULL) return; // 如果链表为空直接返回

    CirNode* current = L->next; // 从第一个实际节点开始
    CirNode* next; // 用于保存下一个节点的指针

    do {
        next = current->next; // 保存下一个节点
        delete current; // 删除当前节点
        current = next; // 移动到下一个节点
    } while (current != L->next); // 当回到第一个实际节点时停止

    delete L; // 删除头节点
    L = NULL; // 设置链表为空
}

// 插入操作(头部)
void Insert_H(CirLinkList& L, ElemType e) {
    CirNode* s = new CirNode; // 创建新节点
    s->data = e; // 设置新节点数据
    if (L == NULL || L->next == L) { // 如果链表为空或只有一个头节点
        L->next = s; // 新节点成为唯一节点
        s->next = L; // 形成循环
    }
    else {
        s->next = L->next; // 新节点插入到头节点之后
        L->next = s; // 更新头节点的next指针
    }
}

// 插入操作(尾部)
void Insert_T(CirLinkList& L, ElemType e) {
    CirNode* s = new CirNode; // 创建新节点
    s->data = e; // 设置新节点数据
    if (L == NULL || L->next == L) { // 如果链表为空或只有一个头节点
        L->next = s; // 新节点成为唯一节点
        s->next = L; // 形成循环
    }
    else {
        CirNode* p = L; // 从头节点开始
        while (p->next != L) { // 寻找最后一个节点
            p = p->next;
        }
        p->next = s; // 将新节点链接到最后一个节点之后
        s->next = L; // 形成循环
    }
}

// 插入操作(中间)
void Insert_M(CirNode* p, ElemType e) {
    if (p == NULL) return; // 如果指定位置为空则不执行

    CirNode* s = new CirNode; // 创建新节点
    s->data = e; // 设置新节点数据
    s->next = p->next; // 新节点插入到指定位置之后
    p->next = s; // 更新前驱节点的next指针
}

// 循环链表的归并
CirLinkList MergeList(CirLinkList& La, CirLinkList& Lb) {
    if (La == NULL || La->next == La) { // 如果La为空或只有一个头节点
        return Lb; // 返回Lb
    }
    if (Lb == NULL || Lb->next == Lb) { // 如果Lb为空或只有一个头节点
        return La; // 返回La
    }

    CirNode* p = new CirNode; // 创建新的头节点
    p->data = 0; // 头节点数据初始化为0
    p->next = p; // 形成循环
    CirNode* p1 = La->next; // La的第一个实际节点
    CirNode* p2 = Lb->next; // Lb的第一个实际节点
    CirNode* tail = p; // 新链表的尾节点

    while (p1 != La && p2 != Lb) { // 遍历两个链表
        if (p1->data <= p2->data) { // 如果La的节点小于等于Lb的节点
            tail->next = p1; // 将La的节点链接到新链表
            p1 = p1->next; // 移动到La的下一个节点
        }
        else {
            tail->next = p2; // 将Lb的节点链接到新链表
            p2 = p2->next; // 移动到Lb的下一个节点
        }
        tail = tail->next; // 更新新链表的尾节点
    }

    // 连接剩余的节点
    tail->next = (p1 != La) ? p1 : p2;
    while (tail->next != La && tail->next != Lb) {
        tail = tail->next;
    }
    tail->next = p; // 形成循环

    delete La; // 释放La的头节点
    delete Lb; // 释放Lb的头节点

    return p; // 返回合并后的链表
}

// 删除操作
void DeleteNode(CirLinkList& L, CirNode* p) {
    if (p == NULL || p->next == L) return; // 如果指定位置为空或为头节点则不执行

    CirNode* q = p->next; // 获取要删除的节点
    if (q == L) { // 如果要删除的是最后一个节点
        while (p->next != L) { // 寻找倒数第二个节点
            p = p->next;
        }
        p->next = L->next; // 更新倒数第二个节点的next指针
        delete L; // 释放头节点
        L = p; // 更新链表头
    }
    else {
        p->next = q->next; // 更新前驱节点的next指针
        delete q; // 释放被删除节点
    }
}

int main() {
    CirLinkList L = NULL; // 初始化主链表
    int choice, n, e, i;
    CirNode* p;

    while (true) {
        cout << "\n请选择操作:" << endl;
        cout << "1. 初始化链表" << endl;
        cout << "2. 前插法创建链表" << endl;
        cout << "3. 后插法创建链表" << endl;
        cout << "4. 打印链表" << endl;
        cout << "5. 查找元素" << endl;
        cout << "6. 插入节点(头部)" << endl;
        cout << "7. 插入节点(尾部)" << endl;
        cout << "8. 插入节点(中间)" << endl;
        cout << "9. 归并链表" << endl;
        cout << "10. 删除节点" << endl;
        cout << "11. 退出" << endl;
        cout << "输入选项: ";
        cin >> choice;

        switch (choice) {
        case 1:
            InitList(L);
            cout << "链表已初始化" << endl;
            break;
        case 2:
            cout << "请输入要创建的节点数: ";
            cin >> n;
            CreateList_H(L, n);
            break;
        case 3:
            cout << "请输入要创建的节点数: ";
            cin >> n;
            CreateList_R(L, n);
            break;
        case 4:
            PrintList(L);
            break;
        case 5:
            cout << "请输入要查找的元素: ";
            cin >> e;
            Find(L, e);
            break;
        case 6:
            cout << "请输入要插入的元素: ";
            cin >> e;
            Insert_H(L, e);
            break;
        case 7:
            cout << "请输入要插入的元素: ";
            cin >> e;
            Insert_T(L, e);
            break;
        case 8:
            cout << "请输入要插入的位置 (节点数据): ";
            cin >> e;
            p = L;
            while (p->next != L && p->next->data != e) {
                p = p->next;
            }
            if (p->next != L) {
                cout << "请输入要插入的元素: ";
                cin >> e;
                Insert_M(p, e);
            }
            else {
                cout << "未找到指定位置" << endl;
            }
            break;
        case 9: {
            CirLinkList Lb = NULL;
            InitList(Lb); // 确保 Lb 被初始化
            cout << "请输入第二个链表的节点数: ";
            cin >> n;
            CreateList_R(Lb, n);
            L = MergeList(L, Lb);
            cout << "链表已归并" << endl;
            break;
        }
        case 10:
            cout << "请输入要删除的位置 (节点数据): ";
            cin >> e;
            p = L;
            while (p->next != L && p->next->data != e) {
                p = p->next;
            }
            if (p->next != L) {
                DeleteNode(L, p);
            }
            else {
                cout << "未找到指定位置" << endl;
            }
            break;
        case 11:
            FreeList(L);
            return 0;
        default:
            cout << "无效的选择,请重新输入" << endl;
        }
    }

    return 0;
}

循环链表基本操作,这个写的更简单,甚至连一点健壮性都没加,但是里面的步骤基本都加上注释了。剩下的里面难懂的操作等我有空再补充。

写在最后

链表比顺序表难写不少,断断续续写了三天才差不多写完,里面还有不少例子什么的没补充,等我缓缓再更新。这篇文章前前后后已经修改了二十多次了,基本上是把线性表的链式结构都写出来了,截止到目前,双向链表还是不太全面,但可能不会再考虑补充,循环链表也就提了点概念性的东西,具体操作没有罗列出来,以后可能会写出来。先写到这吧2024/09/29。在进行操作的时候发现双向链表的例子少了创建,补了一下2024/10/07。补充了循环链表的操作例子2024/10/16