网站分页设计,网页制作的模板代码,阜宁做网站公司,上海电商公司排名欢迎来到我的#xff1a;世界
希望作者的文章对你有所帮助#xff0c;有不足的地方还请指正#xff0c;大家一起学习交流 ! 目录 前言线性表的概述链表的概述 内容链表的结构链表节点的定义 链表的基本功能单向链表的初始化链表的插入操作头插操作尾插操作 链表的删除操作头…
欢迎来到我的世界
希望作者的文章对你有所帮助有不足的地方还请指正大家一起学习交流 ! 目录 前言线性表的概述链表的概述 内容链表的结构链表节点的定义 链表的基本功能单向链表的初始化链表的插入操作头插操作尾插操作 链表的删除操作头删操作尾删操作 链表的查找操作链表的在指定位置的插入在指定位置之前插入在指定位置之后插入 链表在指定位置的删除删除指定位置的结点删除指定位置之后的结点 链表的销毁 额外的知识带头单向链表的初始化 总结 前言
线性表的概述 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。 链表的概述 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 内容
链表的结构 链表的结构跟⽕⻋⻋厢相似并且每节⻋厢都是独⽴存在的 那么思考一个问题既然每个车厢都是独立的那怎么样把他们链接起来 想要把每节车厢都链起来就是依赖每节车厢之间的接口以方便链接 而在链表中就需要依赖指针域来将节点都链接起来 在现实中数据结构的链表实现
链表节点的定义 链表一共可以分为八种类型在后面有详解在这里我以结构最简单的一种来介绍链表的结构这种结构叫做无头单向不循环链表 简称 单向链表 但是链表中的每个节点怎么定义,为什么呢 这里我们需要运用结构体来定义节点 原因 1.结构体可以将不同类型的数据组合在一起根据上述的分析对于链表的结点需要存储数据元素intfloat…和下一个节点的地址结构体的话就可以很好的将这两种不同类型的数据数据域和指针域封装在一起 2.并且我们要了解结构体可以比较方便的表示一种复杂的数据结构而链表的结构也相对比较复杂所以用结构体定义链表的结构在合适不过了 //链表的实现
//单向链表的结点的定义
typedef int typeList;//将int类型重命名为typeList
typedef struct SListNode
{typeList data;//这样定义数据域的好处就是可以随时更改任意类型如char、short...struct SListNode* next;//定义指针域存放下一个节点的地址以便找到下一个节点
}SLNode;链表的基本功能 最基础的功能 增 删 查 改 单向链表的初始化 链表开始的时候需要初始化链表因为初始化能建立一个稳定的起始状态就像盖房子之前需要先打好地基一样以确保数据结构符合预期的初始性质 //直接这样定义即可
int main()
{SLNode*pheadNULL;return 0;
}
链表的插入操作 对于单向链表插入操作可以分为四种头插,尾插,在查找到的位置之后插入,在查找到的位置之前插入 在这里我先介绍头插,尾插其余在后续有介绍 头插操作 头插概述就是将一个新节点插入到单向链表的头部使得新节点成为链表的新头部。 头插操作是将新节点插入到链表的头部。在单链表中头节点 phead 是访问链表的入口。头插操作需要改变头节点 phead 的指向。新插入的节点将成为新的头节点原来的头节点将成为新节点的下一个节点。 询问若将头插操作封装成一个函数请问怎么传参呢 由于C语言函数参数是值传递如果只传递一级指针 phead 在函数内部对phead的修改只是修改了函数内部的一个副本。例如在函数内 phead newNode; newNode 是新插入的节点这样的操作只是改变了函数内部 phead 副本的指向而不会改变函数外部真正的 phead 。传递二级指针 phead 函数接收的是头节点指针phead 的地址。这样在函数内部可以通过解引用二级指针来修改真正的头节点 phead 。比如 *pphead newNode; pphead 是接收二级指针的参数这种操作会改变函数外部的 phead 的值使得新插入的节点成为链表的新头节点从而实现了正确的头插操作。 但是头插要分情况讨论若本来链表中就没有节点呢 若有节点怎么办若没有又该怎么样 若有节点就先让新的节点的next域指向头结点*pphead再让头结点*pphead重新指向这个新的结点 若没有节点就直接让*pphead指向新的结点 //头插
void FrontSLNode(SLNode** pphead, typeList n)
{assert(pphead);//断言就是当pphead为NULL会自动报错并结束程序//创建新的节点并将其指针域和数据域都要进行初始化SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc);return;}//初始化指针域和数据域newnode-data n;newnode-next NULL;//当链表为空直接将新的结点插入链表头部if (*pphead NULL){*pphead newnode;return;}//链表不为空新插入的节点将成为新的头节点原来的头节点将成为新节点的下一个节点。newnode-next *pphead;*pphead newnode;return 0;
}
尾插操作 尾插就是指在单链表的末尾插入一个新节点 在单链表中当进行尾插操作时需要考虑两种情况一是链表为空时插入第一个节点二是链表非空时插入新节点到尾部。首先你要知道尾插如果当链表一开始为空时要尾插的话你就需要改变phead的指向此时你就需要传入二级指针(可以这样想当链表非空时这时尾插不需要改变phead指针的指向此时传一级指针就可以) 为什么需要传二级指针因为 当链表为空时头节点 phead 本身为 NULL 。如果只传一级指针在函数内部修改 phead 的值让它指向新插入的节点这种修改在函数结束后不会影响到函数外部的 phead 变量。因为C语言中函数参数传递是值传递对于指针变量也不例外。传递二级指针 phead 就可以在函数内部真正地修改头节点 phead 本身的值。例如在插入第一个节点时函数内部可以通过 *pphead newNode; 假设 pphead 是二级指针接收的参数 newNode 是新插入的节点这样的操作来让外部的phead指向新节点。当链表非空时通过二级指针也可以方便地遍历到链表的尾部进行插入操作并且保证对链表结构的修改如更新尾节点的 next 指针能够在函数外部生效。 //尾插
void BackSLNode(SLNode** pphead, typeList n)
{assert(pphead);//创建新节点SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc);return;}初始化指针域和数据域newnode-data n;newnode-next NULL;if (*pphead NULL){*pphead newnode;return;}//链表不为空,找到尾巴SLNode* tem *pphead;while (tem-next){tem tem-next;}//更新尾结点指向tem-next newnode;
}链表的删除操作 对于单向链表删除操作可分为很多种比如头删,尾删,删除指定位置的结点,删除指定位置之后的结点;接下来我来分别介绍头删,尾删后面的会在后续介绍 当删除头结点时 当要删除头节点时首先要判断链表是否为空。如果链表为空那就没有节点可删除。若链表不为空将头节点指针 phead 指向下一个节点 *pphead *pphead-next ,此时改变了phead的头节点的指向所以要传二级指针然后释放原来头节点的内存空间这样就完成了头节点的删除。 当不是删除头结点时 首先需要遍历链表找到要删除节点的前驱节点。从链表头开始逐个节点检查直到找到一个节点设为 pre 它的下一个节点 pre-next 是要删除的节点。然后将前驱节点 pre 的指针域跳过要删除的节点即 pre-next pre-next-next 。最后释放要删除节点的内存空间。 头删操作 头删就是将第一个节点删掉然后让第二个节点变成新的节点 //头删
void FrontDelSLNode(SLNode** pphead)
{assert(pphead);assert(*pphead);//当链表为空时最好断言一下否则下面的(*pphead)-next 会报错//作为前驱节点最后要删除SLNode* pre *pphead;//只有一个节点的情况if ((*pphead)-next NULL){free(*pphead);*pphead NULL;return;}//两个以上的结点的情况SLNode* ret pre-next;*pphead ret;free(pre);pre NULL;
}尾删操作 尾删就是删除链表的最后一个节点让倒数第二个节点的指针域指向NULL //尾删
void BackDelSLNode(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* pre *pphead;//只有一个节点的情况if ((*pphead)-next NULL){free(*pphead);*pphead NULL;return;}//两个以上的结点的情况,找到尾结点的前一个节点while (pre-next-next){pre pre-next;}//释放掉最后一个节点free(pre-next-next);pre-next-next NULL;//再让倒数第二个节点的next域指向NULLpre-next NULL;
}链表的查找操作 查找:就是在单链表中寻找特定元素或节点也就是说传参的时候可以传数据值或传地址进行查找 注意查找就是负责查找并且返回那个节点而已并不会改变phead头结点指针的方向所以此时传一级指针即可 按值查找 从链表的头节点开始通过遍历链表逐个比较节点的数据域与目标值。设链表头节点为 phead 可以使用一个指针 p phead 然后在循环中比较 p-data 假设 data 是存储数据的成员和目标值。如果相等就找到了目标节点如果不相等就将 p p-next 继续检查下一个节点直到 p 为 NULL 表示遍历完链表未找到目标值。 按址查找 同样从头节点开始要查找第 n 个位置的节点。定义一个计数变量 count 1 一个指针 p phead 。当 count n 且 p 不为 NULL 时执行 p p-next 和 count 操作。如果 count n 此时 p 指向的就是第 n 个节点如果 p 为 NULL 且 count n 则表示链表长度小于 n 不存在第 n 个节点。 这里我就偷个懒就实现 按值查找 喽 //查找
SLNode* FindSLNode(SLNode* phead, typeList n)
{assert(phead);SLNode* p phead;while (p){if (p-data n)return cour;p p-next;}return NULL;
}链表的在指定位置的插入 其实原理也是和头插,尾插原理相同唯一需要理解的是什么叫在特定位置这里我们就需要和之前的那个查找操作相结合了先找到你需要插入的节点再在对这个节点之前节点之后进行插入新的节点 注意当你在在查找到的位置之前插入就有可能会改变头结点phead指针的指向需要传二级指针但是当你在在查找到的位置之后插入就不会改变头结点phead指针的指向所以不需要传二级指针一级指针就可以了 在指定位置之前插入 此时传参不但需要查找到的那个节点还需要将头结点传入进来是为了遍历链表找到指定的那个节点 //在指定位置之前插入数据
void InsertSLNode(SLNode** pphead, SLNode* pos, typeList n)
{assert(pphead);assert(*pphead);assert(pos);//此时还要对指定位置的结点断言//创建新节点并进行初始化SLNode* newnode (SLNode*)malloc(sizeof(SLNode));newnode-data n;newnode-next NULL;//当在第一个节点之前插入if ((*pphead) pos){//就是头插直接将头插的代码拿过来Ctrl C V真的很快乐FrontSLNode(pphead, n);return;}//其他节点找到指定位置之前的那个节点SLNode* tem *pphead;while (tem-next ! pos){tem tem-next;}//插进来tem-next newnode;newnode-next pos;
}
在指定位置之后插入 在指定位置之后插入就不存在改变头节点phead的可能性不需要遍历就能找到指定的那个节点 //在指定位置之后插入数据
void InsertAfterSLNode(SLNode* pos, typeList n)
{assert(pos);//创建新节点并进行初始化SLNode* newnode (SLNode*)malloc(sizeof(SLNode));newnode-data n;newnode-next pos-next;pos-next newnode;
}链表在指定位置的删除 其实和链表的在指定位置的插入的原理相同先找到这个指定位置在进行删除操作 链表在指定位置的删除可以删除指定位置的结点,删除指定位置之后的结点 删除指定位置的结点 删除指定位置的结点需要传头结点用来遍历找到特定位置的结点也有可能删除头结点phead所以需要传二级指针 进行特殊情况的判断 首先判断链表是否为空如果为空则无法进行删除操作直接返回。如果指定位置是第 1 个节点即删除头节点这时候只需要将头指针指向头节点的下一个节点并释放原来头节点的内存空间即可。 步骤 1.查找要删除节点的前驱节点 2.再删除节点 //删除pos节点
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//当为第一个节点,进行头删if (pos (*pphead)){//相当于进行头删操作FrontDelSLNode(pphead);return;}SLNode* tem *pphead;while (tem-next ! pos){tem tem-next;}tem-next pos-next;free(pos);pos NULL;
}删除指定位置之后的结点 删除指定位置之后的结点,不存在改变头节点phead指针的可能性所以传一级指针即可 //删除pos之后的节点
void SLTEraseAfter(SLNode* pos)
{assert(pos);assert(pos-next);SLNode* tem pos;pos tem-next-next;free(tem-next);tem-next NULL;
}链表的销毁 链表的销毁就是指释放链表中所有节点占用的内存空间使链表不再使用 所以要改变头结点phead指针的指向所以传二级指针 首先需要一个指针ptr来遍历链表接着使用一个临时指针next来保存当前节点 ptr的下一个节点的位置然后释放当前节点ptr所占用的内存空间最后将ptr指针更新为next重复上述步骤直到ptrNULL这意味着已经办理并释放了链表的所有节点 //销毁链表
void SListDesTroy(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* ptr *pphead;while (ptr ! NULL){SLNode* next ptr-next;free(ptr);ptr NULL;}*pphead NULL;
}额外的知识带头单向链表的初始化 链表开始的时候需要初始化链表因为初始化能建立一个稳定的起始状态就像盖房子之前需要先打好地基一样以确保数据结构符合预期的初始性质 当面对传参问题 带头链表的初始化可以有两种形式 1.无参数形式2.参数形式 当为无参数形式 因为链表的初始化主要是创建一个节点并将指针域设置成NULL; 例如这里的InitSLNode函数没有参数 SLNode* InitSLNode() {SLNode* head (SLNode*)malloc(sizeof(SLNode));if (head NULL) {//这里的malloc向堆区中开辟空间可能失败所以这边进行判断return NULL;}//这里最好就将数据域也进行初始化一下要不然你这个结点的数据域就是一个随机值head - data 0;//将指针域设为NULL变成一个独立的节点head - next NULL;return head;
}//无参数形式这样进行初始化
int main()
{SLNode*pheadInitSLNode();return 0;
}当为参数形式 其实传参数可以根据自身需求进行不同的设置比如我这时传入的是一个整数为初始值来初始化链表的节点 这里我们想的是把结构体变成一个链表的结点所以我们直接传结构体的地址就可以了我们就可以将这个结构体直接就变成节点 例如这里的InitSLNode函数有参数 //初始化
void InitSLNode(SLNode* phead)
{//这里最好就将数据域也进行初始化一下要不然你这个结点的数据域就是一个随机值phead-data 0;//将指针域设为NULL变成一个独立的节点phead-next NULL;
}//有参形式这样进行初始化
int main()
{SLNode head;InitSLNode(head);return 0;
}这里对于参数形式的传参问题为什么传结构体的地址 因为只有传地址调用的时候可以直接修改结构体的成员数据域和指针域若你只是传结构体变量进来不能改变结构体的成员数据域和指针域 如果还有不太懂的东西可以去了解一下传值调用和传址调用的区别 总结 到了最后感谢支持
------------对过程全力以赴对结果淡然处之 也是对我自己讲的
