下一个→ ←上一页

循环单链表

在循环单链表中，列表的最后一个节点包含指向列表第一个节点的指针。我们可以有循环单链表和循环双链表。

我们遍历一个循环单链表，直到到达开始的节点。圆形点赞列表没有开始也没有结束。在任何节点的下一部分中都不存在空值。

下图显示了一个循环单链表。

循环链表主要用于操作系统的任务维护。循环链表在计算机科学中的应用有很多例子，包括浏览器浏览，其中用户过去访问过的页面记录以循环链表的形式保存，并且可以在点击上一个按钮时再次访问。

循环链表的内存表示:

在下图中，一个循环链表的记忆表示包含了一个学生在四个科目的分数。然而，该图像显示了循环列表如何存储在内存中的一瞥。列表的开头或头部指向索引为1的元素，数据部分包含13个标记，下一部分包含4个标记。这意味着它与存储在列表第4个索引处的节点链接。

然而，由于我们在内存中考虑循环链表，因此列表的最后一个节点包含列表的第一个节点的地址。

我们也可以在内存中有多个链表，不同的开始指针指向链表中不同的开始节点。最后一个节点由它的下一部分标识，下一部分包含列表的开始节点的地址。我们必须能够识别任何链表的最后一个节点，以便我们能够找出在遍历链表时需要执行的迭代次数。

循环单链表的操作:

插入

SN	操作	描述
1	开始插入	在循环单链表的开头添加一个节点。
2	最后插入	最后在循环单链表中添加一个节点。

删除和遍历

SN	操作	描述
1	开始删除	从循环单链表开始移除节点。
2	最后删除	最后从循环单链表中删除节点。
3.	搜索	将节点的每个元素与给定的项目进行比较，并返回项目在列表中出现的位置，否则返回null。
4	遍历	为了执行某些特定的操作，至少访问列表中的每个元素一次。

菜单驱动程序用C语言实现所有操作

在循环单链表上

            #include<stdlib.h> struct node {int data;Struct node *next;};Struct node *head;Void beginsert ();Void lastinsert ();空白randominsert ();空白begin_delete ();空白last_delete ();空白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 = 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 = 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 == item) { printf("item found at location %d",i+1); flag=0; } else { while (ptr->next != head) { if(ptr->data == 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); } }
           

输出:

*********主菜单*********从以下列表中选择一个…=============================================== 1。插入第2位。最后插入3。从开始4删除。从最后5删除。搜索元素6。显示7。退出输入您的选择?1输入节点数据?10 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 2 Enter Data?20 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 2 Enter Data?30 node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 3 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 4 node deleted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 5 Enter item which you want to search? 20 item found at location 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 6 printing values ... 20 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Delete from Beginning 4.Delete from last 5.Search for an element 6.Show 7.Exit Enter your choice? 7

下一个话题循环双链表

←上一页下一个→