2020-10-22 17:35:55

文章目录

前言
一、循环双链表的定义
二、循环双链表的结构
三、循环双链表的常用操作
结语
附录

前言

之前学习的双链表结构，可以实现从表中任一结点出发找到链表中的其他结点，但是该结构如果要从头结点开始查找尾结点，那么就需要通过遍历查找尾结点，这种情况下双链表的效率较低，为了解决这个缺点，将其改进为循环双链表，以此来提高查找效率。

在这里插入图片描述

一、循环双链表的定义

循环双链表是对双链表的改进，将尾结点与头结点建立连接，使得尾结点可以直接查找到头结点，头结点也能够直接查找到头结点，以此来提高查找的效率。

二、循环双链表的结构

结构图
在这里插入图片描述
代码描述

#define ElemType int
//循环双链表结点结构
typedef struct Node
{
	ElemType data;     //数据域
	struct Node *prio; //前驱结点指针域
	struct Node *next; //后继结点指针域
}Node, *PNode;

//双链表结点管理结构
typedef struct List
{
	PNode first; //指向首结点（首结点不存放数据）
	PNode last;  //指向尾结点
	int   size;  //记录有效结点数
}List;

三、循环双链表的常用操作

初始化循环双联链表

//初始化双链表
void InitDCList(List *list)
{
	//申请头结点空间
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	//将头结点连接入管理结点
	list->first = list->last = s;
	//设置前驱指针指向（指向头结点）
	list->first->prio = list->last;
	//设置后继结点指向（指向尾结点）
	list->last->next  = list->first;
	list->size = 0;
}

获取结点

//获取结点
Node* _buynode(ElemType x)
{
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;
	s->next = s->prio = NULL;
	return s;
}

尾插

void push_back(List *list, ElemType x)
{
	//获取结点
	Node *s = _buynode(x);
	//将插入结点与头结点连接
	s->next = list->last->next;
	s->next->prio = s;
	//将插入结点与上一尾结点连接
	s->prio = list->last;
	list->last->next = s;
	//修改双向链表管理结点的尾指针
	list->last = s;
	list->size++;
}

头插

//头插
void push_front(List *list, ElemType x)
{
	//获取插入结点
	Node *s = _buynode(x);
	//连接新插入结点和其下一个结点
	s->next = list->first->next;
	s->next->prio = s;
	//插入结点和头结点
	s->prio = list->first;
	list->first->next = s;
	//如果这个结点是第一个有效结点，需要更改管理结点尾指针的指向
	if(list->first == list->last)
		list->last = s;
	list->size++;
}

查看循环双链表数据

//查看循环双链表数据
void show_list(List *list)
{
	//指向第一个有效结点
	Node *p = list->first->next;
	//将所有有效结点输出
	while(p != list->first)
	{
		printf("%d-->",p->data);
		p = p->next;
	}
	printf("Nul.\n");
}

尾删

//尾删
void pop_back(List *list)
{   
	//如果没有有效结点，那么不进行删除
	if(list->size == 0)
		return;
	//设置管理结点的尾部指针指向
	Node *p = list->last;
	list->last = list->last->prio;
	//删除结点
	p->next->prio = p->prio;
	p->prio->next = p->next;
	free(p);
	list->size--;
}

头删

//头删
void pop_front(List *list)
{
	//如果没有有效结点不进行删除
	if(list->size == 0)
		return;
	//删除结点
	Node *p = list->first->next;
	p->next->prio = p->prio;
	p->prio->next = p->next;
	//如果只有一个有效结点，需要更改管理结点尾指针指向
	if(list->size == 1)
		list->last = list->first;
	list->size--;
}

按值插入(由小到大的顺序)

//按值插入(由小到大的顺序)
void insert_val(List *list, ElemType x)
{
	Node *p = list->first;//先指向头结点
	//查找要插入结点的位置
	while(p->next!=list->last && p->next->data < x)
		p = p->next;
	//如果插入的位置在最后，则进行尾插
	if(p->next==list->last && p->next->data<x)
	{
		push_back(list,x);
	}
	else //普通插入
	{
		Node *s = _buynode(x);
		s->next = p->next;
		s->next->prio = s;
		s->prio = p;
		p->next = s;
		list->size++;
	}
}

查找某一个值所在的位置

//查找某一个值所在的位置
Node* find(List *list, ElemType key)
{
	//从第一个有效结点位置开始查找
	Node *p = list->first->next;
	while(p != list->first && p->data != key)
		p = p->next;
	//如果没有找到返回空
	if(p == list->first)
		return NULL;
	return p;
}

获取有效结点个数

//获取有效结点个数
int  length(List *list)
{
	return list->size;
}

按值删除

