我要评论双链表的概念和结构
双链表的全称叫做：带头双向循环链表
它的结构示意图如下
注意：这⾥的“带头”跟前⾯我们说的单链表的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了读者们更好的理解就直接称为单链表的头结点。
带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”也可以认为是用来占位置滴！！！
双链表的实现
首先先在结构体当中输入需要的数据，则有如下的数据是需要的
结构体中的数据
typedef int ltdatatype;//方便对数据类型进行统一的替换
typedef struct listnode listnode;//对结构体的名称重新命名交listnode
struct listnode
{
ltdatatype data;
listnode* next;
listnode* prev;
};
则上面的图可以变成这样
双链表新结点的创建及双链表的初始化
listnode* ltbuynode(ltdatatype x)
{
listnode* newnode = (listnode*)malloc(sizeof(listnode));//一个结构体的大小
if (newnode == null)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;//返回头结点
}链表的初始化需要一个创建的新的结点作为哨兵位
//void ltinit(listnode** pphead)
//{
// //创建一个头结点即“哨兵位”
// *pphead = ltbuynode(-1);
//}
listnode* ltinit()
{
listnode* phead = ltbuynode(-1);
return phead;
}
//上面是两种初始化的方法
//第一种需要传递一个二级指针
在上面的代码当中，我们只需要创建一个头结点来保证第一个“头”存在即可。
双链表的尾插
//尾插
void ltpushback(listnode* phead, ltdatatype x)
{
assert(phead);
//创建需要插入的结点
//上面初始化的newnode是头结点，这个newnode是尾插的结点
listnode* newnode = ltbuynode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
这边测试一下我们的尾插代码依次插入1 2 3 4
双链表的头插
//头插
void ltpushfront(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* newnode = ltbuynode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}头插和尾插是类似的 ，不过有一个特殊的地方
头插是头插在哨兵位和第一个真正的结点中间
测试头插代码
这个代码是在上面尾插代码基础上的操作
双链表的尾删
//尾删
void ltpopback(listnode* phead)
{
assert(phead);
assert(!empty(phead));
listnode* del = phead->prev;
listnode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = null;
}
这边仍然是在尾插的基础上的操作
这边我们进行了五次尾删，所以代码assert断言了！
将一次尾删注释，下面就是尾删的效果
双链表的头删
//头删
void ltpopfront(listnode* phead)
{
assert(phead);
assert(!empty(phead));
listnode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = null;
}
这个仍然是在尾插的基础上操作的，如果继续删除，跟上面的情况一样assert断言报错
以上就是最基础的增删 ，下面开始加大难度！
双链表中查找数据pos
//找相同数据
listnode* ltfind(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return null;
}
这边我们查找的是数据3，所以我们可以找到
这个在链表中没有数据6，所以我们没有找到相关的数据
在pos之后插入结点
这个和尾插以及头插其实是类似的，这里主要是寻找到pos结点，然后插入想要的数据
//在pos之后插入结点
void ltinsert(listnode* pos, ltdatatype x)
{
assert(pos);
listnode* newnode = ltbuynode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}在3的后面插入数据10
删除pos结点
//删除指定位置节点
void lterase(listnode* pos)
{
assert(pos);
// pos->prev pos pos->next
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = null;
}
双链表的销毁
这里我们提供了两种的销毁方法，两种方法基本是类似的
//销毁
void ltdestroy(listnode** pphead)
{
assert(pphead && *pphead);
listnode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
listnode* next = pcur->next;
free(pcur);
pcur = next;
}
//销毁哨兵位结点
free(*pphead);
*pphead = null;
pcur = null;
}
//为了更好的记忆，我们让销毁也传递一级指针
void ltdestroy2(listnode* phead)//传一级，需要手动将plist置为null
{
assert(phead);
listnode* pcur = phead->next;
while (pcur != phead)
{
listnode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = pcur = null;
}最后我们将双向链表的源码附上
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int ltdatatype;
typedef struct listnode listnode;
struct listnode
{
ltdatatype data;
listnode* next;
listnode* prev;
};
listnode* ltbuynode(ltdatatype x);
//为了保存接口的一致性
//
//初始化
//void ltinit(listnode** pphead);
listnode* ltinit();
//
void ltprint(listnode* phead);
bool empty(listnode* phead);
//插入
//第一个参数传一级还是二级，要看phead指向的结点会不会改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级
//尾插
void ltpushback(listnode* phead, ltdatatype x);
//头插
void ltpushfront(listnode* phead, ltdatatype x);
//尾删
void ltpopback(listnode* phead);
//头删
void ltpopfront(listnode* phead);
//在pos之后插入结点
void ltinsert(listnode* pos, ltdatatype x);
//删除指定位置的结点
void lterase(listnode* pos);
//找数据
listnode* ltfind(listnode* phead, ltdatatype x);
//销毁
void ltdestroy(listnode** pphead);
void ltdestroy2(listnode* phead);//传一级，需要手动将plist置为null#include"list.h"
listnode* ltbuynode(ltdatatype x)
{
listnode* newnode = (listnode*)malloc(sizeof(listnode));
if (newnode == null)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
//初始化
//void ltinit(listnode** pphead)
//{
// //创建一个头结点即“哨兵位”
// *pphead = ltbuynode(-1);
//}
listnode* ltinit()
{
listnode* phead = ltbuynode(-1);
return phead;
}
//打印
void ltprint(listnode* phead)
{
listnode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
bool empty(listnode* phead)
{
assert(phead);
return phead->next == phead;
}
//尾插
void ltpushback(listnode* phead, ltdatatype x)
{
assert(phead);
//创建需要插入的结点
listnode* newnode = ltbuynode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
//头插
void ltpushfront(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* newnode = ltbuynode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//尾删
void ltpopback(listnode* phead)
{
assert(phead);
assert(!empty(phead));
listnode* del = phead->prev;
listnode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = null;
}
//头删
void ltpopfront(listnode* phead)
{
assert(phead);
assert(!empty(phead));
listnode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = null;
}
//找相同数据
listnode* ltfind(listnode* phead, ltdatatype x)
{
assert(phead);
listnode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return null;
}
//在pos之后插入结点
void ltinsert(listnode* pos, ltdatatype x)
{
assert(pos);
listnode* newnode = ltbuynode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
//删除指定位置节点
void lterase(listnode* pos)
{
assert(pos);
// pos->prev pos pos->next
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
pos = null;
}
//销毁
void ltdestroy(listnode** pphead)
{
assert(pphead && *pphead);
listnode* pcur = (*pphead)->next;
while (pcur != *pphead)
{
listnode* next = pcur->next;
free(pcur);
pcur = next;
}
//销毁哨兵位结点
free(*pphead);
*pphead = null;
pcur = null;
}
void ltdestroy2(listnode* phead)
{
assert(phead);
listnode* pcur = phead->next;
while (pcur != phead)
{
listnode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = pcur = null;
}
#include"list.h"
void test()
{
创建双向链表变量
//listnode* plist = null;
//ltinit(&plist);
listnode* plist = ltinit();
ltpushback(plist, 1);
ltpushback(plist, 2);
ltpushback(plist, 3);
ltpushback(plist, 4);
ltprint(plist);
listnode* pos = ltfind(plist, 3);
ltinsert(pos, 10);
ltprint(plist);
pos = ltfind(plist, 3);
lterase(pos);
ltprint(plist);
/*ltpopfront(plist);
ltprint(plist);
ltpopfront(plist);
ltprint(plist);
ltpopfront(plist);
ltprint(plist);
ltpopfront(plist);
ltprint(plist);*/
/*ltpushfront(plist, 1);
ltprint(plist);
ltpushfront(plist, 2);
ltprint(plist);
ltpushfront(plist, 3);
ltprint(plist);
ltpushfront(plist, 4);
ltprint(plist);*/
/*ltpopback(plist);
ltprint(plist);
ltpopback(plist);
ltprint(plist);
ltpopback(plist);
ltprint(plist);
ltpopback(plist);
ltprint(plist);
ltpopback(plist);
ltprint(plist);*/
/*if (pos == null)
{
printf("没有找到\n");
}
else
{
printf("找到了\n");
}*/
ltdestroy(&plist);
//ltdestroy2(plist);
//plist = null;
}
int main()
{
test();
return 0;
}
发表评论