循环双链表的基本操作C语言详解

忘是亡心i 2023-05-28 14:15 21阅读 0赞

**1. 尾指针：不是尾结点的指针，是指向尾结点的指针  
2. 头指针：不是头结点的指针，是指向头结点的指针，无论链表是否为空，头指针均不为空。  
3. 头结点：放在第一个结点之前的结点（“零结点”），数据域可以不存放东西，也可以存放链表信息（如链表长度）。**

**循环链表的存储结构**

typedef struct DulNode											//双循环链表的存储结构
    { 
    	int data;													//数据域
    	struct DulNode* prior;										//前驱指针
    	struct DulNode* next;										//后继指针
    }DulNode, * DuLinkList;

**数据结构图示**  
百度搜到的图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]

## 基本操作 ##

***1. int InitDuLinkedList(DuLinkList L); //初始化***\*

int InitDuLinkedList(DuLinkList* L)									//初始化,形参L是二级指针
    { 
    	*L = (DulNode*)malloc(sizeof(DulNode));							//头结点申请地址
    	if (*L == NULL)
    	{ 
    		printf("申请空间失败\n");
    		exit(0);
    	}
    	(*L)->data = -999;								//随便存点数据 
    	head = *L;										//头指针指向头结点
    	tail = *L;										//尾指针指向尾结点，目前只有一个结点，它既是头结点，也是尾结点
    	(*L)->prior = tail;								//头结点前驱初指向尾结点
    
    	(*L)->next = (*L);								//(*L)所指结点初始化时，既是头结点，也是尾结点。所以尾结点(**L)的后继指针，指向头结点
    	return 1;
    }

***2. DuLinkList CreatDuLinkList(DuLinkList* L); //创建双循环链表**\*

DuLinkList CreatDuLinkList(DuLinkList* L)						//尾插法创建双循环向链表，形参L是二级指针
    { 
    	int x;														//新插入的结点值
    	printf("输入需要插入的元素值\n");
    	scanf("%d", &x);
    
    	while (x != 9999)											//输入9999时结束插入
    	{ 
    		DuLinkList s = (DulNode*)malloc(sizeof(DulNode));				 //创建新结点
    		if (s == NULL)
    		{ 
    			printf("动态申请内存失败\n");
    			exit(0);
    		}
    		s->data = x;												//将值存入新结点
    
    		s->next = tail->next;									 //关键步骤
    		tail->next->prior = s;
    		tail->next = s;
    		s->prior = tail;
    
    		tail = s;                                              //尾指针指向新的尾结点,
    		printf("插入成功\n");
    		printf("输入需要插入的元素值(输入9999结束插入)\n");
    		scanf("%d", &x);
    	}
    	return *L;                                              //返回单链表地址
    }

***3. int DuLinkListInsert(DuLinkList* L, int i, int e); //位置i插入元素e**

int DuLinkListInsert(DuLinkList* L, int i, int e)				//第i个位置插入指定元素e
    { 
    	int j = 1;
    	DuLinkList p, s;
    	p = *L;
    	while (p && j < i)											//寻找第i-1个结点
    	{ 
    		p = p->next;
    		j++;
    	}
    	if (!p || j > i)
    		return 0;											//插入位置非法
    
    	s = (DulNode*)malloc(sizeof(DulNode));                    //动态分配内存
    	if (s == NULL)
    	{ 
    		printf("动态申请内存失败\n");
    		exit(0);
    	}
    	s->data = e;
    
    	s->prior = p;											//双链表插入操作的四个关键步骤
    	s->next = p->next;
    	p->next->prior = s;
    	p->next = s;
    
    	if (p == tail)                                          //若插入位置为末尾，插入后，修改尾指针指向新尾结点
    		tail = s;
    	return 1;
    }

*4. int DuLinkListDelete(DuLinkList L, int i, int e); //删除位置i的元素，用e返回其值*\*\*

