资源简介

链表的应用导学案
小明有一组数据按照升序排序的数据，用链表数据结构进行存储。
data=[[34,2][67,4][43,1][23,0][78,-1],[19,3]]
head=5
链表的遍历:请用链表遍历的方式，将该数据以升序的方式进行输出。
算法思路：
设计的变量及作用：
输出的格式如下所示[19,23,34,43,67,78]
p=head
链表的插入操作
链表数据结构的优势在于增加删除数据，非常方便。请模拟往程序中输入任意一个整数x，将其插入链表data，使得链表数据依旧保持升序。
x=int(input(“请输入一个正整数：”))
p,q=head,head
算法思路：
设计的变量及作用：
if q==head:
else:
链表的删除操作
请模拟往程序中输入链表中已经存在的数字out，将其从链表data中删除，使得链表数据依旧保持升序。
算法思路：
设计的变量及作用：
m=random.randint(0,len(data)-1)
out=data[m][0]
链表的应用
链表反转
已知有链表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]

展开更多......

收起↑