-
2022-01-21 12:22:35
目录
一、链表的概念
1. 链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
双向循环链表示意图 2. 链表相邻结点不连续
由图可知,00A99740+12=00A9974C!=00A99788,即物理存储结构上相邻结点不连续。
ListPushBack(Head, 1);//尾插法生成结点 ListPushBack(Head, 2); ListPrint(Head); //打印链表 ListFind(Head,1); //查找结点 ListFind(Head,2); printf("一个结点的内存大小为:%d\n",sizeof(ListNode));
链表相邻结点地址不连续 二、双向循环链表的相关函数
1. 创建链表结点(增)
(1)创建结点
a. 在堆上申请空间
ListNode* Node = (ListNode*)malloc(sizeof(ListNode)); if (NULL == Node){//判断申请空间是否失败 assert(0); return 0; }
b. 存储数据
Node->data= data; Node->next = NULL; Node->pre = NULL;
c. 返回结点地址
return Node;
(2)尾插结点
假设结点newNode尾插在结点A后面
a. newNode的next指针指向头结点Head
newNode->next=Head ;
b. newNode的prev指针指向结点Head的prev所指向的结点(即A)
newNode->pre=Head->pre ;
c. A的next(即Head->pre->next)指向结点neNode
Head->pre->next = newNode;
d. newHead的prev指向结点P
Head->pre = newNode;
尾插图解 2. 删除链表结点(删)
a. 创建temp指针,指向Head->next所指向的结点
ListNode* temp = (*Head)->next;
b. 通过循环删除temp所指向的结点
while (temp != *Head){ //Head的next指向temp (*Head)->next = temp->next; free(temp); temp = (*Head)->next; } //删除temp所指向的结点后,temp再次指向Head->next所指向的结点
c. 删除头结点
free(*Head); *Head = NULL;
3. 查找链表结点(查)
a. 创建指针temp,指向头结点Head的下一个结点
ListNode* temp = Head->next;
b. 使用while循环寻找结点
while (temp!= Head){ temp = temp->next; }
c.创建flag变量判断是否找到结点
若flag==0,则未找到结点;若flag==1,则未找到结点;
int flag = 0; //找到结点 if (temp->data ==x){ printf("%d的地址为%p\n",x,temp); flag = 1; break; } //未找到结点 if (0 == flag){ printf("%d不在链表中\n",x); }
4. 修改链表结点(改)
a. 找到结点
ListNode* temp=ListFind(Head, x);
b. 修改内容
LTDataType flag = 0; printf("请输入你要修改的数字:"); scanf("%d",&flag); temp->data = flag;
三、归纳总结
带头双向循环链表是链表中结构最复杂的,但使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
(1)链表在物理存储结构上不连续
(2)链表尾插,请注意结点的链接顺序,避免断连。
Head->prev先链接newNode,造成找不到结点A(即无法使用Head->prev找到结点A),出现A的next无法连接newNode的情况。
结点指针断连 四、源码链接
更多相关内容 -
Python双向循环链表实现方法分析
2020-12-23 21:37:06本文实例讲述了Python双向循环链表实现方法。分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构。遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙。 我自己尝实现了一个... -
数据结构——“双向循环链表“ 易懂刨析双向循环链表(图解+代码)
2022-04-27 12:13:05循环链表单向循环链表双向循环链表1. 双向循环链表——插入2. 双向循环链表——删除 单向循环链表 关于两个循环链表合并为一个循环链表 双向循环链表 在单链表L中,查找ai的后继Next(L,a;),耗时仅为O(1),因为...循环链表
单向循环链表
循环链表和单链表的区别
-
表中最后结点的指针不是NULL,而是改为指向头结点,从而整个链表形成了一个环。
-
循环单链表中没有指针域为NULL的结点,故判空条件为判断
*A (表尾节点)
*A 的next
是否为头指针 -
空表:
if(A->next == H)
{ 空表 }
循环链表的特点
- 循环单链表插入,删除算法于单链表几乎一样
正是因为循环单链表是一个“环”,在任何位置插入和删除操作都是等价的,无须判断是否是表全。循环链表可以从任意一个结点开始遍历整个链表,循环链表不设头指针而仅设尾指针,若只
设置尾指针A,A->next即为头指针
,对表头,表尾进行操作都只要O(n).- 关于两个循环链表合并为一个循环链表
双向循环链表——概念
在单链表L中,查找
ai的后继
Next(L,a;),耗时仅为O(1)
,因为取ai后继指针即可。
但查找ai
的直接前驱Prior(L,ai);
则需从链表的头指针开始,找到结点ai前一结点
即是。故运算Prior(L,ai)
依赖表长n
,耗时为O(n)。另外,若链表中有一指针值被破坏,则整个链表脱节。这是单链表的不足为此,引入双向链表。先定义双向链表中的结点:
其中,data
和next
同单链表,增加一指针域prior
,其指向本结点的直接前驱
。
结点描述:typedef int data_t; typedef struct dnode_t { data_tdata; struct dnode_t *prior; struct dnode_t *next; }dlinknode_t , *dlinklist_t;
- 表L=(a0·····an-1)(设n=2) 的双向循环链表如图:
设p为链表中某结点的指针,有对称性:
(p->prior)->next = p =(p->next)->prior
- 双向链表的查找等运算基本上和单链表类似。
- 在双向循环链表中,某结点
*p 为尾结点
时,p->next == H
,当循环双链表尾空表时,某头结点的prior域
和next域
都等于H
下面我们学习一下双向循环链表的插入和删除运算
1. 双向循环链表——插入
插入: 即实现在链表L的第i结点前插入一结点x的运算,如图
① q->prior = p->prior; ② (p->prior)->next = q; ③ q->next = p; ④ p->prior=q;
- 算法思路:
调用查找算法Getlist(L,i);
,获取结点ai
的指针p
。若存在,申请一q结点
,存入元素x
,然后修改指针,将q结点插入p结点之前。
此算法时间复杂度主要算在查找算法getlist(L,i);
上,故T(n)=O(n)
;
2. 双向循环链表——删除
删除: 即实现删除链表
L
的第i结点
的运算,如图
- 算法思路:
调用查找算法Getlist(L,i);
,获取结点ai
的指针p
,若p存在,则修改指针删除
概念我们了解了,接下来我们要去实现双向链表的操作。
双向链表的插入创建
文件一:
dlist.h
插入创建双向链表#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); #endif
文件二:dlist.c
插入创建双向链表#include"dlist.h" //创建双向链表 dlistnode *dlist_create(){ dlistnode *H,*p,*r; int num; if(( H =(dlistnode *)malloc(sizeof(dlistnode))) == NULL){ puts("malloc failed"); return NULL; } //建立空双向链表 H->prior = H; //头结点前驱后继都指向自己 H->next = H; r = H; //指针r 指向头结点 //用户输入 while(1) { puts("please input(-1 exit):"); scanf("%d",&num); if(num == -1){ puts("-1 exit"); break; } if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){ puts("malloc failed"); return NULL; } //新节点赋值 p->data = num; //插入双向链表 p->prior = r; p->next = r->next; r->next = p; H->prior = p; r = p; } return H; } //遍历链表并输出链表数据 void dlist_show(dlistnode *H){ dlistnode *p; p = H->next; while(p != H){ printf("%d ",p->data); p=p->next; } puts(""); }
文件三:
test.c
插入创建双向链表#include"dlist.h" int main(){ dlistnode *H; H=dlist_create(); dlist_show(H); return 0; }
双向链表——查找
查找:
getlist(L,i);
提供要查找结点ai
的编号,返回指向该结点ai
的指针
结点个数 n=3;i的范围【0,n-1】
文件一:
dlist.h
插入创建双向链表#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); extern dlistnode *dlist_get(dlistnode *H,int pos); #endif
文件二:
dlist.c
按位查找双向链表dlistnode *dlist_get(dlistnode *H,int pos){ int i =-1; dlistnode *p = H; if(pos < 0){ puts("pos < 0,invalid"); return NULL; } while(i < pos){ p = p->next; i++; if(p == H){ puts("pos is invalid"); return NULL; } } return p; }
文件三:
test.c
用户输入按位查找双向链表#include"dlist.h" int main(){ dlistnode *H,*p; int pos; H=dlist_create(); dlist_show(H); //用户输入按位查找 while(1){ puts("input pos"); scanf("%d",&pos); p = dlist_get(H,pos); if(p){ printf("%d \n",p->data); } } return 0; }
双向链表——插入
插入: 即实现在链表L的第i结点前插入一结点x的运算,如图
- 算法思路:
调用查找算法Getlist(L,i);
,获取结点ai
的指针p
。若存在,申请一q结点
,存入元素x
,然后修改指针,将q结点插入p结点之前。
此算法时间复杂度主要算在查找算法getlist(L,i);
上,故T(n)=O(n)
;
文件一:
dlist.h
插入创建双向链表#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); extern dlistnode *dlist_get(dlistnode *H,int pos); extern int dlist_insert(dlistnode *H , int value ,int pos); #endif
文件二:
dlist.c
按位插入双向链表int dlist_insert(dlistnode *H , int value ,int pos){ dlistnode *p,*q; p = dlist_get(H,pos); if(p == NULL){ return -1; } if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){ puts("malloc failed"); return -1; } q->data = value; q->prior = p->prior; q->next = p; p->prior->next = q; q->prior = q; return 0; }
文件三:
test.c
用户输入按位插入双向链表#include"dlist.h" int main(){ dlistnode *H; int pos; H=dlist_create(); dlist_show(H); //用户输入按位查找 while(1){ puts("input pos"); scanf("%d",&pos); dlist_insert(H,100,pos); dlist_show(H); } return 0; }
双向链表——删除
删除: 即实现删除链表
L
的第i结点
的运算,如图
p->prior->next = p->next; p->next->prior = p-prior;
- 算法思路:
调用查找算法Getlist(L,i);
,获取结点ai
的指针p
,若p存在,则修改指针删除
文件一:dlist.h
插入创建双向链表
#ifndef __DLIST_H__ #define __DLIST_H__ #include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node *prior; struct node *next; }dlistnode; extern dlistnode *dlist_create(); extern void dlist_show(dlistnode *H); extern dlistnode *dlist_get(dlistnode *H,int pos); extern int dlist_insert(dlistnode *H , int value ,int pos); extern int dlist_delete(dlistnode *H ,int pos); #endif
文件二:
dlist.c
用户输入按位删除双向链表int dlist_delete(dlistnode *H ,int pos){ dlistnode *p; p = dlist_get(H,pos); if(p == NULL){ return -1; } p->prior->next = p->next; p->next->prior = p-prior; free(p); p=NULL; return 0; }
文件三:
test.c
用户输入按位删除双向链表#include"dlist.h" int main(){ dlistnode *H; int pos; H=dlist_create(); dlist_show(H); while(1){ puts("input pos"); scanf("%d",&pos); dlist_delete(H,pos); dlist_show(H); } return 0; }
-----------------------------------------很棒学习完了数据结构的 双向循环链表--------------------------------------------------
--------------------------------------------------------[下期预告:线性表的应用举例]------------------------------------------------------
-
-
【数据结构算法】③、双向链表和双向循环链表的实现、双向链表的创建-遍历-插入-删除-删除指定元素-查询...
2022-03-22 17:43:08【数据结构算法】③、双向链表和双向循环链表的实现、双向链表的创建-遍历-插入-删除-删除指定元素-查询指定元素、双向循环链表的创建-遍历-插入删除【数据结构算法】③、双向链表和双向循环链表的实现
数据结构与算法 总共分为19个系列
①、数据结构与算法[基础]+线性结构部分内容篇
②、单向循环链表的创建插入删除实现篇
③、双向链表和双向循环链表的实现篇③、双向链表和双向循环链表的实现篇
- 【数据结构算法】③、双向链表和双向循环链表的实现
- ⭐️本文章知识点大纲
- ⭐️双向链表
- ①、线性表 - 双向链表的介绍
- ②、线性表 - 双向链表 `创建`
- ③、线性表 - 双向链表 `插入`
- ④、线性表 - 双向链表 `删除`
- ⑤、线性表 - 双向链表 `删除指定元素`
- ⑥、线性表 - 双向链表 `查找元素`
- ⑦、线性表 - 双向链表 `更新`
- 💡⑧、双向链表end - 双向链表 - 综合代码
- ⭐️双向`循环`链表
- ①、线性表 - 双向循环链表的介绍
- ②、线性表 - 双向循环链表 `创建`
- ③、线性表 - 双向循环链表 `遍历`
- ④、线性表 - 双向循环链表 `插入`
- ⑤、线性表 - 双向循环链表 `删除`
- 💡⑤、双向循环链表end - 双向链表 - 综合代码
⭐️本文章知识点大纲
双向链表
- 双向链表的介绍
- 双向链表的介绍-创建遍历
- 双向链表的插入
- 双向链表的删除
- 双向链表的删除指定元素
- 双向链表的查找指定元素
双向循环链表
- 双向循环链表的介绍
- 双向循环链表的介绍-创建遍历
- 双向循环链表的插入
- 双向循环链表的删除
⭐️双向链表
①、线性表 - 双向链表的介绍
双向链表(创建/插入/删除/查找/替换)
双向链表的特点
每个节点都包含3个部分- 包含前驱 prior
- 包含数据源
- 包含后继 指针域
1.1 流程图 - 双向链表 - 单个节点
结构
1.2 流程图 - 双向链表
整个链表
双向链表 带有头节点 和不带有头节点的结构图
链表最好不要使用头插法。因为头插法插入的数据是倒序的
②、线性表 - 双向链表
创建
2.1 流程图 - 双向链表
创建
双向链表的 头节点的前驱
不是
L,而是空,后继也是空。因为我们不知道后继有没有东西。所以后继也要是空的。2. 🌰案例 - 双向链表 -
创建、遍历
代码实现#include <stdio.h> #include "string.h" #include "ctype.h" #include "stdlib.h" #include "math.h" #include "time.h" #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */ //定义结点 typedef struct Node{ ElemType data; struct Node *prior; // 前驱 struct Node *next; // 后继 }Node; typedef struct Node * LinkList; //5.1 创建双向链接 Status createLinkList(LinkList *L){ //*L 指向头结点 *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) return ERROR; (*L)->prior = NULL; (*L)->next = NULL; (*L)->data = -1; //新增数据 LinkList p = *L; // 创建一个临时变量 指向*L // 使用尾插法插入数据 插入10个数据 for(int i=0; i < 10;i++){ //1.创建1个临时的结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->prior = NULL; temp->next = NULL; temp->data = i; //2.为新增的结点建立双向链表关系 //① temp 是p的后继 p->next = temp; //② temp 的前驱是p temp->prior = p; //③ p 要记录最后的结点的位置,方便下一次插入 p = p->next; } return OK; } //5.2 打印循环链表的元素 void display(LinkList L){ // 不需要把头结点打印出来 // 所以拿到L->next 也就是头结点的下一个结点 LinkList temp = L->next; // 判断打印的结点是不是空 if(temp == NULL){ printf("打印的双向链表为空!\n"); return; } // 循环打印 while (temp) { printf("%d ",temp->data); temp = temp->next; } printf("\n"); } int main(int argc, const char * argv[]) { // insert code here... printf("Hello, World!\n"); Status iStatus = 0; LinkList L; int temp,item,e; iStatus = createLinkList(&L); printf("iStatus = %d\n",iStatus); printf("链表创建成功,打印链表:\n"); display(L); return 0; }
③、线性表 - 双向链表
插入
比如我要往AB中间插入一个C
也就是ACB
那么步骤流程就是
1.1 先找到A结点§
2.1 创建C结点 (temp)
3.1 把B(p-next)的前驱指向C .
3.2 把C结点(temp)的后继(next)指向B(p-next)。
4.1 把A的后继(next)指向C(temp).
4.2 把C结点的前驱指向A如果插入到尾部的时候情况
比如从ABC
插入一个D
那么步骤就是
1.1 先找到C结点§
2.1 创建D结点(temp)(后继一开始就是空的)
3.1 先把D的前驱 指向 C
3.2 把C的后继(p->next)(之前是空的) 指向D3.1 流程图 - 双向链表
插入
3.2 结果图 - 双向链表
插入
3. 🌰案例 - 双向链表 -
插入
代码实现//5.3 双向链表插入元素 Status ListInsert(LinkList *L, int i, ElemType data){ // 不能插入到头结点 头结点相当于牵头人 //1. 插入的位置不合法 为0或者为负数 if(i < 1) return ERROR; //2. 新建结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = data; temp->prior = NULL; temp->next = NULL; //3.将p指向头结点! LinkList p = *L; //4. 找到插入位置i直接的结点 // 这里是找插入的位置 for(int j = 1; j < i && p;j++) p = p->next; //5. 如果插入的位置超过链表本身的长度 if(p == NULL){ return ERROR; } //6. 判断插入位置是否为链表尾部; if (p->next == NULL) { p->next = temp; temp->prior = p; }else { //1️⃣ 将p->next 结点的前驱prior = temp p->next->prior = temp; //2️⃣ 将temp->next 指向原来的p->next temp->next = p->next; //3️⃣ p->next 更新成新创建的temp p->next = temp; //4️⃣ 新创建的temp前驱 = p temp->prior = p; } return OK; }
④、线性表 - 双向链表
删除
比如我要往ABC中间删除B
删除的步骤- 先找到A(变量p)
- 创建一个临时变量(delTemp)记录B
- 用A(变量p)的后继(next)
指向
B的前驱(deltemp的prior)的
指向
C的前驱(C的prior) - 然后C的前驱指向A的后续
- 把B结点删除 释放掉
4.2 结果图 - 双向链表
删除
4. 🌰案例 - 双向链表 -
删除
代码实现//5.4 删除双向链表指定位置上的结点 // e表示删除的元素 可以返回回去 Status ListDelete(LinkList *L, int i, ElemType *e){ int k = 1; LinkList p = (*L); //1.判断双向链表是否为空,如果为空则返回ERROR; if (*L == NULL) { return ERROR; } //2. 将指针p移动到删除元素位置前一个 while (k < i && p != NULL) { p = p->next; k++; } //3.如果k>i 或者 p == NULL 则返回ERROR if (k>i || p == NULL) { return ERROR; } //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数 LinkList delTemp = p->next; *e = delTemp->data; //5. p->next 等于要删除的结点的下一个结点 p->next = delTemp->next; //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p; if (delTemp->next != NULL) { delTemp->next->prior = p; } //7.删除delTemp结点 free(delTemp); return OK; }
⑤、线性表 - 双向链表
删除指定元素
比如我从一个双向链表1-10
我要删除5(变量p)
步骤- 找到p的前驱(prior) - 也就是4的(p->prior)
- 找到4的next 指向 6的前驱
(p->next->prior) - 没有找到 那么就将p=p->next
5. 🌰案例 - 双向链表 -
删除指定元素
代码实现//5.5 删除双向链表指定的元素 Status LinkListDeletVAL(LinkList *L, int data){ LinkList p = *L; //1.遍历双向循环链表 while (p) { //2.判断当前结点的数据域和data是否相等,若相等则删除该结点 if (p->data == data) { //修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣ p->prior->next = p->next; //修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣ if(p->next != NULL){ p->next->prior = p->prior; } //释放被删除结点p free(p); //退出循环 break; } //没有找到该结点,则继续移动指针p p = p->next; } return OK; }
⑥、线性表 - 双向链表
查找元素
6. 🌰案例 - 双向链表 -
删除指定元素
代码实现//5.6.1 在双向链表中查找元素 int selectElem(LinkList L,ElemType elem){ LinkList p = L->next; int i = 1; while (p) { if (p->data == elem) { return i; } i++; p = p->next; } return -1; }
⑦、线性表 - 双向链表
更新
7. 🌰案例 - 双向链表 -
更新
代码实现//5.6.2 在双向链表中更新结点 Status replaceLinkList(LinkList *L,int index,ElemType newElem){ LinkList p = (*L)->next; for (int i = 1; i < index; i++) { p = p->next; } p->data = newElem; return OK; }
💡⑧、双向链表end - 双向链表 - 综合代码
#include <stdio.h> #include "string.h" #include "ctype.h" #include "stdlib.h" #include "math.h" #include "time.h" #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */ //定义结点 typedef struct Node{ ElemType data; struct Node *prior; struct Node *next; }Node; typedef struct Node * LinkList; //5.1 创建双向链接 Status createLinkList(LinkList *L){ //*L 指向头结点 *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) return ERROR; (*L)->prior = NULL; (*L)->next = NULL; (*L)->data = -1; //新增数据 LinkList p = *L; for(int i=0; i < 10;i++){ //1.创建1个临时的结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->prior = NULL; temp->next = NULL; temp->data = i; //2.为新增的结点建立双向链表关系 //① temp 是p的后继 p->next = temp; //② temp 的前驱是p temp->prior = p; //③ p 要记录最后的结点的位置,方便下一次插入 p = p->next; } return OK; } //5.2 打印循环链表的元素 void display(LinkList L){ LinkList temp = L->next; if(temp == NULL){ printf("打印的双向链表为空!\n"); return; } while (temp) { printf("%d ",temp->data); temp = temp->next; } printf("\n"); } //5.3 双向链表插入元素 Status ListInsert(LinkList *L, int i, ElemType data){ //1. 插入的位置不合法 为0或者为负数 if(i < 1) return ERROR; //2. 新建结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = data; temp->prior = NULL; temp->next = NULL; //3.将p指向头结点! LinkList p = *L; //4. 找到插入位置i直接的结点 for(int j = 1; j < i && p;j++) p = p->next; //5. 如果插入的位置超过链表本身的长度 if(p == NULL){ return ERROR; } //6. 判断插入位置是否为链表尾部; if (p->next == NULL) { p->next = temp; temp->prior = p; }else { //1️⃣ 将p->next 结点的前驱prior = temp p->next->prior = temp; //2️⃣ 将temp->next 指向原来的p->next temp->next = p->next; //3️⃣ p->next 更新成新创建的temp p->next = temp; //4️⃣ 新创建的temp前驱 = p temp->prior = p; } return OK; } //5.4 删除双向链表指定位置上的结点 // e表示删除的元素 可以返回回去 Status ListDelete(LinkList *L, int i, ElemType *e){ int k = 1; LinkList p = (*L); //1.判断双向链表是否为空,如果为空则返回ERROR; if (*L == NULL) { return ERROR; } //2. 将指针p移动到删除元素位置前一个 while (k < i && p != NULL) { p = p->next; k++; } //3.如果k>i 或者 p == NULL 则返回ERROR if (k>i || p == NULL) { return ERROR; } //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数 LinkList delTemp = p->next; *e = delTemp->data; //5. p->next 等于要删除的结点的下一个结点 p->next = delTemp->next; //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p; if (delTemp->next != NULL) { delTemp->next->prior = p; } //7.删除delTemp结点 free(delTemp); return OK; } //5.5 删除双向链表指定的元素 Status LinkListDeletVAL(LinkList *L, int data){ LinkList p = *L; //1.遍历双向循环链表 while (p) { //2.判断当前结点的数据域和data是否相等,若相等则删除该结点 if (p->data == data) { //修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣ p->prior->next = p->next; //修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣ if(p->next != NULL){ p->next->prior = p->prior; } //释放被删除结点p free(p); //退出循环 break; } //没有找到该结点,则继续移动指针p p = p->next; } return OK; } //5.6.1 在双向链表中查找元素 int selectElem(LinkList L,ElemType elem){ LinkList p = L->next; int i = 1; while (p) { if (p->data == elem) { return i; } i++; p = p->next; } return -1; } //5.6.2 在双向链表中更新结点 Status replaceLinkList(LinkList *L,int index,ElemType newElem){ LinkList p = (*L)->next; for (int i = 1; i < index; i++) { p = p->next; } p->data = newElem; return OK; } int main(int argc, const char * argv[]) { // insert code here... printf("Hello, World!\n"); Status iStatus = 0; LinkList L; int temp,item,e; iStatus = createLinkList(&L); printf("iStatus = %d\n",iStatus); printf("链表创建成功,打印链表:\n"); display(L); printf("请输入插入的位置\n"); scanf("%d %d",&temp,&item); iStatus = ListInsert(&L, temp, item); printf("插入数据,打印链表:\n"); display(L); printf("请输入插入的位置\n"); scanf("%d %d",&temp,&item); iStatus = ListInsert(&L, temp, item); printf("插入数据,打印链表:\n"); display(L); printf("请输入插入的位置\n"); scanf("%d %d",&temp,&item); iStatus = ListInsert(&L, temp, item); printf("插入数据,打印链表:\n"); display(L); printf("请输入删除的位置\n"); scanf("%d",&temp); iStatus = ListDelete(&L, temp, &e); printf("删除元素: 删除位置为%d,data = %d\n",temp,e); printf("删除操作之后的,双向链表:\n"); display(L); printf("请输入你要删除的内容\n"); scanf("%d",&temp); iStatus = LinkListDeletVAL(&L, temp); printf("删除指定data域等于%d的结点,双向链表:\n",temp); display(L); printf("请输入你要查找的内容\n"); scanf("%d",&temp); ElemType index = selectElem(L, temp); printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",temp,index); printf("请输入你要更新的结点以及内容\n"); scanf("%d %d",&temp,&item); iStatus = replaceLinkList(&L, temp, item); printf("更新结点数据后的双向链表:\n"); display(L); return 0; }
⭐️双向
循环
链表①、线性表 - 双向循环链表的介绍
双向循环链表特点是:
最后一个结点的next指向链表的指针(*L)1.1 流程图 - 双向循环链表 -
整个链表结构
②、线性表 - 双向循环链表
创建
2. 🌰案例 - 双向循环链表
创建
代码实现//6.1 双向循环链表初始化 Status creatLinkList(LinkList *L){ *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) { return ERROR; } (*L)->next = (*L); (*L)->prior = (*L); //新增数据 LinkList p = *L; for(int i=0; i < 10;i++){ //1.创建1个临时的结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = i; //2.为新增的结点建立双向链表关系 //① temp 是p的后继 p->next = temp; //② temp 的前驱是p temp->prior = p; //③ temp的后继是*L temp->next = (*L); //④ p 的前驱是新建的temp p->prior = temp; //⑤ p 要记录最后的结点的位置,方便下一次插入 p = p->next; } return OK; }
③、线性表 - 双向循环链表
遍历
3. 🌰案例 - 双向循环链表
遍历
代码实现//6.3 遍历双向循环链表 Status Display(LinkList L){ if (L == NULL) { printf("打印的双向循环链表为空!\n\n"); return ERROR; } printf("双向循环链表内容: "); LinkList p = L->next; while (p != L) { printf("%d ",p->data); p = p->next; } printf("\n\n"); return OK; }
④、线性表 - 双向循环链表
插入
双向循环链表我们没有创建头结点
双向循环我们创建了头结点
因为有了头结点
我们插入的时候 不需要判断是不是要添加到首元节点
所以我们根本就不需要去判断*L 头部
尾部还是要判断的🌰说明步骤
比如在AB之间插入C
A表示(变量p)
C表示(temp)- 先判断索引值的异常 也就是在链表哪个位置进行插入
- 先找到 A(变量p)
- 创建C结点(temp)
- 将C结点的(next) 指向 B(p->next)
- 将B结点(p->next)的前驱(p->next->prior)指向C
- 将A结点(变量p)next 指向C结点(temp)
- 将C结点的前驱(temp->prior) 指向A结点(变量p)
4.1 结果图 - 双向循环链表
插入
4. 🌰案例 - 双向循环链表
插入
代码实现//6.2 双向循环链表插入元素 /*当插入位置超过链表长度则插入到链表末尾*/ Status LinkListInsert(LinkList *L, int index, ElemType e){ //1. 创建指针p,指向双向链表头 LinkList p = (*L); int i = 1; //2.双向循环链表为空,则返回error if(*L == NULL) return ERROR; //3.找到插入前一个位置上的结点p while (i < index && p->next != *L) { p = p->next; i++; } //4.如果i>index 则返回error if (i > index) return ERROR; //5.创建新结点temp LinkList temp = (LinkList)malloc(sizeof(Node)); //6.temp 结点为空,则返回error if (temp == NULL) return ERROR; //7.将生成的新结点temp数据域赋值e. temp->data = e; //8.将结点temp 的前驱结点为p; temp->prior = p; //9.temp的后继结点指向p->next; temp->next = p->next; //10.p的后继结点为新结点temp; p->next = temp; //如果temp 结点不是最后一个结点 if (*L != temp->next) { //11.temp节点的下一个结点的前驱为temp 结点 temp->next->prior = temp; }else{ (*L)->prior = temp; } return OK; }
⑤、线性表 - 双向循环链表
删除
逻辑基本上是和双向链表基本相似
考虑删除只有一个结点的情况(此时应该还有2个结点 包含头节点)5.1 结果图 - 双向循环链表
删除
5. 🌰案例 - 双向循环链表
删除
代码实现//6.4 双向循环链表删除结点 Status LinkListDelete(LinkList *L,int index,ElemType *e){ int i = 1; LinkList temp = (*L)->next; if (*L == NULL) { return ERROR; } //①.如果删除到只剩下首元结点了,则直接将*L置空; if(temp->next == *L){ free(*L); (*L) = NULL; return OK; } //1.找到要删除的结点 while (i < index) { temp = temp->next; i++; } //2.给e赋值要删除结点的数据域 *e = temp->data; //3.修改被删除结点的前驱结点的后继指针 图1️⃣ temp->prior->next = temp->next; //4.修改被删除结点的后继结点的前驱指针 图2️⃣ temp->next->prior = temp->prior; //5. 删除结点temp free(temp); return OK; }
💡⑤、双向循环链表end - 双向链表 - 综合代码
#include <stdio.h> #include "string.h" #include "ctype.h" #include "stdlib.h" #include "math.h" #include "time.h" #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 20 /* 存储空间初始分配量 */ typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */ //定义结点 typedef struct Node{ ElemType data; struct Node *prior; struct Node *next; }Node; typedef struct Node * LinkList; //6.1 双向循环链表初始化 Status creatLinkList(LinkList *L){ *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) { return ERROR; } (*L)->next = (*L); (*L)->prior = (*L); //新增数据 LinkList p = *L; for(int i=0; i < 10;i++){ //1.创建1个临时的结点 LinkList temp = (LinkList)malloc(sizeof(Node)); temp->data = i; //2.为新增的结点建立双向链表关系 //① temp 是p的后继 p->next = temp; //② temp 的前驱是p temp->prior = p; //③ temp的后继是*L temp->next = (*L); //④ p 的前驱是新建的temp p->prior = temp; //⑤ p 要记录最后的结点的位置,方便下一次插入 p = p->next; } return OK; } //6.2 双向循环链表插入元素 /*当插入位置超过链表长度则插入到链表末尾*/ Status LinkListInsert(LinkList *L, int index, ElemType e){ //1. 创建指针p,指向双向链表头 LinkList p = (*L); int i = 1; //2.双向循环链表为空,则返回error if(*L == NULL) return ERROR; //3.找到插入前一个位置上的结点p while (i < index && p->next != *L) { p = p->next; i++; } //4.如果i>index 则返回error if (i > index) return ERROR; //5.创建新结点temp LinkList temp = (LinkList)malloc(sizeof(Node)); //6.temp 结点为空,则返回error if (temp == NULL) return ERROR; //7.将生成的新结点temp数据域赋值e. temp->data = e; //8.将结点temp 的前驱结点为p; temp->prior = p; //9.temp的后继结点指向p->next; temp->next = p->next; //10.p的后继结点为新结点temp; p->next = temp; //如果temp 结点不是最后一个结点 if (*L != temp->next) { //11.temp节点的下一个结点的前驱为temp 结点 temp->next->prior = temp; }else{ (*L)->prior = temp; } return OK; } //6.3 遍历双向循环链表 Status Display(LinkList L){ if (L == NULL) { printf("打印的双向循环链表为空!\n\n"); return ERROR; } printf("双向循环链表内容: "); LinkList p = L->next; while (p != L) { printf("%d ",p->data); p = p->next; } printf("\n\n"); return OK; } //6.4 双向循环链表删除结点 Status LinkListDelete(LinkList *L,int index,ElemType *e){ int i = 1; LinkList temp = (*L)->next; if (*L == NULL) { return ERROR; } //①.如果删除到只剩下首元结点了,则直接将*L置空; if(temp->next == *L){ free(*L); (*L) = NULL; return OK; } //1.找到要删除的结点 while (i < index) { temp = temp->next; i++; } //2.给e赋值要删除结点的数据域 *e = temp->data; //3.修改被删除结点的前驱结点的后继指针 图1️⃣ temp->prior->next = temp->next; //4.修改被删除结点的后继结点的前驱指针 图2️⃣ temp->next->prior = temp->prior; //5. 删除结点temp free(temp); return OK; } int main(int argc, const char * argv[]) { // insert code here... printf("Hello, World!\n"); LinkList L; Status iStatus; ElemType temp,item; iStatus = creatLinkList(&L); printf("双向循环链表初始化是否成功(1->YES)/ (0->NO): %d\n\n",iStatus); Display(L); printf("输入要插入的位置和数据用空格隔开:"); scanf("%d %d",&temp,&item); iStatus = LinkListInsert(&L,temp,item); Display(L); printf("输入要删除位置:"); scanf("%d",&temp); iStatus = LinkListDelete(&L, temp, &item); printf("删除链表位置为%d,结点数据域为:%d\n",temp,item); Display(L); return 0; }
-
【C语言数据结构】双向循环链表
2022-03-06 22:05:00一、双向循环链表 循环结构 1.双向循环链表头文件及函数声明 2.初始化 1.结点构造 2.初始化函数 3.结点申请 4.数据插入 1.按位置插入 2.尾插 3.头插 5.查找 6.数据删除 1.按位置删除 2.按值删除 3.尾...目录
前言
这次我们将学习双向循环链表,首先了解双向链表和循环链表的定义和讲解。
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,是单链表的进阶,比单链表的结点结构多出一个指向前驱的指针域,如下图所示:
循环链表是一种链式储存结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。方法是将尾结点中的指针域进行使用,指向首结点,如下图所示:
双向循环链表即是将上述二者联合起来使用,以达到完成各类工作的效用,在以后大多数链表结构的使用中,我们都会选择双向循环链表。
一、双向循环链表
循环结构
双向循环链表的循环方式是其尾结点的后继指针指向头结点(表头),而头结点的前置指针指向尾结点,达到双向循环的目的,这样不仅使得对链表尾部的操作更为简单,也减少了对NULL指针的引用。
1.双向循环链表头文件及函数声明
新建头文件"dclist.h"(double circle list)对链表函数声明进行保存,方便我们后期查看及使用
#pragma once #include<stdio.h> #include<string.h> #include<assert.h> #include<ctype.h> #include<stdlib.h> typedef int Element; typedef struct DNode { Element data; DNode* next; DNode* prev; }DNode, * PDNode; //初始化链表 void InitList(PDNode plist); //购买结点 PDNode BuyNode(); //头插 bool Push_Front(PDNode plist, Element val); //尾插 bool Push_Back(PDNode plist, Element val); //按位置插 bool Insert_Pos(PDNode plist, int pos, Element val); //头删 bool Pop_Front(PDNode plist); //尾删 bool Pop_Back(PDNode plist); //按位置删 bool Erease_Pos(PDNode plist, int pos); //按值删 bool Erease_Val(PDNode plist, Element val); //查找 返回结点地址 PDNode Find(PDNode plist, Element val); //判空 bool IsEmpty(PDNode plist); //获取元素个数 int GetSize(PDNode plist); //打印链表 void Print(PDNode plist); //清空 void Clear(PDNode plist); //销毁 void Destroy(PDNode plist);
2.初始化
在对使用链表进行数据的储存之前,我们需要进行链表的初始化
1.结点构造
如图所示,带双向循环链表的结点由三部分构成:
1.数据域
2.指针域1:指向后继结点的指针
3.指针域2:指向前置结点的指针
typedef int Element;//如此对数据类型进行改名操作,若要进行修改数据类型操作会更加方便 typedef struct DNode { Element data; DNode* next;//后继指针 DNode* prev;//前置指针 }DNode, * PDNode;
2.初始化函数
与单链表不同的是,在双向循环链表不存在数据时,头结点的指针域不置为NULL,其后继指针与前置指针都指向头结点本身,以形成最基础的循环形态:
//初始化链表 void InitList(PDNode plist) { assert(plist != NULL); plist->next = plist->prev = plist; }
3.结点申请
因为链表的结构特性,我们需要对结点进行多次申请,为了方便进行其他函数操作,并且为了优化代码,我们将结点的申请封装于一个函数
//购买结点 PDNode BuyNode() { PDNode node = (PDNode)malloc(sizeof(DNode)); if (node == NULL) { exit(1); } memset(node, 0, sizeof(*node));//将申请的结点内存重置,防止数据残留 return node; }
4.数据插入
双向循环链表存在多个指针指向的断开和重新指向,我们在此先进行分析和讲解,如下图所示:
按照正常逻辑,我们再重新指定指针指向时,首先需要打破原有的指针指向,即上图中红叉部分,但实际编写程序中,我们会直接修改指针的指向,从而在代码中只会体现重新指向的过程。
在图中,已经标注出4个指针指向的修改,首先,我们应该对新申请的结点中指针(即图中34箭头的指向)进行指定,因为如果我们先对旧有指针进行修改,那么我们可能会丢失结点的地址信息,从而失去我们已经保存的数据。
其中指针具体的指向修改,我们不用太在意顺序,只需要记住先考虑新节点的指向,后修改旧结点的指向即可,下面的代码中,我们将采用4321的顺序:
1.按位置插入
我们先进行通用插入的实现:
//按位置插 bool Insert_Pos(PDNode plist, int pos, Element val) { assert(plist != NULL); //判断插入位置是否合法 if (pos < 0 || pos > GetSize(plist)) { return false; } PDNode node = plist;//将结点指针定位至需要插入数据位置之前的结点 for (int i = 0; i < pos; i++) { node = node->next; } PDNode newnode = BuyNode();//申请新节点 newnode->data = val; //以下为插入步骤 newnode->next = node->next;//4 newnode->prev = node;//3 node->next->prev = newnode;//2 node->next = newnode;//1 return true; }
2.尾插
因为表头的前置指针指向尾结点,所以我们不用像单链表一样进行遍历后才能尾插。
//尾插 bool Push_Back(PDNode plist, Element val) { assert(plist != NULL); PDNode newnode = BuyNode(); newnode->data = val; //插入 newnode->next = plist;//4 newnode->prev = plist->prev;//3 plist->prev = newnode;//2 plist->prev->next = newnode;//1 return true; }
3.头插
直接调用按位置插入,插入位置为0
//头插 bool Push_Front(PDNode plist, Element val) { assert(plist != NULL); return Insert_Pos(plist, 0, val); }
5.查找
查找与普通链表的查找基本相同,但是在while循环中的结束条件不同,以结点指针是否指向表头来判断
//查找 返回结点地址 PDNode Find(PDNode plist, Element val) { assert(plist != NULL); PDNode node = plist->next; //遍历链表查找与val 相同的值 while (node != plist && node->data != val) { node = node->next; } if (plist == node) { return NULL; } return node; }
6.数据删除
双向循环链表的删除大致与单链表相同,但在两相隔结点的重新链接时需要连结两个指针,即被删除结点的前置结点的后继指针指向被删除结点的后继结点,而后继结点的前置指针指向前置结点
1.按位置删除
//按位置删 bool Erease_Pos(PDNode plist, int pos) { assert(plist != NULL); if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist)) { return false; } PDNode delnode = plist; for (int i = 0; i <= pos; i++) { delnode = delnode->next; } //重新连结 delnode->prev->next = delnode->next; delnode->next->prev = delnode->prev; free(delnode); delnode = NULL; return true; }
2.按值删除
这里调用了查找函数,找到val值所在的结点
//按值删 bool Erease_Val(PDNode plist, Element val) { assert(plist != NULL); PDNode delnode = Find(plist, val); if (delnode == NULL) { return false; } delnode->prev->next = delnode->next; delnode->next->prev = delnode->prev; free(delnode); delnode = NULL; return true; }
3.尾删
同样的,因为表头的前置指针指向尾结点,则可以减少遍历链表所消耗的资源。
//尾删 bool Pop_Back(PDNode plist) { assert(plist != NULL); if (IsEmpty(plist)) { return false; } PDNode delnode = plist->prev; delnode->prev->next = delnode->next; delnode->next->prev = delnode->prev; free(delnode); delnode = NULL; return true; }
4.头删
直接调用按位置删除,删除位置为0
//头删 bool Pop_Front(PDNode plist) { assert(plist != NULL); return Erease_Pos(plist, 0); }
7.清空与销毁
1.清空
这里我们使用比较简单的方法,一直头删即可,当然这里的尾删也可以使用,消耗资源相同。
//清空 void Clear(PDNode plist) { assert(plist != NULL); while (!IsEmpty(plist)) { Pop_Front(plist); } }
2.销毁
调用清空函数,并使链表达到未初始化的状态。
//销毁 void Destroy(PDNode plist) { Clear(plist); plist->next = plist->prev = NULL; }
8.双向循环链表源文件及整体函数实现
#include "dclist.h" //初始化链表 void InitList(PDNode plist) { assert(plist != NULL); plist->next = plist->prev = plist; } //购买结点 PDNode BuyNode() { PDNode node = (PDNode)malloc(sizeof(DNode)); if (node == NULL) { exit(1); } memset(node, 0, sizeof(*node)); return node; } //头插 bool Push_Front(PDNode plist, Element val) { assert(plist != NULL); return Insert_Pos(plist, 0, val); } //尾插 bool Push_Back(PDNode plist, Element val) { assert(plist != NULL); PDNode newnode = BuyNode(); newnode->data = val; newnode->prev = plist->prev; newnode->next = plist; plist->prev->next = newnode; plist->prev = newnode; return true; } //按位置插 bool Insert_Pos(PDNode plist, int pos, Element val) { assert(plist != NULL); if (pos < 0 || pos > GetSize(plist)) { return false; } PDNode node = plist; for (int i = 0; i < pos; i++) { node = node->next; } PDNode newnode = BuyNode(); newnode->data = val; newnode->next = node->next; newnode->prev = node; node->next->prev = newnode; node->next = newnode; return true; } //头删 bool Pop_Front(PDNode plist) { assert(plist != NULL); return Erease_Pos(plist, 0); } //尾删 bool Pop_Back(PDNode plist) { assert(plist != NULL); if (IsEmpty(plist)) { return false; } PDNode delnode = plist->prev; delnode->prev->next = delnode->next; delnode->next->prev = delnode->prev; free(delnode); delnode = NULL; return true; } //按位置删 bool Erease_Pos(PDNode plist, int pos) { assert(plist != NULL); if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist)) { return false; } PDNode delnode = plist; for (int i = 0; i <= pos; i++) { delnode = delnode->next; } delnode->prev->next = delnode->next; delnode->next->prev = delnode->prev; free(delnode); delnode = NULL; return true; } //按值删 bool Erease_Val(PDNode plist, Element val) { assert(plist != NULL); PDNode delnode = Find(plist, val); if (delnode == NULL) { return false; } delnode->prev->next = delnode->next; delnode->next->prev = delnode->prev; free(delnode); delnode = NULL; return true; } //查找 返回结点地址 PDNode Find(PDNode plist, Element val) { assert(plist != NULL); PDNode node = plist->next; while (node != plist && node->data != val) { node = node->next; } if (plist == node) { return NULL; } return node; } //判空 bool IsEmpty(PDNode plist) { assert(plist != NULL); return (plist->next == plist->prev && plist->next == plist); } //获取元素个数 int GetSize(PDNode plist) { assert(plist != NULL); PDNode node = plist->next; int count = 0; while (node != plist) { node = node->next; count++; } return count; } //打印链表 void Print(PDNode plist) { assert(plist != NULL); PDNode node = plist->next; while (node != plist) { printf("%d ", node->data); node = node->next; } printf("\n"); } //清空 void Clear(PDNode plist) { assert(plist != NULL); while (!IsEmpty(plist)) { Pop_Front(plist); } } //销毁 void Destroy(PDNode plist) { Clear(plist); plist->next = plist->prev = NULL; }
总结
以上为双向循环链表的实现和方法讲解,双向循环链表为比较常用的链表形式,学习并理解双向循环链表会方便以后的学习。
-
数据结构----C++ 判断一个带表头结点的双向循环链表L是否对称相等的算法
2021-02-02 23:29:59设计算法,判断带头结点的循环双向链表是否对称 算法思路: ⚫ 建立两个工作指针p和q,p从左向右扫描L,q从右向左扫描L,两者同时扫描⚫ 进入while循环判断,若p与q不相等且p的后继不等于q ⚫ 若对应数据结点的data... -
C语言实现双向循环链表
2021-05-22 14:24:24说明 相比Linux内核链表宿主结构可有多个链表结构的优点,本函数集侧重封装性和易用性,而灵活性和效率有所降低. 可基于该函数集方便地构造栈或队列集. 本函数集暂未考虑并发保护. 一 概念 链表是一种物理存储单元上非... -
【数据结构】(循环链表)判断循环双链表是否对称
2019-08-18 15:25:47=tail){ //这里因为不知道链表是奇数个还是偶数个所以两个条件都写上了 if(pre->data==tail->data){ pre=pre->next; tail=tail->prior; } } if(pre==tail||pre->next==tail){ //这里根据指针判断是否... -
数据结构系列2——双向链表和双向循环链表
2021-09-23 18:48:40双向循环链表,顾名思义就是在双向链表的基础上,将尾节点的“right”指针指向头结点,同时头结点的“left”指针指向尾节点,它和双向链表的不同是,其判断节点是否遍历完毕的条件不再是是否为空,而是是否回到了头... -
python实现·数据结构与算法之双向循环链表
2020-06-30 17:14:25双向循环链表定义 双向循环链表(Double Cycle Linked List)是双向链表的一种更复杂的变形,头结点的上一节点链接域指向尾结点,而尾结点的下一节点链接域指向头节点。 节点示意图 表元素域elem用来存放具体的... -
数据结构:循环双向链表以及用python实现循环双向链表
2021-04-26 17:25:39通过上文,了解相信大家已经简单了解了单链表的结构,本文主要介绍循环双向链表,简单说就是双向链表和循环链表的结合,为什么把它放在一起实现呢,因为总体而言,循环双向链表基本解决了各类链表的弊端,实用性较强... -
线性表——双向循环链表的C语言实现
2021-12-17 19:18:23双向循环链表的C语言实现 头文件 #include<stdio.h> #include<stdlib.h> //结果函数状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define ... -
带头结点的双向循环链表数据结构
2019-01-08 13:05:10用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回... -
如何用C++实现双向循环链表
2020-12-31 01:48:21双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表。各种链表的简单区别如下:单向链表:基本链表;单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代... -
双向循环链表详解及其基本功能的实现
2022-01-25 19:37:54在单链表详解中我们提到了链表的几种基本的结构,在这里要详细讲到的就是带头双向循环链表,其结构如下: 该链表拥有1个头节点,且每个节点都有一个前驱指针和一个后继指针,分别用来保存前一个节点的地址和后一个... -
【数据结构】判断循环双链表是否对称
2021-10-09 10:59:31判断循环双链表是否对称 二、解题思路 解题思路很简单,跟判断回文数的方法类似,只不过换成了链表。 首先需要写出循环双链表,第二,则判断是否对称 判断是否对称,定义两个指针,p1指针指向头指针的后继(头遍历... -
单链表、循环链表、双向循环链表总结
2019-11-23 18:56:31链表介绍 不带头结点的单向链表 带头结点的单向链表 循环链表 双向循环链表 -
双向循环链表的Java版本实现
2021-02-12 21:25:421、单项循环列表单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。和单链表相比,循环单链表的长处是从链尾到链头... -
数据结构——带头结点双向循环链表
2022-03-16 15:17:26带头结点双向循环链表基本操作(c语言版) -
判断循环双链表是否对称
2021-03-18 15:08:25题目:设计一个算法判断带头结点的循环双链表是否对称 分析: 简单分析,我们可以设置两个指针,pre和next,从头结点出发,进行比较,若pre与next所指值不同,则不对称,若pre和next指向了同一个节点 则该循环双... -
双向循环链表的合并
2021-05-23 08:11:38循环链表和双向链表的区别是是什么?最后一个结点指针指向不同 在建立一个...双向循环链表中如何交换两个结点,为什么我p , q交换 先用笨的办法,把p ,q分别摘下来,然后插回去就可以了 t=p->next;t->pre=p... -
java.实现双向循环链表LinkedList
2022-02-09 18:11:35//双向循环链表 可栈可队列 public class LinkedList implements List , Dequeue , Stack { private class Node {//结点定义参数 E data; Node pre; //直接前驱 Node next;//直接后继 public Node(){ this(null,... -
数据结构+带头结点双向循环链表+(C语言)
2021-11-27 19:46:35针对带头的双向循环链表的基本功能展开讲解: 目录 1.结构体定义 a. typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode; -
队列 -- 双向循环链表实现
2021-08-19 10:47:46队列--双向循环链表实现 通过对线性表的插入删除操作在异端完成 比如: 头插入对应的是尾删除 尾插入对应的是头删除 出数据的一端是队头,进数据的是队尾 栈: 先进后出 队列: 先进先出 */ // ... -
C语言双向循环链表
2021-08-07 20:03:39在C语言中,链表分为单向链表和双向链表,单向链表只能朝一个方向遍历,中间的一个节点只能由上一个节点推出,只能往前推,无法往后推,关于单向链表的介绍可以点击单向链表介绍。 这次介绍双向链表,既然叫双向就... -
双向循环链表的创建及基本操作
2020-10-05 16:38:15数据结构c语言双向循环链表 双向循环链表在定义上类似于循环单链表,就多了个前指针,以方便于向前查找。在双向链表中需要同时修改两个方向的指针,是单向链表指针的两倍。 完整代码如下: #include <stdio.h>... -
数据结构之双向链表和双向循环链表
2019-11-25 19:53:47文章目录一:双向链表(一):双向链表的结构(二):数据的构建(三):创建节点(四):创建链表(五):插入1:表头法插入2:表尾法插入3:指定位置插入(六):删除1:头删除 一:双向链表 (一):双向链表的... -
Java实现带头结点的双向循环链表
2019-10-18 16:45:58文章目录一、什么是双向循环链表?二、带头结点的双向循环链表的实现 一、什么是双向循环链表? 双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同,双向链表也有带头结点结构和不带头结点结构两种... -
数据结构手把手教学——双向循环链表
2019-12-28 13:44:37文章不空谈理论,完全采用手把手教学,并有综合示例练习题,看完这篇,你绝对能掌握数据结构双向循环链表。