數(shù)據(jù)結構課后答案

第一章緒論（參考答案）1.3(1)O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/：2(5)(5)執(zhí)行程序段的過程中，x,y值變化如下：循環(huán)次數(shù)xy0（初始）91100192100293100910010010101100119199129210020101992191983010198319197到y(tǒng)=0時，要執(zhí)行10*100次，可記為O（10*y）=O（n）1.52100,(2/3)n，1吵,n1/2,n3/2,(3/2)n,nlo§2n,2n,n!,nn第二章線性表(參考答案)在以下習題解答中，假定使用如下類型定義：順序存儲結構：#defineMAXSIZE1024typedefintElemType;//實際上，ElemType可以是任意類型typedefstruct{ElemTypedata[MAXSIZE];intlast;//last表示終端結點在向量中的位置}sequenlist;鏈式存儲結構(單鏈表)typedefstructnode{ElemTypedata;structnode*next；}linklist;鏈式存儲結構(雙鏈表)typedefstructnode{ElemTypedata;structnode*prior,*next；}dlinklist;靜態(tài)鏈表typedefstruct{ElemTypedata;intnext;}node;nodesa[MAXSIZE];2.1頭指針：指向鏈表的指針。因為對鏈表的所有操均需從頭指針開始，即頭指針具有標識鏈表的作用，所以鏈表的名字往往用頭指針來標識。如：鏈表的頭指針是la,往往簡稱為“鏈表la”。頭結點：為了鏈表操作統(tǒng)一，在鏈表第一元素結點(稱為首元結點，或首結點)之前增加的一個結點，該結點稱為頭結點，其數(shù)據(jù)域不無實際意義(當然，也可以存儲鏈表長度，這只是副產(chǎn)品)，其指針域指向頭結點。這樣在插入和刪除中頭結點不變。開始結點：即上面所講第一個元素的結點。2.2只設尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問鏈表上的任何結點。2-3voidinsert(ElemTypeA[],intelenum,ElemTypex)//向量A目前有elenum個元素，且遞增有序，本算法將乂插入到向量A中，并保持向量的遞增有序。{inti=0,j;while(i<elenum&&A[i]<=x)i++;//查找插入位置for(j=elenum-1;j>=i;j--)A[j+1]=A[j];//向后移動元素A[i]=x;//插入元素}//算法結束2-4voidrightrotate(ElemTypeA[],intn,k)//以向量作存儲結構，本算法將向量中的n個元素循環(huán)右移k位，且只用一個輔助空間。{intnum=0;//計數(shù)，最終應等于nintstart=0;//記錄開始位置(下標)while(num<n){temp=A[start];//暫存起點元素值，temp與向量中元素類型相同empty=start;//保存空位置下標next=(start-K+n)%n;//計算下一右移元素的下標while(next!=start){A[empty]=A[next];//右移num++;//右移元素數(shù)加1empty=next;next=(next-K+n)%n;//計算新右移元素的下標}A[empty]=temp;//把一輪右移中最后一個元素放到合適位置num++;start++;//起點增1，若num<n則開始下一輪右移。}}//算法結束算法二算法思想：先將左面n-k個元素逆置，接著將右面k個元素逆置，最后再將這n個元素逆置。voidrightrotate(ElemTypeA[],intn,k)//以向量作存儲結構，本算法將向量中的n個元素循環(huán)右移k位，且只用一個輔助空間。{ElemTypetemp;for(i=0;i<(n-k)/2;i++)//左面n-k個元素逆置{temp=A[i];A[i]=A[n-k-1-i];A[n-k-1-i]=temp;}for(i=1;i<=k;i++)//右面k個元素逆置{temp=A[n-k-i];A[n-k-i]=A[n-i];A[n-i]=temp;}for(i=0;i<n/2;i++)//全部n個元素逆置{temp=A[i];A[i]=A[n-1-i];A[n-1-i]=temp;}}//算法結束2?5voidinsert(linklist*L,ElemTypex)//帶頭結點的單鏈表L遞增有序，本算法將x插入到鏈表中，并保持鏈表的遞增有序。{linklist*p=L->next,*pre=L，*s;//p為工作指針，指向當前元素，pre為前驅指針，指向當前元素的前驅s=(linklist*)malloc(sizeof(linklist));//申請空間，不判斷溢出s->data=x;while(p&&p->data<=x){pre=p;p=p->next;}//查找插入位置pre->next=s;s->next=p;//插入元素}//算法結束2-6voidinvert(linklist*L)//本算法將帶頭結點的單鏈表L逆置?！ㄋ惴ㄋ枷胧窍葘㈩^結點從表上摘下，然后從第一個元素結點開始，依次前插入以L為頭結點的鏈表中。{linklist*p=L->next,*s;//p為工作指針，指向當前元素，s為p的后繼指針L->next=null;//頭結點摘下，指針域置空。算法中頭指針L始終不變while(p){s=p->next;//保留后繼結點的指針p->next=L->next;//逆置L->next=p;p=s;//將p指向下個待逆置結點}}//算法結束2-7intlength1(linklist*L)//本算法計算帶頭結點的單鏈表L的長度{linklist*p=L->next;inti=0;//p為工作指針，指向當前元素，i表示鏈表的長度while(p){i++;p=p->next;}return(i);}//算法結束intlength1(nodesa[MAXSIZE])//本算法計算靜態(tài)鏈表s中元素的個數(shù)。{intp=sa[0].next,i=0;//p為工作指針，指向當前元素，i表示元素的個數(shù)，靜態(tài)鏈指針等于-1時鏈表結束while(p!=-1){i++;p=sa[p].next;}return(i);}//算法結束2-8voidunion_invert(linklist*A,*B,*C)//A和B是兩個帶頭結點的遞增有序的單鏈表，本算法將兩表合并成//一個帶頭結點的遞減有序單鏈表C，利用原表空間。{linklist*pa=A->next,*pb=B->next,*C=A,*r;//pa,pb為工作指針，分別指向A表和B表的當前元素，r為當前逆置

