数据结构基础知识04

数据结构基础知识(四)

【知识要点】

给定一个单链表及其头节点head,请你反转链表，并返回反转后的链表。

defpList(n):

whilen!=1:

ifL[n][l]!=1:#如果下一个还有数据，后面跟上〃>〃

print(L[n][0],end=〃>〃)

else:

print(L[n][0])

n=L[n][1]

L二[[〃A〃，3],[〃C〃,4],[〃D〃，1],[〃E〃,6],[〃B〃，7],[〃G〃,0],[〃F〃,2],[〃N〃,5]]#初始链表

head=1#链表头指针指向1

print(L)

pList(head)

输出结果：

列表显示为：[[〃A〃，3],[〃C〃,4],[〃D〃，1],[〃E〃,6],[〃B〃，7],[〃G〃，0],[〃F〃，2],[〃N〃，5]]

链表节点显示为：OB>N>G>A>E>F>D

第一种方法：使用头插法完成单向链表的反转

解题思路：

L创建一个空链表res,然后开始遍历原链表

2.对于遍历到的每一个结点，都将其作为res的头结点,那么当遍历到最后，也就完成了反转的目的

3.细节处是我们每一次循环，都要存储当前遍历结点的next结点，方便我们下次遍历，不然会死循环

k=head;newhead=l

whilehead!=1:

head=L[head][1]

L[k][l]=newhead

newhead=k

k=head

print(L)

pList(newhead)

输出结果：

列表显示为：[[〃A〃,5],[〃C〃,1],[〃D〃,6],[〃E〃,0],[〃B〃,1],[〃G〃,7],[〃F〃,3],[〃N〃,4]]

链表节点显示为：D>F>E>A>G>N>B>C

第二种方法：双指针实现链表反转

prev=head#初始化存储前驱指针的变量

cur二L[head][1]#初始化存储当前节点的变量

L[head].append(L[head][1])#先加入头指针的后继

L[head][1]=1#头节点单独操作,其前驱指针为1

whilelen(L[cur])=2:#为其余节点添加前驱指针

L[cur].append(L[cur][1])#加入当前指针的后继

next二L[cur][1]#存储后继指针

L[cur][l]=prev#修改当前节点的前驱指针prev

prev=cur#记录下一个节点的前驱指针prev

cur=next#记录当前节点的后继指针cur

tail=head#初始化尾节点的位置

whileL[tail][2]!=1:#找反向的头指针位置

tail=L[tail][2]

print(L)#打印链表列表

pList(tail)#调用函数输出链表

