浙教版（2019） 高中信息技术 选修1 第2章第2节 链表 课件（共15张PPT）

(共15张PPT)
初识链表
册 别：选择性必修1
学 科：高中信息技术（浙教版）
“老鹰抓小鸡”游戏：“小鸡”队伍中，后面的人拉住前面人的衣服，形成一条链。把每个人想象成一个点，如何存储数据？当有人进队伍，或者有人退出时，数据中这些点的前后关系如何表示？
A
B
C
D
E
F
G
H
I
A
B
C
D
F
G
H
I
A
B
C
D
F
G
J
H
I
链表的概念
链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表中每个节点一般由“数据区域”和“指针区域”两部分构成。数据区域用于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址，并通过该地址指针来实现从当前节点按顺序走到其相邻的节点。
A
B
C
D
E
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,头指针head=0
A
B
C
D
E
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,头指针head=0
A 1
a[0]
B 2
a[1]
head=0
C 3
a[2]
A
B
C
D
E
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
A
B
C
D
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
头指针head=0
删除元素字母“E”
A
B
C
D
F
G
H
I
A
B
C
D
F
G
J
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 9
7 H 8
8 I -1
9 J 7
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
头指针head=0
在“G”后面插入元素字母“J”
链表的特性
1.同一链表中每个节点的结构均相同
2.每个链表必定有一个头指针，对实现对链表的引用和边界处理
3.链表占用的空间不固定
链表与数组
比较项目 数组 链表
逻辑结构 数据相邻的元素存储在地址连续的单元中；数据元素之间的邻接关系由存储单元的邻接关系来确定。 把数据元素放在任意的存储单元中（可连续，可不连续），用指针来反映数元素之间的相邻关系统。
元素的访问 可以随机访问，直接提取 要从头指针开始查找
元素的插入与删除 移动量较大，由元素的位置决定 任何位置上的删除，只需修改指针值，不需要移动
1.链表的创建
A
B
C
D
E
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,头指针head=0
head=0
a=[]
n=int(input("请输入人数："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append([chr(65+n-1),-1])
链表的基本操作
2.链表的访问
A
B
C
D
E
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 4
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
列表a,头指针head=0
head=0
a=[]
n=int(input("请输入人数："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append(['I',-1])
k=head
while(a[k][0]!='E'):
k=a[k][1]
print(k)
输出字母“E”在队伍中的位置
链表的基本操作
链表的基本操作
3.链表元素的删除
head=0
a=[]
n=int(input("请输入人数："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append(['I',-1])
k=head
prev=0
while(a[k][0]!='E'):
prev=k
k=a[k][1]
a[prev][1]=a[k][1]
print(a)
队伍中删除字母“E”
A
B
C
D
F
G
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 7
7 H 8
8 I -1
链表的基本操作
4.链表元素的插入
head=0
a=[]
n=int(input("请输入人数："))
for i in range(n-1):
a.append([chr(65+i),i+1])
a.append(['I',-1])
#删除字母“E”（此处省略）
#在“G”后面插入“J”
alen=len(a)
a.append(["J",alen])
k=head
while(a[k][0]!='G'):
k=a[k][1]
a[alen][1]=a[k][1]
a[k][1]=alen
print(a)
在“G”后面插入元素“J”
A
B
C
D
F
G
J
H
I
列表索引 数据区域 指针区域
0 A 1
1 B 2
2 C 3
3 D 5
4 E 5
5 F 6
6 G 9
7 H 8
8 I -1
9 J 7
链表的基本操作
2.链表的特性
3.链表与数组：相同点与不同点
4.链表的操作：新建链表，访问链表，删除节点，插入节点
1.链表的概念
（图片来源于网络，如有侵权请联系删除）
同学们，再见