您现在的位置是:首页 >学无止境 >双向链表(数据结构)(C语言)网站首页学无止境
双向链表(数据结构)(C语言)
目录
关于无头单向非循环链表无需初始化函数,顺序表、带头双向循环链表需要的思考
关于单链表的尾插需要用到二级指针,双向链表不需要用到二级指针的思考
概念
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。我们一般构造双向循环链表。循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其它结点。
带头双向循环链表的实现
前情提示
List.h 用于 引用的头文件、双向链表的定义、函数的声明。
List.c 用于 函数的定义。
Test.c 用于 双向链表功能的测试。
双向链表的结构体定义
在List.h下
#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突
//先将可能使用到的头文件写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;//假设结点的数据域类型为 int
//给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动
//(比如我晚点想存double类型的数据,我就直接将 int 改为 double )
// 带哨兵位双向循环链表的结构体定义
typedef struct ListNode
{
struct ListNode* prev;//前驱指针域:存放上一个结点的地址
struct ListNode* next;//后继指针域:存放下一个结点的地址
LTDataType data;//数据域
}LTNode;
//struct 关键字和 ListNode 一起构成了这个结构类型
//typedef 为这个结构起了一个别名,叫 LTNode,即:typedef struct ListNode LTNode
//现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量
双向链表的初始化
在List.h下
// 双向链表的初始化
// 如果是单链表直接给个空指针就行,不需要单独写一个函数进行初始化
// 即:LTNode* plist = NULL;
// 那为什么顺序表、带头双向循环链表有呢?
// 因为顺序表、带头双向循环链表的结构并不简单,
// 如: 顺序表顺序表为空size要为0,还要看capacity是否要开空间,
// 若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功
// 带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
LTNode* LTInit();
在List.c下
#include"List.h"//别忘了
//动态申请一个结点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)//如果malloc失败
{
perror("malloc fail");
return NULL;
}
//如果malloc成功
//初始化一下,防止野指针,如果看到返回的是空指针,那逻辑可能有些错误
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
// 双向链表的初始化
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);//创建哨兵位
//自己指向自己
phead->next = phead;
phead->prev = phead;
return phead;
}
关于无头单向非循环链表无需初始化函数,顺序表、带头双向循环链表需要的思考
无头单向非循环链表结构太简单了,初始化只需直接赋空指针,无需单独写一个函数进行初始化。
即:LTNode* plist = NULL;
那为什么顺序表、带头双向循环链表有单独写一个函数进行初始化呢?
因为顺序表、带头双向循环链表的结构并不简单。
如:
顺序表顺序表为空size要为0,还要看capacity是否要开空间,若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功。
带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己。
顺序表和双向循环链表的初始化有点复杂,最好构建一个函数。
双向链表在pos位置之前插入x
在List.h下
// 双向链表在pos位置之前进行插入
void LTInsert(LTNode* pos, LTDataType x);
在List.c下
// 双向链表在pos位置之前进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);//pos肯定不为空
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
双向链表的打印
在List.h下
// 双向链表打印
void LTPrint(LTNode* phead);
在List.c下
// 双向链表打印
void LTPrint(LTNode* phead)
{
assert(phead);//有哨兵位
printf("<=>phead<=>");
LTNode* cur = phead->next;//cur指向第一个要打印的结点
while (cur != phead)//cur等于头结点时打印就结束了
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("
");
}
在Test.c下
#include"List.h"//别忘了
//测试函数
void TestList1()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
}
int main()
{
TestList1();
return 0;
}
双链表删除pos位置的结点
在List.h下
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);
在List.c下
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
assert(pos);//pos肯定不为空
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
//这个置空其实已经没有意义了,形参的改变不会改变实参
}
在Test.c下
//测试函数
void TestList1()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTErase(plist->next);
LTPrint(plist);
}
int main()
{
TestList1();
return 0;
}
双向链表的尾插
在List.h下
//双向链表优于单链表的点——不需要找尾、二级指针
//(我们改的不是结构体的指针,改的是结构体的变量)
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
在List.c下
法一:(便于新手更好地理解双向链表的尾插)
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法一:(便于新手更好地理解双向链表的尾插)
//一步就可完成链表为空/不为空的尾插——因为有哨兵位
LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
LTNode* tail = phead->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
法二:函数复用(简单方便)
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法二:函数复用(简单方便)
LTInsert(phead, x);
}
关于单链表的尾插需要用到二级指针,双向链表不需要用到二级指针的思考
单链表改变的是结构体的指针,双向链表改变的是结构体的变量
二级指针和一级指针的区别在于指针所指向变量的层级不同,一级指针指向的是结构体的变量,而二级指针指向的是结构体指针的地址。
单链表中,在进行链表结点的删除或插入操作时,需要更新结点之间的指针指向。若使用一级指针,则操作会直接改变指向结点的指针,很难实现目标。因此需要传递二级指针,让函数能够修改指向结点指针的地址,也就是修改之前结点指针变量存放的地址。
而双向链表中,每个结点除了保存指向下一结点的指针外,还有保存指向上一结点的指针,结点之间的双向指针关系使得结点的插入和删除操作更加方便。双向链表不需要传递二级指针,因为在结点的删除和插入操作中,只需要先修改当前结点前后结点的指针,无需直接改变前后结点指针变量存放的地址。
综上所述,单链表只有指向下一结点的指针,通过传递二级指针来修改结点之间的指针关系,使得操作更加灵活;而双向链表的结点之间有双向指针关系,无需直接改变前后结点指针变量存放的地址,因此只需要传递一级指针即可。
单链表(对比):
在Test.c下
//测试函数
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPushBack(plist, 8);
LTPrint(plist);
}
int main()
{
TestList2();
return 0;
}
双向链表的判空
在尾删/头删之前,我们要先判断链表是否为空。
在List.h下
// 双向链表的判空
bool LTEmpty(LTNode* phead);
在List.c下
// 双向链表的判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)
}
双向链表的尾删
在List.h下
// 双向链表的尾删
void LTPopBack(LTNode* phead);
在List.c下
法一:(便于新手更好地理解双向链表的尾删)
// 双向链表的尾删
void LTPopBack(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法一:(便于新手更好地理解双向链表的尾删)
LTNode* tail = phead->prev;
LTNode* tailPrev = tail->prev;
tailPrev->next = phead;
phead->prev = tailPrev;
free(tail);
tail = NULL;
}
法二:函数复用(简单方便)
// 双向链表的尾删
void LTPopBack(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法二:函数复用
LTErase(phead->prev);
}
在Test.c下
//测试函数
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPushBack(plist, 8);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
}
int main()
{
TestList2();
return 0;
}
双向链表的头插
在List.h下
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);
在List.c下
法一:只用phead和newnode两个指针(便于新手更好地理解双向链表的头插)
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
//法一:只用phead和newnode两个指针(便于新手更好地理解双向链表的头插)
//顺序很重要!!!
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
}
法二:多用了first记录第一个结点的位置(便于新手更好地理解双向链表的头插)
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//哨兵位
LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
//法二:多用了first先记住第一个结点(便于新手更好地理解双向链表的头插)
LTNode* first = phead->next;
phead->next = newnode;
newnode->prev = phead;
newnode->next = first;
first->prev = newnode;
}
法三:函数复用(简单方便)
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法三:函数复用(简单方便)
LTInsert(phead->next, x);
}
在Test.c下
//测试函数
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
}
int main()
{
TestList3();
return 0;
}
双向链表的头删
在List.h下
// 双向链表头删
void LTPopFront(LTNode* phead);
在List.c下
法一:(便于新手更好地理解双向链表的头删)
// 双向链表头删
void LTPopFront(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法一:(便于新手更好地理解双向链表的头删)
LTNode* head = phead->next;
LTNode* headnext = head->next;
phead->next = headnext;
headnext->prev = phead;
free(head);
head = NULL;
}
法二:函数复用(简单方便)
// 双向链表头删
void LTPopFront(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法二:函数复用(简单方便)
LTErase(phead->next);
}
在Test.c下
//测试函数
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
}
int main()
{
TestList3();
return 0;
}
双向链表查找值为x的结点
在List.h下
// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x);
在List.c下
// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* cur = phead->next;
while (cur != phead)//让cur去遍历
{
if (cur->data == x)//如果找到
{
return cur;
}
cur = cur->next;
}
return NULL;//如果没找到
}
在Test.c下
//测试函数
TestList4()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
}
int main()
{
TestList4();
return 0;
}
双向链表的销毁
在List.h下
// 双向链表的销毁
void LTDestory(LTNode* phead);
在List.c下
// 双向链表的销毁
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;//让cur遍历
while (cur != phead)
{
LTNode* curnext = cur->next;
free(cur);
cur = curnext;
}
free(phead);
phead = NULL;
//这个置空其实已经没有意义了,形参的改变不会改变实参
//我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空
}
在Test.c下
//测试函数
TestList4()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTDestory(plist);
plist = NULL;//在这里置空
}
双向链表的修改
在List.h下
// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x);
在List.c下
// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x)
{
assert(pos);
pos->data = x;
}
在Test.c下
//测试函数
TestList5()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTModify(plist->next,5);
LTPrint(plist);
}
int main()
{
TestList5();
return 0;
}
双向链表删除值为x的结点
在List.h下
// 双向链表删除值为x的结点
void LTRemove(LTNode* phead,LTDataType x);
在List.c下
// 双向链表删除值为x的结点
void LTRemove(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* pos = phead->next;
while (pos != phead)
{
pos = LTFind(phead, x);
if (pos == NULL)//如果遍历完
{
return NULL;
}
LTErase(pos);
pos = pos->next;
}
}
在Test.c下
TestList6()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 3);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTInsert(plist, 3);
LTPrint(plist);
LTRemove(plist, 3);
LTPrint(plist);
}
int main()
{
TestList6();
return 0;
}
双向链表计算结点总数(不计phead)
在List.h下
// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead);
在List.c下
// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead)
{
assert(phead);//有哨兵位
int count = 0;//count来计数
LTNode* cur = phead->next;//让cur去遍历
while (cur != phead)
{
count++;
cur = cur->next;
}
return count;
}
在Test.c下
TestList6()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 3);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTInsert(plist, 3);
LTPrint(plist);
LTRemove(plist, 3);
LTPrint(plist);
printf("%d
", LTTotal(plist));
}
int main()
{
TestList6();
return 0;
}
双向链表获取第i位置的结点
在List.h下
// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i);
在List.c下
// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i)
{
assert(phead);//有哨兵位
int length = LTTotal(phead);
LTNode* cur = phead->next;
if (i == 0)
{
return phead;
}
else if (i<0 || i>length)//位置不合法
{
return NULL;
}
else if (i <= (length / 2))//从表头开始遍历
{
cur = phead->next;
for (int count = 1; count < i; count++)
{
cur = cur->next;
}
}
else//从表尾开始遍历
{
cur = phead->prev;
for (int count = 1; count <= length - i; count++)
{
cur = cur->prev;
}
}
return cur;
}
在Test.c下
//测试函数
TestList7()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTNode* pos = LTGet(plist,3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
}
int main()
{
TestList7();
return 0;
}
双向链表的清空
在List.h下
// 双向链表的清空
void LTClean(LTNode* phead);
在List.c下
// 双向链表的清空
void LTClear(LTNode* phead)
{
assert(phead);//有哨兵位
while (!LTEmpty(phead))//如果不为空就一直头删
{
LTPopFront(phead);
}
}
在Test.c下
//测试函数
TestList8()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTClear(plist);
LTPrint(plist);
}
int main()
{
TestList8();
return 0;
}
总代码(想直接看结果的可以看这里)
在List.h下
#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突
//先将可能使用到的头文件写上
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;//假设结点的数据域类型为 int
//给变量定义一个易于记忆且意义明确的新名字,并且便于以后存储其它类型时方便改动
//(比如我晚点想存double类型的数据,我就直接将 int 改为 double )
// 带哨兵位双向循环链表的结构体定义
typedef struct ListNode
{
struct ListNode* prev;//前驱指针域:存放上一个结点的地址
struct ListNode* next;//后继指针域:存放下一个结点的地址
LTDataType data;//数据域
}LTNode;
//struct 关键字和 ListNode 一起构成了这个结构类型
//typedef 为这个结构起了一个别名,叫 LTNode,即:typedef struct ListNode LTNode
//现在就可以像 int 和 double 那样直接使用 LTNode 来定义变量
// 双向链表的初始化
// 如果是单链表直接给个空指针就行,不需要单独写一个函数进行初始化
// 即:LTNode* plist = NULL;
// 那为什么顺序表、带头双向循环链表有呢?
// 因为顺序表、带头双向循环链表的结构并不简单,
// 如:顺序表顺序表为空size要为0,还要看capacity是否要开空间,
//若不开空间capacity=0,指针要给空,若开空间,还要检查malloc是否成功
// 带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
LTNode* LTInit();
// 双向链表在pos位置之前进行插入x
void LTInsert(LTNode* pos, LTDataType x);
// 双向链表的打印
void LTPrint(LTNode* phead);
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos);
//双向链表优于单链表的点——不需要找尾、二级指针
// (我们改的不是结构体的指针,改的是结构体的变量)
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);
// 双向链表的判空
bool LTEmpty(LTNode* phead);
// 双向链表的尾删
void LTPopBack(LTNode* phead);
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x);
// 双向链表头删
void LTPopFront(LTNode* phead);
// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x);
// 双向链表的销毁
void LTDestory(LTNode* phead);
// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x);
// 双向链表删除值为x的结点
void LTRemove(LTNode* phead, LTDataType x);
// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead);
// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i);
// 双向链表的清空
void LTClear(LTNode* phead);
在List.c下
#include"List.h"
//动态申请一个结点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)//如果malloc失败
{
perror("malloc fail");
return NULL;
}
//如果malloc成功
//初始化一下,防止野指针,如果看到返回的是空指针,那逻辑可能有些错误
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}
// 双向链表的初始化
LTNode* LTInit()
{
LTNode* phead = BuyListNode(-1);
//自己指向自己
phead->next = phead;
phead->prev = phead;
return phead;
}
// 双向链表在pos位置之前进行插入x
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);//pos肯定不为空
LTNode* prev = pos->prev;
LTNode* newnode = BuyListNode(x);//创建一个需要插入的结点
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}
// 双向链表的打印
void LTPrint(LTNode* phead)
{
assert(phead);//有哨兵位
printf("<=>phead<=>");
LTNode* cur = phead->next;//cur指向第一个要打印的结点
while (cur != phead)//cur等于头结点时打印就结束了
{
printf("%d<=>", cur->data);
cur = cur->next;
}
printf("
");
}
// 双向链表删除pos位置的结点
void LTErase(LTNode* pos)
{
assert(pos);//pos肯定不为空
LTNode* posprev = pos->prev;
LTNode* posnext = pos->next;
posprev->next = posnext;
posnext->prev = posprev;
free(pos);
pos = NULL;
//这个置空其实已经没有意义了,形参的改变不会改变实参
}
// 双向链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//法一:(便于新手更好地理解双向链表的尾插)
//一步就可完成链表为空/不为空的尾插
//LTNode* newnode = BuyListNode(x);
//LTNode* tail = phead->prev;
//tail->next = newnode;
//newnode->prev = tail;
//newnode->next = phead;
//phead->prev = newnode;
//法二:函数复用(简单方便)
LTInsert(phead, x);
}
// 双向链表的判空
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//两者相等就是空链表(返回真),两者不相等就不是空链表(返回假)
}
// 双向链表的尾删
void LTPopBack(LTNode* phead)
{
assert(phead);//有哨兵位
//法一:(便于新手更好地理解双向链表的尾删)
//assert(!LTEmpty(phead));//判空
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;
//tailPrev->next = phead;
//phead->prev = tailPrev;
//free(tail);
//tail = NULL;
//法二:函数复用
LTErase(phead->prev);
}
// 双向链表头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
//LTNode* newnode = BuyListNode(x);//创建一个要插入的结点
//法一:只用phead和newnode两个指针(便于新手更好地理解双向链表的头插)
//newnode->next = phead->next;
//phead->next->prev = newnode;
//phead->next = newnode;
//newnode->prev = phead;
//法二:多用了first先记住第一个结点(便于新手更好地理解双向链表的头插)
//LTNode* first = phead->next;
//phead->next = newnode;
//newnode->prev = phead;
//newnode->next = first;
//first->prev = newnode;
//法三:函数复用(简单方便)
LTInsert(phead->next, x);
}
// 双向链表头删
void LTPopFront(LTNode* phead)
{
assert(phead);//有哨兵位
assert(!LTEmpty(phead));//判空
//法一:(便于新手更好地理解双向链表的头删)
//LTNode* head = phead->next;
//LTNode* headnext = head->next;
//phead->next = headnext;
//headnext->prev = phead;
//free(head);
//head = NULL;
//法二:函数复用(简单方便)
LTErase(phead->next);
}
// 双向链表查找值为x的结点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* cur = phead->next;
while (cur != phead)//让cur去遍历
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
// 双向链表的销毁
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* curnext = cur->next;
free(cur);
cur = curnext;
}
free(phead);
phead = NULL;
//这个置空其实已经没有意义了,形参的改变不会改变实参
//我们为了保持接口的一致性,不传二级指针,选择在测试的时候置空
}
// 双向链表的修改,修改pos位置的值为x
void LTModify(LTNode* pos, LTDataType x)
{
assert(pos);//pos肯定不为空
pos->data = x;
}
// 双向链表删除值为x的结点
void LTRemove(LTNode* phead, LTDataType x)
{
assert(phead);//有哨兵位
LTNode* pos = phead->next;
while (pos != phead)
{
pos = LTFind(phead, x);
if (pos == NULL)//如果遍历完
{
return NULL;
}
LTErase(pos);
pos = pos->next;
}
}
// 双向链表计算结点总数(不计phead)
int LTTotal(LTNode* phead)
{
assert(phead);//有哨兵位
int count = 0;//count来计数
LTNode* cur = phead->next;//让cur去遍历
while (cur != phead)
{
count++;
cur = cur->next;
}
return count;
}
// 双向链表获取第i位置的结点
LTNode* LTGet(LTNode* phead, int i)
{
assert(phead);//有哨兵位
int length = LTTotal(phead);
LTNode* cur = phead->next;
if (i == 0)
{
return phead;
}
else if (i<0 || i>length)//位置不合法
{
return NULL;
}
else if (i <= (length / 2))//从表头开始遍历
{
cur = phead->next;
for (int count = 1; count < i; count++)
{
cur = cur->next;
}
}
else//从表尾开始遍历
{
cur = phead->prev;
for (int count = 1; count <= length - i; count++)
{
cur = cur->prev;
}
}
return cur;
}
// 双向链表的清空
void LTClear(LTNode* phead)
{
assert(phead);//有哨兵位
while (!LTEmpty(phead))//如果不为空就一直头删
{
LTPopFront(phead);
}
}
在Test.c下
#include"List.h"
//测试函数
void TestList1()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTErase(plist->next);
LTPrint(plist);
}
//测试函数
void TestList2()
{
LTNode* plist = LTInit();
LTPushBack(plist, 5);
LTPushBack(plist, 6);
LTPushBack(plist, 7);
LTPushBack(plist, 8);
LTPrint(plist);
LTPopBack(plist);
LTPopBack(plist);
LTPrint(plist);
}
//测试函数
void TestList3()
{
LTNode* plist = LTInit();
LTPushFront(plist, 1);
LTPushFront(plist, 2);
LTPushFront(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopFront(plist);
LTPopFront(plist);
LTPrint(plist);
}
//测试函数
TestList4()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTNode* pos = LTFind(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTDestory(plist);
plist = NULL;//在这里置空
}
//测试函数
TestList5()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 2);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTPrint(plist);
LTModify(plist->next, 5);
LTPrint(plist);
}
TestList6()
{
LTNode* plist = LTInit();
LTInsert(plist, 1);
LTInsert(plist, 3);
LTInsert(plist, 3);
LTInsert(plist, 4);
LTInsert(plist, 3);
LTPrint(plist);
LTRemove(plist, 3);
LTPrint(plist);
printf("%d
", LTTotal(plist));
}
//测试函数
TestList7()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTNode* pos = LTGet(plist, 3);
if (pos)
{
LTErase(pos);
pos = NULL;
}
LTPrint(plist);
LTClear(plist);
LTPrint(plist);
}
//测试函数
TestList8()
{
LTNode* plist = LTInit();
LTInsert(plist, 5);
LTInsert(plist, 6);
LTInsert(plist, 7);
LTInsert(plist, 8);
LTInsert(plist, 9);
LTPrint(plist);
LTClear(plist);
LTPrint(plist);
}
int main()
{
//TestList1();
//TestList2();
//TestList3();
//TestList4();
//TestList5();
//TestList6();
//TestList7();
TestList8();
return 0;
}
欢迎指正❀