链表/双向循环链表(C/C++)

发布时间:2024年01月24日

? ? ? ? 本篇将给出双向循环链表的有关操作,以及对应的一些解释,大多都以注释给出。本篇给出的双向循环链表全称为带头双向循环链表。即如下图所示:

? ? ? ? 在本篇中一共包含三个代码片段,分别为:双向链表需要实现的内容、双向链表函数的实现、双向链表的全部代码与测试。如有需要,可直接在对应位置查找。

? ? ? ? 其中的head,为头结点,我们也称之为哨兵位,该位置不会存放任何的有效数据,但这个结点是真实存在的。

? ? ? ? 注意:对于头结点(哨兵位)来说,由图我们可以得出:

? ? ? ? 1.哨兵位的下一位才是第一个结点,即head->next是第一个结点;

? ? ? ? 2.?哨兵位的前一个结点为尾结点,即head->prior为最后一个结点

? ? ? ? 对于哨兵为的意义来说就是:遍历循环链表的时避免死循环

1.双向链表的实现内容

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* prior;
	struct ListNode* next;
}LTNode;

//双向链表初始化
LTNode* LTInit();
//双向链表的销毁
void LTDestroy(LTNode* phead);
//判断链表是否为NULL
void LTEmpty(LTNode* phead);
//遍历双向链表
void LTPrint(LTNode* phead);

//尾插/头插
void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead, DataType x);

//尾删/头删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);

//查找结点位置
LTNode* LTFind(LTNode* phead, DataType x);  

//在指定位置之前/之后插入数据
void LTInsert(LTNode* pos, DataType x);
void LTInsertBefore(LTNode* pos, DataType x);

//删除指定位置
void LTErase(LTNode* pos);


2.双向链表函数的实现?

? ? ? ? 在以下的实现内容中的每个函数,都会有一定的注释,便于读者理解:

//创建一个头结点
LTNode* CreateNode(DataType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟空间是否成功,但其实一般情况下都是可以申请成功(以下判断条件可有可无)
	if (newNode == NULL) {
		perror("malloc:");
		exit(1);
	}
	newNode->data = x;
	//创建一个新结点的同时,将新节点的前驱和后继指向自己
	newNode->next = newNode->prior = newNode;
	return newNode;
}

//双向链表初始化
LTNode* LTInit() {
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	if (head == NULL) {
		perror("malloc:");
		exit(1);
	}
	head->data = -1;
	head->prior = head->next = head;
	//可以用创建结点函数来获取头结点
	//head = CreateNode(-1);
	return head;
}

//尾插,在尾结点插入一个元素
void LTPushBack(LTNode* phead,DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//尾结点的下一个结点指向的是头结点
	newNode->next = phead;
	//头结点的prior结点为尾结点,将新节点的前驱指向原来的尾结点
	newNode->prior = phead->prior;
	
	//phead->prior为原来的尾结点,将原来的尾结点指向newNode
	phead->prior->next = newNode;
	//phead->prior指向新节点
	phead->prior = newNode;
}

//头插,在第一个结点处插入元素
void LTPushFront(LTNode* phead, DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//将新节点的前驱指向头结点
	newNode->prior = phead;
	//新节点的后继指向原来的第一个结点
	newNode->next = phead->next;

	//phead->next为原来的头结点
	phead->next->prior = newNode;
	phead->next = newNode;
}

//尾删,删除链表的尾结点
void LTPopBack(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL,因为这是删除
	assert(phead->next != phead);
	//哨兵位的前一个结点为尾结点
	LTNode* delete = phead->prior;
	//prior为尾结点的前一个结点
	LTNode* prior = delete->prior;

	//将尾结点的前一个结点指向头结点
	prior->next = phead;
	//更新头结点的前驱(尾结点)
	phead->prior = prior;

	//释放空间,同时指针置为NULL
	free(delete);
	delete = NULL; 
}

//头删,删除链表的第一个结点
void LTPopFront(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL,因为这是删除
	assert(phead->next != phead);

	//phead->next为第一个结点
	LTNode* delete = phead->next;
	LTNode* next = delete->next;

	//将第二节点的前驱指向phead(delete->prior)
	next->prior = delete->prior;
	//更新第一个结点
	phead->next = next;

	//释放空间,同时指针置为NULL
	free(delete);
	delete = NULL;
}

