1、第二章 線性表(參考答案) 2.1 頭指針：指向鏈表的指針。因為對鏈表的所有操均需從頭指針開始，即頭指針具有標識鏈表的作用，所以鏈表的名字往往用頭指針來標識。如：鏈表的頭指針是la，往往簡稱為“鏈表la”。頭結點：為了鏈表操作統一，在鏈表第一元素結點（稱為首元結點，或首結點）之前增加的一個結點，該結點稱為頭結點，其數據域不無實際意義（當然，也可以存儲鏈表長度，這只是副產品），其指針域指向頭結點。這樣在插入和刪除中頭結點不變。開始結點：即上面所講第一個元素的結點。2.2 只設尾指針的單循環鏈表，從尾指針出發能訪問鏈表上的任何結點。2·3 設線性表存放在向量A的前elenum個

2、分量中，且遞增有序。協議算法將X插入適當位置、void insert(ElemType A,int elenum,ElemType x)/ 向量A目前有elenum個元素，且遞增有序，本算法將x插入到向量A中，并保持向量的遞增有序。 int i=0,j; while (i<elenum && Ai<=x) i+; / 查找插入位置 for (j= elenum-1;j>=i;j-) Aj+1=Aj;/ 向后移動元素 Ai=x; / 插入元素 / 算法結束 2·4 void rightrotate(ElemType A,int n,k)/ 以

3、向量作存儲結構，本算法將向量中的n個元素循環右移k位，且只用一個輔助空間。 int num=0; / 計數，最終應等于n int start=0; / 記錄開始位置（下標） while (num<n) temp=Astart; /暫存起點元素值，temp與向量中元素類型相同 empty=start; /保存空位置下標 next=(start-K+n) %n; / 計算下一右移元素的下標 while (next !=start) Aempty=Anext;/ 右移 num+; / 右移元素數加1 empty=next; next=(next-K+n) %n; / 計算新右移元素的下標 Ae

