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

004——双向链表和循环链表

news 来源：原创 2024/9/20 7:38:58

目录

双向链表

双向链表的初始化（与单链表类似）

增：

Ⅰ）头插法

Ⅱ）尾插法

Ⅲ）中间插入

删

改

查

整体代码示例：

 循环链表

循环单链表

​编辑 循环双链表

双向链表

不同于单链表，双向链表不仅可以往后指向，还可以往前指向，则双向链表是在单链表的基础上，每个结点增加一个指针域，这个指针域保存上一个结点的地址

pre指针域

（保存前一个结点的地址）

  数据域

    data

next指针域

（保存后一个结点的地址）

//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node,*LinkList;

 由003——单链表可知，单链表分为带头结点的不带头结点的，双向链表也是同理（上图的是带头结点的）

双向链表的初始化
（与单链表类似）

LinkList InitLinkList() {Node* p = (Node*)malloc(sizeof(Node));//申请头结点if (p == NULL) {printf("空间分配失败\n");}else {//p->data	脏数据，不用管p->pre=p->next = NULL;//注意：该语句的执行方向是从右往左/*p->pre = NULL;p->next = NULL;*/}return p;
}
int main() {LinkList L = InitLinkList();
}

增：

双向链表中增加一个结点（数据）

Ⅰ）头插法

固定在头结点和首元结点之间插入一个结点（头结点之后）如下图的例子

为了方便分析，我们为示意图进行编号 

注意，在这里对数据进行处理时，我们不能使得这个线（单向的，无论是正向还是负向）断掉，比如像下面这种情况，就是错误的

正确的顺序应该是先处理③和④，然后再处理①和②（顺序并不唯一）

 （下面代码并不完整）

//头插法：
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next = L->next;//4L->next= s;//1s->next->pre = s;//2}return L;
}

或者可以写成3421（还有其他写法）

        s->pre = L;
        s->next = L->next;
        L->next->pre = s;
        L->next = s;

此时还要考虑L为空的情况，因为这个时候的②是不存在的

所以在我们更改②这条线之前，需要进行一个判断

//头插法：
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next=L->next;//4L->next = s;//1if (s->next != NULL) {s->next->pre = s;//2}}return L;
}

Ⅱ）尾插法

从头结点开始遍历找到尾结点，在尾结点的后面插入新的结点（需要多维护一个pre）

//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p = L;	//指针指p向头结点while (p->next != NULL) {p = p->next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败\n");return L;}else {s->data = k;//将数据传给新申请的结点ss->next = p->next;s->pre = p;p->next = s;}return L;
}

Ⅲ）中间插入


//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p = L->next;while (p != NULL && p->data != k) {//出现NULL->data!=k会报错，所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空，要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p = find(L, x);if (p == NULL) {printf("数据%d不存在,无法找到插入位置，插入失败\n", x);return L;}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败，插入失败\n");return L;}else {s->data = k;s->next = p->next;p->next = s;if (s->next != NULL) {s->next->pre = s;}}return L;
}

删

删除如下面图示

修改后的结果

 

//删除
LinkList Delete(LinkList L, int k) {if (L->next == NULL) {printf("空链表，删除失败\n");return L;}//找到k所在的结点pNode* p = find(L, k);if (p == NULL) {printf("数据%d不存在，删除失败\n");return L;}//删除p->pre->next = p->next;if (p->next != NULL) {p->next->pre = p->pre;}//防止p成为空指针free(p);p = NULL;return L;}

改

修改代码与单链表是相同的

//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == NULL) {printf("数据%d不存在，无法找到修改位置，修改失败\n", x);return L;}else {p->data = k;}return L;
}

查

查找代码与单链表是相同的

Node* find(LinkList L, int k) {Node* p = L->next;while (p != NULL && p->data != k) {//出现NULL->data!=k会报错，所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空，要么保存所要数据
}

整体代码示例：

#include<stdio.h>
#include<stdlib.h>
//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node,*LinkList;LinkList InitLinkList() {Node* p = (Node*)malloc(sizeof(Node));//申请头结点if (p == NULL) {printf("空间分配失败\n");}else {//p->data	脏数据，不用管p->pre=p->next = NULL;//注意：该语句的执行方向是从右往左/*p->pre = NULL;p->next = NULL;*/}return p;
}//头插法：
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next=L->next;//4L->next = s;//1if (s->next != NULL) {s->next->pre = s;//2}}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p = L;	//指针指p向头结点while (p->next != NULL) {p = p->next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败\n");return L;}else {s->data = k;//将数据传给新申请的结点ss->pre = p;//3s->next = p->next;//4p->next = s;//1if (s->next != NULL) {s->next->pre = s;//2}}return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p = L->next;while (p != NULL && p->data != k) {//出现NULL->data!=k会报错，所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空，要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p = find(L, x);if (p == NULL) {printf("数据%d不存在,无法找到插入位置，插入失败\n", x);return L;}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败，插入失败\n");return L;}else {s->data = k;s->next = p->next;p->next = s;if (s->next != NULL) {s->next->pre = s;}}return L;
}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == NULL) {printf("数据%d不存在，无法找到修改位置，修改失败\n", x);return L;}else {p->data = k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L->next == NULL) {printf("空链表，删除失败\n");return L;}//找到k所在的结点pNode* p = find(L, k);if (p == NULL) {printf("数据%d不存在，删除失败\n");return L;}//删除p->pre->next = p->next;if (p->next != NULL) {p->next->pre = p->pre;}//防止p成为空指针free(p);p = NULL;return L;}void show(LinkList L) {Node* p = L->next;while (p != NULL){printf("%d\t", p->data);p = p->next;}
}int main() {LinkList L = InitLinkList();L = HeadInsert(L, 10);L = HeadInsert(L, 22);L = HeadInsert(L, 16);L = HeadInsert(L, 45);L = RearInsert(L, 77);L = MidInsert(L, 77,99);L = Delete(L, 10);show(L);return 0;}

