【数据结构篇】~双向链表（附源码）

前言

学完了单链表，还有其他等着我们去攻克，链表其实分为8种
，共2 * 2 * 2=8种

在这里插入图片描述

之前的单链表是不带头单向不循环链表

一、双向链表

在这里插入图片描述
注意：这里的“带头”跟前面我们说的“头结点”是两个概念，实际前面的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里“放哨
的”
在这里插入图片描述

1.头文件

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int listdatatype;
//双向链表节点(数据、前驱节点、next)
typedef struct listnode {listdatatype data;struct listnode* prev;struct listnode* next;
}lsnode;
void printlist(lsnode* phead);//打印双链表
lsnode* buylistnode(listdatatype x);//创建节点
lsnode* lsinit();//初始化
bool lsempty(lsnode* phead);//判断链表是否为空
void lspushback(lsnode* phead, listdatatype x);//尾插
void lspopback(lsnode* phead);//尾删
void lspushfront(lsnode* phead, listdatatype x);//头插
void lspopfront(lsnode* phead);//头删
//在pos位置之后插入数据
void lsinsert(lsnode* pos, listdatatype x);
void lserase(lsnode* pos);//删除pos处数据
lsnode* lsfind(lsnode* phead, listdatatype x);//查找数据
void lsdestroy(lsnode* phead);//销毁

2.源文件

#include "list.h"
//phead是哨兵位
//双向链表为空：只有个哨兵位
//创建节点
lsnode* buylistnode(x)
{lsnode* newnode = (lsnode*)malloc(sizeof(lsnode));if (newnode == NULL){perror("malloc fail");return 1;}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;
}
lsnode* lsinit()//初始化
{lsnode* phead = buylistnode(-1);return phead;
}
void printlist(lsnode* phead)//打印链表
{lsnode* purc = phead->next;while (purc != phead){printf("%d->",purc->data);purc = purc->next;}printf("\n");
}
void lspushback(lsnode* phead, listdatatype x)//尾插
{//尾插要修改的指针有// （ phead->prev,（原链表的最后一个节点）（phead->prev）的next  ）assert(phead);lsnode* newnode = buylistnode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}
void lspushfront(lsnode* phead, listdatatype x)//头插
{assert(phead);lsnode* newnode = buylistnode(x);//phead->next(第一个节点)newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}
//删除时链表都不能为空
bool lsempty(lsnode* phead)//判断链表是否为空
{assert(phead);return phead->next == phead;//返回true则就是空链表
}
void lspopback(lsnode* phead)//尾删（双向链表不能为空链表）
{assert(phead);assert(!lsempty(phead));phead->prev->prev->next = phead;phead->prev = phead->prev->prev;
}
void lspopfront(lsnode* phead)//头删
{assert(phead);assert(!lsempty(phead));phead->next->next->prev = phead;phead->next = phead->next->next;
}
lsnode* lsfind(lsnode* phead, listdatatype x)//查找数据
{assert(phead);lsnode* purc = phead->next;while (purc != phead){if (purc->data == x){return purc;}purc = purc->next;}return NULL;
}
void lsinsert(lsnode* pos, listdatatype x)//在pos位置之后插入数据
{lsnode* newnode = buylistnode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}
void lserase(lsnode* pos)//删除pos处数据
{assert(pos);lsnode* del = pos;del->next->prev = del->prev;del->prev->next = pos->next;free(pos);pos = NULL;
}
void lsdestroy(lsnode** pphead)//销毁(传二级指针)
{assert(pphead && *pphead);lsnode* purc = (*pphead)->next;while (purc != *pphead){lsnode* Next = purc->next;free(purc);purc = Next;}free(*pphead);*pphead =purc = NULL;
}