數(shù)據(jù)結(jié)構(gòu)經(jīng)典例題

1、數(shù)據(jù)結(jié)構(gòu)經(jīng)典例題1設(shè)計(jì)一個(gè)算法將L拆分成兩個(gè)帶頭節(jié)點(diǎn)的單鏈表L1和L2。voidsplit(LinkList*&L,LinkList*&L1,LinkList*&L2)LinkList*p=L-next,*q,*r1;/p指向第1個(gè)數(shù)據(jù)節(jié)點(diǎn)L1=L;/L1利用原來(lái)L的頭節(jié)點(diǎn)r1=L1;/r1始終指向L1的尾節(jié)點(diǎn)L2=(LinkList*)malloc(sizeof(LinkList);/創(chuàng)建L2的頭節(jié)點(diǎn)L2-next=NULL;置L2的指針域?yàn)镹ULLwhile(p!=NULL)r1-next=p;采用尾插法將*p(data值為ai)插入L1中r1=p;p=p-next;/p移向下一個(gè)節(jié)點(diǎn)(d

2、ata值為bi)q=p-next;/由于頭插法修改p的next域，故用q保存*p的后繼節(jié)點(diǎn)p-next=L2-next;采用頭插法將*卩插入L2中L2-next=p;p=q;/p重新指向ai+1的節(jié)點(diǎn)r1-next=NULL;/尾節(jié)點(diǎn)next置空查找鏈表中倒數(shù)第k個(gè)位置上的節(jié)點(diǎn)(k為正整數(shù))。若查找成功，算法輸出該節(jié)點(diǎn)的data域的值，并返回1；否則，只返回0。typedefstructLNodeintdata;structLNode*link;*LinkList;intSearchk(LinkListlist,intk)LinkListp,q;intcount=0;p=q=list-link

3、;while(p!=NULL)if(countlink;p=p-link;if(countdata);return(1);假定采用帶頭節(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個(gè)單詞有相同的后綴時(shí)，則可共享相同的后綴存儲(chǔ)空間。設(shè)str1和str2分別指向兩個(gè)單詞所在單鏈表的頭節(jié)點(diǎn)請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間上盡可能高效的算法，找出由str1和str2所指向兩個(gè)鏈表共同后綴的起始位置。typedefstructNodechardata;structNode*next;SNODE;SNODE*Findlist(SNODE*str1,SNODE*str2)intm,n;SNODE*p,*q;m=Listlen(str1);/求單

4、鏈表str1的長(zhǎng)度mn=Listlen(str2);/求單鏈表str2的長(zhǎng)度nfor(p=str1;mn;m-)/若m大，則str1后移m-n+1個(gè)節(jié)點(diǎn)p=p-next;for(q=str2;mnext;while(p-next!=NULL&p-next!=q-next)p=p-next;/p、q兩步后移找第一個(gè)指針值相等的節(jié)點(diǎn)q=q-next;returnp-next;intListlen(SNODE*head)/求單鏈表的長(zhǎng)度intlen=0;while(head-next!=NUL)len+;head=head-next;returnlen;設(shè)計(jì)一個(gè)算法，刪除一個(gè)單鏈表L中元素值最大的節(jié)

5、點(diǎn)。voiddelmaxnode(LinkList*&L)LinkList*p=L-next,*pre=L,*maxp=p,*maxpre=pre;while(p!=NULL)用p掃描整個(gè)單鏈表,pre始終指向其前驅(qū)節(jié)點(diǎn)if(maxp-datadata)/若找到一個(gè)更大的節(jié)點(diǎn)maxp=p;/更改maxpmaxpre=pre;/更改maxprepre=p;/p、pre同步后移一個(gè)節(jié)點(diǎn)p=p-next;maxpre-next=maxp-next;刪除*maxp節(jié)點(diǎn)free(maxp);釋放*maxp節(jié)點(diǎn)有一個(gè)帶頭節(jié)點(diǎn)的單鏈表L(至少有一個(gè)數(shù)據(jù)節(jié)點(diǎn))，設(shè)計(jì)一個(gè)算法使其元素遞增有序排列。voidsor

6、t(LinkList*&L)LinkList*p,*pre,*q;p=L-next-next;/p指向L的第2個(gè)數(shù)據(jù)節(jié)點(diǎn)L-next-next=NULL;/構(gòu)造只含一個(gè)數(shù)據(jù)節(jié)點(diǎn)的有序表while(p!=NULL)q=p-next;q保存*p節(jié)點(diǎn)后繼節(jié)點(diǎn)的指針pre=L;從有序表開(kāi)頭進(jìn)行比較,pre指向插入*卩的前驅(qū)節(jié)點(diǎn)while(pre-next!=NULL&pre-next-datadata)pre=pre-next;在有序表中找插入*p的前驅(qū)節(jié)點(diǎn)*prep-next=pre-next;/將*卩佗之后插入*卩pre-next=p;p=q;/掃描原單鏈表余下的節(jié)點(diǎn)6.有一個(gè)帶頭節(jié)點(diǎn)的雙鏈表L,

7、設(shè)計(jì)一個(gè)算法將其所有元素逆置，即第1個(gè)元素變?yōu)樽詈笠粋€(gè)元素，第2個(gè)元素變?yōu)榈箶?shù)第2個(gè)元素，最后一個(gè)元素變?yōu)榈?個(gè)元素。voidreverse(DLinkList*&L)/雙鏈表節(jié)點(diǎn)逆置DLinkList*p=L-next,*q;/p指向開(kāi)好節(jié)點(diǎn)L-next=NULL;while(p!=NULL)q=p-next;p-next=L-next;if(L-next!=NULL)構(gòu)造只有頭節(jié)點(diǎn)的雙鏈表L/掃描L的數(shù)據(jù)節(jié)點(diǎn)/用q保存其后繼節(jié)點(diǎn)采用頭插法將*p節(jié)點(diǎn)插入/修改其前驅(qū)指針L-next-prior=p;L-next=p;p-prior=L;p=q;/讓p重新指向其后繼節(jié)點(diǎn)編寫(xiě)出判斷帶頭節(jié)點(diǎn)的雙向

