唐策善數(shù)據(jù)結(jié)構(gòu)答案-用C語(yǔ)言描述原版

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第二章 線性表(參考答案) 2.1 頭指針：指向鏈表的指針。因?yàn)閷?duì)鏈表的所有操均需從頭指針開(kāi)始，即頭指針具有標(biāo)識(shí)鏈表的作用，所以鏈表的名字往往用頭指針來(lái)標(biāo)識(shí)。如：鏈表的頭指針是la，往往簡(jiǎn)稱(chēng)為“鏈表la”。頭結(jié)點(diǎn)：為了鏈表操作統(tǒng)一，在鏈表第一元素結(jié)點(diǎn)（稱(chēng)為首元結(jié)點(diǎn)，或首結(jié)點(diǎn)）之前增加的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)稱(chēng)為頭結(jié)點(diǎn)，其數(shù)據(jù)域不無(wú)實(shí)際意義（當(dāng)然，也可以存儲(chǔ)鏈表長(zhǎng)度，這只是副產(chǎn)品），其指針域指向頭結(jié)點(diǎn)。這樣在插入和刪除中頭結(jié)點(diǎn)不變。開(kāi)始結(jié)點(diǎn)：即上面所講第一個(gè)元素的結(jié)點(diǎn)。2.2 只設(shè)尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問(wèn)鏈表上的任何結(jié)點(diǎn)。2·3 設(shè)線性表存放

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

3、A,int n,k)/ 以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的n個(gè)元素循環(huán)右移k位，且只用一個(gè)輔助空間。 int num=0; / 計(jì)數(shù)，最終應(yīng)等于n int start=0; / 記錄開(kāi)始位置（下標(biāo)） while (num<n) temp=Astart; /暫存起點(diǎn)元素值，temp與向量中元素類(lèi)型相同 empty=start; /保存空位置下標(biāo) next=(start-K+n) %n; / 計(jì)算下一右移元素的下標(biāo) while (next !=start) Aempty=Anext;/ 右移 num+; / 右移元素?cái)?shù)加1 empty=next; next=(next-K+n) %n; /

4、計(jì)算新右移元素的下標(biāo) Aempty=temp; / 把一輪右移中最后一個(gè)元素放到合適位置num+;start+; / 起點(diǎn)增1，若num<n則開(kāi)始下一輪右移。 / 算法結(jié)束 2·5void insert(linklist *L,ElemType x)/ 帶頭結(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->dat

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

6、算法中頭指針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·7(1) int length1(linklist *L)/ 本算法計(jì)算帶頭結(jié)點(diǎn)的單鏈表L的長(zhǎng)度 linklist *p=L->next; int i=0;/ p為工作指針，指向當(dāng)前元素，i 表示鏈表的長(zhǎng)度 while (p) i+; p=p->next; return(i); / 算法結(jié)束(2) int length1(node

7、 saMAXSIZE)/ 本算法計(jì)算靜態(tài)鏈表s中元素的個(gè)數(shù)。 int p=sa0.next, i=0;/ p為工作指針，指向當(dāng)前元素，i 表示元素的個(gè)數(shù)，靜態(tài)鏈指針等于-1時(shí)鏈表結(jié)束while (p！=-1) i+; p=sap.next; return(i); / 算法結(jié)束  2·8void union_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,p

8、b為工作指針，分別指向A表和B表的當(dāng)前元素，r為當(dāng)前逆置/元素的后繼指針, 使逆置元素的表避免斷開(kāi)。 /算法思想是邊合并邊逆置，使遞增有序的單鏈表合并為遞減有序的單鏈表。 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)的指針 e

9、lse / 將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) / 將A表中剩余元素逆置 r=pa->next; / 保留后繼結(jié)點(diǎn)的指針 pa->next=C->next; / 逆置 C->next=pa; pa=r; / 恢復(fù)待逆置結(jié)點(diǎn)的指針 while (pb) / 將B表中剩余元素逆置 r=pb->next; / 保留后

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

11、 pre->next=s;free(p); / 刪除元素 / 算法結(jié)束  2·10void one_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)的同一類(lèi)字符，利用原表空間。 linklist *p=A->next,r;/ p為工作指針，指向A表的當(dāng)前元素，r為當(dāng)前元素的后繼指針,使表避免斷開(kāi)。 /算法思想是取出當(dāng)前元素，根據(jù)是字母、數(shù)字或其它符號(hào)，分別插入相應(yīng)表中。 B=(linklist

12、*)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->

