双向循环链表的创建及基本操作

今天药忘吃喽~ 2022-12-12 02:28 156阅读 0赞

## 数据结构c语言双向循环链表 ##

双向循环链表在定义上类似于循环单链表，就多了个前指针，以方便于向前查找。在双向链表中需要同时修改两个方向的指针，是单向链表指针的两倍。  
**完整代码如下：**

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct DuLNode
    { 
    	int data;//结点的数据域 
    	struct DuLNode *prior;//结点的后指针域 
    	struct DuLNode *next;//结点的前指针域 
    }DuLNode,*DuLinkList;//DuLinkList为指向结构体LNode的指针类型
    
    DuLNode* InitDuList()//初始化链表 构建一个空的线性表 
    { 
    	DuLNode* L = (DuLNode*)malloc(sizeof(DuLNode));
    	if(L==NULL)//判断申请L结点是否为空 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	L->data = NULL;//定义头结点
    	L->next = L;
    	L->prior = L;
    }
    
    void Interrupt(void)//创建一个中断函数 
    { 
    	while(1)//用于检测换行符，使函数脱离scanf的连续输出 
    		if(getchar()=='\n')
    			break;
    } 
    
    DuLinkList CreatDuList1(DuLinkList &L)//尾插法创建链表 
    { 
    	int a,b,i;
    	DuLNode* p = L;//导入头结点，并创建一个结点s指向头结点 
    	printf("请输入表长： "); 
    	scanf("%d",&a);//输入要插入的链表长度 
    	Interrupt();//中断scanf 
    	printf("请输入表数据： ");
    	for(i=0;i<a;i++)
    	{ 
    		scanf("%d",&b);//输入要链表数据 
    		DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));//创建一个结点
    		s->data = b;
    		p->next = s;
    		s->prior = p;
    		s->next = L;
    		L->prior = s;
    		p = p->next;
    	}
    	Interrupt();
    	return 0;
    }
    DuLinkList CreatDuList2(DuLinkList &L)//头插法创建链表
    { 
    	int a,b,i;
    	DuLNode* p = L;//导入头结点，并创建一个结点s指向头结点 
    	printf("请输入表长： "); 
    	scanf("%d",&a);//输入要插入的链表长度 
    	Interrupt();
    	printf("请输入表数据： ");
    	for(i=0;i<a;i++)
    	{ 
    		scanf("%d",&b);//输入要链表数据 
    		DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));//创建一个结点
    		s->data = b;
    		L->next = s;
    		s->prior = L;
    		s->next = p;
    		p->prior = s;
    		p = s;
    	}
    	Interrupt();
    	return 0;
    }
    int Length(DuLinkList L)//求链表长度 
    { 
    	int i=0;
    	DuLNode* p = L;
    	while(1)//建立一个死循环，链表最后一个结点指向L(头结点)，以此为判断break循环条件 
    	{ 
    		if(p->next == L)
    			break;
    		p = p->next;
    		i++;
    	} 
    	return i;//返回链表长度 
    }
    
    void TraverseDuLNode(DuLinkList L)//遍历链表，并输出链表
    { 
    	DuLNode* p = L;//创建一个结点并指向头结点 
    	if(Length(L) == 0)//判断链表是否为空 
    	{ 
    		printf("空表\n");
    	}
    	else
    	{ 
    		while(1)//建立一个死循环，链表最后一个结点指向L(头结点)，以此为判断break循环条件
    		{ 
    			p = p->next;
    			printf("%d ",p->data);
    			if(p->next == L)//判断break循环条件
    				break; 
    		}
    		printf("\n");
    	}
    	
    }
    
    int LocateElem(DuLinkList L,int e)//按值查找操作。在表L中查找具有给定关键字值的元素 
    { 
    	DuLNode* p = L;//创建一个结点并指向头结点 
    	int i=0; 
    	if(Length(L)==0)
    	{ 
    		printf("空表无法查询\n");
    		return 0;
    	}
    	else
    	{ 
    		bool a = true;//利用bool类型，来判断链表中是否存在要查找的值 
    		scanf("%d",&e);//要查找的值 
    		Interrupt();
    		while(1)//建立一个死循环，链表最后一个结点指向L(头结点)，以此为判断break循环条件 
    		{ 
    			p = p->next;
    			i++;
    			if(p->data == e)
    			{ 
    				printf("第 %d 位 ",i);
    				a = false;
    			}
    			if(p->next == L)
    				break;
    		}
    		if(a)//链表中没有要查找的值 
    			printf("没找到！"); 
    		printf("\n");
    		return 0;
    	}
    }
    int GetElem(DuLinkList L,int i)//按位查找操作 
    { 
    	if(Length(L) == 0)//判断链表是否为空 
    	{ 
    		printf("空表无法查询！\n");
    		return 0;
    	}
    	scanf("%d",&i);//输入要查找第几位 
    	Interrupt();
    	int j=0;
    	DuLNode* p = L;//创建一个结点并指向头结点 
    	if(i<1||i>Length(L))//判断输入的i值是否合理
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	else
    	{ 
    		for( ;j<i;j++)//利用循环，是p结点指向第i位 
    			p = p->next;
    		printf("%d\n",p->data);
    		return 0;
    	}
    }
    int DuListInsert(DuLinkList &L,int i,int e)//插入操作
    { 
    	int j;
    	DuLNode* p = L;//创建一个结点并指向头结点 
    	scanf("%d %d",&i,&e);//输入要插入链表的位置，和值 
    	Interrupt();                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               
    	if(i<1||i>Length(L)+1)//判断插入链表的位置是否合理 
    	{ 
    		printf("ERROR!");
    		return 0;
    	}
    	else
    	{ 
    		DuLNode* s = (DuLNode*)malloc(sizeof(DuLNode));//创建一个新结点 
    		s->data = e;
    		for(j=1;j<i;j++)//利用循环，是p结点指向第i-1位
    			p = p->next;
    		p->next->prior = s;
    		s->next = p->next;
    		p->next = s;
    		s->prior = p;
    		printf("插入成功\n");
    	}
    }
    int DuListDelete(DuLinkList &L,int i)//删除操作 
    { 
    	int j;
    	DuLNode* p = L;//创建一个结点并指向头结点 
    	scanf("%d",&i);//输入要删除链表的结点位置 
    	Interrupt();
    	if(Length(L)==0)//判断要删除的链表是否为空表 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	if(i<1||i>Length(L))//判断删除的结点位置是否合理 
    	{ 
    		printf("ERROR!\n");
    		return 0;
    	}
    	else
    	{ 
    		for(j=0;j<i;j++)//利用循环，是p结点指向第i位 
    			p = p->next;
    		p->prior->next = p->next;
    		p->next->prior = p->prior; 
    		printf("删除成功\n");
    		return 0; 		
    	}
    }
    int main()
    { 
    	int a,b,i=0; 
    	char c;
    	DuLinkList L;//将L定义为LinkList类型的变量，便于直接引用 
    	L = InitDuList();
    	printf("输入0为尾插法（其他为头插法）："); 
    	scanf("%d",&b);
    	Interrupt();//中断scanf 
    	if(b==0)
    		CreatDuList1(L);//尾插法 
    	else
    		CreatDuList2(L);//头插法 
    	TraverseDuLNode(L);
    	printf("操作输入序号选择：\n 1：遍历链表\n 2:链表的按位查找\n 3:删除链表元素\n 4:插入链表元素\n 5:链表的按值查找\n 6：表长\n输入#退出\n");	
    	while(1)
    	{ 
    		int f = 0;
    		printf("请选择："); 
    		scanf("%c",&c);
    		Interrupt();//中断scanf 
    		switch(c)
    		{ 
    			case '1': printf("遍历并输出链表： ");TraverseDuLNode(L); break;
    			case '2': printf("链表的按位查找（取值位置）： ");GetElem(L,a); break;
    			case '3': printf("删除并返回要删除的元素（删除的位置）： ");DuListDelete(L,a); break;
    			case '4': printf("插入元素（位置 插入的元素）： ");DuListInsert(L,a,a); break;
    			case '5': printf("链表的按值查找（输入要查找的元素）： ");LocateElem(L,a); break;
    			case '6': a = Length(L);printf("链表长为： %d\n",a); break;
    			case '#': f = 1; break;
    			default: printf("ERROR\n");
    		}
    		if (f == 1) 
    		{ 
    			printf("已正常退出!\n");
    			break;
    		}
    	}
    	free(L); 
    	return 0;
    }

（完）