我要评论
双向循环链表
前言：虽然笔试常考无头单链表，但是实际上存储数据时，常用带头双向循环链表。这带头双向循环链表相比于无头单链表，不仅在存储数据时更为高效，而且在插入、删除等操作中也表现出更优的性能。
一.带头双向循环链表与无头单向非循环链表的区别
无头单向非循环链表（简称：单链表）：
- 结构简单，一般
不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。 - 另外这种结构在
笔试面试中出现很多。尾删，插入与删除，由于需要从头开始找前一个节点，时间复杂度为o(n)，效率较低。
带头双向循环链表（简称：双向链表）：
- 结构最复杂，一般用在单独
存储数据。实际中使用的链表数据结构，都是带头双向循环链表。 - 另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
- 带头节点，不需要改变传过来的指针，也就意味着
不需要传二级指针。 - 带哨兵位的头节点不存储有效数据。若存储链表的长度，当节点中的数据类型是char时，最大只能为255这是不合理的。
- 查找数据时，时间复杂度为o(n)，一般不用这个，而用
平衡搜索树（avl树，红黑树），哈希表，b树，b+树系列，跳表，布隆过滤器，位图。
二.顺序表和双向链表的优缺点分析
三.带头双向循环链表实现
1.创建双链表
双链表由节点组成，每个节点要存放数据，上一个节点的地址与下一个节点的地址。
双链表：指向该节点的指针。
typedef int ltdatatype; //增强程序的可维护性
typedef struct listnode
{
ltdatatype data; //数据域
struct listnode* next; //前驱指针
struct listnode* prev; //后继指针
}listnode;
listnode* plist;//双链表
2.初始化双链表
将双链表初始化为带哨兵位的头节点，并实现循环结构。
listnode* listinit()
{
//创建头节点
listnode* phead = buynode(0);
//实现循环结构
phead->next = phead;
phead->prev = phead;
return phead;//返回节点指针
}
3.购买节点
由于头插，尾插，按位置插入链表，都要先准备一个节点。为了减少代码的重复，直接对其进行封装，创建新节点的时候直接调用该接口就行。
listnode* buynode(ltdatatype x)
{
//开辟节点空间
listnode* newnode = (listnode*)malloc(sizeof(listnode));
//开辟失败
if (newnode == null)
{
perror("malloc fail!");
exit(1);
}
//开辟成功后初始化节点
newnode->data = x;
newnode->next = null;
newnode->prev = null;
return newnode;
}
4.打印双链表
定义一个指针指向双链表头节点的下一个节点，利用尾节点的next指向头节点这一结束条件，循环遍历打印即可，较为简单。
void listprint(listnode* phead)
{
assert(phead); //断言
//定位链表实际的第一个节点
listnode* cur = phead->next;
while (cur != phead)
{
printf("%d——>", cur->data);
cur = cur->next;
}
printf("null\n");
}
5.插入操作
1.头插
头插思想：在头节点与第一个存储数据的节点之间插入，修改4个指针的指向即可。
void listpushfront(listnode* phead, ltdatatype x)
{
assert(phead);//断言
listnode* newnode = buynode(x); //购买节点
listnode* first = phead->next; //找到实际的第一个节点
//实现头插
newnode->next = first;
first->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
//等价于：listinsert(phead->next, x);
}
2.尾插
尾插思想：定位尾节点，在尾节点后面插入，修改4个指针的指向即可。
void listpushback(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* newnode = buynode(x); //购买节点
listnode* tail = phead->prev; //定位尾节点
//实现尾插
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//等价于：listinsert(phead, x);
}
3.给定位置之前插入
在双链表中插入思路其实都大差不差，而不需考虑单链表时的各种情况，所以说实现较为简单。
void listinsert(listnode* pos, ltdatatype x)
{
assert(pos);
listnode* newnode = buynode(x); //购买节点
listnode* prev = pos->prev; //定位pos前一个节点
//实现插入
newnode->next = pos;
pos->prev = newnode;
prev->next = newnode;
newnode->prev = prev;
}
6.删除操作
删除操作不用分情况，也较为简单，这么一看带头双向循环链表还是非常完美的。
1.头删
void listpopfront(listnode* phead)
{
assert(phead);
assert(phead->next != phead); //当链表中没有为空时，不能头删，否则会将头节点删除！
//实现头删
listnode* first = phead->next; //定位第一个节点
listnode* second = first->next; //定位第二个节点
phead->next = second;
second->prev = phead;
free(first); //释放，防止内存泄漏
first = null; //置空，防止野指针
//等价于：listerase(phead->next);
}
2.尾删
void listpopback(listnode* phead)
{
assert(phead);
assert(phead->next != phead); //当链表中没有为空时，不能尾删，否则会将头节点删除！
//实现尾删
listnode* tail = phead->prev; //定位尾节点
listnode* prev = tail->prev; //定位尾节点前一个节点
prev->next = phead;
phead->prev = prev;
free(tail);
tail = null;
//等价于：listerase(phead->prev);
}
3.删除给定位置的结点
void listerase(listnode* pos)
{
assert(pos);
//实现删除
listnode* prev = pos->prev; //定位pos的前一个节点
listnode* next = pos->next; //定位pos的后一个节点
prev->next = next;
next->prev = prev;
free(pos);
pos = null;
}
7.查找数据
思路：循环遍历双链表即可，找到返回地址，未找到返回null。
listnode* listfind(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* cur = phead->next; //定位第一个节点
while (cur != phead)
{
if (cur->data == x) //找到了，返回cur
{
return cur;
}
cur = cur->next;
}
return null; //未找到，返回null
}
8.修改数据
思路：直接通过listfind函数得到地址，在该处修改即可，较为简单，同时listerase与listinsert函数都要通过listfind函数得到地址。
void listmodify(listnode* pos, ltdatatype x)
{
assert(pos);
pos->data = x;//直接修改即可
}
9.求双链表长度
int listlength(listnode* phead)
{
assert(phead);
int len = 0;
listnode* cur = phead->next; //定位第一个节点
while (cur != phead)
{
cur = cur->next;
len++;
}
return len;
}
10.清空双链表
注意：逐个节点释放，不能释放头节点，为了能找到下一个节点，要用指针保存，最后还原为循环结构。
void clear(listnode* phead)
{
assert(phead);
//实现清空
listnode* cur = phead->next; //定位第一个节点
listnode* next = cur; //辅助删除节点的指针
while (cur != phead)
{
next = next->next;
free(cur);
cur = next;
}
//注意：还原循环结构
phead->next = phead;
phead->prev = phead;
}
11.销毁双链表
先调用clear函数，在释放头节点即可。
void destory(listnode* phead)
{
assert(phead);
//先清空，再销毁phead
clear(phead);
free(phead);
phead = null;
}
四.模块化源代码
1.doublelinklist.h
//#pragma once 防止头文件被重复包含
#ifndef __doublecircularlinklist_h__
#define __doublecircularlinklist_h__
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int ltdatatype; //增强程序的可维护性
typedef struct listnode
{
ltdatatype data; //数据域
struct listnode* next; //前驱指针
struct listnode* prev; //后继指针
}listnode;
listnode* buynode(ltdatatype x);//购买节点
listnode* listinit();//初始化链表
void listprint(listnode* phead);//打印链表
void listpushback(listnode* phead, ltdatatype x);//尾插
void listpushfront(listnode* phead, ltdatatype x);//头插
void listpopback(listnode* phead);//尾删
void listpopfront(listnode* phead);//头删
listnode* listfind(listnode* phead, ltdatatype x);//查找链表中的x值，返回节点的地址
void listinsert(listnode* pos, ltdatatype x);//利用listfind函数找到pos，在pos前，插入x
void listerase(listnode* pos);//利用listfind函数找到pos，删除pos节点
void listmodify(listnode* pos, ltdatatype x);//将pos位置的数据修改为x
int listlength(listnode* phead);//求链表的长度
void clear(listnode* phead);//清空链表
void destory(listnode* phead);//销毁链表
#endif
2.doublelinklist.c
#define _crt_secure_no_warnings 1
#include"doublecircularlinklist.h"
listnode* buynode(ltdatatype x)
{
//开辟节点空间
listnode* newnode = (listnode*)malloc(sizeof(listnode));
//开辟失败
if (newnode == null)
{
perror("malloc fail!");
exit(1);
}
//开辟成功后初始化节点
newnode->data = x;
newnode->next = null;
newnode->prev = null;
return newnode;
}
listnode* listinit()
{
//创建头节点
listnode* phead = buynode(0);
//实现循环结构
phead->next = phead;
phead->prev = phead;
return phead;
}
void listprint(listnode* phead)
{
assert(phead); //断言
//定位链表实际的第一个节点
listnode* cur = phead->next;
while (cur != phead)
{
printf("%d——>", cur->data);
cur = cur->next;
}
printf("null\n");
}
void listpushback(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* newnode = buynode(x); //购买节点
listnode* tail = phead->prev; //定位尾节点
//实现尾插
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
//等价于：listinsert(phead, x);
}
void listpushfront(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* newnode = buynode(x); //购买节点
listnode* first = phead->next; //找到实际的第一个节点
//实现头插
newnode->next = first;
first->prev = newnode;
newnode->prev = phead;
phead->next = newnode;
//等价于：listinsert(phead->next, x);
}
void listpopback(listnode* phead)
{
assert(phead);
assert(phead->next != phead); //当链表中没有为空时，不能尾删，否则会将头节点删除！
//实现尾删
listnode* tail = phead->prev; //定位尾节点
listnode* prev = tail->prev; //定位尾节点前一个节点
prev->next = phead;
phead->prev = prev;
free(tail); //释放，防止内存泄漏
tail = null; //置空，防止野指针
//等价于：listerase(phead->prev);
}
void listpopfront(listnode* phead)
{
assert(phead);
assert(phead->next != phead); //当链表中没有为空时，不能头删，否则会将头节点删除！
//实现头删
listnode* first = phead->next; //定位第一个节点
listnode* second = first->next; //定位第二个节点
phead->next = second;
second->prev = phead;
free(first);
first = null;
//等价于：listerase(phead->next);
}
listnode* listfind(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* cur = phead->next; //定位第一个节点
while (cur != phead)
{
if (cur->data == x) //找到了，返回cur
{
return cur;
}
cur = cur->next;
}
return null; //未找到，返回null
}
void listinsert(listnode* pos, ltdatatype x)
{
assert(pos);
listnode* newnode = buynode(x); //购买节点
listnode* prev = pos->prev; //定位pos前一个节点
//实现插入
newnode->next = pos;
pos->prev = newnode;
prev->next = newnode;
newnode->prev = prev;
}
void listerase(listnode* pos)
{
assert(pos);
//实现删除
listnode* prev = pos->prev; //定位pos的前一个节点
listnode* next = pos->next; //定位pos的后一个节点
prev->next = next;
next->prev = prev;
free(pos);
pos = null;
}
void listmodify(listnode* pos, ltdatatype x)
{
assert(pos);
pos->data = x;//直接修改即可
}
int listlength(listnode* phead)
{
assert(phead);
int len = 0;
listnode* cur = phead->next; //定位第一个节点
while (cur != phead)
{
cur = cur->next;
len++;
}
return len;
}
void clear(listnode* phead)
{
assert(phead);
//实现清空
listnode* cur = phead->next; //定位第一个节点
listnode* next = cur; //辅助删除节点的指针
while (cur != phead)
{
next = next->next;
free(cur);
cur = next;
}
//注意：还原循环结构
phead->next = phead;
phead->prev = phead;
}
void destory(listnode* phead)
{
assert(phead);
//先清空，再销毁phead
clear(phead);
free(phead);
phead = null;
}
3.test.c
#define _crt_secure_no_warnings 1
#include"doublecircularlinklist.h"
enum //匿名枚举
{
exit,
pushback,
pushfront,
popback,
popfront,
insert,
erase,
find,
modify,
print,
length,
clear
};
void menu()
{
printf("**********双向循环链表*********\n");
printf("****1.尾插 2.头插****\n");
printf("****3.尾删 4.头删****\n");
printf("****5.插入 6.删除****\n");
printf("****7.查找 8.修改****\n");
printf("****9.打印 10.长度****\n");
printf("***11.清空 0.退出****\n");
printf("*******************************\n");
}
int main()
{
listnode* plist = null;
plist = listinit();
int select = 0;
ltdatatype value;
ltdatatype value1;
listnode* pos = null; //记录节点的地址
do
{
menu();
printf("请输入您的操作：");
scanf("%d", &select);
switch (select)
{
case exit:
printf("退出双向循环链表!\n");
break;
case pushback:
printf("请输入要尾插的值（以-1结束）：");
while ((scanf("%d", &value), value != -1))
{
listpushback(plist, value);
}
break;
case pushfront:
printf("请输入要头插的值（以-1结束）：");
do
{
scanf("%d", &value);
if (value != -1)
{
listpushfront(plist, value);
}
} while (value != -1);
break;
case print:
listprint(plist);
break;
case popback:
listpopback(plist);
break;
case popfront:
listpopfront(plist);
case find:
printf("请输入您要查找的值：");
scanf("%d", &value);
pos = listfind(plist, value);
if (pos != null)
{
printf("存在!\n");
}
else
{
printf("不存在!\n");
}
break;
case insert:
printf("请输入您要插入到《何值前面》以及《插入的值》：");
scanf("%d %d", &value1, &value);
pos = listfind(plist, value1);
if (pos != null)
{
listinsert(pos, value);
}
else
{
printf("该值不存在，无法插入!\n");
}
break;
case erase:
printf("请输入您要删除的值：");
scanf("%d", &value);
pos = listfind(plist, value);
if (pos != null)
{
listerase(pos);
}
else
{
printf("该值不存在，无法删除!\n");
}
break;
case modify:
printf("请输入您要《要修改的值》以及《修改后的值》：");
scanf("%d %d", &value1, &value);
pos = listfind(plist, value1);
if (pos != null)
{
listmodify(pos, value);
}
else
{
printf("该值不存在，无法修改!\n");
}
break;
case length:
printf("链表的长度：%d\n", listlength(plist));
break;
case clear:
clear(plist);
break;
default:
printf("输入错误，请重新输入!\n");
break;
}
} while (select);
destory(plist);
return 0;
}
五.链表必做oj题
创作不易，如果能帮到你的话能赏个三连吗？感谢啦！！！
发表评论