《數(shù)據(jù)結(jié)構(gòu)-用C語言描述》課后習題答案資料1

數(shù)據(jù)結(jié)構(gòu)課后習題參考答案第一章緒論TOC\o"1-5"\h\z1.3(1)O(n)(2)O(n)(3)O(n)(4)O(n1/)2(5)執(zhí)行程序段的過程中，x,y值變化如下:循環(huán)次數(shù)xy0(初始)911001921002??93??100??9100100101011001191991292100??20??101??9921??91??98??3010198319197到y(tǒng)=0時，要執(zhí)行10*100次，可記為O(10*y)=O(n)1.52100,(2/3)n,log2n,n1/2,n3/2,(3/2)n,nlog2n,2n,n!,nn第二章線性表(參考答案)在以下習題解答中，假定使用如下類型定義：(1)順序存儲結(jié)構(gòu)：實際上，可以是任意類型表示終端結(jié)點在向量中的位置sequenlist;(2)鏈式存儲結(jié)構(gòu)(單鏈表)(3)鏈式存儲結(jié)構(gòu)(雙鏈表)(4)靜態(tài)鏈表頭指針：指向鏈表的指針。因為對鏈表的所有操均需從頭指針開始，即頭指針具有標識鏈表的作用，所以鏈表的名字往往用頭指針來標識。如：鏈表的頭指針是la,往往簡稱為“鏈表la”。頭結(jié)點：為了鏈表操作統(tǒng)一,在鏈表第一元素結(jié)點（稱為首元結(jié)點,或首結(jié)點）之前增加的一個結(jié)點,該結(jié)點稱為頭結(jié)點,其數(shù)據(jù)域不無實際意義（當然,也可以存儲鏈表長度,這只是副產(chǎn)品）,其指針域指向頭結(jié)點。這樣在插入和刪除中頭結(jié)點不變。開始結(jié)點：即上面所講第一個元素的結(jié)點。只設(shè)尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問鏈表上的任何結(jié)點。2?3向量目前有個元素，且遞增有序，本算法將插入到向量中，并保持向量的遞增有序。查找插入位置向后移動元素插入元素算法結(jié)束2?4以向量作存儲結(jié)構(gòu)，本算法將向量中的個元素循環(huán)右移位，且只用一個輔助空間。計數(shù)，最終應等于記錄開始位置（下標）暫存起點元素值，與向量中元素類型相同保存空位置下標計算下一右移元素的下標右移右移元素數(shù)加計算新右移元素的下標把一輪右移中最后一個元素放到合適位置起點增,若則開始下一輪右移。算法結(jié)束算法二算法思想：先將左面?zhèn)€元素逆置，接著將右面?zhèn)€元素逆置，最后再將這個元素逆以向量作存儲結(jié)構(gòu)，本算法將向量中的個元素循環(huán)右移位，且只用一個輔助空間。ElemTypetemp;左面2個元素逆置{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i右面?zhèn)€元素逆置{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i2全部個元素逆置算/法/結(jié)束2?5帶頭結(jié)點的單鏈表遞增有序，本算法將插入到鏈表中，并保持鏈表的遞增有序。L為工作指針，指向當前元素，為前驅(qū)指針，指向當前元素的前驅(qū)申請空間，不判斷溢出查找插入位置插入元素算法結(jié)束2?6voidinvert(linklist*L)本算法將帶頭結(jié)點的單鏈表逆置。算法思想是先將頭結(jié)點從表上摘下，然后從第一個元素結(jié)點開始，依次前插入以為頭結(jié)點的鏈表中。{linklist*p=L->next,*s;為工作指針，指向當前元素，為的后繼指針頭結(jié)點摘下，指針域置空。算法中頭指針始終不變while(p)保留后繼結(jié)點的指針逆置L->next=p;將指向下個待逆置結(jié)點}}/算/法結(jié)束2?7本算法計算帶頭結(jié)點的單鏈表的長度linklist*p=L->next;為工作指針，指向當前元素，表示鏈表的長度}/算法/結(jié)束(2)intlength1(nodesa[MAXSIZE])本算法計算靜態(tài)鏈表中元素的個數(shù)。{intp=sa[0].next,i=0;為工作指針，指向當前元素，表示元素的個數(shù)，靜態(tài)鏈指針等于時鏈表結(jié)束whi！l=e-1()p{i++;p=sa[p].next;}return(i);}算//法結(jié)束2?8voidunion_invert(linklist*A和是兩個帶頭結(jié)點的遞增有序的單鏈表，本算法將兩表合并成一個帶頭結(jié)點的遞減有序單鏈表，利用原表空間。為工作指針，分別指向表和表的當前元素，為當前逆置//元素的后繼指針,使逆置元素的表避免斷開。/算/法思想是邊合并邊逆置，使遞增有序的單鏈表合并為遞減有序的單鏈表。頭結(jié)點摘下，指針域置空。算法中頭指針始終不變兩表均不空時作將表中元素合并且逆置保留后繼結(jié)點的指針逆置C->next=pa;pa=r;恢時復時待逆置結(jié)點的指針}將表中元素合并且逆置保留后繼結(jié)點的指針逆置pb=r;恢時復待時逆置結(jié)點的指針}以下和語句，只執(zhí)行一個將表中剩余元素逆置保留后繼結(jié)點的指針逆置pa=r;恢時復時待逆置結(jié)點的指針}將表中剩余元素逆置保留后繼結(jié)點的指針逆置pb=r;恢時復時待逆置結(jié)點的指針}釋放表頭結(jié)點}時時算法結(jié)束2?9時時長度大于1的單循環(huán)鏈表，既無頭結(jié)點，也無頭指針，本算法刪除的前驅(qū)結(jié)點inip=>netpre二p為工作指針，指向當前元素，pr為前驅(qū)指針，指向當前元素的前驅(qū)ie(p>net!=)pre=p;p=p>ne土查找S勺前驅(qū)pre->next=s;free(p);//刪除元素}//算法結(jié)束2?10voidone_to_three(linklist*A,*B,*C)是帶頭結(jié)點的的單鏈表，其數(shù)據(jù)元素是字符字母、字符、數(shù)字字符、其他字符。本算法將A表分成三個帶頭結(jié)點的循環(huán)單鏈表A、和，分別含有字母、數(shù)字和其它符號的同一類字符，利用原表空間。{linklist*p=A->next,r;為工作指針，指向A表的當前元素，r為當前元素的后繼指針使表避免斷開。將將算法思想是取出當前元素，根據(jù)是字母、數(shù)字或其它符號，分別插入相應表中。=(init)a(ize￡(申逾空間i不判斷溢出B->next=null;準備將循將環(huán)鏈表的頭結(jié)點=(init)a(ize￡(申逾空間i不判斷溢出C->next=null;準備將循將環(huán)鏈表的頭結(jié)點while(p){r=p->next;將用以將記住后繼結(jié)點if(p->data>=’a’&&p->data<=’z’||p->data>=’A’&&p->data<=’Z’)p>net=A>net;A>net=p將字母字符插入A表elseif(>pd-ata>=’0’&&p->data<=’9’)p>net=>net;>ne=將數(shù)字字符插入表eep>net=>net;>9將其竊符號插入表p=r;將將恢復后繼結(jié)點的指針ie}將算將法結(jié)束2?11voidlocate(dlinklist*L)是帶頭結(jié)點的按訪問頻度遞減的雙向鏈表，本算法先查找數(shù)據(jù)將將查找成功時結(jié)點的訪問頻度域增1，最后將該結(jié)點按頻度遞減插入鏈表中適當位置。{linklist*p=L->next,*q;為工作指針，指向表的當前元素，為p的前驅(qū)，用于查找插入位置。ie(p&&p>data!=)p=p>ne查找值為的結(jié)點。if(!p)return("不存在值為的結(jié)點”)；eep>fre令元素值為的結(jié)點的fre域加1。p>net>prir=p>prir;將p結(jié)點從鏈表上摘下。p->prior->next=p->next;=p>prir;以下查找p結(jié)點的插入位置while(q!=L&&q->freq<p-freq)q=q->prior;p>net=>net;>net>pr^pr締點插入p->prior=q;q->ne；xt=p算將法結(jié)束第三章棧和隊列(參考答案)//從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊列是操作受限的線性結(jié)構(gòu)，其順序存儲結(jié)構(gòu)//和鏈式存儲結(jié)構(gòu)的定義與線性表相同，請參考教材，這里不再重復。3.1123421343214432112432143324113242314342113421432設(shè)入棧序列元素數(shù)為n,23412431則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2)證明：由和pp說明p在p之前出棧，即在k未進棧之前p已出棧，之后k進棧，然后p出棧；由和pp說明p在p之后出棧，即p被p壓在下面，后進先出。由以上兩條，不可能存在i使kppp。也就是說，若有，，順序入棧，不可能有，1，2的出棧序列。voidsympthy(linklist*head,stack*s)〃判斷長為n的字符串是否中心對稱{inti=1;linklist*p=head->next;while(i<=n/2)//前一半字符進棧{push(s,p->data);p=p->next;}if(n%!==0)p=pnext;奇數(shù)個結(jié)點時跳過中心結(jié)點while(p&&p->data==pop(s))p=p->next;if(p二二null)printf(“鏈表中心對稱”)elseprintf(“鏈表不是中心對稱”)}//算法結(jié)束intmatch()//從鍵盤讀入算術(shù)表達式，本算法判斷圓括號是否正確配對(inits;//初始化棧sscanf(“%c”,&ch);while(ch!=’#’)//’#’是表達式輸入結(jié)束符號switch(ch){case’(’:push(s,ch);break;case')’：if(empty(s)){printf("括號不配對")；exit(0);}pop(s);}if(!empty(s))printf("括號不配對”)；elseprintf(“括號配對”)；}//算法結(jié)束typedefstruct//兩棧共享一向量空間{lemypem；棧可用空間0-minttop[2]棧/頂/指針}twostack;intpush(twostack*s,inti,ElemTypex)//兩棧共享向量空間，i是0或，表示兩個棧，x是進棧元素，//本算法是入棧操作{if(abs(stp0stp)==)棧滿rn(0);//else{switch(i){case0：s->v[++(s->top)]=x;break;case1：s->v[--(s->top)]=x;break;default:printf("棧編號輸入錯誤”)；return(0);}return(1);//入棧成功}}/算/法結(jié)束ElemTypepop(twostack*s,inti)兩棧共享向量空間是0或，表示兩個棧，本算法是退棧操作{ElemTypex;if(i0i)return(0編號錯誤else{switch(i)ae0:if(tp0)?？誹rn(0);elsex=s->v[s->top--];break;ae:if(tp)棧空urn(0);elsex=s->v[s->top++];break;default:printf("棧編號輸入錯誤”)；return(0);}return(x);/退/棧成功}}//算法結(jié)束ElemTypetop(twostack*s,inti)兩棧共享向量空間是0或，表示兩個棧，本算法是取棧頂元素操作{ElemTypex;switch(i)ae0:if(tp0)?？誹rn(0);elsex=s->v[s->top];break;ae:if(tp)棧空urn(0);elsex=s->v[s->top];break;default:printf("棧編號輸入錯誤”)；return(0);}return(x);/取/棧頂元素成功}/算/法結(jié)束voidAckerman(intm,intn)e函巍的遞歸算法{if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ackerman(m-1,1);elsereturn(Ackerman(m-1,Ackerman(m,n-1))}//算法結(jié)束linklist*init(linklist*q)是以帶頭結(jié)點的循環(huán)鏈表表示的隊列的尾指針，本算法將隊列置空(linlit)all(ief(lin請空間t)不判斷空間溢出q->next=q;return(q);}//算法結(jié)束linklist*enqueue(linkl，isEtle*mqTypex)是以帶頭結(jié)點的循環(huán)鏈表表示的隊列的尾指針，本算法將元素入隊(linlit)all(ief(lSn請空間t)不判斷空間溢出netnet將元素結(jié)點入隊列q->next=s;q=s;修/改/隊尾指針算/法/結(jié)束是以帶頭結(jié)點的循環(huán)鏈表表示的隊列的尾指針，這是出隊算法判斷隊列是否為空指向出隊元素若隊列中只一個元素，置空隊列修改隊頭元素指針釋放出隊結(jié)點//算//法結(jié)束。算法并未返回出隊元素循環(huán)隊列占個存儲單元和為隊頭元素和隊尾元素的指針約定指向隊頭元素的前一位置，指向隊尾元素為循環(huán)隊列，本算法計算其長度算/法/結(jié)束循環(huán)隊列占個存儲單元指向隊尾元素為元素個數(shù)為循環(huán)隊列，本算法判斷隊列是否為空/算/法結(jié)束是如上定義的循環(huán)隊列，本算法將元素入隊隊滿計算插入元素位置將元素入隊列修;改隊列長度算//法結(jié)束是以如上定義的循環(huán)隊列，本算法是出隊算法，且返回出隊元素隊空出隊元素位置修;改隊列長度返回隊頭元素}/算/法結(jié)束第四章串（參考答案在以下習題解答中，假定使用如下類型定義：表示終端結(jié)點在向量中的位置intindex(strings,t)〃s,t是字符串，本算法求子串t在主串s中的第一次出現(xiàn)，若s串中包含t串，返回其〃第一個字符在s中的位置，否則返回0{m=length(s);n=length(t);i=1;while(i<=m-n+1)if(strcmp(substr(s,i,n),t)==0)break;elsei++;if(i<=m-n+1)return(i);//模式匹配成功elsereturn(0);//s串中無子串t}//算法index結(jié)束設(shè)A=""，B=“mule“，C="old"，D="my”則U：（a）（a）strcat(A,B)=”mule”（b）（b）strcat(B,A)=”mule”（c）（c）strcat(strcat(D,C),B)=”myoldmule”（d）（d）substr(B,3,2)=”le”（e）（e）substr(C,1,0)=””（f）（f）strlen(A)=0（g）（g）strlen(D)=2（h）（h）index(B,D)=0（i）（i）index(C,”d”)=3（j）（j）insert(D,2,C)=”moldy”（k）（k）insert(B,1,A)=”mule”（l）（l）delete(B,2,2)=”me”（m）（m）delete(B,2,0)=”mule”（n）（n）replace(C,2,2,”k”)=”ok”4.4將S=“（xyz）*”轉(zhuǎn)為T="(x+z)*y”S=concat(S,substr(S,3,1))//”(xyz)*y”S=replace(S,3,1,”+”)//”(x+z)*y”和是用帶頭結(jié)點的結(jié)點大小為的單鏈表表示的串，本算法查找中第一個不在中出現(xiàn)的字符。算法思想是先從中取出一個字符，到中去查找，如找到，則在中取下一字符，重復以上過程；若沒找到，則該字符為所求為工作指針，控制循環(huán)取中的字符和中字符比較找到中沒有的字符上一字符在中存在，取中下一字符。再從的第一個字符開始比較t)中字符在中均存在的算法結(jié)束intstrcmp(seqstring*S,seqstring*T)和是指向兩個順序串的指針，本算法比較兩個串的大小，若串大于串，返回1若串等于串，返回0；否則返回{inti=0;while>(chs[i-]!=’\0’&&t->ch[i]!=’\0’)if(s->ch[i]>t->ch[i])return(1);elseif(s->ch[i]<t->ch[i])return(-1);i比較下一字符if(>sch-[i]!=’\0’&&t->ch[i]==0)return(1);elseif>ch([is]=-=’\0’&&t->ch[i]!=0)return(-1);elsereturn(0);}的的算法結(jié)束4.7linkstring*invert(linkstring*S,linkstring*T)和是用帶頭結(jié)點的結(jié)點大小為的單鏈表表示的串，是主串，是模式串。本算法是先模式匹配，查找在中的第一次出現(xiàn)。如模式匹配成功，則將中的子串(串)逆置。{linkstring*pre,*sp,*tp;=是前驅(qū)指針，指向中與匹配時，中的前驅(qū)=>tt=和=分別是和串上的工作指針while(sp&&tp)i>t==t>相等時后移指針{sp=sp->next;tp=tp->next;}else失的配的時主串回溯到下一個字符，子串再以第一個字符開始{pre=pre->next;sp=pre->next;tp=T->next;}it!=)t匹配失敗，沒有逆置以下是串逆置t=>是逆置的工作指針，現(xiàn)在指向待逆置的第一個字符>t=將中與串匹配時的前驅(qū)指向匹配后的后繼while(tp!=sp){r=tp->next;tp->next=pre->next;pre->next=tp;tp=r}的的算法結(jié)束第五章多維數(shù)組和廣義表(參考答案)5.1A[2][3][2][3]A0000,A0001,A0002A0010,A0011,A0012A0100,A0101,A0102A0110,A0111,A0112A0200,A0201,A0202A0210,A0211,A0212將第一維的0變?yōu)?后，可列出另外18個元素。以行序為主(即行優(yōu)先)時，先改變右邊的下標，從右到左進行。5.2設(shè)各維上下號為c1?d1,c2?d2,c3?d3，每個元素占l個單元。LOC(aijk)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l推廣到n維數(shù)組??！(下界和上界)為(ci,di),其中1<=i<=n.則：其數(shù)據(jù)元素的存儲位置為：LOC(加…jn)=LOC3c2…c/+[(d2-C2+1)…(dnQ+1)。1-%)+巴$+1)…(dnG+1)n(j2-C2)+?+(dn-Cn+1)(jn-1-Cn-1)+(jn-Cn)]*l=LOC(ac1c2c3)+工。i=1n其中an(1()若從c開始，c數(shù)組下標從0開始，各維長度為bi(1<=i<=n)則：LOC(523)=LOC(a00…0)+(b2*b3*…*bn*L+b3*…*bn*+^2?+bn*第+Q*1n=L0c(a00…0)+￡。其中：a，abi*a，是行列的二維數(shù)組本算法求所有馬鞍點是一維數(shù)組存放一行中可能的馬鞍點的列值記相等值個數(shù)是一維數(shù)組存放某列可能馬鞍點的行值記相等值個數(shù)or(i=0;i<m;i++)最小值初始化數(shù)組記最小值的列號，記最小值的個數(shù)找每一行中的最小值重新確定最小值有相等的最小值第行有個相等的最小值是否是馬鞍點while(kk<m&&max>=a[i][