//按值删除
void delete_val(List *list, ElemType key)
{
	//如果没有有效结点，则无需删除
	if(list->size == 0)
		return;
	//查找要删除结点所在的位置
	Node *p = find(list,key);
	//如果没有找到，无需删除
	if(p == NULL)
	{
		printf("要删除的数据不存在.\n");
		return;
	}
	//如果这个结点是尾结点，则进行尾删
	if(p == list->last)
	{
		pop_back(list);
	}
	else//否则进行普通删除
	{
		p->next->prio = p->prio;
		p->prio->next = p->next;
		free(p);
		list->size--;
	}
}

排序(按照由小到大排序)

//排序(按照由小到大排序)
void sort(List *list)
{
	//如果有效结点数小于等于1，则无需排序
	if(list->size==0 || list->size==1)
		return;
	//将原来的循环双链表，分解成两条
	Node *s = list->first->next;
	Node *q = s->next;
	list->last->next = NULL;
	list->last = s;
	list->last->next = list->first;
	list->first->prio = list->last;

	//从第二条链表中不断拿取元素按值插入(由小到大)到第一条循环链表中
	while(q != NULL)
	{
		//拿取元素
		s = q;
		q = q->next;

		//按值插入（由小到大）
		Node *p = list->first;//查找插入位置
		while(p->next!=list->last && p->next->data < s->data)
			p = p->next;
		
		if(p->next==list->last && p->next->data<s->data)
		{//尾插
			s->next = list->last->next;
			s->next->prio = s;
			s->prio = list->last;
			list->last->next = s;
			list->last = s;
		}
		else
		{//普通插入
			s->next = p->next;
			s->next->prio = s;
			s->prio = p;
			p->next = s;
		}
	}
}

逆置

//逆置
void resver(List *list)
{
	//如果有效结点数小于等于1，则无需排序
	if(list->size==0 || list->size==1)
		return;
	//将原来的循环双链表，分解成两条
	Node *p = list->first->next;
	Node *q = p->next;
	list->last->next = NULL;
	list->last = p;
	list->last->next = list->first;
	list->first->prio = list->last;

	//从第二条链表中不断拿取元素头插到第一条循环链表中
	while(q != NULL)
	{
		//获取元素
		p = q;
		q = q->next;
		//头插
		p->next = list->first->next;
		p->next->prio = p;
		p->prio = list->first;
		list->first->next = p;
	}
}

清空有效结点

//清空有效结点
void clear(List *list)
{
	//如果没有结点
	if(list->size == 0)
		return;
	//从第一个有效结点开始
	Node *p = list->first->next;
	while(p != list->first)
	{
		//清空释放有效结点（头删）
		p->next->prio = list->first;
		list->first->next = p->next;
		free(p);
		p = list->first->next;
	}
	list->last = list->first;
	list->size = 0;
}

销毁循环双链表

//销毁循环双链表
void destroy(List *list)
{
	//清空释放所有有效结点
	clear(list);
	free(list->first);
	//清空管理结点
	list->first = list->last = NULL;
}

结语

对循环双链表的介绍就到这里，希望这篇文章能够给予你一些帮助。

在这里插入图片描述

附录

以下提供循环双链表的测试代码

DCList.h

#ifndef __DCLIST_H__
#define __DCLIST_H__

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

#define ElemType int
//循环双链表结点结构
typedef struct Node
{
	ElemType data;     //数据域
	struct Node *prio; //前驱结点指针域
	struct Node *next; //后继结点指针域
}Node, *PNode;

//双链表结点管理结构
typedef struct List
{
	PNode first; //指向首结点（首结点不存放数据）
	PNode last;  //指向尾结点
	int   size;  //记录有效结点数
}List;

Node* _buynode(ElemType x);
void InitDCList(List *list);

void push_back(List *list, ElemType x);
void push_front(List *list, ElemType x);
void show_list(List *list);

void pop_back(List *list);
void pop_front(List *list);
void insert_val(List *list, ElemType x);
Node* find(List *list, ElemType key);
int  length(List *list);
void delete_val(List *list, ElemType key);
void sort(List *list);
void resver(List *list);
void clear(List *list);
void destroy(List *list);

#endif //__DCLIST_H__

DCList.cpp

#include"DCList.h"

//获取结点
Node* _buynode(ElemType x)
{
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	s->data = x;
	s->next = s->prio = NULL;
	return s;
}

//初始化双链表
void InitDCList(List *list)
{
	//申请头结点空间
	Node *s = (Node *)malloc(sizeof(Node));
	assert(s != NULL);
	//将头结点连接入管理结点
	list->first = list->last = s;
	//设置前驱指针指向（指向头结点）
	list->first->prio = list->last;
	//设置后继结点指向（指向尾结点）
	list->last->next  = list->first;
	list->size = 0;
}
//尾插
void push_back(List *list, ElemType x)
{
	//获取结点
	Node *s = _buynode(x);
	//将插入结点与头结点连接
	s->next = list->last->next;
	s->next->prio = s;
	//将插入结点与上一尾结点连接
	s->prio = list->last;
	list->last->next = s;
	//修改双向链表管理结点的尾指针
	list->last = s;
	list->size++;
}

