数据结构基础知识3

数据结构基础知识(三)

【知识要点】

一、“数据合并”问题简化成合并两个有序数据序列的问题，对如何使用数组解决数据合并问题进行了分析

并设计了算法。下面将对算法进行修改和优化，避免插入数据时其他数据元素的移动，并编程实现该功能。

算法设计：

①初始化3个数组a,b,c,元素个数分别为m,n和n+m。数组a和数组b用来存储已有的两个有

序数据(降序)，数据使用随机函数randint(start,end)产生；数组c用于保存合并后的所有数据(降序)，

所有数组元素的值初始化为0。②使用变量i指向数组a当前未处理数据中要处理的数据元素的位置，初始

化为0;变量j指向数组b当前未处理数据中要处理的数据元素的位置，初始化为0；变量k指向数组c中

可加入元素的位置，初始化为0。③重复以下操作，直至数组a或数组b中的数据元素全部合并入数组c

中：比较a[i]和b[j]的大小，若a[i]2b[j],则将a[i]放入数组c中,并将i和k的值增加1；否则，将

b[j]放入数组c中，并将j和k的值增加1。④如果数组a或数组b中尚有未处理的数据元素，那么将剩余

数据元素按原有顺序依次存入数组c中，合并完成，输出数组c。

fromrandomimportrandint

a=[0]*20;b=[0]*15;c=[0]*35#创建数组

a[0]=randint(95,100)

foriinranged,20):#随机产生降序数据序列一

a[i]=a[il]randint(1,5)

b[0]=randint(95,100)

foriinranged,15):#随机产生降序数据序列二

b[i]=b[il]randint(1,5)

print(，z原始数据序列一为：〃,a)

printCz原始数据序列二为：〃,b)

方法一：通过双指针逐个遍历二数组元素，将较大的存入合并数组中

i=0;j=0;k=0

while(i<20andj>15):#合并数据直至某个数组数据合并完成

ifa[i]>=b[j]:

c[k]=a[i];i=i+l;k=k+l

else:

c[k]=b[j];j=j+l;k=k+l

whilei<20:#当数据序列一中还有数据时的处理

c[k]=a[i];i=i+l;k=k+l

whilej<15:#当数据序列二中还有数据时的处理

c[k]=b[j];j=j+l;k=k+l

print(〃合并后的数据序列为：〃,c)

方法二：将b数组元素依次插入a数组中

forminrange(len(b)):

a.append(b[m])

tmp=a[l]

n=len(a)2

whiletmp>a[n]andn>0:

a[n+l]=a[n]

n=nl

a[n]=tmp

print(a)

⑵将两个有序链表中的数据合并到一个链表中。

fromrandomimportrandint

data_[];head_a=l

data_b=[];head_b=l

tmp=randint(95,100)

data_a.append([tmp,head_a])

head_a=0

foriinrange(1,20):

tmp=data_a[il][0]randint(1,5)

data_a.append([tmp,data_a[il][1]])

data_a[il][l]=i

print(〃链表结构的原始数据序列一〃)

print(data_a)

tmp=randint(95,100)

datab.append([tmp,head_b])

head_b=0

foriinrange(1,25):

tmp=data_b[il][0]randint(1,5)

data_b.append([tmp,data_b[il][1]])

data_b[il][l]=i

print(〃链表结构的原始数据序列二〃)

print(data_b)

k_a=heada;q_a=head_a;k_b=head_b

while(k_a!=1andk_b!=1):

ifdata_a[k_a][0]>=data_b[k_b][0]:

Q_a=k_a

k_a=data_a[k_a][1]

else:

ifk_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的非头部插入节点

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]

kb=data_b[k_b][1]

whilekb!=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]

kb=data_b[k_b][1]

print(〃链表结构的合并后数据序列〃)

print(data_a)

print(〃按链表链接顺序输出数据序列〃)

tmp=heada

whiledata_a[tmp][1]!=1:

print(data_a[tmp][0],end=〃〃)

tmp二data_a[tmp][1]

print(data_a[tmp][0])

(3)算法总结(请根据代码，讲变量名填入空格)

①初始化两个空链表和,并使用和作为两个链表的头指针，其中

()作为存储结果的链表。

②模拟生成两个降序序列数据，每个序列中第一个数据使用随机函数产生，其他数据则由前

一个数据减去一个随机值(「5)产生，产生的数据作为新节点的数据区域的值，生成新的节点在尾部插入。