int DuLinkListDelete(DuLinkList* L, int i, int* e)                      //删除位序为i的结点，并用e返回其元素值
    { 
    	DuLinkList p = *L;											//p最终指向被删除结点
    	int j = 1;													//从第一个结点开始找
    	while (p->next && j <= i)								 //遍历寻找第i个结点
    	{ 
    		p = p->next;
    		j++;
    	}
    
    	if (!(p->next))										//若p->next=null,此时链表长度可能小于i
    		return 0;
    	if (p == tail)										//如果被删除的是尾结点，修改尾指针指向新的尾结点
    		tail = p->prior;
    	*e = p->data;										//返回值
    
    	p->prior->next = p->next;                                //关键两步
    	p->next->prior = p->prior;
    	free(p);										  //释放内存
    
    	return *e;
    }

***5. DulNode* DuLinkPriorElem(DuLinkList L, int cur\_e); //求第一个值为cur\_e的前驱**

DulNode* DuLinkPriorElem(DuLinkList L, int cur_e)					 //求前驱操作
    { 
    	DuLinkList p = L->next;                         //p指向第一个结点，不是头结点
    	while (p != head)                              //遍历整个链表寻找值为cur_e的结点,当p==head时遍历了一周
    	{ 
    		if (p->data == cur_e)
    			break;
    		p = p->next;
    	}
    	if (p == head)                                   //循环一周没找到
    		return NULL;
    	else return p->prior;
    }

***6. DulNode* DuLinkNextElem(DuLinkList L, int cur\_e); //求第一个值为cur\_e的后继**\*

DulNode* DuLinkNextElem(DuLinkList L, int cur_e)			//求后继操作
    { 
    	DuLinkList p = L->next;                         //p指向第一个结点，不是头结点
    	while (p != head)                              //遍历整个链表寻找值为cur_e的结点,当p==head时遍历了一周
    	{ 
    		if (p->data == cur_e)
    			break;
    		p = p->next;
    	}
    	if (p == head)                                   //循环一周没找到
    		return NULL;
    	else return p->next;
    }

***7. DulNode* GetElem(DuLinkList L, int i); //求位序为i的元素值**\*

DulNode* GetElem(DuLinkList L, int i)
    { 
    	int j = 1;									//计数，初始化值为1
    	DulNode* p = L->next;						//p 指向第一个结点，不是头结点
    	if (i == 0)
    		return L;								//返回头结点
    	if (i < 1)
    		return NULL;						 //位置i不合法
    	while (p && j < i && p != head)					//从第一个结点开始找,p==head时，寻找了一周
    	{ 
    		p = p->next;
    		j++;
    	}
    	if (p == head)								//链表循环了一周，i大于循环双链表长度，越界
    		return NULL;
    	return p;								 //返回第i个结点的指针，如果i大于表长，p=NULL
    }

***8. int DuLinkListTraverse(DuLinkList L); //遍历输出***

int DuLinkListTraverse(DuLinkList L)						 //遍历访问整个表L
    { 
    	DulNode* p;
    	for (p = L->next; p != NULL; p = p->next)
    	{ 
    		printf("%-5d", p->data);
    		if (p == tail)                                    //遍历到最后一个元素（tail指向尾结点）
    			break;
    	}
    	return 0;
    }