8、循環(huán)鏈表L是否對(duì)稱相等的算法。intEqueal(DLinkList*L)intsame=1;DLinkList*p=L-next;/p指向第一個(gè)數(shù)據(jù)節(jié)點(diǎn)DLinkList*q=L-prior;/q指向最后數(shù)據(jù)節(jié)點(diǎn)while(same=1)if(p-data!=q-data)same=0;elseif(p=q)break;/數(shù)據(jù)節(jié)點(diǎn)為奇數(shù)的情況q=q-prior;if(p=q)break;/數(shù)據(jù)節(jié)點(diǎn)為偶數(shù)的情況p=p-next;returnsame;假設(shè)有兩個(gè)有序表LA和LB表示,設(shè)計(jì)一個(gè)算法，將它們合并成一個(gè)有序表LC。要求不破壞原有表LA和LB。voidUnionList(SqList*L

9、A,SqList*LB,SqList*&LC)inti=O,j=O,k=O;/i、j分別為L(zhǎng)A、LB的下標(biāo),k為L(zhǎng)C中元素個(gè)數(shù)LC=(SqList*)malloc(sizeof(SqList);/建立有序順序表LCwhile(ilength&jlength)if(LA-dataidataj)LC-datak=LA-datai;i+;k+;else/LA-dataiLB-datajLC-datak=LB-dataj;j+;k+;while(ivLA-length)/LA尚未掃描完，將其余元素插入LC中LC-datak=LA-datai;i+;k+;while(jlength)/LB尚未掃描完，將

10、其余元素插入LC中LC-datak=LB-dataj;j+;k+;LC-length=k;設(shè)有4個(gè)元素a、b、c、d進(jìn)棧，給出它們所有可能的出棧次序。解：所有可能的出棧次序如下:abcdabdcacbdacdbadcbbacdbadcbcadbcdabdcacbadcbdacdbadcba編寫(xiě)一個(gè)算法利用順序棧判斷一個(gè)字符串是否是對(duì)稱串。所謂對(duì)稱串是指從左向右讀和從右向左讀的序列相同。boolsymmetry(ElemTypestr)inti;ElemTypee;SqStack*st;InitStack(st);/初始化棧for(i=0;stri!=0;i+)/將串所有元素進(jìn)棧Push(st,

11、stri);/元素進(jìn)棧for(i=0;stri!=0;i+)Pop(st,e);/退棧元素eif(stri!=e)/若e與當(dāng)前串元素不同則不是對(duì)稱串DestroyStack(st);/銷(xiāo)毀棧returnfalse;DestroyStack(st);/銷(xiāo)毀棧returntrue;編寫(xiě)一個(gè)算法判斷輸入的表達(dá)式中括號(hào)是否配對(duì)(假設(shè)只含有左、右圓括號(hào))boolMatch(charexp,intn)/初始化棧/初始化棧/掃描exp中所有字符/當(dāng)前字符為左括號(hào),將其進(jìn)棧InitStack(st);while(inext,*q;intfind=0;while(p-next!=NULL&find=0)查找ab

12、子串if(p-data=a&p-next-data=b)找到子串p-data=x;p-next-data=z;替換為xyzq=(LiString*)malloc(sizeof(LiString);q-data=y;q-next=p-next;p-next=q;find=1;elsep=p-next;13.含n個(gè)節(jié)點(diǎn)的三次樹(shù)的最小高度是多少？最大高度是多少？解：設(shè)含n個(gè)節(jié)點(diǎn)的(為完全三次樹(shù)時(shí)高度最小)的三次樹(shù)的最小高度為h，則有：1+3+9+3h-2VnW1+3+9+3h-1(3h-1-1)/2VnW(3h-1)/23h-1V2n+1W3h即：h=log3(2n+1)最大高度為n-2。14.假設(shè)

13、圖G采用鄰接表存儲(chǔ)，設(shè)計(jì)一個(gè)算法，輸出圖G中從頂點(diǎn)u到v的所有簡(jiǎn)單路徑。voidPathAll(ALGraph*G,intu,intv,intpath,intd)d是到當(dāng)前為止已走過(guò)的路徑長(zhǎng)度，調(diào)用時(shí)初值為-1intw，intw，i;ArcNode*p;visitedu=1;d+;pathd=u;if(u=v&d1)printf();路徑長(zhǎng)度增1/將當(dāng)前頂點(diǎn)添加到路徑中輸出一條路徑for(i=0;iadjlistu.firstarc;/p指向u的第一條邊while(p!=NULL)w=p-adjvex;w為u的鄰接頂點(diǎn)if(visitedw=0)/若頂點(diǎn)未標(biāo)記訪問(wèn)，則遞歸訪問(wèn)之PathAll(

14、G,w,v,path,d);p=p-nextarc/找u的下一個(gè)鄰接頂點(diǎn)visitedu=0;/恢復(fù)環(huán)境voidmain()intpathMAXV,u=1,v=4,i,j;MGraphg;ALGraph*G;g.n=5;g.e=6;intAMAXVMAXV=0,1,0,1,0，1,0,1,0,0，0,1,0,1,1，1,0,1,0,1，0,0,1,1,0;for(i=0;ig.n;i+)/建立圖的鄰接矩陣for(j=0;jg.n;j+)g.edgesij=Aij;MatToList(g，G);for(i=0;ig.n;i+)visitedi=0;printf(圖G:n);DispAdj(G);

15、輸出鄰接表printf(從4到4的所有路徑:n,u,v);PathAll(G，u，v，path，-1);printf(n);15.普里姆(Prim)算法如下：#defineINF32767/INF表示voidPrim(MGraphg,intv)intlowcostMAXV;intmin;intclosestMAXV,i,j,k;for(i=0;ig.n;i+)/給lowcost和closest置初值lowcosti=g.edgesvi;closesti=v;for(i=1;ig.n;i+)找出(n-1)個(gè)頂點(diǎn)min=INF;for(j=0;jg.n;j+)在(V-U)中找出離U最近的頂點(diǎn)kif(lowcostj!=0&lowcostjmin)min=lowcostj;k=j;/k記錄最近頂點(diǎn)的編號(hào)printf(邊(d,%d)權(quán)為:dn,closestk,k,min);lowcostk=0;/標(biāo)記k已經(jīng)加入U(xiǎn)for(j=0;jg.n;j+)/修改數(shù)組lowcost和closestif(g.e