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

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

B=(linklist*)malloc(sizeof(linklist));//申請(qǐng)空間，不判斷溢出B->next=null;//準(zhǔn)備循環(huán)鏈表的頭結(jié)點(diǎn)C=(linklist*)malloc(sizeof(linklist));//申請(qǐng)空間，不判斷溢出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->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;}//將其它符號(hào)插入C表p=r;//恢復(fù)后繼結(jié)點(diǎn)的指針}//while}//算法結(jié)束2-11voidlocate(dlinklist*L)//L是帶頭結(jié)點(diǎn)的按訪問(wèn)頻度遞減的雙向鏈表，本算法先查找數(shù)據(jù)x,//查找成功時(shí)結(jié)點(diǎn)的訪問(wèn)頻度域增1,最后將該結(jié)點(diǎn)按頻度遞減插入鏈表中適當(dāng)位置。{linklist*p=L->next,*q;//p為工作指針，指向L表的當(dāng)前元素，q為p的前驅(qū)，用于查找插入位置。while(p&&p->data!=x)p=p->next;//查找值為x的結(jié)點(diǎn)。if(!p)return(“不存在值為x的結(jié)點(diǎn)”);else{p->freq++;//令元素值為x的結(jié)點(diǎn)的freq域加1。p->next->prir=p->prior;//將p結(jié)點(diǎn)從鏈表上摘下。p->prior->next=p->next;q=p->prior;//以下查找p結(jié)點(diǎn)的插入位置while(q!=L&&q->freq<p-freq)q=q->prior;p->next=q->next;q->next->prior=p;//將p結(jié)點(diǎn)插入p->prior=q;q->next=p；}3.112342134321443211243214332411324231434211342234114322431設(shè)入棧序列元素?cái)?shù)為n，則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2)第三章棧和隊(duì)列(參考答案)//從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性結(jié)構(gòu)，其順序存儲(chǔ)結(jié)構(gòu)//和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義與線性表相同，請(qǐng)參考教材，這里不再重復(fù)。}//算法結(jié)束3.2證明：由j<k和pj<pk說(shuō)明p.在pk之前出棧，即在k未進(jìn)棧之前p.已出棧，之后k進(jìn)棧，然后pk出棧；由j<k和p>pk說(shuō)明p.在pk之后出棧，即p.被pk壓在下面，后進(jìn)先出。由以上兩條，不可能存在i<j<k使p<p：<p.。也就是說(shuō)，若有、，2,3順序入棧，不可能有3,1，2的出棧序列。J1voidsympthy(linklist*head,stack*s)第三章棧和隊(duì)列(參考答案)//從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性結(jié)構(gòu)，其順序存儲(chǔ)結(jié)構(gòu)//和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義與線性表相同，請(qǐng)參考教材，這里不再重復(fù)?！ㄅ袛嚅L(zhǎng)為n的字符串是否中心對(duì)稱{inti=1;linklist*p=head->next;while(i<=n/2)//前一半字符進(jìn)棧{push(s,p->data);p=p->next;}if(n%2!==0)p=p->next;//奇數(shù)個(gè)結(jié)點(diǎn)時(shí)跳過(guò)中心結(jié)點(diǎn)while(p&&p->data==pop(s))p=p->next;if(p==null)printf(“鏈表中心對(duì)稱”)；elseprintf(“鏈表不是中心對(duì)稱”)；}//算法結(jié)束3.4intmatch()//從鍵盤讀入算術(shù)表達(dá)式，本算法判斷圓括號(hào)是否正確配對(duì)(inits;//初始化棧sscanf("％c”，&ch);while(ch!=’#’)//’#’是表達(dá)式輸入結(jié)束符號(hào)switch(ch){case’(’:push(s,ch);break;case’)’：if(empty(s)){printf("括號(hào)不配對(duì)”)；exit(0);}pop(s);}if(!empty(s))printf("括號(hào)不配對(duì)”)；elseprintf("括號(hào)配對(duì)”);}//算法結(jié)束3.5typedefstruct//兩棧共享一向量空間{ElemTypev[m];//?？捎每臻g0—m-1inttop[2]//棧頂指針}twostack;intpush(twostack*s,inti,ElemTypex)//兩棧共享向量空間，i是0或1，表示兩個(gè)棧，x是進(jìn)棧兀素，//本算法是入棧操作{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(“棧編號(hào)輸入錯(cuò)誤”);return(0);}return(1);//入棧成功}}//算法結(jié)束ElemTypepop(twostack*s,inti)//兩棧共享向量空間，i是0或1，表示兩個(gè)棧，本算法是退棧操作{ElemTypex;if(i!=0&&i!=1)return(0);//棧編號(hào)錯(cuò)誤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(“棧編號(hào)輸入錯(cuò)誤”);return(0);}return(x);//退棧成功}}//算法結(jié)束ElemTypetop(twostack*s,inti)//兩棧共享向量空間，i是0或1,表示兩個(gè)棧，本算法是取棧頂元素操作{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(“棧編號(hào)輸入錯(cuò)誤”);return(0);}_return(x);//取棧頂元素成功}//算法結(jié)束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))}//算法結(jié)束3.7linklist*init(linklist*q)//q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，本算法將隊(duì)列置空{(diào)q=(linklist*)malloc(sizeof(linklist));//申請(qǐng)空間，不判斷空間溢出q->next=q;return(q);}//算法結(jié)束linklist*enqueue(linklist*q,ElemTypex)//q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，本算法將元素x入隊(duì){s=(linklist*)malloc(sizeof(linklist));//申請(qǐng)空間，不判斷空間溢出s->next=q->next;//將元素結(jié)點(diǎn)s入隊(duì)列q->next=s;q=s;//修改隊(duì)尾指針return(q);}//算法結(jié)束linklist*delqueue(linklist*q)//q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，這是出隊(duì)算法{if(q==q->next)return(null);//判斷隊(duì)列是否為空else{linklist*s=q->next->next;//s指向出隊(duì)元素if(s==q)q=q->next;//若隊(duì)列中只一個(gè)元素，置空隊(duì)列elseq->next->next=s->next;//修改隊(duì)頭元素指針free(s);//釋放出隊(duì)結(jié)點(diǎn)}return(q);}//算法結(jié)束。算法并未返回出隊(duì)元素3.8typedefstruct{ElemTypedata[m];//循環(huán)隊(duì)列占m個(gè)存儲(chǔ)單元intfront,rear;//front和rear為隊(duì)頭元素和隊(duì)尾元素的指針//約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素}sequeue;intqueuelength(sequeue*cq)//cq為循環(huán)隊(duì)列，本算法計(jì)算其長(zhǎng)度{return(cq->rear-cq->front+m)%m;}//算法結(jié)束3.9typedefstruct{ElemTypesequ[m];//循環(huán)隊(duì)列占m個(gè)存儲(chǔ)單元intrear,quelen;//rear指向隊(duì)尾元素,quelen為元素個(gè)數(shù)}sequeue;intempty(sequeue*cq)//cq為循環(huán)隊(duì)列，本算法判斷隊(duì)列是否為空{(diào)return(cq->quelen==0?1:0);}//算法結(jié)束sequeue*enqueue(sequeue*cq，ElemTypex)//cq是如上定義的循環(huán)隊(duì)列，本算法將元素x入隊(duì){if(cq->quelen==m)return(0);//隊(duì)滿else{cq->rear=(cq->rear+1)%m;//計(jì)算插入元素位置cq->sequ[cq->rear]=x;//將元素x入隊(duì)列cq->quelen++;//修改隊(duì)列長(zhǎng)度}return(cq);}//算法結(jié)束ElemTypedelqueue(sequeue*cq)//cq是以如上定義的循環(huán)隊(duì)列，本算法是出隊(duì)算法，且返回出隊(duì)元素{if(cq->quelen==0)return(0);//隊(duì)空else{intfront=(cq->rear-cq->quelen+1+m)%m;//出隊(duì)元素位置cq->quelen--;//修改隊(duì)列長(zhǎng)度return(cq->sequ[front]);//返回隊(duì)頭元素}}//算法結(jié)束第四章串(參考答案)在以下習(xí)題解答中，假定使用如下類型定義：#defineMAXSIZE1024typedefstruct{chardata[MAXSIZE];intcurlen;//curlen表示終端結(jié)點(diǎn)在向量中的位置}seqstring;typedefstructnode{chardata;structnode*next；}linkstring;4.2intindex(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串中無(wú)子串t}//算法index結(jié)束設(shè)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)*”轉(zhuǎn)為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是用帶頭結(jié)點(diǎn)的結(jié)點(diǎn)大小為1的單鏈表表示的串，本算法查找X中第一個(gè)不在Y中出現(xiàn)的字符。算法思想是先從X中取出一個(gè)字符，到Y(jié)中去查找，如找到，則在X中取下一字符，重復(fù)以上過(guò)程；若沒(méi)找到，則該字符為所求{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(jié)中沒(méi)有的字符//上一字符在Y中存在，//取X中下一字符。//再?gòu)腨的第一個(gè)字符開始比較//X中字符在Y中均存在while(q&&q->data!=ch)if(!q)return(ch);else{pre=p->next;p=pre;q=Y->next;}}return(null);}//算法結(jié)束4.6intstrcmp(seqstring*S,seqstring*T)//S和T是指向兩個(gè)順序串的指針，本算法比較兩個(gè)串的大小，若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);}//算法結(jié)束4.7linkstring*invert(linkstring*S,linkstring*T)//S和T是用帶頭結(jié)點(diǎn)的結(jié)點(diǎn)大小為1的單鏈表表示的串，S是主串，T是//模式串。本算法是先模式匹配，查找T在S中的第一次出現(xiàn)。如模式匹//配成功，則將S中的子串(T串)逆置。{linkstring*pre,*sp,*tp;pre=S;//pre是前驅(qū)指針，指向S中與T匹配時(shí)，T中的前驅(qū)sp=S->next;tp=T->next;//sp和tp分別是S和T串上的工作指針while(sp&&tp)if(sp->data==tp->data)//相等時(shí)后移指針{sp=sp->next;tp=tp->next;}else//失配時(shí)主串回溯到下一個(gè)字符，子串再以第一個(gè)字符開始{pre=pre->next;sp=pre->next;tp=T->next;}if(tp!=null)return(null);//匹配失敗，沒(méi)有逆置else//以下是T串逆置{tp=pre->next;//tp是逆置的工作指針，現(xiàn)在指向待逆置的第一個(gè)字符pre->next=sp;//將S中與T串匹配時(shí)的前驅(qū)指向匹配后的后繼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個(gè)元素。以行序?yàn)橹?即行優(yōu)先)時(shí)，先改變右邊的下標(biāo)，從右到左進(jìn)行。5.2設(shè)各維上下號(hào)為C]?d]，c2?d2，c3?d3，每個(gè)元素占l個(gè)單元。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ù)元素的存儲(chǔ)位置為：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ù)組下標(biāo)從0開始，各維長(zhǎng)度為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ù)組，本算法求所有馬鞍點(diǎn)//b是一維數(shù)組,存放一行中可能的馬鞍點(diǎn)的列值,k記相等值個(gè)數(shù)//c是一維數(shù)組，存放某列可能馬鞍點(diǎn)的行值,kk記相等值個(gè)數(shù){for(i=0;i<m;i++){min=a[i,0];//最小值初始化b[0]=0;k=1;//b數(shù)組記最小值的列號(hào)，k記最小值的個(gè)數(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個(gè)相等的最小值{j=b[jj];max=a[i][jj];kk=0;//a[i][j]是否是馬鞍點(diǎn)while(kk<m&&max>=a[i][kk])kk++;if(kk>=m)printf(“馬鞍點(diǎn)i=%d,j=%d,a[i][j]=%d”，i,j,a[i][j]);}//ENDOFforjj}//ENDOFfori最壞時(shí)間復(fù)雜度為O(m*(n+n*m)).(最壞時(shí)所有元素相同，都是馬鞍點(diǎn))解法2:若矩陣中元素值互不相同,則用一維數(shù)組row記下各行最小值，再用一維數(shù)組col記下各列最大值，相等者為馬鞍點(diǎn)。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(“馬鞍點(diǎn)i=%d,j=%d,a[i][j]=%d”，i,j,a[i][j]);時(shí)間復(fù)雜度O((m*n)).解法3:設(shè)定兩個(gè)數(shù)組：max[0..n-1]記各列的最大值所在行號(hào)min[0..m-1]記各行的最小值所在列號(hào)第j列的最大值為A[max[j]][j],第i行的最小值是A[i][min[i]]

