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

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í)行程序段的過程中，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

2、n , n! , n n第二章 線性表(參考答案)在以下習(xí)題解答中，假定使用如下類型定義：（1）順序存儲(chǔ)結(jié)構(gòu)：#define MAXSIZE 1024typedef int 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

3、nodeElemTypedata;struct node *prior,*next；dlinklist;（4）靜態(tài)鏈表typedef structElemType data;int next;node;node saMAXSIZE;2.1 頭指針：指向鏈表的指針。因?yàn)閷?duì)鏈表的所有操均需從頭指針開始，即頭指針具有標(biāo)識(shí)鏈表的作用，所以鏈表的名字往往用頭指針來標(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ù)域不無實(shí)際意義（當(dāng)然，也可以存儲(chǔ)鏈表長(zhǎng)度，這只是副產(chǎn)品），其指針域指向頭結(jié)點(diǎn)

4、。這樣在插入和刪除中頭結(jié)點(diǎn)不變。開始結(jié)點(diǎn)：即上面所講第一個(gè)元素的結(jié)點(diǎn)。2.2 只設(shè)尾指針的單循環(huán)鏈表，從尾指針出發(fā)能訪問鏈表上的任何結(jié)點(diǎn)。23 void insert(ElemType A,int elenum,ElemType x)/ 向量A目前有elenum個(gè)元素，且遞增有序，本算法將x插入到向量A中，并保持向量的遞增有序。 int i=0,j; while (ielenum & Ai=i;j-) Aj+1=Aj;/ 向后移動(dòng)元素 Ai=x; / 插入元素 / 算法結(jié)束24 void rightrotate(ElemType A,int n,k)/ 以向量作存儲(chǔ)結(jié)構(gòu)，本算法將向量中的n個(gè)元

5、素循環(huán)右移k位，且只用一個(gè)輔助空間。 int num=0; / 計(jì)數(shù)，最終應(yīng)等于n int start=0; / 記錄開始位置（下標(biāo)） while (numn) 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è)

6、元素放到合適位置 num+; start+; / 起點(diǎn)增1，若numn則開始下一輪右移。 / 算法結(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

7、n-k-i=An-i; An-i=temp; for(i=0;inext, *pre=L，*s;/ p為工作指針，指向當(dāng)前元素，pre為前驅(qū)指針，指向當(dāng)前元素的前驅(qū) s=(linklist *)malloc(sizeof(linklist);/申請(qǐng)空間，不判斷溢出s-data=x; while (p & p-datanext; / 查找插入位置 pre-next=s; s-next=p; / 插入元素 / 算法結(jié)束 26void invert(linklist *L)/ 本算法將帶頭結(jié)點(diǎn)的單鏈表L逆置。 /算法思想是先將頭結(jié)點(diǎn)從表上摘下，然后從第一個(gè)元素結(jié)點(diǎn)開始，依次前插入以L為頭結(jié)點(diǎn)的鏈表中

8、。 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é)束 27(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

9、; return(i); / 算法結(jié)束(2) int length1(node 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é)束 28void union_invert(linklist *A,*B,*C)/ A和B是兩個(gè)帶頭結(jié)點(diǎn)的遞增有序的單鏈表，本算法將兩表合并成 / 一個(gè)帶頭結(jié)點(diǎn)的遞減有序單鏈表C，利用原表空間。 linklist *pa=A-next,*pb=B

10、-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-datadata) / 將A表中元素合并且逆置 r=pa-next; / 保留后繼結(jié)點(diǎn)的指針 pa-next=C-next; / 逆置 C-next=pa; pa=r; / 恢復(fù)待逆置結(jié)點(diǎn)的指針 else / 將B表中元素合并且逆置 r=pb-ne

11、xt; / 保留后繼結(jié)點(diǎn)的指針 pb-next=C-next; / 逆置 C-next=pb; pb=r; / 恢復(fù)待逆置結(jié)點(diǎn)的指針 / 以下while (pa)和while (pb)語句，只執(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-next=C-next; / 逆置 C-next=pb; pb=r; / 恢復(fù)待逆置結(jié)點(diǎn)的指針 fre

12、e(B);/釋放B表頭結(jié)點(diǎn) / 算法結(jié)束 29 void deleteprior(linklist *L)/ 長(zhǎng)度大于1的單循環(huán)鏈表，既無頭結(jié)點(diǎn)，也無頭指針，本算法刪除*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; free(p); / 刪除元素 / 算法結(jié)束 210void one_to_three(linklist *A,*B,*C)/ A是帶頭結(jié)點(diǎn)的的單鏈表，其數(shù)據(jù)元素是字符

13、字母、字符、數(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-

14、next=null; / 準(zhǔn)備循環(huán)鏈表的頭結(jié)點(diǎn) while(p) r=p-next; / 用以記住后繼結(jié)點(diǎn) if (p-data=a&p-datadata=A& p-data next=A-next; A-next=p; / 將字母字符插入A表 else if (p-data=0&p-datanext=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é)束 211void locate(dlinklist *L)/ L是帶頭結(jié)點(diǎn)的按訪問頻度遞減

15、的雙向鏈表，本算法先查找數(shù)據(jù)x,/ 查找成功時(shí)結(jié)點(diǎ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)的

16、插入位置 while (q !=L & q-freqprior; 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 1 4 3 4 2 11 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 設(shè)入棧序列元

17、素?cái)?shù)為n，則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2)3.2 證明：由jk和pjpk 說明pj在pk之前出棧，即在k未進(jìn)棧之前pj已出棧，之后k進(jìn)棧，然后pk出棧；由jpk 說明pj在pk之后出棧，即pj被pk 壓在下面，后進(jìn)先出。由以上兩條，不可能存在ijk使pjpknext;while (idata); p=p-next; if (n % 2 !=0) p=p-next;/ 奇數(shù)個(gè)結(jié)點(diǎn)時(shí)跳過中心結(jié)點(diǎn) while (p & p-data=pop(s) p=p-next; if (p=null) printf(“鏈表中心對(duì)稱”)； else printf(“鏈表不是中心

18、對(duì)稱”)； / 算法結(jié)束 3.4 int match()/從鍵盤讀入算術(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 / 兩棧共享一向量空間 ElemT

19、ype vm; / 棧可用空間0m-1 int top2 / 棧頂指針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); / 入棧成功

20、 / 算法結(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(“棧編號(hào)輸入錯(cuò)誤”);return(0); return(x);

21、 / 退棧成功 / 算法結(jié)束 ElemType top (twostack *s,int i) / 兩棧共享向量空間,i是0或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);/棧空else x=s-vs-top; break; default: printf(“棧編號(hào)輸入錯(cuò)誤”);return(0); return(x); / 取棧頂元素成功 / 算法結(jié)束 36void Acke

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

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

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

25、ngth(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); / 算法結(jié)束 (2) sequeue *enqueue(sequeue *cq，ElemT

26、ype 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ì)元素 if (cq-quelen=0) return(0); / 隊(duì)空 else int front=(cq-rear - cq-qu

27、elen + 1+m) % m;/ 出隊(duì)元素位置 cq-quelen-; / 修改隊(duì)列長(zhǎng)度 return (cq-sequfront); / 返回隊(duì)頭元素 / 算法結(jié)束第四章 串 (參考答案)在以下習(xí)題解答中，假定使用如下類型定義：#define MAXSIZE 1024typedef 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,

28、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)=0) break; else i+;if(inext; 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é)中沒有的字符 else pre=p-next; /

29、 上一字符在Y中存在， p=pre; / 取X中下一字符。 q=Y-next; / 再?gòu)腨的第一個(gè)字符開始比較 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-chit-chi) return(1); else if (s-chichi) return(-1); else i+; / 比較

30、下一字符 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是/ 模式串。本算法是先模式匹配，查找T在S中的第一次出現(xiàn)。如模式匹/ 配成功，則將S中的子串（T串）逆置。linkstring *pre,*sp, *tp; pre=S; / pre是前驅(qū)指針，指向S中與T匹配時(shí)，T 中的前驅(qū) s

31、p=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); / 匹配失敗，沒有逆置 else / 以下是T串逆置 tp=pre-next; / tp是逆置的工作指針，現(xiàn)在指向待逆置的第一個(gè)字符pre-next=sp; / 將S中與T串匹配時(shí)的