13、;next=p; / 將字母字符插入A表 else if (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·11void locate(dlinklist *L)/ L是帶頭結(jié)點(diǎn)的按訪問(wèn)頻度遞減的雙向鏈表，本算法先查找數(shù)據(jù)x,/ 查找成功時(shí)結(jié)點(diǎn)的訪問(wèn)頻度域增1，最后將該結(jié)點(diǎn)按頻

14、度遞減插入鏈表中適當(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; /

15、以下查找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； / 算法結(jié)束 第三章 棧和隊(duì)列(參考答案)3.3 void sympthy(linklist *head, stack *s)/判斷長(zhǎng)為n的字符串是否中心對(duì)稱(chēng) int i=1; linklist *p=head->next;while (i<=n/2) / 前一半字符進(jìn)棧

16、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ì)稱(chēng)”)；else printf(“鏈表不是中心對(duì)稱(chēng)”)； / 算法結(jié)束 3.4int match()/從鍵盤(pán)讀入算術(shù)表達(dá)式，本算法判斷圓括號(hào)是否正確配對(duì)（init s;/初始化棧sscanf(“%c”,&ch);while (ch!=#) /#是表達(dá)式輸入結(jié)束符號(hào)switch (ch)

17、 case (: push(s,ch); break;case ): if (empty(s) printf(“括號(hào)不配對(duì)”); exit(0);pop(s);if (!empty(s) printf(“括號(hào)不配對(duì)”); else printf(“括號(hào)配對(duì)”); / 算法結(jié)束  3.5typedef struct / 兩棧共享一向量空間 ElemType vm; / ?？捎每臻g0m-1 int top2 / 棧頂指針twostack; int push(twostack *s,int i, ElemType x)/ 兩棧共享向量空間,i是0或1，表示兩個(gè)棧，x是進(jìn)棧元素，/

18、 本算法是入棧操作 if (abs(s->top0 - s->top1)=1) return(0);/ 棧滿 else switch (i)case 0: s->v+(s->top)=x; break;case 1: s->v-(s->top)=x; break;default: printf(“棧編號(hào)輸入錯(cuò)誤”); return(0);return(1); / 入棧成功 / 算法結(jié)束 ElemType pop(twostack *s,int i)/ 兩棧共享向量空間,i是0或1，表示兩個(gè)棧，本算法是退棧操作 ElemType x;if (i!=0 &

19、;& i!=1) return(0);/ 棧編號(hào)錯(cuò)誤 else switch (i)case 0: if(s->top0=-1) return(0);/?？誩lse x=s->vs->top-;break;case 1: if(s->top1=m) return(0);/?？誩lse x=s->vs->top+; break;default: printf(“棧編號(hào)輸入錯(cuò)誤”);return(0);return(x); / 退棧成功 / 算法結(jié)束  ElemType top (twostack *s,int i)/ 兩棧共享向量空間,i是0

20、或1，表示兩個(gè)棧，本算法是取棧頂元素操作 ElemType x;switch (i)case 0: if(s->top0=-1) return(0);/?？誩lse x=s->vs->top; break;case 1: if(s->top1=m) return(0);/?？誩lse x=s->vs->top; break;default: printf(“棧編號(hào)輸入錯(cuò)誤”);return(0);return(x); / 取棧頂元素成功 / 算法結(jié)束  36void Ackerman(int m,int n)/ Ackerman 函數(shù)的遞歸算法 i

21、f (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) / 算法結(jié)束  37(1) linklist *init(linklist *q)/ q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，本算法將隊(duì)列置空 q=(linklist *)malloc(sizeof(linklist);/申請(qǐng)空間，不判斷空間溢出q->next=q;return (q); / 算法結(jié)束 (2) linklist *enqueue(li

22、nklist *q，ElemType x)/ 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é)束 (3) linklist *delqueue(linklist *q)/q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，這是出隊(duì)算法 if (q=q->next) return (null); / 判斷隊(duì)列是否為空 else

23、 linklist *s=q->next->next; / s指向出隊(duì)元素 if (s=q) q=q->next; / 若隊(duì)列中只一個(gè)元素，置空隊(duì)列else q->next->next=s->next;/ 修改隊(duì)頭元素指針 free (s); / 釋放出隊(duì)結(jié)點(diǎn) return (q); / 算法結(jié)束。算法并未返回出隊(duì)元素  3.8 typedef structElemType datam;/ 循環(huán)隊(duì)列占m個(gè)存儲(chǔ)單元 int front,rear; / front和rear為隊(duì)頭元素和隊(duì)尾元素的指針 / 約定front指向隊(duì)頭元素的前一位置，rear指

24、向隊(duì)尾元素 sequeue; int queuelength(sequeue *cq)/ cq為循環(huán)隊(duì)列，本算法計(jì)算其長(zhǎng)度 return (cq->rear - cq->front + m) % m; / 算法結(jié)束  3.9 typedef structElemType sequm;/ 循環(huán)隊(duì)列占m個(gè)存儲(chǔ)單元 int rear,quelen; / rear指向隊(duì)尾元素,quelen為元素個(gè)數(shù)sequeue;(1) int empty(sequeue *cq)/ cq為循環(huán)隊(duì)列，本算法判斷隊(duì)列是否為空 return (cq->quelen=0 ? 1: 0); / 算

25、法結(jié)束 (2) sequeue *enqueue(sequeue *cq，ElemType x)/ cq是如上定義的循環(huán)隊(duì)列，本算法將元素x入隊(duì)if (cq->quelen=m) return(0); / 隊(duì)滿 else cq->rear=(cq->rear+1) % m; / 計(jì)算插入元素位置 cq->sequcq->rear=x; / 將元素x入隊(duì)列 cq->quelen+; / 修改隊(duì)列長(zhǎng)度 return (cq); / 算法結(jié)束 ElemType delqueue(sequeue *cq)/ cq是以如上定義的循環(huán)隊(duì)列，本算法是出隊(duì)算法，且返回出隊(duì)元

26、素 if (cq->quelen=0) return(0); / 隊(duì)空 else int front=(cq->rear - cq->quelen + 1+m) % m;/ 出隊(duì)元素位置 cq->quelen-; / 修改隊(duì)列長(zhǎng)度 return (cq->sequfront); / 返回隊(duì)頭元素 / 算法結(jié)束第四章 串 (參考答案) 4.2 用串的去其他運(yùn)算構(gòu)成子串的定位運(yùn)算index。 int index(string s,t)/s,t是字符串，本算法求子串t在主串s中的第一次出現(xiàn)，若s串中包含t串，返回其/第一個(gè)字符在s中的位置，否則返回0m=len

27、gth(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);/模式匹配成功else return(0);/s串中無(wú)子串t/算法index結(jié)束4.4 將S=“（xyz）*”轉(zhuǎn)為T(mén)=“（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)

28、/ 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) ch=p->data; / 取X中的字符 while (q && q->data!=ch) q=q->next; / 和Y中字符比較 if (!

29、q) return(ch); / 找到Y(jié)中沒(méi)有的字符 else pre=p->next; / 上一字符在Y中存在，p=pre; / 取X中下一字符。 q=Y->next; / 再?gòu)腨的第一個(gè)字符開(kāi)始比較return(null); / X中字符在Y中均存在 / 算法結(jié)束  4.6 是設(shè)計(jì)一算法，在順序串上實(shí)現(xiàn)串的比較運(yùn)算 strcmp(s,t)int strcmp(seqstring *S, seqstring *T)/ S和T是指向兩個(gè)順序串的指針，本算法比較兩個(gè)串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否則返回-1 int i=0;while (s-&g

30、t;chi!=0 && t->chi!=0)if (s->chi>t->chi) return(1);else if (s->chi<t->chi) return(-1);else i+; / 比較下一字符 if (s->chi!=0&& t->chi=0) return(1);else if (s->chi=0&& t->chi!=0) return(-1);else return(0);/ 算法結(jié)束4.7 linkstring *invert(linkstring *S, li

31、nkstring *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->n

32、ext;else / 失配時(shí)主串回溯到下一個(gè)字符，子串再以第一個(gè)字符開(kāi)始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/

33、算法結(jié)束 第五章 多維數(shù)組和廣義表（參考答案）5.1 A2323A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0112 A0200 , A0201 , A0202 A0210 , A0211 , A0212 將第一維的0變?yōu)?后，可列出另外18個(gè)元素。以行序?yàn)橹鳎葱袃?yōu)先）時(shí)，先改變右邊的下標(biāo)，從右到左進(jìn)行。5.2 設(shè)各維上下號(hào)為c1d1，c2d2，c3d3，每個(gè)元素占l個(gè)單元。LOC(aijk)=LOC(ac1c2c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)

