數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)（四）【知識(shí)要點(diǎn)】給定一個(gè)單鏈表及其頭節(jié)點(diǎn)head，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。defpList(n):whilen!=1:ifL[n][1]!=1:#如果下一個(gè)還有數(shù)據(jù)，后面跟上">"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#鏈表頭指針指向1print(L)pList(head)輸出結(jié)果：列表顯示為：[["A",3],["C",4],["D",1],["E",6],["B",7],["G",0],["F",2],["N",5]]鏈表節(jié)點(diǎn)顯示為：C>B>N>G>A>E>F>D第一種方法：使用頭插法完成單向鏈表的反轉(zhuǎn)解題思路：1.創(chuàng)建一個(gè)空鏈表res，然后開始遍歷原鏈表2.對(duì)于遍歷到的每一個(gè)結(jié)點(diǎn)，都將其作為res的頭結(jié)點(diǎn),那么當(dāng)遍歷到最后，也就完成了反轉(zhuǎn)的目的3.細(xì)節(jié)處是我們每一次循環(huán)，都要存儲(chǔ)當(dāng)前遍歷結(jié)點(diǎn)的next結(jié)點(diǎn)，方便我們下次遍歷，不然會(huì)死循環(huán)k=head;newhead=1whilehead!=1:head=L[head][1]L[k][1]=newheadnewhead=kk=headprint(L)pList(newhead)輸出結(jié)果：列表顯示為：[["A",5],["C",1],["D",6],["E",0],["B",1],["G",7],["F",3],["N",4]]鏈表節(jié)點(diǎn)顯示為：D>F>E>A>G>N>B>C第二種方法：雙指針實(shí)現(xiàn)鏈表反轉(zhuǎn)prev=head#初始化存儲(chǔ)前驅(qū)指針的變量cur=L[head][1]#初始化存儲(chǔ)當(dāng)前節(jié)點(diǎn)的變量L[head].append(L[head][1])#先加入頭指針的后繼L[head][1]=1#頭節(jié)點(diǎn)單獨(dú)操作,其前驅(qū)指針為1whilelen(L[cur])==2:#為其余節(jié)點(diǎn)添加前驅(qū)指針L[cur].append(L[cur][1])#加入當(dāng)前指針的后繼next=L[cur][1]#存儲(chǔ)后繼指針L[cur][1]=prev#修改當(dāng)前節(jié)點(diǎn)的前驅(qū)指針prevprev=cur#記錄下一個(gè)節(jié)點(diǎn)的前驅(qū)指針prevcur=next#記錄當(dāng)前節(jié)點(diǎn)的后繼指針curtail=head#初始化尾節(jié)點(diǎn)的位置whileL[tail][2]!=1:#找反向的頭指針位置tail=L[tail][2]print(L)#打印鏈表列表pList(tail)#調(diào)用函數(shù)輸出鏈表列表顯示為：[['A',5,3],['C',1,4],['D',6,1],['E',0,6],['B',1,7],['G',7,0],['F',3,2],['N',4,5]]鏈表節(jié)點(diǎn)顯示為：D>F>E>A>G>N>B>C第三種方法：棧實(shí)現(xiàn)鏈表反轉(zhuǎn)這種方法的思路是最簡(jiǎn)單的，因?yàn)闂１旧砭褪菍?shí)現(xiàn)線性結(jié)構(gòu)倒序的常用工具。因?yàn)槭菭奚臻g換取時(shí)間的做法，執(zhí)行時(shí)間應(yīng)該會(huì)比較短，但有較大空間消耗。這里申請(qǐng)一個(gè)存放節(jié)點(diǎn)的棧，將所有節(jié)點(diǎn)入棧，再按出棧順序重構(gòu)鏈表，最終的結(jié)果就是反轉(zhuǎn)的結(jié)果。仍要注意在反轉(zhuǎn)過后要將原h(huán)ead節(jié)點(diǎn)的next指針置空。s=[];top=1whileL[head][1]!=1:#入棧top=top+1s.append(head)head=L[head][1]print(s)k=headwhiletop!=1:#出棧L[k][1]=s.pop()top=1k=L[k][1]L[k][1]=toppList(head)棧滿顯示為：[1,4,7,5,0,3,6]鏈表節(jié)點(diǎn)顯示為：D>F>E>A>G>N>B>C第四種方法：遞歸法實(shí)現(xiàn)鏈表反轉(zhuǎn)對(duì)于一個(gè)有n個(gè)節(jié)點(diǎn)的鏈表而言，對(duì)n個(gè)節(jié)點(diǎn)進(jìn)行反轉(zhuǎn)，就是把第1個(gè)節(jié)點(diǎn)接到第2n個(gè)節(jié)點(diǎn)的反轉(zhuǎn)結(jié)果的末尾。那么我們只需要用遞歸的手法進(jìn)行整個(gè)鏈表反轉(zhuǎn)即可。注意兩點(diǎn)：當(dāng)鏈表為空或者只有一個(gè)節(jié)點(diǎn)時(shí)，直接返回頭指針head；反轉(zhuǎn)過后的頭指針head要對(duì)其next指針置空。defreverseList(head):ifL[head][1]==1:returnheadelse:last=reverseList(L[head][1])L[L[head][1]][1]=headL[head][1]=1returnlastpList(reverseList(head))【例題剖析】小明通過二維列表模擬單向鏈表中特定范圍內(nèi)節(jié)點(diǎn)的翻轉(zhuǎn)。輸入鏈表節(jié)點(diǎn)個(gè)數(shù)n、翻轉(zhuǎn)的范圍left和right,實(shí)現(xiàn)范圍內(nèi)節(jié)點(diǎn)的翻轉(zhuǎn)并輸出結(jié)果,Python代碼如下程序運(yùn)行效果如圖所示。(1)若鏈表L=[[4,1],[5,2],[7,3],[4,4],[8,1]],輸入的邊界為0和2,則輸出鏈表的邏輯結(jié)構(gòu)為(2)請(qǐng)?jiān)趧澗€處填入合適的代碼。importrandomL=[];p=head=0n=int(input("鏈表節(jié)點(diǎn)個(gè)數(shù):"))#輸入鏈表節(jié)點(diǎn)個(gè)數(shù)nforiinrange(n):#生成n個(gè)節(jié)點(diǎn)的鏈表①#節(jié)點(diǎn)值域范圍為1~10內(nèi)的整數(shù)L.append([a,i+1])L[n1][1]=1print(f"翻轉(zhuǎn)前:{L}")left=int(input("翻轉(zhuǎn)區(qū)間左邊界:"))#輸入翻轉(zhuǎn)左邊界leftright=int(input("翻轉(zhuǎn)區(qū)間右邊界:"))#輸入翻轉(zhuǎn)右邊界rightifleft==0:#左邊界等于0head=rightp=rightelse:②ifright==len(L)1:#右邊界等于len(L)1③else:L[left][1]=right+1foriinrange(left,right):#調(diào)整left到right范圍內(nèi)的節(jié)點(diǎn)指針域④print(f"翻轉(zhuǎn)后:{L}")whileL[p][1]!=1: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]],邏輯結(jié)構(gòu)為4>5>7>4>8,輸入的邊界為0和2,即對(duì)索引值為0,1,2的三個(gè)元素進(jìn)行翻轉(zhuǎn),可得7>5>4>4>8。(2)①節(jié)點(diǎn)值域范圍為1~10內(nèi)的整數(shù),即生成1~10范圍的隨機(jī)整數(shù),填入的代碼為a=random.randint(1,10);②根據(jù)翻轉(zhuǎn)范圍left和right可知,left1節(jié)點(diǎn)指針域指向right所在節(jié)點(diǎn)，可知L[left1][1]=right;③條件right==len(L)1滿足表示右邊界等于len(L)1,翻轉(zhuǎn)后left節(jié)點(diǎn)為末位節(jié)點(diǎn),指針域?yàn)?,即L[left][1]=1;④調(diào)整left到right范圍內(nèi)的節(jié)點(diǎn)指針域,原前驅(qū)節(jié)點(diǎn)變?yōu)楹罄^節(jié)點(diǎn),即L[i+1][1]=i。【習(xí)題鞏固】1.有如下Python程序段，使用單向鏈表存儲(chǔ)二進(jìn)制數(shù)，能夠?qū)崿F(xiàn)輸人一個(gè)十進(jìn)制數(shù)后，通過程序輸出該十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的結(jié)果。劃線處應(yīng)填入的正確代碼是num=int(input("請(qǐng)輸入一個(gè)十進(jìn)制數(shù):"))a=[]head=1whilenum>0:a.append([num%2,head])head=①num=num//2p=headwhilep!=1:print(a[p][0],end="")②A.①len(a)1②p=a[p][1]B.①len(a)②p=a[p][1]C.①head1②p=p1D.①head+1②p=p+12.已知一個(gè)鏈表a，其a[i][0]存儲(chǔ)索引i下節(jié)點(diǎn)的數(shù)據(jù)區(qū)域，a[i][1]存儲(chǔ)i下節(jié)點(diǎn)的指針區(qū)域。對(duì)當(dāng)前鏈表中的一個(gè)節(jié)點(diǎn)p（索引為p），若要?jiǎng)h除p的后一個(gè)節(jié)點(diǎn)q（q=a[p][1]），則應(yīng)執(zhí)行下述（）語(yǔ)句。A.a[p]=a[q] B.a[p][1]=a[q][1]C.a[p]=a[a[q][1]] D.a[p]=a[q];a[p][1]=a[q][1]3.采用列表模擬單向鏈表，data[p][0]為數(shù)據(jù)區(qū)域，data[p][1]為指針區(qū)域。在單向鏈表指針為p的節(jié)點(diǎn)之后插入指針為s的節(jié)點(diǎn)，正確的操作是（）A.data[s][1]=pdata[p][1]=data[s][1]B.data[p][1]=sdata[s][1]=data[p][1]C.data[s][1]=data[p][1]data[p][1]=sD.data[p][1]=data[s][1]data[s][1]=p4.使用二維嵌套列表模擬單鏈表，則下列單鏈表中的數(shù)據(jù)成升序排列的是()A.head=0,[[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,4]]C.head=1,[[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.某校軍訓(xùn)，需要按照身高由低到高排成n行5列的方陣。某班學(xué)生按照身高（100≤身高≤199）由低到高編寫編號(hào)并將相關(guān)信息存在如題151圖所示"stu.txt"文件中。根據(jù)教官提出的排方陣要求，排成如題152圖所示方陣，方陣各點(diǎn)顯示學(xué)生編號(hào)。題51圖題52圖題53圖現(xiàn)有延遲報(bào)道學(xué)生歸隊(duì)，歸隊(duì)學(xué)生編號(hào)延續(xù)該班現(xiàn)有編號(hào)依次往后，編寫程序完成下列任務(wù)：輸入學(xué)生身高，輸出新的方陣布局圖。例如：輸入學(xué)生身高為168，新的方陣布局圖如題53圖所示，學(xué)生在方陣的位置：3,4。（1）若插入學(xué)生身高為160cm，根據(jù)題151圖及范例，該學(xué)生應(yīng)該在題52圖方陣中的幾行幾列。（2）為實(shí)現(xiàn)上述功能，請(qǐng)?zhí)顚憚澗€處代碼。f=open("stu.txt","r")a=[]line=f.readline().split()i=1whileline!=[]:a.append([line[0],line[1],i])i+=1line=f.readline().split()n=len(a)1a[n][2]=1sg=input("請(qǐng)輸入插入的學(xué)生身高(cm):")xh=str(len(a))head=1p=head;q=headwhile①:p=qq=a[q][2]ifq==head:②head=len(a)1else:a.append([xh,sg,a[p][2]])a[p][2]=len(a)1p=headm=1whilep!=1:ifm!=5:print(a[p][0],end="")m+=1else:print(a[p][0])m=1③6.雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)節(jié)點(diǎn)中都有兩個(gè)指針，分別指向直接前驅(qū)和直接后驅(qū)。在Python中可以使用二維列表來模擬雙向鏈表，用包含3個(gè)元素的列表來表示每一個(gè)節(jié)點(diǎn)，其中第一個(gè)元素存儲(chǔ)數(shù)據(jù)，后兩個(gè)元素分別存儲(chǔ)指向前驅(qū)和后驅(qū)的指針。若沒有前驅(qū)或后繼節(jié)點(diǎn)，則對(duì)應(yīng)的指針值為－1。下列程序生成了一些隨機(jī)正整數(shù)，并依次存儲(chǔ)到一個(gè)雙向鏈表a中。現(xiàn)要求刪除其中值為偶數(shù)的節(jié)點(diǎn)，請(qǐng)?jiān)趧澗€處填入合適的代碼。importrandoma＝[]head＝－1foriinrange(8)：node＝[random.randint(1，9)，－1，head]a.append(node)ifhead?。剑?：#非空鏈表a[head][1]＝len(a)－1head＝____①____p＝headwhilep?。剑?：ifa[p][0]%2＝＝0：ifa[p][1]！＝－1：#有前驅(qū)節(jié)點(diǎn)a[a[p][1]][2]＝____②____ifa[p][2]?。剑?:#有后繼節(jié)點(diǎn)a[a[p][2]][1]＝a[p][1]ifhead＝＝p：#刪除頭節(jié)點(diǎn)head＝____③____p＝a[p][2]7.旋轉(zhuǎn)鏈表：對(duì)一個(gè)鏈表進(jìn)行個(gè)別元素的旋轉(zhuǎn)，比如原鏈表順序如：c→t→b→a→h，若設(shè)定旋轉(zhuǎn)系數(shù)k=2，則旋轉(zhuǎn)后鏈表順序變?yōu)椋篴→h→c→t→b，k=2即表示將鏈表最后一個(gè)元素旋轉(zhuǎn)至第1個(gè)執(zhí)行兩次，使原先最后的兩個(gè)元素如上述表示旋轉(zhuǎn)為前面兩個(gè)。輸出效果如圖輸出效果如圖所示：原鏈表：c→t→b→a→h輸入旋轉(zhuǎn)系數(shù)k:3旋轉(zhuǎn)后：b→a→h→c→t按照以上程序運(yùn)行的要求補(bǔ)充下列代碼，完成上述功能。defprintLink(lstlink,point):whilelstlink[point][1]!=1:print(lstlink[point][0],'→',end='')①print(lstlink[point][0])list1=[['t',2],['a',4],['b',1],['c',0],['h',1]]head=3print('原鏈表：',end='')printLink(list1,head)pre=1k=int(input('輸入旋轉(zhuǎn)系數(shù)k:'))foriinrange(k):cur=headwhilelist1[cur][1]!=1:②cur=list1[cur][1]else:list1[cur][1]=head③list1[pre][1]=1print('旋轉(zhuǎn)后：',end='')printLink(list1,head)8.臨近年關(guān)，學(xué)校為活躍新年氣氛，舉辦迎新年聯(lián)歡活動(dòng)，最后一個(gè)節(jié)目為“我是大贏家”抽獎(jiǎng)活動(dòng)，為增強(qiáng)互動(dòng)效果，最后中大獎(jiǎng)的中獎(jiǎng)?wù)哂山處焸冏砸鸦?dòng)產(chǎn)生，游戲規(guī)則是：全校所有教工，每人獲得一個(gè)隨機(jī)編號(hào)，編號(hào)不得復(fù)，然后按照編號(hào)大小順時(shí)針手拉手圍成一個(gè)圈，最后一個(gè)老師與第一個(gè)老師手拉手，接下來由第１個(gè)人指定m的值，從編號(hào)為１的人開始報(bào)數(shù)（1，2，3…），報(bào)到m的人出圈，不再參加互動(dòng)游戲，接著再由出圈人的上一位老師新指定m的值，并重新開始報(bào)數(shù)，逆時(shí)針報(bào)到m的人出列，游戲過程中出圈的人由老師們自已決定，如此繼續(xù)，順時(shí)針出一個(gè)人，逆時(shí)針出一個(gè)人，直到圈中只剩下一個(gè)人，他就是今天的最大贏家。小明編寫了一個(gè)Python程序?qū)崿F(xiàn)上述功能，程序運(yùn)行時(shí)，輸入?yún)⒓佑螒虻娜藬?shù)，每次有人出圈后，再輸入下一個(gè)要出圈的人數(shù)。#刪除索引為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]returnheadn=int(input("請(qǐng)輸入?yún)?shù)游戲的人數(shù)"))a=[[i+1,i1,i+1]foriinrange(n)]a[0][1]=n1a[n1][2]=0p=head=0while②:m=int(input("請(qǐng)輸入順時(shí)針數(shù)第幾位人出局"))foriinrange(m1):③head=delete(a,head,p)p=a[p][1]#退回到上一位游戲者ifa[head][1]!=head:m=int(input("請(qǐng)輸入逆時(shí)針數(shù)第幾位人出局"))foriinrange(m1):p=a[p][1]head=delete(a,head,p)④#退回到上一位游戲者print(a[head])參考答案1.A2.B3.C4.D5.(1)1,5（1分）（2）①a[q][1]<sgandq!=1或int(a[q][1])<int(sg)andq!=1（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號(hào)所在位。依此類推，身高160的同學(xué)，插入位應(yīng)為原05號(hào)學(xué)生所在位，即1，5⑵本題是一個(gè)比較典型的鏈表應(yīng)用。程序首先通過循環(huán)構(gòu)建了一個(gè)a列表：列表形式如：[[“01”,”156”,1],[“02”,”159”,2],[“03”,”159”,3],........]每項(xiàng)的最后一位，如[“01”,”156”,1]中的1，是指向后繼節(jié)點(diǎn)的指針，因此a列表可以理解為一個(gè)單向鏈表。由于原數(shù)據(jù)是按身高升序排序，接下來問題轉(zhuǎn)換為：如何在一個(gè)有序鏈表中插入數(shù)據(jù)？插入過程分成兩步：1、從頭節(jié)點(diǎn)開始向后尋找插入位置2、根據(jù)插入位置的不同，分為在鏈表頭部插入和中間插入兩種情況處理填空①處語(yǔ)句是從鏈頭開始向后尋找插入位置，p為當(dāng)前節(jié)點(diǎn)，q為p的后繼節(jié)點(diǎn)，從出循環(huán)后的判斷ifq==head:可以看出，程序判斷的是q點(diǎn)對(duì)應(yīng)數(shù)值a[q][1]與sg的關(guān)系，結(jié)合⑴空，繼續(xù)向后找的條件是：a[q][1]<sg，同時(shí)為了保證鏈表還未遍歷到尾部，循環(huán)條件應(yīng)為：q!=1anda[q][1]<sg。出循環(huán)即找到插入位置，在p、q之間，若q==head，說明數(shù)據(jù)要插在鏈表的頭部，此時(shí)首先向鏈表追加數(shù)據(jù)，同時(shí)設(shè)定后繼節(jié)點(diǎn)是head，然后修改鏈頭head位置（head=len(a)1）②處填：a.append([xh,sg,head])③處所在循環(huán)用于遍歷輸出鏈表，每5個(gè)一行輸出，p變量為鏈表指針，每處理一個(gè)數(shù)據(jù)指針后移一位，即③處填：p=a[p][2]6.①len(a)－1②a[p][2]③a[p][2]解析：空①處在生成鏈表節(jié)點(diǎn)后，把頭節(jié)點(diǎn)的指針指向最后節(jié)點(diǎn)的元素位置；空②處刪除值為偶數(shù)的節(jié)點(diǎn)，當(dāng)有前驅(qū)節(jié)點(diǎn)，需要修改新節(jié)點(diǎn)指針指向與前一節(jié)點(diǎn)的指針指向一致，故答案為a[p][2]；刪除的節(jié)點(diǎn)如果是頭節(jié)點(diǎn)時(shí)，需修改頭指針指向新節(jié)點(diǎn)，故③處答案為a[p][2]。7.①point=lstlink[point][1]②pre=cur③head=cur等價(jià)答案：head=list1[pre][1]解析：①為輸出鏈表的函數(shù)，輸出1個(gè)元素后，當(dāng)前元素的指針由下一個(gè)元