本文概述
- 循环双链表的内存管理
- 循环双链表上的操作
- C程序实现循环双链表上的所有操作
下图显示了一个循环的双向链表。
文章图片
由于圆形双向链表在其结构中包含三部分, 因此它需要每个节点更多的空间和更昂贵的基本操作。但是, 圆形双向链接列表使指针的操作变得容易, 并且搜索效率提高了两倍。
循环双链表的内存管理 下图显示了为循环双链表分配内存的方式。变量head包含列表的第一个元素的地址, 即1, 因此列表的起始节点包含数据A的地址为1。由于列表的每个节点都应具有三部分, 因此, 列表的起始节点该列表包含最后一个节点的地址（即8）和下一个节点（即4）。列表的最后一个节点（存储在地址8处, 数据为6）包含该列表的第一个节点的地址, 如图所示。在循环双向链表中, 最后一个节点由存储在最后一个节点的下一部分中的第一个节点的地址标识, 因此包含第一个节点的地址的节点实际上是第一个节点的最后一个节点。清单。
文章图片
循环双链表上的操作 可以在循环双链表上执行各种操作。圆形双向链表的节点结构类似于双向链表。但是, 下表描述了循环双链表上的操作。
| 序号 | 运作方式 | 描述 |
|---|---|---|
| 1 | 开始插入 | 首先在循环双链列表中添加节点。 |
| 2 | 最后插入 | 最后在循环双向链表中添加节点。 |
| 3 | 开始删除 | 从头开始删除循环双链列表中的节点。 |
| 4 | 最后删除 | 最后在循环双链列表中删除节点。 |
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 deletion_beginning();
void deletion_last();
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 Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search\n6.Show\n7.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:deletion_beginning();
break;
case 4:deletion_last();
break;
case 5:search();
break;
case 6:display();
break;
case 7:exit(0);
break;
default:printf("Please enter valid choice..");
} }}void insertion_beginning(){struct node *ptr, *temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL){printf("\nOVERFLOW");
}else{printf("\nEnter Item value");
scanf("%d", &
item);
ptr->
data=http://www.srcmini.com/item;
if(head==NULL){head = ptr;
ptr ->
next = head;
ptr ->
prev = head;
}else {temp = head;
while(temp ->
next != head) {temp = temp ->
next;
} temp ->
next = ptr;
ptr ->
prev = temp;
head ->
prev = ptr;
ptr ->
next = head;
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=http://www.srcmini.com/item;
if(head == NULL){head = ptr;
ptr ->
next = head;
ptr ->
prev = head;
}else{temp = head;
while(temp->
next !=head){temp = temp->
next;
}temp->
next = ptr;
ptr ->
prev=temp;
head ->
prev = ptr;
ptr ->
next = head;
}}printf("\nnode inserted\n");
}void deletion_beginning(){struct node *temp;
if(head == NULL) {printf("\n UNDERFLOW");
} else if(head->
next == head) {head = NULL;
free(head);
printf("\nnode deleted\n");
} else {temp = head;
while(temp ->
next != head){temp = temp ->
next;
}temp ->
next = head ->
next;
head ->
next ->
prev = temp;
free(head);
head = temp ->
next;
}}void deletion_last(){struct node *ptr;
if(head == NULL) {printf("\n UNDERFLOW");
} else if(head->
next == head) {head = NULL;
free(head);
printf("\nnode deleted\n");
} else {ptr = head;
if(ptr->
next != head){ptr = ptr ->
next;
}ptr ->
prev ->
next = head;
head ->
prev = ptr ->
prev;
free(ptr);
printf("\nnode deleted\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);
}}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");
} } }输出：
*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?1Enter Item value123Node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?2Enter value234node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?1Enter Item value90Node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?2Enter value80node inserted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?3*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?4node deleted*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?6 printing values ... 123*********Main Menu*********Choose one option from the following list ...===============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?5Enter item which you want to search?123item found at location 1*********Main Menu*********Choose one option from the following list ...============================================1.Insert in Beginning2.Insert at last3.Delete from Beginning4.Delete from last5.Search6.Show7.ExitEnter your choice?7推荐阅读
- 数据结构（循环队列）
- 桶排序算法实现
- 冒泡排序算法实现全解
- 图遍历算法（广度优先搜索算法）
- 比并排序算法实现详解
- B树实现详细步骤解析
- B+树实现详细步骤解析
- 二叉树（binary tree）实现详解
- 二叉查找树（binary search tree）实现详解