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

网站建设seo优化推广劳动局免费培训电工

news 2026/4/7 12:06:34
网站建设seo优化推广,劳动局免费培训电工,引用网站的内容如何做注释,腾讯会议收费目录 前言 一、链表的分类 二、双向循环链表 2.1 开辟新的节点 2.2 链表初始化 2.3 打印链表 2.4 链表的尾插 2.5 链表的头插 2.6 链表的尾删 2.7 链表的头删 2.8 查找链表 2.9 在pos位置之后插入数据 2.10 删除pos位置的数据 三、完整代码实现 四、顺序表和双向…

目录

前言

一、链表的分类

二、双向循环链表

2.1 开辟新的节点

2.2 链表初始化

2.3 打印链表

2.4 链表的尾插

2.5 链表的头插

2.6 链表的尾删

2.7 链表的头删

2.8 查找链表

2.9 在pos位置之后插入数据

2.10 删除pos位置的数据

三、完整代码实现

四、顺序表和双向链表的优缺点分析

总结

前言

我们之前讲了顺序表和单链表，它们但是线性表的一种，今天我们来讲链表中的双向循环链表。

一、链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：
其中分为：

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构： 单链表 和 双向带头循环链表
1. 无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希图、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了。

二、双向循环链表

我们之前讲了单链表，今天我们来实现双向带头循环链表。

接口实现：

//list.h//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//打印链表
void LTPrint(LTNode* phead);//尾插 在最后有效节点或者哨兵位前插入都是尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插 在第一个有效节点之前插入
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos后面插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的数据
void LTErase(LTNode* pos);//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);void LTDesTroy(LTNode* phead);

在实现代码前，我们要先用结构体来定义链表的类型。由于是循环链表，所以我们需要两个指针，分别指向节点的前驱节点和后继节点。

typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {LTDataType data;struct ListNode* prev;//前驱节点struct ListNode* next;//后继节点
}LTNode;

2.1 开辟新的节点

在初始化之前，我们来实现开辟新的节点

//新的节点
LTNode* LTBuyNode(LTDataType x) {//为新的节点开辟空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;//让新节点头尾相连newNode->next = newNode->prev = newNode;return newNode;
}

2.2 链表初始化

链表的初始化我们可以有两种写法：

//写法一 传入头节点的地址
void LTInit(LTNode** pphead) {assert(pphead);//哨兵位*pphead = LTBuyNode(-1);
}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {LTNode* pphead = LTBuyNode(-1);return pphead;
}

我们给哨兵位的值赋为-1(任意都可以，哨兵位不作为有效数据)。

我们更推荐使用第二种方法，因为保持接口的一致性。

2.3 打印链表

如果我们往链表中插入数据，可以通过打印知道是否插入成功

void LTPrint(LTNode* phead) {assert(phead);//从哨兵位下一个节点开始打印LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

其中要注意的是循环开始是从哨兵位下一个节点开始的，结束条件是pcur走到哨兵位，即遍历了整个链表。

2.4 链表的尾插

void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);//要插入的新的节点LTNode* newNode = LTBuyNode(x);//phead phead->prev newNodenewNode->next = phead;newNode->prev = phead->prev;phead->prev->next = newNode;phead->prev = newNode;
}

尾插入一个节点，我们要改变的是哨兵位，哨兵位的前驱节点(即尾节点)，新节点三个节点的指向

2.5 链表的头插

void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);//插入的新节点LTNode* newNode = LTBuyNode(x);//phead phead->next newNodenewNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}

头插入一个节点，我们要改变的是哨兵位，哨兵位的后继节点(即第一个有效数据节点)，新节点三个节点的指向

2.6 链表的尾删

void LTPopBack(LTNode* phead) {assert(phead);//链表不为空assert(phead->next != phead);//phead phead->prev->prev(prev) phead->prev(del)LTNode* prev = phead->prev->prev;LTNode* del = phead->prev;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}

尾部删除一个节点，我们要改变的是删除元素的前驱节点，哨兵位的指向，最后释放删除节点

2.7 链表的头删

void LTPopFront(LTNode* phead) {assert(phead);//链表不为空assert(phead->next != phead);//phead phead->next(del) phead->next->next(next)LTNode* del = phead->next;LTNode* next = phead->next->next;phead->next = next;next->prev = phead;free(del);del = NULL;
}

头部删除一个节点，我们要改变的是哨兵位，删除节点的后继节点，最后释放删除节点

2.8 查找链表

如果我们要指定位置插入或者删除，我们就要找到这个位置，我们进行链表的查找

LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}

如果存在返回当前节点，不存在返回空。

2.9 在pos位置之后插入数据

void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newNode = LTBuyNode(x);//newNode pos pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}

我们要改变新节点，pos节点，pos节点的后继节点的指向。

注意：我们要先把pos的后继节点的前驱节点指向新节点，才能把pos的后继节点指向新节点，不然反过来会找不到pos节点后继节点的位置。

2.10 删除pos位置的数据

//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

我们要改变新节点，pos节点的前驱，pos节点的后继节点的指向。

2.11 销毁链表

因为每个节点都是单独开辟的空间，所以我们要依次销毁。

//方法一
void LTDesTroy(LTNode** pphead) {assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}
//方法二
void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur =next;}free(phead);phead = NULL;
}

与链表的初始化一样，我们有两种方法，但是我们一般选择第二种方法，为了保持接口的一致性，但是第二种方法我们要在函数外面手动给链表置为空。

三、完整代码实现