运行结果

 循环链表

循环单链表

循环链表只需要让最后一个结点的指针域指向头结点

 那么循环链表和单链表几乎没有太大差异,只是在为空的一些位置改成头结点

#include<stdio.h>
#include<stdlib.h>
typedef struct Node {int data;		//该节点的数据struct Node* next;		
}Node,*LinkList;//初始化一个带头结点的空的循环链表
LinkList InitLinkList() {Node* s = (Node*)malloc(sizeof(Node));//申请头结点if (s == NULL) {printf("空间分配失败\n");}else {//s->data	脏数据，不用管s->next = s;//改变。。。。。。。。。。。。}return s;
}//头插法：
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->next = L->next;L->next = s;}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* p = L;	//指针指p向头结点while (p->next != L) {//改变。。。。。。。。。。。。p = p->next;}//循环结束后指针p指向最后一个结点//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败\n");return L;}else {s->data = k;//将数据传给新申请的结点ss->next = p->next;//改变。。。。。。。。。。。。p->next = s;}return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {Node* p = L->next;while (p!=L && p->data != k) {//改变。。。。。。。。。。。。
//出现NULL->data!=k会报错，所以这两项的顺序不可以颠倒p = p->next;}return p;//要么为空，要么保存所要数据
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//在元素x后面插入数据kNode* p = find(L, x);if (p == L) {//改变。。。。。。。。。。。。printf("数据%d不存在,无法找到插入位置，插入失败\n",x);return L;}Node* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败，插入失败\n");return L;}else {s->data = k;s->next = p->next;p->next = s;}return L;
}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == L) {//改变。。。。。。。。。。。。printf("数据%d不存在，无法找到修改位置，修改失败\n", x);return L;}else {p->data = k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L->next == L) {//改变。。。。。。。。。。。。printf("数据%d不存在，删除失败\n", k);return L;}//找到k所在的结点p和上一个结点Node* pre = L;Node* p = L->next;while (p!=L&&p->data!=k)//改变。。。。。。。。。。。。{pre = p;p = p->next;}if (p == L) {//改变。。。。。。。。。。。。printf("数据%d不存在，删除失败\n", k);return L;}pre->next = p->next;free(p);p = NULL;//防止p成为野指针return L;
}void show(LinkList L) {Node* p = L->next;while (p!= L)//改变。。。。。。。。。。。。{printf("%d\t", p->data);p = p->next;}
}
int main() {LinkList L = NULL;L = InitLinkList();L=HeadInsert(L,10);L = HeadInsert(L, 8);L = RearInsert(L, 15);L = MidInsert(L, 5, 55);L=Replace(L, 8, 88);L = Delete(L, 8);show(L);return 0;
}

运行结果：

 循环双链表

循环双链表与之同理