voidsaddlepoint（inta[m][n]）;//a是m行n列的二維數(shù)組，本算法求所有馬鞍點(diǎn){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列最大值的行號(hào)if（A[i][j]<A[i][min[i]]）min[i]=j;//重新確定第i行最小值的列號(hào)}for（i=0;i<m;i++）{j=min[i];//a[i][j]是否是馬鞍點(diǎn)if（max[j]==i）printf（“馬鞍點(diǎn)A[%d][%d]=%d”，i,j,a[i][j]）;}//ENDOFforjj}時(shí)間復(fù)雜度為O（m*n+m）.5.5（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））（2）5.6算法分析：兩矩陣A和B相加的結(jié)果是一矩陣C，其元素Ci.有三種情況；(1)4=氣.(B..=0)；(2)C..=B..(A..=0)；(3)C..=A..+B..。在(3)種情況下，要看結(jié)果是否為0,c矩陣只有非零元素？ijij口Voidmatrixaddition(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表在該行無(wú)非0元素；elseif(pb==cb)cb=cb->next//B表在該行無(wú)非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;//取B表行表頭指針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>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⑴根結(jié)點(diǎn)a6.2三個(gè)結(jié)點(diǎn)的樹的形態(tài):(1)6.3設(shè)樹的結(jié)點(diǎn)數(shù)是n，貝0n=n0+n1+n2++nm+(1)設(shè)樹的分支數(shù)為B,有n=B+1n=1n1+2n2++mnm+1(2)由(1)和(2)有：n0=n2+2n3++第6章樹和二叉樹（參考答案）6.1⑴根結(jié)點(diǎn)a6.2三個(gè)結(jié)點(diǎn)的樹的形態(tài):(1)6.4ki-1(i為層數(shù))(n-2)/k+1