//头插
void push_front(List *list, ElemType x)
{
	//获取插入结点
	Node *s = _buynode(x);
	//连接新插入结点和其下一个结点
	s->next = list->first->next;
	s->next->prio = s;
	//插入结点和头结点
	s->prio = list->first;
	list->first->next = s;
	//如果这个结点是第一个有效结点，需要更改管理结点尾指针的指向
	if(list->first == list->last)
		list->last = s;
	list->size++;
}
//查看循环双链表数据
void show_list(List *list)
{
	//指向第一个有效结点
	Node *p = list->first->next;
	//将所有有效结点输出
	while(p != list->first)
	{
		printf("%d-->",p->data);
		p = p->next;
	}
	printf("Nul.\n");
}
//尾删
void pop_back(List *list)
{   
	//如果没有有效结点，那么不进行删除
	if(list->size == 0)
		return;
	//设置管理结点的尾部指针指向
	Node *p = list->last;
	list->last = list->last->prio;
	//删除结点
	p->next->prio = p->prio;
	p->prio->next = p->next;
	free(p);
	list->size--;
}
//头删
void pop_front(List *list)
{
	//如果没有有效结点不进行删除
	if(list->size == 0)
		return;
	//删除结点
	Node *p = list->first->next;
	p->next->prio = p->prio;
	p->prio->next = p->next;
	//如果只有一个有效结点，需要更改管理结点尾指针指向
	if(list->size == 1)
		list->last = list->first;
	list->size--;
}
//按值插入(由小到大的顺序)
void insert_val(List *list, ElemType x)
{
	Node *p = list->first;//先指向头结点
	//查找要插入结点的位置
	while(p->next!=list->last && p->next->data < x)
		p = p->next;
	//如果插入的位置在最后，则进行尾插
	if(p->next==list->last && p->next->data<x)
	{
		push_back(list,x);
	}
	else //普通插入
	{
		Node *s = _buynode(x);
		s->next = p->next;
		s->next->prio = s;
		s->prio = p;
		p->next = s;
		list->size++;
	}
}

//查找某一个值所在的位置
Node* find(List *list, ElemType key)
{
	//从第一个有效结点位置开始查找
	Node *p = list->first->next;
	while(p != list->first && p->data != key)
		p = p->next;
	//如果没有找到返回空
	if(p == list->first)
		return NULL;
	return p;
}
//获取有效结点个数
int  length(List *list)
{
	return list->size;
}
//按值删除
void delete_val(List *list, ElemType key)
{
	//如果没有有效结点，则无需删除
	if(list->size == 0)
		return;
	//查找要删除结点所在的位置
	Node *p = find(list,key);
	//如果没有找到，无需删除
	if(p == NULL)
	{
		printf("要删除的数据不存在.\n");
		return;
	}
	//如果这个结点是尾结点，则进行尾删
	if(p == list->last)
	{
		pop_back(list);
	}
	else//否则进行普通删除
	{
		p->next->prio = p->prio;
		p->prio->next = p->next;
		free(p);
		list->size--;
	}
}

//排序(按照由小到大排序)
void sort(List *list)
{
	//如果有效结点数小于等于1，则无需排序
	if(list->size==0 || list->size==1)
		return;
	//将原来的循环双链表，分解成两条
	Node *s = list->first->next;
	Node *q = s->next;
	list->last->next = NULL;
	list->last = s;
	list->last->next = list->first;
	list->first->prio = list->last;

	//从第二条链表中不断拿取元素按值插入(由小到大)到第一条循环链表中
	while(q != NULL)
	{
		//拿取元素
		s = q;
		q = q->next;

		//按值插入（由小到大）
		Node *p = list->first;//查找插入位置
		while(p->next!=list->last && p->next->data < s->data)
			p = p->next;
		
		if(p->next==list->last && p->next->data<s->data)
		{//尾插
			s->next = list->last->next;
			s->next->prio = s;
			s->prio = list->last;
			list->last->next = s;
			list->last = s;
		}
		else
		{//普通插入
			s->next = p->next;
			s->next->prio = s;
			s->prio = p;
			p->next = s;
		}
	}
}
//逆置
void resver(List *list)
{
	//如果有效结点数小于等于1，则无需排序
	if(list->size==0 || list->size==1)
		return;
	//将原来的循环双链表，分解成两条
	Node *p = list->first->next;
	Node *q = p->next;
	list->last->next = NULL;
	list->last = p;
	list->last->next = list->first;
	list->first->prio = list->last;

	//从第二条链表中不断拿取元素头插到第一条循环链表中
	while(q != NULL)
	{
		//获取元素
		p = q;
		q = q->next;
		//头插
		p->next = list->first->next;
		p->next->prio = p;
		p->prio = list->first;
		list->first->next = p;
	}
}
//清空有效结点
void clear(List *list)
{
	//如果没有结点
	if(list->size == 0)
		return;
	//从第一个有效结点开始
	Node *p = list->first->next;
	while(p != list->first)
	{
		//清空释放有效结点（头删）
		p->next->prio = list->first;
		list->first->next = p->next;
		free(p);
		p = list->first->next;
	}
	list->last = list->first;
	list->size = 0;
}
//销毁循环双链表
void destroy(List *list)
{
	//清空释放所有有效结点
	clear(list);
	free(list->first);
	//清空管理结点
	list->first = list->last = NULL;
}