//元素的后繼指針，使逆置元素的表避免斷開。//算法思想是邊合并邊逆置，使遞增有序的單鏈表合并為遞減有序的單鏈表。C->next=null;//頭結點摘下，指針域置空。算法中頭指針C始終不變while(pa&&pb)//兩表均不空時作if(pa->data<=pb->data)//將A表中元素合并且逆置{r=pa->next;//保留后繼結點的指針pa->next=C->next;//逆置C->next=pa;pa=r;//恢復待逆置結點的指針}else〃將B表中元素合并且逆置{r=pb->next;//保留后繼結點的指針pb->next=C->next;//逆置C->next=pb;pb=r;//恢復待逆置結點的指針}//以下while(pa)和while(pb)語句，只執(zhí)行一個while(pa){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}while(pb){r=pb->next;pb->next=C->next;C->next=pb;pb=r;}free(B);//while(pa){r=pa->next;pa->next=C->next;C->next=pa;pa=r;}while(pb){r=pb->next;pb->next=C->next;C->next=pb;pb=r;}free(B);//釋放B表頭結點}//算法結束//將A表中剩余元素逆置//保留后繼結點的指針//逆置//恢復待逆置結點的指針//將B表中剩余元素逆置//保留后繼結點的指針//逆置//恢復待逆置結點的指針//pre為前驅指針，指向當前元素*?的前驅while(p->next!=s){pre=p;p=p->next;}//查找*s的前驅pre->next=s;free(p);//刪除元素}//算法結束2-10voidone_to_three(linklist*A,*B,*C)//A是帶頭結點的的單鏈表，其數(shù)據(jù)元素是字符字母、字符、數(shù)字字符、其他字符。本算法//將A表分成//三個帶頭結點的循環(huán)單鏈表A、B和C，分別含有字母、數(shù)字和其它符號的同一類字符，利用原表空間。{linklist*p=A->next,r;//p為工作指針，指向A表的當前元素，r為當前元素的后繼指針，使表避免斷開。〃算法思想是取出當前元素，根據(jù)是字母、數(shù)字或其它符號，分別插入相應表中。