## 全部代码如下, 编译环境vc6.0: ##

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct DulNode											//双循环链表的存储结构
    { 
    	int data;													//数据域
    	struct DulNode* prior;										//前驱指针
    	struct DulNode* next;										//后继指针
    }DulNode, * DuLinkList;
    
    struct DulNode* head = NULL;										//头指针,指向头结点
    struct DulNode* tail = NULL;										//尾指针，指向尾结点
    
    int InitDuLinkedList(DuLinkList* L);                             //初始化
    
    DuLinkList CreatDuLinkList(DuLinkList* L);						//创建
    
    int DuLinkListInsert(DuLinkList* L, int i, int e);					//位置i插入元素e
    
    int DuLinkListDelete(DuLinkList* L, int i, int* e);				//删除位置i的元素，用e返回其值
    
    DulNode* DuLinkPriorElem(DuLinkList L, int cur_e);					//求第一个值为cur_e的前驱
    
    DulNode* DuLinkNextElem(DuLinkList L, int cur_e);					//求第一个值为cur_e的后继
    	
    DulNode* GetElem(DuLinkList L, int i);						//求位序为i的元素值
    
    int DuLinkListTraverse(DuLinkList L);							//遍历输出
    
    
    int main()
    { 
    	int i, e;                                         //i存放元素位序，e存放元素值
    	DuLinkList L, DulNode;
    	InitDuLinkedList(&L);                            //初始化
    	CreatDuLinkList(&L);
    
    	printf("\n输入插入的位置i和元素值e\n");
    	scanf("%d%d", &i, &e);
    	if (DuLinkListInsert(&L, i, e))
    		printf("插入成功\n");
    	else printf("插入位置不合法\n\n");
    	printf("\n\n遍历结果\n");
    	DuLinkListTraverse(L);
    
    	printf("\n输入删除的位序i\n");
    	scanf("%d", &i);
    	printf("删除的元素为值为%d\n\n", DuLinkListDelete(&L, i, &e));
    	printf("\n\n遍历结果\n");
    	DuLinkListTraverse(L);
    
    	printf("\n输入需要查找元素的位序i\n");
    	scanf("%d", &i);
    	DulNode = GetElem(L, i);
    	if (DulNode != NULL)
    		printf("查找的元素值为%d\n", DulNode->data);
    	else printf("查找的位序不合法\n\n");
    	printf("\n\n遍历结果\n");
    	DuLinkListTraverse(L);
    
    	printf("\n输入需要查找后继的数值e\n");
    	scanf("%d", &e);
    	DulNode = DuLinkNextElem(L, e);
    	if (DulNode != NULL)
    		printf("查找的元素后继值为%d\n", DulNode->data);
    	else printf("查不到改元素\n\n");
    
    	printf("\n\n遍历结果\n");
    	DuLinkListTraverse(L);
    	return 0;
    }
    int InitDuLinkedList(DuLinkList* L)									//初始化,形参L是二级指针
    { 
    	*L = (DulNode*)malloc(sizeof(DulNode));							//头结点申请地址
    	if (*L == NULL)
    	{ 
    		printf("申请空间失败\n");
    		exit(0);
    	}
    	(*L)->data = -999;								//随便存点数据 
    	head = *L;										//头指针指向头结点
    	tail = *L;										//尾指针指向尾结点，目前只有一个结点，它既是头结点，也是尾结点
    	(*L)->prior = tail;								//头结点前驱初指向尾结点
    
    	(*L)->next = (*L);								//(*L)所指结点初始化时，既是头结点，也是尾结点。所以尾结点(**L)的后继指针，指向头结点
    	return 1;
    }
    
    DuLinkList CreatDuLinkList(DuLinkList* L)						//尾插法创建双循环向链表，形参L是二级指针
    { 
    	int x;														//新插入的结点值
    	printf("输入需要插入的元素值\n");
    	scanf("%d", &x);
    
    	while (x != 9999)											//输入999时结束插入
    	{ 
    		DuLinkList s = (DulNode*)malloc(sizeof(DulNode));				 //创建新结点
    		if (s == NULL)
    		{ 
    			printf("动态申请内存失败\n");
    			exit(0);
    		}
    		s->data = x;												//将值存入新结点
    
    		s->next = tail->next;									 //关键步骤
    		tail->next->prior = s;
    		tail->next = s;
    		s->prior = tail;
    
    		tail = s;                                              //尾指针指向新的尾结点,
    		printf("插入成功\n");
    		printf("输入需要插入的元素值(输入9999结束插入)\n");
    		scanf("%d", &x);
    	}
    	return *L;                                              //返回单链表地址
    }
    
    int DuLinkListInsert(DuLinkList* L, int i, int e)				//第i个位置插入指定元素e
    { 
    	int j = 1;
    	DuLinkList p, s;
    	p = *L;
    	while (p && j < i)											//寻找第i-1个结点
    	{ 
    		p = p->next;
    		j++;
    	}
    	if (!p || j > i)
    		return 0;											//插入位置非法
    
    	s = (DulNode*)malloc(sizeof(DulNode));                    //动态分配内存
    	if (s == NULL)
    	{ 
    		printf("动态申请内存失败\n");
    		exit(0);
    	}
    	s->data = e;
    
    	s->prior = p;											//双链表插入操作的四个关键步骤
    	s->next = p->next;
    	p->next->prior = s;
    	p->next = s;
    
    	if (p == tail)                                          //若插入位置为末尾，插入后，修改尾指针指向新尾结点
    		tail = s;
    	return 1;
    }
    
    int DuLinkListDelete(DuLinkList* L, int i, int* e)                      //删除位序为i的结点，并用e返回其元素值
    { 
    	DuLinkList p = *L;											//p最终指向被删除结点
    	int j = 1;													//从第一个结点开始找
    	while (p->next && j <= i)								 //遍历寻找第i个结点
    	{ 
    		p = p->next;
    		j++;
    	}
    
    	if (!(p->next))										//若p->next=null,此时链表长度可能小于i
    		return 0;
    	if (p == tail)										//如果被删除的是尾结点，修改尾指针指向新的尾结点
    		tail = p->prior;
    	*e = p->data;										//返回值
    
    	p->prior->next = p->next;                                //关键两步
    	p->next->prior = p->prior;
    	free(p);										  //释放内存
    
    	return *e;
    }
    
    DulNode* DuLinkPriorElem(DuLinkList L, int cur_e)					 //求前驱操作
    { 
    	DuLinkList p = L->next;                         //p指向第一个结点，不是头结点
    	while (p != head)                              //遍历整个链表寻找值为cur_e的结点,当p==head时遍历了一周
    	{ 
    		if (p->data == cur_e)
    			break;
    		p = p->next;
    	}
    	if (p == head)                                   //循环一周没找到
    		return NULL;
    	else return p->prior;
    }
    
    DulNode* DuLinkNextElem(DuLinkList L, int cur_e)			//求后继操作
    { 
    	DuLinkList p = L->next;                         //p指向第一个结点，不是头结点
    	while (p != head)                              //遍历整个链表寻找值为cur_e的结点,当p==head时遍历了一周
    	{ 
    		if (p->data == cur_e)
    			break;
    		p = p->next;
    	}
    	if (p == head)                                   //循环一周没找到
    		return NULL;
    	else return p->next;
    }
    
    DulNode* GetElem(DuLinkList L, int i)
    { 
    	int j = 1;									//计数，初始化值为1
    	DulNode* p = L->next;						//p 指向第一个结点，不是头结点
    	if (i == 0)
    		return L;								//返回头结点
    	if (i < 1)
    		return NULL;						 //位置i不合法
    	while (p && j < i && p != head)					//从第一个结点开始找,p==head时，寻找了一周
    	{ 
    		p = p->next;
    		j++;
    	}
    	if (p == head)								//链表循环了一周，i大于循环双链表长度，越界
    		return NULL;
    	return p;								 //返回第i个结点的指针，如果i大于表长，p=NULL
    }
    
    int DuLinkListTraverse(DuLinkList L)						 //遍历访问整个表L
    { 
    	DulNode* p;
    	for (p = L->next; p != NULL; p = p->next)
    	{ 
    		printf("%-5d", p->data);
    		if (p == tail)                                    //遍历到最后一个元素（tail指向尾结点）
    			break;
    	}
    	return 0;
    }

\*\*

## 测试案例 ##

\*\*  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/ddde8bb66590493f9843ca0b97a55799.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/a5302b9240fb43d5a79737edae875a6b.png