數(shù)據(jù)結(jié)構(gòu)--例題剖析

1、當(dāng)j=4時(shí)，找到的關(guān)鍵字應(yīng)是5為數(shù)組長度/在后半部分繼續(xù)進(jìn)行劃分/在前半部分繼續(xù)進(jìn)行劃分!對給定關(guān)鍵字序號j(1vjvn),要求在無序記錄A1.n中找到關(guān)鍵字從小到大 排在第j位上的記錄，寫一個(gè)算法利用快速排序的劃分思想實(shí)現(xiàn)上述查找。(要求 用最少的時(shí)間和最少的空間)例如：給定無序關(guān)鍵字7,5,1,6,2,8,9,3, int partiti on( RecType A, int 1, int n) int i=1,j=n ;x=Ai.key;i=1;while(ivj)while(i=x) if(ij) Ai+=Aj;while(ij & Ai.key=x) i+; if(ij) Aj-=A

2、i; return i;void Fin d_j(RecType A,i nt n ,i nt j) ni=partition (A,1, n);while(i!=j)if(ij) i=partiti on( A,i+1, n);elsei=partitio n( A,1,i-1);因裝填因子為0.7，有7個(gè)元素，故哈希表長 m=7/0.7=10構(gòu)造的哈希表如下： 散列地址 0123456789關(guān)鍵字 714811 30 18 9比較次數(shù)1211133答:ASL 成功=1/7*(1*4+2*1+3*2)=12/7,失敗=1/7*(3+2+1+2+1+5+4)=18/7 設(shè)圖的頂點(diǎn)只是編號1 n