#include<stdio.h>
#include<stdlib.h>
//双向链表的结构体
typedef struct Node {struct Node* pre;int data;struct Node* next;
}Node, * LinkList;LinkList InitLinkList() {Node* p = (Node*)malloc(sizeof(Node));//申请头结点if (p == NULL) {printf("空间分配失败\n");}else {//p->data	脏数据，不用管//	p->next=p->pre=p;p->next = p;p->pre = p;}return p;
}//头插法：
LinkList HeadInsert(LinkList L, int k) {//先申请一个新的结点用来保存数据kNode* s = (Node*)malloc(sizeof(Node));if (s == NULL) {printf("空间分配失败/n");}else {s->data = k;//将数据传给新申请的结点ss->pre = L;//3s->next = L->next;//4L->next = s;//1s->next->pre = s;//2}return L;
}//尾插法
LinkList RearInsert(LinkList L, int k) {Node* s = (Node*)malloc(sizeof(Node));if (s == NULL){printf("空间分配失败\n");return L;}s->data = k;//找尾节点Node* p = L;while (p->next != L){p = p->next;}s->next = p->next;s->pre = p;p->next = s;s->next->pre = s;return L;
}//中间插入
//首先需要一个查找函数,并且返回该结点的地址
Node* find(LinkList L, int k) {//查找数据k所在的节点，并且返回该节点的地址 Node* p = L->next;while (p != L && p->data != k){p = p->next;}return p;
}
//中间插入的函数
Node* MidInsert(LinkList L, int x, int k) {//数据x后插入数据k Node* s = (Node*)malloc(sizeof(Node));if (s == NULL){printf("空间分配失败\n");return L;}s->data = k;//找x所在节点 Node* p = find(L, x);if (p == L){printf("数据%d不存在，插入失败\n", x);return L;}s->pre = p;//3s->next = p->next;//4p->next = s;//1s->next->pre = s;//2return L;}//修改
LinkList Replace(LinkList L, int x, int k) {Node* p = find(L, x);if (p == L) {printf("数据%d不存在，无法找到修改位置，修改失败\n", x);return L;}else {p->data = k;}return L;
}//删除
LinkList Delete(LinkList L, int k) {if (L->next == L){printf("空链表，删除失败\n");return L;}//找k所在的节点pNode* p = find(L, k);if (p == L){printf("数据%d不存在，删除失败\n", k);return L;}//删除：p->pre->next = p->next;p->next->pre = p->pre;free(p);p = NULL;return L;
}void show(LinkList L) {Node* p = L->next;while (p != L){printf("%d\t", p->data);p = p->next;}
}int main() {LinkList L = InitLinkList();L = HeadInsert(L, 10);L = HeadInsert(L, 22);L = HeadInsert(L, 16);L = HeadInsert(L, 45);L = RearInsert(L, 77);L = MidInsert(L, 77, 99);L = Delete(L, 10);show(L);return 0;}

 运行结果：

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 慎投！又一单位发布2024年高中风险预警期刊名单
  • Python | Leetcode Python题解之第389题找不同
  • Mac快速复制和删除命令
  • 编程珠玑3-6
  • wofstream写入文件没有反应的解决方案
  • 【腾讯云】AI驱动的数据库TDSQL-C如何是从0到1体验电商可视化分析小助手得统计功能，一句话就能输出目标统计图
  • 基于YOLOv8的PCB缺陷检测算法，加入一种基于内容引导注意力(CGA)的混合融合方案（一）
  • RS485工业通信网关原理详解-天拓四方
  • 2023下半年软考网络规划
  • Qt事件处理机制
  • 记一次Hiveserver2连接异常的解决-腾讯云-emr
  • python进阶篇-day09-数据结构与算法(非线性结构与排序算法)
  • 数据结构(7.2_1)——顺序查找
  • 彻底理解Proxy和Reflect
  • SQL server 6.5升级到SQL server 2019
  • #Java异常处理
  • [js高手之路]搞清楚面向对象,必须要理解对象在创建过程中的内存表示
  • 【162天】黑马程序员27天视频学习笔记【Day02-上】
  • flask接收请求并推入栈
  • HTML5新特性总结
  • JavaScript异步流程控制的前世今生
  • Java多态
  • js中forEach回调同异步问题
  • Koa2 之文件上传下载
  • mockjs让前端开发独立于后端
  • oschina
  • Python学习之路13-记分
  • sessionStorage和localStorage
  • Sublime Text 2/3 绑定Eclipse快捷键
  • tweak 支持第三方库
  • webpack4 一点通
  • 从0搭建SpringBoot的HelloWorld -- Java版本
  • 对超线程几个不同角度的解释
  • 复杂数据处理
  • 基于web的全景—— Pannellum小试
  • 基于遗传算法的优化问题求解
  • 记录一下第一次使用npm
  • 解决iview多表头动态更改列元素发生的错误
  • 聊聊springcloud的EurekaClientAutoConfiguration
  • 驱动程序原理
  • 如何使用 JavaScript 解析 URL
  • 如何正确配置 Ubuntu 14.04 服务器？
  • 使用阿里云发布分布式网站，开发时候应该注意什么？
  • 在Mac OS X上安装 Ruby运行环境
  • 怎么把视频里的音乐提取出来
  • # windows 安装 mysql 显示 no packages found 解决方法
  • ###51单片机学习（1）-----单片机烧录软件的使用，以及如何建立一个工程项目
  • #传输# #传输数据判断#
  • $redis-setphp_redis Set命令，php操作Redis Set函数介绍
  • (+3)1.3敏捷宣言与敏捷过程的特点
  • (42)STM32——LCD显示屏实验笔记
  • (vue)el-tabs选中最后一项后更新数据后无法展开
  • （附源码）spring boot车辆管理系统 毕业设计 031034
  • (免费领源码）Python#MySQL图书馆管理系统071718-计算机毕业设计项目选题推荐
  • *p++,*(p++),*++p,(*p)++区别？