个性化阅读
专注于IT技术分析
        找回密码
当前位置：srcmini > 数据结构 > 正文

数据结构之双链表

2020-03-04 16:10:10 分类：数据结构 阅读(785) 评论(0)

本文概述

双链表是链表的一种复杂类型, 其中节点包含指向序列中上一个节点和下一个节点的指针。因此, 在双向链表中, 节点由三部分组成：节点数据, 指向顺序中下一个节点的指针（下一个指针）, 指向上一个节点的指针（上一个指针）。图中显示了双向链接列表中的示例节点。

双链表

下图显示了一个双向链接列表, 该列表包含三个节点, 这些节点的数据部分中的数字从1到3。

双链表

在C语言中, 双向链表中节点的结构可以表示为：

struct node 
{
	struct node *prev; 
	int data;
	struct node *next; 
}

第一个节点的上一个部分和最后一个节点的下一个部分将始终包含null, 指示在每个方向上的结束。

在一个单链表中, 我们只能在一个方向上遍历, 因为每个节点都包含下一个节点的地址, 并且没有任何先前节点的记录。但是, 双链表克服了单链表的这一局限性。由于列表中的每个节点都包含其前一个节点的地址, 因此, 我们也可以使用存储在每个节点的前一部分中的前一个地址, 找到有关前一个节点的所有详细信息。

双链表的内存表示

下图显示了双向链接列表的内存表示形式。通常, 双向链表会为每个节点占用更多空间, 因此会导致更广泛的基本操作, 例如插入和删除。但是, 由于列表在两个方向（向前和向后）都维护指针, 因此我们可以轻松地操作列表的元素。

在下图中, 列表的第一个元素（即13）存储在地址1。头指针指向起始地址1。由于这是被添加到列表的第一个元素, 因此列表的prev包含空值。列表的下一个节点位于地址4, 因此第一个节点的下一个指针包含4。

我们可以以这种方式遍历列表, 直到找到下一个包含null或-1的节点。

双链表

双链表上的操作

节点创建

struct node 
{
	struct node *prev;
	int data;
	struct node *next;
};
struct node *head;

下表描述了有关双链表的所有其余操作。

序号 运作方式 描述
1 开始插入 开始时将节点添加到链表中。
2 最后插入 将节点添加到链接列表的末尾。
3 在指定节点后插入 将节点添加到指定节点之后的链接列表中。
4 开始删除 从列表的开头删除节点
5 最后删除 从列表末尾删除节点。
6 删除具有给定数据的节点 删除紧接在包含给定数据的节点之后的节点。
7 Searching 将每个节点数据与要搜索的项目进行比较, 如果找到的项目返回列表, 则返回该项目在列表中的位置。
8 Traversing 至少访问列表的每个节点一次, 以执行某些特定操作, 例如搜索, 排序, 显示等。

C中的菜单驱动程序可实现双链表的所有操作

#include<stdio.h>
#include<stdlib.h>
struct node
{
    struct node *prev;
    struct node *next;
    int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
	while(choice != 9)
	{
		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.Insert at any random location\n4.Delete from Beginning\n
		5.Delete from last\n6.Delete the node after the given data\n7.Search\n8.Show\n9.Exit\n");
		printf("\nEnter your choice?\n");
		scanf("\n%d", &choice);
		switch(choice)
		{
			case 1:
			insertion_beginning();
			break;
			case 2:
            		insertion_last();
			break;
			case 3:
			insertion_specified();
			break;
			case 4:
			deletion_beginning();
			break;
			case 5:
			deletion_last();
			break;
			case 6:
			deletion_specified();
			break;
			case 7:
			search();
			break;
			case 8:
			display();
			break;
			case 9:
			exit(0);
			break;
			default:
			printf("Please enter valid choice..");
		}
	}
}
void insertion_beginning()
{
   struct node *ptr; 
   int item;
   ptr = (struct node *)malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\nOVERFLOW");
   }
   else
   {
    printf("\nEnter Item value");
    scanf("%d", &item);
    
   if(head==NULL)
   {
       ptr->next = NULL;
       ptr->prev=NULL;
       ptr->data=item;
       head=ptr;
   }
   else 
   {
       ptr->data=item;
       ptr->prev=NULL;
       ptr->next = head;
       head->prev=ptr;
       head=ptr;
   }
   printf("\nNode inserted\n");
}
   
}
void insertion_last()
{
   struct node *ptr, *temp;
   int item;
   ptr = (struct node *) malloc(sizeof(struct node));
   if(ptr == NULL)
   {
       printf("\nOVERFLOW");
   }
   else
   {
       printf("\nEnter value");
       scanf("%d", &item);
        ptr->data=item;
       if(head == NULL)
       {
           ptr->next = NULL;
           ptr->prev = NULL;
           head = ptr;
       }
       else
       {
          temp = head;
          while(temp->next!=NULL)
          {
              temp = temp->next;
          }
          temp->next = ptr;
          ptr ->prev=temp;
          ptr->next = NULL;
          }
           
       }
     printf("\nnode inserted\n");
    }
