婺源做微信网站,长沙最坑装修公司,镇江网络营销外包,h5下一页目录#xff1a; 1#xff1a;链表的概念及结构 2#xff1a;实现单链表 3#xff1a;常见疑问 解答 #xff08;看到最后#xff01;#xff01;#xff09; 一#xff1a;链表的概念及结构 1.1 概念#xff1a; 链表是⼀种 物理存储结构上非连续、非顺序的 存储结…目录 1链表的概念及结构 2实现单链表 3常见疑问 解答 看到最后 一链表的概念及结构 1.1 概念 链表是⼀种 物理存储结构上非连续、非顺序的 存储结构但在 逻辑上是连续的 数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 1.2 结构 链表的结构跟火车车厢相似淡季时车次的车厢会相应减少旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上不会影响其他车厢每节车厢都是独立存在的。 ---在链表里每节“车厢”是什么样的呢 与顺序表不同的是链表里的每节车厢都是 独立申请下来的空间我们称之为“结点/节点” 节点的组成主要有两个部分 当前节点要保存的数据 和 下⼀个节点的地址(指针变量 注意链表中的最后一个节点的next指向空指针(nextNULL) 图中指针变量 plist保存的是第⼀个节点的地址我们称plist此时“指向”第⼀个节点链表中的每个节点都是独立申请的即需要插⼊数据时才去申请⼀块节点的空间我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点。 结合前面学到的结构体知识我们可以给出每个节点对应的结构体代码 假设当前保存的节点为整型 struct SListNode
{int data; //节点数据struct SListNode* next; //指向下⼀个节点的指针
};二实现单链表 单链表英文名——single linked list我们简写为SL 1.1创建 为了养成模块化好习惯我们把代码分开来写 1.2 链表的功能 1.3链表的实现 SList.h #pragma once
#includestdio.h
#includestdlib.h
#includeassert.h//定义节点的结构
//数据 指向下一个节点的指针
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//打印
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLTPopBack(SLTNode** pphead);//尾删
void SLTPopFront(SLTNode** pphead);//头删
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead); SList.c #includeSList.hvoid SLTPrint(SLTNode* phead)//打印
{SLTNode* pcur phead;while (pcur)//pcur!NULL{printf(%d-,pcur-data);pcur pcur-next;}printf(NULL\n);
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if(newnodeNULL){perror(newnode fail);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}//一级指针的地址用
void SLTPushBack(SLTNode** pphead, SLTDataType x)//二级指针来接收
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//空链表 与 非空链表if (*pphead NULL)//*pphead就是指向第一个节点的指针{*pphead newnode;}else{SLTNode* ptail *pphead;//先找到尾节点while (ptail-next)//!NULL{ptail ptail-next;}//ptail指向的就是尾节点ptail-next newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}
void SLTPopBack(SLTNode** pphead)//尾删
{assert(*pphead pphead);//一个节点if ((*pphead)-next NULL)// -的优先级高于*{free(*pphead);*pphead NULL;}//多个节点else{SLTNode* ptail *pphead;SLTNode* prev *pphead;while (ptail-next){prev ptail;ptail ptail-next;}free(ptail);ptail NULL;prev-next NULL;}
}
void SLTPopFront(SLTNode** pphead)//头删
{assert(*pphead pphead);SLTNode* next (*pphead)-next;// -的优先级高于*free(*pphead);*pphead next;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur phead;while (pcur)//pcur!NULL{if (pcur-data x){return pcur;}pcur pcur-next;}return NULL;
}
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(*pphead pphead);assert(pos);//还要判断能不能在链表中找到pos这个地址SLTNode* newnode SLTBuyNode(x);if (pos *pphead){SLTPushFront(pphead, x);}else{SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}newnode-next pos;prev-next newnode;}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);SLTNode* next pos-next;newnode-next next;pos-next newnode;}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead *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(pospos-next);//pos-next也要断言因为当cur-next为NULL时
//说明整个链表的节点都排查完了最后还是没有找到地址为pos的结点证明pos传值有误。SLTNode* after pos-next;pos-next after-next;free(after);after NULL;}//销毁链表
//因为链表在物理结构上是不连续存储的销毁链表必须要一个结点一个结点去销毁
void SListDesTroy(SLTNode** pphead)
{assert(*pphead pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;//不要忘记把phead置为NULL。
} test.c 测试输出结果为 可判断功能都可正常实现。 3.常见疑问解答 1.什么时候使用二级指针什么时候使用一级指针 以尾插举例当链表为空时头指针phead指向NULL尾插相当于头插此时要改变phead的指向让phead指向这个新节点此时就 需要二级指针来改变一级指针的值。if用一级指针做形参形参的改变不影响实参。 看下图帮助自己更好理解 2.有关断言 assert(pphead)---- 一级指针也就是phead当链表为空的时候phead就是为NULL而二级指针永远指向pheadphead的地址是永远存在的那么pphead就一定不可能为空所以需要断言pphead assert(*pphead)--- 保证原链表中有元素内容不为空。 assert(pos)--- pos也需断言不可为空 有更多问题欢迎大家提出。 感谢观看喜欢的可以点个赞支持一下。
