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

數(shù)據(jù)結(jié)構(gòu)課后習(xí)題參考答案第一章緒論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時(shí)，要執(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第二章線性表(參考答案)在以下習(xí)題解答中，假定使用如下類型定義：(1)順序存儲(chǔ)結(jié)構(gòu)：實(shí)際上，可以是任意類型表示終端結(jié)點(diǎn)在向量中的位置sequenlist;(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(單鏈表)(3)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(雙鏈表)(4)靜態(tài)鏈表頭指針：指向鏈表的指針。因?yàn)閷︽湵淼乃胁倬鑿念^指針開始，即頭指針具有標(biāo)識(shí)鏈表的作用，所以鏈表的名字往往用頭指針來標(biāo)識(shí)。如：鏈表的頭指針是la,往往簡稱為“鏈表la”。頭結(jié)點(diǎn)：為了鏈表操作統(tǒng)一,在鏈表第一元素結(jié)點(diǎn)（稱為首元結(jié)點(diǎn),或首結(jié)點(diǎn)）之前增加的一個(gè)結(jié)點(diǎn),該結(jié)點(diǎn)稱為頭結(jié)點(diǎn),其數(shù)據(jù)域不無實(shí)際意義（當(dāng)然,也可以存儲(chǔ)鏈表長度,這只是副產(chǎn)品）,其指針域指向頭結(jié)點(diǎn)。這樣在插入和刪除中頭結(jié)點(diǎn)不變。開始結(jié)點(diǎn)：即上面所講第一個(gè)元素的結(jié)點(diǎn)。只設(shè)尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問鏈表上的任何結(jié)點(diǎn)。2?3向量目前有個(gè)元素，且遞增有序，本算法將插入到向量中，并保持向量的遞增有序。查找插入位置向后移動(dòng)元素插入元素算法結(jié)束2?4以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的個(gè)元素循環(huán)右移位，且只用一個(gè)輔助空間。計(jì)數(shù)，最終應(yīng)等于記錄開始位置（下標(biāo)）暫存起點(diǎn)元素值，與向量中元素類型相同保存空位置下標(biāo)計(jì)算下一右移元素的下標(biāo)右移右移元素?cái)?shù)加計(jì)算新右移元素的下標(biāo)把一輪右移中最后一個(gè)元素放到合適位置起點(diǎn)增,若則開始下一輪右移。算法結(jié)束算法二算法思想：先將左面?zhèn)€元素逆置，接著將右面?zhèn)€元素逆置，最后再將這個(gè)元素逆以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的個(gè)元素循環(huán)右移位，且只用一個(gè)輔助空間。ElemTypetemp;左面2個(gè)元素逆置{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全部個(gè)元素逆置算/法/結(jié)束2?5帶頭結(jié)點(diǎn)的單鏈表遞增有序，本算法將插入到鏈表中，并保持鏈表的遞增有序。L為工作指針，指向當(dāng)前元素，為前驅(qū)指針，指向當(dāng)前元素的前驅(qū)申請空間，不判斷溢出查找插入位置插入元素算法結(jié)束2?6voidinvert(linklist*L)本算法將帶頭結(jié)點(diǎn)的單鏈表逆置。算法思想是先將頭結(jié)點(diǎn)從表上摘下，然后從第一個(gè)元素結(jié)點(diǎn)開始，依次前插入以為頭結(jié)點(diǎn)的鏈表中。{linklist*p=L->next,*s;為工作指針，指向當(dāng)前元素，為的后繼指針頭結(jié)點(diǎn)摘下，指針域置空。算法中頭指針始終不變while(p)保留后繼結(jié)點(diǎn)的指針逆置L->next=p;將指向下個(gè)待逆置結(jié)點(diǎn)}}/算/法結(jié)束2?7本算法計(jì)算帶頭結(jié)點(diǎn)的單鏈表的長度linklist*p=L->next;為工作指針，指向當(dāng)前元素，表示鏈表的長度}/算法/結(jié)束(2)intlength1(nodesa[MAXSIZE])本算法計(jì)算靜態(tài)鏈表中元素的個(gè)數(shù)。{intp=sa[0].next,i=0;為工作指針，指向當(dāng)前元素，表示元素的個(gè)數(shù)，靜態(tài)鏈指針等于時(shí)鏈表結(jié)束whi！l=e-1()p{i++;p=sa[p].next;}return(i);}算//法結(jié)束2?8voidunion_invert(linklist*A和是兩個(gè)帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法將兩表合并成一個(gè)帶頭結(jié)點(diǎn)的遞減有序單鏈表，利用原表空間。為工作指針，分別指向表和表的當(dāng)前元素，為當(dāng)前逆置//元素的后繼指針,使逆置元素的表避免斷開。/算/法思想是邊合并邊逆置，使遞增有序的單鏈表合并為遞減有序的單鏈表。頭結(jié)點(diǎn)摘下，指針域置空。算法中頭指針始終不變兩表均不空時(shí)作將表中元素合并且逆置保留后繼結(jié)點(diǎn)的指針逆置C->next=pa;pa=r;恢時(shí)復(fù)時(shí)待逆置結(jié)點(diǎn)的指針}將表中元素合并且逆置保留后繼結(jié)點(diǎn)的指針逆置pb=r;恢時(shí)復(fù)待時(shí)逆置結(jié)點(diǎn)的指針}以下和語句，只執(zhí)行一個(gè)將表中剩余元素逆置保留后繼結(jié)點(diǎn)的指針逆置pa=r;恢時(shí)復(fù)時(shí)待逆置結(jié)點(diǎn)的指針}將表中剩余元素逆置保留后繼結(jié)點(diǎn)的指針逆置pb=r;恢時(shí)復(fù)時(shí)待逆置結(jié)點(diǎn)的指針}釋放表頭結(jié)點(diǎn)}時(shí)時(shí)算法結(jié)束2?9時(shí)時(shí)長度大于1的單循環(huán)鏈表，既無頭結(jié)點(diǎn)，也無頭指針，本算法刪除的前驅(qū)結(jié)點(diǎn)inip=>netpre二p為工作指針，指向當(dāng)前元素，pr為前驅(qū)指針，指向當(dāng)前元素的前驅(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é)點(diǎn)的的單鏈表，其數(shù)據(jù)元素是字符字母、字符、數(shù)字字符、其他字符。本算法將A表分成三個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表A、和，分別含有字母、數(shù)字和其它符號(hào)的同一類字符，利用原表空間。{linklist*p=A->next,r;為工作指針，指向A表的當(dāng)前元素，r為當(dāng)前元素的后繼指針使表避免斷開。將將算法思想是取出當(dāng)前元素，根據(jù)是字母、數(shù)字或其它符號(hào)，分別插入相應(yīng)表中。=(init)a(ize￡(申逾空間i不判斷溢出B->next=null;準(zhǔn)備將循將環(huán)鏈表的頭結(jié)點(diǎn)=(init)a(ize￡(申逾空間i不判斷溢出C->next=null;準(zhǔn)備將循將環(huán)鏈表的頭結(jié)點(diǎn)while(p){r=p->next;將用以將記住后繼結(jié)點(diǎn)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將其竊符號(hào)插入表p=r;將將恢復(fù)后繼結(jié)點(diǎn)的指針ie}將算將法結(jié)束2?11voidlocate(dlinklist*L)是帶頭結(jié)點(diǎn)的按訪問頻度遞減的雙向鏈表，本算法先查找數(shù)據(jù)將將查找成功時(shí)結(jié)點(diǎn)的訪問頻度域增1，最后將該結(jié)點(diǎn)按頻度遞減插入鏈表中適當(dāng)位置。{linklist*p=L->next,*q;為工作指針，指向表的當(dāng)前元素，為p的前驅(qū)，用于查找插入位置。ie(p&&p>data!=)p=p>ne查找值為的結(jié)點(diǎn)。if(!p)return("不存在值為的結(jié)點(diǎn)”)；eep>fre令元素值為的結(jié)點(diǎn)的fre域加1。p>net>prir=p>prir;將p結(jié)點(diǎn)從鏈表上摘下。p->prior->next=p->next;=p>prir;以下查找p結(jié)點(diǎn)的插入位置while(q!=L&&q->freq<p-freq)q=q->prior;p>net=>net;>net>pr^pr締點(diǎn)插入p->prior=q;q->ne；xt=p算將法結(jié)束第三章棧和隊(duì)列(參考答案)//從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性結(jié)構(gòu)，其順序存儲(chǔ)結(jié)構(gòu)//和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義與線性表相同，請參考教材，這里不再重復(fù)。3.1123421343214432112432143324113242314342113421432設(shè)入棧序列元素?cái)?shù)為n,23412431則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2)證明：由和pp說明p在p之前出棧，即在k未進(jìn)棧之前p已出棧，之后k進(jìn)棧，然后p出棧；由和pp說明p在p之后出棧，即p被p壓在下面，后進(jìn)先出。由以上兩條，不可能存在i使kppp。也就是說，若有，，順序入棧，不可能有，1，2的出棧序列。voidsympthy(linklist*head,stack*s)〃判斷長為n的字符串是否中心對稱{inti=1;linklist*p=head->next;while(i<=n/2)//前一半字符進(jìn)棧{push(s,p->data);p=p->next;}if(n%!==0)p=pnext;奇數(shù)個(gè)結(jié)點(diǎn)時(shí)跳過中心結(jié)點(diǎn)while(p&&p->data==pop(s))p=p->next;if(p二二null)printf(“鏈表中心對稱”)elseprintf(“鏈表不是中心對稱”)}//算法結(jié)束intmatch()//從鍵盤讀入算術(shù)表達(dá)式，本算法判斷圓括號(hào)是否正確配對(inits;//初始化棧sscanf(“%c”,&ch);while(ch!=’#’)//’#’是表達(dá)式輸入結(jié)束符號(hào)switch(ch){case’(’:push(s,ch);break;case')’：if(empty(s)){printf("括號(hào)不配對")；exit(0);}pop(s);}if(!empty(s))printf("括號(hào)不配對”)；elseprintf(“括號(hào)配對”)；}//算法結(jié)束typedefstruct//兩棧共享一向量空間{lemypem；?？捎每臻g0-minttop[2]棧/頂/指針}twostack;intpush(twostack*s,inti,ElemTypex)//兩棧共享向量空間，i是0或，表示兩個(gè)棧，x是進(jìn)棧元素，//本算法是入棧操作{if(abs(stp0stp)==)棧滿rn(0);//else{switch(i){case0：s->v[++(s->top)]=x;break;case1：s->v[--(s->top)]=x;break;default:printf("棧編號(hào)輸入錯(cuò)誤”)；return(0);}return(1);//入棧成功}}/算/法結(jié)束ElemTypepop(twostack*s,inti)兩棧共享向量空間是0或，表示兩個(gè)棧，本算法是退棧操作{ElemTypex;if(i0i)return(0編號(hào)錯(cuò)誤else{switch(i)ae0:if(tp0)棧空urn(0);elsex=s->v[s->top--];break;ae:if(tp)?？誹rn(0);elsex=s->v[s->top++];break;default:printf("棧編號(hào)輸入錯(cuò)誤”)；return(0);}return(x);/退/棧成功}}//算法結(jié)束ElemTypetop(twostack*s,inti)兩棧共享向量空間是0或，表示兩個(gè)棧，本算法是取棧頂元素操作{ElemTypex;switch(i)ae0:if(tp0)?？誹rn(0);elsex=s->v[s->top];break;ae:if(tp)?？誹rn(0);elsex=s->v[s->top];break;default:printf("棧編號(hào)輸入錯(cuò)誤”)；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é)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，本算法將隊(duì)列置空(linlit)all(ief(lin請空間t)不判斷空間溢出q->next=q;return(q);}//算法結(jié)束linklist*enqueue(linkl，isEtle*mqTypex)是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，本算法將元素入隊(duì)(linlit)all(ief(lSn請空間t)不判斷空間溢出netnet將元素結(jié)點(diǎn)入隊(duì)列q->next=s;q=s;修/改/隊(duì)尾指針?biāo)?法/結(jié)束是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，這是出隊(duì)算法判斷隊(duì)列是否為空指向出隊(duì)元素若隊(duì)列中只一個(gè)元素，置空隊(duì)列修改隊(duì)頭元素指針釋放出隊(duì)結(jié)點(diǎn)//算//法結(jié)束。算法并未返回出隊(duì)元素循環(huán)隊(duì)列占個(gè)存儲(chǔ)單元和為隊(duì)頭元素和隊(duì)尾元素的指針約定指向隊(duì)頭元素的前一位置，指向隊(duì)尾元素為循環(huán)隊(duì)列，本算法計(jì)算其長度算/法/結(jié)束循環(huán)隊(duì)列占個(gè)存儲(chǔ)單元指向隊(duì)尾元素為元素個(gè)數(shù)為循環(huán)隊(duì)列，本算法判斷隊(duì)列是否為空/算/法結(jié)束是如上定義的循環(huán)隊(duì)列，本算法將元素入隊(duì)隊(duì)滿計(jì)算插入元素位置將元素入隊(duì)列修;改隊(duì)列長度算//法結(jié)束是以如上定義的循環(huán)隊(duì)列，本算法是出隊(duì)算法，且返回出隊(duì)元素隊(duì)空出隊(duì)元素位置修;改隊(duì)列長度返回隊(duì)頭元素}/算/法結(jié)束第四章串（參考答案在以下習(xí)題解答中，假定使用如下類型定義：表示終端結(jié)點(diǎn)在向量中的位置intindex(strings,t)〃s,t是字符串，本算法求子串t在主串s中的第一次出現(xiàn)，若s串中包含t串，返回其〃第一個(gè)字符在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é)點(diǎn)的結(jié)點(diǎn)大小為的單鏈表表示的串，本算法查找中第一個(gè)不在中出現(xiàn)的字符。算法思想是先從中取出一個(gè)字符，到中去查找，如找到，則在中取下一字符，重復(fù)以上過程；若沒找到，則該字符為所求為工作指針，控制循環(huán)取中的字符和中字符比較找到中沒有的字符上一字符在中存在，取中下一字符。再從的第一個(gè)字符開始比較t)中字符在中均存在的算法結(jié)束intstrcmp(seqstring*S,seqstring*T)和是指向兩個(gè)順序串的指針，本算法比較兩個(gè)串的大小，若串大于串，返回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é)點(diǎn)的結(jié)點(diǎn)大小為的單鏈表表示的串，是主串，是模式串。本算法是先模式匹配，查找在中的第一次出現(xiàn)。如模式匹配成功，則將中的子串(串)逆置。{linkstring*pre,*sp,*tp;=是前驅(qū)指針，指向中與匹配時(shí)，中的前驅(qū)=>tt=和=分別是和串上的工作指針while(sp&&tp)i>t==t>相等時(shí)后移指針{sp=sp->next;tp=tp->next;}else失的配的時(shí)主串回溯到下一個(gè)字符，子串再以第一個(gè)字符開始{pre=pre->next;sp=pre->next;tp=T->next;}it!=)t匹配失敗，沒有逆置以下是串逆置t=>是逆置的工作指針，現(xiàn)在指向待逆置的第一個(gè)字符>t=將中與串匹配時(shí)的前驅(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個(gè)元素。以行序?yàn)橹?即行優(yōu)先)時(shí)，先改變右邊的下標(biāo)，從右到左進(jìn)行。5.2設(shè)各維上下號(hào)為c1?d1,c2?d2,c3?d3，每個(gè)元素占l個(gè)單元。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ù)元素的存儲(chǔ)位置為：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ù)組下標(biāo)從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ù)組本算法求所有馬鞍點(diǎn)是一維數(shù)組存放一行中可能的馬鞍點(diǎn)的列值記相等值個(gè)數(shù)是一維數(shù)組存放某列可能馬鞍點(diǎn)的行值記相等值個(gè)數(shù)or(i=0;i<m;i++)最小值初始化數(shù)組記最小值的列號(hào)，記最小值的個(gè)數(shù)找每一行中的最小值重新確定最小值有相等的最小值第行有個(gè)相等的最小值是否是馬鞍點(diǎn)while(kk<m&&max>=a[i][

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

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