③使用变量______与指向两个链表中未合并的数据序列中最前面(值最大)的节点，初始

化,，由于在链表data_a中需要进行插入节点的操作，必须记录插入位置的前驱

节点，使用变量_______，初始化q_a二head。重复以下操作，直到或指向空(即某个链表

元素全部处理完)：比较data_a[k_a][0]和data_b[k_b][0]的大小。若,则

修改q_a与k_a相等，再将k_a指向下一个节点；否则将链表data_b中指向的节点插入到链表

data_a中，作为q_a指向节点的后继节点，再将k_b指向链表中的下一个节点。

④若k_b未指向空，则将链表data_b剩余节点按顺序插入链表的尾部。

⑤输出链表data_a中每个节点的数据区域的值。

【例题剖析】

3.合并两个有序链表。将两个由升序序列数据组成的链表进行合并，要求新链表中的数据仍为升序序列。

程序运行的界面如下图所示：

实现上述功能的Python程序如下：

classNode：

def_init_(self,data=0,next=None)：

self.data=data

self.next=next

classSolution：

defmergeLists(self,hl：Node,h2：Node)：

head=Node()

node=head

whilehlandh2：

数据序列a为：

if①：

3681018

node.next=hl

数据序列b为：

hl=hl.next

27915

else：

合并后的数据序列为：

node.next=h2

236789101518

h2=h2.next

②

ifhl：

node.next=hl

else：

node.next=h2

node=head

returnhead,next

#生成链表a并输出链表中数据，代码略

#生成链表b并输出链表中数据，代码略

x=Solution()

xhead=x.mergeLists(ptrl,ptr2)

print(〃合并后的数据序列为：〃)

whilexhead：

print(xhead.data,end=〃〃)

®

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

答案：①hl.data<h2.data©node=node,next©xhead=xhead.next

解析：本题主要考查的是链表的综合应用。根据if下面的语句可知，if条件为指针hl指向的节点的值小

于指针h2指向的节点的值，因此①处代码为hl.data<h2.data。将a、b链表中的较小值的节点处理后，还

应将node指针移至刚插入到链表中的新节点，因此，划线②处的代码为node=node.next；划线③处while

循环的功能是输出合并后的链表，xhead为链表的头指针，输出当前节点的data值后，将指针移动到下一

个节点，因此③处应填入的代码为xhead=xhead.nexto

【习题巩固】

1.有如下Python程序段：

a=[2,2,6,3,1,5,6,2]

pos=0

foriinrange(1,len(a)):

ifa[i]>a[pos]:

pos=i

则程序执行后,pos的值为()

A.0B.2C.3D.6

2.有如下Python程序段:

a=[1,2,3,4,5,5]

x,j=4,len(a)2

whilej>=0anda[j]>x:

a[j+l]=a[j]

j二l

a[j+l]=x

则程序执行后,a[4]的值为()

A.2B.3C.4D.5

3.有如下Python程序段：

fromrandomimportrandom

i=0

a=[0]*6

whilei<=5:

a[i]=(int(random()*6+5))*(i%2+l)

forjinrange(i):

ifa[j]==a[i]:

i=il

break

i=i+1

程序执行后，数组a各元素的数据可能是

A.[6,12,5,18,8,10]B.[7,18,10,10,6,12]

C.[8,15,6,16,7,12]D.[5,16,12,18,9,10]

4.有如下程序段：

importrandom

a=[0]*6

foriinrange(6):

a[i]=random,randint(1,5)*2+1

i=0

whilei<5:

ifa[i]>a[i+l]:

a[i],a[i+l]=a[i+l],a[i]

a[i]+=l

i+=l

print(a)

以上程序运行后，列表a的值可能是：()

A.[2,5,10,10,10,9]B.[3,8,7,13,3,9]C.[8,12,3,5,3,11]D.[6,10,9,7,10,8]

5.有如下Python程序段

defbianli(head):

pt=head

whilept!=1:

print(data[pt][0],data[pt][1],〃>〃,end='')

pt二data[pt][1]

print()

data=[「A',1],[,B',2],['C',3],['D',1]]

head=0

bianli(head)#遍历链表，显示初始状态为“A1>B2>C3>D1>”

qt=head

pt=data[qt][1]

bianli(head)#遍历链表，显示最终状态为“A2>C1>B3>D1>”

执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为：

