《數(shù)據(jù)結(jié)構(gòu)(C語言描述)》-馬秋菊-源代碼和習(xí)題參考答案

1、習(xí)題配套第一章2C、A、B、B、A、A、D3D=A,B,C,E,F,G,H,I,J;R=,ABCEFGHI題1-3圖 J4順序、鏈?zhǔn)?、索引、哈?！?5解：100n22nn至少要多大6.(n)、(n)、(n)、()、(5)當(dāng)nm，(n),當(dāng)mn，(m)7n!2100lgnn1/2n3/2(3/2)n2nnlgnnn第二章1、2AAD4順序表void Delete_SeqListx(SeqList *L,ElemType x)/*刪除表中值為x元素*/inti,j;for(i=1;ilength;i+)if(L-elemi=x)for(j=i;jlength-1;j+)L-elemj=L-elem

2、j+1;L-length-;/*向上移動(dòng)*/O(n2)鏈表void del_link(LinkList H，int x)/*刪除數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)*/LNode *p，*q;p=H;q=H-next;while(q!=NULL)if(q-data=x)p-next=q-next;free(q);q=p-next;elsep=q;q=q-next;O(n)5int Delete_SeqListx(SeqList *L,int i,int k)/*刪除表中刪除自第i個(gè)結(jié)點(diǎn)開始的k個(gè)結(jié)點(diǎn)*/intj;if(i1|kL-length)/*檢查空表及刪除位置的合法性*/printf(不存在第i個(gè)元素);r

3、eturn ERROR;for(j=i;jlength-k;j+)L-elemj=L-elemj+k; /*向上移動(dòng)*/L-length-=k;Return OK;/*刪除成功*/O(n)6void Delete_SeqListx(SeqList *L,ElemType x)/*將表中值為x元素?fù)Q成y*/inti,j;for(i=1;ilength;i+)if(L-elem=x)L-elemi=y;/* */O(n)7寫一算法在循環(huán)單鏈表上實(shí)現(xiàn)線性表的CList_length(L)運(yùn)算。int link_length(LinkList H)LNode *p;int i=0;p=H;while(

4、p-next!=H)i+;p=p-next;return i;O(n)8在用頭指針表示的單循環(huán)鏈表中，查找開始結(jié)點(diǎn)a1的時(shí)間是O(1)，然而要查找終端結(jié)點(diǎn)則需從頭指針開始遍歷整個(gè)鏈表，其時(shí)間是O(n)。但在很多實(shí)際問題中，表的操作常常是在表的首、尾位置上進(jìn)行，如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an都很方便，它們的存儲位置分別是rear-next-next和rear，顯然，查找時(shí)間都是O(1)。9.int Insert_LinkListab(LinkList H, ElemType a,ElemType b)/*在單鏈表中值為a的結(jié)點(diǎn)前插入一個(gè)值為b的結(jié)點(diǎn)*/L

