YT

用户名：dotcpp0595443

访问量：245

签　名：

向着星辰，向着大海。

等　　级
排　　名	3858
经　　验	1749
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业

　　自我简介：

TA的其他文章

双向循环链表带图详解
浏览：46

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 选取其中最大的数字

A+B for Input-Output Practice (III) （C语言代码）

双向循环链表带图详解

　　作者: YT　　　　发表时间：2022-11-08 00:28:34 浏览：46　|　评论：1　

原题链接：数据结构-双向循环链表

初学者对于链表不是很熟悉，可以借助画图来理清思路，帮助解题

![红色为原来指针指向，黑色为我们需要进行的操作](/image_editor_upload/20221108/20221108122648_22476.png "红色为原来连接，黑色为我们需要进行的操作")

```cpp
#include<iostream>
using namespace std;

#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
typedef struct DuLNode   //双向链表以及其节点类型
{
	ElemType data;
	struct DuLNode *prior;
	struct DuLNode *next;	
}DuLNode ,*DuLinkList;

void ListCreate(DuLinkList &L)
{
	L=new DuLNode;
	L->prior = L;   //开始时指针前后都指向自身；
	L->next = L;
}

// 查询第i个元素
DuLinkList GetElemP(DuLinkList L, int i)
{
	// L为带头结点的单链表的头指针
	// 当第i个元素存在时，返回其地址
	DuLinkList p;
	p = L->next;    // 从首节点开始
	int j=1 ;   // 初始化，p指向第一个节点，j为计数器
	while(p!=NULL&&j<i)
	{
		p = p->next;
		++j;
	}
	if(p == L && j<i){
		return NULL ; // 如果p==L，因为是循环列表，p的下一个指针指向了头指针，还未找到i
	} else
	{
		return p;
	}
}

// 展示链表中所有的元素
Status ListShow(DuLinkList L)
{
	DuLinkList p;
	p=L->next;
	while(p!=L)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<"\n";
	return OK;
}

// 元素的插入
Status ListInsert(DuLinkList &L, int x, int y) 
{  // 在第x个里面插入元素y
	DuLinkList p,q;
	p=L;              // 注意这里的p指的是头节点
	q=new DuLNode;   // 一定要注意开辟新的空间
	q->data=y;
	/*
	for(int i=0;i<x;i++)  //另一种表示方式，不调用函数使用循环，在删除中同样适用
	{
		p=p->next;
	}
	*/
	p = GetElemP(L,x);  // 这个时候的P=L->next
	q->prior=p->prior;  // 可以画图更加清晰  对应图一中的1
	p->prior->next=q;  // 对应图一中的2
	q->next=p;         // 对应图一中的3
	p->prior=q;			// 对应图一中的4
	return OK;
}
// 删除第i个元素
Status ListDelet(DuLinkList &L, int i )
{
	DuLinkList p;
	p = GetElemP(L,i);
	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);           // 释放空间
	return OK;
}

int main()
{
	DuLinkList L;
	ListCreate(L);
	int x,i,y;
	while(cin>>x) 
	{
		switch (x) 
		{
			case 1:
				cin>>i;
				cin>>y;
				ListInsert(L,i,y);
				break;
			case 2:
				cin>>i;
				ListDelet(L,i);
				break;
			case 0:
				ListShow(L);
				break;
		}
	}
	return 0;
}
```
[========]
红色为原来指针指向，黑色为我们需要进行的操作
![](/image_editor_upload/20221108/20221108124048_68881.png)
```cpp
// 注意：这个插入与上面不同，这个当中 p 指的是第 x-1 个(p指向的是头节点)，所以 i=1；而在上面中 p 指的是第 x 个;
Status ListInsert(DuLinkList &L, int x, int y) 
{  // 在第x个里面插入元素y
	DuLinkList p,q;
	p=L;
	q=new DuLNode;
	q->data=y;
	for(int i=1;i<x;i++)
	{
		p=p->next;
	}
	q->next=p->next;		// 对应图二中 2
	p->next->prior=q;		// 对应图二中 1
	p->next=q;				// 对应图二中 4
	q->prior=p;				// 对应图二中 3
	return OK;
}
```

0.0分

2 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

王梦茹

好图！

2022-11-10 19:17:24

YT

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 选取其中最大的数字

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

单词个数统计（C++代码）

A+B for Input-Output Practice (III) （C语言代码）

点我有惊喜！你懂得！

双向循环链表带图详解

评论区

精彩推荐

C语言训练-自守数问题（C语言代码） long long

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

DNA （C语言描述，蓝桥杯）

printf基础练习2 （C语言代码）

1642题解

YT

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 选取其中最大的数字

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

单词个数统计 （C++代码）

A+B for Input-Output Practice (III) （C语言代码）

点我有惊喜！你懂得！

双向循环链表带图详解

评论区

精彩推荐

C语言训练-自守数问题 （C语言代码） long long

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

DNA （C语言描述，蓝桥杯）

printf基础练习2 （C语言代码）

1642题解

单词个数统计（C++代码）

　　评论区

C语言训练-自守数问题（C语言代码） long long

C二级辅导-进制转换（C语言代码）