循环单链表的创建及基本操作 C语言

r囧r小猫 2022-12-12 01:54 154阅读 0赞

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

在单链表的基础上增加了循环，和单链表几乎是一样的，只是对**链表头结点的定义**和对**链表结尾的判断**，从**NULL变成了指向头结点L**。别的定义和单链表一样。  
代码如下：

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

（完）