“馬鞍點”最壞時間復雜度為最壞時所有元素相同，都是馬鞍點解法若矩陣中元素值互不相同則用一維數(shù)組記下各行最小值，再用一維數(shù)組記下各列最大值,相等者為馬鞍點。最小值初始化

找每一行中的最小值重新確定最小值最大值初始化找每一列中的最大值重新確定最大值“馬鞍點

“馬鞍點

時間復雜度

解法3:設(shè)定兩個數(shù)組：第列的最大值為記各列的最大值所在行號記各行的最小值所在列號第行的最小值是是行列的二維數(shù)組本算法求所有馬鞍點重新確定第列最大值的行號

重新確定第行最小值的列號是］否;是馬鞍點/“馬鞍點時間復雜度為（1）三元組表（行號0—5，列號0—5）S=（（0，0，15），（0，3，22），（0，5，-15），（1，1，11），（1，2，3），（2，3，-6），（4，0，91），（5，2，28））算法分析：兩矩陣A和B相加的結(jié)果是一矩陣C,其元素Cij有三種情況；(1)CjAij(Bij=0)；(2)Cij=Bij(Aij=0)；(3)Cij=Aij+Bij。在(3)種情況下，要看結(jié)果是否為0，c矩陣只有非零元素。1J1J1J1JVoidmatrixaddition(crosslist*A,*B)〃稀疏矩陣A和B用十字鏈表存儲結(jié)構(gòu)，本算法將稀疏矩陣B加到矩陣A上{ca=A->next;cb=B->next;while(ca!=A&&cb!=B)〃設(shè)pa和pb為矩陣A和B想加時的工作指針{pa=ca->right;pb=cb->right;}if(pa==ca)ca=ca->next;//A表在該行無非0元素；elseif(pb==cb)cb=cb->next//B表在該行無非0元素；elseif(pb->col<pa->col)//B的非0元素插入A中；{j=pb->col;pt=chb[j];pre=pt//取到表頭指針；while(pt->down_col<pb->col){pre=pt;pt=pt->down;}pre->down=pt->down;//該結(jié)點從B表相應列摘下i=pb->right;pt=chb[i];pre=pt;〃WB表行表頭指針while(pt->right->row<pb->row{pre=pt;pt=pt->right;}pre->right=pt->riht;//該結(jié)點從B表相應行鏈表中摘下。Pbt=pb;pb=pb->right;//B表移至下一結(jié)點〃以下是將pbt插入A表的相應列鏈表中j=pbt->col;pt=cha[j];pre=pt;while(pt->down!=cha[j]&&pt->down->row<ptb->row){pre=pt;pt=pt->down}pre->down=pbt;pbt->down=pt;〃以下是將pbt插入A表相應行鏈表中i=pbt->right;pt=cha[i];pre=pt;while(pt->right!=cha[i]&&pt->right-col<ptb->col){pre=pt;pt=pt->right;}pre->right=ptb;ptb->right=pt;}//endof“if(pb->col<pa->col)elseif(pa->col=pb->col)//處理兩表中行列相同的非0元素{v=pa->data+pb->data;if(v!=0){pa->data+=pb->data;pa=pa->right;將pb從行鏈表中刪除；pb=pb->right;}else{#pa,pb從鏈表中刪除;然后pa=pa->right;pb=pb->right;}(1)head((p,h,w))=ptail((b,k,p,h))=(k,p,h)head(((a,b),(c,d)))=(a,b)tail(((a,b),(c,d)))=((c,d))head(tail(((a,b),(c,d)))=(c,d)tail(head(((a,b),(c,d))))=(b)5.8(1)(2)5.9(1)BAClbII』44lbII』44口a口第6章樹和二叉樹（參考答案）設(shè)樹的結(jié)點數(shù)是，則設(shè)樹的分支數(shù)為，有由（1）和（2）有：為層數(shù)其右兄弟的編號6.5（1）順序存儲結(jié)構(gòu)1234567891011121314ABCD#EF#G####H注：#為空結(jié)點）前序ABDGCEFH）中序DGBAECHF）后序GDBEHFCA）空二叉樹或任何結(jié)點均無左子樹的非空二叉樹）空二叉樹或任何結(jié)點均無右子樹的非空二叉樹）空二叉樹或只有根結(jié)點的二叉樹是以二叉鏈表為存儲結(jié)構(gòu)的二叉樹，本算法求二叉樹的高度局部變量，分別表示二叉樹左、右子樹的高度左右子樹高度的大者加（根）}算/法/結(jié)束preorder（cbt[],intn,inti）;是以完全二叉樹形式存儲的個結(jié)點的二叉樹，是數(shù)

組下標，初始調(diào)用時為1。本算法以非遞歸形式前序遍歷該二叉樹是棧，棧中元素是二叉樹結(jié)點在中的序是棧頂指針，?？諘r“輸入錯誤”(0i)；“輸入錯誤”(0i)；訪問根結(jié)點若右子樹非空，其編號進棧先序訪問左子樹訪問根結(jié)點若右子樹非空，其編號進棧先序訪問左子樹退棧，先序訪問右子樹退棧，先序訪問右子樹//算法結(jié)束/以下是非完全二叉樹順序存儲時的遞歸遍歷算法，“虛結(jié)點”用‘*’表示是以完全二叉樹形式存儲的一維數(shù)組，是數(shù)組元素個數(shù)。是數(shù)組下標，初始調(diào)用時為1。，，//算法結(jié)束/以下是非完全二叉樹順序存儲時的遞歸遍歷算法，“虛結(jié)點”用‘*’表示是以完全二叉樹形式存儲的一維數(shù)組，是數(shù)組元素個數(shù)。是數(shù)組下標，初始調(diào)用時為1。，，/算法/結(jié)束和是兩棵二叉樹，本算法判斷和是否等價和都是空二叉樹則等價和只有一棵為空，另一棵非空，則不等價和均非空，且根結(jié)點值相等，則比較其左、右子樹同為空二叉樹只有一棵為空根結(jié)點值不等lsereturn(equal(T1->lchild,T/判左右子樹等價//算法結(jié)束本算法按層次遍歷二叉樹if(ht!=null)處始化隊列，隊列元素為二叉樹結(jié)點的指針根結(jié)點指針入隊列訪問結(jié)點若左子女非空/，/則左子女入隊列if(p->rchi若右子女非/空/，則右子女入隊列}算/法結(jié)束前序非遞歸遍歷是指針數(shù)組，數(shù)組中元素為二叉樹節(jié)點的指針算/法結(jié)束中序非遞歸遍歷算/法結(jié)束后序非遞歸遍歷}算/法/結(jié)束13tree*dissect(bitree**t,Ele二叉樹至多有一個結(jié)點的數(shù)據(jù)域為，本算法拆去以為根的子樹拆開后的第一棵樹用表示，成功拆開后返回第二棵二叉樹根結(jié)點數(shù)據(jù)域為

在左子樹中查找并拆開若在左子樹/中/未找到，就到右子樹中查找并拆開空二叉樹算/法結(jié)束設(shè)二叉樹中，值為的結(jié)點至多一個，本算法打印的所有祖先算法思想是，借助后序非遞歸遍歷，用棧裝遍歷過程的結(jié)點，當查到值為的結(jié)點時，棧中元素都是的祖先沿左分支向下輸出，設(shè)元素為字符退出右子樹已訪問的結(jié)點置訪問標志1訪問右子樹沒有值為的結(jié)點/算/法結(jié)束6.15中序序歹BDCEAFHG后序序歹DECBHGFA6.15nullnull前序序列ABCDEFGH6.16后序線索樹:只有空指針處才能加線索。線索鏈表:查找前序線索二叉樹上給定結(jié)點的前序后繼；左標記為時，若的右子樹非空，的右子樹的根為的后繼；若右子樹為空，指向后繼左標記為時，的左子女為的后繼}左算左法結(jié)束6.18bitree*search（b：tree*p）//在后序線索二叉樹中查找給定結(jié)點的后序前驅(qū)的算法