Main.cpp

#include"DCList.h"

void main()
{
	List mylist;
	InitDCList(&mylist);

	ElemType Item;
	Node *p = NULL;
	int select = 1;
	while(select)
	{
		printf("**************************************\n");
		printf("* [1] push_back      [2] push_front  *\n");
		printf("* [3] show_list      [4] pop_back    *\n");
		printf("* [5] pop_front      [6] insert_val  *\n");
		printf("* [7] find           [8] length      *\n");
		printf("* [9] delete_val     [10] sort       *\n");
		printf("* [11] resver        [12] clear      *\n");
		printf("* [13*] destroy      [0] quit_system *\n");
		printf("**************************************\n");
		printf("请选择:>");
		scanf("%d",&select);
		if(select == 0)
			break;
		switch(select)
		{
		case 1:
			printf("请输入要插入的数据(-1结束):>");
			while(scanf("%d",&Item),Item != -1)
			{
				push_back(&mylist,Item);
			}
			break;
		case 2:
			printf("请输入要插入的数据(-1结束):>");
			while(scanf("%d",&Item),Item != -1)
			{
				push_front(&mylist,Item);
			}
			break;
		case 3:
			show_list(&mylist);
			break;
		case 4:
			pop_back(&mylist);
			break;
		case 5:
			pop_front(&mylist);
			break;
		case 6:
			printf("请输入要插入的数据:>");
			scanf("%d",&Item);
			insert_val(&mylist,Item);
			break;
		case 7:
			printf("请输入要查找的数据:>");
			scanf("%d",&Item);
			p = find(&mylist,Item);
			if(p == NULL)
			{
				printf("要查找的数据在链表中不存在.\n");
			}
			break;
		case 8:
			printf("双向循环链表的长度为:> %d \n",length(&mylist));
			break;
		case 9:
			printf("请输入要删除的值:>");
			scanf("%d",&Item);
			delete_val(&mylist,Item);
			break;
		case 10:
			sort(&mylist);
			break;
		case 11:
			resver(&mylist);
			break;
		case 12:
			clear(&mylist);
			break;
		//case 13:
		//	destroy(&mylist);
		//	break;
		default:
			printf("输入的命令错误,请重新输入.\n");
			break;
		}
	}
	destroy(&mylist);
}

数据结构

更多相关内容

数据结构——“双向循环链表“ 易懂刨析双向循环链表（图解+代码）

千次阅读 2022-04-27 12:13:05

循环链表单向循环链表双向循环链表1. 双向循环链表——插入2. 双向循环链表——删除单向循环链表 关于两个循环链表合并为一个循环链表 双向循环链表 在单链表L中，查找ai的后继Next(L，...先定义双向链表中的结点:

单向循环链表

循环链表和单链表的区别

表中最后结点的指针不是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;
}

在这里插入图片描述

-----------------------------------------很棒学习完了数据结构的双向循环链表--------------------------------------------------

在这里插入图片描述

--------------------------------------------------------[下期预告：线性表的应用举例]------------------------------------------------------

收起

展开全文

c语言算法数据结构

【数据结构】循环链表和双向链表
2020-09-14 11:24:42
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录前言 ...一、循环链表的定义 1、定义将单链表中终端结点的指针端由空指针改为指向头指针，就使整个单链表形..
文章目录

一、循环链表的定义

二、循环链表的改进

三、双向链表的定义

四、双向循环链表

五、双向链表的插入和删除操作

1.插入操作

2.删除操作

前言

对于单链表，由于每个结点只存储了向后的指针，到了为标志就停止了向后链的操作。这样，当我们需要找到某个结点的前驱就没办法了。如何从链表中的任一结点出发，访问到链表的全部结点？循环链表就是解决这个麻烦的重要方法。

一、循环链表的定义

1、定义

将单链表中终端结点的指针端由空指针改为指向头指针，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

为了使空链表与非空链表处理一致，通常可以设一个头结点，当然不是所有的循环链表一定要头结点。

2.特点：

