【文章內(nèi)容簡(jiǎn)介】 寫(xiě)符合上述要求的ListLocate(la，x)運(yùn)算的算法，返回找到結(jié)點(diǎn)的指針。 【題目分析】首先在雙向鏈表中查找數(shù)據(jù)值為x的結(jié)點(diǎn)，查到后，將結(jié)點(diǎn)從鏈表上摘下，然后再順結(jié)點(diǎn)的前驅(qū)鏈查找該結(jié)點(diǎn)的位置。 DLinkList ListLocate(DLinkedList L，ElemType x)∥ L是帶頭結(jié)點(diǎn)的按訪問(wèn)頻度遞減的雙向鏈表,本算法先查找數(shù)據(jù)x∥查找成功時(shí)結(jié)點(diǎn)的訪問(wèn)頻度域增1，最后將該結(jié)點(diǎn)按頻度遞減插入鏈表中{DLinkList p=Lnext,q。 ∥p為L(zhǎng)表的工作指針，q為p的前驅(qū)，用于查找插入位置 while(p amp。amp。 pdata!=x) p=pnext。∥ 查找值為x的結(jié)點(diǎn) if(!p) {printf(“不存在所查結(jié)點(diǎn)\n”)。 exit(0)。} else { pfreq++。 ∥ 令元素值為x的結(jié)點(diǎn)的freq域加1 pnextprior=pprior。 ∥ 將p結(jié)點(diǎn)從鏈表上摘下 ppriornext=pnext。q=pprior。 ∥ 以下查找p結(jié)點(diǎn)的插入位置 while(q !=L amp。amp。 qfreqpfreq) q=qprior。 pnext=qnext。 qnextprior=p?！?將p結(jié)點(diǎn)插入 pprior=q。 qnext=p； } return(p)。 ∥返回值為x的結(jié)點(diǎn)的指針} ∥ 算法結(jié)束 三個(gè)帶頭結(jié)點(diǎn)的線(xiàn)性鏈表la、lb和lc中的結(jié)點(diǎn)均依元素值自小至大非遞減排列（可能存在兩個(gè)以上值相同的結(jié)點(diǎn)），編寫(xiě)算法對(duì)la表進(jìn)行如下操作：使操作后的la中僅留下三個(gè)表中均包含的數(shù)據(jù)元素的結(jié)點(diǎn)，且沒(méi)有值相同的結(jié)點(diǎn)，并釋放所有無(wú)用結(jié)點(diǎn)。限定算法的時(shí)間復(fù)雜度為O（m+n+p），其中m、n和p分別為三個(gè)表的長(zhǎng)度?！绢}目分析】 留下三個(gè)鏈表中公共數(shù)據(jù)，首先查找兩表la和B中公共數(shù)據(jù)，再去lc中找有無(wú)該數(shù)據(jù)。要消除重復(fù)元素，應(yīng)記住前驅(qū)，要求時(shí)間復(fù)雜度O（m+n+p），在查找每個(gè)鏈表時(shí)，指針不能回溯。LinkedList lmon（LinkedList la，lb，lc）∥本算法使la表留下la、lb和lc三個(gè)非遞減有序表共同結(jié)點(diǎn)，無(wú)重復(fù)元素{pa=lanext；pb=lbnext；pc=lcnext；∥pa,pb和pc分別是la,lb和lc三個(gè)表的工作指針pre=la；ladata=MaxElemType ∥pre是la表當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針,頭結(jié)點(diǎn)作監(jiān)視哨while（pa amp。amp。 pb amp。amp。 pc） ∥當(dāng)la,lb和lc表均不空時(shí)，查找三表共同元素 {while(paamp。amp。padata==predata) {u=pa。 pa=panext。 free(u)。}//刪la中相同元素while（pb amp。amp。 pc） if（pbdatapcdata）pb=pbnext。 ∥結(jié)點(diǎn)元素值小時(shí)，后移指針 else if（pbdatapcdata）pc=pcnext； else break 。∥處理lb和lc表元素值相等的結(jié)點(diǎn) if(pb amp。amp。 pc){while（pa amp。amp。 padatapcdata）{u=pa；pa=panext；free（u）；} if(pa amp。amp。 padatapcdata){pb=pbnext。 pc=pcnext。} else if(pa amp。amp。 padata==pcdata)∥pc，pa和pb對(duì)應(yīng)結(jié)點(diǎn)元素值相等 {prenext=pa；pre=pa；pa=panext；∥將新結(jié)點(diǎn)鏈入la表 pb=pbnext；pc=pcnext； ∥鏈表的工作指針后移 }∥pc，pa和pb對(duì)應(yīng)結(jié)點(diǎn)元素值相等 } }∥while（pa amp。amp。 pb amp。amp。 pc）prenext=null； ∥置新la表表尾while（pa!=null） ∥刪除原la表剩余元素。{u=pa；pa=panext；free（u）；} }∥算法結(jié)束【算法討論】 算法中l(wèi)a表、lb表和lc表均從頭到尾（嚴(yán)格說(shuō)lb、lc中最多一個(gè)到尾）遍歷一遍，算法時(shí)間復(fù)雜度符合O（m+n+p）。算法主要由while（pa amp。amp。 pb amp。amp。 pc）控制。三表有一個(gè)到尾則結(jié)束循環(huán)。要注意頭結(jié)點(diǎn)的監(jiān)視哨的作用，否則第一個(gè)結(jié)點(diǎn)要特殊處理。算法最后要給新la表置結(jié)尾標(biāo)記，同時(shí)若原la表沒(méi)到尾，還應(yīng)釋放剩余結(jié)點(diǎn)所占的存儲(chǔ)空間。第3章 棧和隊(duì)列 一、基礎(chǔ)知識(shí)題 有五個(gè)數(shù)依次進(jìn)棧：1，2，3，4，5。在各種出棧的序列中，以3，4先出的序列有哪幾個(gè)。（３在４之前出棧）?！窘獯稹?4215 ，34251， 34521 鐵路進(jìn)行列車(chē)調(diào)度時(shí)，常把站臺(tái)設(shè)計(jì)成棧式結(jié)構(gòu)，若進(jìn)站的六輛列車(chē)順序?yàn)椋?，2，3，4，5，6， 那么是否能夠得到435612， 325641， 154623和135426的出站序列，如果不能，說(shuō)明為什么不能； 如果能， 說(shuō)明如何得到(即寫(xiě)出進(jìn)棧或出棧的序列)。 【解答】輸入序列為123456，不能得出435612和154623。不能得到435612的理由是，輸出序列最后兩元素是12，前面4個(gè)元素（4356）得到后，棧中元素剩12，且2在棧頂，不可能讓棧底元素1在棧頂元素2之前出棧。不能得到154623的理由類(lèi)似，當(dāng)棧中元素只剩23，且3在棧頂，2不可能先于3出棧。得到325641的過(guò)程如下：1 2 3順序入棧，32出棧，得到部分輸出序列32；然后45入棧，5出棧，部分輸出序列變?yōu)?25；接著6入棧并退棧，部分輸出序列變?yōu)?256；最后41退棧，得最終結(jié)果325641。 得到135426的過(guò)程如下：1入棧并出棧，得到部分輸出序列1；然后2和3入棧，3出棧，部分輸出序列變?yōu)?3；接著4和5入棧，5，4和2依次出棧，部分輸出序列變?yōu)?3542；最后6入棧并退棧，得最終結(jié)果135426。 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少？【解答】2和 4 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e3，e5，e4，e6，e2，e1，則棧S的容量至少應(yīng)該是多少？【解答】 4 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么，如何判斷“空”和“滿(mǎn)”。【解答】循環(huán)隊(duì)列解決了常規(guī)用0m1的數(shù)組表示隊(duì)列時(shí)出現(xiàn)的“假溢出”（即隊(duì)列未滿(mǎn)但不能入隊(duì)）。在循環(huán)隊(duì)列中我們?nèi)杂藐?duì)頭指針等于隊(duì)尾指針表示隊(duì)空，而用犧牲一個(gè)單元的辦法表示隊(duì)滿(mǎn)，即當(dāng)隊(duì)尾指針加1（求模）等于隊(duì)頭指針時(shí)，表示隊(duì)列滿(mǎn)。也有通過(guò)設(shè)標(biāo)記以及用一個(gè)隊(duì)頭或隊(duì)尾指針加上隊(duì)中元素個(gè)數(shù)來(lái)區(qū)分隊(duì)列的“空”和“滿(mǎn)”的。 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)和出隊(duì)的時(shí)間如何？若只設(shè)尾指針呢？【解答】若只設(shè)頭指針，則入隊(duì)的時(shí)間為O(n），出隊(duì)的時(shí)間為O(1)。若只設(shè)尾指針，則入隊(duì)和出隊(duì)的時(shí)間均為O(1)。 指出下面程序段的功能是什么？(1) void demo1(SeqStack S){int i，arr[64]，n=0。 while(!StackEmpty(S)) arr[n++]=Pop(S)。 for(i=0。in。i++) Push(S，arr[i])。}【解答】程序段的功能是實(shí)現(xiàn)了棧中元素的逆置。(2) void demo2(SeqStack S，int m)∥設(shè)棧中元素類(lèi)型為int型{int x。SeqStack T。 StackInit(T)。 while(!StackEmpty(S))if((x=Pop(S)!=m) Push(T，x)。while(!(StackEmpty(T)) {x=Pop(T)。 Push(S，x)。}}【解答】程序段的功能是刪除了棧中值為m的元素。(3) void demo3(SeQueue Q，int m)∥設(shè)隊(duì)列中元素類(lèi)型為int型{int x。SeqStack S。 StackInit(S)。 while(!QueueEmpty(Q)){x=QueueOut(Q)。 Push(S，x)。}while(!StackEmpty(S)){x=Pop(s)。 QueueIn(Q，x)。}}【解答】程序段的功能是實(shí)現(xiàn)了隊(duì)列中元素的逆置。 試將下列遞推過(guò)程改寫(xiě)為遞歸過(guò)程。void ditui(int n){i=n。 while(i1) printf(i)。}【解答】void digui(int n){if(n1){printf(n)。 digui(n1)。 }} 寫(xiě)出下列中綴表達(dá)式的后綴表達(dá)式： (1)A*B*C (2)(A+B)*CD (3)A*B+C/(DE) (4)(A+B)*D+E/(F+A*D)+C【解答】(1)ABC** (2)AB+C*D (3)AB*CDE/+ (4)AB+D*EFAD*+/+C+ 選擇題：循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為( )。 A. rear=rear+1 B. rear=(rear+1) % (m1)C. rear=(rear+1) % m D. rear=(rear+1) % (m+1)【解答】D 選擇題：4個(gè)園盤(pán)的Hahoi塔，總的移動(dòng)次數(shù)為( )。 B. 8 【解答】C：允許對(duì)隊(duì)列進(jìn)行的操作有( )。 A. 對(duì)隊(duì)列中的元素排序 B. 取出最近進(jìn)隊(duì)的元素C. 在隊(duì)頭元素之前插入元素 D. 刪除隊(duì)頭元素【解答】D二、算法設(shè)計(jì)題 利用棧的基本操作，編寫(xiě)求棧中元素個(gè)數(shù)的算法。【題目分析】 將棧值元素出棧，出棧時(shí)計(jì)數(shù)，直至棧空?！舅惴ā?int StackLength(Stack S) {//求棧中元素個(gè)數(shù) int n=0。 while(!StackEmpty(S) {n++。 Pop(S)。 } return n。 }算法討論：若要求統(tǒng)計(jì)完元素個(gè)數(shù)后，不能破壞原來(lái)?xiàng)?，則在計(jì)數(shù)時(shí)，將原棧導(dǎo)入另一臨時(shí)棧，計(jì)數(shù)完畢，再將臨時(shí)棧倒入原棧中。 int StackLength(Stack S) {//求棧中元素個(gè)數(shù) int n=0。 Stack T。StackInit(T)。 //初始化臨時(shí)棧T while(!StackEmpty(S) {n++。 Push(T,Pop(S))。 }while(!StackEmpty(T) {Push(S,Pop(T))。 } return n。 } 雙向棧S是在一個(gè)數(shù)組空間V[m]內(nèi)實(shí)現(xiàn)的兩個(gè)棧，棧底分別處于數(shù)組空間的兩端。試為此雙向棧設(shè)計(jì)棧初始化Init(S)、入棧Push(S，i，x)、出棧Pop(S，i)算法，其中i為0或1，用以指示棧號(hào)。[題目分析]兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥?，初始時(shí)，s1棧頂指針為1，s2棧頂為m。兩棧頂指針相鄰時(shí)為棧滿(mǎn)。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。define ElemType int ∥假設(shè)元素類(lèi)型為整型typedef struct {ElemType V[m]。 ∥?？臻g int top[2]。 ∥top為兩個(gè)棧頂指針}stk。stk S。 ∥S是如上定義的結(jié)構(gòu)類(lèi)型變量，為全局變量(1) 棧初始化int Init() {[0]=1。 [1]=m。 return 1。 //初始化成功}(2) 入棧操作：int push(stk S ,int i,int x)∥i為棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，否則返回0{if(i0||i1){printf(“棧號(hào)輸入不對(duì)\n”)。exit(0)。}if([1][0]==1) {printf(“棧已滿(mǎn)\n”)。return(0)。}switch(i) {case 0: [++[0]]=x。 return(1)。 break。case 1: [[1]]=x。 return(1)