卓商网站建设,一流的邯郸网站建设,企业网站建设费用会计科目,企业邮箱是qq邮箱吗[一篇读懂]C语言十一讲#xff1a;单链表的删除和单链表真题实战1. 与408关联解析及本节内容介绍1 本节内容介绍2. 单链表的删除操作实战3. 单链表真题解读与解题设计1 题目解读2 解题设计第一阶段#xff1a;双指针找中间结点第二阶段#xff1a;原地逆置第三阶段#xff…
[一篇读懂]C语言十一讲单链表的删除和单链表真题实战1. 与408关联解析及本节内容介绍1 本节内容介绍2. 单链表的删除操作实战3. 单链表真题解读与解题设计1 题目解读2 解题设计第一阶段双指针找中间结点第二阶段原地逆置第三阶段轮流放入合并链表4. 代码实战5. 时间复杂度分析总结23.251. 与408关联解析及本节内容介绍
1 本节内容介绍
本节分为四小节讲解。 第一小节是链表删除进行实战 第二小节是是针对408考研真题2019年41题进行题目解读与解题设计 第三小节是针对408考研真题2019年41题进行实战 第四小节是分析真题实战代码的时间复杂度 2. 单链表的删除操作实战
一切数据结构 - 增删查改
之前介绍了链表的新增、删除、查找的原理。
单链表删除操作流程图 画流程图很关键。 单链表删除操作
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.htypedef int ElemType; //写分号typedef struct LNode
{ElemType data; //数据域struct LNode* next;
}LNode, * LinkList;void list_tail_insert(LNode* L)
{L (LinkList)malloc(sizeof(LNode));//申请头结点空间头指针指向头结点L-next NULL;//头结点的next为NULLElemType x;scanf(%d, x);LNode* s, * r L;//s用来指向申请的新节点r始终指向列表尾部while (x ! 9999){s (LinkList)malloc(sizeof(LNode));//为新节点申请空间s-data x;r-next s;//新节点给尾节点的next指针r s;//r要指向新的尾部scanf(%d, x);}r-next NULL;//让尾节点的next为NULL
}void print_list(LinkList L)
{L L-next;while (L ! NULL){printf(%3d, L-data);L L-next;}printf(\n);
}
//按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{int j 0;if (SearchPos 0){return NULL;}while (L j SearchPos)//L!NULL地址不为NULL{L L-next;j;}return L;
}//删除第i个位置的元素
//删除时不改变L所以不需要加引用
bool ListDelete(LinkList L, int i)
{LinkList p GetElem(L, i - 1);//拿到要删除结点的前一个结点指针p//判断p是不是空的if (NULL p){return false;}LinkList q p-next;//拿到p的下一个结点指针 - 即要删除的结点指针p-next q-next;//断链free(q);//释放return true;
}//尾插法新建链表
int main()
{LinkList L; //L是链表头指针是结构体指针类型 - 大小8个字节//list_head_insert(L); //输入数据可以为3 4 5 6 7 9999头插法新建链表list_tail_insert(L);print_list(L); //链表打印ListDelete(L, 4);//删除第四个结点print_list(L);return 0;
}这里删除第四个结点运行结果为 3. 单链表真题解读与解题设计
1 题目解读
2019年(单链表) 41.(13分)设线性表L(a1,a2,a3,…,an−2.an−1,an)L(a_1,a_2,a_3,…,a_{n-2}.a_{n-1},a_n)L(a1,a2,a3,…,an−2.an−1,an)采用带头结点的单链表保存链表中的结点定义如下 typedef struct node {int data;struct node* next;} NODE;请设计一个空间复杂度为O(1)且时间上尽可能高效的算法重新排列L中的各结点得到线性表L′(a1,an,a2,an−1,a3,an−2…)L(a_1,a_n,a_2,a_{n-1},a_3,a_{n-2}…)L′(a1,an,a2,an−1,a3,an−2…)。要求 1给出算法的基本设计思想。 2根据设计思想采用C或C语言描述算法关键之处给出注释。 3说明你所设计的算法的时间复杂度。
解读: 首先空间复杂度是O(1)不能申请额外的空间然后找到链表的中间结点前面一半是链表L将链表的后半部分给一个新的头结点L2然后将链表L2进行原地逆置然后再将L和L2链表进行交替合并。 空间复杂度O(?)额外使用的空间和原有空间之间的比例关系。 2 解题设计
分解题目针对三个阶段封装三个子函数条理清晰、逻辑缜密。
第一阶段双指针找中间结点
如何找到链表的中间结点。
方法一首先遍历一次链表长度假如是20再次遍历走到第10个。 这样的缺点是遍历了两次链表。 不好。方法二两个指针同步向后遍历的方法。 定义两个指针pcurppre让pcur指针每次走两步ppre指针每次走一步这样当pcur 指针走到最后那么ppre指针刚好在中间。 好。 注意由于pcur每次循环是走两步的因此每走一步都注意判断是否为NULL。 双指针找中间结点
第二阶段原地逆置
后一半链表我们设置为了L2如何让 L2原地逆置 首先需要判断链表是否为空如果为空就返回如果只有1个结点也不需要逆置直接返回。 第一步链表原地逆置需要使用3个指针假如分别是rst它们分别指向链表的1,2,3,也就是前三个结点。 第二步让s-next r这样2号结点就指向了1号结点完成了逆置。 第三步这时r ss tt t-next通过这个操作r,s,t分别指向了链表的2,3,4结点这时回到第二步循环往复当t为NULL时结束循环。 第四步循环结束时t为NULL这时s是最后一个结点r是倒数第第二个结点需要再次执行一下s-next r。 第五步最后需要L2-next-next NULL因为原有链表的头结点变成链表最后一个结点最后一个结点的next需要为NULL。这时让L2-next s因为s是原链表最后一个结点完成了逆置后就是第一个结点因此链表头结点L2指向s。 第三阶段轮流放入合并链表
将L与L2链表合并合并时轮流放入一个结点。 因为空间复杂度是O(1)因此不申请新空间但是依然需要3个指针pcur,p,q合并后的新链表让pcur指针始终指向新链表尾部初始化为pcur L-next使用p指针始终指向链表L待放入的结点初始化值为p L-nextq指针始终指向链表L2待放入的结点初始化值为q L2-next。因为链表L的第一个结点不动所以 pp-next。 开启循环while(p ! NULL q ! NULL)首先将pcur-next q然后q q-next和 pcur pcur-next接着pcur-next p,然后p p-next和pcur pcur-next直到循环结束。循环结束后有可能L还剩余一个结点也可能L2剩余一个结点但是只会有一个剩余的有结点因此判断如果p不为NULL把p放入如果q不为NULL把q放入即可。 4. 代码实战
代码流程先用尾插法新建一条链表然后将链表拆分为两条分别为L和L2然后L2进行逆置再把L和L2进行合并。 此处代码演示与上文一致实际解题时须与题目一致。 代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdlib.htypedef int ElemType; //写分号typedef struct LNode
{ElemType data; //数据域struct LNode* next;
}LNode, * LinkList;//尾插法新建链表
void list_tail_insert(LNode* L)
{L (LinkList)malloc(sizeof(LNode));//申请头结点空间头指针指向头结点L-next NULL;//头结点的next为NULLElemType x;scanf(%d, x);LNode* s, * r L;//s用来指向申请的新节点r始终指向列表尾部while (x ! 9999){s (LinkList)malloc(sizeof(LNode));//为新节点申请空间s-data x;r-next s;//新节点给尾节点的next指针r s;//r要指向新的尾部scanf(%d, x);}r-next NULL;//让尾节点的next为NULL
}//打印链表
void print_list(LinkList L)
{L L-next;while (L ! NULL)//NULL时为了代表一张空的藏宝图{printf(%3d, L-data);//打印当前结点数据L L-next;//指向下一个结点}printf(\n);
}//找到链表中间结点并设置好L2链表
void find_middle(LinkList L, LinkList L2)
{L2 (LinkList)malloc(sizeof(LNode));//第二条链表的头结点LinkList pcur, ppre;//双指针遍历 - 常考ppre pcur L-next;while (pcur){pcur pcur-next;//要检验每一步后是否结束所以不可以写成pcur pcur-next-nextif (NULL pcur)//为了防止pcur为NULL{break;}pcur pcur-next;//判断没有结束再走一步if (NULL pcur)//前一个指针在第二步结束时后一个指针不动{break;}ppre ppre-next;}L2-next ppre-next;//由L2头结点指向后面一半链表 - 让L2成为后一半ppre-next NULL;//前一半链表的最后一个结点的next为NULL - 让L成为前一半
}//原地逆置链表
void reverse(LinkList L2)//不改变头指针L2不需要加引用
{LinkList r, s, t;r L2-next;if (NULL r){return;//链表为空 - 只有头结点}s r-next;if (NULL s){return;//链表只有1个结点}t s-next;while (t)//t不为空{s-next r;//原地逆置r s;//以下3句 - 3个指针同时向后走一步s t;t t-next;}s-next r;L2-next-next NULL;//逆置后链表第一个结点的next要为NULLL2-next s;//s时链表第一个结点L2指向它
}//轮流放入合并链表
void merge(LinkList L, LinkList L2)
{LinkList pcur, p, q;pcur L-next;//pcur始终指向合并链表的链表尾p pcur-next;//p指向L链表第一个结点 - p用来遍历L链表q L2-next;//q指向L2链表第一个结点 - q用来遍历L2链表while (NULL ! p NULL ! q){pcur-next q;//链表L2给过来一个结点q q-next;//指向下一个pcur pcur-next;//合并链表往后走一个pcur-next p;//链表L给过来一个结点p p-next;//指向下一个pcur pcur-next;//合并链表往后走一个}//任何一个链表都可能剩余一个结点放进来即可if (NULL ! p){pcur-next p;}if (NULL ! q){pcur-next q;}
}int main()
{LinkList L; //链表头是结构体指针类型list_tail_insert(L);print_list(L); //链表打印//寻找中间结点并返回第二条链表LinkList L2 NULL;find_middle(L, L2);//只有一个结点时L2中是没有结点的printf(-----------------------------\n);//双指针遍历 - 分L和L2链表print_list(L);print_list(L2);printf(-----------------------------\n);//原地逆置链表reverse(L2);print_list(L2);printf(-----------------------------\n);//轮流放入合并链表merge(L, L2);free(L2);print_list(L);return 0;
}输入偶数个1 2 3 4 5 6 9999 输出结果为
输入奇数个1 2 3 4 5 6 7 9999 输出结果为 5. 时间复杂度分析
分析上一部分代码。
第一部分find_middle函数可以看到有一个while循环因为pcur每次移动两个节点因此循环的次数是n/2忽略首项系数所以时间复杂度是O(n)
//找到链表中间结点并设置好L2链表
void find_middle(LinkList L, LinkList L2)
{L2 (LinkList)malloc(sizeof(LNode));//第二条链表的头结点LinkList pcur, ppre;//双指针遍历 - 常考ppre pcur L-next;while (pcur){pcur pcur-next;//要检验每一步后是否结束所以不可以写成pcur pcur-next-nextif (NULL pcur)//为了防止pcur为NULL{break;}pcur pcur-next;//判断没有结束再走一步if (NULL pcur)//前一个指针在第二步结束时后一个指针不动{break;}ppre ppre-next;}L2-next ppre-next;//由L2头结点指向后面一半链表 - 让L2成为后一半ppre-next NULL;//前一半链表的最后一个结点的next为NULL - 让L成为前一半
}第二部分reverse函数遍历了L2链表遍历长度是n/2所以时间复杂度是O(n)
//原地逆置链表
void reverse(LinkList L2)//不改变头指针L2不需要加引用
{LinkList r, s, t;r L2-next;if (NULL r){return;//链表为空 - 只有头结点}s r-next;if (NULL s){return;//链表只有1个结点}t s-next;while (t)//t不为空{s-next r;//原地逆置r s;//以下3句 - 3个指针同时向后走一步s t;t t-next;}s-next r;L2-next-next NULL;//逆置后链表第一个结点的next要为NULLL2-next s;//s时链表第一个结点L2指向它
}第三部分merge函数while循环遍历次数也是n/2因此时间复杂度是O(n)
//轮流放入合并链表
void merge(LinkList L, LinkList L2)
{LinkList pcur, p, q;pcur L-next;//pcur始终指向合并链表的链表尾p pcur-next;//p指向L链表第一个结点 - p用来遍历L链表q L2-next;//q指向L2链表第一个结点 - q用来遍历L2链表while (NULL ! p NULL ! q){pcur-next q;//链表L2给过来一个结点q q-next;//指向下一个pcur pcur-next;//合并链表往后走一个pcur-next p;//链表L给过来一个结点p p-next;//指向下一个pcur pcur-next;//合并链表往后走一个}//任何一个链表都可能剩余一个结点放进来即可if (NULL ! p){pcur-next p;}if (NULL ! q){pcur-next q;}
}上面3个函数总的运行次数是1.5n忽略首项系数因此时间复杂度是O(n) 总结
2
单链表删除操作流程图 3.2
两个指针同步向后遍历的方法很常用
5
分析时间复杂度时最好分块分析时间复杂度忽略首项系数