{if(p->rtag==0)return(p->rchild);//p有右子女時，其右子女p->rchild是p的后序前驅(qū)elsereturn(p->lchild);else//p的左標記為0,左子女p->lchild是后序前驅(qū)，否則，線索p->lchild指向p的后序前驅(qū)}6.19前序序列：ABCDEFGHIJKLMPQRNO序前驅(qū)}6.19前序序列：ABCDEFGHIJKLMPQRNO后序序列：BDEFCAIJKHGQRPMNOL6.216.227,19,2,6,32,3,21,10其對應字母分別為a,b,c,e,f,g,h。哈夫曼編碼：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章圖(參考答案)7．1(1)鄰接矩陣中非零元素的個數(shù)的一半為無向圖的邊數(shù)；A[i][j]==0為頂點，I和j無邊，否則j和j有邊相通;(3)任一頂點I的度是第I行非0元素的個數(shù)。7．2(1)任一頂點間均有通路，故是強連通；(2)簡單路徑V4V3V1V2;TOC\o"1-5"\h\z\/。1818888(88/逆鄰接表7．3(1)鄰接表(2)從頂點4開始的DFS序列：V5,V3,V4,V6,V2,V1(3)從頂點4開始的BFS序列：V4,V5,V3,V6,V1,V27.4(1)①adjlisttpg;vtxptri,j;〃全程變量voiddfs(vtxptrx)從頂點開始深度優(yōu)先遍歷圖。在遍歷中若發(fā)現(xiàn)頂點，則說明頂點和間有路徑。置訪問標記if(y==j)有通路，退出找的第一鄰接點(!visiift)eddf[sk(]k);下一鄰接點}}voidconnect_DFS(adjlisttpg)基于圖的深度優(yōu)先遍歷策略，本算法判斷一鄰接表為存儲結(jié)構(gòu)的圖種，是否存在頂點i到頂點的路徑。設(shè){visited[1..n]=0;found=0;scanf(&i,&j);dfs(i);if(found)printf("頂點”,i,“和頂點”,j,“有路徑”)；elseprintf("頂點”,i,”和頂點”,j,"無路徑”)；}//

(2寬)度優(yōu)先遍歷全程變量，調(diào)用函數(shù)與(1)相同，下面僅寫寬度優(yōu)先遍歷部分。{found=1;exit(0);}//有通路，退出else{p=g[x].firstarc;//第一鄰接點while(p!=null){k=p->adjvex;if(!Visted[k])enqueue(q,k);p=p->nextarc}}//if(y==j)}//while(!empty(q))7．5。假定該有向圖以鄰接表存儲，各頂點的鄰接點按增序排歹V1,V3,V6,V7,V4,V2,V5,V8V1,V3,V4,V6,V7,V2,V5,V8DFS序歹1」：BFS序歹1」：DFS森林V2V5BFSV1,V3,V6,V7,V4,V2,V5,V8V1,V3,V4,V6,V7,V2,V5,V8DFS序歹1」：BFS序歹1」：DFS森林V2V5BFS森林V6V7V2V6V8V5V77．6簡單回路指起點和終點相同的簡單路徑。算法基本思想是利用圖的遍歷，以頂點VK開始，若遍歷中再通到VK,則存在簡單回路，否則不存在簡單回路。Adjlisttpg;visited[1..n]=0;Intfound=0;//全程變量Intdfs(btxptrx)〃從k頂點深度優(yōu)先遍歷圖g,看是否存在k的簡單回路{visited[x]=1;p=g[x].firstarc;while(p!=null){w=p->adjvex;if(w==k){found=1;exit(0);}//有簡單回路，退出if(!visited[k])dfs(w);p=p->nextarc;}//while(p!=null)}//dfs7.7(1)7.7(1)PRIM算法的最小生成樹(2)KRUSKAL算法的最小生成樹(權(quán)值相同的邊選取無順序)7.8所選頂點已選定點的集合尚未被選頂點的集合DIST[2][3][4][5][6]初態(tài){1}{2,3,4,5,6}20158883{1,3}{2,4,5,6}19882{1,3,2}{4,5,6}86{1,3,2,6}{4,5}29294{1,3,2,6,4}{5}295{1,3,2,6,4,5}{}注：選定點4和5時無優(yōu)先順序，二者最短路徑均為29

7．9Z08%A0=308V7．9Z08%A0=308V2”1238:1到3沒有直接通路Z088A1=308I52cj同加入頂點后無變化A2=X用鄰接表存儲結(jié)構(gòu)，鄰接點逆序即編號大的排在前面。入度為0頂點用棧結(jié)構(gòu)存儲，初始時從頂點1到頂點N掃描，入度為0的頂點進棧，得V5在棧頂。7．11voidtoposort_dfs（graphg；vtptrv）〃從頂點v開始，利用深度優(yōu)先遍歷對圖g進行拓撲排序?！ɑ舅枷胧抢脳存放頂點，首先出棧的頂點是出度為0的頂點，是拓撲序列中最后個頂//點。若出棧元素個數(shù)等于頂點數(shù)，則拓撲排序成功，輸出的是逆拓撲排序序列。{visited[1..n]=0;top=0;num=0;//初始化；top為棧頂指針，num記出棧元素數(shù)s[++top]=v;//頂點入棧while(top!=0){w=firstadj(g,v);//求頂點v的第一鄰接點while(w！=0)//w!=0的含義是w存在{if(!visited[w])s[++top]=w;w=nextadj(g,v,w);//求下一個鄰接點}if(top!=0){v=s[top--];num++;printf(v);}//輸出頂點}printf(“\n”);if(num<n)printf(“從”,“v",”頂點開始拓撲排序不能順利完成”)；elseprints"拓撲排序成功，輸出的是一個逆拓撲序列.\n")；}7.12a1=5a1=5V1'Qa3=6頂點VeVl活動ell-eV100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220關(guān)鍵路徑V1->V3->V4->V7->V9->V10長22關(guān)鍵活動a3,a4,a7,a11,a14頂點VeVl活動ell-eV100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220關(guān)鍵路徑V1->V3->V4->V7->V9->V10長22關(guān)鍵活動a3,a4,a7,a11,a14第八章排序(參考答案)本章所用數(shù)據(jù)結(jié)構(gòu)待排序記錄的個數(shù)為結(jié)構(gòu)體數(shù)組8.2穩(wěn)定排序有：直接插入排序、起泡排序、歸并排序、基數(shù)排序不穩(wěn)定排序有：希爾排序、直接選擇排序、堆排序希爾排序例：49，38,_49，90，70，25直接選擇排序例：2,萬，1堆排序例：1,2，2對靜態(tài)鏈表進行表插入排序，并調(diào)整結(jié)果，使表物理上排序機器最大整數(shù)為結(jié)構(gòu)體數(shù)組頭結(jié)點和第一個記錄組成循環(huán)鏈表從第2個/元/素開始，依次插入有序鏈表中(i<=n)指向當前最小元素，是的前驅(qū)查找插入位置將第個元素鏈入靜態(tài)鏈表的插入以下是重排靜態(tài)鏈表，使之物理有序[■i算/法/結(jié)束對進行雙向冒泡排序。即相鄰兩遍向兩個相反方向起泡設(shè)標記hile(exchange)假定本趟無交換向前起泡，一趟有一最小冒出[有交換向后起泡，一趟有一最大沉底[有交換}/算法/結(jié)束8.5(1)在n=7時，最好情況下進行10次比較。6次比較完成第一趟快速排序，將序列分成相等程度的序列(各3個元素)，再各進行2次比較，完成全部排序。(2)最好的初始排列：4，1，3，2，6，5，7對進行快速排序的非遞歸算法函數(shù)聲明算/法/結(jié)束一/次/劃分算法結(jié)束dQuickSort(rectyper[n+對進行快速排序的非遞歸算法對算法的改進pedsetfruct{intlow,high;}nodees；[n+1]top;函數(shù)聲明=1;s[top].low=1;s[top].hs[top].low;tt=s[top].highile(flag||top>0){k=quickpass(r,ss,tt);一趟排序后分割成左右兩部分左部子序列長度大于右部，左部進棧{top++;s[top].lo右部短的直接處理右部處理完，需退棧}右部子序列長度大于左部，右部進棧{top=top+1;s[to左部短的直接處理左部處理完，需退棧算/法/結(jié)束用“三者取中法”對8.進6行改進三者/取/中：最佳次比較三者/取/中：最佳次比較3次移動；最差3次比較10次移動)e}一/次/劃分算法結(jié)束viodsearchjrec(rectyper[]，intj)〃在無序記錄r[n]中，找到第j(0<=j<n)個記錄。算法利用快速排序思想，找到第一〃軸元素的位置i，若i=j則查找結(jié)束。否則根據(jù)j<i或j>i在0?i、1或i+1?n+1之間查〃找，直到/i=j為止。{intquichpass(rectyper[],int,int)//函數(shù)聲明i=quichpass(r,0,n-1);//查找樞軸位置whilehile(i!=j)if(j<i)i=quichpass(r,0.i-1);elsei=quichpass(r,i+1.n-1);}//searchjrec算法結(jié)束viodrearrange(rectyper[],intn)〃本算法重排具有n個元素的數(shù)r，使取負值的關(guān)鍵字放到取非負值的關(guān)鍵字之前。{inti=0,j=n-1;rp=r[0];while(i<j){while(i<j&&r[j].key>=0)j--;if(i<j)r[i++]=r[j];//取負值關(guān)鍵字記錄放到左面while(i<j&&r[i].key<0)i++;if(i<j)r[j--]=r[i]//取非負值關(guān)鍵字記錄放到右面}//while(i<j)進行整理，使關(guān)鍵字為負值的記錄排在非負值的記錄之前將關(guān)鍵字取負值的記錄放到前面將關(guān)鍵字取非負值的記錄放到后面/算/法結(jié)束/本算法并未判斷軸樞的關(guān)鍵字的正負，在排序中并未和軸樞/記錄比較，而是按正負區(qū)分，提高了效率是單鏈表的頭指針，本算法對其進行直接選擇排序。設(shè)指向無序區(qū)第一個記錄（開始是鏈表的第一個記錄），用指向一趟排序中的最小記錄，為簡便起見，將和所指結(jié)點的數(shù)據(jù)交換。{p=head->next;剩最后一個元素時，排序結(jié)束{q=p;設(shè)當前結(jié)點為最/小/指向待比較結(jié)點用指向新的最小if（q!=p）{x=q->data;鏈表指針后移，指向下一個最小值結(jié)點}}/算/法結(jié)束8.11按極小化堆取調(diào)整（若已是極大化堆則維持不變）（1）

（2）（4），待排序元素在向量中，從素調(diào)整成堆。1到（2）（4），待排序元素在向量中，從素調(diào)整成堆。1到已是堆，現(xiàn)將第個元素加入，本算法這個元用［暫存第個元素，為其關(guān)鍵字設(shè)表示第個元素的下標，是其雙親的下標，本算法將子女與雙親比較，若符合堆的定義，則排序結(jié)束；否則將雙親和子女交換。之后，雙親的下標為新的子女，再與新的雙親比較，直至根結(jié)點（無雙親）已符合堆的定義，排序結(jié)束僅將雙親移至子女將暫存記錄（原第個記錄）放入合適位置算待法結(jié)束利用上述排序思想，從空堆開始，一個一個添加元素的建堆算法如下：向量的第到第個元素為待排序元素，本算法將這個元素建成堆。}/算/法結(jié)束8.13voidsort(rectyper[],intn)〃對具有n個元素的數(shù)組進排序。算法思想是先對數(shù)組掃描一遍，形成若干最大有序子//列，再兩兩歸并，最后完成排序。各子序列的長度(上界和下界)存儲在循環(huán)隊列中，//隊頭指針指向隊頭元素的前一位置，隊尾指針指向隊尾元素。#definem100//子隊列長度{intq[m+1];i=1;front=0;rear=0;while(i<=n-1)//該循環(huán)求出rear個子序列{if(r[i+1].key>=r[i].key)i++;q[++rear]=i;//一個子序列上界I++;//I指向下一子序列下界}if(q[rear]<n)q[++rear]=n;//最后一個子序列下界〃以下為兩兩歸并，當最后只剩下一個有序子序列(即lrear-front=1l)時，合并結(jié)束。while((front+1)%m!=rear){newrear=rear;while((front+1)%m!=rear)//從r合并到ri中合并{low=q[front]+1;//取兩個子序列界mid=q[++front%m];if(front+1%m!=rear)high=q[++front%m];elsehigh=mid;merge(r,r1,low,mid,high);newrear=(newrear+1)%m;q[newrear]=high;//新子序列上界}q[front]=0;rear=newrear;//下一輪歸并初始化while((front+1)%m!=rear)〃從n拷入r中{low=q[front]+1;mid=q[++front%m];if(front+1%m!=rear)high=q[++front%m]elsehigh=mid;merge(r1,r,low,mid,high);newrear=++rear%m;q[newrear]=high;}q[front]=0;rear=newrear;//下一輪歸并從第一個元素開始}//最外層的while((front+1)%m!=rear)voidmerge(rectypea[],a1[],intl,m,h)〃設(shè)a數(shù)組中a[l…..m]和a1[m+1…..h]有序，本算法使L..h有序，并拷貝到al中{i=l;j=m+1;k=l-1;while(i<=m&&j<=h)ifa[i].key<=a[j].keya1[++k]=a[i++]elsea1[++k]=a[j++]while(i<=m)a1[++k]=a[i++];while(j<=h)a1[++k]=a[j++];}.14voidCountSort(rectype對進行計數(shù)排序intc[n]={0};數(shù)組初始化，元素值指其在中的位置。如則意味著應在的第位置上。一趟掃描比較選出大小，給數(shù)組賦值若)則正好是第個元素否則，需要調(diào)整{k=c[i];和交換將存入已是第個記錄//while(c[i]!=i)8.15#defineD10//假設(shè)每個關(guān)鍵字長度為10typedefstruct{charkey[D];//關(guān)鍵字用字符數(shù)組表示anytype:otheritem;//元素的其他信息intnext;//指針域}rcdnode;rcdnoder[n];〃為n個英文單詞為關(guān)鍵字的記錄排序intf[27],e[27];intdistribute(inti;intp)〃靜態(tài)鏈表r中的記錄按key[i+1],,key[D]有序，p指向鏈表中第一記錄。本算法〃第I位關(guān)鍵字key[i]建立子表，同一子表中的key[i]值相同。項和e[i]分別指向各子表〃中第一個記錄和最后一個記錄。0<=j<=27,key[i]為空格時，j=0；而key[i]為字母時，j=〃該字母的ASCII碼-64。f[i]=0表示第j個子表為空{(diào)for(j=0;j<=27;j++)f[j]=0;//子表初始化為空表while(p!=0)//p=0表示鏈表到尾{if(r[p].key[i]==’’)j=0;elsej=r[p].key[i]-64;if(f[j]==0)f[j]=p;elsef[e[j]].next=p;e[j]=p;//將p所指結(jié)點插入第j個子表}p=r[p].next;//p指向下一個元素}//forintcollet(inti)//本算法按key[i]自小到大將f[j]不等于0所指各子表鏈成一個鏈表，e用為相應子表的尾//指針，，函數(shù)返回鏈接后鏈表頭指針。{j=0;while(f[j]==0)j++;//找第一個非空子表p=f[j]；t=e[j]；//p為鏈表頭指針while(j<=27){j++;while(j<=27&&f[j]==0)j++;//找下一個非空子表if(f[j]!=0){r[t].next=f[j];t=e[j]}//鏈接兩個非空子表}r[t].next=0;//置鏈表尾return(p);}//collectintradixwordsort()//n個英文單詞為關(guān)鍵字的元素存放在靜態(tài)鏈表的數(shù)據(jù)域中。本算法按基數(shù)排序思想對這些//英文字母進行排序。排序后按關(guān)鍵字自小到大升序相鏈，算法返回指向第一個記錄的下標//值。{for(i=0;i<n-1;i++)r[i].next=i+1;//形成初始鏈表r[n-1].next=0;//0表示鏈表尾p=0;for(i=d;i>0;i--){p=distribute(i,p);p=collect(i);}return(p)}見8.3s=Togkm「//s為歸并趟數(shù)，m為順串個數(shù)，k為歸并路數(shù)因為m=100和s=3所以k>=5,故至少取5路歸并即可第九章