4、mpty=temp; / 把一輪右移中最后一個元素放到合適位置num+;start+; / 起點增1，若num<n則開始下一輪右移。 / 算法結束 2·5void insert(linklist *L,ElemType x)/ 帶頭結點的單鏈表L遞增有序，本算法將x插入到鏈表中，并保持鏈表的遞增有序。 linklist *p=L->next, *pre=L，*s;/ p為工作指針，指向當前元素，pre為前驅指針，指向當前元素的前驅 s=(linklist *)malloc(sizeof(linklist);/申請空間，不判斷溢出s->data=x;while (p

5、&& p->data<=x) pre=p; p=p->next; / 查找插入位置 pre->next=s; s->next=p; / 插入元素 / 算法結束  2·6void invert(linklist *L)/ 本算法將帶頭結點的單鏈表L逆置。 /算法思想是先將頭結點從表上摘下，然后從第一個元素結點開始，依次前插入以L為頭結點的鏈表中。 linklist *p=L->next,*s;/ p為工作指針，指向當前元素，s為p的后繼指針 L->next=null;/頭結點摘下，指針域置空。算法中頭指針L始終不變 w

6、hile (p)s=p->next; / 保留后繼結點的指針 p->next=L->next; / 逆置 L->next=p; p=s; / 將p指向下個待逆置結點 / 算法結束  2·7(1) int length1(linklist *L)/ 本算法計算帶頭結點的單鏈表L的長度 linklist *p=L->next; int i=0;/ p為工作指針，指向當前元素，i 表示鏈表的長度 while (p) i+; p=p->next; return(i); / 算法結束(2) int length1(node saMAXSIZE)/

7、本算法計算靜態鏈表s中元素的個數。 int p=sa0.next, i=0;/ p為工作指針，指向當前元素，i 表示元素的個數，靜態鏈指針等于-1時鏈表結束while (p！=-1) i+; p=sap.next; return(i); / 算法結束  2·8void union_invert(linklist *A,*B,*C)/ A和B是兩個帶頭結點的遞增有序的單鏈表，本算法將兩表合并成 / 一個帶頭結點的遞減有序單鏈表C，利用原表空間。 linklist *pa=A->next,*pb=B->next,*C=A,*r;/ pa,pb為工作指針，分別指向A表

8、和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表中元素合

9、并且逆置 r=pb->next; / 保留后繼結點的指針 pb->next=C->next; / 逆置 C->next=pb; pb=r; / 恢復待逆置結點的指針 / 以下while (pa)和while (pb)語句，只執行一個 while (pa) / 將A表中剩余元素逆置 r=pa->next; / 保留后繼結點的指針 pa->next=C->next; / 逆置 C->next=pa; pa=r; / 恢復待逆置結點的指針 while (pb) / 將B表中剩余元素逆置 r=pb->next; / 保留后繼結點的指針 pb->

10、;next=C->next; / 逆置 C->next=pb; pb=r; / 恢復待逆置結點的指針 free(B);/釋放B表頭結點 / 算法結束  2·9 void deleteprior(linklist *L)/ 長度大于1的單循環鏈表，既無頭結點，也無頭指針，本算法刪除*s 的前驅結點 linklist *p=s->next,*pre=s; / p為工作指針，指向當前元素，/ pre為前驅指針，指向當前元素*p的前驅 while (p->next!=s) pre=p; p=p->next; / 查找*s的前驅 pre->next

11、=s;free(p); / 刪除元素 / 算法結束  2·10void one_to_three(linklist *A,*B,*C)/ A是帶頭結點的的單鏈表，其數據元素是字符字母、字符、數字字符、其他字符。本算法/將A表分成 / 三個帶頭結點的循環單鏈表A、B和C，分別含有字母、數字和其它符號的同一類字符，利用原表空間。 linklist *p=A->next,r;/ p為工作指針，指向A表的當前元素，r為當前元素的后繼指針,使表避免斷開。 /算法思想是取出當前元素，根據是字母、數字或其它符號，分別插入相應表中。 B=(linklist *)malloc(size

12、of(linklist);/申請空間，不判斷溢出B->next=null; / 準備循環鏈表的頭結點 C=(linklist *)malloc(sizeof(linklist);/申請空間，不判斷溢出C->next=null; / 準備循環鏈表的頭結點 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; / 將字

13、母字符插入A表 else if (p->data>=0&&p->data<=9)p->next=B->next; B->next=p; / 將數字字符插入B 表 else p->next=C->next; C->next=p;/ 將其它符號插入C 表 p=r; / 恢復后繼結點的指針 /while / 算法結束 2·11void locate(dlinklist *L)/ L是帶頭結點的按訪問頻度遞減的雙向鏈表，本算法先查找數據x,/ 查找成功時結點的訪問頻度域增1，最后將該結點按頻度遞減插入鏈表中適當位置。

14、 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結點的插入位置

15、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.1設有編號分別為1,2,3,4的4輛列車,順序進入一個棧式結構的站臺.試寫出這4輛車開出站臺的所有可能的順序.至少14種全進再情況1種：4321進3再情況3種3,4,2,1 3,2,4,1 3,2,1,4進2再情況5種2,4,3,1 2,3,4,1 2,1, 3,4

16、 2,1,4,3 2,1,3,4進1再情況5種1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33.3 void sympthy(linklist *head, stack *s)/判斷長為n的字符串是否中心對稱 int i=1; linklist *p=head->next;while (i<=n/2) / 前一半字符進棧 push(s,p->data); p=p->next; if (n % 2 !=0) p=p->next;/ 奇數個結點時跳過中心結點 while (p && p->data=pop(s)

17、p=p->next;if (p=null) printf(“鏈表中心對稱”)；else printf(“鏈表不是中心對稱”)； / 算法結束 3.4int match()/從鍵盤讀入算術表達式，本算法判斷圓括號是否正確配對（init s;/初始化棧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(“括號不配對”); else

18、 printf(“括號配對”); / 算法結束  3.5typedef struct / 兩棧共享一向量空間 ElemType vm; / 棧可用空間0m-1 int top2 / 棧頂指針twostack; int push(twostack *s,int i, ElemType x)/ 兩棧共享向量空間,i是0或1，表示兩個棧，x是進棧元素，/ 本算法是入棧操作 if (abs(s->top0 - s->top1)=1) return(0);/ 棧滿 else switch (i)case 0: s->v+(s->top)=x; break;ca

19、se 1: s->v-(s->top)=x; break;default: printf(“棧編號輸入錯誤”); return(0);return(1); / 入棧成功 / 算法結束 ElemType pop(twostack *s,int i)/ 兩棧共享向量空間,i是0或1，表示兩個棧，本算法是退棧操作 ElemType x;if (i!=0 && i!=1) return(0);/ 棧編號錯誤 else switch (i)case 0: if(s->top0=-1) return(0);/棧空else x=s->vs->top-;break

20、;case 1: if(s->top1=m) return(0);/棧空else x=s->vs->top+; break;default: printf(“棧編號輸入錯誤”);return(0);return(x); / 退棧成功 / 算法結束  ElemType top (twostack *s,int i)/ 兩棧共享向量空間,i是0或1，表示兩個棧，本算法是取棧頂元素操作 ElemType x;switch (i)case 0: if(s->top0=-1) return(0);/棧空else x=s->vs->top; break;cas

21、e 1: if(s->top1=m) return(0);/棧空else x=s->vs->top; break;default: printf(“棧編號輸入錯誤”);return(0);return(x); / 取棧頂元素成功 / 算法結束  36void Ackerman(int m,int n)/ Ackerman 函數的遞歸算法 if (m=0) return(n+1);else if (m!=0 && n=0) return(Ackerman(m-1,1);else return(Ackerman(m-1,Ackerman(m,n-1) /

22、 算法結束  37(1) linklist *init(linklist *q)/ q是以帶頭結點的循環鏈表表示的隊列的尾指針，本算法將隊列置空 q=(linklist *)malloc(sizeof(linklist);/申請空間，不判斷空間溢出q->next=q;return (q); / 算法結束 (2) linklist *enqueue(linklist *q，ElemType x)/ q是以帶頭結點的循環鏈表表示的隊列的尾指針，本算法將元素x入隊 s=(linklist *)malloc(sizeof(linklist);/申請空間，不判斷空間溢出s->nex

23、t=q->next; / 將元素結點s入隊列 q->next=s;q=s; / 修改隊尾指針 return (q); / 算法結束 (3) linklist *delqueue(linklist *q)/q是以帶頭結點的循環鏈表表示的隊列的尾指針，這是出隊算法 if (q=q->next) return (null); / 判斷隊列是否為空 else linklist *s=q->next->next; / s指向出隊元素 if (s=q) q=q->next; / 若隊列中只一個元素，置空隊列else q->next->next=s->n

24、ext;/ 修改隊頭元素指針 free (s); / 釋放出隊結點 return (q); / 算法結束。算法并未返回出隊元素  3.8 typedef structElemType datam;/ 循環隊列占m個存儲單元 int front,rear; / front和rear為隊頭元素和隊尾元素的指針 / 約定front指向隊頭元素的前一位置，rear指向隊尾元素 sequeue; int queuelength(sequeue *cq)/ cq為循環隊列，本算法計算其長度 return (cq->rear - cq->front + m) % m; / 算法結束 &

25、#160;3.9 typedef structElemType sequm;/ 循環隊列占m個存儲單元 int rear,quelen; / rear指向隊尾元素,quelen為元素個數sequeue;(1) int empty(sequeue *cq)/ cq為循環隊列，本算法判斷隊列是否為空 return (cq->quelen=0 ? 1: 0); / 算法結束 (2) sequeue *enqueue(sequeue *cq，ElemType x)/ cq是如上定義的循環隊列，本算法將元素x入隊if (cq->quelen=m) return(0); / 隊滿 else c

26、q->rear=(cq->rear+1) % m; / 計算插入元素位置 cq->sequcq->rear=x; / 將元素x入隊列 cq->quelen+; / 修改隊列長度 return (cq); / 算法結束 ElemType delqueue(sequeue *cq)/ cq是以如上定義的循環隊列，本算法是出隊算法，且返回出隊元素 if (cq->quelen=0) return(0); / 隊空 else int front=(cq->rear - cq->quelen + 1+m) % m;/ 出隊元素位置 cq->quele

27、n-; / 修改隊列長度 return (cq->sequfront); / 返回隊頭元素 / 算法結束第四章 串 (參考答案) 4.2 用串的去其他運算構成子串的定位運算index。 int index(string s,t)/s,t是字符串，本算法求子串t在主串s中的第一次出現，若s串中包含t串，返回其/第一個字符在s中的位置，否則返回0m=length(s); n=length(t);i=1;while(i<=m-n+1)if(strcmp(substr(s,i,n),t)=0) break;else i+;if(i<=m-n+1) return(i);/模式

28、匹配成功else return(0);/s串中無子串t/算法index結束4.4 將S=“（xyz）*”轉為T=“（x+z）*y”S=concat(S, substr(S,3,1) / ”(xyz)*y”S=replace(S,3,1,”+”) / ”(x+z)*y” 4.5 char search(linkstring *X, linkstring *Y)/ X和Y是用帶頭結點的結點大小為1的單鏈表表示的串，本算法查找X中 第一個不在Y中出現的字符。算法思想是先從X中取出一個字符，到Y中去查找，如找到，則在X中取下一字符，重復以上過程；若沒找到，則該字符為所求  link

29、string *p, *q,*pre; / p,q為工作指針，pre控制循環 p=X->next; q=Y->next; pre=p;while (p && q) ch=p->data; / 取X中的字符 while (q && q->data!=ch) q=q->next; / 和Y中字符比較 if (!q) return(ch); / 找到Y中沒有的字符 else pre=p->next; / 上一字符在Y中存在，p=pre; / 取X中下一字符。 q=Y->next; / 再從Y的第一個字符開始比較return(n

30、ull); / X中字符在Y中均存在 / 算法結束  4.6 是設計一算法，在順序串上實現串的比較運算 strcmp(s,t)int strcmp(seqstring *S, seqstring *T)/ S和T是指向兩個順序串的指針，本算法比較兩個串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否則返回-1 int i=0;while (s->chi!=0 && t->chi!=0)if (s->chi>t->chi) return(1);else if (s->chi<t->chi) return(-1);

31、else i+; / 比較下一字符 if (s->chi!=0&& t->chi=0) return(1);else if (s->chi=0&& t->chi!=0) return(-1);else return(0);/ 算法結束4.7 linkstring *invert(linkstring *S, linkstring *T)/ S和T是用帶頭結點的結點大小為1的單鏈表表示的串，S是主串，T是/ 模式串。本算法是先模式匹配，查找T在S中的第一次出現。如模式匹/ 配成功，則將S中的子串（T串）逆置。linkstring *pre,

32、*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); /

33、 匹配失敗，沒有逆置 else / 以下是T串逆置 tp=pre->next; / tp是逆置的工作指針，現在指向待逆置的第一個字符pre->next=sp; / 將S中與T串匹配時的前驅指向匹配后的后繼 while (tp!=sp) r=tp->next;tp->next=pre->next;pre->next=tp;tp=r/ 算法結束 第五章 多維數組和廣義表（參考答案）5.1 A2323A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A

34、0112 A0200 , A0201 , A0202 A0210 , A0211 , A0212 將第一維的0變為1后，可列出另外18個元素。以行序為主（即行優先）時，先改變右邊的下標，從右到左進行。5.2 設各維上下號為c1d1，c2d2，c3d3，每個元素占l個單元。LOC(aijk)=LOC(ac1c2c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)*l推廣到n維數組！（下界和上界）為（ci，di），其中1<=i<=n.則：其數據元素的存儲位置為：LOC（aj1j2.jn）=LOC（ac1c2cn）+（d2-c2+1

35、） （dn-cn+1）(j1-c1)+(d3-c3+1) （dn-cn+1）n(j2-c2)+(dn-cn+1)(jn-1-cn-1)+(jn-cn)*l=LOC(ac1c2c3)+ i(ji-ci) i=1n其中i（dk-ck+1）（1<=i<=n）k=i+15.7 (1) head(p,h,w)=p(2) tail(b,k,p,h)=(k,p,h)(3) head(a,b),(c,d)=(a,b)(4) tail(a,b),(c,d)=(c,d)(5) head(tail(a,b),(c,d)=(c,d)(6) tail(head(a,b),(c,d)=(b)第6章 樹和二叉樹

36、（參考答案）6.8int height(bitree bt)/ bt鏈表為存儲結構的是以二叉二叉樹，本算法求二叉樹bt的高度 int bl,br; / 局部變量，分別表示二叉樹左、右子樹的高度 if (bt=null) return(0);else bl=height(bt->lchild);br=height(bt->rchild);return(bl>br? bl+1: br+1); / 左右子樹高度的大者加1（根） / 算法結束 6.227,19,2,6,32,3,21,10其對應字母分別為a,b,c,e,f,g,h。哈夫曼編碼：a：0010b：10c：00000d：0

37、001e：01f：00001g：11h：0011第七章 圖（參考答案）71（1）鄰接矩陣中非零元素的個數的一半為無向圖的邊數；（2）Aij= =0為頂點，I 和j無邊，否則j和j有邊相通；（3）任一頂點I的度是第I行非0元素的個數。73（1）鄰接表（2）從頂點4開始的DFS序列：V5,V3,V4,V6,V2,V1（3）從頂點4開始的BFS序列：V4,V5,V3,V6,V1,V276簡單回路指起點和終點相同的簡單路徑。算法基本思想是利用圖的遍歷，以頂點VK開始，若遍歷中再通到VK，則存在簡單回路，否則不存在簡單回路。Adjlisttp g ; visited1.n=0;Int found =0;

38、/全程變量Int dfs(btxptr x)/從k頂點深度優先遍歷圖g，看是否存在k的簡單回路 visitedx=1;p=gx.firstarc;while(p!=null) w=p->adjvex;if(w= =k) found=1;exit(0);/有簡單回路，退出if (!visitedk ) dfs(w );p=p->nextarc;/while(p!=null)/ dfs711void toposort_dfs （graph g；vtptr v）/從頂點v開始，利用深度優先遍歷對圖g進行拓撲排序。/基本思想是利用棧s存放頂點，首先出棧的頂點是出度為0的頂點，是拓撲序列中最

39、后一個頂/點。若出棧元素個數等于頂點數，則拓撲排序成功，輸出的是逆拓撲排序序列。 visited1.n=0;top=0;num=0;/初始化；top為棧頂指針，num記出棧元素數s+top=v;/頂點入棧while (top!=0) w=firstadj(g,v);/求頂點v的第一鄰接點while (w！=0) / w!=0的含義是w存在 if ( !visitedw) s+top=w;w=nextadj(g,v,w);/求下一個鄰接點if (top!=0) v=stop-; num+; printf(v);/輸出頂點printf(“n”);if (num<n) printf(“ 從”,

40、”v”,”頂點開始拓撲排序不能順利完成 ”)；else printf(“拓撲排序成功，輸出的是一個逆拓撲序列.n”);第八章 排序（參考答案）8.4void TwoWayBubbleSort( rectype rn+1; int n)/ 對r1.n進行雙向冒泡排序。即相鄰兩遍向兩個相反方向起泡 int i=1, exchange=1; / 設標記 while (exchange) exchange=0; / 假定本趟無交換 for (j=n-i+1 j>=i+1;j-) / 向前起泡，一趟有一最小冒出 if (rj<rj-1) rjß>rj-1; exchange=

41、1; / 有交換 for (j= i+1;j>=n-I;j+) / 向后起泡，一趟有一最大沉底 if (rj>rj+1) rjß>rj+1; exchange=1; / 有交換 i+; / end of WHILE exchange /算法結束 8.6void QuickSort(rectype rn+1; int n)/ 對r1.n進行快速排序的非遞歸算法 typedef struct int low,high; nodenode sn+1；int top;int quickpass(rectype r,int,int); / 函數聲明 top=1; stop.l

42、ow=1; stop.high=n;while (top>0)ss=stop.low; tt=stop.high; top-;if (ss<tt) k=quickpass(r,ss,tt);if (k-ss>1) top+; stop.low=ss; stop.high=k-1;if (tt-k>1) top+; stop.low=k+1; stop.high=tt; / 算法結束 int quickpass(rectype r;int s,t)i=s; j=t; rp=ri; x=ri.key;while （i<j）while (i<j &&

43、; x<=rj.key) j-;if (i<j) ri+=rj; while (i<j && x>=rj.key) i+;if (i<j) rj-=ri;ri=rp; return (i); / 一次劃分算法結束 8.7void QuickSort(rectype rn+1; int n)/ 對r1.n進行快速排序的非遞歸算法 對8.6算法的改進 typedef struct int low,high; nodenode sn+1；int top;int quickpass(rectype r,int,int); / 函數聲明 top=1; sto

44、p.low=1; stop.high=n;ss=stop.low; tt=stop.high; top-; flag=true;while (flag | top>0)k=quickpass(r,ss,tt);if (k-ss>tt-k) / 一趟排序后分割成左右兩部分 if (k-ss>1) / 左部子序列長度大于右部，左部進棧 top+; stop.low=ss; stop.high=k-1; if (tt-k>1) ss=k+1; / 右部短的直接處理 else flag=false; / 右部處理完，需退棧 else if (tt-k>1) /右部子序列長

45、度大于左部，右部進棧 top=top+1; stop.low=k+1; stop.high=tt; if (k-ss>1) tt=k-1 / 左部短的直接處理 else flag=false / 左部處理完，需退棧 if (!flag && top>0)ss=stop.low; tt=stop.high; top-; flag=true; / end of while (flag | top>0) / 算法結束 int quickpass(rectype r;int s,t)/ 用“三者取中法”對8.6進行改進 int i=s, j=t, mid=(s+t)/

46、2; rectype tmp;if (ri.key>rmid.key) tmp=ri;ri=rmid;rmid=tmp if (rmid.key>rj.key)tmp=rj;rj=rmid;if (tmp>ri) rmid=tmp; else rmid=ri;ri=tmp tmp=ri;ri=rmid;rmid=tmp / 三者取中：最佳2次比較3次移動；最差3次比較10次移動 rp=ri; x=ri.key;while （i<j）while (i<j && x<=rj.key) j-;if (i<j) ri+=rj; while (i

47、<j && x>=rj.key) i+;if (i<j) rj-=ri;ri=rp; return (i); / 一次劃分算法結束 8.8viod searchjrec（rectype r，int j）/在無序記錄rn中，找到第j（0<=j<n）個記錄。算法利用快速排序思想，找到第一/軸元素的位置i，若i=j則查找結束。否則根據j<i或j>i在0i、1或i+1n+1之間查/找，直到/i=j為止。 int quichpass (rectype r,int,int) / 函數聲明i=quichpass(r,0,n-1); / 查找樞軸位置w

48、hilehile(i!=j)if (j<i) i=quichpass(r,0.i-1);else i=quichpass(r,i+1.n-1);/ searchjrec算法結束8.9viod rearrange (rectype r,int n)/本算法重排具有n個元素的數r，使取負值的關鍵字放到取非負值的關鍵字之前。 int i=0,j=n-1; rp=r0;while(i<j)while(i<j&&rj.key>=0) j-;if(i<j) ri+=rj;/取負值關鍵字記錄放到左面while(i<j&&ri.key<

49、0) i+;if(i<j) rj-=ri/ 取非負值關鍵字記錄放到右面/while(i<j)8.9void arrange(rectype rn+1; int n)/ 對r1.n進行整理，使關鍵字為負值的記錄排在非負值的記錄之前 int i=0, j=-1;rp=r0; while (i<j) while (i<j && rj.key>=0) j-;if (i<j) ri+=rj; /將關鍵字取負值的記錄放到前面while (i<j && ri.key<0) i+;if (i<j) rj-=ri;/將關鍵字取

50、非負值的記錄放到后面ri=rp;/算法結束 /本算法并未判斷軸樞的關鍵字的正負，在排序中并未和軸樞/記錄比較，而是按正負區分，提高了效率 8.10typedef struct nodeElemTypedata;struct node *next;linklist;void simpleselect(linklist *head)/head是單鏈表的頭指針，本算法對其進行直接選擇排序。設p指向無序區第一個記錄（開始是鏈表的第一個記錄），用q指向一趟排序中的最小記錄，為簡便起見，將p和q所指結點的數據交換。p=head->next;while (p->next!=null) / 剩最后

51、一個元素時，排序結束 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.14 void CountSort(rectype r; int n);/ 對r0.n-1進行計數排序 i

52、nt cn = 0;/ c數組初始化，元素值指其在r中的位置。如ci=j,(0<=i,j<n)/ 則意味著ri 應在r的第 j 位置上。for (i=0;i<n;i+) / 一趟掃描比較選出大小，給數組 c 賦值for (j=i+1;j<n;j+)if (ri>rj) ci=ci+1else cj=cj+1;for (i=0;i<n;i+)while (ci!=i) /若ci = i，則ri 正好是第i個元素;否則，需要調整 k=ci;temp=rk; rk=ri; ri=temp; / rk和ri交換ci=ck; / 將ck存入ci,ck=k; / rk已是第k個記錄/ while (ci!=i)第九章 查找（參考答案）9.1 int seqsearch( rectype r, keytype k)/ 監視哨設在n個元素的升序順序表低下標端，順序查找關鍵字為k的數據/ 元素。若存在，則返回其在順序表中的位置，否則，返回0 r0.key=k; i=n; while (ri.key>k) i-;if (i>0 && ri.key=k) ret