①data[data[qt][1]][1]=pt②data[qt][1]=data[pt][1]③data[pt][1]=

data[data[pt][1]][1]

则方框处代码的正确顺序是

A.①②③B.①③②C.②①③D.②③①

6.小华规划自驾旅游路线，出发地为杭州，目的地为北京，规划过程中经过了多次更改。

第一次依次加入的途径地为上海、苏州、南京、济南、石家庄；

第二次在南京和济南之间加入了途径地青岛，取消了途径地南京；

第三次则在石家庄和北京之间加入了途径地天津。

请使用链表编程实现其更改过程，并输出三次更改路线后的结果。

完善代码如下：

a=["杭州"，"上海","苏州南京济南"，"石家庄"，"北京"，"青岛"，"天津"]

head=O

b=[l,1,1,1,1,1,1,1,1]

foriinrange(6):#第一次规划

m

k=head#第二次规划

whilek!=l:

ifa[k]二二〃南京〃:

break

(2)

(3)

b[k]=7

k=head

whilek!=l:

ifa[k]=〃南京〃：

break

q=k

k=b[k]

(4)

k=head#第三次规划

whilek!=l:

ifa[k]=〃石家庄〃：

break

k=b[k]

b[8]=b[k]

b[k]=8

k=head

while(k!=l):

print(a[k],end=，/〃)

(5)

7.某投资者小赵将一段时间内的证券操作记录保存在文件“record,csv”中，部分界面如第4题图a所

zj\O

使用pandas模块对证券操作记录进行数据处理。

学习链表数据结构后，小赵同学想筛选出证券操作盈利的记录，并将结果以链表形式存储。

(1)代码实现如下，请在划线处填入合适的代码。

importcsv

csvFile=open(z，record.csv〃，〃r〃，encoding=〃UTF8〃)

reader=csv.reader(csvFile)

a=[]#数据区域

foriteminreader:

a.append(item)

csvFile.close

points=[l]*len(a)#指针区域，与数据区域a中的数据---对应

head二①

P=1

foriinrange(1,len(a)):

iffloat(a[i][5])>0:

ifhead=l:

P=i

else:

P=i

print（〃显示证券操作盈亏为正的记录：〃）

print（a[0]）#显示标题

p=head

whilep!=l:

print（a[p]）

_______④________

8.小明来到探险岛寻宝，岛上共有N个宝藏（标号为0至NDo每个宝藏有一条路连接下一个宝藏，宝

藏号和下一个宝藏号使用链表存储。小明想知道，从其中一个宝藏出发，最多可以找到多少个宝藏。

例如，共有5个宝藏，输入“1,3,4,4,1,”表示0~4各宝藏点连接的下一个宝藏依次是：

L3,4,4,1（如下表）。则最多可以找到4个宝藏，路径为：0号1号3号4号。

程序代码如下：

（1）若有4个宝藏，且每个宝藏的连接情况为：2,0,0,1,那么小明最多可以挖到的宝藏数是o

（2）请将代码补充完整。

s二input（〃请输入宝藏连接的情况：〃）

t=0;c=，z/z;a=[]

宝藏号01234

下一个宝藏号13441

else:

a.append([t,int(c)])

〃〃

c二

①

max=0

forheadinrange(0,t):#枚举寻找宝藏起点

g=[]

p=head

whilepnoting:

g.append(p)

②

iflen(g)>max:

print(max)

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

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

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

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

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

importrandom

a=□

head=1

foriinrange(8):

node二[random,randint(1,9),1,head]

a.append(node)

ifhead!=1:#非空链表

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

head二①

p-head

whilep!=1:

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

ifa[p][1]!=1:#有前驱节点

a[a[p][l]][2]=②

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

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

ifhead=p:#删除头节点

head=(3)

p=a[p][2]

10.王老师在处理最近一次的技术考试成绩，在这次考试中，每位同学的信息通用成绩是通过机器分开扫描

并存放在csv文件中，如图a所示为csv文件的部分截图。由于机器老化，在识别准考证号时，部分准考

证号的识别出现了乱码(乱码显示为“？”)。王老师编写了一个Python程序处理这些成绩，这个程序实现

了以下功能：1.将csv文件中的数据用链表形式存储在列表中，并按准考证号升序排序。每位同学有两行

数据，信息成绩在前，通用成绩在后；2.将这些乱码数据去除；3.排序完成后将全年级的信息成绩和通用