list.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//双向循环链表结构体类型
typedef struct ListNode {LTDataType data;struct ListNode* prev;//前驱节点struct ListNode* next;//后继节点
}LTNode;//链表初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();//打印链表
void LTPrint(LTNode* phead);//尾插 在最后有效节点或者哨兵位前插入都是尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插 在第一个有效节点之前插入
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos后面插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置的数据
void LTErase(LTNode* pos);//销毁链表 保持接口一致性
//void LTDesTroy(LTNode** pphead);void LTDesTroy(LTNode* phead);

list.c

#include"list.h"//新的节点
LTNode* LTBuyNode(LTDataType x) {//为新的节点开辟空间LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));if (newNode == NULL) {perror("malloc fail!");exit(1);}newNode->data = x;//让新节点头尾相连newNode->next = newNode->prev = newNode;return newNode;
}//链表初始化
//写法一 传入头节点的地址
//void LTInit(LTNode** pphead) {
//	assert(pphead);
//   哨兵位
//	*pphead = LTBuyNode(-1);
//}
//写法二 返回哨兵位,不传入值
LTNode* LTInit() {LTNode* pphead = LTBuyNode(-1);return pphead;
}//打印链表
void LTPrint(LTNode* phead) {assert(phead);//从哨兵位下一个节点开始打印LTNode* pcur = phead->next;while (pcur != phead) {printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//尾插	
void LTPushBack(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = LTBuyNode(x);//phead phead->prev newNodenewNode->next = phead;newNode->prev = phead->prev;phead->prev->next = newNode;phead->prev = newNode;
}//头插	
void LTPushFront(LTNode* phead, LTDataType x) {assert(phead);LTNode* newNode = LTBuyNode(x);//phead phead->next newNodenewNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}//尾删
void LTPopBack(LTNode* phead) {assert(phead);assert(phead->next != phead);//phead phead->prev->prev(prev) phead->prev(del)LTNode* prev = phead->prev->prev;LTNode* del = phead->prev;phead->prev = prev;prev->next = phead;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead) {assert(phead);assert(phead->next != phead);//phead phead->next(del) phead->next->next(next)LTNode* del = phead->next;LTNode* next = phead->next->next;phead->next = next;next->prev = phead;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x) {assert(pos);LTNode* newNode = LTBuyNode(x);//newNode pos pos->nextnewNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}//删除pos位置的数据
void LTErase(LTNode* pos) {assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁链表
/*void LTDesTroy(LTNode** pphead) {assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead) {LTNode* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}*/
void LTDesTroy(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead) {LTNode* next = pcur->next;free(pcur);pcur =next;}free(phead);phead = NULL;
}

listest.c

#include"list.h"void Listest() {//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist=LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);//1 2 3 4;LTPrint(plist);//头插/*LTPushFront(plist, 8);LTPushFront(plist, 7);LTPushFront(plist, 6);LTPushFront(plist, 5);LTPrint(plist);*///尾删/*	LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);//删除失败，链表为空//LTPopBack(plist);*///头删/*LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);//删除错误链表为空//LTPopFront(plist);*///查找LTNode* retFInd = LTFind(plist,1);/*if (retFInd) {printf("找到了\n");}else {printf("没找到\n");}*///在pos后面插入数据/*LTInsert(retFInd, 50);LTPrint(plist);*///删除pos位置上的数据/*LTErase(retFInd);LTPrint(plist);*///销毁链表//LTDesTroy(&plist);//保持接口一致性LTDesTroy(plist);plist = NULL;
}int main() {Listest();return 0;
}

四、顺序表和双向链表的优缺点分析

不同点
顺序表
链表（单链表）
存储空间上
物理上⼀定连续
逻辑上连续，但物理上不⼀定连续
随机访问
⽀持O(1)
不⽀持：O(N)
任意位置插⼊或删除元素
可能需要搬移元素，效率低O(N)
只需修改指针指向
插⼊
动态顺序表，空间不够时需要扩
容
没有容量的概念
应⽤场景
元素⾼效存储+频繁访问
任意位置插⼊和删除频繁

总结

上述文章我们讲了链表的双向带头循环链表的实现，希望对你有所帮助

http://www.hkea.cn/news/783657/

相关文章：

  • 江西网站做的好的企业文化百度指数在哪里看
  • 山东电商网站建设seo网站排名优化公司
  • 赤峰市做网站公司今日的最新消息
  • 上海最大的贸易公司seo网络推广机构
  • jsp 网站开发广告发布平台
  • b2c网站综合对比评价站长统计幸福宝
  • 网站建设意见做推广app赚钱的项目
  • 哈尔滨营销网站制作做外贸推广
  • 深圳网站建设外贸公司排名搜索热词排名
  • 网络科技公司招聘可靠吗seo多久可以学会
  • 企业网站建设的方案ppt网络营销的特点主要包括什么
  • 如何自行建设网站推广关键词优化
  • 建设学院网站百度收录关键词查询
  • 有关外贸的网站有哪些内容武汉抖音seo搜索
  • 娄底网站建设的话术深圳网站关键词排名优化
  • 福田大型商城网站建设seo营销方法
  • 网站开发专业就业指导企业网站设计与实现论文
  • 网络营销方式的思维导图seo关键词优化系统
  • wordpress访客ip记录福清市百度seo
  • 网站下载速度慢互联网广告推广公司
  • 电影网站空间配置网络营销的工具和方法有哪些
  • 包装设计网站免费百度seo搜索引擎优化厂家
  • 免费做公司网站sem对seo的影响有哪些
  • 网站空间购买费用关键词优化计划
  • 网站制作可以卖多少钱陕西网站建设制作
  • 深圳中小企业网站制作谷歌海外广告投放
  • 做游戏网站的需求分析创建app平台
  • 青岛胶南做网站的有多少seo商学院
  • 二月网站建设南宁百度个人中心登录
  • 如何在相关网站免费做宣传广告免费建立个人网站官网