循环链表和单链表的主要差异在于循环的判断条件上，单链表是判断p->next是否为空，而循环链表是p->next是否等于头结点。

二、循环链表的改进

在单链表中，有头结点时，访问第一个结点的时间是O(1)，但要访问最后一个元素时，需要O(n)时间。

如何改进能使由链表指针访问到最后一个结点用O(1)时间呢？

方法：对于上述的循环链表进行改进，不用头指针，而使用指向终端结点的尾指针来表示循环链表。

上图循环链表，查找终端结点为O(1)，而开始结点为rear->next->next，时间复杂度也是O(1)。

应用：将两个循环链表合并成一个表。

三、双向链表的定义

循环链表为遍历及查找尾结点带来了遍历，但是查找某个结点的直接前驱，与单链表一样，都要从头结点（或尾结点）开始，遍历整个链表，时间复杂度为O(n)。双向链表解决了这个问题，但需要付出一定的空间代价。

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以双向链表结点都有两个指针域，一个指向直接前驱，一个指向直接后继。

双向链表存储结构设计：
```
typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;/*直接前驱指针*/
    struct DulNode *next；/*直接后继指针*/
}DulNode,*DulLinkList;
```
四、双向循环链表

既然单链表有循环结构-单向循环链表，那么双向链表也可以循环——双向循环链表。

带头结点的双向循环链表的空链表：

非空的带头结点的双向循环链表：

对于双向链表，链中的某一个结点p,它的前驱的后继，后继的前驱都是自己，

即：p->prior->next=p=p->next->prior

五、双向链表的插入和删除操作

1.插入操作

2.删除操作
收起
展开全文

【线性表】链表：循环单链表、双链表、循环双链表的基本特性

千次阅读 2020-06-06 14:09:57

链表不仅作为链式存储的一种实现方式，还表达了计算机不连续（离散）的存储思想。

链表不仅作为链式存储的一种实现方式，还表达了计算机不连续（离散）的存储思想。在初学阶段，链表的实现类型有单链表（带/不带头结点）、循环单链表、双链表、循环双链表四种。

上文已经讲解了单链表，接下来将讲解其他三类。

Table of Contents

循环单链表

双链表

循环双链表

循环单链表

定义：

将单链表中终端结点的指针端由 NULL 改为 指向头结点 ，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

两种情形：

为使空链表与非空链表处理一致，通常设置一个头结点。但并非必须设置头结点。

循环单链表特征：

对于单链表而言，最后一个结点指向NULL；把最后一个结点的不指向NULL而指向头，就是循环单链表；
在单循环链表上的操作基本上与非循环链表相同。循环链表和单链表的主要差异就在于循环的条件判断上，原来是 p->next == NULL，现在是 p->next != 头结点，则循环未结束。
单循环链表可以从表中任意结点开始遍历整个链表，不仅如此，有时对链表常做的操作是在表尾、表头进行。如果用头指针表示循环链表，则需O(n) 时间找到最后一个结点。若改用尾指针表示循环链表，此时查找开始结点和终端结点都很方便了。查找终端结点时间是O(1)，而开始结点，其实就是 rear->next->next ，其时间复杂也为O(1)。

第一个循环单链表


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

typedef struct node
{
	int data;
	struct node* next;
}Node; //struct node 完全等于 Node（结构体变量）
typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针）

int main()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	assert(head != NULL);  //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用）
	LinkList NodeAa = (LinkList)malloc(sizeof(Node));
	assert(NodeAa != NULL);
	LinkList NodeBb = (LinkList)malloc(sizeof(Node));
	assert(NodeBb != NULL);
	LinkList NodeCc = (LinkList)malloc(sizeof(Node));
	assert(NodeCc != NULL);

	head->data = NULL; //头结点，不保存数据
	head->next = NodeAa;
	NodeAa->data = 202;
	NodeAa->next = NodeBb;
	NodeBb->data = 303;
	NodeBb->next = NodeCc;
	NodeCc->data = 404;
	NodeCc->next = head;  //单链表中：NodeCc->next = NULL;

	LinkList p = head->next; //把链表头结点的下一个节点，交给指针p，去遍历
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	return 0;
}

双链表

定义：

双向链表也叫双链表，它的每个数据结点中都有两个指针（保存两个节点的地址），分别指向直接后继和直接前驱。

双链表的代码定义：

typedef struct node
{
	int data;
	struct node* pre; //前驱
	struct node* next; //后继
}Node;

特性：

从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
循环链表的最后一个结点指向头结点，循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
双向链表使单链表中扩展出来的结构，因此有一部分操作与单链表是相同的，如求长度函数、查找元素位置、打印函数、销毁函数等，这些函数操作都只要涉及一个方向的指针即可。

第一个双链表

第一个双链表
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