B=(linklist*)malloc(sizeof(linklist));//申請空間，不判斷溢出B->next=null;//準備循環(huán)鏈表的頭結點C=(linklist*)malloc(sizeof(linklist));//申請空間，不判斷溢出C->next=null;//準備循環(huán)鏈表的頭結點while(p){r=p->next;//用以記住后繼結點if(p->data>=’a’&&p->data<=’z’||p->data>=’A’&&p->data<=’Z’){p->next=A->next;A->next=p;}//將字母字符插入A表elseif(p->data>=’0’&&p->data<=’9’){p->next=B->next;B->next=p;}//將數(shù)字字符插入B表else{p->next=C->next;C->next=p;}//將其它符號插入C表p=r;//恢復后繼結點的指針}//while}//算法結束2-11voidlocate(dlinklist*L)//L是帶頭結點的按訪問頻度遞減的雙向鏈表，本算法先查找數(shù)據(jù)x,//查找成功時結點的訪問頻度域增1,最后將該結點按頻度遞減插入鏈表中適當位置。{linklist*p=L->next,*q;//p為工作指針，指向L表的當前元素，q為p的前驅，用于查找插入位置。while(p&&p->data!=x)p=p->next;//查找值為x的結點。if(!p)return(“不存在值為x的結點”);else{p->freq++;//令元素值為x的結點的freq域加1。p->next->prir=p->prior;//將p結點從鏈表上摘下。p->prior->next=p->next;q=p->prior;//以下查找p結點的插入位置while(q!=L&&q->freq<p-freq)q=q->prior;p->next=q->next;q->next->prior=p;//將p結點插入p->prior=q;q->next=p；}3.112342134321443211243214332411324231434211342234114322431設入棧序列元素數(shù)為n，則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2)第三章棧和隊列(參考答案)//從數(shù)據(jù)結構角度看，棧和隊列是操作受限的線性結構，其順序存儲結構//和鏈式存儲結構的定義與線性表相同，請參考教材，這里不再重復。}//算法結束3.2證明：由j<k和pj<pk說明p.在pk之前出棧，即在k未進棧之前p.已出棧，之后k進棧，然后pk出棧；由j<k和p>pk說明p.在pk之后出棧，即p.被pk壓在下面，后進先出。由以上兩條，不可能存在i<j<k使p<p：<p.。也就是說，若有、，2,3順序入棧，不可能有3,1，2的出棧序列。J1voidsympthy(linklist*head,stack*s)第三章棧和隊列(參考答案)//從數(shù)據(jù)結構角度看，棧和隊列是操作受限的線性結構，其順序存儲結構//和鏈式存儲結構的定義與線性表相同，請參考教材，這里不再重復。〃判斷長為n的字符串是否中心對稱{inti=1;linklist*p=head->next;while(i<=n/2)//前一半字符進棧{push(s,p->data);p=p->next;}if(n%2!==0)p=p->next;//奇數(shù)個結點時跳過中心結點while(p&&p->data==pop(s))p=p->next;if(p==null)printf(“鏈表中心對稱”)；elseprintf(“鏈表不是中心對稱”)；}//算法結束3.4intmatch()//從鍵盤讀入算術表達式，本算法判斷圓括號是否正確配對(inits;//初始化棧sscanf("％c”，&ch);while(ch!=’#’)//’#’是表達式輸入結束符號switch(ch){case’(’:push(s,ch);break;case’)’：if(empty(s)){printf("括號不配對”)；exit(0);}pop(s);}if(!empty(s))printf("括號不配對”)；elseprintf("括號配對”);}//算法結束3.5typedefstruct//兩棧共享一向量空間{ElemTypev[m];//?？捎每臻g0—m-1inttop[2]//棧頂指針}twostack;intpush(twostack*s,inti,ElemTypex)//兩棧共享向量空間，i是0或1，表示兩個棧，x是進棧兀素，//本算法是入棧操作{if(abs(s->top[0]-s->top[1])==1)return(0);//棧滿else{switch(i){case0:s->v[++(s->top)]=x;break;case1:s->v[—(s->top)]=x;break;default:printf(“棧編號輸入錯誤”);return(0);}return(1);//入棧成功}}//算法結束ElemTypepop(twostack*s,inti)//兩棧共享向量空間，i是0或1，表示兩個棧，本算法是退棧操作{ElemTypex;if(i!=0&&i!=1)return(0);//棧編號錯誤else{switch(i){case0:if(s->top[0]==-1)return(0);//?？誩lsex=s->v[s->top--];break;case1:if(s->top[1]==m)return(0);//^空elsex=s->v[s->top++];break;default:printf(“棧編號輸入錯誤”);return(0);}return(x);//退棧成功}}//算法結束ElemTypetop(twostack*s,inti)//兩棧共享向量空間，i是0或1,表示兩個棧，本算法是取棧頂元素操作{ElemTypex;switch(i){case0:if(s->top[0]==-1)return(0);//棧空elsex=s->v[s->top];break;case1:if(s->top[1]==m)return(0);//^空elsex=s->v[s->top];break;default:printf(“棧編號輸入錯誤”);return(0);}_return(x);//取棧頂元素成功}//算法結束3.6voidAckerman(intm,intn)//Ackerman函數(shù)的遞歸算法{if(m==0)return(n+1);elseif(m!=0&&n==0)return(Ackerman(m-1,1);elsereturn(Ackerman(m-1,Ackerman(m,n-1))}//算法結束3.7linklist*init(linklist*q)//q是以帶頭結點的循環(huán)鏈表表示的隊列的尾指針，本算法將隊列置空{q=(linklist*)malloc(sizeof(linklist));//申請空間，不判斷空間溢出q->next=q;return(q);}//算法結束linklist*enqueue(linklist*q,ElemTypex)//q是以帶頭結點的循環(huán)鏈表表示的隊列的尾指針，本算法將元素x入隊{s=(linklist*)malloc(sizeof(linklist));//申請空間，不判斷空間溢出s->next=q->next;//將元素結點s入隊列q->next=s;q=s;//修改隊尾指針return(q);}//算法結束linklist*delqueue(linklist*q)//q是以帶頭結點的循環(huán)鏈表表示的隊列的尾指針，這是出隊算法{if(q==q->next)return(null);//判斷隊列是否為空else{linklist*s=q->next->next;//s指向出隊元素if(s==q)q=q->next;//若隊列中只一個元素，置空隊列elseq->next->next=s->next;//修改隊頭元素指針free(s);//釋放出隊結點}return(q);}//算法結束。算法并未返回出隊元素3.8typedefstruct{ElemTypedata[m];//循環(huán)隊列占m個存儲單元intfront,rear;//front和rear為隊頭元素和隊尾元素的指針//約定front指向隊頭元素的前一位置，rear指向隊尾元素}sequeue;intqueuelength(sequeue*cq)//cq為循環(huán)隊列，本算法計算其長度{return(cq->rear-cq->front+m)%m;}//算法結束3.9typedefstruct{ElemTypesequ[m];//循環(huán)隊列占m個存儲單元intrear,quelen;//rear指向隊尾元素,quelen為元素個數(shù)}sequeue;intempty(sequeue*cq)//cq為循環(huán)隊列，本算法判斷隊列是否為空{return(cq->quelen==0?1:0);}//算法結束sequeue*enqueue(sequeue*cq，ElemTypex)//cq是如上定義的循環(huán)隊列，本算法將元素x入隊{if(cq->quelen==m)return(0);//隊滿else{cq->rear=(cq->rear+1)%m;//計算插入元素位置cq->sequ[cq->rear]=x;//將元素x入隊列cq->quelen++;//修改隊列長度}return(cq);}//算法結束ElemTypedelqueue(sequeue*cq)//cq是以如上定義的循環(huán)隊列，本算法是出隊算法，且返回出隊元素{if(cq->quelen==0)return(0);//隊空else{intfront=(cq->rear-cq->quelen+1+m)%m;//出隊元素位置cq->quelen--;//修改隊列長度return(cq->sequ[front]);//返回隊頭元素}}//算法結束第四章串(參考答案)在以下習題解答中，假定使用如下類型定義：#defineMAXSIZE1024typedefstruct{chardata[MAXSIZE];intcurlen;//curlen表示終端結點在向量中的位置}seqstring;typedefstructnode{chardata;structnode*next；}linkstring;4.2intindex(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結束設A=””，B=''mule”，C=''old”，D=''my”則0：(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)*”轉為T="(x+z)*y”S=concat(S,substr(S,3,1))//”(xyz)*yS=replace(S,3,1,''+”)//”(x+z)*y''4.5charsearch(linkstring*X,linkstring*Y)//X和Y是用帶頭結點的結點大小為1的單鏈表表示的串，本算法查找X中第一個不在Y中出現(xiàn)的字符。算法思想是先從X中取出一個字符，到Y中去查找，如找到，則在X中取下一字符，重復以上過程；若沒找到，則該字符為所求{linkstring*p,*q,*pre;//p,q為工作指針，pre控制循環(huán)p=X->next;q=Y->next;pre=p;while(p&&q)//取X中的字符//取X中的字符q=q->next;//和Y中字符比較//找到Y中沒有的字符//上一字符在Y中存在，//取X中下一字符。//再從Y的第一個字符開始比較//X中字符在Y中均存在while(q&&q->data!=ch)if(!q)return(ch);else{pre=p->next;p=pre;q=Y->next;}}return(null);}//算法結束4.6intstrcmp(seqstring*S,seqstring*T)//S和T是指向兩個順序串的指針，本算法比較兩個串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否則返回-1

