数据结构（循环单链接列表）循环单链接列表|数据结构

本文概述

循环链表的内存表示
循环单链表上的操作
C语言中的菜单驱动程序, 可实现所有操作

在循环的单链接列表中, 列表的最后一个节点包含一个指向列表的第一个节点的指针。我们可以有循环单链表以及循环双链表。
我们遍历循环的单链列表, 直到到达开始的同一节点。循环单个喜欢的列表没有开头也没有结尾。在任何节点的下一部分中都没有空值。
下图显示了循环单链接列表。

文章图片
循环链表主要用于操作系统中的任务维护。有许多示例在计算机科学中使用了循环链接列表, 包括浏览器浏览, 在该浏览器中, 用户过去访问的页面记录以循环链接列表的形式维护, 并且可以通过单击上一个按钮再次访问。
循环链表的内存表示在下图中, 一个圆形链接列表的内存表示形式, 其中包含4个科目的学生的成绩。但是, 该图像显示了循环列表如何在内存中存储的情况。列表的开头或开头指向索引为1的元素, 数据部分包含13个标记, 下一部分包含4个标记。这意味着它与存储在列表第4个索引处的节点链接。
【数据结构（循环单链接列表）】但是, 由于我们正在考虑在内存中使用循环链接列表, 因此列表的最后一个节点包含列表的第一个节点的地址。

文章图片
我们还可以在内存中拥有多个链接列表, 并且不同的起始指针指向列表中的不同起始节点。最后一个节点由其下一部分标识, 该部分包含列表的起始节点的地址。我们必须能够确定任何链接列表的最后一个节点, 以便我们能够找出遍历列表时需要执行的迭代次数。
循环单链接列表上的操作插入

序号	运作方式	描述
1	开始插入	在开始时将节点添加到循环单链列表中。
2	最后插入	最后, 将节点添加到循环单链列表中。

删除和遍历

序号	运作方式	描述
1	开始删除	首先从循环单链列表中删除节点。
2	最后删除	最后从循环单链列表中删除该节点。
3	Searching	将节点的每个元素与给定的项目进行比较, 并返回该项目在列表中的位置, 否则返回null。
4	Traversing	至少访问列表的每个元素一次, 以执行某些特定操作。

C语言中的菜单驱动程序, 可实现所有操作在循环单链表上

#include< stdio.h> #include< stdlib.h> struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main (){ int choice =0; while(choice != 7) {printf("\n*********Main Menu*********\n"); printf("\nChoose one option from the following list ...\n"); printf("\n===============================================\n"); printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search for an element\n6.Show\n7.Exit\n"); printf("\nEnter your choice?\n"); scanf("\n%d", & choice); switch(choice){case 1:beginsert(); break; case 2:lastinsert(); break; case 3:begin_delete(); break; case 4:last_delete(); break; case 5:search(); break; case 6:display(); break; case 7:exit(0); break; default:printf("Please enter valid choice.."); } }}void beginsert(){ struct node *ptr, *temp; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) {printf("\nOVERFLOW"); } else {printf("\nEnter the node data?"); scanf("%d", & item); ptr -> data = http://www.srcmini.com/item; if(head == NULL){head = ptr; ptr -> next = head; }else { temp = head; while(temp-> next != head)temp = temp-> next; ptr-> next = head; temp -> next = ptr; head = ptr; } printf("\nnode inserted\n"); }}void lastinsert(){ struct node *ptr, *temp; int item; ptr = (struct node *)malloc(sizeof(struct node)); if(ptr == NULL) {printf("\nOVERFLOW\n"); } else {printf("\nEnter Data?"); scanf("%d", & item); ptr-> data = http://www.srcmini.com/item; if(head == NULL){head = ptr; ptr -> next = head; }else{temp = head; while(temp -> next != head){temp = temp -> next; }temp -> next = ptr; ptr -> next = head; }printf("\nnode inserted\n"); }}void begin_delete(){ struct node *ptr; if(head == NULL) {printf("\nUNDERFLOW"); } else if(head-> next == head) {head = NULL; free(head); printf("\nnode deleted\n"); } else { ptr = head; while(ptr -> next != head)ptr = ptr -> next; ptr-> next = head-> next; free(head); head = ptr-> next; printf("\nnode deleted\n"); }}void last_delete(){ struct node *ptr, *preptr; if(head==NULL) {printf("\nUNDERFLOW"); } else if (head -> next == head) {head = NULL; free(head); printf("\nnode deleted\n"); } else {ptr = head; while(ptr -> next != head){preptr=ptr; ptr = ptr-> next; }preptr-> next = ptr -> next; free(ptr); printf("\nnode deleted\n"); }}void search(){ struct node *ptr; int item, i=0, flag=1; ptr = head; if(ptr == NULL) {printf("\nEmpty List\n"); } else { printf("\nEnter item which you want to search?\n"); scanf("%d", & item); if(head -> data =http://www.srcmini.com/= item){printf("item found at location %d", i+1); flag=0; }else {while (ptr-> next != head){if(ptr-> data =http://www.srcmini.com/= item){printf("item found at location %d ", i+1); flag=0; break; } else{flag=1; }i++; ptr = ptr -> next; }}if(flag != 0){printf("Item not found\n"); } } }void display(){ struct node *ptr; ptr=head; if(head == NULL) {printf("\nnothing to print"); } else {printf("\n printing values ... \n"); while(ptr -> next != head){printf("%d\n", ptr -> data); ptr = ptr -> next; }printf("%d\n", ptr -> data); }}

输出：

*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?1Enter the node data?10node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?2Enter Data?20node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?2Enter Data?30node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?3node deleted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?4node deleted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?5Enter item which you want to search?20item found at location 1*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?6 printing values ... 20*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in begining2.Insert at last3.Delete from Beginning4.Delete from last5.Search for an element6.Show7.ExitEnter your choice?7