成绩分开，前半部分为信息成绩，后半部分为通用成绩。图b为处理完的链表按顺序输出的部分截图。

definsertnode(num,grade,p):

node=[num,grade,p]

a.append(node)

return①

csv_file=open(，score2.csv，,*r*)#打开存有准考证号和成绩的文件

flines=csv_file.readlines()#将文件中的数据按行读入flines中，返回一个列表

csv_file.close()

a=[];head=l

foriinranged,len(flines)1,2):#跳过第一行标题

xx=flines[i].stripC\n).splitC,J)#每行数据去除换行符号,返回以:为分隔符的列

表

ty=flines[i+l].strip(J\n).split[,')

if'?'inxx[0]:#若准考证存在乱码

continue

p=head

pre=head

whilep!=landxx[0]>a[p][0]:

pre=p

②

文件懈能杳有

ifp=head:准考证号，成绩

202008480,18

head=insertnode(xx[0],xx[l],p)202008480,33

202008319,19

202008319,23

pre=head202008333,20

202008333,20

202083775,22

else:202083775,27

202007294,23

202007294,18

a[pre][2]=insertnode(xx[0],xx[l],p)202007439,24

202007439,32

202009871,24

202009871,14

202008445,25

a[pre][2]=insertnode(ty[0],ty[1],p)202008445,28

#将信息和通用成绩分开存储第10题图ascore2.csv文件

cur=head

last=a[cur][2][12020021781,’42L516]

tmp=last「2020036271’49L512]

「2020036291’481296]

whilea[cur][2]!=1anda[last][2]!=1:

[1202007230,,’41L476]

a[cur][2]=a[last][2];cur=a[cur][2][1202007288,,'471,82]

a[last][2]=a[cur][2];last=a[last][2][,202007289,,,31]510]

a[cur][2]-④[,202007290,,’48]6]

[1202007294,,,231126]

p=head#输出链表

