数据结构：循环单链接列表

本文概述

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

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

我们遍历循环的单链列表, 直到到达开始的同一节点。循环单个喜欢的列表没有开头也没有结尾。在任何节点的下一部分中都没有空值。

下图显示了循环单链接列表。

循环链表主要用于操作系统中的任务维护。有许多示例在计算机科学中使用了循环链接列表, 包括浏览器浏览, 在该浏览器中, 用户过去访问的页面记录以循环链接列表的形式维护, 并且可以通过单击上一个按钮再次访问。

循环链表的内存表示

在下图中, 一个圆形链接列表的内存表示形式, 其中包含4个科目的学生的成绩。但是, 该图像显示了循环列表如何在内存中存储的情况。列表的开头或开头指向索引为1的元素, 数据部分包含13个标记, 下一部分包含4个标记。这意味着它与存储在列表第4个索引处的节点链接。

但是, 由于我们正在考虑在内存中使用循环链接列表, 因此列表的最后一个节点包含列表的第一个节点的地址。

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

循环单链接列表上的操作

插入

删除和遍历

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 = 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);
	}
			
}

输出：

*********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?
1

Enter the node data?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