(n-1)*k+i+1(n-1)%k!=0;其右兄弟的編號(hào)n+16.5(1)順序存儲(chǔ)結(jié)構(gòu)1234567891011121314ABCD#EF#G####H#為空結(jié)點(diǎn)注：6.6(1)6.6⑵(3)中序DGBAECHF后序GDBEHFCA6.7(1)⑵中序DGBAECHF后序GDBEHFCA(1)⑵(3)6.8height(bitreebt)height(bitreebt)//bt是以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹，本算法求二叉樹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(根)}}//算法結(jié)束6.9voidpreorder(cbt[],intn,inti);//cbt是以完全二叉樹形式存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，i是數(shù)//組下標(biāo)，初始調(diào)用時(shí)為1。本算法以非遞歸形式前序遍歷該二叉樹{inti=1,s[],top=0;//s是棧，棧中元素是二叉樹結(jié)點(diǎn)在cbt中的序號(hào)//top是棧頂指針，棧空時(shí)top=0if(n<=0){printf(“輸入錯(cuò)誤”);exit(0)；}while(i<=n||top>0){while(i<=n){visit(cbt[i]);//訪問(wèn)根結(jié)點(diǎn)if(2*i+1<=n)s[++top]=2*i+1;//若右子樹非空，其編號(hào)進(jìn)棧i=2*i;//先序訪問(wèn)左子樹}if(top>0)i=s[top--];//退棧，先序訪問(wèn)右子樹}//ENDOFwhile(i<=n||top>0)}//算法結(jié)束〃以下是非完全二叉樹順序存儲(chǔ)時(shí)的遞歸遍歷算法，“虛結(jié)點(diǎn)”用‘"表示voidpreorder(bt[],intn,inti);//bt是以完全二叉樹形式存儲(chǔ)的一維數(shù)組，n是數(shù)組元素個(gè)數(shù)。i是數(shù)//組下標(biāo)，初始調(diào)用時(shí)為1。{if(i<=n&&bt[i]!=’*’){visit(bt[i]);preorder(bt,n,2*i);preorder(bt,n,2*i+1);}//算法結(jié)束6.10intequal(bitreeT1,bitreeT2);//T1和T2是兩棵二叉樹，本算法判斷T1和T2是否等價(jià)//T1和T2都是空二叉樹則等價(jià)//T1和T2只有一棵為空，另一棵非空，則不等價(jià)//T1和T2均非空，且根結(jié)點(diǎn)值相等，則比較其左、右子樹{if(T1==null&&T2==null)return(1);//同為空二叉樹elseif(T1==null||T2==null)return(0);//只有一棵為空elseif(T1->data!=T2->data)return(0);//根結(jié)點(diǎn)值不等elsereturn(equal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild))//判左右子樹等價(jià)}//算法結(jié)束11voidlevelorder(bitreeht);{本算法按層次遍歷二叉樹ht}{if(ht!=null){initqueue(q);{處始化隊(duì)列，隊(duì)列元素為二叉樹結(jié)點(diǎn)的指針}enqueue(q,ht);{根結(jié)點(diǎn)指針入隊(duì)列}while(!empty(q)){p=delqueue(q);visit(p);//訪問(wèn)結(jié)點(diǎn)if(p->lchild!=null)enqueue(q,p->lchild);//若左子女非空，則左子女入隊(duì)列if(p->rchild!=null)enqueue(q,p->rchild)；//若右子女非空，則右子女入隊(duì)列}}}//算法結(jié)束6.12voidpreorder(bitree*t);(前序非遞歸遍歷){bitree*s[n+1];//s是指針數(shù)組，數(shù)組中元素為二叉樹節(jié)點(diǎn)的指針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;}}}//算法結(jié)束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;}}//算法結(jié)束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;}}}//算法結(jié)束6.13bitree*dissect(bitree**t,ElemTypex)//二叉樹t至多有一個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閤,本算法拆去以x為根的子樹//拆開后的第一棵樹用t表示，成功拆開后返回第二棵二叉樹{bitree*p,*find;if(*t!=null){if((*t)->data==x)//根結(jié)點(diǎn)數(shù)據(jù)域?yàn)閤{p=*t;*t=null;return(p);}else{find=(dissect(&(*t)->lchild),x);//在左子樹中查找并拆開//若在左子樹中未找到，就到右子樹中查找并拆開if(!find)find=(dissect(&(*t)->rchild),x);return(find);}}elsereturn(null);//空二叉樹}//算法結(jié)束6.14intsearch(bitreet,ElemTypex)//設(shè)二叉樹t中，值為x的結(jié)點(diǎn)至多一個(gè)，本算法打印x的所有祖先//算法思想是，借助后序非遞歸遍歷，用棧裝遍歷過(guò)程的結(jié)點(diǎn)，當(dāng)查到//值為x的結(jié)點(diǎn)時(shí)，棧中元素都是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);//輸出，設(shè)元素為字符return(1);}elsewhile(top>0&&s[top].tag==1)top--;//退出右子樹已訪問(wèn)的結(jié)點(diǎn)if(top>0)//置訪問(wèn)標(biāo)志1，訪問(wèn)右子樹{s[top].tag=1;t=s[top].p;t=t->rchild;}}return(0);//沒(méi)有值為x的結(jié)點(diǎn)}//算法結(jié)束6.15中序序列BDCEAFHG___后序序列DECBHGFAZ'"一一、【A前序序列ABCDEFGH6.16后序線索樹：null_/.-E0A0/0B1//0C0100/0A0/0B1//0C0100/1E1/0F1/I1IH6.17bitree*search(bitree*p)//查找前序線索二叉樹上給定結(jié)點(diǎn)p的前序后繼{if(p->ltag==1)return(p->rchild)；//左標(biāo)記為1時(shí)，若p的右子樹非空，p的右子樹的根p->rchild為p的后繼；若右子樹為空，p->rchild指向后繼elsereturn(p->lchild);//左標(biāo)記為0時(shí)，p的左子女p->lchild為p的后繼.}//算法結(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);//p的左標(biāo)記為0，左子女p->lchild是后序前驅(qū)，否則，線索p->lchild指向p的后序前驅(qū)}6.196.21}27,19,2,6,32,3,21,10其對(duì)應(yīng)字母分別為a,b,c,e,f,g,h。哈夫曼編碼：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章圖(參考答案)1(1)鄰接矩陣中非零元素的個(gè)數(shù)的一半為無(wú)向圖的邊數(shù)；A[i][j]==0為頂點(diǎn)，I和j無(wú)邊，否則j和j有邊相通;任一頂點(diǎn)I的度是第I行非0元素的個(gè)數(shù)。7.2(1)任一頂點(diǎn)間均有通路，故是強(qiáng)連通；(2)簡(jiǎn)單路徑V4V3V1V2;(3)01818018180888鄰接矩陣10V1=?V4|?V2laV2?V3lAV3V1lAV3|aV4鄰接表V1?V3|aV2?V1|AV4|aV2|aV3?V4—V1lA逆鄰接表7.3(1)鄰接表從頂點(diǎn)4開始的DFS序列：V5,V3,V4,V6,V2,V1從頂點(diǎn)4開始的BFS序列：V4,V5,V3,V6,V1,V27.4(1)①adjlisttpg;vtxptri,j;//全程變量voiddfs(vtxptrx)//從頂點(diǎn)x開始深度優(yōu)先遍歷圖g。在遍歷中若發(fā)現(xiàn)頂點(diǎn)j,則說(shuō)明頂點(diǎn)i和j間有路徑。{visited[x]=1;//置訪問(wèn)標(biāo)記if(y==j){found=1;exit(0);}//有通路，退出else{p=g[x].firstarc;//找x的第一鄰接點(diǎn)while(p!=null){k=p->adjvex;if(!visited[k])dfs(k);p=p->nextarc;//下一鄰接點(diǎn)}}voidconnect_DFS(adjlisttpg)〃基于圖的深度優(yōu)先遍歷策略，本算法判斷一鄰接表為存儲(chǔ)結(jié)構(gòu)的圖g種，是否存在頂點(diǎn)i//到頂點(diǎn)j的路徑。設(shè)1<=i,j<=n,i<>j.(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,”無(wú)路徑”)；}//voidconnect_DFS(2)寬度優(yōu)先遍歷全程變量，調(diào)用函數(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;//第一鄰接點(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)按增序排列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簡(jiǎn)單回路指起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑。算法基本思想是利用圖的遍歷，以頂點(diǎn)VK開始，若遍歷中再通到VK,則存在簡(jiǎn)單回路，否則不存在簡(jiǎn)單回路。Adjlisttpg;visited[1..n]=0;Intfound=0;//全程變量Intdfs(btxptrx)〃從k頂點(diǎn)深度優(yōu)先遍歷圖g，看是否存在k的簡(jiǎn)單回路{visited[x]=1;p=g[x].firstarc;while(p!=null){w=p->adjvex;if(w==k){found=1;exit(0);}//有簡(jiǎn)單回路，退出if(!visited[k])dfs(w);p=p->nextarc;}//while(p!=null)}//dfs(2)KRUSKAL算法的最小生成樹(權(quán)值相同的邊選取無(wú)順序)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}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}{}注：選定點(diǎn)4和5時(shí)無(wú)優(yōu)先順序，二者最短路徑均為297.9Z0881200:1->1A0=308path0=1201:1->2I5201238：1到3沒(méi)有直接通路Z088path1同path0,加入頂點(diǎn)1后無(wú)變化A1=308520K488^A2=308path2同path1k28/088A3=308本題不好，終態(tài)和初態(tài)無(wú)變化