void insertion_specified()
{
   struct node *ptr, *temp;
   int item, loc, i;
   ptr = (struct node *)malloc(sizeof(struct node));
   if(ptr == NULL)
   {
	   printf("\n OVERFLOW");
   }
   else
   {
	   temp=head;
	   printf("Enter the location");
	   scanf("%d", &loc);
	   for(i=0;i<loc;i++)
	   {
		   temp = temp->next;
		   if(temp == NULL)
		   {
			   printf("\n There are less than %d elements", loc);
			   return;
		   }
	   }
	   printf("Enter value");
	   scanf("%d", &item);
	   ptr->data = item;
	   ptr->next = temp->next;
	   ptr -> prev = temp;
	   temp->next = ptr;
	   temp->next->prev=ptr;
	   printf("\nnode inserted\n");
   }
}
void deletion_beginning()
{
    struct node *ptr;
    if(head == NULL)
	{
		printf("\n UNDERFLOW");
	}
	else if(head->next == NULL)
	{
		head = NULL; 
		free(head);
		printf("\nnode deleted\n");
	}
	else
	{
		ptr = head;
		head = head -> next;
		head -> prev = NULL;
		free(ptr);
		printf("\nnode deleted\n");
	}

}
void deletion_last()
{
    struct node *ptr;
    if(head == NULL)
	{
		printf("\n UNDERFLOW");
	}
	else if(head->next == NULL)
	{
		head = NULL; 
		free(head);	
		printf("\nnode deleted\n");
	}
	else 
	{
		ptr = head; 
		if(ptr->next != NULL)
		{
			ptr = ptr -> next; 
		}
		ptr -> prev -> next = NULL; 
		free(ptr);
		printf("\nnode deleted\n");
	}
}
void deletion_specified()
{
	struct node *ptr, *temp;
	int val;
	printf("\n Enter the data after which the node is to be deleted : ");
	scanf("%d", &val);
	ptr = head;
	while(ptr -> data != val)
	ptr = ptr -> next;
	if(ptr -> next == NULL)
	{
		printf("\nCan't delete\n");
	}
	else if(ptr -> next -> next == NULL)
	{
		ptr ->next = NULL;
	}
	else
	{ 
		temp = ptr -> next;
		ptr -> next = temp -> next;
		temp -> next -> prev = ptr;
		free(temp);
		printf("\nnode deleted\n");
	}	
}
void display()
{
	struct node *ptr;
	printf("\n printing values...\n");
	ptr = head;
	while(ptr != NULL)
	{
		printf("%d\n", ptr->data);
		ptr=ptr->next;
	}
} 
void search()
{
	struct node *ptr;
	int item, i=0, flag;
	ptr = head; 
	if(ptr == NULL)
	{
		printf("\nEmpty List\n");
	}
	else
	{ 
		printf("\nEnter item which you want to search?\n"); 
		scanf("%d", &item);
		while (ptr!=NULL)
		{
			if(ptr->data == item)
			{
				printf("\nitem found at location %d ", i+1);
				flag=0;
				break;
			} 
			else
			{
				flag=1;
			}
			i++;
			ptr = ptr -> next;
		}
		if(flag==1)
		{
			printf("\nItem not found\n");
		}
	}	
		
}

输出量

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value12

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value123

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
1

Enter Item value1234

Node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
1234
123
12

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
2

Enter value89

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
3
Enter the location1
Enter value12345

node inserted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
1234
123
12345
12
89

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.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.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
5

node deleted

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
123
12345

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted : 123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
8

 printing values...
123

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
7

Enter item which you want to search?
123

item found at location 1 
*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
6

 Enter the data after which the node is to be deleted : 123

Can't delete

*********Main Menu*********

Choose one option from the following list ...

===============================================

1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete the node after the given data
7.Search
8.Show
9.Exit

Enter your choice?
9 

Exited..
赞(0)
未经允许不得转载：srcmini » 数据结构之双链表
标签：

相关推荐

评论 抢沙发

评论前必须登录！

 

猜你喜欢

热门标签

网站开发 (2587)WordPress开发 (2055)WordPress主题 (1517)Web开发 (692)主题 (528)数据科学 (444)合集 (336)资源合集 (333)教程合集 (317)函数 (287)页面 (267)python开发 (261)百度盘 (246)项目示例 (243)WordPress自定义页面 (233)图像 (219)错误 (213)视频 (195)网站 (190)网红 (189)UX设计 (187)Web安全 (179)模板 (178)Web运维 (177)应用程序 (177)WordPress插件 (176)插件 (171)前端开发 (166)美女 (164)主播 (164)