| 单链表练习题 | 您所在的位置：网站首页 › c语言单向链表程序代码 › 单链表练习题 |
单链表练习题
|
单链表练习题-构造环以及判断是否有环(C语言实现)
文章目录
单链表练习题-构造环以及判断是否有环(C语言实现)一.题目二.构造环三.判断是否有环四.全部代码五.测试
一.题目
如下图所示：
本次就是要构造环以及判断是否有环。 二.构造环 构造环比较简单，只需要修改某个结点的指针就可以了，为了方便我这里直接修改尾结点的指针，使其指向指定元素的后继，这样就构成了一个环。 bool Make_Loop(LinkList *L,ElemType e) //构造环,直接让尾指针指向特定结点的后继 { LinkList *q,*s,*tail;//*s标记特定的结点,tail表示最后一个结点 q = L->next; //打印出所有元素 while(q->next!=NULL) { if(q->data==e)//找到指定结点 s = q; q = q->next; } tail = q;//跳出while循环时,q已经指向了最后一个结点 //构造环 tail->next = s->next; return true; } 三.判断是否有环 判断是否有环也比较简单，思路是：设置一个快指针和慢指针，慢指针每次走一步，快指针每次走两步，如果环存在，那么快指针总能追上慢指针，也就是如果快慢指针能指向同一个元素的时候，那么说明是有环的。反之，如果快慢指针无法相遇，那么链表就无环。 bool Is_Loop(LinkList *L)//判断链表是否有环,有环现在能判断 { LinkList *slow,*fast; slow = fast = L->next; fast = fast->next;//fast先走一步 while((slow!=NULL)&&(fast->next!=NULL)) { slow = slow->next;//slow指针每次走一步 fast = fast->next;//fast指针每次走两步 fast = fast->next; if(slow == fast)//如果快慢指针相遇,说明环存在,直接返回true return true; } return false;//如果指针到了末尾函数还没返回，说明环不存在 } 四.全部代码 #include #include #include //根据C99标准,C语言使用bool类型需要添加这个头文件 typedef int ElemType; typedef struct LinkNode { ElemType data; struct LinkNode *next; }LinkList; //------------ 函数声明 ----------// void MainMenu(); bool InitLinkList(LinkList *L);//初始化 bool InsertLinkList(LinkList *L,ElemType e);//插入 void PrintAll(LinkList *L);//输出所有元素 bool Make_Loop(LinkList *L,ElemType e); //构造环 bool Is_Loop(LinkList *L);//判断链表是否有环 //------------ 函数声明 ----------// int main() { LinkList L; int ch; ElemType element; if(InitLinkList(&L)) printf("初始化成功！\n"); else printf("初始化失败！\n"); while(1) { MainMenu(); printf("请输入您要执行的操作:"); scanf("%d",&ch); switch(ch) { case 0: printf("感谢使用，已退出！"); exit(0); break; case 1: printf("请输入您要插入的元素:\n"); scanf("%d",&element); if(InsertLinkList(&L,element)) printf("插入成功！\n"); else printf("插入失败！\n"); break; case 2: PrintAll(&L); break; case 3: printf("请输入您要让环指针指向的元素:\n"); scanf("%d",&element); if(Make_Loop(&L,element)) printf("环构造成功！\n"); else printf("环构造失败！\n"); break; case 4: if(Is_Loop(&L)) printf("链表有环！\n"); else printf("链表无环！\n"); break; default: printf("您输入的操作指令有误！请重新输入！"); } } return 0; } //主菜单，显示 void MainMenu() { printf("\n\n\n"); printf("\t **** 单链表构造环、判断是否有环 ****\n\n"); printf("\t ------- 0.退出 \n\n"); printf("\t ------- 1.插入元素\n\n"); printf("\t ------- 2.输出所有元素\n\n"); printf("\t ------- 3.使链表构成环\n\n"); printf("\t ------- 4.判断链表是否有环\n\n"); printf("\t *************************************\n"); } //初始化单链表(带头结点) bool InitLinkList(LinkList *L) { //先申请一个头结点 LinkList *head = (LinkList *)malloc(sizeof(LinkList)); L->next = head; head->next = NULL;//头结点之后一开始还没元素 return true; } //插入 bool InsertLinkList(LinkList *L,ElemType e) { //头插法 LinkList *p = L;// //申请一个新的结点 LinkList *s = (LinkList *)malloc(sizeof(LinkList)); s->data = e;//赋值 //修改指针 将结点s插入到结点p之后 s->next = p->next;//s指针指向 p->next = s; return true; } //打印所有元素 void PrintAll(LinkList *L) { LinkList *q; q = L->next; //打印出所有元素 while(q->next!=NULL) { printf("%d ",q->data); q = q->next; } } bool Make_Loop(LinkList *L,ElemType e) //构造环,直接让尾指针指向特定结点的后继 { LinkList *q,*s,*tail;//*s标记特定的结点,tail表示最后一个结点 q = L->next; //打印出所有元素 while(q->next!=NULL) { if(q->data==e)//找到指定结点 s = q; q = q->next; } tail = q;//跳出while循环时,q已经指向了最后一个结点 //构造环 tail->next = s->next; return true; } bool Is_Loop(LinkList *L)//判断链表是否有环,有环现在能判断 { LinkList *slow,*fast; slow = fast = L->next; fast = fast->next;//fast先走一步 while((slow!=NULL)&&(fast->next!=NULL)) { slow = slow->next;//slow指针每次走一步 fast = fast->next;//fast指针每次走两步 fast = fast->next; if(slow == fast) return true; } return false; } 五.测试1.首先依次插入元素并输出：
2.此时是无环的，先判断一下算法是否正确：
3.判断正确，那就构造一个环：
4.再来判断是否有环：
完成。 |
【本文地址】
公司简介
联系我们