列表显示为：[['A',5,3],['C,1,4],['D',6,1],['E',0,6],['B',1,7],['G',7,0],['F',3,2],['N',4,5]]

链表节点显示为：D>F>E>A>G>N>B>C

第三种方法：栈实现链表反转

这种方法的思路是最简单的，因为栈本身就是实现线性结构倒序的常用工具。因为是牺牲空间换取时间的

做法，执行时间应该会比较短，但有较大空间消耗。这里申请一个存放节点的栈，将所有节点入栈，再按出栈

顺序重构链表，最终的结果就是反转的结果。仍要注意在反转过后要将原head节点的next指针置空。

s=[];top=l

whileL[head][1]!=1:并入栈

top=top+l

s.append(head)

head=L[head][1]

print(s)

k=head

whiletop!=1:#出栈

L[k][1]=s.pop()

top二1

k=L[k][1]

L[k][l]=top

pList(head)

栈满显示为：[1,4,7,5,0,3,6]

链表节点显示为：D>F>E>A>G>N>B>C

第四种方法：递归法实现链表反转

对于一个有n个节点的链表而言，对n个节点进行反转，就是把第1个节点接到第2n个节点的反转结果的

末尾。那么我们只需要用递归的手法进行整个链表反转即可。注意两点：当链表为空或者只有一个节点时，直

接返回头指针head；反转过后的头指针head要对其next指针置空。

defreverseList(head):

ifL[head][1]==1:

returnhead

else:

last=reverseList(L[head][1])

L[L[head][1]][l]=head

L[head][1]=1

returnlast

pList(reverseList(head))

【例题剖析】

小明通过二维列表模拟单向链表中特定范围内节点的翻转。输入链表节点个数n、翻转的范围left和right,

实现范围内节点的翻转并输出结果,Python代码如下程序运行效果如图所示。

⑴若链表L=[[4,1],[5,2],[7,3],[4,4],[8,1]],输入的边界为0和2,则输出链表的逻辑结构为

⑵请在划线处填入合适的代码。

importrandom

L=[];p=head=0

n=int(input(〃链表节点个数："))

#输入链表节点个数n

foriinrange(n):#生成n个节点的链表

①#节点值域范围为rio内的整数

L.append([a,i+1])

L[nl][l]=l

print(f〃翻转前：{L}")

left=int(input(〃翻转区间左边界：〃))#输入翻转左边界left

right=int(input(〃翻转区间右边界：〃))#输入翻转右边界right

ifleft==0:#左边界等于0

head=right

p=right

else:

②

ifright=len(L)1:#右边界等于len(L)1

else:

L[left][l]=right+l

foriinrange(left,right):#调整left到right范围内的节点指针域

④

print(f〃翻转后：{L}〃)

whileL[p][l]!=l:

print(L[p][0],end=〃>〃)

p=L[p][1]

print(L[p][0])

【解析】(1)初始链表L=[[4,1],[5,2],[7,3],[4,4],[8,1]],逻辑结构为4>5>7>4>8,输入的边界为0和2,即对

索引值为0,1,2的三个元素进行翻转,可得7>5>4>4>8o(2)①节点值域范围为「10内的整数,即生成P10范

围的随机整数,填入的代码为a=random.randint(l,10):②根据翻转范围left和right可知，leftl节点指针域

指向right所在节点，可知[l]=right;③条件right==len(L)1满足表示右边界等于len(L)1,翻转后

left节点为末位节点，指针域为1,即L[left]④调整left到right范围内的节点指针域，原前驱节点变

为后继节点，即

【习题巩固】

1.有如下Python程序段，使用单向链表存储二进制数，能够实现输人一个十进制数后，通过程序输出该十进

制数转换成二进制数的结果。划线处应填入的正确代码是

num=int(input(〃请输入一个十进制数：〃))

a=[]

head=l

whilenum>0:

a.append([num%2,head])

head二0

num=num//2

p=head

whilep!=l:

print(a[p][0],end=〃〃)

②

A.①len(a)l②p=a[p][1]B.①len(a)②p=a[p][1]C.①headl②p=plD.①head+1②p=p+1

2.已知一个链表a,其a[i][O]存储索引i下节点的数据区域，存储i下节点的指针区域。对当前链表

中的一个节点P(索引为P),若要删除P的后一个节点q(q=a[p][1]),则应执行下述()语句。

A.a[p]=a[q]B.a[p][l]=a[q][1]C.a[p]=a[a[q][1]]D.a[p]=a[q];a[p][l]=a[q][1]

3.采用列表模拟单向链表，data[p][O]为数据区域，data[p][l]为指针区域。在单向链表指针为p的节点之后

插入指针为s的节点，正确的操作是()

A.data[s][l]=pB.data[p][l]=s

data[p][l]=data[s][1]data[s][l]=data[p][1]

C.data[s][l]=data[p][1]

data[p][l]=s

D.data[p][l]=data[s][1]

data[s][l]=p

4.使用二维嵌套列表模拟单链表，则下列单链表中的数据成升序排列的是（）

A.head=O,[[11,2],[22,1],[33,4],[44,1],[55,5],[66,3]]

B.head=5,[[11,1],[22,0],[33,1],[44,2],[55,3],[66,411

C.head=l,[[44,4],[66,3],[22,5],[55,0],[33,2],[11,1]]

D.head=3,[[44,2],[22,5],[55,4],[11,1],[66,1],[33,0]]

5.某校军训，需要按照身高由低到高排成n行5列的方阵。某班学生按照身高(100W身高399)由低到高

编写编号并将相关信息存在如题151图所示”stu.txt”文件中。根据教官提出的排方阵要求，排成如题152图

所示方阵，方阵各点显示学生编号。

编方身图(cm)

01156

02159

03159

04159

05160

06160

07161

08162

09163清输入插入的学生身高（cm）168

101650102030405

1116601020304050607080910

12167Oh070809101112133114

1316711121314151516171819

1416816171819202021222324

1516921222324252526272829

262728293030

题51图题52图题53图

现有延迟报道学生归队，归队学生编号延续该班现有编号依次往后，编写程序完成下列任务：输入学生身

高，输出新的方阵布局图。例如：输入学生身高为168,新的方阵布局图如题53图所示，学生在方阵的位

置：3,4o

（1）若插入学生身高为160cm,根据题151图及范例，该学生应该在题52图方阵中的几行几列。

（2）为实现上述功能，请填写划线处代码。

f=open（〃stu.txt〃，〃r〃）

a=[]

line=f.readline().split()

i=l

whileline!=[]:

a.append([line[0],line[1],i])

i+=l

line=f.readline().split()

n=len(a)1

a[n][2]=1

sg二input(〃请输入插入的学生身高(cm):〃)

xh=str(len(a))

head=l

p=head;q=head

while______®_______

p=q

q=a[q][2]

ifq==head:

head=len(a)1

else:

a.append([xh,sg,a[p][2]])

a[p][2]=len(a)1

p=head

m=l

whilep!=1:

ifm!=5:

print(a[p][0],end=〃〃)

m+=1

else:

print(a[p][0])

m=1

③

6.双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向直接前驱和直接后

驱。在Python中可以使用二维列表来模拟双向链表，用包含3个元素的列表来表示每一个节点，其中第一

个元素存储数据，后两个元素分别存储指向前驱和后驱的指针。若没有前驱或后继节点，则对应的指针值

为一1。下列程序生成了一些随机正整数，并依次存储到一个双向链表a中。现要求删除其中值为偶数的节

点，请在划线处填入合适的代码。

importrandom

a=[]

head——■1

foriinrange(8)：

node=[random,randint(1,9),—1,head]

a.append(node)

ifhead!=-l：#非空链表

a[head][1]=len(a)—1

head=①

p=head

whilep!=11：

ifa[p][0]%2==0：

ifa[p][l]!=-l：#有前驱节点

a[a[p][1]][2]=②

ifa[p][2]!=—1:#有后继节点

a[a[p][2]][1]=a[p][1]

ifhead==p：#删除头节点

head二③

p=a[p][2]

7.旋转链表：对一个链表进行个别元素的旋转，比如原链表顺序如：c-t-b-a—h,若设定旋转系数k=2,

则旋转后链表顺序变为：a-h-c-Lb,k=2即表示将链表最后一个元素旋转至第1个执行两次，使原先

最后的两个元素如上述表示旋转为前面两个。

235

输出效果如图所示：

原链表：c—tTbTaTh

二:次旋转：

GXIXiWLMI输入旋转系数k:3

旋转后：b—a—hTcTt

第2次旋转：(7)-<£)-o—(£)_€

按照以上程序运行的要求补充下列代码，完成上述功能。

defprintLink(lstlink,point):

whilelstlink[point][1]!=1:

print(Istlink[point][0],'f',end='')

①

print(lstlink[point][0])

listl=[['t',2],「a',4],['b',1],['c',0],['h',1]]

head=3

print('原链表：'，end='')

printLink(listl,head)

pre=l

k=int(input('输入旋转系数k:'))

foriinrange(k):

cur=head

whilelistl[cur][1]!=1:

②

cur=listl[cur][1]

else:

listl[cur][l]=head

③

listl[pre][1]=1

print('旋转后：'，end='')

printLink(listl,head)

8.临近年关，学校为活跃新年气氛，举办迎新年联欢活动，最后一个节目为“我是大赢家”抽奖活动，为

增强互动效果，最后中大奖的中奖者由教师们自己互动产生，游戏规则是：全校所有教工，每人获得一个

随机编号，编号不得复，然后按照编号大小顺时针手拉手围成一个圈，最后一个老师与第一个老师手拉手，

接下来由第1个人指定m的值，从编号为1的人开始报数(1,2,3…)，报到m的人出圈，不再参加互动

游戏，接着再由出圈人的上一位老师新指定m的值，并重新开始报数，逆时针报到m的人出列，游戏过程

中出圈的人由老师们自己决定，如此继续，顺时针出一个人，逆时针出一个人，直到圈中只剩下一个人，

他就是今天的最大赢家。小明编写了一个Python程序实现上述功能，程序运行时，输入参加游戏的人数,

每次有人出圈后，再输入下一个要出圈的人数。

#删除索引为P的游戏者

defdelete(a,head,p):

ifa[p][1]!=1:

a[a[p][1]][2]=a[p][2]

ifa[p][2]!=1:

①

ifhead==p:

head=a[head][2]

returnhead

n=int(input(〃请输入参数游戏的人数〃))

a=[[i+1,il,i+1]foriinrange(n)]

a[0][l]=nl

a[nl][2]=0

p=head=0

while②:

m=int(input(〃请输入顺时针数第几位人出局〃))

foriinrange(ml):

head=delete(a,head,p)

P=a[p][l]#退回到上一位游戏者

ifa[head][1]!=head:

m=int(input(〃请输入逆时针数第几位人出局〃))

foriinrange(ml):

P=a[p][1]

head=delete(a,head,p)

④#退回到上一位游戏者

print(a[head])

参考答案

1.A2.B3.C4.D

5.(1)1,5(1分)(2)①a[q]andq!=l或int(a[q][l])<int(sg)andq!=l(2分)

②a.append([xh,sg,head])或a.append([xh,sg,p])或a.append([xh,sg,q])或

a+=[[xh,sg,head]]

③P=a[p][2](2分)

解析：⑴观察身高168的插入位置，可以看出插在原14号所在位。依此类推，身高160的同学，插入位

应为原05号学生所在位，即1,5

⑵本题是一个比较典型的链表应用。程序首先通过循环构建了一个a列表：列表形式如：

I“01”，"156"，1],[“02”，"159"，2],[“03”，"159"，3],.......]每项的最后一位，如

[“01”，"156"，1]中的1,是指向后继节点的指针，因此a列表可以理解为一个单向链表。由于原数据是

按身高升序排序，接下来问题转换为：如何在一个有序链表中插入数据？插入过程分成两步：

1、从头节点开始向后寻找插入位置

2、根据插入位置的不同，分为在链表头部插入和中间插入两种情况处理

填空①处语句是从链头开始向后寻找插入位置，P为当前节点，q为p的后继节点，从出循环后的判断if

q=head:可以看出，程序判断的是q点对应数值a[q][1]与sg的关系，结合⑴空，继续向后找的条件是:

a[q][l]<sg,同时为了保证链表还未遍历到尾部，循环条件应为：q!=1anda[q][l]<sgo出循环即找到插

入位置，在P、q之间，若干=110@(1,说明数据要插在链表的头部，此时首先向链表追加数据，同时设定后

继节点是head,然后修改链头head位置(head=len(a)1)②处填：a.append([xh,sg,head])③处所在循

环用于遍历输出链表，每5个一行输出，p变量为链表指针，每处理一个数据指针后移一位，即③处填：

p=a[p][2]

6.①len(a)—l②a[p][2]③a[p][2]

解析：空①处在生成链表节点后，把头节点的指针指向最后节点的元素位置；空②处删除值为偶数的节点，

当有前驱节点，需要修改新节点指针指向与前一节点的指针指向一致，故答案为a[p][2]；删除的节点如果

是头节点时，需修改头指针指向新节点，故③处答案为a[p][2]。

7.①point=lstlink[point][1]②pre=cur③head=cur等价答案：head=listl[pre][1]

解析：①为输出链表的函数，输出1个元素后，当前元素的指针由下一个元素的指针进行迭代，完成遍历

的目的。②由代码listl[pre][l]=l得