,V2,V3,共七種用TOPOSORT算法求得第七種，用鄰接表存儲(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在棧頂。,V2,V3,7.11voidtoposort_dfs(graphg；vtptrv)〃從頂點(diǎn)v開始，利用深度優(yōu)先遍歷對(duì)圖g進(jìn)行拓?fù)渑判颉?/基本思想是利用棧s存放頂點(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ù)渑判虿荒茼樌瓿伞?；elseprintf(“拓?fù)渑判虺晒?，輸出的是一個(gè)逆拓?fù)湫蛄?\n”)；}7.12

V100a1000V259a2594V366a3000V41212a4660V51516a56137V61620a612131V71717a712124V81920a815160V92222a912164V102424a1015161a1117170a1216204a1319201a1422220關(guān)鍵路徑V1->V3->V4->V7->V9->V10長(zhǎng)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長(zhǎng)22關(guān)鍵活動(dòng)a3,a4,a7,a11,a14第八章排序（參考答案）本章所用數(shù)據(jù)結(jié)構(gòu)#defineN待排序記錄的個(gè)數(shù)typedefstruct{intkey;ElemTypeother;}rectype;rectyper[n+1];//r為結(jié)構(gòu)體數(shù)組8.2穩(wěn)定排序有：直接插入排序、起泡排序、歸并排序、基數(shù)排序不穩(wěn)定排序有：希爾排序、直接選擇排序、堆排序希爾排序例：49，38,_49，90，70，25直接選擇排序例：2，2，1堆排序例：1，2，28.3voidStlinkedInsertSort(s,n);//對(duì)靜態(tài)鏈表s[1..n]進(jìn)行表插入排序，并調(diào)整結(jié)果，使表物理上排序{#defineMAXINT機(jī)器最大整數(shù)typedefstruct{intkey;intnext;}rec;recs[n+1];//s為結(jié)構(gòu)體數(shù)組s[0].key=maxint;s[1].next=0;//頭結(jié)點(diǎn)和第一個(gè)記錄組成循環(huán)鏈表i=2;〃從第2個(gè)元素開始，依次插入有序鏈表中while(i<=n){q=0;p=s[0].next;//p指向當(dāng)前最小元素，q是p的前驅(qū)while(p!=0&&s[p].key<s[i].key)//查找插入位置{q=p;p=s[p].next;}s[i].next=p;s[q].next=i;//將第個(gè)元素鏈入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++;}}}//算法結(jié)束8.4voidTwoWayBubbleSort(rectyper[n+1];intn)//對(duì)r[1..n]進(jìn)行雙向冒泡排序。即相鄰兩遍向兩個(gè)相反方向起泡{inti=1,exchange=1;//設(shè)標(biāo)記while(exchange){exchange=0;//假定本趟無(wú)交換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}//算法結(jié)束8.5在n=7時(shí)，最好情況下進(jìn)行10次比較。6次比較完成第一趟快速排序，將序列分成相等程度的序列(各3個(gè)元素)，再各進(jìn)行2次比較，完成全部排序。最好的初始排列：4，1，3，2，6,5，78.6voidQuickSort(rectyper[n+1];intn)//對(duì)r[1..n]進(jì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;}}}//算法結(jié)束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);}//一次劃分算法結(jié)束8.7voidQuickSort(rectyper[n+1];intn)//對(duì)r[1..n]進(jìn)行快速排序的非遞歸算法對(duì)8.6算法的改進(jìn){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)//左部子序列長(zhǎng)度大于右部，左部進(jìn)棧{top++;s[top].low=ss;s[top].high=k-1;}if(tt-k>1)ss=k+1;//右部短的直接處理elseflag=false;//右部處理完，需退棧}elseif(tt-k>1)//右部子序列長(zhǎng)度大于左部，右部進(jìn)棧{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)}//算法結(jié)束intquickpass(rectyper[];ints,t)//用“三者取中法”對(duì)8.6進(jìn)行改進(jìn){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次移動(dòng)；最差3次比較10次移動(dòng)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);}//一次劃分算法結(jié)束8.8viodsearchjrec(rectyper[]，intj)//在無(wú)序記錄r[n]中，找到第j(0<=j<n)個(gè)記錄。算法利用快速排序思想，找到第一〃軸元素的位置i，若i=j則查找結(jié)束。否則根據(jù)j<i或j>i在0?i、1或i+1?n+1之間查〃找，直到/i習(xí)為止。(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é)束8.9viodrearrange(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)8.9voidarrange(rectyper[n+1];intn)//對(duì)r[1..n]進(jìn)行整理，使關(guān)鍵字為負(fù)值的記錄排在非負(fù)值的記錄之前[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];//將關(guān)鍵字取負(fù)值的記錄放到前面while(i<j&&r[i].key<0)i++;if(i<j){r[j--]=r[i];//將關(guān)鍵字取非負(fù)值的記錄放到后面}r[i]=rp;//}〃算法結(jié)束〃本算法并未判斷軸樞的關(guān)鍵字的正負(fù)，在排序中并未和軸樞〃記錄比較，而是按正負(fù)區(qū)分，提高了效率8.10typedefstructnode{ElemTypedata;structnode*next;}linklist;voidsimpleselect(linklist*head)//head是單鏈表的頭指針，本算法對(duì)其進(jìn)行直接選擇排序。設(shè)p指向無(wú)序區(qū)第一個(gè)記錄(開始是鏈表的第一個(gè)記錄)，用q指向一趟排序中的最小記錄，為簡(jiǎn)便起見(jiàn)，將P和q所指結(jié)點(diǎn)的數(shù)據(jù)交換。{p=head->next;while(p->next!=null)//剩最后一個(gè)元素時(shí)，排序結(jié)束{q=p;//設(shè)當(dāng)前結(jié)點(diǎn)為最小s=p->next;//s指向待比較結(jié)點(diǎn)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;//鏈表指針后移，指向下一個(gè)最小值結(jié)點(diǎn)}}〃算法結(jié)束8.11按極小化堆取調(diào)整(若已是極大化堆則維持不變)(1)(2)(以T口為根的子樹不符合根定義)(3)(4)(以T口為根的子樹不符合根定義)(4)8.11voidheapadjust(K[],n)〃待排序元素在向量K中，從K1到Kn已是堆，現(xiàn)將第n+1個(gè)元素加入，本算法這n+1個(gè)元素調(diào)整成堆。{rp=K[n+1];x=K[n+1].key;//用rp暫存第n+1個(gè)元素，x為其關(guān)鍵字intc=n+1,f=c/2;//設(shè)c表示第n+1個(gè)元素的下標(biāo)，f是其雙親的下標(biāo)，本算法將子女與雙親比較，若符合堆的定義，則排序結(jié)束；否則將雙親和子女交換。之后，雙親的下標(biāo)為新的子女，再與新的雙親比較，直至根結(jié)點(diǎn)(無(wú)雙親)while(f>0)if(K[f].key<=x)break;//已符合堆的定義，排序結(jié)束else{K[c]=k[f];c=f;f=c/2;}//僅將雙親移至子女K[c]=rp;//將暫存記錄rp(原第n+1個(gè)記錄)放入合適位置}//算法結(jié)束//利用上述排序思想，從空堆開始，一個(gè)一個(gè)添加元素的建堆算法如下：voidheapbuilder(rectypeR[])//向量R的第1到第n個(gè)元素為待排序元素，本算法將這n個(gè)元素建成堆。{for(i=0;i<n;i++)heapadjust(R，i);}〃算法結(jié)束8.13voidsort(rectyper[],intn)//對(duì)具有n個(gè)元素的數(shù)組進(jìn)排序。算法思想是先對(duì)數(shù)組掃描一遍，形成若干最大有序子〃列，再兩兩歸并，最后完成排序。各子序列的長(zhǎng)度(上界和下界)存儲(chǔ)在循環(huán)隊(duì)列中，〃隊(duì)頭指針指向隊(duì)頭元素的前一位置，隊(duì)尾指針指向隊(duì)尾元素。#definem100//子隊(duì)列長(zhǎng)度(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è)有序子序列(即|rear-front=1|)時(shí)，合并結(jié)束。while((front+1)%m!=rear)(newrear=rear;while((front+1)%m!=rear)//從r合并到r1中合并{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有序，并拷貝到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);//對(duì)r[0..n-1]進(jìn)行計(jì)數(shù)排序{intc[n]={0};//c數(shù)組初始化，元素值指其在r中的位置。如c[i]=j,(0<=i,j<n)//則意味著r[i]應(yīng)在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個(gè)元素;否則，需要調(diào)整{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個(gè)記錄//while(c[i]!=i)8.15#defineD10//假設(shè)每個(gè)關(guān)鍵字長(zhǎng)度為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]值相同。巾]和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)//