西北网站建设,网站备案法规,wordpress搜索引擎优化,国外的网站服务商文章目录 #x1f349;前言#x1f349;基本概念#x1f349;链表的分类#x1f34c;单链表节点的结构#x1f34c;创建节点#x1f34c;打印链表#x1f34c;插入和删除#x1f95d;尾插#x1f95d;头插#x1f95d;尾删#x1f95d;头删#x1f95d;指定位置之前… 文章目录 前言基本概念链表的分类单链表节点的结构创建节点打印链表插入和删除尾插头插尾删头删指定位置之前插入指定位置之后插入删除指定节点 销毁 源码头文件声明部分源文件功能实现部分 前言
喜茶的果汁茶有这样的一句宣传语一半果汁一半茶。用这个来形容单链表那可是再合适不过了一一 一半数据一半指针。
基本概念
链表是一种数据结构采用链式存储一一在内存中不是连续存储的各元素的逻辑顺序是通过链表中的指针链接次序实现的。它包含数据域和指针域分别保存数据和下一个节点的地址。 如果要创建节点一般是在堆上申请。 链表的分类
链表结构多种多样有三种分类这些分类进行排列组合共有8种 ①单向或双向 区分单双向就看各节点之间的指向是否是双向的比如下面这个就是双向链表。 ②带头或不带头 就是有没有带头节点头节点的数据域一般是存放这个链表的基本信息其指针域指向第一个节点。③循环或非循环 尾节点的指针指向头节点就可以形成一个循环。 我们最常用的是这两种无头单向非循环链表和带头双向循环链表本文要讲的是单链表。
单链表节点的结构
typedef int SLTypeDate;
typedef struct SListNode {SLTypeDate data;struct SListNode* next;
}SLNode;这个结构体里面有一个同类型的结构体指针这种现象叫做结构体的自引用往下看你就会知道这个指针的妙处了。 Q使用 typedef 对结构体重命名之后可以在结构体内部使用新的名字吗 A不可以因为编译器是向下编译的上面的语句相当于 struct SListNode {SLTypeDate data;struct SListNode* next;
};
typedef int SLTypeDate SLNode;创建节点
刚才已经在头文件里面定义了一个结构体类型SLNode链表节点那么现在来建立一些节点用于后面测试相应的函数。 原文件 test.c
void SLTest() {SLNode* Node1 (SLNode*)malloc(sizeof(SLNode));Node1-data 1;SLNode* Node2 (SLNode*)malloc(sizeof(SLNode));Node1-data 2;SLNode* Node3 (SLNode*)malloc(sizeof(SLNode));Node1-data 3;SLNode* Node4 (SLNode*)malloc(sizeof(SLNode));Node1-data 4;
}Node1-next Node2;Node2-next Node3;Node3-next Node4;Node4-next NULL;建立了四个节点但是它们现在彼此之间还没有联系就是孤零零的四个节点此时我们用next指针把它们给串联起来。整体效果图就是这样 某个节点的指针域保存的是下一个节点的地址 打印链表
我们来写一个函数打印链表中存放的数据。
void SLPrint(SLNode* phead) {SLNode* pcur phead;while (pcur) {printf(%d -, pcur-data);pcur pcur-next; //pcur原先指向某个节点现在让它指向下一个节点}printf(NULL\n);
}这里解释下为什么要用一个pcur保存第一个节点的地址因为你如果用phead的话那到时phead在循环中就会不断往前走直到它为NULL也就是说循环结束以后phead就是空指针了那你就再也找不到链表中各个节点的地址了。 所以我们不难看出链表是通过地址的赋值从上一个节点走到下一个节点
接下来也是和顺序表差不多有头插、尾插的操作执行插入操作时我们需要申请新节点为了避免重复让代码简洁一点我们可以写一个申请新节点的函数。
SLNode* SLBuyNode(SLTypeDate x) { //申请一个节点并将想要存储的数据存进去SLNode* node (SLNode*)malloc(sizeof(SLNode));node-data x;node-next NULL;return node;
}插入和删除
老规矩还是分为头插和尾插还有随便插先来写个尾插
尾插 我们首先得找到最后一个节点然后把它的next指针改为node的地址代码如下该说的基本都在注释讲了主要来说一下 while 循环的终止条件。 如果循环终止条件是pcur NULL 的话那就跑过头了此时pcur就成空指针。
void SLPushBack(SLNode** pphead,SLTypeDate x) {assert(pphead);SLNode* node SLBuyNode(x);if (*pphead NULL) { //phead为空说明此时链表为空,那就直接插入*pphead node; //让node是第一个节点的地址return;}//若不为空则先找到链表的最后一个节点再插入SLNode* pcur *pphead; //老样子用临时变量pcur去走循环while (pcur-next) {pcur pcur-next;}//此时pcur指向最后一个节点pcur-next node;
}
如果你指针部分的知识学得很扎实那你一眼就可以看出这段代码有问题了。 这样写问题出在哪里呢问题在于你传的参数你觉得把实参传给这个phead是传值调用还是传址调用显然是传值因为实参虽然是节点的地址但是它本质上是一个值你传过来给 phead 的只是一个值而已任你怎么改变phead都与实参无关。而在这个函数中如果你进行尾插时链表为空那node的值只给到了phead无法影响到实参。 要解决问题的话改为传二级指针就ok了。 而如果链表不为空那就没啥影响了因为此时你只需改变 next 无需改变实参。传值确实没问题但是为了形式上的统一避免一下子是一级指针一下子又是二级指针所以也传二级指针。 phead 是一级指针那么二级指针我们就记为pphead把原本的phead改为 *pphead就ok了。同时我们需要对 pphead 进行断言因为它为空的话那就不能解引用。 所以正确的代码如下
void SLPushBack(SLNode** pphead,SLTypeDate x) {assert(pphead); //进行断言防止传过来的指针为空SLNode* node SLBuyNode(x);if (*pphead NULL) { //phead为空说明此时链表为空,那就直接插入*pphead node; //让node是第一个节点的地址return;}//若不为空则先找到链表的最后一个节点再插入SLNode* pcur *pphead; //老样子用临时变量pcur去走循环while (pcur-next) {pcur pcur-next;}//此时pcur指向最后一个节点pcur-next node;
}头插
头插就很简单了不用考虑顺序表为不为空。
void SLPushFront(SLNode** pphead, SLTypeDate x) {assert(pphead);SLNode* node SLBuyNode(x);node-next *pphead;*pphead node;
} 尾删
尾删需要完成2个任务①释放掉最后一个节点的空间②将倒数第二个节点的 next 指针置为空。 最后一个节点这个好找那倒数第二个呢请看下面代码
void SLPopBack(SLNode** pphead,SLTypeDate x) {assert(pphead);assert(*pphead); //如果节点地址为空那么说明节点为空为空说明没有指向而节点为空时显然不能删除SLNode* prev NULL;SLNode* ptail *pphead;if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;return;}while (ptail-next) {prev ptail;ptail ptail-next;}prev-next ptail-next;free(ptail);ptail NULL;
}
}我这次弄了两个指针prev和ptailptail经过循环最终指向最后一个节点而prev则是指向倒数第二个节点。可以看到每次循环我在把下一个节点地址赋给 ptail之前就把当下ptail 保存到prev这样在最后一次循环时 prev 就在倒二了。 然后 if 语句里面的是只有一个节点的情况为什么要单独把它拿出来讨论呢因为如果没有这个 if 语句那么此时 prev 就是NULL它不能解引用去访问节点里面的 next更何况此时还是一个空节点。 释放最后一个节点之后一定要把它的地址置为空你如果不置空在尾删这个函数里面确实没问题但是在打印链表的函数中循环的终止条件是pcur为空当pcur走到被删掉的节点时因为地址不为空所以会把这里的东西打印出来。 释放掉某块空间只是把里面的数据给释放掉但是那块空间仍然存在 头删
头删的思路就是把第一个节点释放掉把 phead*pphead 给到原先的第二个节点
void SLPopFront(SLNode** pphead) {assert(pphead);assert(*pphead);SLNode* pcur *pphead;*pphead (*pphead)-next;free(pcur);pcur NULL;
}这里 pcur 可以不置为空但出于代码规范所以置空。 指定位置之前插入
既然要在某位置前插入那就得先找到这个位置怎么找呢当然是循环遍历了先来写下找到我们想要的节点的函数
SLNode* SLFindNode(SLNode** pphead, SLTypeDate x) {assert(pphead);SLNode* pcur *pphead;while (pcur) {if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL; //找不到就返回空指针
}然后可以写插入的函数了
void SLInsert(SLNode** pphead, SLNode* pos, SLTypeDate x) {assert(pphead);assert(*pphead);assert(pos);SLNode* node SLFindNode(*pphead,pos);SLNode* prev *pphead;if (*pphead pos) { //只有一个节点或插入位置位于第一个节点之前的情况node-next *pphead;*pphead node;return;}//多个节点的情况while (prev-next ! pos) {prev prev-next;}node-next pos;prev-next node;
}注你画图就会发现只有一个节点or插入第一个节点之前的位置这两种情况下 pos 和 *pphead 都指向第一个节点。 指定位置之后插入
这个就比上面那个简单多了因为现在pos节点已知那就少了遍历的过程。pos后面的节点可以通过 next 找到但是pos之前的节点只能遍历得到 不过这次需要注意的插入的次序比如现在节点node和pos已知插入时应该先让node的next指向第三个节点然后再让 pos 的 next 指向 node如果反过来的话那第三个节点可就找不到了即pos-next 这个函数的实现很简单的你自己尝试一下。 删除指定节点
如图要删除pos这个节点 首先我们得找到pos前面的节点 prev然后让prev-next pos-next完事之后这个pos就没啥“利用价值”了把它 free 掉。 不过前面做了这么多个接口之后你应该也会考虑到一些特殊情况比如要删除的pos就是第一个节点。
这种情况下我们就先弄一个pcur 保存第一个节点的地址然后*pphead (*pphead)-next再把pcur指向的空间free掉并置空。 这里有一个要注意的点解引用操作符优先度比“-”低所以要用括号给括起来不然会报错。
void SLErase(SLNode** pphead, SLNode* pos) {assert(*pphead);assert(pphead);assert(pos);if (*pphead pos) {*pphead (*pphead)-next;free(pos);pos NULL;return;}SLNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}销毁
使用完之后就要把链表给销毁了。
void SLDestroy(SLNode** pphead) {assert(pphead);SLNode* pcur *pphead;while (*pphead) {pcur *pphead;*pphead (*pphead)-next;free(pcur);pcur NULL;}
}源码
头文件声明部分
#pragma once
#includestdlib.h
#includestdio.h
#includeassert.htypedef int SLTypeDate;
typedef struct SListNode {SLTypeDate data;struct SListNode* next;
}SLNode;void SLPrint(SLNode* phead);void SLPushBack(SLNode** pphead, SLTypeDate x);void SLPushFront(SLNode** pphead, SLTypeDate x);void SLPopFront(SLNode** pphead);void SLPopBack(SLNode** pphead);void SLInsert(SLNode** pphead, SLNode* pos, SLTypeDate x);SLNode* SLFindNode(SLNode** pphead, SLTypeDate x);void SLInsertAfter(SLNode* pos, SLTypeDate x);void SLErase(SLNode** pphead, SLNode* pos);void SLDestroy(SLNode** pphead);源文件功能实现部分
#includeSList.hvoid SLPrint(SLNode* phead) {SLNode* pcur phead;while (pcur) {printf(%d -, pcur-data);pcur pcur-next;}printf(NULL\n);
}SLNode* SLBuyNode(SLTypeDate x) { //申请一个节点并将想要存储的数据存进去SLNode* node (SLNode*)malloc(sizeof(SLNode));node-data x;node-next NULL;return node;
}void SLPushBack(SLNode** pphead,SLTypeDate x) {assert(pphead);SLNode* node SLBuyNode(x);if (*pphead NULL) { //phead为空说明此时链表为空,那就直接插入*pphead node; //让node是第一个节点的地址return;}//若不为空则先找到链表的最后一个节点再插入SLNode* pcur *pphead; //老样子用临时变量pcur去走循环while (pcur-next) {pcur pcur-next;}//此时pcur指向最后一个节点pcur-next node;
}void SLPushFront(SLNode** pphead, SLTypeDate x) {assert(pphead);SLNode* node SLBuyNode(x);node-next *pphead;*pphead node;
}void SLPopBack(SLNode** pphead) {assert(pphead);assert(*pphead); //如果节点地址为空那么说明节点为空为空说明没有指向而节点为空时显然不能删除SLNode* prev NULL;SLNode* ptail *pphead;if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;return;}while (ptail-next) {prev ptail;ptail ptail-next;}free(ptail);ptail NULL;
}void SLPopFront(SLNode** pphead) {assert(pphead);assert(*pphead);SLNode* pcur *pphead;*pphead (*pphead)-next;free(pcur);//pcur (*pphead)-next;//free(*pphead);//*pphead pcur;pcur NULL;
}SLNode* SLFindNode(SLNode** pphead, SLTypeDate x) {assert(pphead);SLNode* pcur *pphead;while (pcur) {if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL; //找不到就返回空指针
}//在指定位置前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLTypeDate x) {assert(pphead);assert(*pphead);assert(pos);SLNode* node SLFindNode(*pphead,pos);SLNode* prev *pphead;if (*pphead pos) { //只有一个节点或插入位置位于第一个节点之前的情况node-next *pphead;*pphead node;return;}//多个节点的情况while (prev-next ! pos) {prev prev-next;}node-next pos;prev-next node;
}void SLInsertAfter(SLNode* pos, SLTypeDate x) {assert(pos);SLNode* node SLBuyNode(x);node-next pos-next;pos-next node;
}void SLErase(SLNode** pphead, SLNode* pos) {assert(*pphead);assert(pphead);assert(pos);if (*pphead pos) {*pphead (*pphead)-next;free(pos);pos NULL;return;}SLNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}prev-next pos-next;free(pos);pos NULL;}void SLDestroy(SLNode** pphead) {assert(pphead);SLNode* pcur *pphead;while (*pphead) {pcur *pphead;*pphead (*pphead)-next;free(pcur);pcur NULL;}
}
