分类导航

编程语言发布时间：2022-06-27 发布网站：大佬教程 code.js-code.com

大佬教程收集整理的这篇文章主要介绍了带头双向循环链表的实现@线性表，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

0. 引
1. 双向循环链表实现
- 1.1 创建、销毁、申请新节点、打印
- - 1.1.1 创建
  - 1.1.2 销毁
  - 1.1.3 申请新节点
  - 1.1.4 打印
- 1.2 尾插、尾删
- - 1.2.1 尾插
  - 1.2.2 尾删
- 1.3 头插、头删
- - 1.3.1头插
  - 1.3.2 头删
- 1.4 查找、任意位置插入、任意位置删除
- - 1.4.1 查找
  - 1.4.2 任意位置插入
  - 1.4.3 任意位置删除
  - 1.4.4 复用
2. 顺序表和链表的比较
附：
- `List.h`
- `List.c`
- `test.c`

🍓本文出现如此多草莓的原因是࿰c;我昨天晚上吃了好多草莓࿰c;并且现在还想吃。 🍓接下来要更新链表这儿的题解咯~

正文开始@边通书

0. 引

上文提到࿰c;带头双向循环链表 ——

结构最复杂࿰c;一般用在单独存储数据。实际中使用的链表数据结构࿰c;都是带头双向循环链表。
另外这个结构虽然复杂࿰c;却也是无死角的结构࿰c;用代码实现时会发现结构会带来很多优势࿰c;非常爽࿰c;后面我们代码实现了就知道了。

带头双向循环链表的实现@线性表

代码实现的简单归功于它复杂的结构࿰c;以下这几点都是在写的过程中感受到的 ——

🍓 带头

这样使得尾插尾删头插头删不必传二级指针࿰c;因为pList这个带哨兵位头节点的地址不会发生改变
尾删时࿰c;只剩一个节点和普遍情况(>=2个节点)可以合并

🍓 双向

方便找上一个下一个

🍓 循环

使找尾变得简单

1. 双向循环链表实现

1.1 创建、销毁、申请新节点、打印

1.1.1 创建

带头双向循环链表的实现@线性表

🍓 对于pList即这个链表地址的分配我们完全可以直接写࿰c;但还是推荐写成接口函数

🍓 初始化函数࿰c; 对于pList这个实参的改变࿰c;我们同样可以采取以往的办法传二级指针（即pList的地址类型࿰c;为LTNode**）

🍓 这里采取返回值的办法࿰c;返回地址࿰c;赋给pList

LTNode* LisTinit()
{
	//哨兵位的头结点
	LTNode* phead = (LTNode*)@H_43_173@malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	phead->prev = phead;
	phead->next = phead;
	
	return phead;
}

test.c中是这样调用的

	LTNode* pList = LisTinit();

1.1.2 销毁

带头双向循环链表的实现@线性表

void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	
	while (cur != phead)
	{
		LTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
	//phead = NULL;
}

注意这里的phead = NULL;很有必要࿰c;但这样写没有发挥实际作用（所以我也把它注释掉了）࿰c;因为phead是形参࿰c;形参改变不会影响实参࿰c;也就是pList不会改变。

这就导致了野指针的问题 —— 虽然pList仍保持着原来的地址࿰c;但是phead已经被释放了࿰c;此时pList就是一个野指针。（可以传二级࿰c;实际上传二级就不会有这些问题࿰c;但为了保持接口一致性用一级比较好）

因此࿰c;我们需要在外面࿰c;即test.c文件中把它置空 ——

	ListDestroy(pList);
	pList = NULL;//外面置空࿰c;就跟free一样

1.1.3 申请新节点

LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)@H_43_173@malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

1.1.4 打印

带头双向循环链表的实现@线性表

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) 
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("n");
}

1.2 尾插、尾删

1.2.1 尾插

带头双向循环链表的实现@线性表

🍓 相比于单链表

不必再传二级指针࿰c;因为phead不用更改
完美处理空链表࿰c;无需再把链表为空时的插入单拎出来解决
找尾也很方便O(1)࿰c;不必像单链表一样找尾找得好辛苦

