有了域名如何建设网站,上海出啥大事了今天,六盘水网络推广,自媒体运营从入门到精通目录
1. 链表的概念及结构
2. 链表的分类
3. 无头单向非循环链表的实现(下面称为单链表)
3.1 SListNode* BuySListNode(SLTDateType x) 的实现 3.2 void SListPrint(SListNode* plist) 的实现
3.3 void SListPushBack(SListNode** pplist, SLTDateType x) 的实现
3.4 voi…目录
1. 链表的概念及结构
2. 链表的分类
3. 无头单向非循环链表的实现(下面称为单链表)
3.1 SListNode* BuySListNode(SLTDateType x) 的实现 3.2 void SListPrint(SListNode* plist) 的实现
3.3 void SListPushBack(SListNode** pplist, SLTDateType x) 的实现
3.4 void SListPushFront(SListNode** pplist, SLTDateType x) 的实现
3.5 void SListPopBack(SListNode** pplist) 的实现
3.6 void SListPopFront(SListNode** pplist) 的实现
3.7 SListNode* SListFind(SListNode* plist, SLTDateType x) 的实现
3.8 void SListInsertAfter(SListNode* pos, SLTDateType x) 的实现
3.9 void SListEraseAfter(SListNode* pos) 的实现
3.10 void SListDestroy(SListNode* plist) 的实现
4. 题目练习
4.1 链表中的倒数第 K 个节点
4.2 环形链表 Ι 环形链表 Ⅱ
4.3 反转链表
4.4 合并两个有序链表 1. 链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。 链表的逻辑结构其实和上面的通过连接头连接起来的火车车厢差不多。 注意
1从上图中可以看出链式结构在逻辑上是连续的但是在物理上不一定连续程序中表现为每个节点在堆上的内存是不连续的
2现实中的节点一般都是从堆上申请出来的。
3从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续。
2. 链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构 1. 单向或者双向 2. 带头或者不带头 3. 循环和不循环 八种结构是怎么来的呢需要数学基础哈这里就不多说了。组合一下
虽然说链表有这么多中但是我们最常用的是两种哈
1无头单向非循环链表。
2带头双向循环链表。 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。
3. 无头单向非循环链表的实现(下面称为单链表)
// slist.h
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode* plist);3.1 SListNode* BuySListNode(SLTDateType x) 的实现
为啥要将开辟一个新节点封装成函数嘞因为在单链表的尾插头插指定位置后面插入均需要开辟新的节点如果我们将开辟节点封装成一个函数就可以少写几行代码调用函数就阔以啦
参数列表中的 x 用来初始化向堆区申请的节点。
//动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{//开辟节点SListNode* newNode (SListNode*)malloc(sizeof(SListNode));//返回的指针可能为空判断一下if (newNode NULL){perror(BuyNewNode::malloc);exit(-1);}else{//将值初始化newNode-next初始化为NULL是很有必要的//可以通过后面对该函数的使用来体会。newNode-data x;newNode-next NULL;}
} 3.2 void SListPrint(SListNode* plist) 的实现
参数 plist 是指向第一个结点的指针哈
这里就有一个小小的问题在写顺序表的代码时我们常常对传入的指针进行断言这里呢到底需不需要断言 plist 指针呢这里是没有必要的哈根据顺序表的结构传入的指针指向的结构体里面存储的是 堆上开辟的数组的指针如果传入的指针为空我们尝试去访问顺序表中的数据就会发生空指针的解引用引起程序崩溃 再看链表一个节点就是一个数据当 plist 传入空指针时就说明了此时单链表为空直接打印一个NULL就行或者啥都不打印。故不需要断言 plist 指针。 总结断言可以确保指针的合法使用如果程序可能出现非法使用指针则需要断言不妨称之为暴力检查或者用 if 进行判断不妨称之为温柔的检查。不知道 uu 们喜欢哪一种呢 打印数据就创建一个指针 cur初始化为 plist用 cur 指针遍历链表中的数据直到 cur 为空为止。
//打印单链表
void SListPrint(SListNode* plist)
{//初始化cur指针SListNode* cur plist;//循环遍历while (cur ! NULL){//生动的显示链表的结构打印一个 -printf(%d-, cur-data);cur cur-next;}//链表的尾节点指向 NULLprintf(NULL);printf(\n);
}
3.3 void SListPushBack(SListNode** pplist, SLTDateType x) 的实现
这里需要注意的一个点就是为啥传二级指针哈(C传一级指针加引用也行的哦)。了解了函数栈帧的创建和销毁之后印象最深刻的结论就是这个吧形参只是实参的临时拷贝形参的改变不会影响实参。 如果有不理解的地方请参考http://t.csdn.cn/SYcAp 好的理解了这个我们就来尝试理解为啥要传二级指针哈。
假设我们传入的是一级指针当我们的链表为空时指向第一个节点的指针 plist 就是 NULL这时我们将 plist 传入 SListPushBack 函数尾插嘛需要新节点调用上面的 BuySListNode 函数即可。既然插入了一个节点当然是需要改变 plist 的值的。我们直接将该函数返回的新节点的指针赋值给 plist这能达到改变 plist 的目的吗
显然是不能的。下图是传入一级指针尾插数据打印后的结果 这是为啥呢 一级指针不行为啥二级指针就行嘞 那好在弄清楚了这个问题我们就可以得出结论当我们需要改变 plist 的值时就必须传入plist的地址。
尾插还会分两种情况当单链表中没有节点时我们只需要将 newNode 赋值给 *pplist如果说有节点的话就需要找到单链表中的尾节点 tail然后令 tail - next newNode即可。还是比较好理解的哈。真正难理解的是二级指针那里呢
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newNode BuySListNode(x);//链表中没有节点直接赋值即可if (*pplist NULL){*pplist newNode;}else{//这里是找尾节点SListNode* tail *pplist;while (tail-next ! NULL){tail tail-next;}//连接新的节点tail-next newNode;}
}
3.4 void SListPushFront(SListNode** pplist, SLTDateType x) 的实现
头插和尾插差不多的哦头插同样要改变 plist 的值所以也需要传 plist 的地址哦头插就简单啦直接让 newNode - next *pphead 就行链表的增删改查函数你就先想一般的情况然后嘞在看看有没有特殊的情况比如说链表为空只有一个节点啥的呀这样就能分析出需不需要把一种情况单独拿出来处理。显然这个头插函数是不需要的哦
//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newNode BuySListNode(x);newNode-next *pplist;*pplist newNode;
}
3.5 void SListPopBack(SListNode** pplist) 的实现
尾删的话肯定没有数据的话是不让删的需要断言 *pplist。同样可能改变 plist 需要传入 plist 的地址哦
尾删有两种思路的哦
1双指针 根据上面说的链表函数接口的写法我们把一般的情况写出来了就得看看有没有特殊的情况捏显然是有的哦当链表只有一个节点时这个程序会崩溃的当只有一个节点时 (*plplist)-next 就是空无法进入循环prev也就是 NULLprev-next NULL这行代码就会发生空指针的解引用程序会崩溃的所以需要单独处理只有一个节点的情况。
void SListPopBack(SListNode** pplist)
{assert(*pplist);assert(pplist);if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{SListNode* tail *pplist;SListNode* prev NULL;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}
2不找到尾节点找尾节点的前一个节点 这里同样是需要单独处理一种情况的喔
void SListPopBack(SListNode** pplist)
{assert(*pplist);assert(pplist);//只有一个节点的情况if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else{//骑士不是找尾节点啦找的是尾节点的前一个节点SListNode* tail *pplist;while (tail-next-next ! NULL){tail tail-next;}//释放置空free(tail-next);tail-next NULL;}
}
3.6 void SListPopFront(SListNode** pplist) 的实现
头删肯定要改变 plist 的撒所以要传 plist 的地址哦同样需要断言没有数据不允许删除数据。
头删就简单啦找到 *pplist 的下一个节点记录下来然后释放 *pplist将 *pplist 置为记录下来的那个值就行。
//单链表的头删
void SListPopFront(SListNode** pplist)
{assert(pplist);assert(*pplist);//记录*pplist的下一个节点SListNode* next (*pplist)-next;//释放改变原来的plistfree(*pplist);*pplist next;
}
3.7 SListNode* SListFind(SListNode* plist, SLTDateType x) 的实现
这是在链表中查找值为 x 的第一个节点的返回这个节点的指针。这个是配合 指定位置删除和插入的函数使用的。
这里不需要改变 plist不用传 plist 的地址查找方法就是遍历加判断。
//单链表的查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{assert(plist);//用cur遍历链表SListNode* cur plist;while (cur ! NULL){//查找到值为x的节点返回即可if (cur-data x)return cur;cur cur-next;}//找不到返回NULLreturn NULL;
}
3.8 void SListInsertAfter(SListNode* pos, SLTDateType x) 的实现
这个函数是在 pos 之后插入一个节点。为啥不在 pos 位置之前插入 x 呢就是麻烦pos位置之前插入的话必须遍历找到pos位置之前的结构体时间复杂度 O(N)。而在pos位置之后的插入找到pos的下一个节点很轻松直接插就行了。这也是单链表的缺点无法向前找元素的哦
这个 pos 的结构体指针就是通过 SListNode* SListFind(SListNode* plist, SLTDateType x) 的返回值来的哦
//在pos位置之后插入 x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);//申请节点SListNode* newNode BuySListNode(x);//找到pos的下一个节点SListNode* next pos-next;//连接节点pos-next newNode;newNode-next next;
}
3.9 void SListEraseAfter(SListNode* pos) 的实现
这个函数是删除 pos 位置之后的节点。同样不删除 pos 位置 或者 pos位置之前的节点都是因为找到 pos 位置之前的节点很不容易。单链表没办法
//单链表删除pos位置之后的节点
void SListEraseAfter(SListNode* pos)
{assert(pos);assert(pos-next);//记录pos之后的下一个节点SListNode* next pos-next-next;free(pos-next);pos-next next;
}
3.10 void SListDestroy(SListNode* plist) 的实现
这个函数简单咯遍历单链表一个一个的释放节点就行注意一定要在找到下一个节点之后才能释放哦
//单链表的销毁
void SListDestroy(SListNode* plist)
{//用cur遍历链表SListNode* cur plist;while (cur ! NULL){//找到下一个节点SListNode* next cur-next;free(cur);cur next;}
}
4. 题目练习
4.1 链表中的倒数第 K 个节点 剑指 Offer 22. 链表中倒数第k个节点 - 力扣LeetCode 题目详解 http://t.csdn.cn/NcVND 4.2 环形链表 Ι 环形链表 Ⅱ 141. 环形链表 - 力扣LeetCode 142. 环形链表 II - 力扣LeetCode 题目详解 http://t.csdn.cn/YNwfJ 4.3 反转链表 剑指 Offer 24. 反转链表 - 力扣LeetCode 题目详解 http://t.csdn.cn/kkUvk 4.4 合并两个有序链表 21. 合并两个有序链表 - 力扣LeetCode 题目详解 http://t.csdn.cn/J1LBu
