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

1、數(shù)據(jù)結(jié)構(gòu)課后習(xí)題參考答案第一章 緒論1.3 (1) O(n)(2) (2)          O(n)(3) (3)          O(n)(4) (4)          O(n1/2)(5) (5)          執(zhí)行程序段的過(guò)

2、程中，x,y值變化如下：循環(huán)次數(shù) x y0（初始） 91 1001 92 1002 93 100 9 100 10010 101 10011 91 9912 92 100 20 101 9921 91 98 30 101 9831 91 97 到y(tǒng)=0時(shí)，要執(zhí)行10*100次，可記為O（10*y）=O（n）1.5 2100 , (2/3)n , log2n , n1/2 , n3/2 , (3/2)n , nlog2n , 2 n , n! , n n第二章 線性表(參考答案)在以下習(xí)題解答中，假定使用如下類型定義：（1）順序存儲(chǔ)結(jié)構(gòu)：#define MAXSIZE 1024typedef i

3、nt ElemType;/ 實(shí)際上，ElemType可以是任意類型 typedef struct ElemType dataMAXSIZE;int last; / last表示終端結(jié)點(diǎn)在向量中的位置 sequenlist;（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（單鏈表）typedef struct nodeElemType data; struct node *next； linklist;（3）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（雙鏈表）typedef struct nodeElemTypedata;struct node *prior,*next；dlinklist;（4）靜態(tài)鏈表typedef structElemType da

4、ta;int next;node;node saMAXSIZE;2.1 頭指針：指向鏈表的指針。因?yàn)閷?duì)鏈表的所有操均需從頭指針開(kāi)始，即頭指針具有標(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)不變。開(kāi)始結(jié)點(diǎn)：即上面所講第一個(gè)元素的結(jié)點(diǎn)。2.2 只設(shè)尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問(wèn)鏈表上的任何結(jié)點(diǎn)。2·3 void i

5、nsert(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 A,int n,k)/ 以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的n個(gè)元素循環(huán)右移k位，且只用一個(gè)輔助空

6、間。 int num=0; / 計(jì)數(shù)，最終應(yīng)等于n int start=0; / 記錄開(kāi)始位置（下標(biāo)） while (num<n) temp=Astart; /暫存起點(diǎn)元素值，temp與向量中元素類型相同 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; / 計(jì)算新右移元素的下標(biāo) Aempty=temp; / 把一輪右移中最后一個(gè)元素放到合適位置 num

7、+; start+; / 起點(diǎn)增1，若num<n則開(kāi)始下一輪右移。 / 算法結(jié)束 算法二 算法思想：先將左面n-k個(gè)元素逆置，接著將右面k個(gè)元素逆置，最后再將這n個(gè)元素逆置。void rightrotate(ElemType A,int n,k)/ 以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的n個(gè)元素循環(huán)右移k位，且只用一個(gè)輔助空間。 ElemType temp; for(i=0;i<(n-k)/2;i+) /左面n-k個(gè)元素逆置 temp=Ai; Ai=An-k-1-i; An-k-1-i=temp; for(i=1;i<=k;i+) /右面k個(gè)元素逆置 temp=An-k-i; A

8、n-k-i=An-i; An-i=temp; for(i=0;i<n/2;i+) /全部n個(gè)元素逆置 temp=Ai; Ai=An-1-i; An-1-i=temp; / 算法結(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->

9、;data=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)摘下，指針域置空。算

10、法中頭指針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 saMAX

11、SIZE)/ 本算法計(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,pb為工作指針，分別指向

12、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)的指針 else / 將B表中元

13、素合并且逆置 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; / 保留后繼結(jié)點(diǎn)的指針 pb-&

14、gt;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ū) pre->next=s;

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

16、st);/申請(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

17、表 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)按頻度遞減插入鏈表中適當(dāng)位置。 link

18、list *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)的插入位置 wh

19、ile (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ì)列(參考答案)/ 從數(shù)據(jù)結(jié)構(gòu)角度看，棧和隊(duì)列是操作受限的線性結(jié)構(gòu)，其順序存儲(chǔ)結(jié)構(gòu) / 和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義與線性表相同，請(qǐng)參考教材，這里不再重復(fù)。3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3

20、 1 4 3 4 2 11 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 設(shè)入棧序列元素?cái)?shù)為n，則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2)3.2 證明：由j<k和pj<pk 說(shuō)明pj在pk之前出棧，即在k未進(jìn)棧之前pj已出棧，之后k進(jìn)棧，然后pk出棧；由j<k和pj>pk 說(shuō)明pj在pk之后出棧，即pj被pk 壓在下面，后進(jìn)先出。由以上兩條，不可能存在i<j<k使pj<pk<pi。也就是說(shuō)，若有1，2，3順序入棧，不可能有3，1，2的出棧序列。 3.3 void sympthy(linklist *head

21、, stack *s) /判斷長(zhǎng)為n的字符串是否中心對(duì)稱 int i=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ì)稱”)； else printf(“鏈表不是中心對(duì)稱”)； / 算法結(jié)束 3.4 int match()/從

