世代网络高端企业网站建设设计功能公司,营销宣传文案,thinkphp5 网站开发,高端手表品牌排行榜前十名目录
概念
带头双向循环链表的实现
前情提示
双向链表的结构体定义
双向链表的初始化
关于无头单向非循环链表无需初始化函数#xff0c;顺序表、带头双向循环链表需要的思考
双向链表在pos位置之前插入x
双向链表的打印
双链表删除pos位置的结点
双向链表的尾插
关…目录
概念
带头双向循环链表的实现
前情提示
双向链表的结构体定义
双向链表的初始化
关于无头单向非循环链表无需初始化函数顺序表、带头双向循环链表需要的思考
双向链表在pos位置之前插入x
双向链表的打印
双链表删除pos位置的结点
双向链表的尾插
关于单链表的尾插需要用到二级指针双向链表不需要用到二级指针的思考
双向链表的判空
双向链表的尾删
双向链表的头插
双向链表的头删
双向链表查找值为x的结点
双向链表的销毁
双向链表的修改
双向链表删除值为x的结点 双向链表计算结点总数(不计phead)
双向链表获取第i位置的结点
双向链表的清空
总代码想直接看结果的可以看这里 概念 双向链表也叫双链表是链表的一种它的每个数据结点中都有两个指针分别指向直接后继和直接前驱。所以从双向链表中的任意一个结点开始都可以很方便地访问它的前驱结点和后继结点。我们一般构造双向循环链表。循环链表是一种链式存储结构它的最后一个结点指向头结点形成一个环。因此从循环链表中的任何一个结点出发都能找到任何其它结点。 带头双向循环链表的实现
前情提示
List.h 用于 引用的头文件、双向链表的定义、函数的声明。
List.c 用于 函数的定义。
Test.c 用于 双向链表功能的测试。
双向链表的结构体定义 在List.h下
#pragma once//使同一个文件不会被包含(include)多次,不必担心宏名冲突//先将可能使用到的头文件写上
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef 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是否要开空间,
// 若不开空间capacity0,指针要给空,若开空间,还要检查malloc是否成功
// 带头双向循环链表要开个结点,检查malloc是否成功,然后让结点自己指向自己
// 顺序表和双向循环链表的初始化有点复杂,最好构建一个函数
LTNode* LTInit();
在List.c下
#includeList.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是否要开空间,若不开空间capacity0,指针要给空若开空间,还要检查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下
#includeList.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 (i0 || ilength)//位置不合法{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)多次,不必担心宏名冲突//先将可能使用到的头文件写上
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef 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是否要开空间,
//若不开空间capacity0,指针要给空,若开空间,还要检查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下
#includeList.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 (i0 || ilength)//位置不合法{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下
#includeList.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;
} 欢迎指正❀