34、+(j-c2)*(d3-c3+1)+(k-c3)*l推廣到n維數(shù)組?。ㄏ陆绾蜕辖纾椋╟i，di），其中1<=i<=n.則：其數(shù)據(jù)元素的存儲(chǔ)位置為：LOC（aj1j2.jn）=LOC（ac1c2cn）+（d2-c2+1） （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

35、) 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章 樹(shù)和二叉樹(shù)（參考答案）6.8int height(bitree bt)/ bt鏈表為存儲(chǔ)結(jié)構(gòu)的是以二叉二叉樹(shù)，本算法求二叉樹(shù)bt的高度 int bl,br; / 局部變量，分別表示二叉樹(shù)左、右子樹(shù)的高度 if (bt=null) return(0);else bl=height(bt->lchild);br=height(bt->rchild);return(bl&

36、gt;br? bl+1: br+1); / 左右子樹(shù)高度的大者加1（根） / 算法結(jié)束 6.227,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第七章 圖（參考答案）71（1）鄰接矩陣中非零元素的個(gè)數(shù)的一半為無(wú)向圖的邊數(shù)；（2）Aij= =0為頂點(diǎn)，I 和j無(wú)邊，否則j和j有邊相通；（3）任一頂點(diǎn)I的度是第I行非0元素的個(gè)數(shù)。73（1）鄰接表（2）從頂點(diǎn)4開(kāi)始的DFS序列：V5,V3,V4,V6,V2,V1（3）從頂點(diǎn)4開(kāi)始的BFS序列：V4,V5,V3,V6,