[,2020073231,'33L100]

whilep!=l:

第10题图b输出链表数据部分截图

print(a[p])

p=a[p][2]

H.扫描算法是一种电梯的调度算法，电梯在最底层(1楼)和最顶层(20楼)之间连续往返扫描并运行，

在运行过程中优先处理与当前电梯运行方向相同的请求，比如：当前电梯在3楼，方向为向上，此时有3

个人请求使用电梯：7楼去16楼、2楼去9楼、6楼去1楼，则电梯先向上运行，依次在7楼和16楼

停靠；然后再向下运行，依次在6楼和1楼停靠，最后再向上运行，依次在2楼和9楼停靠。小明编写

Python程序实现这个调度算法，运行界面如图所示，请回答下列问题。

(1)Python程序如下，请在划线处填入合适的代码。

defscan(now,d):#scan函数的功能：从当前楼层开始,按当前运行方向扫描一趟

i二0

whilei<=len(ask)1:

ifask[i][2]==dand①:

stop[ask[i][0]]=1

stop[ask[i][1]]=1

ask.pop(i)#删除索引为i的列表元素

当前楼层：3方向：向上

else:

上

靠

楼层716

i=i+1

下

楼层

靠61

上

楼层

ask=[[7,16,0],[2,9,0],[6,1,0]]靠29

direct={1:〃向上”,1：〃向下〃}

now=3:d=1

print(〃当前楼层:",now,"方向:",direct[d])

foriinrange(len(ask)):

t=②

t=t//abs(t)

ask[i][2]=t#t表示该请求的电梯运行方向

whilelen(ask)>0:

stop=[0]*21#标记120各楼层是否停靠

scan(now,d)

print(〃\n〃，direct[d],停靠楼层：〃，end=〃〃)

ifd==1:

st=1;ed=21

nownext=20

else:

st=20;ed=0

now_next=1

foriinrange(st,ed,d):

ifstop[i]==1:

print(i,end二〃〃)

now=now_next

(2)若电梯当前在3楼，方向为向上，

ask=[[7,16,0],[6,1,0],[2,9,0],[17,1,0],[10,15,0]],

则第一趟向上运行依次停靠的楼层是：(按停靠顺序填写数字)。

12.某校工会组织包粽子比赛，为体现团队协作，每个工会小组派5名选手参加，以接力赛形式完成15个

粽子的制作，要求每名选手至少包1个，最多包5个，且只能上场一次。现在高二年级组5名选手的包粽

子成绩保存在文档data,txt中，如第18题图a所示：

您data.txt-记事本

文件(F)编辑(E)格式(可直看(V)都助(H)

066140240342448-

160121192274360

4OU1^1QUOccc

356116178276396万某总时耗：988

|462126200280370|第12题图aI各选手需包粽子数目：23334I第12题图b

文档数据共5行，6歹U,每行数据分别是某选手编号、该选手累计包1到5个粽子的耗时(由于劳累因素

等影响，连续包的粽子越多，速度越慢或不变，绝不会变快)。请利用python编程设计方案，分配每位选

手需要包的粽子个数，使小组接力用时最短(接力时换人时间忽略不计)。运行界面如第18题图b所示:

f=openC(1)"r")#数据文件与程序文件在同一目录

a=[]

c=[l]*5#每位选手至少包1个粽子

forlineinf.readlines():

t=line.split()#将以空格分隔的数字字串存储在列表t

score=list(map(int,t))#将列表各元素转换成整数存储在列表score中

a.append(score)

pos=l

ans=0

b=[[0],[0],[0],[0],[0]]胱[i][j]表示第i位选手包第j个粽子所需的时间

foriinrange(0,5):

b[i].append(a[i][1])

forjinrange(2,6):

b[i].append(^2))

foriinrange(10):#每位选手至少包1个粽子，另10个粽子需分配

minx=1000000

forjinrange(5):

ifb[j][c[j]+l]<minxandc[j]+l<-5:

pos=j

⑶

c[pos]+=l

foriinrange(5):

ans+=_______(4)________

print(〃方案总时耗：”,ans)

print(〃各选手需包粽子数目：〃,c[0],c[1],c[2],c[3],c[4])

13.一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则称为该序列为摇摆序列。小王同

学想求出某个数列的最长摇摆子序列。以序列[3,14,7,6,9,12,10,8,13,5]为例,整体不是摇摆序列，但子

序列[3,14,7,9]、[3,14,6,12]等都属于摇摆子序列，其中最长的摇摆子序列是[3,14,6,12,8,13,5]。根据

第16题图a分析得知，当序列有一段连续的递增(或递减)时，可形成摇摆子序列，我们只需要找到每一

次转折中的拐点元素。小王编写了一个Python程序实现该功能：程序运行时，输入一串用逗号分隔和结束

的数字，可以得到最长摇摆序列的长度，以及具体的序列。程序运行界面如下图所示：

(1)若输入数据“2,4,5,3,2,1”，则最长摇摆子序列为—

(2)实现上述功能的Python代码如下，请在划线处填入合适的代码。

deff(n):

f=1

globalansftglobal表示此处的ans就是全局变量ans

ans=str(a[n1])

请输入以逗号分隔和结束的数据(木超过加个数)；3,14,7,6,9,12,10,8,13,

foriinrange(n2,1,1):最长摇摆子序列长度为6

最长摇摆子序列为।3,14,6,12,8,13

ifb[i]:

f=f+1

①

returnf

s二input(〃请输入以逗号分隔和结束的数据(不超过20个数)：〃)

a=[0]*20;b=[False]*20;flag,n,i,t,ans=0,0,0,

forchins:

•ci〃〃

ifch==,:

a[i]=int(t);n+=1;i+=1;t=

else:

t二t+ch

foriinrange(1,n):

gd=True

ifflag==0:

ifa[i]>a[i1]:

flag=1

elifa[i]<a[i1]:

flag=2

else:

gd=False

elifflag=1anda[i]<a[i1]:

flag=2

elif②:

flag=1

else:

gd=False

iff(n)<3:

print(〃不构成摇摆子序列”)

else:

print("最长摇摆子序列长度为"，str(f(n)))

print("最长摇摆子序列为："，ans)

参考答案

1.B2.C3.A4.C5.D

6.(1)b[i]=i+1(2)k=b[k](3)b[7]=b[k](4)b[q]=b[k](5)k=b[k]

7.(1)①1(2分)②head=i(2分)③points[p]=i(2分)@p=points[p](2分)

根据程序可知，先读取文件csv中的数据存入列表a中，Points为一维列表，存储指针。head的初值为1,

表示链表初始状态的头指针。列表a为二维列表，其中a[0]为标题项，因此从第1项开始遍历，当

float(a[i][5])>0成立，说明盈亏为正，此时将head更新为i,即第一个为盈亏为正的索引即为头指针,

②处答案为head=i。将p的值赋值为i,即p为前驱节点。指向下一