网站开发实训周报,泰安网站建设个人工作室,怎么给网站制作二维码,企业门户网站 源码文中代码源文件已上传#xff1a;数据结构源码 -上一篇 初级数据结构#xff08;一#xff09;——顺序表 | NULL 下一篇-
1、链表特征 与顺序表数据连续存放不同#xff0c;链表中每个数据是分开存放的#xff0c;而且存放的位置尤其零散#… 文中代码源文件已上传数据结构源码 -上一篇 初级数据结构一——顺序表 | NULL 下一篇-
1、链表特征 与顺序表数据连续存放不同链表中每个数据是分开存放的而且存放的位置尤其零散毫无规则可言。对于零散的数据而言我们当然可以通过某种方式统一存储每一个数据存放的地址如下图 但这个 sheet 无论怎么看都是一个数组而 ptr_data 是个指针也就是说以上数据结构仍然是一种顺序表只不过表中的数据从具体的值改为指针。它仍然没有脱离顺序表的范畴。自然顺序表的优势及劣势它也照单全收。 顺序表的劣势在于开辟空间并非随需开辟释放空间也显得不那么灵活。如果顺序表做到每次增加数据便拓展空间删除数据便回收空间基于 realloc 可能异地开辟的特点搬运数据的时间复杂度为 O(N) 。如果顺序表的长度是几千万乃至几亿每添加或者删除一个数据其延迟是难以忽略的。因此上篇中的顺序表每次开辟空间均是成批开辟。但这种方式也必然造成空间的浪费。 如果有一种储存方式可以解决上述问题做到每一个数据的空间都按需开辟且按需释放那么在最极端的情况下它甚至可以节省近一半存储空间。在此思想上数组的特性完全不符合该要求首先需要抛弃的便是数组。但上图倘若没了数组每一个数据节点的位置便无从知晓。于是有了链表的概念。 链表可以将下一个节点的位置储存在上一个节点中此外还可以将上一个节点的位置储存在下一个节点中。 如上图。链表还需要一个头指针指向第一个节点。上述结构称为单链表。此外链表还有以下常见结构环链、双向链。 比如这篇文章最顶端“上一篇”、“下一篇”的导航链接就类似双向链。
2、链表创建
2.1、文件结构 本文以最基本的单链为例因为其他变形比单链的复杂程度高不了多少有机会再作补充。仍是先从文件结构开始分别建立以下三个文件 lnkTab.h 用于创建结构体类型及声明函数 lnkFunction.c 用于创建链表各种操作功能的函数 main.c 仅创建 main 函数用作测试。
2.2、前期工作 在 lnkTab.h 中先码入以下内容
#include stdio.h
#include stdlib.h
#include limits.h//自定义数据类型和打印类型方便后续更改储存数据的类型
#define PRINT_FORMAT %d
typedef int DATATYPE;//创建链表节点的结构体类型
typedef struct LinkedListType
{DATATYPE data;struct LinkedListType* next;
}LinkedListType;//---------------------函数声明---------------------
//打印链表
extern void DataPrint(LinkedListType*);//创建节点
extern LinkedListType* NodeCreate(const DATATYPE, const LinkedListType*);//销毁链表
extern void DataDestory(LinkedListType**); 在 lnkFunction.c 中包含 lnkTab.h 并分别创建一个打印链表和销毁链表的函数
#include lnkTab.h//打印链表
void DataPrint(LinkedListType* ptr_headNode)
{//创建节点指针LinkedListType* currentNode ptr_headNode;//循环打印while (currentNode){//打印printf(PRINT_FORMAT - , currentNode-data);//移动节点指针currentNode currentNode-next;}printf(NULL\n);
}//创建节点
LinkedListType* NodeCreate(const DATATYPE data, const LinkedListType* next)
{LinkedListType* node (LinkedListType*)malloc(sizeof(LinkedListType));//加入判断防止空间开辟失败if (node NULL){perror(Malloc Fail);return NULL;}//节点赋值node-data data;node-next next;return node;
}//销毁链表
void DataDestory(LinkedListType** ptr2_headNode)
{//空链表判断if (!ptr2_headNode) return;//创建节点指针LinkedListType* currentNode *ptr2_headNode;//循环逐个销毁节点while (currentNode){LinkedListType* nextNode currentNode-next;free(currentNode);currentNode nextNode;}//头指针置空*ptr2_headNode NULL;
} 最后在 main.c 中包含 lnkTab.h并创建一个链表头指针
#include lnkTab.hint main()
{LinkedListType* ptr_headNode NULL;return 0;
} 至此前期工作准备完毕。
3、链表操作
3.1、增 同顺序表一样链表除了指定位置插入数据之外最好也定义下头部插入数据及尾部插入数据的函数。因此先在 lnkTab.h 中加入以下函数声明
//指定位置插入数据
extern void DataPush(LinkedListType**, const int, const DATATYPE);
//头部插入数据
extern void DataPushHead(LinkedListType**, const DATATYPE);
//尾部插入数据
extern void DataPushTail(LinkedListType**, const DATATYPE); 之后先创建 DataPush 函数。在此之前把函数的流程图画出以助于思考。画流程图的过程中能认识到空链表跟非空链表要分开处理除了头插其他位置插入的逻辑是相同的 对照上图照着在 lnkFunction.c 里写出如下代码
void DataPush(LinkedListType** ptr2_headNode, const int pos, const DATATYPE data)
{//有效性检查if (!ptr2_headNode) return;LinkedListType* currentNode *ptr2_headNode;//如果插入位置小于等于0或者没有节点if (pos 0 || !currentNode){//创建节点将头指针的值赋予该节点的指向并将头指针指向该节点LinkedListType* node NodeCreate(data, currentNode);*ptr2_headNode node;return;}//遍历节点至插入位置前一节点for (int i 0; i pos - 1; i){//若遇到最后一个节点则停止遍历当前节点指针指向最后一个节点if (currentNode-next)currentNode currentNode-next;elsebreak;}//创建节点将当前节点的指向值赋予创建的该节点的指向并将当前节点指向创建的节点LinkedListType* node NodeCreate(data, currentNode-next);currentNode-next node;
} 至于头插尾插数据只不过是上述函数 pos 位置的区别。因此
//pos 0 便是头插
void DataPushHead(LinkedListType** ptr2_headNode, const DATATYPE data)
{DataPush(ptr2_headNode, 0, data);
}//由于 DataPush 函数在 pos 大于节点数时自动进行尾插
//因此 pos INT_MAX 在任意情况下都是尾插
void DataPushTail(LinkedListType** ptr2_headNode, const DATATYPE data)
{DataPush(ptr2_headNode, INT_MAX, data);
} 验证环节。在 main 函数中加入如下代码试运行 DataPush(ptr_headNode, 10, 1234);DataPrint(ptr_headNode); // 1234 NULLDataPushTail(ptr_headNode, 1);DataPrint(ptr_headNode); // 1234 1 NULLDataPushHead(ptr_headNode, 2);DataPrint(ptr_headNode); // 2 1234 1 NULLDataPushTail(ptr_headNode, 3);DataPrint(ptr_headNode); // 2 1234 1 3 NULLDataPush(ptr_headNode, 1, 14542);DataPrint(ptr_headNode); // 2 14542 1234 1 3 NULLDataPushHead(ptr_headNode, 4);DataPrint(ptr_headNode); // 4 2 14542 1234 1 3 NULLDataPushTail(ptr_headNode, 114514);DataPrint(ptr_headNode); // 4 2 14542 1234 1 3 114514 NULLDataPush(ptr_headNode, 10, 1442);DataPrint(ptr_headNode); // 4 2 14542 1234 1 3 114514 1442 NULL 结果与预期无误。至此插入功能便已完成。
3.2、删 第一步当然是在 lnkTab.h 中加入函数声明
//指定位置删除数据
extern void DataPop(LinkedListType**, const int, const int);
//头部删除数据
extern void DataPopHead(LinkedListType**);
//尾部删除数据
extern void DataPopTail(LinkedListType**); 完毕后二话不说先上流程图。这里同样要注意区分空链和其他位置删除。不过删除节点还得将头删及其他位置删除分开判定。 而且这里要注意的是删除与插入不同万一 pos 值传错导致小于 0 或者大于链表长度便不能如上图简单粗暴地执行头删尾删。创建函数的时候多加一个参数来判断是否要在这种情况下头删或者尾删最好不过了。为了直观还是在 lnkTab.h 头文件中加个枚举类型
//定义删除节点的暴力模式和非暴力模式
enum Deletion { UNFORCED, FORCED }; 然后在 lnkFunction.c 里码下这些
void DataPop(LinkedListType** ptr2_headNode, const int pos, const int deletionMode)
{//如果没有节点则直接退出if (!ptr2_headNode || !*ptr2_headNode) return;LinkedListType* currentNode *ptr2_headNode;//如果插入位置小于等于0则头删前提是在非暴力模式下if (pos 0 || (pos 0 deletionMode)){*ptr2_headNode (*ptr2_headNode)-next;free(currentNode);return;}//遍历节点至需要删除的节点前一节点int i;for (i 1; i pos - 1; i){//若遇到倒数第二个节点则停止遍历当前节点指针指向倒数第二个节点if (currentNode-next-next)currentNode currentNode-next;elsebreak;}//模式不暴力的话pos超出表长度就直接退出了if (i pos - 1 !deletionMode) return;//删LinkedListType* freeNode currentNode-next;currentNode-next currentNode-next-next;free(freeNode);
} 然后头删 pos 为 0 尾删 pos INT_MAX 且删除模式为 FORCED 。就没必要再赘述了
//删除头部节点
void DataPopHead(LinkedListType** ptr2_headNode)
{DataPop(ptr2_headNode, 0, UNFORCED);
}//删除尾部节点
void DataPopTail(LinkedListType** ptr2_headNode)
{DataPop(ptr2_headNode, INT_MAX, FORCED);
} 题外话这里再提另一种更安全的方式 指定位置删除的 pos 如果超出链表范围直接报错然后头删尾删单独写
//删除头部节点
void DataPopHead(LinkedListType** ptr2_headNode)
{if (!ptr2_headNode) return;LinkedListType* currentNode *ptr2_headNode;//如果没有节点则直接退出if (currentNode NULL) return;//将头指针置为第一个节点的指向并释放第一个节点*ptr2_headNode currentNode-next;free(currentNode);
}//删除尾部节点
void DataPopTail(LinkedListType** ptr2_headNode)
{if (!ptr2_headNode) return;LinkedListType* currentNode *ptr2_headNode;//如果没有节点则直接退出if (currentNode NULL) return;//如果只有一个节点则采用头删else if (currentNode-next NULL){DataPopHead(ptr2_headNode);return;}//遍历至倒数第二个节点释放最后一个节点并将倒数第二个节点指向置空else{while (currentNode-next-next){currentNode currentNode-next;}free(currentNode-next);currentNode-next NULL;}
} 回归正题之后是熟悉的测试阶段。 main 函数中添加 printf(\n----------DataPopTest----------\n);DataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // 2 14542 1234 1 3 114514 1442 NULLDataPop(ptr_headNode, 2, UNFORCED);DataPrint(ptr_headNode); // 2 14542 1 3 114514 1442 NULLDataPop(ptr_headNode, 1000, UNFORCED);DataPrint(ptr_headNode); // 2 14542 1 3 114514 1442 NULLDataPop(ptr_headNode, 1000, FORCED);DataPrint(ptr_headNode); // 2 14542 1 3 114514 NULLDataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // 14542 1 3 114514 NULL DataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // 1 3 114514 NULL DataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // 3 114514 NULL DataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // 114514 NULL DataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // NULL DataPop(ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode); // NULL 完事
3.3、改和查 这两个功能简直不要太简单。查的逻辑跟打印逻辑一致至于改用查的功能返回节点地址直接改 data 完事。 lnkTab.h
//查找节点
extern LinkedListType* DataSearch(const LinkedListType*, const DATATYPE);
//修改节点
extern void DataModify(const LinkedListType*, DATATYPE, DATATYPE); lnkFunction.c //查找节点
LinkedListType* DataSearch(const LinkedListType* ptr_headNode, const DATATYPE data)
{LinkedListType* currentNode ptr_headNode;while (currentNode){if (currentNode-data data) break;currentNode currentNode-next;}return currentNode;
}//修改节点
void DataModify(const LinkedListType* ptr_headNode, DATATYPE target, DATATYPE replace)
{LinkedListType* node DataSearch(ptr_headNode, target);if (!node) return;node-data replace;
} main.c 测试
printf(\n----------DataSearchModifyTest----------\n);for (int i 20; i 10; i--){DataPushHead(ptr_headNode, i);}DataPrint(ptr_headNode); // 10 12 13 14 15 16 17 18 19 20 NULLDataModify(ptr_headNode, 3, 23457); DataPrint(ptr_headNode); // 10 12 13 14 15 16 17 18 19 20 NULLDataModify(ptr_headNode, 13, 23457);DataPrint(ptr_headNode); // 10 12 23457 14 15 16 17 18 19 20 NULL 搞定准备下一篇。撒花
4、作点补充 一开始就提到双向链表和环链。虽然结构复杂了但是这两种结构比单链简单太多了。可以说学懂了单链那么其他结构的链表跟玩似的。 以另一个常规的极端不考虑中途环状环状双向链举例。在数据操作的代码上这个结构可比单链节省了寻找尾节点以及记录上一个节点指针的麻烦。 双向链如果一直找上一个 prev 节点它也只不过是另一种单链视作 next 结构的倒序。最直观的在于链表倒置
while(currentNode)
{DATATYPE* nextNode currentNode-next;currentNode-next currentNode-prev;currentNode-prev temp;currentNode nextNode;
} 一个循环搞定整个链表导致而如果是单链需要考虑遍历分别头插之类的代码量直线上升。至于环链尾节点的 next 指向头节点。事实上这种结构提供了寻找尾节点的便利 currentNode-prev 。那是更便利了只不过不支持迭代总有牺牲嘛。 构建节点的结构体特别自由链表也就那么几种大体结构细节没有规定。总之只要实现节点内记录其他节点的信息便属于链表。奥力给