22、鍵盤讀入算術(shù)表達(dá)式，本算法判斷圓括號(hào)是否正確配對(duì)（init s;/初始化棧s scanf(“%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ì)”); else printf(“括號(hào)配對(duì)”); / 算法結(jié)束 3.5typedef struct / 兩棧共享一向量空間 ElemType vm; / 棧可用空間0m-1 int to

23、p2 / 棧頂指針twostack;int push(twostack *s,int i, ElemType x) / 兩棧共享向量空間,i是0或1，表示兩個(gè)棧，x是進(jìn)棧元素，/ 本算法是入棧操作 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); / 入棧成功 /

24、 算法結(jié)束 ElemType pop(twostack *s,int i) / 兩棧共享向量空間,i是0或1，表示兩個(gè)棧，本算法是退棧操作 ElemType x;if (i!=0 && 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);/棧空else x=s->vs->top+; break; default: printf(“

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

26、錯(cuò)誤”);return(0); return(x); / 取棧頂元素成功 / 算法結(jié)束 36void Ackerman(int m,int n) / Ackerman 函數(shù)的遞歸算法 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) / 算法結(jié)束 37(1) linklist *init(linklist *q)/ q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，本算法將隊(duì)列置空 q=(linklist *)mallo

27、c(sizeof(linklist);/申請(qǐng)空間，不判斷空間溢出q->next=q;return (q); / 算法結(jié)束 (2) linklist *enqueue(linklist *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(li

28、nklist *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ì)列else q->next->next=s->next;/ 修改隊(duì)頭元素指針 free (s); / 釋放出隊(duì)結(jié)點(diǎn) return (q); / 算法結(jié)束。算法并未返回出隊(duì)元素 3.8 typedef structElemType datam;

29、/ 循環(huán)隊(duì)列占m個(gè)存儲(chǔ)單元 int front,rear; / front和rear為隊(duì)頭元素和隊(duì)尾元素的指針 / 約定front指向隊(duì)頭元素的前一位置，rear指向隊(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

30、 empty(sequeue *cq) / cq為循環(huán)隊(duì)列，本算法判斷隊(duì)列是否為空 return (cq->quelen=0 ? 1: 0); / 算法結(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)度 ret

31、urn (cq); / 算法結(jié)束 ElemType delqueue(sequeue *cq)/ cq是以如上定義的循環(huán)隊(duì)列，本算法是出隊(duì)算法，且返回出隊(duì)元素 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é)束第四章 串 (參考答案)在以下習(xí)題解答中，假定使用如下類型定義：#define MAXSIZE 1024

32、typedef struct char dataMAXSIZE;int curlen; / curlen表示終端結(jié)點(diǎn)在向量中的位置 seqstring; typedef struct nodechar data;struct node *next ；linkstring;4.2 int index(string s,t) /s,t是字符串，本算法求子串t在主串s中的第一次出現(xiàn)，若s串中包含t串，返回其/第一個(gè)字符在s中的位置，否則返回0m=length(s); n=length(t); i=1; while(i<=m-n+1) if(strcmp(substr(s,i,n),t

33、)=0) break; else i+;if(i<=m-n+1) return(i);/模式匹配成功else return(0);/s串中無(wú)子串t/算法index結(jié)束4.3 設(shè)A=” ”, B=”mule”, C=”old”, D=”my” 則：（a） （a）       strcat（A,B）=”mule”（b） （b）       strcat(B,A)=”mule”（c） （c）       strcat

34、(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）    

35、60;  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,

36、2)=”me”（m） （m）     delete(B,2,0)=”mule”（n） （n）       replace(C,2,2,”k”)=”ok”4.4 將S=“（xyz）*”轉(zhuǎn)為T=“（x+z）*y”S=concat(S, substr(S,3,1) / ”(xyz)*y”S=replace(S,3,1,”+”) / ”(x+z)*y”4.5 char search(linkstring *X, linkstring *Y)/ X和Y是用帶頭結(jié)點(diǎn)的結(jié)點(diǎn)大小為1的單鏈表表示的串，本算法查找

37、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 (!q) return(ch); / 找到Y(jié)中沒(méi)有的字符 else

38、 pre=p->next; / 上一字符在Y中存在， p=pre; / 取X中下一字符。 q=Y->next; / 再?gòu)腨的第一個(gè)字符開(kāi)始比較 return(null); / X中字符在Y中均存在 / 算法結(jié)束 4.6 int strcmp(seqstring *S, seqstring *T)/ S和T是指向兩個(gè)順序串的指針，本算法比較兩個(gè)串的大小，若S串大于T串，返回1；若S串等于T串，返回0；否則返回-1 int i=0; while (s->chi!=0 && t->chi!=0) if (s->chi>t->chi) retu

39、rn(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, linkstring *T)/ S和T是用帶頭結(jié)點(diǎn)的結(jié)點(diǎn)大小為1的單鏈表表示的串，S是主串，T是/ 模式串。本算法是先模式匹配，

40、查找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è)字符開(kāi)始 pre=pre->next; sp=pre-

41、>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 / 算法結(jié)束 第五章 多維數(shù)組和廣義表（參考答案）5.1 A2323A0000 , A0001 , A0002 A00

42、10 , 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)+(j-c2)*(d3-c3+1)+(k-c3)*l推廣到n維數(shù)組?。ㄏ陆绾蜕辖纾椋╟i，di），其中1<

