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

小鱼儿 2023-02-27 15:53 4阅读 0赞

### 循环双链表-带头结点 ###

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

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int

# 2.循环双链表结点类型定义 #

typedef struct DNode {
        				//定义双链表结点类型
    	ElemType data;
    	struct DNode* prior, * next;	//前驱和后继指针
    }DNode, * DLinkList;

# 3.函数声明 #

/*函数声明*/
    bool InitDLinkList(DLinkList& L);				//1.初始化循环双链表
    bool Empty(DLinkList L);						//2.判空
    bool isTail(DLinkList L, DNode* p);				//3.判断表尾结点
    DNode* GetElem(DLinkList L, int i);				//4.按位查找
    bool InsertNextDNode(DNode* p, ElemType e);		//5.指定结点后插
    bool DeleteNextDNode(DNode* p);					//6.删除指定结点的后继结点
    DLinkList List_HeadInsert(DLinkList& L);		//7.头插法
    void PrintDLinkList(DLinkList L);				//8.遍历
    void DestoryList(DLinkList& L);					//9.销毁循环双链表

# 4.基本操作 #

## 4.1 初始化循环双链表 ##

//1.初始化循环双链表(带头结点)
    bool InitDLinkList(DLinkList& L) {
        
    	L = (DNode*)malloc(sizeof(DNode));		//创建头结点
    	if (L == NULL)
    		return false;    //内存不足，分配失败
    	L->prior = L;	//头结点的prior指向L
    	L->next = L;	//头结点的next指向L
    	return true;
    }

## 4.2 判空 ##

//2.判空（与循环单链表一致）
    bool Empty(DLinkList L) {
        
    	if (L->next == L)
    		return true;		//表为空
    	else
    		return false;		//表非空
    }

## 4.3 判断表尾结点 ##

//3.判断结点p是否为循环双链表的表尾结点（与循环单链表一致）
    bool isTail(DLinkList L, DNode* p) {
        
    	if (p->next == L)
    		return true;
    	else
    		return false;
    }

## 4.4 按位查找 ##

//4.查找操作-按位查找：返回第i个结点
    DNode* GetElem(DLinkList L, int i) {
        
    	if (i < 0)
    		return NULL;
    	int j = 0;
    	DNode* p = L;
    	while (p != NULL && j < i) {
        
    		p = p->next;
    		j++;
    	}
    	return p;		//也可能返回NULL，当输入i大于双链表长度时
    }

## 4.5 指定结点后插 ##

//5.插入操作-指定结点后插
    bool InsertNextDNode(DNode* p, ElemType e) {
        
    	if (p == NULL)		//非法参数
    		return false;
    	DNode* q = p->next;		//q为p原先的后继结点
    	DNode* s = (DNode*)malloc(sizeof(DNode));	//s为p新的后继结点
    	if (s == NULL)
    		return false;		//内存不足，分配失败
    	s->data = e;	//为新结点赋值
    	s->next = q;
    	/*此处与双链表有区别，不需要判断，因为在循环双链表中每个结点都有后继结点，
    因此不存在q为NULL的情况，故可以给q的前驱结点赋值，不会发生空指针的情况*/
    	q->prior = s;		
    	s->prior = p;
    	p->next = s;
    	return true;
    }

## 4.6 删除指定结点后继结点 ##

//6.删除操作-删除指定结点p的后继结点q
    bool DeleteNextDNode(DNode* p) {
        
    	if (p == NULL)
    		return false;	//非法参数：p不存在
    	DNode* q = p->next;
    	if (q == NULL)
    		return false;	//p没有后继结点
    	p->next = q->next;
    	q->next->prior = p;		//此处与上述插入操作类似，也不需要判断
    	free(q);
    	return true;
    }

## 4.7 创建循环双链表 ##

