资源简介

(共51张PPT)
知识回顾
组织、处理一批数据时，若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中，这种方法的具体实现形式就是链表。
CHZX
2.2 链表
浙江省高中信息技术 选择性必修一 《数据与数据结构》
昌化中学 应彤鑫
链表的概念与特性
概念
特性
01
链表
是指将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
由数据区域和指针区域两部分构成。
链表的概念
lianbiao de gainian
保存数据元素
保存相邻结点的存储地址
一个链表的节点
链表的组成
单向链表中各个结点在内存中可以非顺序存储
每个结点使用指针指向其后继结点的存储地址
进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。
链表的概念
lianbiao de gainian
头 节 点：用于进入链表和边界判断
前驱节点：某个节点前面的相邻节点
后继节点：某个节点后面的相邻节点
尾 节 点：最后一个节点，指针指向空
链表的存储方式
头指针的作用
(1)链表的入口，只有通过头指针才能进入链表。
(2)为循环链表设立一个边界，便于数据处理时的边界判断和处理。
链表的概念
lianbiao de gainian
head
(头指针)
tail
None
数据域
指针域
My_list
前驱节点
后继节点
链表的分类
链表的概念
lianbiao de gainian
（1）单向链表：
（2）双向链表：
（3）循环链表：
链表的特性
同一链表中每个结点的结构均相同
每个节点的数据区域的数据类型相同，指针区域中的指针数量和功能是相同的。
每个链表必定有一个头指针，以实现对链表的引用和边界处理
链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。
对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。
链表占用的空间不固定
链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。
链表的特性
lianbiao de texing
链表的基本操作
链表的创建
链表元素的访问
链表元素的插入
链表元素的删除
02
链表的基本操作——链表创建
Lianbiao de jibencaozuo——lianbiaochuangjian
1.创建空链表
2.使用列表模拟链表
Item=[]
Head=-1
其中head值为–1，表示头指针指向为空，该链表为空链表。
创建链表时，首先要根据问题特点规划结点的数据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。
例如：a = [ [ 99, 1 ],[ 95, 2 ],[ 88, -1] ]
列表a中有3个元素： [ 99, 1 ] 、 [ 95, 2 ] 、[ 88, -1]
数据元素(a[0])的第一个元素(99)为数据域。
数据元素(a[0])的第二个元素(1)为指针域，是列表a的第二元素的索引。
头指针 = 0 为开始节点
尾指针 = -1 为尾节点，表示指向为空。
练一练
lianyilian
1.使用python 的二维列表来模拟单向链表，如下代码创建了
一个拥有4个节点的链表a：
a=[[“hello”,1],[“china”,3],[“Olympics”,-1],
[“winter”,2]]
head=0
①a[1][1]的值为：
A.1 B.2 C.0 D.3
②a[1][1]的含义是什么？
D
china后面指向的下一个节点是[“winter”,2]
链表的基本操作——链表访问
Lianbiao de jibencaozuo——linabiaofangwen
链表的访问
链表只能通过头指针（head）进行访问，其他节点通过节点间的指针依次访问。即链表无法随机访问，只能进行顺序访问。
链表的基本操作——链表访问
Lianbiao de jibencaozuo——linabiaofangwen
链表的访问
lista = [["c", 3], ["e", -1], ["a", 4], ["d", 1], ["b", 0]]
head = 2
p = head
while lista[p][1] != -1:
print(lista[p][0], end="->")
p = lista[p][1]
print(lista[p][0])
输出结果：
a->b->c->d->e
1.使用python 的二维列表来模拟单向链表，如下代码创建了
一个拥有4个节点的链表a：
a=[[“hello”,1],[“china”,3],[“Olympics”,-1],
[“winter”,2]]
head=0
③依次输出各节点数据域的值，则输出内容为________________
__________________
hello
china
winter
Olympics
练一练
lianyilian
2.如下代码创建了一个拥有4个节点的链表a：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
依次输出各节点数据域的值，则输出的内容是（ ）
练一练
lianyilian
6,7,8,9
3.有如下python程序段：
a = [[3, 2], [2, 3], [7, 1], [1, 0]]
head = 0
p = head
while a[p][1] != head:
print(a[p][0], end="->")
p = a[p][1]
print(a[p][0])
执行上述语句后，程序输出的结果为（ ）
练一练
lianyilian
3->7->2->1
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
思想：当需要在链表中某个位置中插入一个新元素时，只需将元素添加在尾部，并改动指针值
0 data8 -1
1 data3 7
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
head
列表名data
列表索引
0 data8 -1
1 data3 7
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
0 data8 -1
1 data3 8
2 data1 6
3 data6 5
4 data5 3
5 data7 0
6 data2 1
7 data4 4
8 new 7
head
head
列表名data
列表索引
列表名data
列表索引
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
现有链表a=[[“t”,2],[“y”,0],[“o”,-1]]，要实现分别在头部（插入p），中间（在t后面插入h）和尾部（插入n）插入新节点，最终形成链表a=[[“t”,4],[“y”,0],[“o”,5],[“p”,1],[“h”,2],[“n”,-1]]，请思考形成过程，并尝试用代码实现。
0 t 2
1 y 0
2 o -1
head→
0 t 4
1 y 0
2 o 5
3 p 1
4 h 2
5 n -1
head→
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
一般先在列表尾部插入新节点，再寻找其前驱节点在列表中的索引，然后修改相关节点的指针区域的值。
①从头部插入新节点
0 t 2
1 y 0
2 o -1
head→
0 t 2
1 y 0
2 o -1
head→
3
p
1
a=[["t",2],["y",0],[“o",-1]]
head=1
new_data="p"
a.append([new_data,head])
head=len(a)-1
print(head,a)
运行结果：
3 [['t', 2], ['y', 0], ['o', -1], ['p', 1]]
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
②从中间插入新节点
0 t 2
1 y 0
2 o -1
3 p 1
head→
4
h
2
a=[["t",2],["y",0],["o",-1],["p",1]]
head=3
new_data="h"
p=0
a.append([new_data,a[p][1]])
a[p][1]=len(a)-1
print(head,a)
0 t 2
1 y 0
2 o -1
3 p 1
head→
4
运行结果：
3 [['t', 4], ['y', 0], ['o', -1], ['p', 1], ['h', 2]]
0 t 4
1 y 0
2 o -1
3 p 1
4 h 2
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
②从尾部插入新节点
0 t 4
1 y 0
2 o -1
3 p 1
4 h 2
head→
5
n
-1
a=[["t",4],["y",0],["o",-1],["p",1],["h",2]]
head=3
new_data="n"
p=head
while a[p][1]!=-1:
p=a[p][1]
a.append([new_data,a[p][1]])
a[p][1]=len(a)-1
print(head,a)
5
运行结果：
3 [['t', 4], ['y', 0], ['o', 5], ['p', 1], ['h', 2], ['n', -1]]
head→
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
0 t 2
1 y 0
2 o -1
head→
0 t 2
1 y 0
2 o -1
head→
3
p
1
4
h
2
0 t 2
1 y 0
2 o -1
3 p 1
head→
4
0 t 4
1 y 0
2 o -1
3 p 1
4 h 2
5
n
-1
5
head→
①从头部插入p
②从中间插入h
③从尾部插入n
链表的基本操作——链表插入
Lianbiao de jibencaozuo——lianbiaocharu
链表元素的插入
①从头部插入
②从中间插入
③从尾部插入
a=[["t",2],["y",0],[“o",-1],["p",1]]
head=1
new_data="x"
a.append([new_data,head])
head=len(a)-1
print(head,a)
a=[["t",2],["y",0],["o",-1],["p",1]]
head=3
new_data="x"
p=0
a.append([new_data,a[p][1]])
a[p][1]=len(a)-1
print(head,a)
a=[["t",4],["y",0],["o",-1],["p",1]]
head=3
new_data="x"
p=head
while a[p][1]!=-1:
p=a[p][1]
a.append([new_data,a[p][1]])
a[p][1]=len(a)-1
print(head,a)
while p != -1: #未到尾部
if item[p][0] < num:
if p==head:
item.append([num,p]) #插入并复制前序next值
head = len(item)-1 #更新head值
break
else:
item.append([num,item[q][1]]) #插入并复制前序next值
item[q][1] = len(item)-1 #更新前序next值
break
q = p #存储前序节点
p = item[p][1] #切换到下一节点
if p == -1: #在链表尾部插入
item.append([num,-1])
item[q][1] = len(item)-1
print(head,item)
head = 0
item = [[99,1],[98,2],[97,3],[95,4],[94,-1]]
num = int(input( )) #被插入数据
p = head
链表的基本操作——链表删除
Lianbiao de jibencaozuo——lianbiaoshanchu
链表元素的删除
删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。
链表节点的删除，并没有将元素从列表中删除，而仅仅是修改了节点指针域的值，通过将被删除节点的前驱节点和其后继节点直接相连的方式实现。
尾节点可以直接删除，若删除了头节点，则需要修改头指针。
0 t 2
1 y 0
2 o -1
head→
链表的基本操作——链表删除
Lianbiao de jibencaozuo——lianbiaoshanchu
链表元素的删除
0 a 1
1 b 2
2 c -1
head→
①删除头部节点
a=[["a",1],["b",2],["c",-1]]
head=0
head=a[head][1]
print(head,a)
运行结果：
1 [['a', 1], ['b', 2], ['c', -1]]
0 a 1
1 b 2
2 c -1
head→
链表的基本操作——链表删除
Lianbiao de jibencaozuo——lianbiaoshanchu
链表元素的删除
0 a 1
1 b 2
2 c -1
head→
②删除中间节点
a=[["a",1],["b",2],["c",-1]]
head=0
pre=0
p=a[pre][1]
a[pre][1]=a[p][1]
print(head,a)
运行结果：
0 [['a', 2], ['b', 2], ['c', -1]]
0 a 2
1 b 2
2 c -1
head→
链表的基本操作——链表删除
Lianbiao de jibencaozuo——lianbiaoshanchu
链表元素的删除
0 a 1
1 b 2
2 c -1
head→
③删除尾部节点
a=[["a",1],["b",2],["c",-1]]
head=0
pre=head
while a[a[pre][1]][1]!=-1
pre=a[pre][1]
a[pre][1]=-1
print(head,a)
运行结果：
0 [['a', 1], ['b', -1], ['c', -1]]
0 a 1
1 b -1
2 c -1
head→
1.有如下python程序段：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
head=a[head][1]
则程序执行后，链表a有几个节点（ ）
A.1 B.2 C.3 D.4
程序实现了什么功能？
程序执行后链表a变为 ：
练一练
lianyilian
C
删除了头部节点[6,0]
a=[[7,1],[8,2],[9,-1],[6,0]]
拓展——创建链表类
方法三（使用类创建）：
class Node( object ): #定义单链表节点类
def __init__( self, data, next = None ): #初始化节点：self为对象、data为数据
self.data = data #data为当前节点的数据
self.next = next #next为下一节点的链接，默认为None
例：
s=Node(5,1)
则：
s.data=5
s.next=1
双向链表的基本操作
链表的创建
链表元素的访问
链表元素的插入
链表元素的删除
03
双向链表
shuangxianglianbiao
双向链表
什么是双向链表？
双向链表（又称双链表）每个节点有两个指针prev和next，
分别指向其前驱节点和后继节点，这样可以提供方便的双向
查找功能。
双向链表的表示？
Dui=[[“吴坚”，-1，1],[“王林”,0，2],
[“黄刚”,1，3],[“李丰”,2，-1]]
节点
（由数据区域和前驱节点指针、后继节点指针构成）
我前面没人
我后面没人
我后面是黄刚
数据区域 前驱结点指针 后继节点指针
双向链表
shuangxianglianbiao
双向链表
下图所示为用二维列表表示一个长度为6的双向链表
data 1
^
data 2
data 3
data 4
data 5
data 6
head
双向链表中当节点中prev指向为-1（即指向为空）时，表示该节点为链表
中的首个节点；相对的，当节点中next指向为-1时，表示该节点为链表中
的最后一个节点。
双向链表
shuangxianglianbiao
双向链表的创建
Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来
表示每一个节点，其中第一个元素存储数据，第二、三个元素分别存储
前驱指针prev和后继指针next。
创建一个拥有2个节点的双向链表dblinklist的代码如下：
dblinklist=[[6,-1,1],[8,0,-1],]
head=0
创建一个空链表dblinklist的代码如下：
dblinklist=[]
head=-1
双向链表
shuangxianglianbiao
双向链表的访问
链表节点只能通过头指针（head）进行访问，其他节点通过节点间的next指针
依次访问。
可以设计如下自定义函数输出链表的所有节点：
listb=[[6,-1,1],[8,0,-1],]
def shuchu(a,head):
p=head
while a[p][2]!=-1
print(a[p][0],end=“---->”)
p=a[p][2]
print(a[p][0])
lista = [["c", 3], ["e", -1], ["a", 0], ["d", 1]]
head = 2
p = head
while lista[p][1] != -1:
print(lista[p][0], end="->")
p = lista[p][1]
print(lista[p][0])
双向链表
shuangxianglianbiao
双向链表的插入
在链表a的索引p之后插入一个新节点，可以设计自定义函数如下:
Def insert_behind(a,p,data):
node=[data,p,a[p][2]]
a.append(node)
if a[p][2]!=-1:
a[a[p][2]][1]=len(a)-1
a[p][2]=len(a)-1
双向链表
shuangxianglianbiao
双向链表的删除
双向链表节点的删除操作比单向链表要简单，它无需查找前驱节点，只需
判断被删除的节点是否有前驱节点或后继节点，然后修改相关指针即可。
尾结点可以直接删除，若删除了头节点，则需要修改头指针。
可设计自定义函数删除索引为p的节点，代码如下：
Def delete(a,head,p):
if a[p][1]!=-1:
a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
a[a[p][2]][1]=a[p][1]
if head==p:
head=a[head][2]
return head
练一练
lianyilian
1.Python中可以使用二维列表来模拟双向链表，用包含三个元素的
列表来表示每一个节点，其中第一个元素存储数据，第二、三个元素
分别存储前驱指针prev和后继指针next。下列代码创建了一个拥有4
个节点的双链表a：
a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]
head=2
则其头节点和尾结点数据域的值分别为：
A.2和4 B.0和8 C.8和0 D.3和-1
B
练一练
lianyilian
3.有如下python程序段：
a=[[1,-1,1],[2,0,2],[3,1,3],[4,2,-1]]
head=0
while a[head][2]!=-1:
a[head][1],a[head][2]=a[head][2],a[head][1]
head=a[head][1]
a[head][1],a[head][2]=a[head][2],a[head][1]
则程序执行后，链表各节点数据值依次为：
C
链表的应用
链表合并
约瑟夫环
04
数据合并
（1）算法设计
①初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链表的头指针，其中data_a作为存储结果的链表。
②使用随机函数randint(start,end)模拟生成两个降序序列数据，生成新的结点在尾部插入。
数据合并
程序 测试结果
from random import randint data_a=[] head_a=-1 data_b=[] head_b=-1 tmp=randint(95,100) data_a.append([tmp,head_a]) head_a=0 for i in range(1,20): tmp=data_a[i-1][0]-randint(1,5) data_a.append([tmp,data_a[i-1][1]]) data_a[i-1][1]=i print(" 链表结构的原始数据序列一 ") print(data_a) 链表结构的原始数据序列一
[[99, 1], [98, 2], [94, 3], [93, 4],[91, 5], [89, 6], [85, 7], [84, 8],[79, 9], [75, 10], [72, 11], [71,12], [66, 13], [64, 14], [59, 15],[54, 16], [52, 17], [48, 18], [44,19], [43,-1]]
程序 测试结果
tmp=randint(95,100) data_b.append([tmp,head_b]) head_b=0 for i in range(1,25): tmp=data_b[i-1][0]-randint(1,5) data_b.append([tmp,data_b[i-1][1]]) data_b[i-1][1]=i print(" 链表结构的原始数据序列二 ") print(data_b) #初始化列表索引 k_a=head_a q_a=head_a k_b=head_b 链表结构的原始数据序列二
[[98, 1], [95, 2], [93, 3], [91, 4],[90, 5], [89, 6], [84, 7], [80, 8],[79, 9], [75, 10], [71, 11], [69,12], [68, 13], [63, 14], [58, 15],[56, 16], [52, 17], [47, 18], [42,19], [41, 20], [38, 21], [34, 22],
[32, 23], [29, 24], [24, –1]]
数据合并
（1）算法设计
③使用变量k_a与k_b指向两个链表中未合并的数据序列中最前面（值最大）的结点，初始化k_a=head_a，k_b=head_b，由于在链表data_a中需要进行插入结点的操作，必须记录插入位置的前驱结点，使用变量q_a，初始化q_a=head。重复以下操作，直到k_a或k_b指向空（即某个链表元素全部处理完）：比较data_a[k_a][0]和data_b[k_b][0]的大小。若data_a[k_a][0]≥data_b[k_b][0]，则修改q_a与k_a相等，再将k_a指向下一个结点；否则将链表data_b中k_b指向的结点插入到链表data_a中，作为q_a指向结点的后继结点，再将k_b指向链表data_b中的下一个结点。
④若k_b未指向空，则将链表data_b剩余结点按顺序插入链表data_a的尾部。
⑤输出链表data_a中每个结点的数据区域的值。
数据合并
程序 测试结果
while(k_a!=-1 and k_b!=-1): if data_a[k_a][0]>=data_b[k_b][0]: q_a=k_a k_a=data_a[k_a][1] else: if k_a==head_a: # 在链表 data_a 的头部插入结点 data_a.append([data_b[k_b][0],head_a]) head_a=len(data_a)-1 q_a=head_a k_b=data_b[k_b][1] else: data_a.append([data_b[k_b][0],k_a]) data_a[q_a][1]=len(data_a)-1 q_a=data_a[q_a][1] k_b=data_b[k_b][1] 链表结构的合并后数据序列
[[99, 1], [98, 20], [94, 3], [93,
22], [91, 23], [89, 25], [85, 7],
[84, 26], [79, 28], [75, 29], [72,
11], [71, 30], [66, 13], [64, 33],
[59, 34], [54, 16], [52, 36], [48,
37], [44, 19], [43, -1], [98, 21],
[95, 2], [93, 4], [91, 24], [90, 5],
[89, 6], [84, 27], [80, 8], [79, 9],
[75, 10], [71, 31], [69, 32], [68,
12], [63, 14], [58, 35], [56, 15],
[52, 17], [47, 18]]
数据合并
程序 测试结果
while k_b!=-1: data_a.append([data_b[k_b][0],-1]) data_a[q_a][1]=len(data_a)-1 q_a=data_a[q_a][1] k_b=data_b[k_b][1] print(" 链表结构的合并后数据序列 ") print(data_a) print(" 按链表链接顺序输出数据序列 ") tmp=head_a while data_a[tmp][1]!=-1: print(data_a[tmp][0],end=" ") tmp=data_a[tmp][1] print(data_a[tmp][0]) 链表结构的合并后数据序列
[[99,1],[98,20],[94,3],[93,22],[91,23],[89,25],[85,7],[84,26],[79,28],[75,29],[72,11],[71,30],[66,13],[64,33],[59,34],[54,16],[52,36],[48,37],[44,19],[43,38],[98,21],[95,2],[93,4],[91,24],[90,5],[89,6],[84,27],[80,8],[79,9],[75,10],[71,31],[69,32],[68,12],[63,14],[58,35],[56,15],[52,17],[47,18],[42,39],[41,40], [38,41],[34,42],[32,43],[29, 44], [24, –1]]
按链表链接顺序输出数据序列
99 98 98 95 94 93 93 91 91 90 89 89 85 84 84 80 79 79 75 75 72 71 71 69 68 66 64 63 59 58 56 54 52 52 48 47 44 43 42 41 38 34 32 29 24
约瑟夫环问题
（1）抽象与建模
该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下人员的初始编号。
约瑟夫环问题
（2）设计数据结构与算法
该问题中数据规模在初始时可以确定（最大为n），但是在数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。
由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：
约瑟夫环问题
算法如下：
①创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。
②重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数m时，将对应的链表结点删除，若删除的结点为头结点，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数器i的值为1。
③将链表中唯一结点，也就是头指针指向的结点中的数据（即初始编号）输出。
约瑟夫环问题
程序 测试结果
llist=[] n=int(input(" 请输入参与人数（ N ） :")) m=int(input(" 请输入淘汰数（ M ） :")) for i in range(n-1): llist.append([i+1,i+1]) llist.append([n,0]) # 将尾结点的指针指向头结点，构成循环单向链表 初始化约瑟夫环
约瑟夫环问题
程序 测试结果
head=0 long=n k=head i=1 while long>1: i=i+1 if i==m: t=llist[k][1] llist[k][1]=llist[t][1] if t==head: # 删除结点为头指针指向的结点 head=llist[k][1] i=1 long=long-1 k=llist[k][1] print(llist[head][0]) 测试效果 1 ：
请输入参与人数 (N) ： 400
请输入淘汰数 (M) ： 2
最后一人的起始编号是： 289
测试效果 2 ：
请输入参与人数 (N) ： 5000
请输入淘汰数 (M) ： 15
最后一人的起始编号是： 152
课堂小结

展开更多......

收起↑