我要评论目录
关于链表的分类
根据链表的三大特性，单向or双向、带头or不带头、循环or不循环，可将链表分为2*2*2，8种链表，前面我们已经实现了单链表，即：不带头单向非循环链表，它的结构简单，不常用于单独存储数据，而是作为其他数据结构的子结构。
实际运用中，只有单链表（不带头单向非循环链表）和双向链表（带头双向循环链表）运用最多，带头双向循环链表，结构最复杂，常常运用于单独存储数据，使用的链表结构也几乎都是双向带头链表。
附上一张bit课件的图：
双向链表结构体
放一张bi课件的图片很形象：
//重定义一下类型，方便统一修改
typedef int lndatatype;
typedef struct listnode {
lndatatype data;//数据
struct listnode* prev;//前一个结点
struct listnode* next;//后一个结点
}ln;
初始化
双向链表的初始化，应创建一个哨兵结点（也称头结点），它存放的数据是无效数据（假定-1），
所以我们先实现一个创建单节点的函数：
//创建新节点
ln* lnbuynode(lndatatype x) {
ln* node = (ln*)malloc(sizeof(ln));//开辟空间
if (!node) {//判断为空
perror("malloc fail!");
exit(1);
}
node->data = x;//传入数据
node->next = node->prev = node;
//双向循环链表单节点也应满足循环，不能初始化为null;
return node;
}接着我们就可方便地调用，创建一个哨兵结点：
//初始化
void lninit(ln** pphead) {
assert(pphead);
*pphead=lnbuynode(-1);
}尾插
//尾插
void lnpushback(ln* phead, lndatatype x) {
assert(phead);
ln* node = lnbuynode(x);//创建新结点
node->next = phead;//先对新申请的结点参数进行操作，防止对原链表造成改变
node->prev = phead->prev;
phead->prev->next = node;//更改尾结点的next参数的指向
phead->prev = node;//更改头结点prev结点的指向
}运行测试一下：
头插
注意头插的操作是在哨兵位后插入，双向链表为空的情况也是只剩下哨兵位，因为哨兵位并没有存储有效数据。
//头插
void lnpushfront(ln* phead, lndatatype x) {
assert(phead);
ln* node = lnbuynode(x);//创建新结点
node->next = phead->next;//先对新申请的结点参数进行操作，防止对原链表造成改变
node->prev = phead;
phead->next->prev = node;//更改头结点的下一个结点的prev指向
phead->next = node;//更改头结点的next指向
}运行测试一下：
打印
//打印
void lnprint(ln* phead) {
assert(phead);
ln* pcur = phead->next;
//因为头结点内存储的是无效数据，所以我们让它指向下一个结点
while (pcur!=phead) {//与头结点相遇说明我们已经遍历完整个链表了
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}判断是否为空
双向链表为空的情况是只有一个哨兵结点而不是null
//判断是否为空
bool lnempty(ln* phead) {
assert(phead);
return phead->next == phead;
}尾删
//尾删
void lnpopback(ln* phead) {
assert(phead);
assert(!lnempty(phead));//删除操作至少有一个有效数据
//lnemptys是空返回true,取反保证不为空
ln* del = phead->prev;//保存要删除的结点
phead->prev = del->prev;//对要受影响的结点的参数进行更改
phead->prev->next = phead;
free(del);//释放掉该地址
del = null;
}运行测试一下：
头删
//头删
void lnpopfront(ln* phead) {
assert(phead);
assert(!lnempty(phead));
ln* del = phead->next;//保存要删除的结点
phead->next = del->next;//对要受影响的结点的参数进行更改
phead->next->prev = phead;
free(del);//释放掉该地址
del = null;
}运行测试一下：
查找
因为后面涉及到任意位置的操作，所以这里要写一个查找方法：
//查找
ln* lnfind(ln* phead, lndatatype x) {
assert(phead);
assert(!lnempty(phead));
ln* pcur = phead->next;
while (pcur!=phead) {
//判断条件为!=phead,遇到哨兵位说明已经遍历完
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
return null;
}运行测试一下：
指定位置之后的插入
//指定位置之后的插入
void lninsert(ln* pos, lndatatype x) {
assert(pos);
ln* node = lnbuynode(x);
node->next = pos->next;//先对要受影响的结点的参数进行更改
node->prev = pos;
pos->next->prev = node;//更改pos结点的后一个结点的prev参数
pos->next = node;//更改pos结点的next参数
}运行测试一下：
指定位置的删除
//任意位置的删除
void lnerase(ln* pos) {
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = null;
}运行测试一下：
销毁
//销毁
void lndestory(ln** phead) {
assert(phead && *phead);
ln* pcur = (*phead)->next;
while (pcur != *phead) {
ln* next = pcur->next;
free(pcur);
pcur = next;
}
free(*phead);
*phead =pcur= null;
}
发表评论