37、V1,V276簡(jiǎn)單回路指起點(diǎn)和終點(diǎn)相同的簡(jiǎn)單路徑。算法基本思想是利用圖的遍歷，以頂點(diǎn)VK開(kāi)始，若遍歷中再通到VK，則存在簡(jiǎn)單回路，否則不存在簡(jiǎn)單回路。Adjlisttp g ; visited1.n=0;Int found =0;/全程變量Int dfs(btxptr x)/從k頂點(diǎn)深度優(yōu)先遍歷圖g，看是否存在k的簡(jiǎn)單回路 visitedx=1;p=gx.firstarc;while(p!=null) w=p->adjvex;if(w= =k) found=1;exit(0);/有簡(jiǎn)單回路，退出if (!visitedk ) dfs(w );p=p->nextarc;/while(

38、p!=null)/ dfs711void toposort_dfs （graph g；vtptr v）/從頂點(diǎn)v開(kāi)始，利用深度優(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ù)渑判蛐蛄小?visited1.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 ( !visitedw

39、) s+top=w;w=nextadj(g,v,w);/求下一個(gè)鄰接點(diǎn)if (top!=0) v=stop-; num+; printf(v);/輸出頂點(diǎn)printf(“n”);if (num<n) printf(“ 從”,”v”,”頂點(diǎn)開(kāi)始拓?fù)渑判虿荒茼樌瓿?”)；else printf(“拓?fù)渑判虺晒?，輸出的是一個(gè)逆拓?fù)湫蛄?n”);第八章 排序（參考答案）8.4void TwoWayBubbleSort( rectype rn+1; int n)/ 對(duì)r1.n進(jìn)行雙向冒泡排序。即相鄰兩遍向兩個(gè)相反方向起泡 int i=1, exchange=1; / 設(shè)標(biāo)記 while (exc

40、hange) exchange=0; / 假定本趟無(wú)交換 for (j=n-i+1 j>=i+1;j-) / 向前起泡，一趟有一最小冒出 if (rj<rj-1) rjß>rj-1; exchange=1; / 有交換 for (j= i+1;j>=n-I;j+) / 向后起泡，一趟有一最大沉底 if (rj>rj+1) rjß>rj+1; exchange=1; / 有交換 i+; / end of WHILE exchange /算法結(jié)束 8.6void QuickSort(rectype rn+1; int n)/ 對(duì)r1.n進(jìn)行快

41、速排序的非遞歸算法 typedef struct int low,high; nodenode sn+1；int top;int quickpass(rectype r,int,int); / 函數(shù)聲明 top=1; stop.low=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; s