32、前驅(qū)指向匹配后的后繼 while (tp!=sp) r=tp-next; tp-next=pre-next; pre-next=tp; tp=r / 算法結(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)

33、為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ù)組！（下界和上界）為（ci，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=1 n其中i（dk-ck+1）

34、（1=i=n） k=i+1若從c開始，c數(shù)組下標(biāo)從0開始，各維長(zhǎng)度為bi（1=i=n）則：LOC（aj1j2jn）=LOC(a000)+(b2* b3* bn*j1+ b3* * bn*+ j2+ bn* jn-1+ jn)*l n=LOC(a000)+ iji 其中：i=l，i-1=bi*i ，1i=n5.3 (1) k=2*i+j ( 0=k3n-2 )(2) i=(k+1)/3 ( 0=k3n-2 ) j=k-2*i5.4void saddlepoint(int amn); / a是m行n列的二維數(shù)組,本算法求所有馬鞍點(diǎn) / b是一維數(shù)組,存放一行中可能的馬鞍點(diǎn)的列值,k記相等值個(gè)數(shù) /

35、 c是一維數(shù)組,存放某列可能馬鞍點(diǎn)的行值,kk記相等值個(gè)數(shù) for(i=0;im;i+) min=ai,0; / 最小值初始化 b0=0; k=1; / b數(shù)組記最小值的列號(hào)，k記最小值的個(gè)數(shù) for(j=1;jn;j+) / 找每一行中的最小值 if (aijmin) b0=j; min=aij;k=1;/ 重新確定最小值 else if (aij=min) bk+1=j; k+; / 有相等的最小值 for (jj=0;jjk;k+) / 第i 行有k個(gè)相等的最小值 j=bjj; max=aijj; kk=0; / aij是否是馬鞍點(diǎn) while (kk=aikk) kk+; if(kk=

36、m)printf(“馬鞍點(diǎn) i=%d,j=%d,aij=%d”,i,j,aij); / 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;im;i+) rowi=ai0; / 最小值初始化 for (j=1;jn;j+) / 找每一行中的最小值 if (aijrowi) rowi=aij; / 重新確定最小值 for (j=0;jn;j+) colj=a0,j; / 最大值

37、初始化 for (i=1;icolj) colj=aij; / 重新確定最大值 for (i=0;im;i+) for (j=1;jn;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,min=0;for(i=0;im

38、;i+) for(i=0; im; i+) for (j=0; jAmaxjj) maxj=i; / 重新確定第j列最大值的行號(hào)if (AijAimini) mini=j; / 重新確定第i行最小值的列號(hào) for (i=0;inext;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表在該行無非0元素； else if(pb=cb)cb=cb-next/B表在該行無非0元素； else if(pb-colcol)/B的非0元素插入A中； j=pb-col;pt=chbj;pre=pt/ 取到表頭指針； while(pt-down_colcol) pre=pt;pt=pt-down; pre-down=pt-down;/該結(jié)點(diǎn)從B表相應(yīng)列摘下 i=pb-right;pt=chbi;pre=pt;/取B表行表頭指針 while(pt-right-rowrow pre=pt;