typedef struct node
{
	int data;
	struct node* pre;
	struct node* next;
}Node; //struct node 完全等于 Node（结构体变量）
typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针）

int main()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	assert(head != NULL);  //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用）
	LinkList NodeAa = (LinkList)malloc(sizeof(Node));
	assert(NodeAa != NULL);
	LinkList NodeBb = (LinkList)malloc(sizeof(Node));
	assert(NodeBb != NULL);
	LinkList NodeCc = (LinkList)malloc(sizeof(Node));
	assert(NodeCc != NULL);

	head->data = 101;
	head->pre = NULL;
	head->next = NodeAa;

	NodeAa->data = 202;
	NodeAa->pre = head;
	NodeAa->next = NodeBb;

	NodeBb->data = 303;
	NodeBb->pre = NodeAa;
	NodeBb->next = NodeCc;

	NodeCc->data = 404;
	NodeCc->pre = NodeBb;
	NodeCc->next = NULL;  //单链表中：NodeCc->next = NULL;

	LinkList p = head; //把链表头结点的下一个交给指针p，去遍历
	printf("顺序遍历：");
	while (p != NULL)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	printf("\n逆序遍历：");
	LinkList tail = NodeCc;
	p = tail;
	while (p != NULL)
	{
		printf("%d  ", p->data);
		p = p->pre;
	}

	return 0;
}

循环双链表

定义：

双向链表也叫双链表，它的每个数据结点中都有两个指针（保存两个节点的地址），分别指向直接后继和直接前驱。头指针的前驱指向最后一个节点，最后一个节点的后继指向头指针。

双链表的代码定义：

typedef struct node
{
	int data;
	struct node* pre; //前驱
	struct node* next; //后继
}Node;

特性：

从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
循环链表的最后一个结点指向头结点，循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
双向链表使单链表中扩展出来的结构，因此有一部分操作与单链表是相同的，如求长度函数、查找元素位置、打印函数、销毁函数等，这些函数操作都只要涉及一个方向的指针即可。

两种情形：

第一个循环双链表

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

typedef struct node
{
	int data;
	struct node* pre;
	struct node* next;
}Node; //struct node 完全等于 Node（结构体变量）
typedef Node* LinkList; //struct node * 完全等于 LinkList（结构体指针）

int main()
{
	LinkList head = (LinkList)malloc(sizeof(Node));
	assert(head != NULL);  //检查malloc之后是不是空间不够，返回了空指针NULL（WarningC6011：取消对NULL指针的引用）
	LinkList NodeAa = (LinkList)malloc(sizeof(Node));
	assert(NodeAa != NULL);
	LinkList NodeBb = (LinkList)malloc(sizeof(Node));
	assert(NodeBb != NULL);
	LinkList NodeCc = (LinkList)malloc(sizeof(Node));
	assert(NodeCc != NULL);

	head->data = NULL; //头结点，不保存数据
	head->pre = NodeCc;
	head->next = NodeAa;

	NodeAa->data = 202;
	NodeAa->pre = head;
	NodeAa->next = NodeBb;

	NodeBb->data = 303;
	NodeBb->pre = NodeAa;
	NodeBb->next = NodeCc;

	NodeCc->data = 404;
	NodeCc->pre = NodeBb;
	NodeCc->next = head;  //单链表中：NodeCc->next = NULL;

	LinkList p = head->next; //把链表头结点的下一个交给指针p，去遍历
	printf("顺序遍历：");
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->next;
	}

	printf("\n逆序遍历：");
	p = p->pre;
	while (p != head)
	{
		printf("%d  ", p->data);
		p = p->pre;
	}

	return 0;
}

收起

展开全文

数据结构链表循环单链表双链表

java实现双向循环链表（循环双链表）
千次阅读 2021-04-20 14:16:27

若是不清楚链表的结构，该篇文章不适合观看，这里只做文字说明，没有链表结构的图示

收起

链表数据结构循环链表
王道数据结构——双链表、循环双链表实现
2022-05-02 10:54:40

王道考研双链表、循环双链表

收起

数据结构 c++
深入解析C++的循环链表与双向链表设计的API实现
2021-01-01 16:04:23

循环链表的定义：将单链表中最后一个数据元素的next指针指向第一个元素 循环链表拥有单链表的所有操作创建链表销毁链表获取链表长度清空链表获取第pos个元素操作插入元素到位置pos 删除位置pos处的...

收起
数据结构系列2——双向链表和双向循环链表
2021-09-23 18:48:40

双向循环链表，顾名思义就是在双向链表的基础上，将尾节点的“right”指针指向头结点，同时头结点的“left”指针指向尾节点，它和双向链表的不同是，其判断节点是否遍历完毕的条件不再是是否为空，而是是否回到了头...

收起

数据结构 c语言
循环双链表的基本运算算法（增删改查）
2021-10-08 17:49:04

