1.双向链表
1.1概念与结构
注意：这里的“带头”跟前⾯我们说的“头结点”是两个概念，实际前面的在单链表阶段称呼不严
谨，但是为了更好的理解就直接称为单链表的头结点。
带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨
的。
1.2 实现双向链表
在这里，由于双链表和单链表的基本逻辑是一样的，我将只保留重要部分的注释，详情逻辑请参考单链表！
和之前一样，我们还是创建三个文件。
这是list.h文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int ltdatatype;
//定义双向链表结构
typedef struct listnode
{ltdatatype data;struct listnode* next;struct listnode* prev;
}ltnode;
//初始化
ltnode* ltinit();
//尾插
void ltpushback(ltnode* phead, ltdatatype x);
//头插
void ltpushfront(ltnode* phead, ltdatatype);
//尾删
void ltpopback(ltnode* phead);
//头删
void ltpopfront(ltnode* pead);
//查找
ltnode* ltfind(ltnode* phead, ltdatatype x);
//在pos位置之后插入数据
void ltinsert(ltnode* pos, ltdatatype);
//在pos位置之前插入数据
void ltinsertbefore(ltnode* pos, ltdatatype x);
//删除pos结点
void lterase(ltnode* pos);
//打印
void ltprint(ltnode* phead);
//销毁
void ltdestroy(ltnode* phead);这是list.c文件
#include"list.h"
//申请结点
ltnode* ltbuynode(ltdatatype x)
{ltnode* node = (ltnode*)malloc(sizeof(ltnode));assert(node);node->data = x;node->next = node->prev = node; return node;//由于我们创建的是双向循环链表，故不可置为NULL，要让结点自己转起来。
}
//初始化
ltnode* ltinit()
{ltnode* phead = ltbuynode(-1);return phead;
}
//打印
void ltprint(ltnode* phead)
{//由于链表是循环的，而恰好Head里面没有有效数据，故让pcur从head->next开始遍历，直到head为止ltnode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}
//尾插 (插入小技巧：先对要插入的结点进行操作，要尽可能减小对原链表的影响）
void ltpushback(ltnode* phead, ltdatatype x)
{assert(phead);ltnode* newnode = ltbuynode(x);newnode->next = phead;newnode->prev = phead->prev; //由于链表是循环的，尾结点就是Phead的前一个结点，可以看一下例图phead->prev->next = newnode;phead->prev = newnode;
}
//头插(插在哨兵位结点之后，插在哨兵位结点之前叫尾插）
void ltpushfront(ltnode* phead, ltdatatype x)
{assert(phead);ltnode* newnode = ltbuynode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
//尾删 （删除小技巧：把所有指向删除节点的箭头干掉，然后frree））
void ltpopback(ltnode* phead)
{assert(phead && phead->next != phead);ltnode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}
//头删
void ltpopfront(ltnode* phead)
{assert(phead && phead->next != phead);ltnode* del = phead->next;phead->next = del->next;phead->prev->prev = phead;free(del);del = NULL;
}//查找
ltnode* ltfind(ltnode* phead, ltdatatype x)
{ltnode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//在pos位置之后插入数据
void ltinsert(ltnode* pos, ltdatatype x)
{assert(pos);ltnode* newnode = ltbuynode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}
//删除Pos结点
void lterase(ltnode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
//在pos位置之前插入数据
void ltinsertbefore(ltnode* pos, ltdatatype x)
{assert(pos);ltnode* newnode = ltbuynode(x);newnode->next = pos;newnode->prev = pos->prev;pos->prev->next = newnode;pos->prev = newnode;
}
//销毁
void ltdestroy(ltnode* phead)
{assert(phead);ltnode* pcur = phead->next;while (pcur != phead){ltnode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}这是Test.c文件
#include"list.h"
void listtest()
{ltnode* plist = ltinit();//尾插ltpushback(plist, 1);ltprint(plist);ltpushback(plist, 2);ltprint(plist);ltpushback(plist, 3);ltprint(plist);ltpushback(plist, 4);ltprint(plist);//头插ltpushfront(plist, 4);ltprint(plist);ltpushfront(plist, 3);ltprint(plist);ltpushfront(plist, 2);ltprint(plist);ltpushfront(plist, 1);ltprint(plist);//尾删ltpopback(plist);ltprint(plist);ltpopback(plist);ltprint(plist);//头删ltpopfront(plist);ltprint(plist);ltpopfront(plist);ltprint(plist);//查找ltnode* find = ltfind(plist, 4);if (find == NULL){printf("没找到！\n");}else{printf("找到了\n");}//在pos位置之后插入数据ltinsert(find, 5);ltprint(plist);//删除Pos结点lterase(find); //函数执行后，find会被释放掉ltprint(plist);//在pos位置之前插入数据ltnode* find1 = ltfind(plist, 5); //由于此处的find已经被释放掉了，故需要重新定义一下ltinsertbefore(find1, 6); ltprint(plist);//销毁ltdestroy(plist);
}
int main()
{listtest();return 0;
}