5、Node*q=H,*s;*p=H-next;while(p!=NULL&p-data!=a) /*q-next&q-next-data!=a*/q=p;p=p-next;/*查找a結(jié)點(diǎn)*/s=(LinkList)malloc(sizeof(LNode);/*申請、填裝結(jié)點(diǎn)*/s-data=b;s-next=q-next;/*新結(jié)點(diǎn)插入在第i-1個(gè)結(jié)點(diǎn)的后面*/q-next=s；return OK;/*Insert_LinkListab*/10順序表void Reverse_Sq(SqList *L)/*順序表的就地逆置*/for(i=1，j=L.len;inext;q=p-next;s=q-n

6、ext;p-next=NULL;while(s-next)q-next=p;p=q;q=s;s=s-next;/*把H的元素逐個(gè)插入新表表頭*/q-next=p;s-next=q;H-next=s;/*Reverse_L*/分析：本算法的思想是，逐個(gè)地把L的當(dāng)前元素q插入新的鏈表頭部，p為新表表頭。11void merge1(LinkList &A,LinkList &B,LinkList &C)/*把鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲空間*/p=A-next;q=B-next;C=A;while(p&q)s=p-next;p-next=q;/*將B的元素插入*/if(s)

7、t=q-next;q-next=s;/*如A非空,將A的元素插入*/p=s;q=t;/*while*/*merge1*/12Status Delete_Pre(CiLNode s)/*刪除單循環(huán)鏈表中結(jié)點(diǎn)p的直接前驅(qū)*/q=p;while(q-next-next!=p)q=q-next;/*找到p的前驅(qū)的前驅(qū)*/s=q-next;q-next=p;free(s);return OK;/*Delete_Pre*/13Status Insert_SqList(SeqList &L，int x)if(L-length+1m-1)return ERROR;L-length+;i=L-length;wh

8、ile(L-elemix&i0;)L-elemi+1=L-elemi;i-;L-elemi+1=x;return OK;/*Insert_SqList14intInsert_Linkx(LinkList H,ElemType x)/*在值遞增單鏈表中插入一個(gè)值為x的結(jié)點(diǎn)，仍遞增*/LNode*q=H,*s;*p=H-next;while(p!=NULL&p-datanext&q-next-datanext;/*查找a結(jié)點(diǎn)*/s=(LinkList)malloc(sizeof(LNode);/*申請、填裝結(jié)點(diǎn)*/s-data=x;s-next=q-next;/*新結(jié)點(diǎn)插入*/q-next=s；r

9、eturn OK;/*Insert_Linkx*/15源程序代碼：（在TubroC2.0測試通過）#include#includestructnodeintnumber;/*人的序號*/intcipher;/*密碼*/structnode*next;/*指向下一個(gè)節(jié)點(diǎn)的指針*/;structnode*CreatList(intnum)/*建立循環(huán)鏈表*/inti;structnode*ptr1,*head;if(ptr1=(structnode*)malloc(sizeof(structnode)=NULL)perror(malloc);returnptr1;head=ptr1;ptr1-ne

10、xt=head;for(i=1;inext=(structnode*)malloc(sizeof(structnode)=NULL)perror(malloc);ptr1-next=head;returnhead;ptr1=ptr1-next;ptr1-next=head;returnhead;main()inti,n=30,m;/*人數(shù)n為30個(gè)*/structnode*head,*ptr;randomize();head=CreatList(n);for(i=1;inumber=i;head-cipher=rand();head=head-next;m=rand();/*m取隨機(jī)數(shù)*/i=

11、0;/*因?yàn)槲覜]辦法刪除head指向的節(jié)點(diǎn)，只會刪除head的下一節(jié)點(diǎn)，所以只能從0數(shù)起。*/while(head-next!=head)/*當(dāng)剩下最后一個(gè)人時(shí)，退出循環(huán)*/if(i=m)ptr=head-next;/*ptr記錄數(shù)到m的那個(gè)人的位置*/printf(number:%dn,ptr-number);printf(cipher:%dn,ptr-cipher);m=ptr-cipher;/*讓m等于數(shù)到m的人的密碼*/head-next=ptr-next;/*讓ptr從鏈表中脫節(jié)，將前后兩個(gè)節(jié)點(diǎn)連接起來*/head=hea/d-next;/*head移向后一個(gè)節(jié)點(diǎn)*/free(ptr

12、);/*釋放ptr指向的內(nèi)存*/i=0;/*將i重新置為0，從0再開始數(shù)*/elsehead=head-next;i+;printf(number:%dn,head-number);printf(cipher:%dn,head-cipher);free(head);/*讓最后一個(gè)人也出列*/16void SqList_Intersect(SqList A,SqList B,SqList &C)/*求元素遞增排列的線性表A和B的元素的交集并存入C中*/i=1;j=1;k=0;while(A.elemi&B.elemj)if(A.elemiB.elemj)j+;if(A.elemi=B.elemj

13、)C.elem+k=A.elemi;/當(dāng)發(fā)現(xiàn)了一個(gè)在A,B中都存在的元素,/就添加到C中i+;j+;/*while*/*SqList_Intersect*/17Status DuLNode_Pre(DuLinkList*H)/*完成雙向循環(huán)鏈表結(jié)點(diǎn)的pre域*/p=H;while(q-next!=H)p-next-pre=p;p=p-next;return OK;/*DuLNode_Pre*/第三章 棧與隊(duì)列1假定有編號A、B、C的3輛列車順序開進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺，請寫出每一種開出站臺的列車編號順序(注：每一列車開出棧開出站臺后，不允許再進(jìn)棧)。2指出下述程序段的功能是什么？ void De

14、mo1(SeqStack *S) int i; arra16;n=16；initStack(&S);for(i=0,inext=NULL;s=( LinkStack *)malloc（sizeof（LinkStack）;s-top= p; 判棧空int Empty_LS（LinkStack *s ） return s-top-next=NULL; 入棧 LinkStack *Push_LS（LinkStack *s , ElemType x） StackNode *p=(StackNode*)malloc（sizeof（StackNode）; p-data=x; p-next=s-top-ne

15、xt; /* 將元素x插入鏈棧頂 */ s-top-next =p ; return s; 出棧int Pop_LS(LinkStack *s , ElemType *y) StackNode *p; if （Empty_LS（s）printf (Stack Underflow.) ; /* 下溢 */ return OVERFLOW; else *y=s-top-next-data ; = s-top-next ; s-top-next=p-next ; free (p); return OK ; 取棧頂元素int GetTop(LinkStack *s,ElemType *y)if(Emp

16、ty_LS(s )printf(Stack underflow.);/*下溢*/return OVERFLOW;else*y= s-top-next-data;return OK;4Status AllBrackets_Test(char str)/*判別表達(dá)式中三種括號是否匹配*/InitStack(s);for(p=str;*p;p+)if(*p=(|*p=|*p=push(s,*p);else if(*p=)|*p=|*p=)if(StackEmpty(s)return ERROR;pop(s,c);if(*p=)&c!=()return ERROR;if(*p=)&c!=return

17、ERROR;if(*p=)&c!=return ERROR;/*必須與當(dāng)前棧頂括號匹配*/*for*/if(!StackEmpty(s)return ERROR;return OK;/*AllBrackets_Test*/或int PairBracket(char *S)/*檢查表達(dá)式中括號是否配對*/int i;SeqStack T;/*定義一個(gè)棧*/InitStack(&T);for(i=0;istrlen(S);i+)if(Si=()Push(&T，Si);/*遇(時(shí)進(jìn)棧*/if(Si=)Pop(&T);/*遇)時(shí)出棧*/return !EmptyStack(&T);/*由棧空否返回正確

18、配對與否*/5寫出計(jì)算表達(dá)式5+3*（3/6-7）時(shí)操作數(shù)和算符棧的變化情況。 表達(dá)式5+3*（4/6-7）的求值過程 步驟運(yùn)算符棧OPTR對象棧OPND讀字符主要操作1#55+3*（3/6-7）#5入棧OPND2# +5+3*（3/6-7）#+入棧OPTR3# +5，33*（3/6-7）#3入棧OPND4# + *5，3*（3/6-7）#*入棧OPTR5# + * (5，3（3/6-7）#( 入棧OPTR6# + * (5，3，34/6-7）#3入棧OPND7# +* ( /5，3，3/6-7）#/入棧OPTR8# + * ( /5，3，3，66-7）#6入棧OPND9# + * (5，3，

19、0.5-7）#3，6出棧OPND，/出棧OPTR求4/6，結(jié)果0.5入棧OPND10# +* (-5，3，0.5-7）#-入棧OPTR11# +* (-5，3，0.5，77）#7入棧OPND12# + * (5，3，-6.5）#0.5，7出棧OPND，-出棧OPTR求0.5-7，結(jié)果-6.5入棧OPND13# + *5，3，-6.5#( 出棧14# +5，-19.5#3，-6.5出棧OPND，*出棧OPTR求3*-6.5，結(jié)果-19.5入棧OPND15#-14.5#5，-19.5出棧OPND，*出棧OPTR,求5+-19.5，結(jié)果-14.5入棧OPND16#-14.5#RERTURN(-14.

20、5) 6對于給定的十進(jìn)制正整數(shù)，輸出對應(yīng)的八進(jìn)制正整數(shù)。(1)寫出遞歸算法。(2)寫出非遞歸算法。(1)遞歸算法。void conversion1(int N, int R) if ( N0) push(S,n); n=n-1 ; while (!EmptyStack(S) ) Pop(S,i); f=f*i; return (f) ; 8.void huiwen()Init_LS(s); printf(Please input a string:n); for(i=0;(i20)&(ai=getchar()!=n);+i); /*輸入字符串*/ for(j=0;ji/2;+j) /* 字符串

21、的前一半入棧*/ Push_LS(s,aj); for(j=i-i/2;jrear-sq-front sq-rear=sq-frontcount= m-(sq- front-sq-rear) sq-rearfront11循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？優(yōu)點(diǎn)：防止假溢出；判別循環(huán)隊(duì)列的空：return(sq-rear=sq-front)；判別循環(huán)隊(duì)列的滿：return(sq-rear+1)%MAXSIZE=sq-front)12假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾元素位置(注意不設(shè)頭指針)，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空、入隊(duì)和出隊(duì)等算法。typedef struct

22、 qnode ElemType data; struct qnode *next; QCNode; /* 鏈?zhǔn)窖h(huán)鏈隊(duì)列結(jié)點(diǎn)的類型 */typedef struct QCNode *rear; LCQueue ; /* 只設(shè)一個(gè)指向隊(duì)尾元素的指針 */（1）置空隊(duì)算法：void Init_LCQueue(LCQueue *Lcq ) p=(QCnode*)malloc(sizeof(QCNode); /* 申請頭結(jié)點(diǎn) */ p-next=p; Lcq-rear=p; （2）判隊(duì)空算法：int Empty_LCQueue( LCQueue *Lcq) return Lcq-rear-next=L

23、cq-rear; /* 或Lq-rear=NULL; */ （3）入隊(duì)算法：void In_LCQueue(LCQueue *Lcq , ElemType x) /*進(jìn)隊(duì)操作*/ LCQueue *p; p=(QCNode*)malloc(sizeof(QCNode); /* 申請新結(jié)點(diǎn) */ p-data=x; p-next= Lcq-rear-next; Lcq-rear-next=p; Lcq-rear=p; /* In_LCQueue */（4）出隊(duì)算法：int Out_LCQueue(LCQueue *Lq , ElemType *y) LCQueue p ; if (Empty_L

24、CQueue(Lq) ) printf (隊(duì)空) ; return OVERFLOW ; /* 隊(duì)空, 出隊(duì)失敗 */ else p=Lcq-rear-next-next; /* 隊(duì)頭第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)*/ Lcq-rear-next-next =p-next ; *y=p-data; /* 隊(duì)頭元素放y中 */ free (p); return OK; 13假設(shè)用一個(gè)數(shù)組QM來表示隊(duì)列，該隊(duì)列只設(shè)一個(gè)隊(duì)頭指針front，不設(shè)隊(duì)尾指針，用計(jì)數(shù)器count來記錄隊(duì)列中元素的個(gè)數(shù)。試編寫出相應(yīng)的置空隊(duì)列、入隊(duì)列和出隊(duì)列的算法。typedef struct queuenode ElemType el

25、emMAXSIZE; /* 隊(duì)列中數(shù)據(jù)元素的存儲空間 */ int front ,count; /* 隊(duì)頭指針、隊(duì)中元素?cái)?shù)量 */ CirQueue;/* 以上是結(jié)點(diǎn)類型的定義 */ void Init_Queue ( CirQueue *Q) /* 置空隊(duì) */ Q-front=Q-count=0; int Empty_Queue( CirQueue *Q) /* 判隊(duì)空 */ return (Q-count=0); int In_Queue (CirQueue *Q, ElemType x) /* 入隊(duì) */ if(Q-count=MAXSIZE) printf(隊(duì)已滿，不可以入隊(duì)); r

26、eturn OVERFLOW; Q-elem(sq-front+sq-count)%MAXSIZE=x; sq-count +; return OK; int Out_Queue( CirQueue *Q,ElemType *y) /* 出隊(duì) */ if(Empty_Queue(Q) printf(隊(duì)已空，無元素可以出隊(duì)); return OVERFLOW); *y=sq-elemsq-front; /* 讀出隊(duì)頭元素 */ sq-front=(sq-front+1)%MAXSIZE; sq-count-; return OK; int Front_Queue( CirQueue *Q, El

27、emType *y) /* 取隊(duì)頭元素 */ if(Empty_Queue(Q) printf(隊(duì)空，無元素可取); return OVERFLOW); *y=sq-elemsq-front; /* 讀出隊(duì)頭元素 */ return OK; 14設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)出隊(duì)操作的時(shí)間復(fù)雜度是多少？若只設(shè)尾指針呢？若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度是O(1)，出隊(duì)操作的時(shí)間復(fù)雜度是O(n)；若只設(shè)尾指針，則入隊(duì)操作的時(shí)間復(fù)雜度都是O(1)。*15寫一個(gè)算法，借助于棧將一個(gè)單鏈表置逆。第4章 數(shù)組1請按行和按列優(yōu)先順序列出二維數(shù)組A34的所有元素在內(nèi)存中的存儲次序

28、，開始結(jié)點(diǎn)為a00。a00 a10 a20 a01 a11 a21 a02 a12 a22 a03 a13 a232寫出三維數(shù)組地址計(jì)算公式。設(shè)三維數(shù)組Amn*p，先行，列，最后Z方向LOC（Aijk）= LOC（A00 0）+(imn+jm+k) L 3設(shè)有三對角矩陣A nn，將其三條對角線上的元素逐行地存儲到向量B03n-3中，使得Bk=aij，求：用i,j表示k的下標(biāo)變換公式。Aij之間的對應(yīng)關(guān)系為：k=2i+j4二維數(shù)組M的元素是4個(gè)字符（每個(gè)字符占一個(gè)存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲時(shí)元素M35的起始地址與M按列存儲時(shí)元素（ ）的起始地址

29、相同。A. m24 B. M34 C. M35 D. M43M35 與M存儲時(shí)元素M35 起始地址相同。5數(shù)組A中，每個(gè)元素A的存儲占3個(gè)單元，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元個(gè)數(shù)是（1），若該數(shù)組按行存放時(shí)，元素A85的起始地址是（2），若該數(shù)組按列存放時(shí)，元素A85的起始地址是（）。 （1） A. 80 B. 100 C. 240 D. 270 （2） A.SA+141 B.SA+144 C.SA+222 D.SA+225（3） A.SA+141 B.SA+180 C.SA+222 D.SA+225（1）C. （2） C.

30、（3） A6對于二維數(shù)組Amn，其中m=80，n=80，先讀入m，n，然后讀入該數(shù)組的全部元素，對如下三種情況分別編寫相應(yīng)函數(shù)： (1) 求數(shù)組A邊界元素之和。int sum( L ) int row,col,sum=0;for ( row=0;rown;row+) sum= L0row;sum= sum+Lm-1row;/*列*/for (col = 0; coln;col+) sum= Lcol0;sum= sum+ Lcolm-1; /*行*/ (2)求從A00開始的互不相鄰的各元素之和；int sum2( L ) int row,col,sum1=0,sum2=0;for ( row=

31、0;rown;row+,row+) for (col=0; coln;col +, col +) sum1= sum1+Lrowcol; sum2= sum2+Lrow+1col+1; (3)當(dāng)m=n時(shí)，分別求兩條對角線的元素之和，否則打印m!=n的信息。int sum2( L ) int row,col,sum3=0, sum3=0;if(m!=n) printf (m!=n !n);elsefor ( row=0;rowrheadi; while(q)&(q-colright; if(!q) printf(“not searched!”;return NULL;) p=M-cheadj;

32、while(q)&(q -rowdown; if(!p) printf(“not searched!”;return NULL;) return p;（2）已知數(shù)據(jù)元素的值x，查找 x 在A中的行、列號；QLNode * searchx(CrossList M,ElemType x) int i; /*mu,nu*/for (i=1;irheadi; if (q)&(q-vx) q=q-right; else return q;9簡述廣義表和線性表的區(qū)別和聯(lián)系。答：相同點(diǎn)：線性；不同點(diǎn)：數(shù)據(jù)元素分為原子和廣義表。10設(shè)廣義表L=(),()，試問head(L),tail(L)，L的長度、深度各為

33、多少？head(L)= ()tail(L)= ()L的長度為2。11求下列廣義表運(yùn)算的結(jié)果(1) head(a,b,c)= (a,b,c)；(2) tail(b,d,p,h) =()；(3) head(a,b),(c,d) =(a,b),(c,d)；(4) tail(a,b),(c,d) =()；(5)head(tail(a,b),(c,d) =()；(6) tail(head(a,b),(c,d) =()第6章 樹樹的形狀acbfgdeljkimmh1.根據(jù)題意畫出樹的形狀為右圖：a是根結(jié)點(diǎn)，mndfjkl是葉結(jié)點(diǎn)；c是g的雙親；c，a是g的祖先；j，k是g的孩子；imn是e的子孫；d是e的

34、兄弟；g，h是f的兄弟；b的層次是2；n的層次是5；樹的深度是5；以c為根的子樹深度是3；樹的度數(shù)是3。2三個(gè)結(jié)點(diǎn)的二叉樹如下所示：有五種形態(tài)：(1)(2)(3)(4)(5)3分別寫出圖6-28(a)所示的二叉樹的前序、中序和后序遍歷序列。前序ABCDEF中序ACEDB后序EDCBA4畫出圖6-28(b)所示二叉樹順序存儲和二叉鏈表的存儲結(jié)構(gòu)。BACDEABCDGEFHI(b)(a)圖6-285請畫出如圖6-29所示兩棵二叉樹的順序存儲結(jié)構(gòu)，并比較每棵二叉樹所用的存儲空間的大小。CBADLKMN圖6-29 (a)(b)(b) 所用的存儲空間的大6一棵完全二叉樹的第3層上有4個(gè)葉子結(jié)點(diǎn)，問該二叉

35、樹最多有多少個(gè)結(jié)點(diǎn)？7個(gè)結(jié)點(diǎn)7已知一棵二叉樹只存在度數(shù)為0或度數(shù)為2的結(jié)點(diǎn)，度數(shù)為2的結(jié)點(diǎn)有19個(gè)，問度數(shù)為0的結(jié)點(diǎn)有多少個(gè)？20個(gè)，分析：根據(jù)公式n0=n2+1，有n0=19+1=208寫出用非遞歸實(shí)現(xiàn)二叉樹的中序遍歷算法，并分析其時(shí)間復(fù)雜度和棧所需要的最大容量。二叉樹的中序遍歷的非遞歸算法。void Inorder2（BTNode *bt） /* 利用棧實(shí)現(xiàn)前序遍歷非遞歸算法 */ p=bt；top=-1； while(p|top-1) if(p) /* 二叉樹非空 */ +top ；stop=p ； /*根結(jié)點(diǎn)指針進(jìn)棧*/p=p-lchild ； /*p移向左孩子*/else /*棧非空*/ p=stop ；-top ； /*雙親結(jié)點(diǎn)指針出棧*/ printf(p-data)； /*訪問根結(jié)點(diǎn)，輸出結(jié)點(diǎn)*/ p=p-rchild ； /*p移向右孩子*/ /* Inorder2 */9若已知某二叉樹的前序遍歷序列為ABCDEFGHI和中序遍歷序列為BCAEDGHFI，試畫出該二叉樹。并寫出后序遍歷的結(jié)果。ABDCHEFGI10設(shè)二叉樹以二叉鏈表形式存儲，寫一算法交換各結(jié)點(diǎn)的左右子樹。void Exchange1(BTNode *bt) /* 交換左右子樹的第一種方法*/ if(*bt) /