42、top.high=tt; / 算法結(jié)束 int quickpass(rectype r;int s,t)i=s; j=t; rp=ri; x=ri.key;while （i<j）while (i<j && 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); / 一次劃分算法結(jié)束 8.7void QuickSort(rectype rn+1; int n)/ 對(duì)r1.n進(jìn)行快速排序的非遞歸

43、算法 對(duì)8.6算法的改進(jìn) typedef struct int low,high; nodenode sn+1；int top;int quickpass(rectype r,int,int); / 函數(shù)聲明 top=1; stop.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) / 左部子序列長(zhǎng)度大于右部，左部進(jìn)棧 top+; sto

44、p.low=ss; stop.high=k-1; if (tt-k>1) ss=k+1; / 右部短的直接處理 else flag=false; / 右部處理完，需退棧 else if (tt-k>1) /右部子序列長(zhǎng)度大于左部，右部進(jìn)棧 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;

45、/ end of while (flag | top>0) / 算法結(jié)束 int quickpass(rectype r;int s,t)/ 用“三者取中法”對(duì)8.6進(jìn)行改進(jìn) int i=s, j=t, mid=(s+t)/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次

46、移動(dòng)；最差3次比較10次移動(dòng) rp=ri; x=ri.key;while （i<j）while (i<j && 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); / 一次劃分算法結(jié)束 8.8viod searchjrec（rectype r，int j）/在無(wú)序記錄rn中，找到第j（0<=j<n）個(gè)記錄。算法利用快速排序思想，找到第一/軸元素的位置i，若i=j則查找結(jié)束。否

47、則根據(jù)j<i或j>i在0i、1或i+1n+1之間查/找，直到/i=j為止。 int quichpass (rectype r,int,int) / 函數(shù)聲明i=quichpass(r,0,n-1); / 查找樞軸位置whilehile(i!=j)if (j<i) i=quichpass(r,0.i-1);else i=quichpass(r,i+1.n-1);/ searchjrec算法結(jié)束8.9viod rearrange (rectype r,int n)/本算法重排具有n個(gè)元素的數(shù)r，使取負(fù)值的關(guān)鍵字放到取非負(fù)值的關(guān)鍵字之前。 int i=0,j=n-1; rp=r0;

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

49、key>=0) j-;if (i<j) ri+=rj; /將關(guān)鍵字取負(fù)值的記錄放到前面while (i<j && ri.key<0) i+;if (i<j) rj-=ri;/將關(guān)鍵字取非負(fù)值的記錄放到后面ri=rp;/算法結(jié)束 /本算法并未判斷軸樞的關(guān)鍵字的正負(fù)，在排序中并未和軸樞/記錄比較，而是按正負(fù)區(qū)分，提高了效率 8.10typedef struct nodeElemTypedata;struct node *next;linklist;void simpleselect(linklist *head)/head是單鏈表的頭指針，本算法對(duì)其進(jìn)

50、行直接選擇排序。設(shè)p指向無(wú)序區(qū)第一個(gè)記錄（開(kāi)始是鏈表的第一個(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->

51、data; p->data=x; p=p->next; / 鏈表指針后移，指向下一個(gè)最小值結(jié)點(diǎn) /算法結(jié)束 8.14 void CountSort(rectype r; int n);/ 對(duì)r0.n-1進(jìn)行計(jì)數(shù)排序 int cn = 0;/ c數(shù)組初始化，元素值指其在r中的位置。如ci=j,(0<=i,j<n)/ 則意味著ri 應(yīng)在r的第 j 位置上。for (i=0;i<n;i+) / 一趟掃描比較選出大小，給數(shù)組 c 賦值for (j=i+1;j<n;j+)if (ri>rj) ci=ci+1else cj=cj+1;for (i=0;i<n

52、;i+)while (ci!=i) /若ci = i，則ri 正好是第i個(gè)元素;否則，需要調(diào)整 k=ci;temp=rk; rk=ri; ri=temp; / rk和ri交換ci=ck; / 將ck存入ci,ck=k; / rk已是第k個(gè)記錄/ while (ci!=i)第九章 查找（參考答案）9.1 int seqsearch( rectype r, keytype k)/ 監(jiān)視哨設(shè)在n個(gè)元素的升序順序表低下標(biāo)端，順序查找關(guān)鍵字為k的數(shù)據(jù)/ 元素。若存在，則返回其在順序表中的位置，否則，返回0 r0.key=k; i=n; while (ri.key>k) i-;if (i>0 && ri.key=k) return(i); else r