1、知识回顾知识回顾 组织、处理一批数据时，若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中，这种方法的具体实现形式就是链表。2.2 链表浙江省高中信息技术 选择性必修一 数据与数据结构昌化中学 应彤鑫链表的概念与特性链表的概念与特性 概念 特性链表l 是指将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。l 由数据区域和指针区域两部分构成。链表的概念链表的概念l i a n b i a o d el i a n b i a o d e g a i n i a n g a i n i a n保存数据元素 保存相邻结点的存储地址
2、一个链表的节点链表的组成l 单向链表中各个结点在内存中可以非顺序存储l 每个结点使用指针指向其后继结点的存储地址l 进入链表只能通过头指针head，其他结点则需要经过所有在它之前的结点才可以访问，尾结点的指针指向为null，表示指向为空。链表的概念链表的概念l i a n b i a o d el i a n b i a o d e g a i n i a n g a i n i a np 头 节 点：用于进入链表和边界判断p 前驱节点：某个节点前面的相邻节点p 后继节点：某个节点后面的相邻节点p 尾 节 点：最后一个节点，指针指向空链表的存储方式头指针的作用l(1)链表的入口，只有通过头指针
3、才能进入链表。l(2)为循环链表设立一个边界，便于数据处理时的边界判断和处理。链表的概念链表的概念l i a n b i a o d el i a n b i a o d e g a i n i a n g a i n i a nhead(头指针)tailNone数据域指针域My_list前驱节点后继节点链表的分类链表的概念链表的概念l i a n b i a o d el i a n b i a o d e g a i n i a n g a i n i a n（1）单向链表：（2）双向链表：（3）循环链表：链表的特性l 同一链表中每个结点的结构均相同 每个节点的数据区域的数据类型相同，指针
4、区域中的指针数量和功能是相同的。l 每个链表必定有一个头指针，以实现对链表的引用和边界处理 链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。l 链表占用的空间不固定 链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。链表的特性链表的特性l i a n b i a ol i a n b i a o d e d e t e x i n g t e x i n
5、 g链表的基本操作链表的基本操作 链表的创建 链表元素的访问 链表元素的插入 链表元素的删除链表的基本操作链表的基本操作链表链表创建创建L i a n b i a o d eL i a n b i a o d e j i b e n c a o z u o l i a n b i a o c h u a n g j i a n j i b e n c a o z u o l i a n b i a o c h u a n g j i a n1.创建空链表2.使用列表模拟链表Item=Head=-1其中head值为1，表示头指针指向为空，该链表为空链表。创建链表时，首先要根据问题特点规划结点的数
6、据域和指针域，然后根据规划创建一个空表和头结点。接下来就可以根据输入的实际数据形成结点并逐步插入到已有的链表中。例如：a=99,1,95,2,88,-1 列表a中有3个元素：99,1 、95,2 、88,-1数据元素(a0)的第一个元素(99)为数据域。数据元素(a0)的第二个元素(1)为指针域，是列表a的第二元素的索引。头指针=0 为开始节点尾指针=-1 为尾节点，表示指向为空。练一练练一练l i a n y i l i a nl i a n y i l i a n1.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a：a=“hello”,1,“china”,
7、3,“Olympics”,-1,“winter”,2head=0a11的值为：A.1 B.2 C.0 D.3a11的含义是什么？Dchina后面指向的下一个节点是“winter”,2链表的基本操作链表访问L i a n b i a o d eL i a n b i a o d e j i b e n c a o z u o j i b e n c a o z u o l i n a b i a ol i n a b i a o f a n g w e nf a n g w e n链表的访问 链表只能通过头指针（head）进行访问，其他节点通过节点间的指针依次访问。即链表无法随机访问，只能进行顺
8、序访问。链表的基本操作链表访问L i a n b i a o d eL i a n b i a o d e j i b e n c a o z u o j i b e n c a o z u o l i n a b i a ol i n a b i a o f a n g w e nf a n g w e n链表的访问lista=c,3,e,-1,a,4,d,1,b,0head=2p=headwhile listap1!=-1:print(listap0,end=-)p=listap1print(listap0)输出结果：a-b-c-d-e1.使用python 的二维列表来模拟单向链表，如下代
9、码创建了一个拥有4个节点的链表a：a=“hello”,1,“china”,3,“Olympics”,-1,“winter”,2head=0依次输出各节点数据域的值，则输出内容为_hello china winterOlympics练一练练一练l i a n y i l i a nl i a n y i l i a n2.如下代码创建了一个拥有4个节点的链表a：a=7,1,8,2,9,-1,6,0head=3依次输出各节点数据域的值，则输出的内容是（）练一练练一练l i a n y i l i a nl i a n y i l i a n6,7,8,93.有如下python程序段：a=3,2,2
10、,3,7,1,1,0head=0p=headwhile ap1!=head:print(ap0,end=-)p=ap1print(ap0)执行上述语句后，程序输出的结果为（）练一练练一练l i a n y i l i a nl i a n y i l i a n3-7-2-1链表的基本操作链表插入L i a n b i a o L i a n b i a o d e d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入思想：当需要在链
11、表中某个位置中插入一个新元素时，只需将元素添加在尾部，并改动指针值0data8-11data372data163data654data535data706data217data44head列表名data列表索引0data8-11data372data163data654data535data706data217data440data8-11data382data163data654data535data706data217data448new7headhead列表名data列表索引列表名data列表索引链表的基本操作链表插入L i a n b i a o L i a n b i a o d e
12、 d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入现有链表a=“t”,2,“y”,0,“o”,-1，要实现分别在头部（插入p），中间（在t后面插入h）和尾部（插入n）插入新节点，最终形成链表a=“t”,4,“y”,0,“o”,5,“p”,1,“h”,2,“n”,-1，请思考形成过程，并尝试用代码实现。0t21y02o-1head0t41y02o53p14h25n-1head链表的基本操作链表插入L i a n b i a o L
13、i a n b i a o d e d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入一般先在列表尾部插入新节点，再寻找其前驱节点在列表中的索引，然后修改相关节点的指针区域的值。从头部插入新节点0t21y02o-1head0t21y02o-1head3p1a=t,2,y,0,“o,-1head=1new_data=pa.append(new_data,head)head=len(a)-1print(head,a)运行结果：3 t,2
14、,y,0,o,-1,p,1链表的基本操作链表插入L i a n b i a o L i a n b i a o d e d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入从中间插入新节点0t21y02o-13p1head4h2a=t,2,y,0,o,-1,p,1head=3new_data=hp=0a.append(new_data,ap1)ap1=len(a)-1print(head,a)0t21y02o-13p1head4运行结
15、果：3 t,4,y,0,o,-1,p,1,h,20t41y02o-13p14h2链表的基本操作链表插入L i a n b i a o L i a n b i a o d e d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入从尾部插入新节点0t41y02o-13p14h2head5n-1a=t,4,y,0,o,-1,p,1,h,2head=3new_data=np=headwhile ap1!=-1:p=ap1a.append(ne
16、w_data,ap1)ap1=len(a)-1print(head,a)5运行结果：3 t,4,y,0,o,5,p,1,h,2,n,-1head链表的基本操作链表插入L i a n b i a o L i a n b i a o d e d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入0t21y02o-1head0t21y02o-1head3p14h20t21y02o-13p1head40t41y02o-13p14h25n-15h
17、ead从头部插入p从中间插入h从尾部插入n链表的基本操作链表插入L i a n b i a o L i a n b i a o d e d e j i b e n c a o z u o l i a n b i a o c h a r u j i b e n c a o z u o l i a n b i a o c h a r u 链表元素的插入从头部插入从中间插入从尾部插入a=t,2,y,0,“o,-1,p,1head=1new_data=xa.append(new_data,head)head=len(a)-1print(head,a)a=t,2,y,0,o,-1,p,1head=3ne
18、w_data=xp=0a.append(new_data,ap1)ap1=len(a)-1print(head,a)a=t,4,y,0,o,-1,p,1head=3new_data=xp=headwhile ap1!=-1:p=ap1a.append(new_data,ap1)ap1=len(a)-1print(head,a)while p!=-1:#未到尾部 if itemp0”)p=ap2 print(ap0)lista=c,3,e,-1,a,0,d,1head=2p=headwhile listap1!=-1:print(listap0,end=-)p=listap1print(list
19、ap0)双向链表s h u a n g x i a n g l i a n b i a os h u a n g x i a n g l i a n b i a o双向链表的插入在链表a的索引p之后插入一个新节点，可以设计自定义函数如下:Def insert_behind(a,p,data):node=data,p,ap2 a.append(node)if ap2!=-1:aap21=len(a)-1 ap2=len(a)-1双向链表s h u a n g x i a n g l i a n b i a os h u a n g x i a n g l i a n b i a o双向链表的删除
20、双向链表节点的删除操作比单向链表要简单，它无需查找前驱节点，只需判断被删除的节点是否有前驱节点或后继节点，然后修改相关指针即可。尾结点可以直接删除，若删除了头节点，则需要修改头指针。可设计自定义函数删除索引为p的节点，代码如下：Def delete(a,head,p):if ap1!=-1:aap12=ap2 if ap2!=-1:aap21=ap1 if head=p:head=ahead2 return head练一练练一练l i a n y i l i a nl i a n y i l i a n1.Python中可以使用二维列表来模拟双向链表，用包含三个元素的列表来表示每一个节点，其中
21、第一个元素存储数据，第二、三个元素分别存储前驱指针prev和后继指针next。下列代码创建了一个拥有4个节点的双链表a：a=2,2,3,8,3,-1,0,-1,0,4,0,1head=2则其头节点和尾结点数据域的值分别为：A.2和4 B.0和8 C.8和0 D.3和-1B练一练练一练l i a n y i l i a nl i a n y i l i a n3.有如下python程序段：a=1,-1,1,2,0,2,3,1,3,4,2,-1head=0while ahead2!=-1:ahead1,ahead2=ahead2,ahead1 head=ahead1ahead1,ahead2=ah
22、ead2,ahead1则程序执行后，链表各节点数据值依次为：C链表的应用链表的应用 链表合并 约瑟夫环数据合并 （1）算法设计 初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链表的头指针，其中data_a作为存储结果的链表。使用随机函数randint(start,end)模拟生成两个降序序列数据，生成新的结点在尾部插入。数据合并程序测试结果from random import randintdata_a=head_a=-1data_b=head_b=-1tmp=randint(95,100)data_a.append(tmp,head_a)head_a=0
23、for i in range(1,20):tmp=data_ai-10-randint(1,5)data_a.append(tmp,data_ai-11)data_ai-11=iprint(链表结构的原始数据序列一)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=
24、0for i in range(1,25):tmp=data_bi-10-randint(1,5)data_b.append(tmp,data_bi-11)data_bi-11=iprint(链表结构的原始数据序列二)print(data_b)#初始化列表索引k_a=head_aq_a=head_ak_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
25、,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_ak_a0和data_bk_b0的大小。若data_ak_a0data_bk_b0，则修改q_a与k_a相等，再将k_a指向下一个结点；否则将链表data_b中k_b指向的结点插入到链表data_a中，作为q_a指向结点的后继
26、结点，再将k_b指向链表data_b中的下一个结点。若k_b未指向空，则将链表data_b剩余结点按顺序插入链表data_a的尾部。输出链表data_a中每个结点的数据区域的值。数据合并程序测试结果while(k_a!=-1 and k_b!=-1):if data_ak_a0=data_bk_b0:q_a=k_a k_a=data_ak_a1 else:if k_a=head_a:#在链表 data_a 的头部插入结点 data_a.append(data_bk_b0,head_a)head_a=len(data_a)-1 q_a=head_a k_b=data_bk_b1 else:dat
27、a_a.append(data_bk_b0,k_a)data_aq_a1=len(data_a)-1 q_a=data_aq_a1 k_b=data_bk_b1链表结构的合并后数据序列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,5
28、2,17,47,18数据合并程序测试结果while k_b!=-1:data_a.append(data_bk_b0,-1)data_aq_a1=len(data_a)-1 q_a=data_aq_a1 k_b=data_bk_b1print(链表结构的合并后数据序列)print(data_a)print(按链表链接顺序输出数据序列)tmp=head_awhile data_atmp1!=-1:print(data_atmp0,end=)tmp=data_atmp1print(data_atmp0)链表结构的合并后数据序列99,1,98,20,94,3,93,22,91,23,89,25,85
29、,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 7
30、1 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），但是在数据处理过程中
31、需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据规模在处理过程中逐渐变小，呈现不稳定的特性，符合链表的应用。由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：约瑟夫环问题算法如下：创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，
32、报数计数器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=0long=nk=headi=1while long1:i=i+1 if i=m:t=llistk1 llistk1=llistt1 if t=head:#删除结点为头指针指向的结点 head=llistk1 i=1 long=long-1 k=llistk1print(llisthead0)测试效果 1：请输入参与人数(N)：400请输入淘汰数(M)：2最后一人的起始编号是：289测试效果 2：请输入参与人数(N)：5000请输入淘汰数(M)：15最后一人的起始编号是：152课堂小结
