网站空间购买官方,网站建设完成汇报,html底部友情链接代码,wordpress thinkphp相关代码gitee自取#xff1a;
C语言学习日记: 加油努力 (gitee.com)
接上期#xff1a;
【数据结构初阶】二、 线性表里的顺序表_高高的胖子的博客-CSDN博客 引言 通过上期对顺序表的介绍和使用 我们可以知道顺序表有以下优点和缺点#xff1a; 顺序表优点 尾插 和 尾…
相关代码gitee自取
C语言学习日记: 加油努力 (gitee.com) 接上期
【数据结构初阶】二、 线性表里的顺序表_高高的胖子的博客-CSDN博客 引言 通过上期对顺序表的介绍和使用 我们可以知道顺序表有以下优点和缺点 顺序表优点 尾插 和 尾删 操作足够快 能够使用下标的随机访问和修改这是很方便的 ----------------------------------------------------------------------------------------------- 顺序表缺点 头部/中间的插入和删除操作较慢时间复杂度为O(N) 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长势必会有一定的空间浪费。 例如 当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 下面将要介绍和实现的链表就不会出现这些问题 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 1 . 链表 1. 链表的概念及结构 链表的概念 链表是一种物理存储结构上非连续、非顺序的存储结构 数据元素的逻辑顺序是通过链表中的指针链接次序实现的单链表一般不会单独使用 只有头插和头删实现简单且效率高 链表的结构 链表也属于线性表线性表在物理上存储时 通常以数组顺序表和链式结构链表的形式存储链式结构在逻辑上是连续的但在物理上不一定连续 现实中的结点一般是从堆上申请出来的 从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 图示 2. 链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构 单向 或 双向 链表 单向链表图示 双向链表图示 --------------------------------------------------------------------------------------------- 带头(哨兵位) 或 不带头(哨兵位) 链表 带头链表图示 不带头链表图示 --------------------------------------------------------------------------------------------- 循环 或 非循环 链表 循环链表图示 非循环链表图示 虽然有这么多的链表的结构 但是我们实际中最常用还是两种结构 无头单向非循环链表 和 带头双向循环链表 3. 两种常用链表结构 无头单向非循环链表 简介 结构简单一般不会单独用来存数据。 实际中更多是作为其他数据结构的子结构 如哈希桶、图的邻接表等等。 另外这种结构在笔试面试中出现很多。 图示 --------------------------------------------------------------------------------------------- 带头双向循环链表 简介 结构最复杂一般用在单独存储数据。 实际中使用的链表数据结构都是带头双向循环链表。 另外这个结构虽然结构复杂 但是使用代码实现以后会发现结构会带来很多优势实现反而简单了 图示 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 2 . 链表的实现 无头单向非循环链表 详细解释在图片的注释中代码分文件放最后 实现具体功能前的准备工作 创建单链表数据类型 -- 链表结点中数据域里存储的数据的类型 创建单链表结点结构体(类型) -- 结点中应有 数据域 和 指针域 图示 --------------------------------------------------------------------------------------------- PrintSList函数 -- 遍历打印链表 需要使用到链表头指针phead为了后续使用又不能改变头指针所以要代替头指针 因为链表到最后结点里指针域的NULL(0x00000000)才结束 所以可以使用while循环进行遍历并打印 最后提示已指向NULL指针链表遍历结束 图示 --------------------------------------------------------------------------------------------- SLTNode函数 -- 生成链表的结点 开辟结点所需的动态空间要注意一个结点大小要看数据域和指针域的大小 检查空间是否开辟成功 将要放入结点数据域的数据放入 设置新创建结点的指针域 返回创建的新结点的指针地址 图示 测试 -- PrintSList、SLTNode函数 --------------------------------------------------------------------------------------------- SLTPushBack函数难 -- 向链表尾部插入一个结点尾插 因为要插入一个结点所以先使用BuySListNode函数创建一个结点 尾插时要判断链表是否已经有结点 如果没有结点 则将新创建结点的地址赋给头指针 因为是对指针本身进行操作所以用二级指针对头指针进行操作 如果已经有了结点 则先创建一个指针替代头指针 这里是对头指针直线的结点结构体进行操作所以用指针就够了不需要二级指针 再使用while循环获得最后一个结点的地址 最后将尾插的结点连接起来 图示 可以结合单链表物理图来理解 ↓↓↓↓ 测试 -- SLTPushBack函数 --------------------------------------------------------------------------------------------- SLTPushFront函数 -- 向链表头部插入一个结点头插 因为要插入一个结点所以先使用BuySListNode函数创建一个结点 使用plist把原本头结点地址赋给新插入头结点指针域 再把头指针改为指向新插入头结点 图示 测试 -- SLTPushFront函数 --------------------------------------------------------------------------------------------- SLTPopBack函数 -- 删除链表尾部结点尾删 链表尾删要考虑三种情况第一种情况链表为空没有任何结点 这种情况直接assert断言即可 第二种情况链表只有一个结点 这种情况要释放掉唯一的结点 第三种情况链表有一个以上结点 这种情况需要两个指针来进行操作 图示 测试 -- SLTPopBack函数 --------------------------------------------------------------------------------------------- SLTPopFront函数 -- 删除链表头部结点头删 头删分两种情况就够了空链表 和 非空链表 空链表头删 直接assert断言pass掉莫名戳中笑点哈哈哈哈哈哈哈哈 非空链表头删 先通过plist头指针获得第二个结点地址方便头删后让原本的第二个结点做新的头结点 再free释放掉头指针 最后让plist头指针指向原本的第二个结点做新的头结点 图示 测试 -- SLTPopFront函数 --------------------------------------------------------------------------------------------- SLTFind函数 -- 查找指定值(x)所在结点的地址 创建一个变量代替头指针 使用while循环在链表中进行遍历查找指定值(x) 图示 测试 -- SLTFind函数 --------------------------------------------------------------------------------------------- SLTInsert函数 -- 在链表指定位置(pos)之前插入一个值(x) 分三种情况讨论链表为空(空链表)、在第一个结点前插入(头插)、非头插 链表为空 直接assert断言pass掉 在第一个结点前插入(头插)复用头插SLTPushFront函数进行插入 非头插 使用链表头指针找到pos结点的前一个结点地址prev再创建一个新结点newnode 将新结点newnode插入pos结点之前prev结点之后 图示 测试 -- SLTInsert函数 --------------------------------------------------------------------------------------------- SLTInsertAfter函数 -- 在链表指定位置(pos)之后插入一个值(x) 如果接收的pos结点地址为空无法继续操作 要用assert断言继续处理 因为要在链表中插入一个值 所以要用BuySListNode函数新增一个结点 先让newnode结点的指针域next指向后一个结点 再让pos结点指向newnode结点将链表连接起来 图示 测试 -- SLTInsertAfter函数 --------------------------------------------------------------------------------------------- SLTErase函数 -- 在链表删除指定位置(pos)结点 为防止要删的pos结点指针为空指针使用assert断言 分两种情况头删 和 非头删 头删 直接复用头删SLTPopFront函数 非头删找到pos结点的前一个结点prev 将 prev结点 和 pos结点后一个结点 连接起来 最后释放(删除)pos结点完成删除操作 图示 测试 -- SLTErase函数 --------------------------------------------------------------------------------------------- SLTEraseAfter函数 -- 在链表删除指定位置(pos)之后一个结点 先使用assert断言分别排除pos结点指针为空和pos结点为尾结点的情况 我们是删除pos结点的后一个结点 如果pos为尾结点就会无法操作 将要删除的pos结点下个结点posNext地址先保存起来 再把pos结点和下下个结点连接起来 最后释放删除posNext结点 图示 测试 -- SLTEraseAfter函数 --------------------------------------------------------------------------------------------- SLTDestroy函数 -- 销毁链表释放开辟的动态空间 因为链表释放后还要把头指针plist给置为空要操作到plist所以要用到二级指针 进行assert断言pphead二级指针不为空 以上函数中参数带二级指针pphead的都需要进行此操作 创建一个指针进行遍历释放空间 最后将链表头指针置为空 图示 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 3 . 对应代码 SList.h -- 单链表头文件 //链表头文件
#pragma once//先包含之后要用到的头文件
#include stdio.h
#include stdlib.h
#include assert.h//重命名一个单链表数据类型
typedef int SLTDataType;
//SLT -- single link table//创建一个单链表结点结构体
//这里数据域是int类型4字节指针域指针也是4个字节
//所以一个结点就是8个字节
typedef struct SListNode
{//结点数据域SLTDataType data;//结点指针域//因为是指向单链表结点结构体的指针//所以是单链表结点结构体类型的指针struct SListNode* next;//第一个结点要找到第二个结点物理空间不连续//通过上个结点指向下个结点实现逻辑连续}SLTNode; //将struct SListNode重命名为SLTNode//创建遍历打印单链表的函数 -- 接收单链表头指针
void PrintSList(SLTNode* phead);//创建生成结点的函数 -- 接收要存入结点数据域的数据返回该结点的指针
SLTNode* BuySListNode(SLTDataType x);//创建尾插函数 --
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushBack(SLTNode** pphead, SLTDataType x);//创建头插函数 --
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushFront(SLTNode** pphead, SLTDataType x);//创建尾删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopBack(SLTNode** pphead);//创建头删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopFront(SLTNode** pphead);//创建查找函数 --
//查找指定值(x)所在结点的地址
//接收 链表头指针phead、查找值x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//创建指定位置插入函数1 --
//在链表指定位置(pos)之前插入一个值(x)
//接收 链表头指针地址pphead、指定结点指针pos、插入值x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//创建指定位置插入函数2 --
//在链表指定位置(pos)之后插入一个值(x)
//接收 指定结点指针pos、插入值x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//创建删除指定结点函数1 --
//在链表删除指定位置(pos)结点
///接收 链表头指针地址pphead、指定结点指针pos
void SLTErase(SLTNode** pphead, SLTNode* pos);//创建删除指定结点函数2 --
//在链表删除指定位置(pos)之后一个结点
//接收 指定结点指针pos
void SLTEraseAfter(SLTNode* pos);//创建销毁链表函数
void SLTDestroy(SLTNode** pphead); --------------------------------------------------------------------------------------------- SList.c -- 单链表函数实现文件 //链表实现文件
#define _CRT_SECURE_NO_WARNINGS 1//包含链表头文件
#include SList.h//创建遍历单链表的函数接收单链表结点的头指针
void PrintSList(SLTNode* phead)
{//phead头指针指向第一个结点//之后还要多次使用phead头指针//所以不要改变phead头指针//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针SLTNode* cur phead;//因为链表到最后结点的指针域为NULL才结束//所以只要cur不为NULL就继续遍历结点进行打印while (cur ! NULL){//通过cur当前指向的结点打印cur里数据域的内容printf(%d-, cur-data);//通过结点里指针域指向下一个结点方便打印下个结点的数据域内容cur cur-next;}//最后提示已指向NULL指针链表遍历结束printf(NULL\n);
}//创建生成结点的函数 -- 接收要存入结点数据域的数据返回该结点的指针
SLTNode* BuySListNode(SLTDataType x)
{//给结点开辟动态空间注意开辟空间的大小是SLTNode结点的大小--8个字节SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode)); //返回该结点地址//检查是否开辟成功if (newnode NULL) //返回空指针说明开辟失败{//打印错误信息perror(malloc fail);//开辟失败直接退出程序exit(-1);}//将接收的值x赋给该结点的数据域newnode-data x;//设置新创建结点的指针域//因为是最新的结点即最尾部的结点//所以指针域的指针应是NULL(链表末尾结束)//之后通过指针域连接各个结点的操作要看情况操作先都初始化为NULLnewnode-next NULL;//返回该新结点的指针地址return newnode;
}//创建尾插函数
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//改变结构体要用结构体指针//改变结构体指针要用结构体指针的指针二级指针//因为pphead二级指针存储的是plist指针//plist指针指向的值可能为空但指针的地址不能为空//pphead是plist的地址正常情况下一定不为空assert(pphead);//先使用newnode函数为要尾插的值创建一个结点//并返回该结点地址SLTNode* newnode BuySListNode(x);//判断phead是否是NULL如果是说明链表还没开辟过一个结点if (*pphead NULL){//如果为空则将上面开辟的newnode结点地址赋给phead*pphead newnode;//要改变结构体的指针就要用二级指针//这里pphead是二级指针存放链表头指针plist的地址//因为如果用一级指针SLTNode* phead的话//phead形参只是plist实参的临时拷贝两者空间相互独立//改变phead的话不会改变plistplist还会是空指针//所以要用二级指针pphead存放plist指针的地址//*pphead解引用就能得到一级指针plist,//即 *pphead plist//所以实际上上面的代码就相当于plist newnode//这样就让本来指向空指针的头指针指向了新创建的结点指针//链表就能够连接起来}else//不为空则往尾部插入新结点{//创建另一个指针存放单链表头指针SLTNode* tail *pphead; //*pphead plist//使用while循环获得最后一个结点的地址while (tail-next ! NULL)//如果下个结点的next指针域不为NULL//则继续往后找直到tail等于最后结点的地址{//把当前结点指针域里下个结点的地址给到tail//进行while循环下次判断tail tail-next;}//tail找到最后结点地址后//把尾插的新结点地址给到tail的next指针域//连接起链表tail-next newnode;//要改变结构体用结构体的指针即可//因为newnode、tail、pphead都是临时(局部)变量//所以函数运行结束后都会销毁//但malloc函数开辟的空间(结点)都在堆上不会销毁//通过解引用二级指针pphead改变plist也没有问题}
}//创建头插函数 --
//使用二级指针接收单链表头指针的地址 和 接收要插入的值
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{//因为pphead二级指针存储的是plist指针//plist指针指向的值可能为空但指针的地址不能为空//pphead是plist的地址正常情况下一定不为空assert(pphead);//先使用newnode函数为要头插的值创建一个结点//并返回该结点地址SLTNode* newnode BuySListNode(x);//因为也要用到链表头指针本身所以也要使用二级指针//因为plist指向原本头结点地址//所以可以使用plist把原本头结点地址赋给新插入头结点指针域newnode-next *pphead;//再把头指针改为指向新插入头结点*pphead newnode;
}//创建尾删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopBack(SLTNode** pphead)
{//尾删需要考虑三种情况//注*pphead 就是 plist//因为pphead二级指针存储的是plist指针//plist指针指向的值可能为空但指针的地址不能为空//pphead是plist的地址正常情况下一定不为空assert(pphead);// 第一种情况链表为空 -- 没有任何结点//没有结点那就删不了了使用assert接收到空指针就报警告assert(*pphead);// 第二种情况链表只有一个结点if ((*pphead)-next NULL)// - 也是解引用(结构体的)优先级比 * 高//所以 *pphead 要用() 括起来{//只有一个结点又要尾删那就直接把这唯一的结点删掉free(*pphead); //直接free释放掉plist指向的结点//再把释放掉的plist置为空指针防止成为野指针*pphead NULL;}else// 第三种情况链表有一个以上结点{//这种情况额外两个指针//一个tail指针 -- 用来找到最后一个结点地址并将其释放//还有一个tailPrev指针 -- 指向tail指针的前一个结点地址//用来改变该结点的指针域//防止原本指向tail结点的指针域变成野指针//先替代头指针plistSLTNode* tail *pphead;//创建tailPrev指针//之后操作会指向tail结点的前一个结点//即倒数第二个结点SLTNode* tailPrev NULL;//再使用while循环找到尾结点//和尾插的操作类似while (tail-next ! NULL){//tail查找之前先把当前指向结点地址给tailPrev//这样最后tail会指向尾结点//tailPrev会指向倒数第二个结点tailPrev tail;tail tail-next;}//结束while循环后tail指向尾结点地址//因为是尾删所以free释放掉tail就可以“删掉”尾结点free(tail);//因为tail是局部临时变量出了函数就销毁//所以不置为指针也可以不用担心成为野指针//删除原尾结点后倒数第二个结点成为尾结点//要把其指针域next置为空指针成为链表新结尾tailPrev-next NULL;}
}//创建头删函数 --
//使用二级指针接收单链表头指针的地址
void SLTPopFront(SLTNode** pphead)
{//因为pphead二级指针存储的是plist指针//plist指针指向的值可能为空但指针的地址不能为空//pphead是plist的地址正常情况下一定不为空assert(pphead);//分两种情况//第一种情况链表里没有结点空链表//没有结点可以删直接assert断言pass掉assert(*pphead);//第二种情况链表有一个和多个结点非空链表//因为是删掉头结点所以不用考虑找尾结点//所以不用细分一个或多个结点的情况//这种情况要先通过plist拿到第二个结点的地址SLTNode* newhead (*pphead)-next;//使用newhead存储第二个结点地址//拿到第二个结点地址后再释放掉头结点//实现头删效果free(*pphead);//这时要让第二个结点成为新的头结点*pphead newhead; //头指针指向原本的第二个结点
}//创建查找函数 --
//查找指定值(x)所在结点的地址
//接收 链表头指针phead、查找值x
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//像SLTFind和PrintSList函数只用头指针遍历//不改变指针本身就不需要用到二级指针//创建个变量代替头指针SLTNode* cur phead;//使用while循环对链表进行遍历查找while (cur ! NULL)//只要cur指针指向地址不为空就继续循环
//while遍历时(cur-next ! NULL) 和 (cur ! NULL) 的区别
//(cur-next ! NULL)这个条件最后cur会是最后结点的地址
//(cur ! NULL)这个条件最后cur会是NULL
//(cur-next ! NULL) 会比 (cur ! NULL) 少一次循环{//遍历过程中依次查找各结点数据域数据是否与x相同if (cur-data x){//找到了一个结点数据域数据是x返回该结点地址return cur;}//这里如果while循环的条件是(cur-next ! NULL)//最后一个结点进不来不能判断最后结点数据域数据是不是xcur cur-next; //改变循环条件指向下个结点}//如果能指向到这说明没找到返回NULLreturn NULL;
}//创建指定位置插入函数1 --
//在链表指定位置(pos)之前插入一个值(x)
//接收 链表头指针地址pphead、指定结点指针pos、插入值x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{//因为pphead二级指针存储的是plist指针//plist指针指向的值可能为空但指针的地址不能为空//pphead是plist的地址正常情况下一定不为空assert(pphead);//第一种情况空指针//先排除空指针的情况assert(pos);//第二种情况头插if (pos *pphead)// *pphead plist//如果pos是pphead即第一个指针//则在第一个指针前插入一个值相当于头插{//直接复用头插函数SLTPustFrontSLTPushFront(pphead, x);//直接传pphead二级指针过去}else//第三种情况非头插{//从头开始找pos结点的前一个结点//先获得头指针SLTNode* prev *pphead;//当前结点的指针域不是指向pos结点则继续循环while (prev-next ! pos){prev prev-next;}//此时prev已指向pos结点的前一个结点//为要插入的结点创建一个结点newnode//插入位置是pos结点之前prev结点之后SLTNode* newnode BuySListNode(x);//让prev结点指针域指向新插入结点地址prev-next newnode;//newnode结点指针域指向pos结点newnode-next pos;//此时newnode新结点就插入完成了}
}//创建指定位置插入函数2 --
//在链表指定位置(pos)之后插入一个值(x)
//接收 指定结点指针pos、插入值x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//因为是在pos结点后插入一个值(结点)//所以不可能会有头插的情况那就不需要头指针plist//pos指针存储结点地址可能会接收到空指针//使用assert断言pass掉assert(pos);//先为插入值创建一个新结点newnodeSLTNode* newnode BuySListNode(x);//先让newnode的指针域next指向后一个结点//这里后一个结点就是pos结点指针域里的地址//因为未插入前pos就是指向后一个地址newnode-next pos-next;//再让pos的指针域next指向newnodepos-next newnode;
}//创建删除指定结点函数1 --
//在链表删除指定位置(pos)结点
///接收 链表头指针地址pphead、指定结点指针pos
void SLTErase(SLTNode** pphead, SLTNode* pos)
{//因为pphead二级指针存储的是plist指针//plist指针指向的值可能为空但指针的地址不能为空//pphead是plist的地址正常情况下一定不为空assert(pphead);//防止要删的pos结点指针为空指针//使用assert断言assert(pos);//分两种情况// 1.头删if (pos *pphead)//pos结点 头结点 -- 头删{//直接复用SLTPopFront头删函数SLTPopFront(pphead);}else// 2.非头删//尾删不用单独分出一种情况因为还得判断是不是尾结点//直接用通用逻辑删除也可以处理尾删的情况{//从头开始找pos结点的前一个结点//先获得头指针SLTNode* prev *pphead;//当前结点的指针域不是指向pos结点则继续循环while (prev-next ! pos){prev prev-next;}//此时prev已指向pos结点的前一个结点//因为要删除pos结点//所以要让pos前一个和后一个结点连接起来prev-next pos-next;//连接成功后再把pos结点释放实现删除效果free(pos);}
}//创建删除指定结点函数2 --
//在链表删除指定位置(pos)之后一个结点
//接收 指定结点指针pos
void SLTEraseAfter(SLTNode* pos)
{//删除pos结点后的一个结点//那么就不可能出现头删的情况//pos结点是尾结点也没用//因为尾结点后就没有结点可以删了//使用assert断言处理assert(pos); //防止接收“空结点”assert(pos-next); //防止接收尾结点//将要删的pos结点的下个结点posNext先保存起来SLTNode* posNext pos-next;//再把pos结点和下下个结点连接起来pos-next posNext-next;//posNext的指针域next就是pos结点的下下个结点地址//最后释放(删除)posNext结点free(posNext);
}//创建销毁链表函数
void SLTDestroy(SLTNode** pphead)
{//因为链表释放后还要把头指针plist给置为空//要操作到plist所以要用到二级指针//plist指向空链表pphead也不能为空assert(pphead);//创建一个指针进行遍历SLTNode* cur *pphead;//*pphead plist//进行遍历释放while (cur ! NULL){//创建一个指针保存下个结点地址SLTNode* next cur-next;//释放当前结点free(cur);//cur指针移向下一个结点cur next;}//将链表头指针置为空*pphead NULL;
} --------------------------------------------------------------------------------------------- test.c -- 单链表测试文件 //链表测试文件
#define _CRT_SECURE_NO_WARNINGS 1/* 链表学习引入小测试#include stdio.h//重命名一个单链表数据类型
typedef int SLTDataType;
//SLT -- single link table//创建一个单链表结点结构体
typedef struct SListNode
{//结点数据域SLTDataType data; //结点指针域//因为是指向单链表结点结构体的指针//所以是单链表结点结构体类型的指针struct SListNode* next; }SLTNode; //将struct SListNode重命名为SLTNode//创建遍历单链表的函数接收单链表结点的头指针
void PrintSList(SLTNode* phead)
{//phead头指针指向第一个结点//之后还要多次使用phead头指针//所以不要改变phead头指针//所以可以创建一个和phead头指针一样类型的指针cur代替phead头指针SLTNode* cur phead;//因为链表到最后结点的指针域为NULL才结束//所以只要cur不为NULL就继续遍历结点进行打印while (cur ! NULL){//通过cur当前指向的结点打印cur里数据域的内容printf(%d-, cur-data);//通过结点里指针域指向下一个结点方便打印下个结点的数据域内容cur cur-next;}//最后提示已指向NULL指针链表遍历结束printf(NULL\n);
}int main()
{//创建单链表结点SLTNode* n1 (SLTNode*)malloc(sizeof(SLTNode));n1-data 10; //在该结点数据域存放数据SLTNode* n2 (SLTNode*)malloc(sizeof(SLTNode));n2-data 20; //在该结点数据域存放数据SLTNode* n3 (SLTNode*)malloc(sizeof(SLTNode));n3-data 30; //在该结点数据域存放数据n1-next n2; //n1的指针域指向结点n2n2-next n3; //n2的指针域指向结点n3n3-next NULL; //n3的指针域指向NULL(结束)PrintSList(n1); //调用函数打印单链表return 0;
}*///包含链表头文件
#include SList.h//测试函数1测试--PrintSList、BuySListNode函数
void TestList1()
{int n; //存放链表长度//打印提示信息printf(请输入链表的长度);//接收链表长度scanf(%d, n); //打印提示信息printf(\n请依次输入每个结点的值);SLTNode* plist NULL; //链表头指针一开始链表没数据所以为NULL//使用for循环循环创建结点并赋值形成链表for (int i 0; i n; i){int val; //存放结点数据域数据scanf(%d, val); //接收结点数据域数据//使用BuySListNode函数创建结点并给数据域赋值:SLTNode* newnode BuySListNode(val);//头插: 使用头插把链表连接起来//把链表头指针plist指向的头结点地址赋给新创建结点的指针域next//这样新结点的指针域next就能指向原来的头结点地址newnode-next plist;//再把新创建结点的地址赋给头指针//这样头指针就指向了新创建结点地址让其成为新的头结点plist newnode;}//使用PrintSList函数打印链表PrintSList(plist); //接收头指针后打印//使用SLTPushBack函数手动向链表尾部插入数据尾插SLTPushBack(plist, 10000);//再使用PrintSList函数打印插入后的链表PrintSList(plist);//plist和phead都是单链表头指针//但 plist是实参 phead是形参//phead 是 plist 的一份临时拷贝
}//测试函数2测试--SLTPushBack、SLTPushFront函数
void TestList2()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPushBack(plist, 5);//使用头插随机插入几个值SLTPushFront(plist, 10);SLTPushFront(plist, 20);SLTPushFront(plist, 30);SLTPushFront(plist, 40);//使用SLTPrintf函数打印该链表PrintSList(plist);
}//测试函数3测试--SLTPopBack尾删函数
void TestList3()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(尾删前链表\n);PrintSList(plist);//使用尾删函数SLTPopBack(plist);//使用SLTPrintf函数打印该链表printf(尾删后链表\n);PrintSList(plist);SLTPopBack(plist);//使用SLTPrintf函数打印该链表printf(尾删后链表\n);PrintSList(plist);SLTPopBack(plist);//使用SLTPrintf函数打印该链表printf(尾删后链表\n);PrintSList(plist);SLTPopBack(plist);//使用SLTPrintf函数打印该链表printf(尾删后链表\n);PrintSList(plist);//使用SLTPrintf函数打印该链表printf(尾删后链表\n);PrintSList(plist);
}//测试函数4测试--SLTPopFront头删函数
void TestList4()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(头删前链表\n);PrintSList(plist);SLTPopFront(plist);//使用SLTPrintf函数打印该链表printf(头删后链表\n);PrintSList(plist);SLTPopFront(plist);//使用SLTPrintf函数打印该链表printf(头删后链表\n);PrintSList(plist);SLTPopFront(plist);//使用SLTPrintf函数打印该链表printf(头删后链表\n);PrintSList(plist);SLTPopFront(plist);//使用SLTPrintf函数打印该链表printf(头删后链表\n);PrintSList(plist);
}//测试函数5测试 -- SLTFind函数
void TestList5()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(操作前链表\n);PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点的地址SLTNode* pos SLTFind(plist, 1);if (pos ! NULL){ //找到了可以对该结点进行修改pos-data * 10;//所以SLTFind查找函数可以负责查找和修改的操作}printf(操作后链表\n);PrintSList(plist);
}//测试函数6测试 -- SLTInsert函数
void TestList6()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(操作前链表\n);PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点的地址SLTNode* pos SLTFind(plist, 2);if (pos ! NULL){int x; //接收要插入的值scanf(%d, x); //输入要插入的值SLTInsert(plist, pos, x); //在2前面插入x }printf(操作后链表\n);PrintSList(plist);
}//测试函数7测试 -- SLTInsertAfter函数
void TestList7()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(操作前链表\n);PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点d的地址SLTNode* pos SLTFind(plist, 2);if (pos ! NULL){int x; //接收要插入的值scanf(%d, x); //输入要插入的值SLTInsertAfter(pos, x); //在2后面插入x }printf(操作后链表\n);PrintSList(plist);
}//测试函数8测试 -- SLTErase函数
void TestList8()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(操作前链表\n);PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点d的地址SLTNode* pos SLTFind(plist, 2);if (pos ! NULL){int x; //接收要插入的值scanf(%d, x); //输入要插入的值SLTErase(plist, pos); //删除pos所在结点//pos结点指针删除释放后要将其置为空pos NULL;}printf(操作后链表\n);PrintSList(plist);
}//测试函数9测试 -- SLTEraseAfter函数
void TestList9()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(操作前链表\n);PrintSList(plist);//用SLTFind函数查找链表中数据域为3的结点d的地址SLTNode* pos SLTFind(plist, 2);if (pos ! NULL){int x; //接收要插入的值scanf(%d, x); //输入要插入的值SLTEraseAfter(pos); //删除pos结点的下个结点//pos结点指针删除释放后要将其置为空pos NULL;}printf(操作后链表\n);PrintSList(plist);
}//测试函数10测试 -- SLTDestroy函数
void TestList10()
{//创建单链表头指针SLTNode* plist NULL;//使用尾插随机插入几个值: //(此时头指针指向NULL还没有开辟空间创建结点)SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);//使用SLTPrintf函数打印该链表printf(操作前链表\n);PrintSList(plist);SLTDestroy(plist);
}//主函数
int main()
{//TestList1();//TestList2();//TestList3();//TestList4();//TestList5();//TestList6();//TestList7();//TestList8();//TestList9();TestList10();return 0;
}