void ListPushBACk(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
    
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

1.2.2 尾删

带头双向循环链表的实现@线性表

🍓 与单链表相比

不必再传二级指针࿰c;因为phead不用更改
不用单拎出来解决只剩一个节点时的情况࿰c;它的结构保证了tail不会为空࿰c;就不会被错误的解引用

void ListPopBACk(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//1.删空了
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	//链接
	phead->prev = tailPrev;
	tailPrev->next = phead;
}

1.3 头插、头删

1.3.1头插

带头双向循环链表的实现@线性表

🍓 与单链表相比

不必再传二级指针࿰c;因为phead不用更改
链表为空？也没事。其实这在单链表那儿也没事࿰c;就是情不自禁要想一下

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* headNext = phead->next;
	//链接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = headNext;
	headNext->prev = newnode;
}

1.3.2 头删

带头双向循环链表的实现@线性表

🍓 与单链表相比

不必再传二级指针࿰c;因为phead不用更改
只剩一个节点？也没事。其实这在单链表那儿也没事࿰c;就是情不自禁要想一下

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//删空时断言
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
	free(next);
	//链接
	phead->next = nextNext;
	nextNext->prev = phead;
}

1.4 查找、任意位置插入、任意位置删除

1.4.1 查找

和打印类似

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	//空链表
	if (phead->next == phead)
	{
		return NULL;
	}
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

1.4.2 任意位置插入

带头双向循环链表的实现@线性表

void LisTinsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posPrev = pos->prev;
	//链接
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

1.4.3 任意位置删除

带头双向循环链表的实现@线性表

void ListErase(LTNode* pos)
{
	//按理说应该断言一下pos是pList的情况࿰c;但是为了这个再增加一个参数࿰c;得不偿失
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	free(pos);
	//链接
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

1.4.4 复用

有了上面的任意位置插入删除࿰c;就可以快速写出头插头删、尾插尾删。

//尾插
void ListPushBACk(LTNode* phead, LTDataType x)
{
	assert(phead);
	LisTinsert(phead, x);
}

//尾删
void ListPopBACk(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//1.删空了
	ListErase(phead->prev);
}

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LisTinsert(phead->next, x);
}

//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//删空时断言
	ListErase(phead->next);
}

2. 顺序表和链表的比较

这两个结构各有优势࿰c;很难说谁更优࿰c;它们是相辅相成的结构。

	顺序表	链表（带头双向循环链表）
优点	1. 支持随机访问࿰c;需要随机访问支持的结构可以很好地适用	1. 任意位置插入删除效率高O(1)
	2. CPU高速缓存命中率高	2. 按需申请释放空间

缺点	1. 头部、中间插入效率低	1. 不支持随机访问（即下标访问࿰c;如要访问第5个）
	2. 连续的物理空间࿰c;空间不够了需要增容	2. 链表存储一个值࿰c;同时要存储两个指针࿰c;有一定消耗
	a. 增容有一定程度的消耗	3. CPU高速缓存命中率低
	b. 为了避免频繁增容࿰c;一般按倍数去增࿰c;用不完存在一定空间浪费

带头双向循环链表的实现@线性表

关于CPU高速缓存命中率࿰c;请阅读陈皓的文章与程序员相关的CPU缓存知识 | 酷壳 - CoolSHell࿰c;我顺便也读了࿰c;没法完全的懂࿰c;另外我还被他的其他文章拽走了࿰c;太有意思了࿰c;但还是解释一下CPU高速缓存命中率。

带头双向循环链表的实现@线性表

附：

`List.h`

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;

//带头双向循环---非常棒的结构
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;

//初始化
LTNode* LisTinit();
//链表打印
void ListPrint(LTNode* phead);
//销毁
void ListDestroy(LTNode* phead);

//尾插
void ListPushBACk(LTNode* phead, LTDataType x);
//尾删
void ListPopBACk(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//头删
void ListPopFront(LTNode* phead);
//查找
LTNode* ListFind(LTNode* phead, LTDataType x);


//任意位置插入
void LisTinsert(LTNode* pos, LTDataType x);
//任意位置删除
void ListErase(LTNode* pos);

`List.c`

#define _CRT_SECURE_NO_WARNINGS 1

#include@R_874_7468@ist.h"

LTNode* BuyListNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)@H_43_173@malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;

	return newnode;
}

LTNode* LisTinit()
{
	//哨兵位的头结点
	LTNode* phead = (LTNode*)@H_43_173@malloc(sizeof(LTNode));
	if (phead == NULL)
	{
		printf("malloc failedn");
		exit(-1);
	}
	phead->prev = phead;
	phead->next = phead;
	
	return phead;
}

void ListDestroy(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	
	while (cur != phead)
	{
		LTNode* curNext = cur->next;
		free(cur);
		cur = curNext;
	}
	free(phead);
	//phead = NULL;
}

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead) 
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("n");
}