“馬鞍點(diǎn)

時(shí)間復(fù)雜度

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

重新確定第行最小值的列號(hào)是］否;是馬鞍點(diǎn)/“馬鞍點(diǎn)時(shí)間復(fù)雜度為（1）三元組表（行號(hào)0—5，列號(hào)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用十字鏈表存儲(chǔ)結(jié)構(gòu)，本算法將稀疏矩陣B加到矩陣A上{ca=A->next;cb=B->next;while(ca!=A&&cb!=B)〃設(shè)pa和pb為矩陣A和B想加時(shí)的工作指針{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é)點(diǎn)從B表相應(yīng)列摘下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é)點(diǎn)從B表相應(yīng)行鏈表中摘下。Pbt=pb;pb=pb->right;//B表移至下一結(jié)點(diǎn)〃以下是將pbt插入A表的相應(yīng)列鏈表中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表相應(yīng)行鏈表中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é)點(diǎn)數(shù)是，則設(shè)樹的分支數(shù)為，有由（1）和（2）有：為層數(shù)其右兄弟的編號(hào)6.5（1）順序存儲(chǔ)結(jié)構(gòu)1234567891011121314ABCD#EF#G####H注：#為空結(jié)點(diǎn)）前序ABDGCEFH）中序DGBAECHF）后序GDBEHFCA）空二叉樹或任何結(jié)點(diǎn)均無左子樹的非空二叉樹）空二叉樹或任何結(jié)點(diǎn)均無右子樹的非空二叉樹）空二叉樹或只有根結(jié)點(diǎn)的二叉樹是以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹，本算法求二叉樹的高度局部變量，分別表示二叉樹左、右子樹的高度左右子樹高度的大者加（根）}算/法/結(jié)束preorder（cbt[],intn,inti）;是以完全二叉樹形式存儲(chǔ)的個(gè)結(jié)點(diǎn)的二叉樹，是數(shù)

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

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

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

(2寬)度優(yōu)先遍歷全程變量，調(diào)用函數(shù)與(1)相同，下面僅寫寬度優(yōu)先遍歷部分。{found=1;exit(0);}//有通路，退出else{p=g[x].firstarc;//第一鄰接點(diǎn)while(p!=null){k=p->adjvex;if(!Visted[k])enqueue(q,k);p=p->nextarc}}//if(y==j)}//while(!empty(q))7．5。假定該有向圖以鄰接表存儲(chǔ)，各頂點(diǎn)的鄰接點(diǎn)按增序排歹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簡單回路指起點(diǎn)和終點(diǎn)相同的簡單路徑。算法基本思想是利用圖的遍歷，以頂點(diǎn)VK開始，若遍歷中再通到VK,則存在簡單回路，否則不存在簡單回路。Adjlisttpg;visited[1..n]=0;Intfound=0;//全程變量Intdfs(btxptrx)〃從k頂點(diǎn)深度優(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所選頂點(diǎn)已選定點(diǎn)的集合尚未被選頂點(diǎn)的集合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}{}注：選定點(diǎn)4和5時(shí)無優(yōu)先順序，二者最短路徑均為29

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

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