美丽寮步网站建设高性能,本地wordpress后台,宁波市建设局,wordpress获取父级id大家好#xff0c;又是我#xff08;小锋#xff09;#xff0c;今天给大家带了一个比较有挑战的章节#xff08;链表#xff09;#xff0c;但是不用担心#xff0c;小锋会陪大家一起度过。
顺序表的思考与问题 1. 中间/头部的插入删除#xff0c;时间复杂度为O(N) …大家好又是我小锋今天给大家带了一个比较有挑战的章节链表但是不用担心小锋会陪大家一起度过。
顺序表的思考与问题 1. 中间/头部的插入删除时间复杂度为O(N) 我们在进行一些插入删除操作时我们会先内存覆盖然后再进行操作覆盖内存的时间复杂度为O(N)。 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 当我们进行扩容时我们是不是要用realloc函数而realloc函数再扩容时分为异地扩容和原地扩容当我们异地扩容时又有一系列的操作这又加大了消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 我们增加容量后可能用不完这就会造成空间的浪费以及顺序表的空间是连续的我们要释放就必须全部释放。 那我们今天讲到链表就不会出现上面的问题但也不是说链表就没有缺点不论是顺序表还是链表都有优缺点重点在于我们怎么运用。 链表 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。 我们这节主要讲解单链表 这个就是链表的逻辑结构了一个节点中有指向下一个节点的指针这样走下去最后一个节点中放的是空指针NULL像链条一样一环扣一环。 我给大家画一个物理结构方便大家理解 我们可以形象看出链表的基本结构 那我们来创建一个链表 我们先来实现一个打印链表内容的函数 单链表打印 //链表输出void LBexport(LBbiao* att) {assert(att);LBbiao* ps att;while (ps! NULL) {printf(%d-, ps-SZ);ps ps-next;}printf(NULL\n);} 这里大家可以画图一步一步的理一下理解会更加深刻主要注意循环的判断条件。 我们下面来实现一个插入函数 单链表头插数据 我们想一想在链表的头部插入数据我们只需要开辟一个链表空间mon然后另它的next指向当前链表的表头的地址并将mon的地址交给表头的指针是不是就可以插入数据并且将链表连接起来了 大家可以看看大致原理如图 我们还要注意要进行断言防止出现错误 //链表头插数据void LBcutin(LBbiao** att,CMMlet n) {assert(att);LBbiao* pt LBopen();if (*att NULL) {*att pt;}else {pt-next *att;*att pt;}pt-SZ n;} 这里开辟一个新的链表空间我们还会用到所有我们用一个函数来实现 //开辟链表LBbiao* LBopen() {LBbiao* mon (LBbiao*)malloc(sizeof(CMMlet) sizeof(LBbiao*));if (mon NULL) {printf(开辟失败%s,strerror(errno));return NULL;}mon-next NULL;mon-SZ 0;return mon;} 我们这里可以用老方法分装一个函数来验证 单链表头删数据 还是我们用图来演示 //链表头删数据void LBdelete(LBbiao**att) {assert(*att ! NULL);assert(att ! NULL);//断言LBbiao* ps *att;*att ps-next;ps-next NULL;free(ps);} 我们验证试试 单链表尾删数据 我们还是画图演示原理 我们可以看见尾删数据直接将倒数第二个节点的next为空就行了,当然我们还要断言一些情况 并且我们还要分情况当链表只有一个节点时该怎么删。 //链表尾删数据void LBweishan(LBbiao*att) {assert(att ! NULL);//断言LBbiao* ps att;while (ps-next-next ! NULL) {ps ps-next;}free(ps-next);ps-next NULL;} 单链表尾插数据 老规矩画图理解 我们通过图可以看出尾插数据要开辟一个新的节点然后让原链表的最后一个节点的next指向新开辟出来的节点并将新开辟的节点的next为空。同样我们要分情况讨论 //链表尾插数据void LBweicha(LBbiao** att,CMMlet n) {LBbiao* ps *att;LBbiao* pt LBopen();if (ps NULL) {*att pt;}else {while (ps-next ! NULL) {ps ps-next;}ps-next pt;}pt-SZ n;} 单链表查找 我们可以直接遍历链表如果遇到我们就返回该数据的节点地址如果没找到我们返回NULL。 //链表查找LBbiao* LBchazhao(LBbiao* att, CMMlet n) {assert(att);LBbiao* ps att;while (ps ! NULL) {if (ps-SZ n) {return ps;break;}ps ps-next;}return NULL;} 我们可以测试一下 单链表在pos位置之后插入x 与头插类似我们主要注意的是要不要分情况讨论以及断言的内容具体插入的过程我们大家可以自己画图试试 接下来我们来实现一下这个函数 //链表在pos位置后插入xvoid LBporcr(LBbiao* pos, CMMlet x) {assert(pos);LBbiao* ps pos;LBbiao* pt LBopen();if (pos-next NULL) {//相当于尾插数据LBweicha(pos, x);}else {//一般情况pt-nextps-next;ps-next pt;pt-SZ x;}} 验证试试 单链表删除pos位置之后的值 我们还是用图说话 分析后我们发现我们只需要将pos位置的next指向pos-next-next就ok了最后还要注意一下特殊情况以及断言 //链表在pos位置后删除xvoid LBpossc(LBbiao* pos) {assert(pospos-next!NULL);if (pos-next-next NULL) {//相当于尾删free(pos-next);pos-next NULL;}else {LBbiao* ps pos-next;pos-next pos-next-next;ps-next NULL;free(ps-next);}} 我们可以测试一下 我们的单链表就讲解完了是不是畅快淋漓呢 这是我们本节的所有代码大家可以自己试试 # define _CRT_SECURE_NO_WARNINGS 1
# includestdio.h
# includeassert.h
# includestring.h
# includeerrno.h
# includestdlib.h//类型重命名
//方便后期修改
typedef struct LBbiao LBbiao;
typedef int CMMlet;
//链表创建struct LBbiao{CMMlet SZ;//链表存储的数据struct LBbiao* next;//指向下一个节点};//开辟链表LBbiao* LBopen() {LBbiao* mon (LBbiao*)malloc(sizeof(CMMlet) sizeof(LBbiao*));if (mon NULL) {printf(开辟失败%s,strerror(errno));return NULL;}mon-next NULL;mon-SZ 0;return mon;}//链表输出void LBexport(LBbiao* att) {assert(att);LBbiao* ps att;while (ps! NULL) {printf(%d-, ps-SZ);ps ps-next;}printf(NULL\n);}//链表头插数据void LBcutin(LBbiao** att,CMMlet n) {assert(att);LBbiao* pt LBopen();if (*att NULL) {*att pt;}else {pt-next *att;*att pt;}pt-SZ n;}//链表头删数据void LBdelete(LBbiao**att) {assert(*att ! NULL);assert(att ! NULL);//断言LBbiao* ps *att;*att ps-next;ps-next NULL;free(ps);}//链表尾删数据void LBweishan(LBbiao**att) {assert(att ! NULL);//断言assert(*att ! NULL);LBbiao* ps *att;if (ps-next NULL) {*att NULL;free(ps);}else {while (ps-next-next ! NULL) {ps ps-next;}free(ps-next);ps-next NULL;}}//链表尾插数据void LBweicha(LBbiao** att,CMMlet n) {LBbiao* ps *att;LBbiao* pt LBopen();if (ps NULL) {*att pt;}else {while (ps-next ! NULL) {ps ps-next;}ps-next pt;}pt-SZ n;}//链表查找LBbiao* LBchazhao(LBbiao* att, CMMlet n) {assert(att);LBbiao* ps att;while (ps ! NULL) {if (ps-SZ n) {return ps;break;}ps ps-next;}return NULL;}//链表在pos位置后插入xvoid LBporcr(LBbiao* pos, CMMlet x) {assert(pos);LBbiao* ps pos;LBbiao* pt LBopen();if (pos-next NULL) {//相当于尾插数据LBweicha(pos, x);}else {//一般情况pt-nextps-next;ps-next pt;pt-SZ x;}}//链表在pos位置后删除xvoid LBpossc(LBbiao* pos) {assert(pospos-next!NULL);if (pos-next-next NULL) {//相当于尾删free(pos-next);pos-next NULL;}else {LBbiao* ps pos-next;pos-next pos-next-next;ps-next NULL;free(ps-next);}}//测试链表1void ceshi1() {LBbiao* arr NULL;LBweicha(arr, 1);LBweicha(arr, 2);LBweicha(arr, 3);LBweicha(arr, 4);LBexport(arr);LBporcr(arr, 0);LBexport(arr);LBpossc(arr);LBexport(arr);}int main() {ceshi1();return 0;} 以上就是全部内容了如果有错误或者不足的地方欢迎大家给予建议。