//遍历链表
void LTPrint(LTNode* phead) {
	assert(phead);
	if (phead->next == phead) {
		printf("该链表为NULL\n");
		return;
	}
	//将current指向第一个结点
	LTNode* current = phead->next;
	printf("head->");
	//当current为头结点时,停止遍历
	while (current!= phead) {
		printf("%d->", current->data);
		current = current->next;
	}
	printf("head\n");
}

//判断链表是否为NULL
void LTEmpty(LTNode* phead) {
	assert(phead);
	//头结点的后继指向自己或者前驱指向自己时,链表为NULL
	if (phead->next == phead) {
		printf("空链表\n");
	}
	else {
		printf("非空链表\n");
	}
}

//链表的销毁
void LTDestroy(LTNode* phead) {
	assert(phead);
	//从第一个结点开始删除
	LTNode* current = phead->next;
	while (current != phead) {
		//先找到下一个结点
		LTNode* next = current->next;
		free(current);
		//更新current
		current = next;
	}
	//删除尾结点
	free(phead);
	//注:由于phead与传入的指针head同为一级指针,
	//free(phead)只能释放head存放的东西,
	//但不能改变head的地址,在函数外还需要将head置为NULL
}

//找元素
LTNode* LTFind(LTNode* phead, DataType x) {
	assert(phead);
	//从第一个结点开始遍历
	LTNode* current = phead->next;
	while (current != phead) {
		if (current->data == x) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}

//在指定位置尾插
void LTInsert(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->next = pos->next;
	newNode->prior = pos;

	//将pos位置的后继的proir指针指向新节点
	pos->next->prior = newNode;
	//pos的next指针指向新节点
	pos->next = newNode;
}

//在指定位置之前插入元素
void LTInsertBefore(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->prior = pos->prior;
	newNode->next = pos;

	//将pos位置的前驱的next指针指向新节点
	pos->prior->next = newNode;
	//将pos的prior指针指向新节点
	pos->prior = newNode;
}

//删除指定位置的元素
void LTErase(LTNode* pos) {
	assert(pos);
	//将pos位置的前驱结点和后继结点记录下来
	LTNode* prior = pos->prior;
	LTNode* next = pos->next;

	//前驱结点的next指针指向后继结点
	prior->next = next;
	//后继结点的proir指针指向前驱结点
	next->prior = prior;
	free(pos);
	pos = NULL;
}

3.双向链表的全部代码与测试

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode {
	DataType data;
	struct ListNode* prior;
	struct ListNode* next;
}LTNode;

//创建一个头结点
LTNode* CreateNode(DataType x) {
	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
	//判断开辟空间是否成功,但其实一般情况下都是可以申请成功(以下判断条件可有可无)
	if (newNode == NULL) {
		perror("malloc:");
		exit(1);
	}
	newNode->data = x;
	//创建一个新结点的同时,将新节点的前驱和后继指向自己
	newNode->next = newNode->prior = newNode;
	return newNode;
}

//双向链表初始化
LTNode* LTInit() {
	LTNode* head = (LTNode*)malloc(sizeof(LTNode));
	if (head == NULL) {
		perror("malloc:");
		exit(1);
	}
	head->data = -1;
	head->prior = head->next = head;
	//可以用创建结点函数来获取头结点
	//head = CreateNode(-1);
	return head;
}

//尾插,在尾结点插入一个元素
void LTPushBack(LTNode* phead,DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//尾结点的下一个结点指向的是头结点
	newNode->next = phead;
	//头结点的prior结点为尾结点,将新节点的前驱指向原来的尾结点
	newNode->prior = phead->prior;
	
	//phead->prior为原来的尾结点,将原来的尾结点指向newNode
	phead->prior->next = newNode;
	//phead->prior指向新节点
	phead->prior = newNode;
}

//头插,在第一个结点处插入元素
void LTPushFront(LTNode* phead, DataType x) {
	//传过来的头结点不能为NULL
	assert(phead);
	LTNode* newNode = CreateNode(x);
	//将新节点的前驱指向头结点
	newNode->prior = phead;
	//新节点的后继指向原来的第一个结点
	newNode->next = phead->next;

	//phead->next为原来的头结点
	phead->next->prior = newNode;
	phead->next = newNode;
}

//尾删,删除链表的尾结点
void LTPopBack(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL,因为这是删除
	assert(phead->next != phead);
	//哨兵位的前一个结点为尾结点
	LTNode* delete = phead->prior;
	//prior为尾结点的前一个结点
	LTNode* prior = delete->prior;

	//将尾结点的前一个结点指向头结点
	prior->next = phead;
	//更新头结点的前驱(尾结点)
	phead->prior = prior;

	//释放空间,同时指针置为NULL
	free(delete);
	delete = NULL; 
}

//头删,删除链表的第一个结点
void LTPopFront(LTNode* phead) {
	assert(phead);
	//第一个结点也不能为NULL,因为这是删除
	assert(phead->next != phead);

	//phead->next为第一个结点
	LTNode* delete = phead->next;
	LTNode* next = delete->next;

	//将第二节点的前驱指向phead(delete->prior)
	next->prior = delete->prior;
	//更新第一个结点
	phead->next = next;

	//释放空间,同时指针置为NULL
	free(delete);
	delete = NULL;
}

//遍历链表
void LTPrint(LTNode* phead) {
	assert(phead);
	if (phead->next == phead) {
		printf("该链表为NULL\n");
		return;
	}
	//将current指向第一个结点
	LTNode* current = phead->next;
	printf("head->");
	//当current为头结点时,停止遍历
	while (current!= phead) {
		printf("%d->", current->data);
		current = current->next;
	}
	printf("head\n");
}

//判断链表是否为NULL
void LTEmpty(LTNode* phead) {
	assert(phead);
	//头结点的后继指向自己或者前驱指向自己时,链表为NULL
	if (phead->next == phead) {
		printf("空链表\n");
	}
	else {
		printf("非空链表\n");
	}
}

//链表的销毁
void LTDestroy(LTNode* phead) {
	assert(phead);
	//从第一个结点开始删除
	LTNode* current = phead->next;
	while (current != phead) {
		//先找到下一个结点
		LTNode* next = current->next;
		free(current);
		//更新current
		current = next;
	}
	//删除尾结点
	free(phead);
	//注:由于phead与传入的指针head同为一级指针,
	//free(phead)只能释放head存放的东西,
	//但不能改变head的地址,在函数外还需要将head置为NULL
}

//找元素
LTNode* LTFind(LTNode* phead, DataType x) {
	assert(phead);
	//从第一个结点开始遍历
	LTNode* current = phead->next;
	while (current != phead) {
		if (current->data == x) {
			return current;
		}
		current = current->next;
	}
	return NULL;
}

//在指定位置尾插
void LTInsert(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->next = pos->next;
	newNode->prior = pos;

	//将pos位置的后继的proir指针指向新节点
	pos->next->prior = newNode;
	//pos的next指针指向新节点
	pos->next = newNode;
}

//在指定位置之前插入元素
void LTInsertBefore(LTNode* pos, DataType x) {
	assert(pos);
	LTNode* newNode = CreateNode(x);
	//改变新节点的前驱和后继指向
	newNode->prior = pos->prior;
	newNode->next = pos;

	//将pos位置的前驱的next指针指向新节点
	pos->prior->next = newNode;
	//将pos的prior指针指向新节点
	pos->prior = newNode;
}

//删除指定位置的元素
void LTErase(LTNode* pos) {
	assert(pos);
	//将pos位置的前驱结点和后继结点记录下来
	LTNode* prior = pos->prior;
	LTNode* next = pos->next;

	//前驱结点的next指针指向后继结点
	prior->next = next;
	//后继结点的proir指针指向前驱结点
	next->prior = prior;
	free(pos);
	pos = NULL;
}

void Test01() {
	LTNode* head = LTInit();
	LTPushBack(head, 1);
	LTPushBack(head, 2);
	LTPushBack(head, 3);
	LTPushBack(head, 4);
	LTPrint(head); // 1 2 3 4

	LTPushFront(head, 5);
	LTPushFront(head, 6);
	LTPushFront(head, 7);
	LTPrint(head); // 7 6 5 1 2 3 4

	LTPopBack(head);
	LTPrint(head); // 7 6 5 1 2 3 

	LTPopFront(head);
	LTPrint(head); // 6 5 1 2 3 


	LTNode* Find = LTFind(head, 3);
	if (Find == NULL) {
		printf("没有找到\n");    //找到了
	}
	else {
		printf("找到了\n");   
	}

	LTInsert(Find, 5); 
	LTInsertBefore(Find, 6); 
	LTPrint(head); // 6 5 1 2 6 3 5

	LTErase(Find);
	LTPrint(head); // 6 5 1 2 6 5
	LTDestroy(head);
	head = NULL;
}

int main() {
	Test01();
	return 0;
}

? ? ? ? 测试结果:

? ? ? ? 这些所有操作即为带头双向循环链表的所有操作了。?

文章来源:https://blog.csdn.net/m0_74830524/article/details/135830038
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。