{inti=0;while(s->ch[i]!=’\0’&&t->ch[i]!=’\0’)if(s->ch[i]>t->ch[i])return(1);elseif(s->ch[i]<t->ch[i])return(-1);elsei++;//比較下一字符if(s->ch[i]!=’\0’&&t->ch[i]==0)return(1);elseif(s->ch[i]==’\0’&&t->ch[i]!=0)return(-1);elsereturn(0);}//算法結束4.7linkstring*invert(linkstring*S,linkstring*T)//S和T是用帶頭結點的結點大小為1的單鏈表表示的串，S是主串，T是//模式串。本算法是先模式匹配，查找T在S中的第一次出現(xiàn)。如模式匹//配成功，則將S中的子串(T串)逆置。{linkstring*pre,*sp,*tp;pre=S;//pre是前驅指針，指向S中與T匹配時，T中的前驅sp=S->next;tp=T->next;//sp和tp分別是S和T串上的工作指針while(sp&&tp)if(sp->data==tp->data)//相等時后移指針{sp=sp->next;tp=tp->next;}else//失配時主串回溯到下一個字符，子串再以第一個字符開始{pre=pre->next;sp=pre->next;tp=T->next;}if(tp!=null)return(null);//匹配失敗，沒有逆置else//以下是T串逆置{tp=pre->next;//tp是逆置的工作指針，現(xiàn)在指向待逆置的第一個字符pre->next=sp;//將S中與T串匹配時的前驅指向匹配后的后繼while(tp!=sp){r=tp->next;tp->next=pre->next;pre->next=tp;tp=r}}第五章多維數(shù)組和廣義表(參考答案)5.1第五章多維數(shù)組和廣義表(參考答案)5.1A⑵[3]⑵[3],A0001,A0011,A0101,A0111,A0201,A0211,A0002,A0012,A0102,A0002,A0012,A0102,A0112,A0202,A0212A0010A0100A0110A0200A將第一維的’0變?yōu)榱撕?，可列出另?8個元素。以行序為主(即行優(yōu)先)時，先改變右邊的下標，從右到左進行。5.2設各維上下號為C]?d]，c2?d2，c3?d3，每個元素占l個單元。LOC(a)=LOC(ac1c2c3)+[(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)]*l推廣到Jn維數(shù)組??！(下界和上界)為(ci，di)，其中1<=i<=n.則：其數(shù)據(jù)元素的存儲位置為：LOC(a”.)=LOC(a]°)+[(d-c+1)??-(d-c+1)(^,-c)+(d-c+1)?(d-c+1)l22nn^11，'33，nn(j-Cc)+…+(d-c+1)(j-cJ+(j-c)]*l=LOC(a)+￡a(j-c)22nnn-1n-1nnC1C2C3iiii=1其中a,n(dk-ck+1)(1<=i<=n)k=i+1若從c開始，c數(shù)組下標從0開始，各維長度為bi(1<=i<=n)則：LOC(a.”.)=LOC(ag?)+(b*b*?*b*j+b*…*b*+j?+b*j+j)*lliein'Of)(V'D2n1QnJonJn_1J"JIJ匕??.jnUU..?U23II13II2IIIllIIn=LOC(a000)+￡aiji其中：ai=l,ai-i=bi*ai，1<i<=n(1)k=2*i+j(0<=k<3n-2)(2)i=(k+1)/3(0<=k<3n-2)j=k-2*i5.4voidsaddlepoint(inta[m][n]);//a是m行n列的二維數(shù)組，本算法求所有馬鞍點//b是一維數(shù)組,存放一行中可能的馬鞍點的列值,k記相等值個數(shù)//c是一維數(shù)組，存放某列可能馬鞍點的行值,kk記相等值個數(shù){for(i=0;i<m;i++){min=a[i,0];//最小值初始化b[0]=0;k=1;//b數(shù)組記最小值的列號，k記最小值的個數(shù)for(j=1;j<n;j++)//找每一行中的最小值if(a[i][j]<min){b[0]=j;min=a[i][j];k=1;}//重新確定最小值elseif(a[i][j]==min){b[k+1]=j;k++;}//有相等的最小值for(jj=0;jj<k;k++)//第i行有k個相等的最小值{j=b[jj];max=a[i][jj];kk=0;//a[i][j]是否是馬鞍點while(kk<m&&max>=a[i][kk])kk++;if(kk>=m)printf(“馬鞍點i=%d,j=%d,a[i][j]=%d”，i,j,a[i][j]);}//ENDOFforjj}//ENDOFfori最壞時間復雜度為O(m*(n+n*m)).(最壞時所有元素相同，都是馬鞍點)解法2:若矩陣中元素值互不相同,則用一維數(shù)組row記下各行最小值，再用一維數(shù)組col記下各列最大值，相等者為馬鞍點。for(i=0;i<m;i++){row[i]=a[i][0];//最小值初始化for(j=1;j<n;j++)//找每一行中的最小值if(a[i][j]<row[i])row[i]=a[i][j];//重新確定最小值}for(j=0;j<n;j++){col[j]=a[0,j];//最大值初始化for(i=1;i<m;i++)//找每一列中的最大值if(a[i][j]>col[j])col[j]=a[i][j];//重新確定最大值}for(i=0;i<m;i++)for(j=1;j<n;j++)if(row[i]==col[j])printf(“馬鞍點i=%d,j=%d,a[i][j]=%d”，i,j,a[i][j]);時間復雜度O((m*n)).解法3:設定兩個數(shù)組：max[0..n-1]記各列的最大值所在行號min[0..m-1]記各行的最小值所在列號第j列的最大值為A[max[j]][j],第i行的最小值是A[i][min[i]]

voidsaddlepoint（inta[m][n]）;//a是m行n列的二維數(shù)組，本算法求所有馬鞍點{intmax[]=0,min[]=0;for（i=0;i<m;i++）for（i=0;i<m;i++）for（j=0;j<n;k++）{if（A[i][j]>A[max[j]][j]）max[j]=i;//重新確定第j列最大值的行號if（A[i][j]<A[i][min[i]]）min[i]=j;//重新確定第i行最小值的列號}for（i=0;i<m;i++）{j=min[i];//a[i][j]是否是馬鞍點if（max[j]==i）printf（“馬鞍點A[%d][%d]=%d”，i,j,a[i][j]）;}//ENDOFforjj}時間復雜度為O（m*n+m）.5.5（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））（2）5.6算法分析：兩矩陣A和B相加的結果是一矩陣C，其元素Ci.有三種情況；(1)4=氣.(B..=0)；(2)C..=B..(A..=0)；(3)C..=A..+B..。在(3)種情況下，要看結果是否為0,c矩陣只有非零元素？ijij口Voidmatrixaddition(crosslist*A,*B)//稀疏矩陣A和B用十字鏈表存儲結構，本算法將稀疏矩陣B加到矩陣A上(ca=A->next;cb=B->next;while(ca!=A&&cb!=B)〃設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;//該結點從B表相應列摘下i=pb->right;pt=chb[i];pre=pt;//取B表行表頭指針while(pt->right->row<pb->row{pre=pt;pt=pt->right;}pre->right=pt->riht;//該結點從B表相應行鏈表中摘下。Pbt=pb;pb=pb->right;//B表移至下一結點〃以下是將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>co<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;}5.7(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)

第6章樹和二叉樹（參考答案）6.1⑴根結點a6.2三個結點的樹的形態(tài):(1)6.3設樹的結點數(shù)是n，貝0n=n0+n1+n2++nm+(1)設樹的分支數(shù)為B,有n=B+1n=1n1+2n2++mnm+1(2)由(1)和(2)有：n0=n2+2n3++第6章樹和二叉樹（參考答案）6.1⑴根結點a6.2三個結點的樹的形態(tài):(1)6.4ki-1(i為層數(shù))(n-2)/k+1

(n-1)*k+i+1(n-1)%k!=0;其右兄弟的編號n+16.5(1)順序存儲結構1234567891011121314ABCD#EF#G####H#為空結點注：6.6(1)6.6⑵(3)中序DGBAECHF后序GDBEHFCA6.7(1)⑵中序DGBAECHF后序GDBEHFCA(1)⑵(3)6.8height(bitreebt)height(bitreebt)//bt是以二叉鏈表為存儲結構的二叉樹，本算法求二叉樹bt的高度{intbl,br;//局部變量，分別表示二叉樹左、右子樹的高度if(bt==null)return(0);else{bl=height(bt->lchild);br=height(bt->rchild);return(bl>br?bl+1:br+1);//左右子樹高度的大者加1(根)}}//算法結束6.9voidpreorder(cbt[],intn,inti);//cbt是以完全二叉樹形式存儲的n個結點的二叉樹，i是數(shù)//組下標，初始調用時為1。本算法以非遞歸形式前序遍歷該二叉樹{inti=1,s[],top=0;//s是棧，棧中元素是二叉樹結點在cbt中的序號//top是棧頂指針，?？諘rtop=0if(n<=0){printf(“輸入錯誤”);exit(0)；}while(i<=n||top>0){while(i<=n){visit(cbt[i]);//訪問根結點if(2*i+1<=n)s[++top]=2*i+1;//若右子樹非空，其編號進棧i=2*i;//先序訪問左子樹}if(top>0)i=s[top--];//退棧，先序訪問右子樹}//ENDOFwhile(i<=n||top>0)}//算法結束〃以下是非完全二叉樹順序存儲時的遞歸遍歷算法，“虛結點”用‘"表示voidpreorder(bt[],intn,inti);//bt是以完全二叉樹形式存儲的一維數(shù)組，n是數(shù)組元素個數(shù)。i是數(shù)//組下標，初始調用時為1。{if(i<=n&&bt[i]!=’*’){visit(bt[i]);preorder(bt,n,2*i);preorder(bt,n,2*i+1);}//算法結束6.10intequal(bitreeT1,bitreeT2);//T1和T2是兩棵二叉樹，本算法判斷T1和T2是否等價//T1和T2都是空二叉樹則等價//T1和T2只有一棵為空，另一棵非空，則不等價//T1和T2均非空，且根結點值相等，則比較其左、右子樹{if(T1==null&&T2==null)return(1);//同為空二叉樹elseif(T1==null||T2==null)return(0);//只有一棵為空elseif(T1->data!=T2->data)return(0);//根結點值不等elsereturn(equal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild))//判左右子樹等價}//算法結束11voidlevelorder(bitreeht);{本算法按層次遍歷二叉樹ht}{if(ht!=null){initqueue(q);{處始化隊列，隊列元素為二叉樹結點的指針}enqueue(q,ht);{根結點指針入隊列}while(!empty(q)){p=delqueue(q);visit(p);//訪問結點if(p->lchild!=null)enqueue(q,p->lchild);//若左子女非空，則左子女入隊列if(p->rchild!=null)enqueue(q,p->rchild)；//若右子女非空，則右子女入隊列}}}//算法結束6.12voidpreorder(bitree*t);(前序非遞歸遍歷){bitree*s[n+1];//s是指針數(shù)組，數(shù)組中元素為二叉樹節(jié)點的指針top=0;while(t!=null||top!=0){while(t!=null){visit(*t);s[++top]=t;t=t->lchild}if(top!=0){t=s[top—];t=t->rchild;}}}//算法結束voidinorder(bitree*t);(中序非遞歸遍歷){bitree*s[n+1];top=0;while((t!=null||top!=0){while(t!=null){s[++top]=t;t=t->lchild}if(top!=0){t=s[top—];visit(*t);t=t->rchild;}}//算法結束voidpostorder(bitree*t);(后序非遞歸遍歷){typedefstructnode{bitree*t;tag:0..1}stack;stacks[n+1];top=0;while(t||top){while(t){s[++top].t=t;s[top].tag=0;t=t->lchild;}while(top&&s[top].tag==1){printf(s[top—].t->data:3);}if(top){s[top].tag=1;t=s[top].t->rchild;}}}//算法結束6.13bitree*dissect(bitree**t,ElemTypex)//二叉樹t至多有一個結點的數(shù)據(jù)域為x,本算法拆去以x為根的子樹//拆開后的第一棵樹用t表示，成功拆開后返回第二棵二叉樹{bitree*p,*find;if(*t!=null){if((*t)->data==x)//根結點數(shù)據(jù)域為x{p=*t;*t=null;return(p);}else{find=(dissect(&(*t)->lchild),x);//在左子樹中查找并拆開//若在左子樹中未找到，就到右子樹中查找并拆開if(!find)find=(dissect(&(*t)->rchild),x);return(find);}}elsereturn(null);//空二叉樹}//算法結束6.14intsearch(bitreet,ElemTypex)//設二叉樹t中，值為x的結點至多一個，本算法打印x的所有祖先//算法思想是，借助后序非遞歸遍歷，用棧裝遍歷過程的結點，當查到//值為x的結點時，棧中元素都是x的祖先{typedefstruct{bitreep;inttag;}snode;snodes[];inttop=0;while(t&&t->data!=x||top)

{while(t&&t->data!=x)//沿左分支向下{s[++top].p=t;s[top].tag=0;t=t->lchild;}if(t->data==x)//{for(i=1;i<=top;++i)printf("％c\n”，s[i].p->data);//輸出，設元素為字符return(1);}elsewhile(top>0&&s[top].tag==1)top--;//退出右子樹已訪問的結點if(top>0)//置訪問標志1，訪問右子樹{s[top].tag=1;t=s[top].p;t=t->rchild;}}return(0);//沒有值為x的結點}//算法結束6.15中序序列BDCEAFHG___后序序列DECBHGFAZ'"一一、【A前序序列ABCDEFGH6.16后序線索樹：null_/.-E0A0/0B1//0C0100/0A0/0B1//0C0100/1E1/0F1/I1IH6.17bitree*search(bitree*p)//查找前序線索二叉樹上給定結點p的前序后繼{if(p->ltag==1)return(p->rchild)；//左標記為1時，若p的右子樹非空，p的右子樹的根p->rchild為p的后繼；若右子樹為空，p->rchild指向后繼elsereturn(p->lchild);//左標記為0時，p的左子女p->lchild為p的后繼.}//算法結束6.18bitree*search(b：tree*p)//在后序線索二叉樹中查找給定結點的后序前驅的算法{if(p->rtag==0)return(p->rchild);//p有右子女時，其右子女p->rchild是p的后序前驅elsereturn(p->lchild);//p的左標記為0，左子女p->lchild是后序前驅，否則，線索p->lchild指向p的后序前驅}6.196.21}27,19,2,6,32,3,21,10其對應字母分別為a,b,c,e,f,g,h。哈夫曼編碼：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章圖(參考答案)1(1)鄰接矩陣中非零元素的個數(shù)的一半為無向圖的邊數(shù)；A[i][j]==0為頂點，I和j無邊，否則j和j有邊相通;任一頂點I的度是第I行非0元素的個數(shù)。7.2(1)任一頂點間均有通路，故是強連通；(2)簡單路徑V4V3V1V2;(3)01818018180888鄰接矩陣10V1=?V4|?V2laV2?V3lAV3V1lAV3|aV4鄰接表V1?V3|aV2?V1|AV4|aV2|aV3?V4—V1lA逆鄰接表7.3(1)鄰接表從頂點4開始的DFS序列：V5,V3,V4,V6,V2,V1從頂點4開始的BFS序列：V4,V5,V3,V6,V1,V27.4(1)①adjlisttpg;vtxptri,j;//全程變量voiddfs(vtxptrx)//從頂點x開始深度優(yōu)先遍歷圖g。在遍歷中若發(fā)現(xiàn)頂點j,則說明頂點i和j間有路徑。{visited[x]=1;//置訪問標記if(y==j){found=1;exit(0);}//有通路，退出else{p=g[x].firstarc;//找x的第一鄰接點while(p!=null){k=p->adjvex;if(!visited[k])dfs(k);p=p->nextarc;//下一鄰接點}}voidconnect_DFS(adjlisttpg)〃基于圖的深度優(yōu)先遍歷策略，本算法判斷一鄰接表為存儲結構的圖g種，是否存在頂點i//到頂點j的路徑。設1<=i,j<=n,i<>j.(visited[1..n]=0;found=0;scanf(&i,&j);dfs(i);if(found)printf(”頂點”,i,”和頂點”,j,”有路徑”)；elseprintf(”頂點”,i,”和頂點”,j,”無路徑”)；}//voidconnect_DFS(2)寬度優(yōu)先遍歷全程變量，調用函數(shù)與(1)相同，下面僅寫寬度優(yōu)先遍歷部分。voidbfs(vtxptrx)//

{initqueue(q);enqueue(q,x);while(!empty(q));{y=delqueue(q);if(y==j)(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。假定該有向圖以鄰接表存儲，各頂點的鄰接點按增序排列DFS序歹U：BFS序歹UDFS序歹U：BFS序歹U：DFS森林1V7V1,V3,V6,V7,V4,V2,V5,V8V1,V3,V4,V6,V7,V2,V5,V8、2V5W8BFS森林V2V5J?7.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)}//dfs(2)KRUSKAL算法的最小生成樹(權值相同的邊選取無順序)7.8所選頂點已選定點的集合尚未被選頂點的集合DIST[2][3][4][5][6]初態(tài){1}{2,3,4,5,6}20158883{1，3}{2,4,5,6}1988252{1,3,2}{4,5,6}829256{1,3,2,6}{4,5}29294{1,3,2,6,4}{5}295{1,3,2,6,4,5}{}注：選定點4和5時無優(yōu)先順序，二者最短路徑均為297.9Z0881200:1->1A0=308path0=1201:1->2I5201238：1到3沒有直接通路Z088path1同path0,加入頂點1后無變化A1=308520K488^A2=308path2同path1k28/088A3=308本題不好，終態(tài)和初態(tài)無變化

,V2,V3,共七種用TOPOSORT算法求得第七種，用鄰接表存儲結構，鄰接點逆序即編號大的排在前面。入度為0頂點用棧結構存儲，初始時從頂點1到頂點N掃描，入度為0的頂點進棧，得V5在棧頂。,V2,V3,7.11voidtoposort_dfs(graphg；vtptrv)〃從頂點v開始，利用深度優(yōu)先遍歷對圖g進行拓撲排序。//基本思想是利用棧s存放頂點，首先出棧的頂點是出度為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”,”頂點開始拓撲排序不能順利完成”)；elseprintf(“拓撲排序成功，輸出的是一個逆拓撲序列.\n”)；}7.12

V100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220關鍵路徑V1->V3->V4->V7->V9->V10長22關鍵活動a3,a4,a7,a11,a14頂點VeVl活動ell-eV100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220關鍵路徑V1->V3->V4->V7->V9->V10長22關鍵活動a3,a4,a7,a11,a14第八章排序（參考答案）本章所用數(shù)據(jù)結構#defineN待排序記錄的個數(shù)typedefstruct{intkey;ElemTypeother;}rectype;rectyper[n+1];//r為結構體數(shù)組8.2穩(wěn)定排序有：直接插入排序、起泡排序、歸并排序、基數(shù)排序不穩(wěn)定排序有：希爾排序、直接選擇排序、堆排序希爾排序例：49，38,_49，90，70，25直接選擇排序例：2，2，1堆排序例：1，2，28.3voidStlinkedInsertSort(s,n);//對靜態(tài)鏈表s[1..n]進行表插入排序，并調整結果，使表物理上排序{#defineMAXINT機器最大整數(shù)typedefstruct{intkey;intnext;}rec;recs[n+1];//s為結構體數(shù)組s[0].key=maxint;s[1].next=0;//頭結點和第一個記錄組成循環(huán)鏈表i=2;〃從第2個元素開始，依次插入有序鏈表中while(i<=n){q=0;p=s[0].next;//p指向當前最小元素，q是p的前驅while(p!=0&&s[p].key<s[i].key)//查找插入位置{q=p;p=s[p].next;}s[i].next=p;s[q].next=i;//將第個元素鏈入i++；}//while(i<=n)靜態(tài)鏈表的插入//以下是重排靜態(tài)鏈表，使之物理有序i=1;p=s[0].next;while(i<=n){WHILE(p<i)p=s[p].next;q=s[p].next;if(i!=p){s[i](3s[p];s[i].next=p;p=q;i++;}}}//算法結束8.4voidTwoWayBubbleSort(rectyper[n+1];intn)//對r[1..n]進行雙向冒泡排序。即相鄰兩遍向兩個相反方向起泡{inti=1,exchange=1;//設標記while(exchange){exchange=0;//假定本趟無交換for(j=n-i+1j>=i+1;j--)//向前起泡，一趟有一最小冒出if(r[j]<r[j-1]){r[j]Or[j-1];exchange=1;}//有交換for(j=i+1;j>=n-I;j++)//向后起泡，一趟有一最大沉底if(r[j]>r[j+1]){r[j]Or[j+1];exchange=1;}//有交換i++;}//endofWHILEexchange}//算法結束8.5在n=7時，最好情況下進行10次比較。6次比較完成第一趟快速排序，將序列分成相等程度的序列(各3個元素)，再各進行2次比較，完成全部排序。最好的初始排列：4，1，3，2，6,5，78.6voidQuickSort(rectyper[n+1];intn)//對r[1..n]進行快速排序的非遞歸算法{typedefstruct{intlow,high;}nodenodes[n+1]；inttop;intquickpass(rectyper[],int,int);//函數(shù)聲明top=1;s[top].low=1;s[top].high=n;while(top>0){ss=s[top].low;tt=s[top].high;top—;if(ss<tt){k=quickpass(r,ss,tt);if(k-ss>1){top++;s[top].low=ss;s[top].high=k-1;}if(tt-k>1){top++;s[top].low=k+1;s[top].high=tt;}}}//算法結束intquickpass(rectyper[];ints,t){i=s;j=t;rp=r[i];x=r[i].key;while(i<j){while(i<j&&x<=r[j].key)j—;if(i<j)r[i++]=r[j];while(i<j&&x>=r[j].key)i++;if(i<j)r[j--]=r[i];;]r[i]=rp;return(i);}//一次劃分算法結束8.7voidQuickSort(rectyper[n+1];intn)//對r[1..n]進行快速排序的非遞歸算法對8.6算法的改進{typedefstruct{intlow,high;}nodenodes[n+1]；inttop;intquickpass(rectyper[],int,int);//函數(shù)聲明top=1;s[top].low=1;s[top].high=n;ss=s[top].low;tt=s[top].high;top—;flag=true;while(flag||top>0){k=quickpass(r,ss,tt);if(k-ss>tt-k)//一趟排序后分割成左右兩部分{if(k-ss>1)//左部子序列長度大于右部，左部進棧{top++;s[top].low=ss;s[top].high=k-1;}if(tt-k>1)ss=k+1;//右部短的直接處理elseflag=false;//右部處理完，需退棧}elseif(tt-k>1)//右部子序列長度大于左部，右部進棧{top=top+1;s[top].low=k+1;s[top].high=tt;}if(k-ss>1)tt=k-1//左部短的直接處理elseflag=false//左部處理完，需退棧}if(!flag&&top>0){ss=s[top].low;tt=s[top].high;top--;flag=true;}}//endofwhile(flag||top>0)}//算法結束intquickpass(rectyper[];ints,t)//用“三者取中法”對8.6進行改進{inti=s,j=t,mid=(s+t)/2;rectypetmp;if(r[i].key>r[mid].key){tmp=r[i];r[i]=r[mid];r[mid]=tmp}if(r[mid].key>r[j].key){tmp=r[j];r[j]=r[mid];if(tmp>r[i])r[mid]=tmp;else{r[mid]=r[i];r[i]=tmp}}{tmp=r[i];r[i]=r[mid];r[mid]=tmp}//三者取中：最佳2次比較3次移動；最差3次比較10次移動rp=r[i];x=r[i].key;while(i<j){while(i<j&&x<=r[j].key)j--;if(i<j)r[i++]=r[j];while(i<j&&x>=r[j].key)i++;if(i<j)r[j--]=r[i];;]r[i]=rp;return(i);}//一次劃分算法結束8.8viodsearchjrec(rectyper[]，intj)//在無序記錄r[n]中，找到第j(0<=j<n)個記錄。算法利用快速排序思想，找到第一〃軸元素的位置i，若i=j則查找結束。否則根據(jù)j<i或j>i在0?i、1或i+1?n+1之間查〃找，直到/i習為止。(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算法結束8.9viodrearrange(rectyper[],intn)//本算法重排具有n個元素的數(shù)r，使取負值的關鍵字放到取非負值的關鍵字之前。(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];//取負值關鍵字記錄放到左面while(i<j&&r[i].key<0)i++;if(i<j)r[j--]=r[i]//取非負值關鍵字記錄放到右面}//while(i<j)8.9voidarrange(rectyper[n+1];intn)//對r[1..n]進行整理，使關鍵字為負值的記錄排在非負值的記錄之前[inti=0,j=-1;rp=r[0];while(i<j){while(i<j&&r[j].key>=0)j—;if(i<j)r[i++]=r[j];//將關鍵字取負值的記錄放到前面while(i<j&&r[i].key<0)i++;if(i<j){r[j--]=r[i];//將關鍵字取非負值的記錄放到后面}r[i]=rp;//}〃算法結束〃本算法并未判斷軸樞的關鍵字的正負，在排序中并未和軸樞〃記錄比較，而是按正負區(qū)分，提高了效率8.10typedefstructnode{ElemTypedata;structnode*next;}linklist;voidsimpleselect(linklist*head)//head是單鏈表的頭指針，本算法對其進行直接選擇排序。設p指向無序區(qū)第一個記錄(開始是鏈表的第一個記錄)，用q指向一趟排序中的最小記錄，為簡便起見，將P和q所指結點的數(shù)據(jù)交換。{p=head->next;while(p->next!=null)//剩最后一個元素時，排序結束{q=p;//設當前結點為最小s=p->next;//s指向待比較結點while(s!=null)if(s->data>q->data)s=s->next;else{q=s;s=s->next;}//用指向新的最小if(q!=p){x=q->data;q->data=p->data;p->data=x;}p=p->next;//鏈表指針后移，指向下一個最小值結點}}〃算法結束8.11按極小化堆取調整(若已是極大化堆則維持不變)(1)(2)(以T口為根的子樹不符合根定義)(3)(4)(以T口為根的子樹不符合根定義)(4)8.11voidheapadjust(K[],n)〃待排序元素在向量K中，從K1到Kn已是堆，現(xiàn)將第n+1個元素加入，本算法這n+1個元素調整成堆。{rp=K[n+1];x=K[n+1].key;//用rp暫存第n+1個元素，x為其關鍵字intc=n+1,f=c/2;//設c表示第n+1個元素的下標，f是其雙親的下標，本算法將子女與雙親比較，若符合堆的定義，則排序結束；否則將雙親和子女交換。之后，雙親的下標為新的子女，再與新的雙親比較，直至根結點(無雙親)while(f>0)if(K[f].key<=x)break;//已符合堆的定義，排序結束else{K[c]=k[f];c=f;f=c/2;}//僅將雙親移至子女K[c]=rp;//將暫存記錄rp(原第n+1個記錄)放入合適位置}//算法結束//利用上述排序思想，從空堆開始，一個一個添加元素的建堆算法如下：voidheapbuilder(rectypeR[])//向量R的第1到第n個元素為待排序元素，本算法將這n個元素建成堆。{for(i=0;i<n;i++)heapadjust(R，i);}〃算法結束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;//最后一個子序列下界〃以下為兩兩歸并，當最后只剩下一個有序子序列(即|rear-front=1|)時，合并結束。while((front+1)%m!=rear)(newrear=rear;while((front+1)%m!=rear)//從r合并到r1中合并{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)〃設a數(shù)組中a[l.....m]和a1[m+1.....h]有序，本算法使l....h有序，并拷貝到a1中{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++];}8.14voidCountSort(rectyper[];intn);//對r[0..n-1]進行計數(shù)排序{intc[n]={0};//c數(shù)組初始化，元素值指其在r中的位置。如c[i]=j,(0<=i,j<n)//則意味著r[i]應在r的第j位置上。for(i=0;i<n;i++)//一趟掃描比較選出大小，給數(shù)組c賦值for(j=i+1;j<n;j++)if(r[i]>r[j])c[i]=c[i]+1elsec[j]=c[j]+1;for(i=0;i<n;i++)while(c[i]!=i)//若c[i]=i,則r[i]正好是第i個元素;否則，需要調整{k=c[i];temp=r[k];r[k]=r[i];r[i]=temp;//r[k]和r[i]交換c[i]=c[k];〃將c[k]存入c[i],c[k]=k;//r[k]已是第k個記錄//while(c[i]!=i)8.15#defineD10//假設每個關鍵字長度為10typedefstruct{charkey[D];//關鍵字用字符數(shù)組表示anytype:otheritem;//元素的其他信息intnext;//指針域}rcdnode;rcdnoder[n];//為n個英文單詞為關鍵字的記錄排序intf[27],e[27];intdistribute(inti;intp)//靜態(tài)鏈表r中的記錄按key[i+1]，，key[D侑序，p指向鏈表中第一記錄。本算法//第I位關鍵字key[i]建立子表，同一子表中的key[i]值相同。巾]和e[i]分別指向各子表〃中第一個記錄和最后一個記錄。0<=j<=27，key[i]為空格時，j=0；而key[i]為字母時，j=〃該字母的ASCII碼-64。f[i]=0表示第j個子表為空{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所指結點插入第j個子表}p=r[p].next;//p指向下一個元素}//forintcollet(inti)//