【信息技术 】链表 课件 浙教版（2019）高中信息技术选修1.pptx

《【信息技术 】链表 课件 浙教版（2019）高中信息技术选修1.pptx》由会员分享，可在线阅读，更多相关《【信息技术 】链表 课件 浙教版（2019）高中信息技术选修1.pptx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.2 2.2 链表链表导入小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。原计划的途径地为上海、苏州、南京、济南、石家庄.第一次在南京和济南之间加入了途径地青岛，第二次取消了途径地南京.用数组来实现其更改过程。杭州杭州苏州苏州南京南京济南济南石家庄石家庄 北京北京青岛青岛数组a 0 1 23 4 5 67a=杭州,上海,苏州,南京,济南,石家庄,北京,n=len(a)p=4for i in range（n-2,p-1,-1）:_n+=1print(a)ai+1=ai ap=”青岛”第一次：上海上海导入小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过

2、了多次更改。原计划的途径地为上海、苏州、南京、济南、石家庄.第一次在南京和济南之间加入了途径地青岛，第二次取消了途径地南京.用数组来实现其更改过程。杭州杭州上海上海苏州苏州南京南京济南济南石家庄石家庄北京北京青岛青岛第二次：a=杭州,上海,苏州,南京,青岛,济南,石家庄,北京n=len(a)q=3for i in range(_):ai=ai+1 a.pop()n-=1print(a)q,n-1数组a 0 1 23 4 5 67导入小华规划自驾游路线，出发地为杭州，目的地为北京，在规划过程中经过了多次更改。第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；第二次在南京和济南之间加入了途径

3、地青岛，取消了途径地南京；用数组来实现其更改过程。杭州杭州苏州苏州济南济南石家庄石家庄北京北京青岛青岛数组的缺点：插入和删除元素操作需要移动大量的元素频繁增、删数据导致数据规模不稳，形成存储空间“碎片”需要限定最大空间，造成资源浪费链表适用于当数据规模不确定或初始时确定但在处理过程中由于频繁增、删数据导致数据规模不稳定的问题。数组a 0 1 23 4 5 67上海上海链表基本概念链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表基本概念：链表节点结构保存数据元素 保存相邻节点的存储地址头指针（head）作用：一是链表的入口，只有通过头指针才能进入链表二是为循环链

4、表设立一个边界，便于数据处理时的边界判断和处理吴坚黄刚王林李丰headnextnextnext链表基本概念根据每个节点中指针的数量分为：单向链表：循环链表：第一个节点和最后一个节点使用指针链接，这样就形成了循环链表。nextprevdata next双向链表：prev data nextprevprevnext：指向其后继节点prev：指向其前驱节点链表基本概念单向链表中各个节点在内存中可以随意存储，每个节点使用指针指向其后继节点的存储地址。进入链表只能通过头指针head，其他节点则需要经过所有在它之前的节点才可以访问，尾结点的指针指向为null，表示指向为空。链表的特性（1）同一链表中每个节

5、点的结构均相同数据类型相同指针数量和功能相同（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理链表的头指针使用变量head表示，用来进入链表。当访问链表中某一节点，只能从头指针开始，通过指针链接依次访问，不能使用下标直接引用。对于循环链表，一轮访问的开始和结束都可以用借助头指针指向位置来进行判断，即边界处理。head（3）链表占用的空间不固定链表的节点间是通过指针链接，相邻节点存储时不需要连续的空间。所以链表的存储空间由节点数决定，改变节点数就能改变链表的存储空间。链表的基本操作Python中没有直接定义链表结构，可以使用其提供的列表来模拟实现。实现单向链表时，列表中的每个数据项作为

