网站推广入口百度开户资质
目录
链表的分类
双向链表的实现
1）定义链表
2）初始化双向链表
3）申请节点
4）尾插
5）头插
6）打印链表
7）尾删
8）头插
9）查找
10）指定位置删除
11）在指定位置后删除
12）销毁链表
链表的分类
根据链表的三个特点（带头/不带头，单向/双向，循环/不循环），可以将链表分为8种。常见的有两种：单链表（单向不带头不循环链表），双链表（双向带头循环链表）。是否带头指的是有没有头节点。链表（全网最详细）-CSDN博客。单链表已经写过了，此处我们将双链表。
双向链表的实现
1）定义链表
typedef int SLDateType;//定义双向链表
typedef struct ListNode
{SLDateType date; //节点中的邮箱有效数据struct ListNode* next; //保存下一个节点地址struct ListNode* prev; //保存上一个节点的有效地址
}LN;2）初始化双向链表
双链表的初始化，主要是创建头节点，即哨兵位。
//双链表的初始化
void List_start(LN** head)
{*head = (LN*)malloc(sizeof(LN));(*head)->date = -1;//给哨兵位一个数据，但是它其实是无效数据//注意因为是循环链表，所以当只有一个哨兵位的时候，要让它指向它自己；(*head)->next = (*head)->prev = (*head);
}3）申请节点
//申请节点
LN* ListBuyNode(SLDateType x)
{LN* newnode = (LN*)malloc(sizeof(LN));newnode->date = x;//因为是双向循环链表，永远不会走到空，所以将新节点也指向其自己newnode->next = newnode->prev = newnode;return newnode;
}4）尾插
注意：除了双向链表的初始化以及销毁要传二级指针，其他函数均采用一级指针，因为哨兵位在被定义后就不能再对他进行修改了。
//双向链表的尾插
void SLpushback(LN* head, SLDateType x)
{LN* newnode = ListBuyNode(x);//对头节点head，尾节点head->prev，新节点newnodenewnode->next = head;newnode->prev = head->prev;head->prev->next = newnode;head->prev = newnode;
}5）头插
头插是指查到烧饼位的后面。
//双向链表的头插
void SLpushfront(LN* head, SLDateType x)
{LN* newnode = ListBuyNode(x);//对head newnode head->next进行修改newnode->next = head->next;newnode->prev = head;head->next->prev = newnode;head->next = newnode;
}6）打印链表
//打印双向链表
void SLPrint(LN* head)
{LN* pcur = head->next;while (pcur != head){printf("%d ", pcur->date);pcur = pcur->next;}
}7）尾删
//双链表尾删
void SLDelback(LN* head)
{//对head head->prev head->prev->prevLN* del = head->prev;head->prev = del->prev;del->prev->next = head;free(del);del = NULL;
}8）头插
//双链表的头插
void SLDelfront(LN* head)
{//对head head->next head->next->next进行调整LN* del = head->next;head->next = del->next;del->next->prev = head;
}9）查找
找双向链表中查找数据，并返回节点；
//双链表的查找
LN* SLFind(LN* head,SLDateType x)
{LN* pcur = head->next;while (pcur != head){if (pcur->date == x)return pcur;pcur = pcur->next;}return NULL;
}10）指定位置删除
//指定位置删除
void SLDEL(LN* head, LN* pos)
{//删除pos节点//对pos->prev pos pos->next进行操作pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}11）在指定位置后删除
//在指定位置后插入
void LInsert(LN* pos, SLDateType x)
{LN* newnode = ListBuyNode(x);//对pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}12）销毁链表
//销毁链表
void LDestory(LN** head)
{//循环删除节点LN* pcur = (*head);while (pcur != *head){LN* next = pcur->next;free(pcur);pcur = next;}free(*head);*head = NULL;
}