//7.创建循环双链表：头插法
    DLinkList List_HeadInsert(DLinkList& L) {
        
    	if (InitDLinkList(L))	//初始化循环双链表
    		printf("循环双链表初始化成功！\n");
    	else
    		printf("循环双链表初始化失败！\n");
    	if (Empty(L))
    		printf("当前表为空!\n");
    	else
    		printf("当前表非空!\n");
    	ElemType x;
    	int i = 1;		//用作记录插入第几个元素
    	printf("开始创建循环双链表！\n请输入%d个元素：", i);
    	scanf("%d", &x);
    	while (x != 0) {
        
    		if (InsertNextDNode(L, x)) 		//头插法本质是头结点的后插操作
    			printf("成功插入第%d个元素：%d\n", i, x);
    		else
    			printf("插入第%d个元素失败！\n", i);
    		printf("请输入%d个元素：", ++i);
    		scanf("%d", &x);
    	}
    	printf("循环双链表创建完成！\n");
    	return L;
    }

## 4.8 遍历 ##

//8.遍历循环双链表
    void PrintDLinkList(DLinkList L) {
        
    	DNode* p;
    	p = L->next;
    	printf("遍历循环双链表：\n");
    	while (p != L) {
        		//此处判断与普通双链表有区别
    		printf("%d\t", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }

## 4.9 销毁循环双链表 ##

//9.销毁操作
    void DestoryList(DLinkList& L) {
        
    	printf("开始销毁双链表！\n");
    	//循环释放各个数据结点--对头结点依次做删除操作
    	while (L->next != L)	//此处与普通双链表有区别
    		DeleteNextDNode(L);
    	free(L);	//释放头结点
    	L = NULL;	//头指针指向NULL
    }

## 4.10 main函数 ##

int main() {
        
    	DLinkList L;
    	int i;
    
    	/*以下操作只要涉及对循环双链表的改动，均遍历循环双链表*/
    
    	/*1、头插法建立循环双链表*/
    	L = List_HeadInsert(L);
    
    	/*2、判空*/
    	if (Empty(L))
    		printf("当前表为空!\n");
    	else
    		printf("当前表非空!\n");
    	PrintDLinkList(L);
    
    	/*3、按位查找*/
    	printf("请输入您要查找的位序i：");
    	scanf("%d", &i);
    	DNode* p = GetElem(L, i);
    	printf("位序为%d的值为：%d\n", i, p->data);
    
    	/*4.判断表尾结点*/
    	if (isTail(L, p))
    		printf("当前结点为表尾结点！\n");
    	else
    		printf("当前结点不是表尾结点！\n");
    
    	//*5、指定结点后插,以按位查找的p结点为例*/
    	ElemType e;
    	printf("请输入您要后插的值：");
    	scanf("%d", &e);
    	if (InsertNextDNode(p, e))
    		printf("p结点后插成功，元素值为：%d\n", e);
    	else
    		printf("p结点后插失败！\n");
    	PrintDLinkList(L);
    
    	/*6.再次判断表尾结点*/
    	if (isTail(L, p))
    		printf("当前结点为表尾结点！\n");
    	else
    		printf("当前结点不是表尾结点！\n");
    
    	/*7、删除指定结点的后继结点，此处删除p的后继结点*/
    	ElemType e1 = p->next->data;
    	if (DeleteNextDNode(p))
    		printf("此结点后继结点删除成功，值为：%d\n", e1);
    	else
    		printf("此结点后继结点删除失败！");
    	PrintDLinkList(L);
    	
    	/*8、销毁循环双链表*/
    	DestoryList(L);
    	if (L == NULL)
    		printf("循环双链表已销毁！\n");
    	else
    		printf("循环双链表销毁失败！\n");
    	return 0;
    }

# 5.小结 #

1.  **普通双链表和循环双链表的对比**  
    (1)不同点  
    除**初始化**、**判空**、**判断表尾结点**、**遍历结束条件**方面有微小的变化外，在**循环双链表的销毁操作**上也有微小变化，也是循环的结束条件发生了变化。另外，在循环双链表中的后插操作和指定结点的后继结点的删除操作不再需要判断插入结点或被删除结点是否是最后一个结点，因为所有结点都有后继结点。  
    (2)相同点  
    增删查以及创建操作没有改变。
2.  **说明**  
    上述代码主要是对循环双链表中与普通双链表有区别的操作进行了测试，其他基本操作与普通双链表基本一致。