6、链表中的一个节点，包含两个数据，一个作为数据域存储具体数据，另一个作为指针域存储后继节点在列表中的指针。用列表的索引来代替地址指针，并规定列表索引均为正索引，当某个指针区域值为-1时表示指向为空，该节点为尾节点。b=165,2,160,-1,162,1,172,0head=31652160-1162117200123head1721651621600123数组存储顺序存储链表存储非顺序存储data next头节点尾节点数据区域 指针区域空链表的创建其中head值为1，表示头指针指向为空，该链表为空链表。创建链表时，首先要根据问题特点规划节点的数据域和指针域，然后根据规划创建一个空表和头节点。接

7、下来就可以根据输入的实际数据形成节点并逐步插入到已有的链表中。item=head=-1练习1.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a：a=“hello”,1,“china”,3,“Olympics”,-1,“winter”,2head=0a11的值为：A.1 B.2 C.0 D.3a11的含义是什么？Dchina后面指向的下一个节点是“winter”,2链表的访问链表只能通过头指针（head）进行访问，其他节点通过节点间的指针依次访问。如图，当想访问单向链表中data3所在的节点时，需通过头指针进入链表，再分别按照各个节点的指针指向经过data1和d

8、ata2所在节点，最后通过data2所在节点的指针才能访问data3所在的节点。链表的插入3newdatadata1data22data3-1head在单向链表data1和data2所处节点的中间位置插入一个新节点31012思想：当需要在链表中某个位置中插入一个新元素时，只需将元素添加在尾部，并改动指针值data.append(newdata,0)1.将元素添加在尾部：列表名datadata31=data012.修改指针值：data01=3链表的插入data81=data11data11=82.修改指针值：思想：当需要在链表中某个位置中插入一个新元素时，只需将元素添加在尾部，并改动指针值0da

9、ta8-11data372data163data654data535data706data217data44head列表名data列表索引0data8-11data372data163data654data535data706data217data448new0data8-11data382data163data654data535data706data217data448new7headheaddata.append(new,7)1.将元素添加在尾部：链表的插入现有链表b=165,2,160,-1,162,1,172,0，要实现分别在链表头部插入数据175，请思考插入过程，并尝试用代码实现。

10、1652160-11621172017501234head在链表头部插入元素 172016521621160-1175 3head b=165,2,160,-1,162,1,172,0head=3_#插入新节点head=_#修改头指针print(b)3b.append(175,3)4链表的插入现有链表b=165,2,160,-1,162,1,172,0，要实现分别在链表中间插入数据163，请思考插入过程，并尝试用代码实现。1652160-11621172016301234head在链表中间插入元素 172016521621160-1163 2head b=165,2,160,-1,162,1,

11、172,0head=3#插入新节点pre=headcur=headwhilecur!=-1:ifbcur0=163:pre=curcur=bcur1else:_break 2b.insert(4,163,bpre1)bpre1=4 4 4curpre链表的插入现有链表b=165,2,160,-1,162,1,172,0，要实现分别在链表头部插入数据159，请思考插入过程，并尝试用代码实现。1652160-11621172015901234head在链表尾部插入元素 172016521621160-1159-1head b=165,2,160,-1,162,1,172,0head=3#插入新节点

12、cur=head#当前访问节点的索引值whilecur!=-1:#查找尾节点pre=curcur=bcur1_-1b.append(159,-1)bpre1=4 4 4curpre练习从头部插入从中间插入从尾部插入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=3new_data=xp=0a.append(new_data,ap1)ap1=len(a)-1print(head,a)a=t,4,y,0,o,-1,p,1head=3n

13、ew_data=xp=headwhile ap1!=-1:p=ap1a.append(new_data,ap1)ap1=len(a)-1print(head,a)数据合并 （1）算法设计 初始化两个空链表data_a和data_b，并使用head_a和head_b作为两个链表的头指针，其中data_a作为存储结果的链表。使用随机函数randint(start,end)模拟生成两个降序序列数据，生成新的结点在尾部插入。数据合并 （1）算法设计 使用变量k_a与k_b指向两个链表中未合并的数据序列中最前面（值最大）的结点，初始化k_a=head_a，k_b=head_b，由于在链表data_a中需