43、=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=1 n其中i（dk-ck+1）（1<=i<=n） k=i+1若從c開(kāi)始，c數(shù)組下標(biāo)從0開(kāi)始，各維長(zhǎng)度為bi（1<=i<=n）則：LOC（aj1j2jn）=LOC(a000)+(b2* b3* bn*j1+ b3* * bn*+ j2+ bn* jn-1+

44、 jn)*l n=LOC(a000)+ iji 其中：i=l，i-1=bi*i ，1<i<=n5.3 (1) k=2*i+j ( 0<=k<3n-2 )(2) i=(k+1)/3 ( 0<=k<3n-2 ) j=k-2*i5.4void saddlepoint(int amn); / 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=ai,0; / 最小值初始化 b0=0; k=1; / b數(shù)組

45、記最小值的列號(hào)，k記最小值的個(gè)數(shù) for(j=1;j<n;j+) / 找每一行中的最小值 if (aij<min) b0=j; min=aij;k=1;/ 重新確定最小值 else if (aij=min) bk+1=j; k+; / 有相等的最小值 for (jj=0;jj<k;k+) / 第i 行有k個(gè)相等的最小值 j=bjj; max=aijj; kk=0; / aij是否是馬鞍點(diǎn) while (kk<m && max>=aikk) kk+; if(kk>=m)printf(“馬鞍點(diǎn) i=%d,j=%d,aij=%d”,i,j,aij)

46、; / END OF for jj / END OF for i 最壞時(shí)間復(fù)雜度為O(m*(n+n*m). (最壞時(shí)所有元素相同，都是馬鞍點(diǎn)) 解法2: 若矩陣中元素值互不相同,則用一維數(shù)組row記下各行最小值，再用一維數(shù)組col記下各列最大值， 相等者為馬鞍點(diǎn)。for (i=0;i<m;i+) rowi=ai0; / 最小值初始化 for (j=1;j<n;j+) / 找每一行中的最小值 if (aij<rowi) rowi=aij; / 重新確定最小值 for (j=0;j<n;j+) colj=a0,j; / 最大值初始化 for (i=1;i<m;i+)

47、/ 找每一列中的最大值 if (aij>colj) colj=aij; / 重新確定最大值 for (i=0;i<m;i+) for (j=1;j<n;j+)if(rowi=colj)printf(“馬鞍點(diǎn) i=%d,j=%d,aij=%d”,i,j,aij); 時(shí)間復(fù)雜度O( (m*n). 解法3: 設(shè)定兩個(gè)數(shù)組： max0.n-1 記各列的最大值所在行號(hào) min0.m-1 記各行的最小值所在列號(hào)第j 列的最大值為Amaxjj,第i行的最小值是Aiminivoid saddlepoint(int amn); / a是m行n列的二維數(shù)組,本算法求所有馬鞍點(diǎn) int max=0

48、,min=0;for(i=0;i<m;i+) for(i=0; i<m; i+) for (j=0; j<n; k+) if (Aij>Amaxjj) maxj=i; / 重新確定第j列最大值的行號(hào)if (Aij<Aimini) mini=j; / 重新確定第i行最小值的列號(hào) for (i=0;i<m;i+) j=mini; / aij是否是馬鞍點(diǎn) if( maxj=i) printf(“馬鞍點(diǎn) A%d%d=%d”,i,j,aij); / END OF for jj 時(shí)間復(fù)雜度為O(m*n+m). 5.5 （1）三元組表（行號(hào) 05，列號(hào) 05）S=（0，0

49、，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，其元素Cij有三種情況；（1）Cij=Aij（Bij =0）；（2）Cij=Bij（Aij =0）；（3）Cij=Aij+Bij 。在（3）種情況下，要看結(jié)果是否為0，C矩陣只有非零元素。Void matrixaddition(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元素； else if(pb=cb)cb=cb->next/B表在該行無(wú)非0元素； else if(pb->col<pa->col)/B的非0元素插入A中； j=pb->col;pt=chbj