高等學(xué)校_數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

1、第一章 1、簡述下列術(shù)語： 數(shù)據(jù)元素、數(shù)據(jù)、數(shù)據(jù)對象、 數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和算法 解： 數(shù)據(jù)元素 ：數(shù)據(jù)的基本單位。在計算機程序常作為一個整體進(jìn)行考慮和處理。 數(shù)據(jù) ：信息的載體。 是描述客觀事物的數(shù)字、 字符以及所有能輸入到計算機中并被 計算機程序處理的符號的集合。 數(shù)據(jù)對象 ：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。 數(shù)據(jù)結(jié)構(gòu) ：相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合， 包括數(shù)據(jù)的邏輯結(jié)構(gòu)和 物理結(jié)構(gòu)兩方面的容。 存儲結(jié)構(gòu) ：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算集中的表示方式， 包含順序存儲方法、 存儲方法、 索 引存儲方法、散列存儲方法。 算法 ： 對特定問題求解步驟的一種描述，它是指令或語句

2、的有限序列，并具有有 窮型、確定性、可行性、輸入和輸出五個重要特性。 2、試寫一算法，自大至小依次輸出順序讀入的三個整數(shù)x， y 和 z 的值 解： void f1(void) int x,y,z; printf(enter x,y,z:); scanf(%d,%d,%d, if(xy) if(yz) printf(%d,%d,%d,x,y,z); else if(xz) printf(%d,%d,%d,x,z,y); else printf(%d,%d,%d,z,x,y); else if(xz) printf(%d,%d,%d,y,x,z); else if(zy) printf(%d,%

3、d,%d,z,y,x); else printf(%d,%d,%d,y,z,x); 3、舉出一個數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、 運算等三方面的容 解： 4、分析下列算法的時間復(fù)雜度： (1) int prime(int n) for(i=2;isqrt(n);i+) if(n%i=0) return 0; return 1; 解： O(n1/2 ) (2) long sun(int n) s=0; for(i=1;i=n;i+) for(p=1,j=1;jlen=0) return -1;/*表已空 */ while (ile n) if(L-elemi=x) for (j=i;j

4、le n_1;j+) L-elemj=L-elemj+1;/*被刪除元素之后的元素左移*/ -L-le n; else i+; return 1; 4、 設(shè)線性表(ai, a2,，an)存儲在帶表頭結(jié)點的單鏈表中， 試設(shè)計算法，求出該線性表中值為x的元素的序號。如果 x 不存在，則序號為 0。 int In dex_Li nkst( LNode *H,ELEMTP x) p=H-next; j=1;f=0; /* P指向第一個結(jié)點，j為計數(shù)器，f為標(biāo)志*/ while( p ) if(p-data!=x) j+; p=p-n ext; else f=1; if( f=1 ) return j;

5、 else return 0; 5、在一個非遞減有序線性表中，插入一個值為x 的元素， 使插入后的線性表仍為非遞減有序。 分別寫出用順序表和單 鏈表表示時的算法。 順序表： int Insert_Sq (SqList *L ,ELEMTP x) if ( L-len= MAXSIZE-1) return -1; /*表已滿 */ if(x=L-elemL-len) L-elemL-len+1=x; L-len+=1; else i=1; while (x=L-elemi) i+; for(j=L-len;j=i;j-) L-elemj+1=L-elemj; L-elemi=x; L-len+=

6、1; return 1; 單鏈表： int Insert_Linkst (LNode *H, ELEMTP x) p=H; s= (LNode *) malloc (sizeof(LNode); if(s) s-data=x; s-next=NULL; else return 0; while ( p-next) if(p-next-datanext; else 插入 */ s-next=p-next; p-next=s; /* return 1; /* Insert_Linkst*/ p-next=s; return 1; 6、設(shè)一個線性表L=(a1 , a2,，a n),編寫算法將其逆置，

7、 即成為(a n, an-1，a2, al)。要求逆置后的線性表仍占 用原來的存儲空間，并且用順序和單鏈表兩種方法表示，寫 出不同的處理過程。 順序表： void inverse_Sq( SqList *L ) int i; ELEMTP x; for(i=1;ilen/2;i+) x=L-elemi; L-elemi=L-elemL-len-i+1; L-elemL-len-i+1=x; 單鏈表： void inverse_Linkst (LNode *H ) d=h-next; if(d!=NULL) p=d-next; while(p) t=p-next; p-next=d; d=p;

8、p=t; h=d; 7、設(shè)兩個單鏈表A和B,它們的數(shù)據(jù)元素分別為(x1 ,x2，,x m)和(y1 , y2 ,，y n)。設(shè)計一個算法將它們合并為一個 單鏈表C使得： 當(dāng) m n 時，C= (x1 , y1 , x2, y2, . , x n, y n, .,x m ) 當(dāng) n m時，C= (y1 , x1 , y2 , x2 , . , y m , x m,y n ) 。 LNode * Link_Linkst( LNode *A,LNode *B ) p=A-next; q=B-next; m=0; n=0; while(p) m+; p=p-next; while(q) n+; q=q

9、-next; if(m=n) p=A-next; q=B-next; C=A; else p=B-next; q=A-next; C=B; while(q) t=p-next; p-next=q; q=q-next; p-next-next=t; p=t; return C; 8、試寫一算法，在無表頭結(jié)點的單鏈表中值為 a 的結(jié)點前 插入一個值為 b 的結(jié)點 , 如果 a 不存在， 則把 b 插在表尾 。 將該算法與第 2.3.2 節(jié)中的算法 2 7 進(jìn)行比較。 void Insertx_Linkst (LNode *H, Elemtp a, Elemtp b) s=(LNode *) mal

10、loc (sizeof(LNode); s-data=b; s-next=NULL; if(H=NULL) H=s; else p=H; q=p-next; if(p-data=a)/* 對首元節(jié)點處理 */ s-next=p; H=s; else while(q q=q-next; p-next=s; s-next=q; 9、假設(shè)有一個單向循環(huán)鏈表，其結(jié)點包含三個域： data ， pre 和 next ，其中 data 為數(shù)據(jù)域， next 為指針域，其值為 后繼結(jié)點的地址，pre也為指針域，其初值為空(NULL),試 設(shè)計算法將此單向循環(huán)鏈表改為雙向循環(huán)鏈表。 void Change_L

11、inkst (LNode *H) q=H; p=H-next; while(p) p-pre=q; q=p; p=p-next; H-pre=q; q-next=H; 10、已知二維數(shù)組 A57 ，其每個元素占四個存儲單元， 且 A00 的存儲地址為 1100 ，試求出元素 A35 的存儲 地址(分別討論以行為序和以列為序方式存儲時的結(jié)論) 。 行為序 1100+4*(3*7+5)=1204 列為序 1100+4*(5*5+3)=1212 11、設(shè)有一個二維數(shù)組AMN ，對以下三種情況分別編寫 算法： ( 1) 求數(shù)組 A 的最外圍元素之和； ( 2)求從 A00 開始的互不相鄰的各元素之和；

12、 (3) 當(dāng)M=N時，分別求兩條對角線上的元素之和，否則 輸出M N的信息。 int A1(int AMN)/* 求數(shù)組 A 的最外圍元素之和 */ s=0; for(i=0;iM;i+) if(i=0|i=M-1) for(j=0;jN;j+) s+=Aij; else s+=Ai0+AiN-1; return s; */ int A2(ELEMTP AMN)/* 求從A00開始的互不相鄰的各元素之和 s=0; for(i=0;iM;i+) if(i%2=0) j=0; else j=1; for(;jN;j+=2) s+=Aij; return s; void A3(int AMN,int

13、 *s1,int *s2)/* 分別求兩條對角線上的元素之和*/ *s1= 0;/* */ *s2=0; /* / */ if(M!=N) prin tf(M!=N); else for(i=0;iM;i+) *s1+=Aii; *s2+= AiN-1-i; 12、現(xiàn)有如下所示的稀疏矩陣 字鏈表。 A試寫出它的三元組表和十 廠 3 0 0 7 0 0 -1 0 A= 2 0 0 0 0 0 0 0 匚 0 0 0 -3 解: (1) i j v 1 1 3 1 4 7 2 3 -1 3 1 2 0 1 2 4 (2) -3 M.chead A M.rhead 1 A r 1 1 3 1 1 3

14、 1 2 A A 2 3-1 / A A 1 4 7 A 5 ,4 -3 , A A 13、假設(shè)稀疏矩陣A和B (具有相同的行列數(shù))都采用三元 組表示，編寫算法計算C=A+B /* 思路：依次掃描 A、B的行號和列號，若 A的當(dāng)前項的行號等于 B當(dāng)前項的行號，則比較其 列號，將較小列號的項放入C,如果列號也相等，相加后放入C;若A當(dāng)前項的行號小于B 當(dāng)前項的行號，則將 A項放入C,否則將B項放入C */ void matadd( SpMatTp *A, SpMatTp *B, SpMatTp *C) int i=1;j=1,k=1; while(i m C-elemk.j=A-elemi.j;

15、 C-elemk.v=A-elemi.v; k+; i+; else if(A-elemi.jB-elemj.j) C-elemk.i=B-elemj.i; C-elemk.j=B-elemj.j; C-elemk.v=B-elemj.v; k+; j+; else C-elemk.i=B-elemj.i; C-elemk.j=B-elemj.j; C-elemk.v=B-elemj.v+A-elemi.v; k+; j+; i+; else if(A-elemi.ielemj.i) /*若A當(dāng)前項的行號小于 B當(dāng)前項的行號，則將 A項放入C*/ C-elemk.i=A-elemi.i; C-

16、elemk.j=A-elemi.j; C-elemk.v=A-elemi.v; k+; i+; else /*若A當(dāng)前項的行號大于 B當(dāng)前項的行號，則將 B項放入C*/ C-elemk.i=B-elemj.i; C-elemk.j=B-elemj.j; C-elemk.v=B-elemj.v; k+; j+; C-m=A-m;/*C 的行數(shù) */ C-n=A-n;/*C 的列數(shù) */ C-t=k-1;/*C 的非零元個數(shù) */ 14、設(shè)稀疏矩陣 A 用十字鏈表表示，編寫算法查找元素： ( 1)已知 i ，j ，查找 Aij； ( 2)已知 x 的值，查找它在第幾行第幾列。 解： (1) int

17、 findmat(CrossList *M,int i,int j,int *val) if(imu while(p) if(p-col=j) *val=p-val; return 1;/* 找到 */ else p=p-right; return 0;/* 未找到 */ else return -1;/* 行號錯誤 */ (2) int findmat(CrossList *M,int x,int *rown,int *coln) for(int i=1;imu;i+) p=M-rheadi; while(p) if(p-val=x) *rown=p-row; *coln=p-col; re

18、turn 1; else p=p-right; return 0; 上機實習(xí)題 1.設(shè) A= (ai,a 2，,an)和 B= (bi,b2,bm)是兩個線 性表，其數(shù)據(jù)類型是整型。若n=m且ai = b i(1 i n),則 稱 A=B；若 ai = bj (1 i vj ),而 aj v bj (j v n m),則稱 Av B；除此以外，均稱A=B設(shè)計一個比較 A、B大小的程序。 #include #define MAXSIZE i00 typedef struct int elemMAXSIZE; /*存儲線性表中的元素 */ int len; /* 線性表的當(dāng)前表長 */ SqLis

19、t; SqList * InitList(SqList *L) L=(SqList *)malloc(sizeof(SqList); L-len=0; return L; int Insert(SqList *L,int i,int x) int j; if (iL-len+1) return 0; /* 不合理的插入位置 i */ if ( L-len= MAXSIZE-1) return -1; /* 表已滿 */ for (j=L-len;j=i;-j) L-elemj+1=L-elemj; /* L-elemi=x; /* +L-len; /* return 1; 插入位置及之后的元素

20、右移 */ 插入 x */ 表長加 1 */ int f(SqList *A,SqList*B) SqList *As=NULL,*Bs=NULL; int i=1,j,ms=0,ns=0; As=InitList(As); Bs=InitList(Bs); while(A-elemi=B-elemi) i+; for(j=i;jlen;j+) Insert(As,j-i+1,A-elemj); for(j=i;jlen;j+) Insert(Bs,j-i+1,B-elemj); ms=As-len; ns=Bs-len; if(ms=ns else if(ms=0 else return 1

21、; int main() SqList *A=NULL,*B=NULL; int n=0,m=0,i=0,d=0; A=InitList(A); B=InitList(B); if(A!=B) printf(A!=B); else printf(A=B); printf(nInput n:); scanf(%d, for(i=1;i=n;i+) printf(a%d:,i); scanf(%d, Insert(A,i,d); for(i=1;ilen;i+) printf(%d ,A-elemi); printf(n); printf(nInput m:); scanf(%d, for(i=1

22、;i=m;i+) printf(b%d:,i); scanf(%d, Insert(B,i,d); for(i=1;ilen;i+) printf(%d ,B-elemi); printf(n); printf(n); for(i=1;ilen;i+) printf(%d ,A-elemi); printf(n); for(i=1;ilen;i+) printf(%d ,B-elemi); i=f(A,B); if(i=0) printf(A=B); else if(i0) printf(AB); return 0; 2. 設(shè) 計 一 個 程 序 求 出 約 瑟 夫 環(huán) 的 出 列 順 序 。

23、 約 瑟 夫 (Joseph)問題的一種描述是：編號為 1, 2,，n的n個 人按順時針方向圍坐一圈，每人持有一個密碼(正整數(shù)) 。 一開始任選一個正整數(shù)作為報數(shù)上限值m從第一個人開始 按順時針方向自1開始順序報數(shù)，報到 m時停止報數(shù)。報 m 的人出列，將他的密碼作為新的m值，從他在順時針方向上 的下一個人開始重新從 1 報數(shù)，如此下去，直至所有人全部 出列為止。例如 n=7,7 個人的密碼依次為： 3, 1 , 7, 2, 4, 8, 4, m的初值取6,則正確的出列順序應(yīng)為 6，1, 4，7, 2, 3，5。要求使用單向循環(huán)鏈表模擬此出列過程。 #include typedef struc

24、t node int data; struct node *next; int id; LNode; LNode * insert (LNode *rear,int x,int id) LNode *s; s=(LNode *)malloc(sizeof(LNode); s-data=x; s-id=id; if(rear=NULL) rear=s; s-next=s; return rear; else s-next=rear-next; rear-next=s; rear=s; return rear; int main() LNode *rear=NULL,*p=NULL,*q=NULL

25、; int d,m,i=1; printf(input:); scanf(%d, while(d!=0) rear=insert(rear,d,i+); printf(ninput:); scanf(%d, p=rear-next;/* 顯示數(shù)據(jù) */ while(p!=rear) printf(%d ,p-data); p=p-next; printf(%d,p-data); printf(input m:);/* 輸入初始 m*/ scanf(%d, p=rear; while(p!=p-next) for(i=1;inext; q=p-next; p-next=q-next; m=q-d

26、ata; printf(%d ,q-id); free(q); printf(%d ,p-id); free(p); return 0; 第三章 習(xí)題 l 假定有編號為 A、B、C 的 3 輛列車，順序開進(jìn)一個棧式 結(jié)構(gòu)的站臺，請寫出開出車站站臺的列車順序 ( 注：每一列 車由站臺開出時均可進(jìn)棧，出棧開出站臺，但不允許出棧后 回退 ) 。寫出每一種可能的序列。 解： 產(chǎn)生： ABC、 ACB、 BAC、 BCA、 CBA 不會產(chǎn)生： CAB 2. 有字符串次序為5*-y-a/y T 2,試?yán)脳Ｅ懦鰧⒋涡蚋淖?為5y-*ay T /-的操作步驟(可用X代表掃描該字符串過程中 順序取一字符進(jìn)棧的

27、操作，用S代表從棧中取出一字符加到 新字符串尾的出棧的操作)。例如，ABC變?yōu)锽CA的操作步驟 為 XXSXSS。 解： XSXXXSSSXXSXXSXXSSSS 3. 寫出鏈棧的取棧頂元素和置?？盏乃惴?。 解： (1) int GetTop(SNode *top,ELEMTP *Y) if(top=NULL) return -1 else *y=top-data; return 1; (2) SNode * Empty(SNode *top) while(top) p=top; top=top-n ext; free(p); return NULL; 4. 假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方

28、括弧和花括弧， 編寫一個判別表達(dá)式中括弧是否正確配對的算法。 解： int f() In itStack(p); Push(p,#); c=getchar(); while(c!=#|GetTop(p)!=#) if(c=(|c=|c=) Push(p,c); if(c=) Pop(p,o); if(o!= ( ) return -1; if(c=) Pop(p,o); if(o!= ) return -1; if(c= ) Pop(p,o); if(o!= ) return -1; c=getchar(); return 1; 5.寫出計算表達(dá)式5+3*4/6-7 時操作數(shù)棧和運算符棧的變

29、化情況。 解: 步驟 OPTR OPND 輸入字符 1 # 5+3*4/6-7# 2 # 5 +3*4/6-7# 3 #+ 5 3*4/6-7# 4 #+ 5，3 *4/6-7# 5 #+* 5，3 4/6-7# 6 #+* 5, 3，4 /6-7# 7 #+ 5，12 /6-7# 8 #+/ 5，12 6-7# 9 #+/ 5，12，6 -7# 10 #+ 5, 2， -7# 11 # 7 -7# 12 #- 7 7# 13 #- 7, 7 # 14 # 0 # 6. 對于給定的十進(jìn)制正整數(shù)，打印出對應(yīng)的八進(jìn)制正整數(shù) (1) 寫出遞歸算法。 (2) 寫出非遞歸算法。 解： int f(int

30、 n)/*遞歸算法 */ if (n 1)/*退棧求值 */ fval=stacktop0; top-; stacktop2=fval; stacktop0=stacktop1*stacktop2; return(stacktop0); int front; /* 隊頭 */ int count; MySqQueue; void Empty(MySqQueue *Sq)/* 置空隊列 */ Sq-front=0; Sq-count=0; int EnQueue(MySqQueue *Sq , ELENTP x)/* 在循環(huán)隊列 Sq的尾部插入一個新的元素x */ if(Sq-count=MAX

31、SIZE) return -1;/* 隊列上溢 */ else Sq-count+; Sq-elem(Sq-front+Sq-count)%MAXSIZE=x; return 1; int DelQueue(MySqQueue *Sq ，ELEMTP *y)/* 刪除循環(huán)隊列 Sq 的隊頭元素，并存人 *y 中*/ if(Sq-count=0) return -1;/* 隊列下溢 */ else Sq-front=(Sq-front+1)%MAXSIZE; *y=Sq-elemSq-front; Sq-count-; return 1; 10假設(shè)以帶頭結(jié)點的循環(huán)鏈表示列隊，并且只設(shè)一個指針 指

32、向隊尾元素結(jié)點 ( 注意不設(shè)頭指針 ) ，試編寫出相應(yīng)的置空 隊列，入隊列和出隊列的算法。 解： typedef struct node /* 結(jié)點結(jié)構(gòu) */ ELEMTP data; struct node *next; QNode; typedef struct QNone *rear; /* 隊尾指針 */ MyLQueue; void Empty(MyLQueue *Lq)/* 置空隊列 */ if(Lq-rear!=NULL)/* 循環(huán)隊列為非空 */ head=Lq-rear-next; while(head!=Lq-rear) p=head; head=head-next; fr

33、ee(p); free(head); Lq-rear=NULL; int EnQueue(MyLQueue *Lq , ELENTP x)/* 在循環(huán)隊列 Sq的尾部插入一個新的元素x */ p=(QNone *)malloc(sizeof(QNone); if(p=NULL) return -1; else p-data=x; p-next=NULL ; if(Lq-rear=NULL)/* 循環(huán)隊列為空 */ Lq-rear=p; p-next=p; else head=Lq-rear-next; Lq-rear-next=s; Lq-rear=s; s-next=head; return

34、 1; int DelQueue(MyLQueue *Lq ， ELEMTP *y)/* 刪除循環(huán)隊列 Sq 的隊頭元素，并存人 *y 中*/ if(Lq-rear=NULL)/* 隊列下溢 */ return -1; else head=Lq-rear-next; if(head=Lq-rear)/* 只有一個節(jié)點 */ *y=head-data; free(head); Lq-rear=NULL; else *y=head-data; Lq-rear-next=head-next; free(head); return 1; 上機實習(xí)題 1設(shè)計一個算法，檢驗C 源程序代碼中的括弧對是否正確

35、 配對。要求在某個 C 源程序文件上對你的算法進(jìn)行驗正。 #include typedef struct node char data; struct node *next; SNode; SNode * Push(SNode *top , char x) SNode *p; p=(SNode *)malloc(sizeof(SNode); p-data=x; p-next=top; top=p; return top; SNode *Pop(SNode *top , char *y, int *flag) SNode *p; if(top=NULL) *flag=0; /* 鏈棧已空 */

36、else /* 出棧 */ p=top; *y=p-data; top=p-next; *flag=1; return top; int main(int argc, char *argv) FILE *fp; char ch,o; int flag=1; SNode *p=NULL; if(argc!=2) printf(You forgot to enter the filenamen); exit(1); if(fp=fopen(argv1,r)=NULL) printf(cannot open filen); exit(1); ch=getc(fp); while(ch!=EOF) i

37、f(ch=(|ch=|ch=) printf(Push%cn,ch); p=Push(p,ch); if(ch=) p=Pop(p, printf():Pop%c,%dn,o,flag); if(flag=0) printf(d lose (); else switch (o) case ( :break; case :printf(lose );exit(0); case :printf(lose );exit(0); if(ch=) p=Pop(p, printf(:Pop%c,%dn,o,flag); if(flag=0) printf(d lose ); else switch (o)

38、 case ( :printf(lose );exit(0); case :break; case :printf(lose );exit(0); if(ch=) p=Pop(p, printf(:Pop%c,%dn,o,flag); if(flag=0) printf(d lose ); else switch (o) case ( :printf(lose );exit(0); case :printf(lose );exit(0); case :break; ch=getc(fp); p=Pop(p, if(flag=0) printf(OK); while(flag!=0)/* 如果棧

39、未空 */ switch (o) case ( :printf(lose );break; case :printf(lose );break; case :printf(lose );break; p=Pop(p, fclose(fp); return 0; 2設(shè)計程序，模擬手機的某些短信息功能。 功能要求： 20 條）， （1）接受短信息，若超過存儲容量（如最多可存儲 自動將最早接受的信息刪除。 （ 2）顯示短信息數(shù)量。 （ 3）逐條顯示短信息（從最新的開始） ； （4）刪除其中的任意一條短信息； （5）清除。 /* （1）接受短信息，若超過存儲容量（如最多可存儲20 條），自動將最早接受

40、的信息刪除。 （2）顯示短信息數(shù)量。 （3）逐條顯示短信息（從最新的開始） ； （4）刪除其中的任意一條短信息； （5）清除。 */ #include #include #include #define MAXSIZE 20/* 存儲容量 */ #define INFOLEN 100/* 信息長度 */ typedef struct node /* 結(jié)點結(jié)構(gòu) */ char InfoINFOLEN; struct node *next; QNode; typedef struct QNode * front; /*隊頭指針 */ QNode * rear; /* 隊尾指針 */ int cou

41、nt; MyInfo; MyInfo *Init() /* 初始化 */ MyInfo *p; QNode *q; p=(MyInfo *)malloc(sizeof(MyInfo); p-count=0; q=(QNode *)malloc(sizeof(QNode); q-next=NULL; p-front=q; p-rear=q; return p; int GetNew(MyInfo *Lq)/* 獲得新短信 */ time_t t; struct tm *local; QNode * p; t=time(NULL); local=localtime(/* 獲得時間信息，模擬短信容

42、*/ if(Lq-count=MAXSIZE) Delete(Lq); p=(QNode *)malloc(sizeof(QNode); strcpy(p-Info,asctime(local); p-next=NULL ; Lq-rear-next=p; Lq-rear=p; Lq-count+; return 1; int Delete(MyInfo *Lq)/* 刪除循環(huán)隊列 Lq 的隊頭元素 */ QNode * p; if(Lq-front=Lq-rear) return 0; p=Lq-front-next; /*p Lq-front-next=p-next; if (Lq-rea

43、r=p ) Lq-rear=Lq-front;/* free(p); Lq-count-; return 1; int DeleteI(MyInfo *Lq,int i)/* QNode * p,* q; int n=1; 指向新的隊頭結(jié)點 */ 尾指針指向頭結(jié)點 */ 刪除循環(huán)隊列 Lq 的第 i 個元素 */ if(Lq-front=Lq-rear|iLq-count) return 0; p=Lq-front; while(nnext; n+; q=p-next; p-next=q-next; if (Lq-rear=q ) Lq-rear=p;/* 尾指針指向前結(jié)點 */ free(q

44、); Lq-count-; return 1; void Echo(MyInfo *Lq,int i)/* 顯示第 i 條短信 */ QNode * p=Lq-front-next; int n=1; if(i0 n+; printf(message %d of %d:%sn,i,Lq-count,p-Info); void Remove(MyInfo *Lq) while(Lq-front!=Lq-rear) Delete(Lq); void PrintHlp() printf(nnnn); printf(=n); printf(=press G to get new message=n);

45、 printf(=press E to Echo message=n); printf(=press D to delete a message=n); printf(=press P to delete last message=n); printf(=press R to remove all=n); printf(=n); printf(= =n); printf(=press Q to Quit=n); printf(= =n); printf(=n); printf(nnnn); int main( ) char c; MyInfo * p; int i; p=l ni t(); P

46、rin tHlp(); c=getch(); while(c!=qbreak; case e:/*顯示消息*/ case E:for(i=1;ico un t;i+) Echo(p,i);break; case d:/*刪除當(dāng)前消息*/ case D:pri ntf(i nput i:);sca nf(%d,Deletel(p,i);break; case p:/*刪除最先的紀(jì)錄*/ case P:Delete(p);break; case r:/*清楚所有消息*/ case R:Remove(p);break; c=getch(); Prin tHlp(); Remove(p); retur

47、n 0; 第四章 1 有一棵樹如題圖4-1所示，求出樹的葉子結(jié)點、非終端結(jié)點、 各結(jié)點的度、樹的度和樹深。 解： （1） 葉子結(jié)點：E、F、G H、K J （2）非終端結(jié)點：A B C D、I （3）各結(jié)點的度：度為 3的結(jié)點：A、C 題圖4-1 度為2的結(jié)點：D 度為1的結(jié)點：B、I 度為0的結(jié)點：E、F、G H K、J （4 ）樹的度：3 （5）樹深：4 2 具有三個結(jié)點的二叉樹有多少種不同的形態(tài)？請分別畫出。 解：具有三個結(jié)點的二叉樹有 5種不同的形態(tài)，如下所示： 3. 如果一棵樹有ni個度為1的結(jié)點，n2個度為2的結(jié)點， ，nm個度為m的結(jié)點，則該 樹共有多少個葉子結(jié)點 ？可參考二叉樹

48、性質(zhì) 3的證明方法來思考 m叉樹問題。 解：設(shè)樹中有no個葉子結(jié)點，那么樹中總結(jié)點數(shù)N為： N= no+n i+nm(a) 由于樹中除根結(jié)點外， 其它各結(jié)點都有僅有一個分支指向它， 所以樹中的總結(jié)點數(shù)恰好 比分支數(shù)少1。設(shè)B為樹中總分支數(shù)，即有： B = N-1 另外，除度為0的結(jié)點沒有分支外，每個度為k的結(jié)點有k個分支，所以總分支數(shù)又為： B= 1 Xn i+2Xn 2+nrKn m 即總結(jié)點數(shù)為： N= ni+2Xn2+nXn m+1( b) 由式和式(b)有： n0+n 1+nm= n 1+2Xn2+nXn m+1 即得：no = 1 Xn 2+2Xn 3+ (i-1 ) Xn i +

49、( m-1)Xn m+1 =E( i-1 ) Xn i +1(i=2 4. 寫出按層遍歷二叉樹的算法。 解 ：二叉鏈表結(jié)點結(jié)構(gòu)描述為： typedef struct btnode ELEMTP data;/*數(shù)據(jù)域 */ struct btnode *lchild, *rchild; /*左、右孩子指針域 */ BTNode; void Levorder(BTNode *bt) /* 按層次遍歷二叉樹 InitQueue(Q); if(bt) /* bt非遞歸算法，Q是BTNode *類型的隊列*/ 初始化隊列 Q */ EnQueue(Q,bt); /* 根結(jié)點入隊列 */ while( ！

50、 QueueEmpty(Q) /* 隊列非空 */ DelQueue (Q, /* Visit(p-data); /* 隊頭元素存入變量 p 中 */ 訪問根結(jié)點 */ if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q, p-rchild); /* Levorder*/ 5 .設(shè)計算法求二叉樹中度為1的結(jié)點數(shù)。 解：設(shè)置一個初始值為0的全局變量Count進(jìn)行計數(shù)，在對二叉樹進(jìn)行遍歷的過程中判斷當(dāng) 前所訪問的結(jié)點是否為度為1的結(jié)點，若是則Count加1。因此當(dāng)遍歷完整個二叉樹后，count 的值就是度為1的結(jié)點的數(shù)目。算法描述如下：

51、 int Cou nt=0; void CountDegree1 (BTNode *bt) if (bt) if(bt-lchild /*計數(shù) */ Cou ntDegree1 (bt-lchild); Coun tDegree1 (bt-rchild); /* Cou ntDegree1 */ 6.設(shè)計遞歸算法，求出先根序列中第k個結(jié)點的值。 解： char Locat_bt(BTree bt,int k) /*求先序序列中第k個結(jié)點的值的遞歸算法*/ static int n; n=k; if(bt) n-； if(n=0) return(bt-data); Locat_bt(bt-lch

52、ild,n); if(n!=0) Locat_bt(bt-rchild,n); else return (#); struct thr node *lchild,*rchild; int Rtag; ThrNode2; void in thread2(ThrNode2 *t); ThrNode2 *pre; void Crt_inthread2(ThrNode2 *thrt ) /*已知thrt指向二叉樹的根結(jié)點， 中序遍歷建立中序后繼線索二叉樹*/ pre=NULL; inthread2(thrt);/* 中序遍歷線索化*/ pre-Rtag=1;/* 最后一個結(jié)點線索化*/ /* Crt_

53、inthread2*/ void inthread2(ThrNode *t) /*中序遍歷線索化以t為根的二叉樹*/ if( t ) inthread2(t-lchild); /* 左子樹線索化*/ if(pre!=NULL) if( pre-rchild=NULL) /* pre-Rtag=1; pre-rchild=t; 建立pre結(jié)點的后繼線索*/ pre=t;/*pre 指向t的前驅(qū)*/ inthread2(t-rchild); /* /* inthread2 */ 右子樹線索化*/ 11.畫出與題圖4-2所示二叉樹對應(yīng)的森林。 解: 上機實習(xí)題 、實習(xí)目的 1掌握樹的結(jié)構(gòu)的非線性特點

54、、遞歸性特點和動態(tài)數(shù)據(jù)結(jié)構(gòu)等特點。 2 掌握二叉樹的存儲結(jié)構(gòu)、各種遍歷算法以及基于遍歷算法的其他操作的實現(xiàn)。 二、實習(xí)容 1 編寫一個 C 語言程序，對二叉樹實現(xiàn)以下操作： （1）按先根、中根和后根次序遍歷二叉樹； （ 2）按二叉樹的層次輸出各結(jié)點（每一行輸出一層）； （3）利用遍歷算法，將二叉樹中所有結(jié)點的左右子樹交換。 2在一段文字中 10 個常用漢字及出現(xiàn)的頻度如下： 的地得于個和在再是有 26 6 4 15 7 6 8 5 18 5 試為這些常用漢字設(shè)計哈夫曼編碼表。 第五章 3 V1入度2,出度1 , v2入度1,出度2,v3入度1，出度0, v4入度1，出度2 鄰接陣G 0 0 0

55、 1 1 0 1 0 0 0 0 0 1 1 0 0 鄰接表 v1-v4 v2-v1 v3 v4-v1-v2 逆鄰接表 v1-v2-v4 v2-v4 v3-v2 v4-v1 2廣度優(yōu)先序列是： v2,v1,v3,v6,v4,v5 深度優(yōu)先序列是： v2,v1,v3,v4,v5,v6 3深度優(yōu)先序列是： v1,v3,v4,v2,v5(根據(jù)存儲順序，如果根據(jù)序號大小有不同結(jié)果) 4給出歸并順序： 普里姆： v1,-v3-v4-v5-v2 克魯斯卡爾： v4,v5邊，v4,v2邊，v3,v4邊，v3,v1邊(有權(quán)值相同的邊，不唯一) 5最短路徑 (v1-v3 )5 (v1-v6) 15 (v1-v4

56、) 19 (v1-v2) 20 (v1-v5) 25 6 AOV網(wǎng)絡(luò) v1,v4,( 或者 v4,v1) 可換 ;v2 位置不可變， v5,v3( 或者 v3,v5) ， v6 不可變 鄰接表中 : v1,v4,v2,v3,v5,v6 第六章 1 算法說明： 本程序使用兩個結(jié)點鏈交換的方法， 比較復(fù)雜， 要簡化的同學(xué)可以直接交 換容。代碼可以省去三分之二。 /*insert sort via LinkList*/ struct Node int data; struct Node *next; ; struct Node * locateCount(struct Node *h,int k)

57、int i=0; struct Node *h1=h; for(i=1;inext; return h1; ; show(struct Node *head) struct Node *p; p=head-next; while(p!=0) printf( : %3d : ,p-data); p=p-next; printf(n); return; sort(struct Node *head) struct Node *h,*searchGoalPtr,*p,*q,*qStart,*preGoal; struct Node *temp,*pt1,*pt2,*goalNext; int cou

58、nt=2; h=head; preGoal=head-next; searchGoalPtr=head-next-next; qStart=head; while(searchGoalPtr!=0)/*go */ h-data=searchGoalPtr-data; q=qStart; while(q-next-datadata) q=q-next; pt1=q-next; q-next=searchGoalPtr; pt2=searchGoalPtr-next; searchGoalPtr-next=pt1; preGoal-next=pt2; preGoal=locateCount(hea

59、d,count); count+; searchGoalPtr=locateCount(head,count); show(head); /*while*/ main() struct Node *h,*p1,tail; int var=0; h= (struct Node*) malloc(sizeof(struct Node); h-data=0; h-next=0; /*construct a linked list*/ while(1) printf(Please input a Node,enter -1 end:); scanf(%d, if (var=-1) break; p1=

60、(struct Node*) malloc(sizeof(struct Node); p1-data=var; p1-next=h-next; h-next=p1; show(h); sort(h); show(h); /*yes constructed!*/ free(h); return ; 2 排序過程 56 67 59 41 98 47 26 38 75 52 16原始數(shù)據(jù) 16 26 38 41 52 47 67 59 75 98 56 d=5 16 26 38 41 52 47 67 56 75 98 59 d=3 16 26 38 41 47 52 56 59 67 75 98