目的：领会循环双链表存储结构和掌握循环双链表中的各种基本运算算法。如果双链表的操作会了，单链表那是手到擒来，很简单。下面用一个实验来实现，该实现完成了以下功能： 1、初始化循环双链表h。 2、依次采用...

收起

算法数据结构
循环双链表 CDList.h
2021-12-17 23:48:12

在Linux内核源码list.h基础上，修改成应用层使用的头文件实现了循环双链表的的各功能函数和宏定义，包括但不限于链表的创建、插入、删除、遍历。

收起
单循环链表和双向循环链表
2022-03-27 22:00:41

循环链表就是普通的单链表，最后一个元素存的地址本来是ＮＵＬＬ，现在改成头结点的地址，从而形成循环． #include <stdio.h> #include <stdlib.h> #define MAX(X,Y) (X>Y?X:Y) #include <math....

收起

数据结构算法
双链表与循环链表和静态链表
千次阅读 2022-04-22 16:25:28

2，循环双链表 相比于浦东的双链表，循环双链表的头结点的prior指向表尾结点，表尾结点的next指向头结点。 //初始化双链表 bool InitDLinkList(DLinkList& L) { L = (DLinkList)malloc(sizeof(DNode)); if (L == ...

收起

c++ 数据结构
双向循环链表的定义以及基本操作超详细！
千次阅读 2020-06-28 16:40:26

struct node//结点结构体定义 { struct node* prior;//前指针指向前一个节点 struct node* next;//后指针指向后一个节点 int data; }; typedef struct node node;//为"struct node"起别名node 指结点 typedef ...

收起

数据结构
循环双链表的简单实现（C语言）
千次阅读 2022-03-25 21:10:23

循环双链表的C语言版简单实现，及简单讲解

收起

c语言数据结构开发语言
数据结构之带头结点的循环双向链表详细图片+文字讲解
2021-08-08 21:05:09

文章目录双向循环链表前言文件的创建双向链表结构的定义创建返回链表的头结点值传递时：地址传递：双向链表的销毁双向链表的打印开辟一个新结点双向链表的尾插双向链表的头插双向链表的尾删双向链表的头删双向链表...

收起

数据结构 C语言
循环双链表的插入删除操作--（作业）
千次阅读 2022-03-23 15:44:09

#include<iostream> using namespace std; //先定义双链表 typedef struct DNode { int data;...//先初始化循环双链表 void inisDoublelist(DoubleLIst *L) { *L = (DNode *)malloc(sizeof(.

收起

c++
【数据结构】判断循环双链表是否对称
2021-10-09 10:59:31