14、要进行插入结点的操作，必须记录插入位置的前驱结点，使用变量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指向结点的后继结点，再将k_b指向链表data_b中的下一个结点。若k_b未指向空，则将链表data_b剩余结点按顺序插入链表data_a的尾部。输出链表data_a中每个结点的数据区域的值。数据合并程序实现程序测试

15、结果from random import randintdata_a=head_a=-1data_b=head_b=-1tmp=randint(95,100)data_a.append(tmp,head_a)head_a=0for 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,1

16、1,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=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,

17、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数据合并程序实现程序测试结果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=le

18、n(data_a)-1 q_a=head_a k_b=data_bk_b1 else:data_a.append(data_bk_b0,k_a)data_aq_a1=len(data_a)-1 q_a=data_aq_a1 k_b=data_bk_b199198294393491-101234567head98195293390-10123head数据合并程序实现程序测试结果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(链表结构的合并后数

19、据序列)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,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

20、,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链表的删除data1data22data3-1head将单向链表data1和data3中间的节点删除掉10122739-1

21、50813201234head739-150813201234head739-150813201234head删除第一个节点删除第3个节点删除最后一个节点链表的删除参考链表的插入，描述出在单向链表中删除第一个节点、中间节点及尾节点的过程。a=7,3,9,-1,5,0,8,1,3,2head=4wz=int(input()k_a=headq_a=headc=0whilek_a!=-1:c=c+1ifc=wz:ifq_a=head:_else:_breakelse:_print(a)k_a=headforiinrange(len(a):ifk_a!=-1:print(ak_a0)k_a=ak_a1

22、head=aq_a1aq_a1=ak_a1q_a=k_ak_a=aq_a1739-1508132head练习1.有如下python程序段：a=7,1,8,2,9,-1,6,0 head=3 head=ahead1则程序执行后，链表a有几个节点（）A.1 B.2 C.3 D.4程序实现了什么功能？程序执行后链表a变为：C删除了头部节点6,0a=7,1,8,2,9,-1,6,0练习下列程序的运行结果为：lista=c,3,e,-1,a,4,d,1,b,0head=2p=headwhile listap1!=-1:print(listap0,end=-)p=listap1print(listap0)

23、输出结果：a-b-c-d-e链表节点的访问与遍历（1）抽象与建模 该问题中的关键数据是n个参与人员的初始编号，1至n的序列。从编号1开始计数，每过一个编号加1，当计数到m时将该编号从数据序列中移除，并从该编号的后一编号从1开始重新计数。而当计数到序列中最后一个编号，又从序列的开始编号继续计数，从而将计数序列构成一个环。重复这个过程，直到序列中只剩一个编号，该编号即为最后剩下人员的初始编号。链表节点的访问与遍历（2）设计数据结构与算法 该问题中数据规模在初始时可以确定（最大为n），但是在数据处理过程中需要按照规则不断地移除数据，直至只剩一个为止。也就是说，数据规模在处理过程中逐渐变小，呈现不稳定

24、的特性，符合链表的应用。由于最终需要输出初始编号信息，所以链表每个结点中数据区域用来保存初始编号，指针区域需要一个用来保存指向后继结点的指针。同时由于序列中最大编号报数后会从序列中最小编号继续报数，所以可以采用单向循环链表来组织数据。基于链表这种数据结构的设计，可以设计出相应的算法如下：链表节点的访问与遍历算法如下：创建一个由n个结点组成的单向循环链表，并使报数计数器i的初始化值为1，同时当前报数人的指针k指向链表中第一个结点。重复执行下列处理，直到链表中只剩下一个结点：随着报数的进行，不断指向下一个结点，报数计数器i也随之增加，当i增加到淘汰数m时，将对应的链表结点删除，若删除的结点为头结点

25、，则需同时修改头指针的指向；在删除结点的同时，需要重置报数计数器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)110221332443554665776807head课堂小结