void ListPushBACk(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	//链接
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
	//LisTinsert(phead, X);
}

void ListPopBACk(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//1.删空了
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	//链接
	phead->prev = tailPrev;
	tailPrev->next = phead;
	//ListErase(phead->prev);
}

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* headNext = phead->next;
	//链接
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = headNext;
	headNext->prev = newnode;
	//LisTinsert(phead->next, X);

}

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);//删空时断言
	LTNode* next = phead->next;
	LTNode* nextNext = next->next;
	free(next);
	//链接
	phead->next = nextNext;
	nextNext->prev = phead;
	//ListErase(phead->next);

}

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	//空链表
	if (phead->next == phead)
	{
		return NULL;
	}
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void LisTinsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* posPrev = pos->prev;
	//链接
	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

void ListErase(LTNode* pos)
{
	//按理说应该断言一下pos是pList的情况࿰c;但是为了这个再增加一个参数࿰c;得不偿失
	assert(pos);
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
	free(pos);
	//链接
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

`test.c`

#define _CRT_SECURE_NO_WARNINGS 1

#include@R_874_7468@ist.h"

//测试尾插尾删
void testList1()
{
	LTNode* pList = LisTinit();
	ListPushBACk(pList, 1);
	ListPushBACk(pList, 2);
	ListPushBACk(pList, 3);
	ListPrint(pList);

	ListPopBACk(pList);
	//ListPopBACk(pList);
	/*ListPopBACk(pList);
	ListPopBACk(pList);*/

	ListPrint(pList);
	ListDestroy(pList);
	pList = NULL;
}

//测试头插头删
void testList2()
{
	LTNode* pList = LisTinit();
	ListPushFront(pList, 1);
	ListPushFront(pList, 2);
	ListPushFront(pList, 3);
	ListPrint(pList);

	ListPopFront(pList);
	/*ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);*/

	ListPrint(pList);
	ListDestroy(pList);
	pList = NULL;

}

//测试查找、任意位置插入、任意位置插入
void testList3()
{
	LTNode* pList = LisTinit();
	ListPushBACk(pList, 1);
	ListPushBACk(pList, 2);
	ListPushBACk(pList, 4);
	ListPushBACk(pList, 5);
	ListPrint(pList);

	LTNode* ret = ListFind(pList, 4);
	if (ret == NULL)
	{
		printf("not foundn");
	}
	else
	{
		printf("%dn", ret->data);
	}
	LisTinsert(ret,3);
	ListPrint(pList);

	ListErase(ret);
	ListPrint(pList);

	ListDestroy(pList);
	pList = NULL;

}


int @H_43_173@main()
{
	//testList1();
	testList2();
	//testList3();
	return 0;
}

本文完@边通书

大佬总结

以上是大佬教程为你收集整理的带头双向循环链表的实现@线性表全部内容，希望文章能够帮你解决带头双向循环链表的实现@线性表所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。

标签：cap list php shell while 一致性参数查找程序员

上一篇: 1.文件描述符、文件句柄和打开文... 下一篇:Pointnet_part_seg

猜你在找的编程语言相关文章

IntelliJ IDEA2022.1.1永久破解教程永久激活码永久有效 2022-06-24
MySQL高级学习笔记 2022-06-22
圆环进度条两种实现方式 2022-06-22
今天公司来了个拿 30K 出来的测试，算是见识到了基础的天花板 2022-06-22
测试部门来了个00后卷王之王，老油条感叹真干不过，但是... 2022-06-22
九、忘记密码功能的实现 2022-06-22
基于 SpringBoot + MyBatis 的博客系统 2022-06-22
基于QT的超市信息管理系统 2022-06-22
Java实现贪吃蛇大作战小游戏（完整版） 2022-06-22
HCIP第三天学习笔记 2022-06-27

带头双向循环链表的实现@线性表

目录

0. 引

1. 双向循环链表实现

1.1 创建、销毁、申请新节点、打印

1.1.1 创建

1.1.2 销毁

1.1.3 申请新节点

1.1.4 打印

1.2 尾插、尾删

1.2.1 尾插

1.2.2 尾删

1.3 头插、头删

1.3.1头插

1.3.2 头删

1.4 查找、任意位置插入、任意位置删除

1.4.1 查找

1.4.2 任意位置插入

1.4.3 任意位置删除

1.4.4 复用

2. 顺序表和链表的比较

附：

List.h

List.c

test.c

大佬总结

`List.h`

`List.c`

`test.c`