韩式风格的网页设计欣赏,网站排名优化快速,微信公众平台怎么开发,新媒体营销名词解释目录 前言#xff1a;一.顺序表的缺陷 介绍链表1.顺序表的缺陷2.介绍链表#xff08;1#xff09;链表的概念#xff08;2#xff09;链表的结构#xff08;3#xff09;链表的功能 二.单链表的实现1.创建节点的结构2.头文件函数的声明3.函数的实现#xff… 目录 前言一.顺序表的缺陷 介绍链表1.顺序表的缺陷2.介绍链表1链表的概念2链表的结构3链表的功能 二.单链表的实现1.创建节点的结构2.头文件函数的声明3.函数的实现1打印单链表2创建一个节点3尾插4头插5尾删6头删7查找8在pos位置前插入9在pos位置后插入10删除pos位置11删除pos位置后的节点12清理单链表 三.全部代码1.SList.h2.SList.c3.Test.c 前言
上篇文章介绍了顺序表这篇文章开始着重讲解链表了。 链表有很多种单、双链表循环、非循环链表还有带头、不带头的链表。本篇的主要内容是单链表无头单向非循环。 链表对比顺序表有哪些不同之处接下来会带大家一起了解~
一.顺序表的缺陷 介绍链表
1.顺序表的缺陷
1.头部和中间的插入删除效率都较低时间复杂度为O(N)。需要挪动数据。 2.空间不够用了增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。尤其是异地扩容 3.扩容会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间
2.介绍链表
针对顺序表的缺陷就有了链表这个数据结构
1链表的概念
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 特点按需申请释放
顺序表是数组存储数据的空间是连续的可通过一个指针找到所有的值通过size标记直到没有数据前面的为size的个数即有效数据。 链表的每个节点的大小没有关系也不连续多次malloc开辟出来的空间是随机的。它是通过一个头指针phead先找到第一个节点然后通过第一个节点的指针找到第二个节点第二个节点的指针找到第三个节点以此类推通过指针链接。每个位置的节点都有指针指向下一个当下一个为空指针的时候就结束。
2链表的结构
物理图 逻辑图 链表的节点组成单链表 注意链表的最后一个节点的next指向空 看到这有些小伙伴可能有些疑惑链表的每个节点是不连续的为什么上面的两个图中每个节点都有线连接起来变成看似连续的呢其实不是这样的以上的两张图是为了方便理解。实际在内存中每个节点的地址是随机的只不过用这个节点的指针next找到了下一个节点的地址所以才能实现链接。
3链表的功能
链表的功能与顺序表类似无非是增删查改在某位置的插入与删除对数据内容进行管理和操作。
二.单链表的实现
还是以多文件的形式分模块写 SList.h——函数和类型的声明 SList.c——函数的实现 Test.c——进行测试 1.创建节点的结构
单链表一个节点的结构 存放数据data 结构体指针next 注意不能这样写
typedef int SListDataType;//方便更改存储的数据类型
typedef struct SListNode
{SListDataType data;SLTNode* next;
}SLTNode;// -重定义开始生效的位置因为typedef重定义结构体类型的名称是在上面有箭头的一行开始生效生效了才能使用在前面就提前使用就会出现错误。
正确写法
typedef int SListDataType;//方便更改存储的数据类型
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;2.头文件函数的声明 1.打印单链表 2.创建一个节点 3.尾插 4.头插 5.尾删 6.头删 7.查找包含修改 8.在pos位置前插入 9.在pos位置后插入 10.删除pos位置的节点 11.删除pos位置后一个的节点 12.清理单链表 //打印单链表
void SLTPrint(SLTNode* phead);
//创建一个节点
SLTNode* BuySLTNode(SListDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SListDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SListDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SListDataType x);
//在pos位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SListDataType x);
//在pos位置后插入
void SLTInsertAfter(SLTNode* pos, SListDataType x);
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置后一个的节点
void SLTEraseAfter(SLTNode* pos);
//清理单链表
void SLTDestroy(SLTNode** pphead);3.函数的实现
1打印单链表
创建一个结构体指针变量cur使它指向第一个节点把头指针覆给cur。利用循环如果cur不是空指针就打印cur所指向的数据然后cur往后走到下一个节点。直到cur为空跳出最后打印NULL最后一个节点为空指针。
逻辑图 物理图 注意与顺序表不同顺序表传过来的指针一定不为空链表传过来的指针可能为空比如链表没有节点头指针指向的就是NULL所以不需要断言头指针。
所以在测试的文件里Test.c刚开始要让头指针指向NULL SLTNode * plist NULL; void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}2创建一个节点
为了方便后面的尾插、头插等操作所以写个函数来创建一个新节点。 新节点的类型也是结构体指针用malloc函数开辟一个新节点。如果新节点为空就报错。然后给新节点的data赋值next为空返回这个节点方便其他的函数使用
SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}3尾插
尾插一个新节点假设有多个节点首先要找到尾定义一个变量tail去遍历链表找到尾 注意用tail遍历找尾再尾插时不能写成 SLTNode* tail *pphead;while (tail){tail tail-next;}tail newnode; 这段代码看似没有什么问题其实是与正确的代码差别很大。 tail刚开始指向第一个节点如果不为空到下一个节点当tail为空时跳出循环把newnode的值新节点的地址赋给tail。 如图 这里有一个问题tail里面存放的是新节点的地址但是原来链表的最后一个节点的next指针并没有存放新节点的地址也就是说最后一个节点没有与新节点连接起来就没有尾插了。其次还有可能存在内存泄漏新创建的节点丢了。
因为tail是局部变量newnode和phead也是它们出这个函数就销毁了所以给tail这个变量赋新节点的地址没有用。
要成功完成尾插就必须改变结构体的内容让最后一个节点的next指针指向新节点的地址。
这里大家可能有些疑惑既然tail销毁了那么链表的这些节点会不会销毁呢 答案是不会因为这些节点是malloc出来的malloc在堆上开辟的空间只有自己主动free释放掉才能销毁。
正确的思路 首先想到的是要改变结构体节点的内容那么tail这个指针变量就不能到空结束而是到最后一个节点结束tail的next为空就结束tail的位置指向最后一个节点。
此时尾节点的next为空我们要做的是让尾节点的next存放新节点的地址。让tail的next存放newnode的值新节点的地址就可以改变结构体的内容。
找尾尾插正确的一小段代码 SLTNode* tail *pphead;while (tail-next){tail tail-next;}tail-next newnode;还有一种情况如果刚开始链表没有节点就不需要找尾了。直接将新节点的地址给头指针plist就行
但是这种情况要注意什么呢 以下是错误示范 if (phead NULL){phead newnode;}这个代码的意思如图所示 有两个问题 一plist没有改变还是指向空指针新节点丢了可能造成内存泄漏。 二newnode和phead是形参形参是实参的拷贝出这个函数就销毁了改变phead并没有改变plist。
注意plist是一级指针改变一级指针需要用到二级指针并且有解引用操作。所以在函数的参数应该用二级指针来接收传参时plist要有取地址符才能与二级指针类型对应 正确的一小段代码 if (*pphead NULL){*pphead newnode;}总结 1.改变结构体要用结构体指针 2.改变结构体指针要有结构体指针的指针即二级指针 最后一点什么时候要断言指针 当一级指针* pphead为空时不需要断言因为如果刚开始链表没有节点* pphead所指向的就是空指针。二级指针pphead存放的是一级指针的地址一级指针的地址不可能为空所以二级指针需要断言。
void SLTPushBack(SLTNode** pphead, SListDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);//原来没有节点改变结构体指针用二级指针if (*pphead NULL){*pphead newnode;}//原来有节点改变结构体用结构体指针else{SLTNode* tail *pphead;while (tail-next){tail tail-next;}tail-next newnode;}
}4头插
头插也需要用到二级指针因为每次头插头指针plist都要连接新的节点。改变了头指针 头插时原来链表没有节点与原来链表有节点的思路是一样的 新节点先连接第一个节点或者空指针然后plist再连接新节点 注意两者的顺序不能换因为如果先让plist连接newnode那么原来链表plist头指针后面的节点就找不到了。newnode再连接plist所指向的下一个节点就是自己导致死循环。 void SLTPushFront(SLTNode** pphead, SListDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}5尾删
前面的尾插、头插都有用到二级指针那么尾删需不需要二级指针呢接下来我们一点一点的分析
尾删的大体思路是找到尾然后free释放掉尾节点就行。
但是链表有一个很重要的点前后关联
这里我们定义一个指针变量tail去找尾把尾节点删掉了那么原来前一个节点变成新的尾节点还需要用另一个变量当作原来尾节点的前一个节点新的尾节点next指针就必须指向NULL只需要改变结构体否则就访问野指针了。 有两种写法这里只展现一种就用tail一个指针变量让它的下一个的下一个指针为空时停下tail-next-nextNULL此时tail-next就是最后一个节点tail是前一个节点修改新的尾节点的next让tail-next为NULL改变结构体就行了。
以上只是包括一类情况一个以上节点的时候是这样的 如果尾删把节点只删到剩下一个节点时还是如此吗 按前面的思路来走遇到尾节点就把它的前一个节点的next置空。
依图分析只有一个节点时前一个节点就不是节点了是头指针。要让头指针指向NULL即改变头指针就要用到二级指针了。 让 * pphead置空就可以改变头指针 plist 等价于 * pphead 没有节点的情况 断言 * pphead为空就不能再删了
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//一个以上的节点else{SLTNode* tail *pphead;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}6头删
通过前面的分析发现有改变头指针所指向的内容就要用到二级指针头删是把第一个节点除去让头指针指向新的头节点。
画图分析 当链表没有节点时不能再删了所以要对 * pphead断言 * pphead等价于plist即第一个节点
只有一个节点和有多个节点不需要分开处理定义一个变量记录原来链表的第二个节点新的头节点free释放掉第一个节点让头指针连接新的头节点
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead (*pphead)-next;//注意优先级free(*pphead);//不需要置空因为头指针直接连接新的头*pphead newhead;
}7查找
定义一个变量cur遍历链表先判断cur所指向的数据是否等于x如果相等返回cur否则往后走找不到返回空指针。
SLTNode* SLTFind(SLTNode* phead, SListDataType x)
{assert(phead);SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}查找可以包含修改这个节点的数据 SLTNode* pos1 SLTFind(plist, 2);//测试查找修改if (pos1 ! NULL){printf(找到了\n);pos1-data * 100;SLTPrint(plist);}else{printf(找不到\n);}8在pos位置前插入
要在pos位置前插入一个新节点首先pos这个位置的节点必须存在所以要断言pos后面有pos位置插入删除的函数也要用到 pos可能在任意一个位置如果pos在第一个节点就相当于头插了。头插要改变头指针所指向的内容所以要用二级指针。直接调用头插的函数即可。
pos不在第一个节点的情况 首先要定义一个变量prev遍历链表找到并指向pos的前一个节点因为插入新的节点必须前后连接起来单链表的不足之处后期文章用双向循环带头链表就非常简单。 当prev-next pos往后走pos时跳出循环让prev-next连接新节点新节点的next连接pos完成插入。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{assert(pphead);assert(pos);//pos在第一个节点就是头插if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySLTNode(x);prev-next newnode;newnode-next pos;}
}9在pos位置后插入
因为在pos位置后插入新的节点所以可以不用头指针了找到pos位置的下一个节点即可。可以定义一个变量posNext为pos位置的下一个节点让新节点的next连接posNextpos-next连接新节点 不需要考虑是不是尾插因为在哪插入都是一样的
void SLTInsertAfter(SLTNode* pos, SListDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);SLTNode* posNext pos-next;newnode-next posNext;pos-next newnode;
}10删除pos位置
删除pos位置的节点必须把它的前一个节点与后一个节点连接起来这里就要有头指针去找pos位置的前一个节点。 我们要考虑一些情况pos在第一个节点、中间某个节点和尾节点
当pos在第一个节点时就是头删要改变头指针指向的内容所以要用二级指针然后调用头删的函数即可
如果pos是在中间的某个节点或者尾节点呢 其实两者的思路是一致的把pos位置的节点删除让前一个节点连接后一个节点就行是尾节点的话让前一个节点连接空指针
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}11删除pos位置后的节点
要删除pos位置的后一个节点除了pos这个位置要存在之外pos位置的后一个节点也必须存在所以pos-next要断言。假如pos是在尾节点就没有意义了。
定义一个变量posNext为pos的下一个节点然后使pos-next指向posNext-next即把pos位置的节点与posNext的下一个节点连接起来最后释放掉posNext void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//检查是否为尾节点SLTNode* posNext pos-next;pos-next posNext-next;free(posNext);posNext NULL;
}12清理单链表
清理销毁链表必须要一个一个节点清理因为链表在物理结构上是不连续的。
定义一个变量cur遍历链表每到一个节点把它释放掉。但是这里又有一个问题当前节点被释放了怎么到下一个节点呢所以我们循环里再定义一个变量next为cur的下一个节点释放完当前的cur然后把next赋给cur这样cur就能到下一个节点了。
最后全部节点释放完头指针要指向空这里又有改变头指针了所以有二级指针。
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}三.全部代码
1.SList.h
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
typedef int SListDataType;//方便更改存储的数据类型
typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;
//打印单链表
void SLTPrint(SLTNode* phead);
//创建一个节点
SLTNode* BuySLTNode(SListDataType x);
//尾插
void SLTPushBack(SLTNode** pphead, SListDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SListDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SListDataType x);
//在pos位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SListDataType x);
//在pos位置后插入
void SLTInsertAfter(SLTNode* pos, SListDataType x);
//删除pos位置的节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置后一个的节点
void SLTEraseAfter(SLTNode* pos);
//清理单链表
void SLTDestroy(SLTNode** pphead);2.SList.c
#include SList.h
//打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}
//创建一个节点
SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-data x;newnode-next NULL;return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, SListDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);//原来没有节点改变结构体指针用二级指针if (*pphead NULL){*pphead newnode;}//原来有节点改变结构体用结构体指针else{SLTNode* tail *pphead;while (tail-next){tail tail-next;}tail-next newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, SListDataType x)
{assert(pphead);SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//一个以上的节点else{SLTNode* tail *pphead;while (tail-next-next){tail tail-next;}free(tail-next);tail-next NULL;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//空assert(*pphead);//非空SLTNode* newhead (*pphead)-next;//注意优先级free(*pphead);//不需要置空因为头指针直接连接新的头*pphead newhead;
}
//查找
SLTNode* SLTFind(SLTNode* phead, SListDataType x)
{assert(phead);SLTNode* cur phead;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}
//在pos位置前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{assert(pphead);assert(pos);//pos在第一个节点就是头插if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySLTNode(x);prev-next newnode;newnode-next pos;}
}
//在pos位置后插入
void SLTInsertAfter(SLTNode* pos, SListDataType x)
{assert(pos);SLTNode* newnode BuySLTNode(x);SLTNode* posNext pos-next;newnode-next posNext;pos-next newnode;
}
//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (pos *pphead){SLTPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
//删除pos位置后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//检查是否为尾节点SLTNode* posNext pos-next;pos-next posNext-next;free(posNext);posNext NULL;
}
//清理
void SLTDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}3.Test.c
#include SList.h
test()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);//测试尾插SLTPrint(plist);SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);//测试头插SLTPrint(plist);SLTPopBack(plist);SLTPopBack(plist);SLTPopBack(plist);//测试尾删SLTPrint(plist);SLTPopFront(plist);SLTPopFront(plist);//测试头删SLTPrint(plist);SLTNode* pos1 SLTFind(plist, 2);//测试查找修改if (pos1 ! NULL){printf(找到了\n);pos1-data * 100;SLTPrint(plist);}else{printf(找不到\n);}SLTNode* pos2 SLTFind(plist, 10);//测试pos位置前插入if (pos2){SLTInsert(plist, pos2, 66);SLTPrint(plist);}SLTNode* pos3 SLTFind(plist, 20);//测试pos位置后插入if (pos3){SLTInsertAfter(pos3, 77);SLTPrint(plist);}SLTNode* pos4 SLTFind(plist, 1);//测试删除pos位置if (pos4){SLTErase(plist, pos4);SLTPrint(plist);}SLTNode* pos5 SLTFind(plist, 66);//测试删除pos位置的后一个节点if (pos5){SLTEraseAfter(pos5);SLTPrint(plist);}SLTDestroy(plist);
}
int main()
{test();return 0;
}总算把最费劲的写完了感谢铁子们的观看期待大家的支持~
