数据结构基础知识02.-高考信息技术一轮二轮复习数据结构基础知识（浙教版2019）

数据结构基础知识（二）【知识要点】1.链表的概念与特性链表的概念：链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。2.表头:每个链表拥有一个表头——head(也称头指针),有两个作用:(1)链表的入口,只有通过头指针才能进入链表。(2)为循环链表设立边界,便于数据处理时的边界判断和处理。3.节点：链表中的每个节点一般由“数据区域”和“指针区域”两部分构成。数据区域用于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址。某个节点前面的相邻节点称为该节点的前驱节点，后面的相邻节点称为该节点的后继节点。4.链表的分类。(1)单向链表:只有一个指针区域,指向该节点的后继节点。双向链表:有两个指针区域,一个指向该节点的前驱节点,一个指向该节点的后继节点。循环链表:根据需要把链表第一个节点和最后一个节点使用指针链接,就形成了循环链表。5.链表的特性①同一个链表中每个节点的结构均相同。(1)每个节点的数据区域中的数据类型是相同的。(2)每个节点指针区域中的指针数量和功能相同的。②每个链表必定有一个头指针,以实现对链表的引用和边界处理。(1)引用链表时使用头指针head进入链表。(2)访问链表中某一个节点只能从头指针开始,通过指针链接依次访问,不能通过下标直接引用。(3)对于循环链表,一轮访问的开始和结束都可以借助头指针指向位置进行判断,即边界处理。③链表占用的空间不固定。(1)链表的相邻节点存储时不需要连续空间,充分利用了内存的零散空间,提高了存储空间利用率。(2)链表的存储空间由节点数决定,节点的增加或减少会导致链表占用的空间不固定。6.链表的基本操作（python中没有专门的链表结构,但是列表(list)相当灵活,可以用二维列表来模拟链表。为了方便模拟,先做几个约定:空链表:头指针head=1,为空链表；节点:每个节点又是一个列表,含有二个元素:[数据,指针]；尾节点:某个节点元素,指针=1,说明不存在后继节点；索引:每个节点在列表的索引位置,模拟节点在内存中的位置。）①链表的创建：例：item=[];head=1(1)根据问题特点规划节点的数据域和指针域。(2)根据规划创建一个空链表(3)根据输入的实际数据形成节点并逐步插入到已有的链表中。②链表节点的访问。例：p=head#头节点入口whilep!=1:#节点不为空 print(item[p][0])#输出数据域 p=item[p][1]#下一个节点链表只能通过头指针(head)进行访问。其他节点通过节点间的指针依次访问。若要访问链表中第n个节点,则步骤是:通过头指针进入链表→通过第一个节点的指针访问第二个节点→通过第二个节点的指针访问第三个节点→……→通过第n1个节点的指针访问第n个节点。③链表节点的插入与删除。(1)链表节点的插入。①链表节点的插入指的是根据新输入的实际数据形成节点,然后修改新节点与其前驱节点的指针,将新节点插入到链表的正确位置。②插入举例（一定要注意语句的先后顺序,防止链表断链。下面的代码在p指向节点后插人一个新的节点t）item[t][1]=item[p][1]item[p][1]=t情况操作步骤在空/非空单向链表中插入第一个节点根据新输入的实际数据形成新节点﹔修改新节点的指针指向与头指针一致;修改头指针指向新节点在非空单向链表两个节点中间插入新节点(或者在末尾插入新节点)根据新输入的实际数据形成新节点﹔修改新节点的指针指向与前一节点的指针指向一致;将前一节点的指针指向新节点③插入过程。插入新的节点，一定要注意语句的先后顺序,防止链表断链。下面的代码在p指向节点后插入一个新节点t:item[t][1]=item[p][1]；item[p][1]=t(2)链表节点的删除①链表节点的删除，是通过将需要删除的节点的前驱节点和其后继节点直接相连的方式实现。②删除举例。情况操作步骤删除链表第一个节点修改头指针head指向该节点的后继节点删除非空链表中间的一个节点修改该节点的前驱节点的指针指向该节点的后继节点删除链表最后一个节点修改该节点的前驱节点的指针指向为空③删除过程删除某个节点,一定要保留它的前驱节点的信息。假定变量p指向待删除节点,变量t指向p的前驱节点:item[t][1]=item[p][1]根据链表的特点，还可以写成：item[t][1]=item[item[t][1]][1]。7.Python语言中的类（1）类和实例①在Python中，对象用类创建。类是现实世界或思维世界中的实体在计算机中的反映，用来描述具有相同的属性和方法的对象的集合，它定义了每个对象所共有的属性和方法。②在Python中，类被称为类对象，类的实例被称为类的对象。创建一个新类意味着创建一个新类型的对象，从而允许创建一个该类型的对象实例。每个类的实例可以拥有保存自己状态的属性和改变自己状态的、定义在类中的方法。（2）类的定义class类名：Python使用class关键字来定义类，其语法格式如下：类体类是抽象的，要使用类定义的功能，就必须进行类的实例化，即创建类的对象，其语法格式为：对象名=类名(参数列表)。（3）类中的属性①类的数据成员是在类中定义的成员变量，用来存储描述类的状态特征的值，也称为属性。属性可以被该类中定义的方法访问，也可以通过类的对象进行访问。②通过“self.变量名”定义的属性，称为类的对象属性，属于类实例化的特定对象。对象属性在类的内部通过“self.变量名”访问，在外部通过“对象名.变量名”来访问。③类属性属于整个类，是在类中所有方法之外定义的变量，所有实例之间共享一个副本。类属性在类的内部通过“类名.类属性名”或“self.类属性名”访问，在外部可以通过类对象和实例对象访问公有的类属性，但不能访问私有的类属性。（4）类的对象方法①类的对象方法对类的某个实例化对象进行操作，一般以self作为其第一个形式参数（也可以使用其他名字）。声明对象方法的语法格式如下：def方法名（self，[形参列表]）方法体方法的调用格式为：对象名.方法名([实参列表])。②注意：虽然对象方法的第一个参数是self，但是在调用时，用户不需要也不能给该参数传递值，Python会自动地把对象传递给self参数。实现一个求长方体体积函数的类classBox():def__init__(self,length1,width1,height1):self.length=length1self.width=width1self.height=height1defvolume(self):returnself.length*self.width*self.height#以上是定义类my_box=Box(10,10,10)print("长方体体积是%d"%my_box.volume())链表的类实现：Python中用自定义类方式来构建链表,真正体现了链表的特性,各种操作更加方便自然。1.构建节点类:classLinkNode():def__init__(self,data,next=None):self.data=dataself.next=next2.构建链表:a=["Tom","Jerry","Spike","Tyke","Butch,Topsy","Tuffy"]#准备好节点数据head=LindNode(a[0])p=head#链表一般不能改变头指针变量foriinrange(1,len(a)):p.next=LindNode(a[i])p=p.next【例题剖析】例1下列有个链表的说法,不正确的是:()A.链表是将处理的对象以节点的形式,通过指针串联在一起的一种数据结构B.链表中的每个节点结构均相同,都包含“数据区域”和“指针区域”C.要访问有n个节点的链表的最后一个节点,和第一个节点一样快速D.链表的主要形式有单向链表,双向链表和循环链表【答案】C【解析】本题目涉及链表的基本特性,由于链表和数组不同,的每个节点只能通过节点间的指针依次访问。头节点一次就可以,尾节点要遍历完所有节点。例2.已知学生类的定义如下:classStudent:def_init_(self,name,age_=18,sex_="女"):=nameself.age=age_self.sex=sex_def__str__(self):returnf"姓名:{},年龄:{self.age},性别:{self.sex}"下列代码段定义了一个学生类的实例a,并输出其值:a=Student("张梅","16")print(a)则执行该段程序后,程序输出的值为()A.姓名:张梅,年龄:16,性别:B.姓名:张梅,年龄:18,性别:女C.姓名:张梅,年龄:16,性别:女D.姓名:张梅,年龄:18,性别:女【答案】C【解析】当使用print()函数输出类的实例的值时,会自动调用魔术方法__str__();Student类的_init_()方法有两个默认参数age_=18,sex_="女",定义类的实例a=Student("张梅","16")时，sex_取默认值。【习题巩固】1.下列有关链表的特性的描述,正确的是()A.同一链表中每个节点的结构可以不同B.一旦创建好链表后,链表的占用空间将固定不变C.链表中相邻节点存储时需要连续的存储空间D.每个链表必定有有一个头指针,只有通过头指针才能进入链表2.单向链表与数组都属于线性表，它们都用于存储具有相同属性的数据，下列说法不正确的是()A.对于需要频繁插入和删除元素的情况，使用单向链表比使用数组合适B.查找特定元素，使用单向链表比使用数组方便C.数组适用于最大元素个数容易确定的情况D.存储相同的元素，使用单向链表比使用数组方便3.已知指针p和q分别指向单链表x中的第一个结点和最后一个节点，假设指针s指向另一个单链表中某个节点，已知节点的指针区域为next。现要实现在s所指结点之后插入链表x，则正确的操作为()A.s.next＝p；q.next＝s.next B.p.next＝s.next；s.next＝qC.s.next＝q；p.next＝s.next D.q.next＝s.next；s.next＝p4.在Python中可以使用二维列表来模拟单向链表,用包含两个元素列表来表示每一个节点,其中第一个元素存储数据,第二个元素存储指针(即后继节点在二维列表中的索引)。下列代码创建了一个拥有3个节点的链表a:a=[[7,2],[8,1],[9,1]]head=0则其头节点和尾节点数据域的值分别为()A.7和8B.7和9C.8和9D.2和15.下列关于数组和链表的特征,说法正确的是()A.数组元素的数据类型可以相同,也可以不相同B.数组元素的占用的存储空间可以连续,也可以不连续C.链表节点的数据类型可以相同,也可以不相同D.链表节点占用的存储空间可以连续,也可以不连续6.使用Python的二维列表来模拟单向链表,如下代码创建了一个拥有4个节点的链表a:a=[[7,1],[8,2],[9,1],[6,0]]head=3依次输出各节点数据域的值,则输出内容为()A.7,8,9,6B.6,7,8,9C.9,8,7,6D.9,6,7,87.在Python中用列表模拟链表结构，某程序段如下：a=[["H",1],["a",2],["n",3],["g",4],["2",5],["0",6],["2",7],["2",0]]p,head=3,3;q,c=1,0;m,n=3,0whilen<4:c=c+1ifc==m:n=n+1;c=0ifp==head:head=a[p][1]a[q][1]=headp=a[p][1]else:a[q][1]=a[p][1]p=a[p][1]else:q=pp=a[p][1]#从头节点开始遍历链表a逻辑顺序的所有节点，并依次输出节点的数据，代码略该程序段执行后的输出结果为()ng02B.g02nC.2an2D.22an8.已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如右图所示，下列操作需要遍历多个节点的是（）A.删除该链表中的最后一个节点B.删除该链表中的第一个节点C.在该链表第一个节点前插入一个新节点D.在该链表最后一个节点后插入一个新节点9.下面程序运行后，结果显示如下，请问，程序中①②处的代码分别是（）classstudent(object):def__init__(self,x1,x2):①=x1②=x2defscreen(self):print("数学:",self.mh,"英语:",self.eng)subj=student(95,93)subj.screen()A.self.mh、self.engB.mh、engC.self.__mh、self.__engD..__mh、.__eng10.使用Python二维列表来模拟双向链表,用包含三个元素的列表来表示每一个节点,其中第一个元素存储数据,第二、三个元素分别存储前驱指针prev和后继指针next。下列代码创建了一个拥有4个节点的双链表a:a=[[2,2,3],[8,3,1],[0,1,0],[4,0,1]];head=2则其头节点和尾节点数据域的值分别为()A.2和4B.0和8C.8和0D.3和111.使用Python二维列表来模拟双向链表,用包含三个元素的列表来表示一个节点，其中第一个元素存储数据，第二、三个元素分别存储前驱节点的地址和后继节点的地址(1表示无前驱节点或后继节点)。下列代码创建了一个有4个节点的升序（从小到大）双向链表a。a=[[12,2,3],[18,3,1],[10,1,0],[14,0,1]],;head=2现要用append方法插入新数据17，并使a依旧保持升序，则插入后的列表a为()A.[[12,2,3],[18,3,1],[10,1,0],[14,0,1],[17,3,1]]B.[[12,2,3],[18,3,1],[10,1,0],[14,0,4],[17,3,1]]C.[[12,2,3],[18,4,1],[10,1,0],[14,0,4],[17,3,1]]D.[[12,2,3],[18,4,1],[10,1,0],[14,0,1],[17,3,1]]12.有如下Python程序段:a=[[3,4,2],[4,2,3],[8,4,1],[6,1,4],[5,3,2]]p=head=2whilea[p][1]!=head:print(a[p][0],end="一>")p=a[p][1]print(a[p][0])则执行上述语句后,程序输出结果为()A.3>8>5>6>4B.8>5>6>4C.4>8>5>6D.8>4>6>513.下面程序为实现在链表中插入一个大于3的数后使链表data的数据依然有序。data=[[14,1],[25,4],[3,0],[48,1],[27,3]]q=2foriinrange(len(data)):ifx>data[q][0]:① q=data[q][1]② )data[k][1]=len(data)1print(data)）C.①q ①q 14.使用列表模拟单链表，其存储结构如第10题图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’,则指针域中的索引值依次为()A.0123 B.3102 C.2011 D.201115.有如下Python程序段a=[[2,2,3],[8,3,1],[0,—1,0],[4,0,1]]head=2ifa[head][2]!=1:#有后继节点a[a[head][2]][1]=—1head=a[head][2]上述代码段中的二维列表a看作是一个双向链表,则执行上述语句后,双向链表的结构可以表示为（）A.0>2>4>8B.0>2>4C.0>2>8D.2>4>816.某医院每天提前发放100个预约号，考虑到老年人身体原因，预约病人按照以下规则进行就诊:①老年人(年龄>=60岁)比非老年人优先就诊。②老年人按年龄从大到小的顺序就诊，年龄相同的按预约顺序就诊。③非老年人按预约顺序就诊。小王根据以上规则编写了一个Python程序，程序运行时，实时读取病人预约数据，并根据以上规则，实时调整并显示当前诊顺序，程序运行界面如图所示。（1）如图所示，若当前就诊顺序为“7567401530”，下一位预约病人年龄为60，则就诊顺序变为______________________。（2）实现上述功能的代码如下，请在划线处填入合适的代码。#遍历链表data,头指针为headdefvisit(data,head):cur=headwhilecur!=1:print(data[cur][0],end="")cur=data[cur][1]print("\n")data=[]head=tail=1#head、tail分别表示链表头节点和尾节点所在位置foriinrange(100):#为了简洁，本程序只输入、存储病人的年龄信息age=int(input("请输入病人的信息："))cur=headifage>=60:whilecur!=1anddata[cur][0]>=age:#查找第一个数据域小于age的节点pre=cur_____①______ifcur==head:#在头节点插入新节点data.append([age,cur])head=len(data)1else:#在链表中间插入新节点data.append([age,cur])______②_____ifcur==1:#更新尾指针位置tail=len(data)1else:#直接插在链表尾节点后data.append([age,1])ifhead==1:#添加第一个节点head=tail=0else:______③_____tail=len(data)1print("当前就诊顺序为：")visit(data,head)17.山顶上有10个圆形排列的洞，一只狐狸和一只兔子各住一个洞。狐狸总想吃掉兔子。一天兔子对狐狸说：“你想吃我有一个条件，先把洞从1～10编上号，你先到1号洞找我；第二次隔1个洞（即3号洞）找我，第三次隔2个洞（即6号洞）找我，以后依此类推，次数不限。但狐狸从早到晚进进出出了1000次，仍没有找到兔子。请问免子可能躲在哪个洞里？实现上述功能的Python程序如下，请在划线处填入合适的代码：hone=[];n=10;m=1000#构造一个循环链表，并给n个洞编号，设置洞的初始标志为0#链表的节点样式为：[洞的标志,洞的编号]foriinrange(n1):hone.append([0,i+1])（1）1#狐狸开始找兔子，将进入过的洞标志改为1，寻找m次结束head=0k=headhone[0][0]=1foriinrange(1,m):forjinrange(1,i+2):（2）2hone[k][0]=1#输出标志仍为0的洞，即兔子可能藏身地点foriinrange(len(hone)):ifhone[i][0]==0:print("兔子可能躲在第"+（3）+"号洞")18．猴子选大王问题：有n只猴子，挑选大王。挑选规则如下：(1)将这n只猴子，围成一圈。从某一只猴子开始，按顺时针方向依次编号为1—n。(2)给定一个初始值k，从1号猴子开始，沿顺时针方向从1开始报数，报到k的猴子退出。(3)将k值增1，从刚才退出猴子逆时针方向第1只猴子开始，从1开始沿逆时针方向报数，报到k的猴子退出。(4)将k值增1，从刚才退出猴子顺时针方向第1只猴子开始，从1开始沿顺时针方向报数，报到k的猴子退出。(5)按上述(3)(4)两步，反复报数，直到圈中只剩下1只猴子。这只猴子就是大王。现要求，输入猴子的总只数n，和初始k值，要求输出大王的编号。同学们在程老师的指导下，利用如下数据结构来表示猴子和圆圈：1只猴子用包含3个元素的列表表示，其中第1个元素表示猴子的编号，第2个元素表示当前猴子的前1只没有退出圆圈的猴子的索引号，第3个元素表示当前猴子的后1只没有退出圆圈的猴子的索引号。圈中猴子用列表元素表示。比如，[[1,2,1],[2,0,2],[3,1,0]]表示包含3只猴子的圆圈，这也是3只猴子在挑选大王之前的初始状态。根据上面的数据结构，小李同学设计的算法并实现的python代码如下，请回答下列问题。n=int(input("请输入猴子的数量："))k=int(input("请输入k值："))monkey=[]foriinrange(n):tmp=[i+1,i1,i+1]#tmp表示索引号为i的猴子节点ifi==n1:tmp[2]=0elifi==0:①monkey.append(tmp)p=0;cnt=1;flag=0whilemonkey[p][2]!=p:p=monkey[p][2flag%2]cnt+=1ifcnt==k:②monkey[monkey[p][2]][1]=monkey[p][1]cnt=0k+=1③print('大王是：',monkey[p][0],'号')（1）根据上述算法，如输入猴子数量n为3，k值为2，则大王编号为▲号。（2）为使程序正确运行，请在划线处填入合适代码。19.下列Python程序的功能是创建一个链表,并在链表中间插入一个新节点,请回答下列问题。classNode():def_init_(self,data=None):self.data=dataself.next=NoneclassLink_list():def_init_(self):self.head=Nonedefprint_list(self):ptr=self.headwhileptr:print(ptr.data)ptr=ptr.nextdefinsertnode(self,pre_node,newdata):ifpre_node==None:print("插入位置不对")returnnew_node=Node(newdata)①

②

link=Link_list()link.head=Node(1)n2=Node(5)n3=Node(9)link.head.next=n2n2.next=n3link.print_list()print("新的链表")link.insertnode(n2,7)③#打印链表

(1)操作后的新链表中的节点为;

(2)请在程序划线处填入合适的代码。20.在Python语言中，可以使用列表来模拟链表节点的插入操作。以下Python程序段用二维列表来定义单向链表。如要在该链表