判断循环双链表是否对称二、解题思路解题思路很简单，跟判断回文数的方法类似，只不过换成了链表。首先需要写出循环双链表，第二，则判断是否对称判断是否对称，定义两个指针，p1指针指向头指针的后继(头遍历...

收起

数据结构算法
【数据结构算法】③、双向链表和双向循环链表的实现、双向链表的创建-遍历-插入-删除-删除指定元素-查询...
千次阅读 2022-03-22 17:43:08

【数据结构算法】③、双向链表和双向循环链表的实现、双向链表的创建-遍历-插入-删除-删除指定元素-查询指定元素、双向循环链表的创建-遍历-插入删除

收起

数据结构算法数据结构与算法
数据结构——循环链表与双链表
2022-02-10 17:28:04

循环链表 概念：表中最后一个节点的指针域指向头结点，整个链表形成一个环。循环单链表与双向循环链表的操作（初始化、插入、删除、判断是否为空等）： //带头结点的循环单链表 typedef struct LNode{ ElemType ...

收起

数据结构 list
【Python】数据结构——线性表（顺序表、单链表、循环单链表、双链表、循环双链表）
千次阅读 2022-04-16 19:27:02

线性表线性表定义线性表类型线性表特性线性表用处顺序表顺序表定义顺序表的操作链表链表的定义链表与顺序表的区别链表的构成链表的类型单链表的操作循环单链表的操作双向链表的操作 循环双链表的操作...

收起

python 数据结构
链表 - 双链表/循环链表/静态链表
2022-03-09 15:39:10

双链表/循环链表/静态链表双链表初始化插入删除双链表的遍历循环链表插入删除静态链表定义静态链表基本操作 双链表 单链表无法逆向检索，有时候不太方便；使用双链表，可进可退，存储密度比单链表低一些，因为一个...

收起

数据结构 c++
链表——循环单链表，循环双链表及静态链表
2021-04-18 14:44:40

文章目录循环链表循环单链表循环双链表静态链表说明循环链表循环链表一般包括循环单链表和循环双链表，如下图所示：循环单链表循环单链表与单链表的区别在于，表中最后一个结点的指针不是NULL，而改为...

收起
Python双向循环链表实现方法分析
2020-09-20 05:10:21

主要介绍了Python双向循环链表,结合实例形式分析了Python双向链表的定义、遍历、添加、删除、搜索等相关操作技巧,需要的朋友可以参考下

收起
【数据结构】-循环链表(双链表）
2020-07-21 16:50:02

循环双链表结点类型定义3.函数声明4.基本操作4.1 初始化循环双链表4.2 判空4.3 判断表尾结点4.4 按位查找4.5 指定结点后插4.6 删除指定结点后继结点4.7 创建循环双链表4.8 遍历4.9 销毁循环双链表4.10 main函数5.小...

收起

数据结构
【数据结构】循环链表定义及基本操作
2022-01-10 22:14:33

//循环链表定义及各类操作 #include<stdio.h> #include<string.h> #include<stdlib.h> #include<stdbool.h> typedef int Elemtype; //定义循环单链表节点类型 typedef struct CLinkList { ...

收起

数据结构
C语言双向循环链表
2021-08-07 20:03:39

这次介绍双向链表，既然叫双向就说明可以往两个方向进行遍历，可以利用中间的一个节点推出下一个节点和上一个节点，所以在定义一个双向链表节点的时候，除了要保存数据和下一个节点的地址，还得保存上一个节点的地址...

收起

数据结构算法
单链表结构实现和循环链表及双向链表的定义
2019-06-06 16:42:40

循环链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此从表中任一结点出发均可找到表中其他结点。 循环链表的操作和单链表基本一致，差别仅在于算法中的...

收起
（带头结点）循环双链表的创建于与输出
2022-01-26 12:06:02

void initdl(dulinklist &L)//循环双链表初始化函数（带头结点） { L=new dulnode; L->prior=L; L->next=L; } void creatdl(dulinklist &L,int n)//循环双链表创建函数 { dulnode *r,*s; r=L; int e; for(int i=1;i...

收起

c++
【C语言数据结构】双向循环链表
2022-03-06 22:05:00

目录前言一、双向循环链表 循环结构 1.双向循环链表头文件及函数声明 ...8.双向循环链表源文件及整体函数实现 ...这次我们将学习双向循环链表，首先了解双向链表和循环链表的定义和讲解。双向链表也叫双链...

收起

c语言数据结构
建立循环双链表（尾插法）
千次阅读 2020-12-12 22:32:53

该方法是将节点插入在当前循环双链表的表尾上，为此增加一个尾指针r ,并始终指向当前链表的尾节点，最后让r->next 指向头结点。头结点的prior 指向尾节点。注意：这里头结点，尾节点要相互指向才是循环双链表 ...

收起

数据结构单链表

文章目录

前言

一、循环双链表的定义

二、循环双链表的结构

三、循环双链表的常用操作

结语

附录

数据结构——“双向循环链表“ 易懂刨析双向循环链表（图解+代码）

循环链表

单向循环链表

循环链表和单链表的区别

循环链表的特点

双向循环链表——概念

1. 双向循环链表——插入

2. 双向循环链表——删除

双向链表的插入创建

双向链表——查找

双向链表——插入

双向链表——删除

【数据结构】循环链表和双向链表

文章目录

前言

一、循环链表的定义

二、循环链表的改进

三、双向链表的定义

四、双向循环链表

五、双向链表的插入和删除操作

1.插入操作

2.删除操作

【线性表】链表：循环单链表、双链表、循环双链表的基本特性

循环单链表

双链表

循环双链表

java实现双向循环链表（循环双链表）

王道数据结构——双链表、循环双链表实现

深入解析C++的循环链表与双向链表设计的API实现

数据结构系列2——双向链表和双向循环链表

循环双链表的基本运算算法（增删改查）

循环双链表 CDList.h

单循环链表和双向循环链表

双链表与循环链表和静态链表

双向循环链表的定义以及基本操作 超详细！

循环双链表的简单实现（C语言）

数据结构之带头结点的循环双向链表详细图片+文字讲解

循环双链表的插入删除操作--（作业）

【数据结构】判断循环双链表是否对称

【数据结构算法】③、双向链表和双向循环链表的实现、双向链表的创建-遍历-插入-删除-删除指定元素-查询...

数据结构——循环链表与双链表

【Python】数据结构——线性表（顺序表、单链表、循环单链表、双链表、循环双链表）

链表 - 双链表/循环链表/静态链表

链表——循环单链表，循环双链表及静态链表

Python双向循环链表实现方法分析

【数据结构】-循环链表(双链表）

【数据结构】循环链表定义及基本操作

C语言双向循环链表

单链表结构实现和循环链表及双向链表的定义

（带头结点）循环双链表的创建于与输出

【C语言数据结构】双向循环链表

建立循环双链表（尾插法）

循环双链表定义

双向循环链表的定义以及基本操作超详细！