2.2 链表—— 链表数据结构的操作与应用导学案 2023—-2024学年浙教版（2019）高中信息技术选修1

链表的应用导学案 小明有一组数据按照升序排序的数据，用链表数据结构进行存储。 data=[[34,2][67,4][43,1][23,0][78,-1],[19,3]] head=5 1． 链表的遍历:请用链表遍历的方式，将该数据以升序的方式进行输出。 算法思路： 设计的变量及作用： 输出的格式如下所示[19,23,34,43,67,78] p=head 2． 链表的插入操作 链表数据结构的优势在于增加删除数据，非常方便。请模拟往程序中输入任意一个整数x，将其插入链表data，使得链表数据依旧保持升序。 x=int(input(“请输入一个正整数：”)) p,q=head,head 算法思路： 设计的变量及作用： if q==head: else: 3． 链表的删除操作 请模拟往程序中输入链表中已经存在的数字out，将其从链表data中删除，使得链表数据依旧保持升序。 算法思路： 设计的变量及作用： m=random.randint(0,len(data)-1) out=data[m][0] 4. 链表的应用 （1） 链表反转 已知有链表data如下所示，请将链表进行反转，使原链表按照逆序进行连接。 (1)画出下方链接data的逻辑数据结构： data=[[34,2][67,4][43,1][23,0][78,-1],[19,3]] head=5 方法一：原地反转法 算法思路： 设计的变量及作用： 方法二：头插法 data=[[34,2][67,4][43,1][23,0][78,-1],[19,3]] head=5 算法思路： 设计的变量及作用： （2）链表的合并 算法思路： 设计的变量及作用： 现有两组升序排序的数据，分别存储在链表data_a和data_b中，请将两个链表进行合并，使合并后的数据依旧保持升序。 data_a=[[34,2][67,4][43,1][23,0][78,-1],[19,3]] head_a=5 data_b=[[29,3][88,4][98,-1][49,1][2,5],[11,0]] head_b=4 （3）删除无序链表中重复元素 将链表中重复出现的数据所在节点删除，请完成下方方法一的填空，并说一说两种方法的思路。 方法一： 算法思路： 设计的变量及作用： a=[[0,3],[1,2],[1,4],[0,1],[0,5],[2,-1]] dele(a,0) def dele(a,head): pre=head;p=a[head][1] while p!=-1: q=head flag=False While____________: if a[q][0]==a[p][0]: _______________ p=a[p][1] flag=True break if not flag: pre=p p=a[p][1] 算法思路： 设计的变量及作用： 方法二： def guess(cur): q=cur;p=a[cur][1] while p!=-1: if a[p][0]==a[cur][0]: a[q][1]=a[p][1] p=a[p][1] else: q=p p=a[p][1] return a=[[1,1],[2,2],[3,3],[3,4],[4,5],[3,6],[5,-1]] head=0 cur=head while a[cur][1]!=-1: guess(cur) cur=a[cur][1] cur=head while cur！=-1： print(a[cur][0],end=””) cur=a[cur][1] 1 学科网（北京）股份有限公司 $$