罗阳网站建设西安seo包年服务
目录
概念
带头双向循环链表的实现
前情提示
双向链表的结构体定义
双向链表的初始化
关于无头单向非循环链表无需初始化函数，顺序表、带头双向循环链表需要的思考
双向链表在pos位置之前插入x
双向链表的打印
双链表删除pos位置的结点
双向链表的尾插
关于单链表的尾插需要用到二级指针，双向链表不需要用到二级指针的思考
双向链表的判空
双向链表的尾删
双向链表的头插
双向链表的头删
双向链表查找值为x的结点
双向链表的销毁
双向链表的修改
双向链表删除值为x的结点
双向链表计算结点总数(不计phead)
双向链表获取第i位置的结点
双向链表的清空
总代码（想直接看结果的可以看这里）
概念
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。我们一般构造双向循环链表。循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其它结点。
带头双向循环链表的实现
前情提示
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("\n");
}在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\n", 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("\n");
}// 双向链表删除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\n", 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;
}欢迎指正❀
