目录
一、基础概念
对链表而言,双向均可遍历是最方便的,另外首尾相连循环遍历也可大大增加链表操作的便捷性。因此,双向循环链表,是在实际运用中是最常见的链表形态。
二、适用场景
经过单链表、双链表的学习,可以总结链表的适用场合:
1.适合用于节点数目不固定,动态变化较大的场合。
2.适合用于节点需要频繁插入、删除的场合。
3.适合用于对节点查找效率不十分敏感的场合 。
三、双向循环链表功能
1结构体节点设计
typedef struct node
{
int data;
//指向前缀节点的指针
struct node * prev;
//指向后缀节点的指针
struct node * next;
}node; //node == struct node
2.初始化
node *initList(void)
{
//在堆空间里面开辟新的内存
node *new = malloc(sizeof(node));
//判断是否开辟成功,开辟失败后返回提示
if(new == NULL)
{
printf("malloc fail\n");
return NULL;
}
//开辟的空间数据初始化为0
new->data = 0;
//双向循环链表,单个节点也是循环链表
new->next = new;
new->prev = new;
return new;
}
3.将新节点插入到链表的首部
void insertHead_1(node *head, node *new)
{
new->next = head->next;
head->next->prev = new;
new->prev = head;
head->next = new;
}
4.将新节点插入到链表的尾部
void insertHead_2(node *head, node *new)
{
new->prev = head->prev;
head->prev->next = new;
head->prev = new;
new->next = head;
}
5.查找数据
node *find_data(node *head, int data)
{
node *p = NULL;
for(p = head->next; p != head ; p = p->next)
{
//判断节点的数据是否等于 查看的数据,如果是,返回节点
if(p->data == data)
{
return p;
}
}
return NULL;
}
6.节点删除
node *del_node(node *head, int data)
{
node *del;
del = find_data(head, data);
if(del == NULL)
{
printf("链表当中没有此数据节点\n");
return NULL;
}
//将点解下来
del->next->prev = del->prev;
del->prev->next = del->next;
//把解下来的节点前后都指向自己
del->next=del;
del->prev=del;
return del;
}
7.打印数据
void display(node *head)
{
node *p;
for(p = head->next; p != head; p=p->next)
{
printf("%d\t", p->data);
}
printf("\n");
}
8.移动数据头插
void move_front(node *head)
{
int data1, data2;
node *move, *basic;
printf("请输入数据要插入哪个前面:");
scanf("%d", &data1);
move=find_data(head,data1);
if (move==NULL)
{
printf("找不到该数据");
return;
}
printf("请输入需要移动的数据:");
scanf("%d", &data2);
basic=del_node(head,data2);
if (move==NULL)
{
printf("找不到该数据");
return;
}
insertHead_2(move,basic);
printf("插入成功");
return;
}
9.移动数据尾插
void move_behind(node *head)
{
int data1, data2;
node *move, *basic;
printf("请输入数据要插入哪个后面:");
scanf("%d", &data1);
move=find_data(head,data1);
if (move==NULL)
{
printf("找不到该数据");
return;
}
printf("请输入需要移动的数据:");
scanf("%d", &data2);
basic=del_node(head,data2);
if (move==NULL)
{
printf("找不到该数据");
return;
}
insertHead_1(move,basic);
printf("插入成功");
return;
}
10.双向循环链表的销毁
void destroy(node *head)
{
node *p=head->next;
while(p!=head)
{
node *pp=p;
p=p->next;
free(pp);
}
head->next=head;
head->prev=head;
printf("已经成功摧毁\n");
}
完整代码
#include <stdio.h>
#include <stdlib.h>
//结构体节点设计
typedef struct node
{
int data;
//指向前缀节点的指针
struct node * prev;
//指向后缀节点的指针
struct node * next;
}node; //node == struct node
//函数声明
node *initList(void);
void insertHead_1(node *head, node *new);
void insertHead_2(node *head, node *new);
node *find_data(node *head, int data);
node *del_node(node *head, int data);
void display(node *head);
void move_front(node *head);
void move_behind(node *head);
void destroy(node *head);
int main(void)
{
//定义局部变量
char ch;
int data, ret,q;
node *head, *new, *find, *del;
//生产一个双向链表结构体
head = initList();
while(1)
{
printf("===================操作功能==================\n");
printf("\t\ta:头插添加数据\n");
printf("\t\tb:尾插添加数据\n");
printf("\t\tc:查找数据\n");
printf("\t\td:删除数据\n");
printf("\t\tp:显示数据\n");
printf("\t\tn:节点移动头插\n");
printf("\t\tm:节点移动尾插\n");
printf("\t\tt:销毁双向链表\n");
//等待用户指令输入
ch = getchar();
switch (ch)
{
//头插添加数据
case 'a':
new = initList();
printf("请输入要头插的数据:");
scanf("%d", &new->data);
insertHead_1(head, new);
break;
//尾插添加数据
case 'b':
new = initList();
printf("请输入要尾插的数据:");
scanf("%d", &new->data);
insertHead_2(head, new);
break;
//查找数据
case 'c':
printf("请输入要查找的数据:");
scanf("%d", &data);
find = find_data(head, data);
if(find == NULL)
{
printf("链表当中没有此数据节点\n");
}
else
{
printf("链表当中有此数据节点\n它的节点地址:%p\n", find);
}
break;
//删除数据
case 'd':
printf("请输入要删除的数据:");
scanf("%d", &data);
del = del_node(head, data);
if(del != NULL)
{
free(del);
printf("节点删除完成\n");
}
break;
//显示数据
case 'p':
display(head);
break;
//节点移动头插
case 'n':
move_front(head);
break;
//节点移动尾插
case 'm':
move_behind(head);
break;
//销毁双向链表
case 't':
destroy(head);
break;
default:
printf("输入格式有误,请重新输入!\n");
break;
}
//去除缓冲区的空格
while (getchar() != '\n');
}
return 0;
}
//初始化,一个新的结构体节点生成
node *initList(void)
{
//在堆空间里面开辟新的内存
node *new = malloc(sizeof(node));
//判断是否开辟成功,开辟失败后返回提示
if(new == NULL)
{
printf("malloc fail\n");
return NULL;
}
//开辟的空间数据初始化为0
new->data = 0;
//双向循环链表,单个节点也是循环链表
new->next = new;
new->prev = new;
return new;
}
// 将新节点插入到链表的首部
void insertHead_1(node *head, node *new)
{
new->next = head->next;
head->next->prev = new;
new->prev = head;
head->next = new;
}
// 将新节点插入到链表的尾部
void insertHead_2(node *head, node *new)
{
new->prev = head->prev;
head->prev->next = new;
head->prev = new;
new->next = head;
}
//查找数据,数据存在返回数据所在的节点地址
node *find_data(node *head, int data)
{
node *p = NULL;
for(p = head->next; p != head ; p = p->next)
{
//判断节点的数据是否等于 查看的数据,如果是,返回节点
if(p->data == data)
{
return p;
}
}
return NULL;
}
//节点删除
node *del_node(node *head, int data)
{
node *del;
del = find_data(head, data);
if(del == NULL)
{
printf("链表当中没有此数据节点\n");
return NULL;
}
//将点解下来
del->next->prev = del->prev;
del->prev->next = del->next;
//把解下来的节点前后都指向自己
del->next=del;
del->prev=del;
return del;
}
//打印数据
void display(node *head)
{
node *p;
for(p = head->next; p != head; p=p->next)
{
printf("%d\t", p->data);
}
printf("\n");
}
//移动数据头插
void move_front(node *head)
{
int data1, data2;
node *move, *basic;
printf("请输入数据要插入哪个前面:");
scanf("%d", &data1);
move=find_data(head,data1);
if (move==NULL)
{
printf("找不到该数据");
return;
}
printf("请输入需要移动的数据:");
scanf("%d", &data2);
basic=del_node(head,data2);
if (move==NULL)
{
printf("找不到该数据");
return;
}
insertHead_2(move,basic);
printf("插入成功");
return;
}
//移动数据尾插
void move_behind(node *head)
{
int data1, data2;
node *move, *basic;
printf("请输入数据要插入哪个后面:");
scanf("%d", &data1);
move=find_data(head,data1);
if (move==NULL)
{
printf("找不到该数据");
return;
}
printf("请输入需要移动的数据:");
scanf("%d", &data2);
basic=del_node(head,data2);
if (move==NULL)
{
printf("找不到该数据");
return;
}
insertHead_1(move,basic);
printf("插入成功");
return;
}
//双向链表的销毁
void destroy(node *head)
{
node *p=head->next;
while(p!=head)
{
node *pp=p;
p=p->next;
free(pp);
}
head->next=head;
head->prev=head;
printf("已经成功摧毁\n");
}