3、,邊的信息是有(用1表示)或無(用0表示)，這時(shí)可 用鄰接矩陣表示圖的存儲結(jié)構(gòu)。請編寫算法建立無向圖的鄰接矩陣的存儲結(jié)構(gòu)void creatgraph(int M,int n,int e) /設(shè)有 n 個(gè)頂點(diǎn) e 條邊int i,j;for (i=1;i=n ;i+)for(j=1;j=n ;j+)Mij=0;for (i=1;i ij;Mij=1; Mji=1;在根指針t所指二叉排序樹中遞歸查找某關(guān)鍵字等于k的數(shù)據(jù)元素BSTree SearchBST1(BSTree t，keyType k)if(!t|k=t-key) return(t);else if(kkey) return(Searc

4、hBST1(t-lchild，k);else return(SearchBST1(t-rchild ， k);寫出快速排序中一趟劃分的算法。int partition(int R,int s,int t) s和t是數(shù)組的低下標(biāo)和高下標(biāo)int i=s,j=t,x=Ri.key;while(ivj)while(i=x)j-;Ri=Rj;while(ij & Ri.key=x)i+;Rj=Ri;ri=x;return i;要求完全利用循環(huán)隊(duì)列中的元素空間，設(shè)置一個(gè)標(biāo)志域tag，并以tag的值是0或1來區(qū)分尾指針和頭指針相同時(shí)的隊(duì)列狀態(tài)是“空”還是“不空”請編寫與此 結(jié)構(gòu)相對應(yīng)的出隊(duì)算法。相關(guān)類型定義

5、如下：void QueueOut(CycQueue cq);if(cq.tag=0) cout隊(duì)列為空 n;elsecq.fr on t=( cq.fr on t+1) % m;if(cq.fr on t= cq.rear)cq.tag=0; / 空隊(duì)列 !設(shè)n是非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是(O(log2n)x=2; while(xlchild); hr=Height(bt-rchild); if(hlhr) return(hl+1); else return(h 葉1);/左子樹的深度/右子樹的深度/二叉樹的深度以二叉鏈表作為存儲結(jié)構(gòu)，試編寫求二叉樹中葉子數(shù)的算法。int LeafC

6、ou nt(BiTree T)if(!T) return 0;/空樹沒有葉子elseif(!T-lchild & !T-rchild) return 1;/葉子結(jié)點(diǎn)else return LeafCou nt(T-lchild)+LeafCou nt(T-rchild);設(shè)有順序放置的n個(gè)桶,每個(gè)桶中裝有一粒礫石，每粒礫石的顏色是紅、白、藍(lán)之 一。要求重新安排，使得紅色礫石在前，白色礫石居中，藍(lán)色礫石居后。對每粒礫 石的顏色只能察看一次，且只允許交換操作來調(diào)整礫石的位置。void QkSort(rectype r ,i nt n) /int i=0, j=0, k=n-1;while(j=k)

7、if( rj=1)/ri 交換 rj; i+; j+; else if( rj=2) j+;/else(rj=3)rj 交換 rk; k-; 把十進(jìn)制n轉(zhuǎn)換為八進(jìn)制void Conv ert(i nt n ) if(n !=0)Con vert( n/8);coutvoid Un io n(arrList&A,arrList &B) /union 是類 arrList 的友元int m=A.curLe n;int n=B.curLen;m， n分別為線性表 A和B的長度。int k=m+n-1;k為結(jié)果線性表的工作指針(下標(biāo))int i=m-1;int j=n-1;/i ，j分別為線性表A和B

8、的工作指針(下標(biāo))while (i=0 & j=0)if (A.aListi=B.aListj)A.aListk-=A.aListi-;elseA.aListk-=B.aListj-;while (j=0)A.aListk-=B.aListj-;A.curLe n=m+n;已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時(shí)間復(fù)雜度為0(n)、空間復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。void arrList :DelAll(T item) int i=0,j=curLen-1;/設(shè)置數(shù)組低、高端指針(下標(biāo))while(i=j) while(i=j & aListi

9、!=item) i+;while(i=j & aListj=item) j-;if(ij) aListi+=aListj-;curLe n=i;PS:若題目要求元素間相對順序不變，可用如下語句段：void arrList :DelAll(T item)i=0 ； j=0 ；while ( jn )if(aListj=item )j+ ；else Ai+=Aj+； /最后線性表中的元素個(gè)數(shù)是i。將非遞減有序的單鏈表la和lb合并成新的非遞減有序單鏈表lc，并要求利用 原表空間In kList* Un io n(ln kList* la, l nkList * lb) /友元函數(shù)Link*pa,*

10、pb,*pc;/分別是是鏈表la、lb、lc的工作指針ln kList* lc;lc=la;/lc利用la空間，將lb合并進(jìn)來pa=(la-head)-n ext; (la-head)-n ext=NULL; pb=(lb-head)-n ext; (lb-head)-n ext=NULL;pc=lc-head;while(pa & pb)/la 和 lb 均非空中元素插入lc中元素插入lcif(pa-datadata)/lapc-n ext=pa; pc=pa; pa=pa-n ext; else/lbpc-n ext=pb; pc=pb; pb=pb-n ext; if(pa) pc-ne

11、xt=pa;/ 若 pa 未到尾，將 pc 指向 pawhile(pa-n ext)pa=pa-n ext;lc-tail=pa;/修改尾指針else if(pb) pc-next=pb;/ 若 pb 未至U尾，將 pc 指向 pbwhile(pb-n ext)pb=pb-n ext;lc-tail=pb;/修改尾指針delete lb;return(lc);假設(shè)一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域pre、data、next。其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針(null ); next為指針域，它指向后繼結(jié)點(diǎn)。 請?jiān)O(shè)計(jì)算法，將此表改成雙向循環(huán)鏈表。void SToDouble (

12、Lin kedList la ) while (la-next-pre=null)la-n ext-pre=la;la=la-n ext；請編寫算法將單鏈表L1拆成二個(gè)鏈表，其中以L1為頭的鏈表保持原來向后的鏈 接，另一個(gè)鏈表的表頭為L2,其鏈接方向與L1相反，L1包含原鏈表的奇數(shù)序號 的結(jié)點(diǎn)，L2包含原鏈表的偶數(shù)序號的結(jié)點(diǎn)。Li nk * DisU nion (Li nk * L1 , Li nk * L2 ) int i=0;Li nk *p,*s, *tail, * L2=new Li nk(NULL);L2-next=NULL;/以L2為頭指針的空鏈表p=L1- n ext; tail

13、=L1;while(p)i+;if(i%2)tail-n ext=p; tail=p; p=p-n ext;elses=p-next; p-next=L2-next; /s儲存 p 的下一個(gè)結(jié)點(diǎn)L2- next=p; p=s;/采用頭插法逆置偶數(shù)序號的結(jié)點(diǎn)tail-next=NULL; / 置 L1 表尾已知p是指向單向循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針，試編寫只包含一個(gè)循環(huán)的算法，將線性表(a1,an)改造為(a1,an-1,an, an-1,a1)Lin k* Cycll nsert(Li nk* p )q=p-next;q指向a1結(jié)點(diǎn)，工作指針t=new Li nk(NULL);t-data=q

14、-data; t-next=p-next; r=t; /r記住 a1 結(jié)點(diǎn)的指針p-n ext=t;q=q-n ext;while(q!=p) t=new Li nk(NULL);t-data=q-data; t-n ext=p-n ext; p-n ext=t;q=q-n ext;p=r; return p;設(shè)ha和hb分別是兩個(gè)帶頭結(jié)點(diǎn)的非遞減有序單鏈表的頭指針，將這兩個(gè)有序鏈表合并成一個(gè)非遞增有序的單鏈表。要求使用原鏈表空間，表中無重復(fù)數(shù)據(jù)。Li nk* Union (Li nk *ha, Li nk *hb)pa=ha-n ext;pb=hb-n ext;ha-next=null; /

15、ha作結(jié)果鏈表的頭指針，先將結(jié)果鏈表初始化為空while(pa & pb)while(pa-n ext & pa-data=pa-n ext-data)u=pa-n ext;pa-n ext=u-n ext;delete u;while(pb-n ext & pb-data=pb-n ext-data) u=pb-n ext; pb-n ext=u-n ext; delete u; if(pa-datadata) /頭插法，逆序建新表 r=pa-next; /將pa的后繼結(jié)點(diǎn)暫存于r恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn)pa-n ext=ha-n ext; ha-n ext=pa; pa=r;/else i

16、f(pb-datadata) r=pb-n ext;/pb-n ext=ha-n ext;ha-n ext=pb;pb=r;/ else u=pb;將pb的后繼結(jié)點(diǎn)暫存于r恢復(fù)pb為當(dāng)前待比較結(jié)點(diǎn)/刪除鏈表pb=pb-n ext; delete u; pb和pa中的重復(fù)元素/避免再對pa寫下面的while語句if(pa) pb=pa;while(pb)while(pb-n ext & pb-data=pb-n ext-data) u=pb-n ext; pb-n ext=u-n ext; delete u; r=pb-n ext; pb-n ext=ha-n ext; ha-n ext=pb;

17、 pb=r; /將尚未到尾的表逆置到結(jié)果表中，注意也要?jiǎng)h除重復(fù)元素return ha;以二叉鏈表作為存儲結(jié)構(gòu)，設(shè)計(jì)算法交換二叉樹中所有結(jié)點(diǎn)的左、右子樹void cha nge(BiTree T) if(T!=NULL)cha nge(T-lchild);cha nge(T-rchild); t=T-lchild;T-lchild=T-rchild;T-rchild=t;以二叉鏈表作為存儲結(jié)構(gòu)，設(shè)計(jì)算法拷貝二叉樹。BiTree copy(BiTree T) BiTree T1;if(T=nu II) T1= null;elseT仁(BiTree)malloc(sizeof(BiNode); /申

18、請結(jié)點(diǎn)T1-data=T-data;T1-lchild=copy(T-lchild);T1-rchild=copy(T-rchild);return T1;!單鏈表的逆置template vclass T / 單鏈表的元素類型為Tvoid In kList : inv ert()/逆置單鏈表Lin k *p=head- next, *r; /p為工作指針，指向第一個(gè)元素head-next=NULL; /保留第一個(gè)元素的指針后，將頭結(jié)點(diǎn)的指針域置空tail=p; while(p!=NULL) r=p-n ext;head-n ext=p; p=r;/頭結(jié)點(diǎn)的指針域指向新插入的結(jié)點(diǎn)/恢復(fù)待處理結(jié)點(diǎn)

19、/將原鏈表的元素按頭插法插入/暫存p的后繼p-n ext=head- next; /逆置(頭插法插入)!已知一個(gè)帶有表頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法，查 找鏈表中倒數(shù)第k個(gè)位置上的結(jié)點(diǎn)(k為正整數(shù))，若查找成功，算法輸出該結(jié) 點(diǎn)的data域的值，并返回1否則，只返回0,int SearchI nvK(c onst int k) /在單鏈表la上查找倒數(shù)第k個(gè)結(jié)點(diǎn)p=list-li nk; /p指向當(dāng)前待處理元素q=list; /若成功,q指向倒數(shù)第k個(gè)元素i=1;while(p & ilink

20、; if(p=null) coutvv “不存在 n ” ； return 0; while(p) q=q-li nk; p=p-li nk; cout “倒數(shù)第 k 個(gè)元素的 data 域：” datan ext; Q= B-n ext; num= 0;while (P!=NULL) & (Q!=NULL)switch case P-datadata:P= P-n ext; num= nu m+1; break; case P-dataQ-data:Q= Q-n ext; break;case P-data=Q-data:P= P-n ext; Q= Q-n ext ; break;whil

21、e (P!=NULL) num= num+1; P= P- next; judge = num=O;if (nu m!=0 )cout” Numberof elements that is in A but not in B=” 1)個(gè)整數(shù)存放到一維數(shù)組 R中。試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面 都盡可能高效的算法，將R中保存的序列循環(huán)左移P (0Pn個(gè)位置， 即將R 中的數(shù)據(jù)由(X0,X1,Xn-1 )變換為(Xp,Xp+1,Xn-1,X0,X1,Xp-1 )。(1) 給出算法的基本設(shè)計(jì)思想。(2根據(jù)設(shè)計(jì)思想，采用C或C+或 JAVA語言描述算法，關(guān)鍵之處給出注釋。(3)說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜

22、度和空間復(fù)雜度。(1)算法設(shè)計(jì)思想：按照下標(biāo)0到p-1、p到n-1、0到n-1的順序，將這三段分 別逆置，最后的結(jié)果即為所求。 void leftshift(i nt R, i nt p, i nt n)elemtype t;/t和數(shù)組R中的元素具有相同類型for(i=0;ip/2;i+)/逆置 0.p-1 段t=Ri; Ri=Rp-1-i； Rp-1-i=t;For(i=p;i(n+p)/2;i+)/逆置 p.n-1 段t=Ri; Ri=R n-1-i+p;R n-1-i+p=t;for(i=0;in/2;i+)/逆置0.n-1段，即整個(gè)數(shù)組逆置t=Ri; Ri=Rn-1-i; Rn-1-i

23、=t;(3)算法執(zhí)行了兩趟逆置，時(shí)間復(fù)雜度為0(n);用了一個(gè)輔助變量空間，空間復(fù)雜度為O(1)。討論：若采用直接左移p位，空間復(fù)雜度仍為O(1)，但時(shí)間復(fù)雜 度為O(np)。!在一個(gè)設(shè)la是帶頭結(jié)點(diǎn)的雙向鏈表的指針，其結(jié)點(diǎn)中除有 prior ，data和 next夕卜，還有一訪問頻度域freq，其值在鏈表初始使用時(shí)為0。當(dāng)在鏈表中進(jìn)行ListLocate(la ，x)運(yùn)算時(shí)，若查找失敗，則在表尾插入值為x的結(jié)點(diǎn)；若查找成功，值為x的結(jié)點(diǎn)的freq值增1，并要求鏈表按freq域值非增(遞減)的 順序排列，且最近訪問的結(jié)點(diǎn)排在頻度相同的結(jié)點(diǎn)的后面，使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。試編寫符合上述要求

24、的ListLocate(la ，x)運(yùn)算的算法，返回找到結(jié)點(diǎn)的指針。Dlink * ListLocate(Dlink * La ，T x)Dlink * p=La-next, *q=La; while(p&p-data!=x) q=p; p=p-next;if(!p) printf(“不存在所查結(jié)點(diǎn)，現(xiàn)插入之n ”)；s=new Link;s-data=x; s-freq=0;/ 插入值為 x 的結(jié)點(diǎn)s-n ext=p; s-prior=q;q-next=s; p=s;/ 返回 p 結(jié)點(diǎn);else p-freq+;/令元素值為x的結(jié)點(diǎn)的freq域加1p-next-prior=p-prior;

25、p-prior-next=p-next;/ 將 p 結(jié)點(diǎn)摘下q=p-prior;/以下查找p結(jié)點(diǎn)的插入位置while(q !=L & q-freqvp-freq) q=q-prior;p-next=q-next; q-next-prior=p;/ 將 p 結(jié)點(diǎn)插入 q 的后面p-prior=q; q-n ext=p;return(p); / 算法結(jié)束!L1與L2分別為兩單鏈表頭結(jié)點(diǎn)地址指針，且兩表中數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)域均為 一個(gè)字母。設(shè)計(jì)把L1中與L2中數(shù)據(jù)相同的連續(xù)結(jié)點(diǎn)順序完全倒置的算法。Link * PatternInvert(Link * L1, Link * L2) p=L1 ;/ p是每

26、趟匹配時(shí)L1中的起始結(jié)點(diǎn)前驅(qū)的指針q=L1-next ;/ q是L1中的工作指針s=L2-next ;/ s是L2中的工作指針。while (q & s )if (q-data=s-data ) q=q-next; s=s-next; /對應(yīng)字母相等指針 后移else p=p-next; q=p-next ; s=L2-next ; /失配時(shí)L1起始結(jié)點(diǎn)后移，L2從首結(jié)點(diǎn)開始。if ( s=null )/匹配成功，這時(shí)p為L1中與L2中首字母結(jié)點(diǎn)相同數(shù)據(jù)域結(jié)點(diǎn)的前驅(qū)，q為L1 中與L2最后一個(gè)結(jié)點(diǎn)相同數(shù)據(jù)域結(jié)點(diǎn)的后繼。p-n ext=q ; while (r!=q )；s=r- n extr-n ext=p-n