計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程上機(jī)題一：線性表1. 建立單向鏈表；表長(zhǎng)任意；2. 可交互輸出單鏈表中的內(nèi)容；3. 編寫算法計(jì)算出自己所建單鏈表的長(zhǎng)度并輸出；4. 輸出自己所建立單鏈表中的第K個(gè)結(jié)點(diǎn)，并將剩余結(jié)點(diǎn)輸出；5. 將單鏈表倒排并輸出結(jié)果#include#includetypedef int datatype;typedef struct node datatype data; struct node *next;linklist; linklist*Creatlist() /建立鏈表/ int x; linklist *h, *s; h=NULL; printf(n please inpu

2、t the date end with 0:n); printf(n Input data:); scanf(%d,&x); while(x!=0) s=malloc(sizeof(linklist); s-data=x; s-next=h; h=s; printf(n Input data:); scanf(%d,&x); return h; void Putlist(linklist *h) /輸出單鏈表中的內(nèi)容/ linklist *s; s=h; while(s!=NULL) printf(%4d,s-data); s=s-next; int Long(linklist *h) /計(jì)算

3、鏈表的長(zhǎng)度/ int i=0; linklist *s; s=h; while(s!=NULL) i+; s=s-next; return(i); void Delete(linklist *h,int k) /刪除鏈表中第k個(gè)結(jié)點(diǎn)/ int i=0; linklist *p1,*p2; p1=h; if(k=1) h=h-next;free(p1); else while(inext; p2-next=p1-next; free(p1); linklist *Nixu(linklist *h) /逆序輸出鏈表/ linklist *r,*q,*p; r=h; p=r-next; q=p-ne

4、xt; if(h=NULL) printf(the linklist is emptyn); / /空表/ while(q!=NULL&h!=NULL) p-next=r; r=p; p=q; q=q-next; h-next=NULL; p-next=r; return(p); /返回根結(jié)點(diǎn)/ main() int k,x; linklist *h; do /輸出菜單/ printf(nqing shu ru ming ling:n); printf(1.jian li lian biao;n); printf(2.shu chu lian biao zhong de nei rong;n)

5、; printf(3.shu chu lian biao de chang du;n); printf(4.shan chu di K ge jie dian;n); printf(5.jiang lian biao dao xu bing shu chu;n); printf(6.tui chu cheng xu;n); printf(qing shu ru 1-6 de shu zi:n); scanf(%d,&x); if(x6) printf(error!n); else switch(x) case 1:h=Creatlist();break; case 2:Putlist(h);b

6、reak; case 3:printf(lian biao de chang du shi %d,Long(h);break; case 4:printf(Input the node you want to delete:n); scanf(%d,&k); Delete(h,k);Putlist(h);break; case 5:h=Nixu(h);Putlist(h);break; case 6:exit(0);break; /退出程序/ while(1);退出程序；上機(jī)題二：二叉樹1. 動(dòng)態(tài)交互建立二叉樹，結(jié)點(diǎn)個(gè)數(shù)任意；2. 分別用DLR,LDR,LRD三種方式對(duì)二叉樹進(jìn)行遍歷并輸出結(jié)果

7、；3. 計(jì)算二叉樹中結(jié)點(diǎn)個(gè)數(shù)并輸出；4. 計(jì)算二叉樹深度并輸出源程序：#include stdio.h#include malloc.hstruct TreeNode int data; struct TreeNode *Lchild ; struct TreeNode *Rchild;struct TreeNode *create( ) / 用于建立二叉樹的子函數(shù) / struct TreeNode *T; int a; scanf(%d,&a); if (a=0) return NULL; else / 動(dòng)態(tài)建立二叉樹 / T=(struct TreeNode *)malloc(sizeo

8、f(struct TreeNode); T-data=a; / 建立根結(jié)點(diǎn) / T-Lchild=create( ); / 遞歸建立左子樹 / T-Rchild=create( ); / 遞歸建立右子樹 / return (T);void Pre (struct TreeNode *T) / 用于進(jìn)行先序遍歷的子函數(shù) / if (T!= NULL) printf (%5d,T-data); / 訪問根結(jié)點(diǎn) / Pre (T-Lchild); / 遞歸訪問左子樹 / Pre (T-Rchild); / 遞歸訪問右子樹 / void Mid(struct TreeNode *T) / 用于進(jìn)行中序

9、遍歷的子函數(shù) / if ( T != NULL) Mid (T-Lchild); / 遞歸訪問左子樹 / printf(%5d,T-data); / 訪問根結(jié)點(diǎn) / Mid (T-Rchild); / 遞歸訪問右子樹 / void Post (struct TreeNode *T) / 用于進(jìn)行后序遍歷的子函數(shù) / if ( T != NULL) Post (T-Lchild); / 遞歸訪問左子樹 / Post (T-Rchild); / 遞歸訪問右子樹 / printf(%5d,T-data); void visit(struct TreeNode *T) / 用于訪問二叉樹的子函數(shù) /

10、printf(the result of DLR:); Pre(T); printf(n); printf(the result of LDR:); Mid(T); printf(n); printf(the result of LRD:); Post(T); printf(n);int leaf(struct TreeNode *T) / 用于計(jì)算葉子結(jié)點(diǎn)的子函數(shù) / int a,b; if(T=NULL) return (0); else if(T-Lchild=NULL&T-Rchild=NULL) / 判斷該結(jié)點(diǎn)是葉子結(jié)點(diǎn) / return (1); else a=leaf(T-Lch

11、ild); / 遞歸計(jì)算左子樹上葉子數(shù) / b=leaf(T-Rchild); / 遞歸計(jì)算右子樹上葉子數(shù) / return (a+b+1); int max(int x,int y) / 用于取兩數(shù)的較大值的子函數(shù) / if(xy) return (x); else return (y);int deep(struct TreeNode *T) / 用于計(jì)算二叉樹深度的子函數(shù) / int k=0; if(T=NULL) return (0); else if(T-Lchild=NULL&T-Rchild=NULL)/ 該結(jié)點(diǎn)有孩子，深度增加1 / return (1); else retur

12、n (1+max(deep(T-Lchild),deep(T-Rchild);/ 遞歸求取樹的深度 / main() int m,n,p; struct TreeNode *T; printf(create a treen); T=create(); / 建立二叉樹 / printf(1.visit the treen); / 打印菜單 / printf(2.putout the total number of noden); printf(3.putout the depth of the treen); printf(4.exitn); while(1) printf(nplease in

13、put 1-4: ); / 完成菜單的相應(yīng)功能 / scanf(%d,&m); if(m=1) visit(T); if(m=2) n=leaf(T); printf(the total number of leaves in the tree is %dn,n); if(m=3) if(m=3) p=deep(T); printf(the depth of the tree is %dn,p); if(m=4) break; 調(diào)試結(jié)果：create a tree1 0 2 5 0 4 0 6 8 96 0 0 0 56 85 0 0 69 0 0 0 2 5 0 0 01.visit the

14、 tree2.putout the total number of node3.putout the depth of the tree4.exitplease input 1-4: the total number of leaves in the tree is 10please input 1-4:please input 1-4:please input 1-4:please input 1-4:please input 1-4: 1the result of DLR: 1 2 5 4 6 8 96 56 85 69the result of LDR: 1 5 4 96 8 6 85

15、56 69 2the result of LRD: 96 8 85 69 56 6 4 5 2 1please input 1-4: 2the total number of leaves in the tree is 10please input 1-4: 3the depth of the tree is 7please input 1-4: 4Press any key to continue上機(jī)題三 圖在交互方式下完成下列任務(wù)：1、根據(jù)教材上算法，完成圖的深度和廣度優(yōu)先遍歷，要求任意給定起始點(diǎn)，輸出結(jié)果；2、根據(jù)教材上算法，完成圖的單源最短路徑的算法，要求任意給定源點(diǎn)，輸出結(jié)果程序：#

16、include #include #define M 1000#define VNum 6struct GLink int No; int Right; struct GLink *Relat; ;int GVNumVNum = 1 / 對(duì)圖進(jìn)行初始化 / 1 , 31, 11, M, 41, M, M, 0, 15, 50, 10, M, 13, M, 0, 15, M, M, M, 13, M, 0, 17, M, M, M, M, 26, 0, M, M, M, M, 3, M, 0 ;struct GLink *GLVNum;int VisitedVNum;void CreateGLi

17、nk(int GVNumVNum) / 建立鄰接表 / int i,j; struct GLink *p,*q; for (i=0; iVNum; i+) GLi = q = NULL; for (j=0; j 0) & (Gij No = j; / 將該點(diǎn)加入鄰接表 / p-Right = Gij; if (GLi = NULL) GLi = p; else q-Relat = p; q = p; void DFS(int AVNumVNum, int V) / 用于進(jìn)行深度優(yōu)先遍歷的子函數(shù)，V是起點(diǎn) / int i; printf( %d , V); VisitedV = 1; / 將其標(biāo)

18、記為已訪問 / for (i = 0; i 0) & (AVi M) & (Visitedi != 1) / 該結(jié)點(diǎn)未被訪問過 / DFS(A,i); / 訪問該點(diǎn) / for (i = 0; i VNum; i+) if (Visitedi != 1) DFS(A,i); / 仍有未必訪問過的點(diǎn)，訪問該點(diǎn) / void BFS(int AVNumVNum, int V) / 用于廣度優(yōu)先遍歷的子函數(shù) / int CQVNum; int a=0,b,c; int i,k=1; for (i=0;iVNum;i+) CQi=M; VisitedV = 1; / 標(biāo)志為訪問過 / CQ0=V; p

19、rintf(%d ,V); / 將該結(jié)點(diǎn)放入隊(duì)列 / while(k6&ak) /仍有結(jié)點(diǎn)未被訪問并且隊(duì)列中仍有結(jié)點(diǎn)的后繼結(jié)點(diǎn)未被訪問 / b=CQa; for(c=0;cVNum;c+) / 依次將隊(duì)列中以結(jié)點(diǎn)為首的鄰接表中的結(jié)點(diǎn)插入隊(duì)列 / if(Visitedc=0&AbcM&Abc!=0) printf(%d , c); CQ+k=c; / 未被訪問過，將其插入到隊(duì)列中 / Visitedc=1; / 標(biāo)志為訪問過 / a+; for(i=0;iVNum;i+) if(Visitedi=0) BFS(A,i);void Short(int AVNumVNum,int V) / 用于計(jì)算

20、最短路徑的子函數(shù)，V是起點(diǎn) / int DistVNum, PathVNum; int S = 0; int i, k; int wm, u; for (i=0; iVNum; i+) Disti = AVi; / 默認(rèn)這兩點(diǎn)之間即為最短路徑 / if (Disti M) Pathi = V; / 存儲(chǔ)該路徑 / S = S | (1 V); for (k=0; kVNum; k+) wm = M; u = V; for (i=0; iVNum; i+) if (S & (1 i)=0) & (Disti wm) / 該兩點(diǎn)間存在路徑 / u = i; wm = Disti; S = S |

21、(1 u); for (i=0; iVNum; i+) if (S & (1 i)=0) & (Distu + Aui) Disti) Disti = Distu + Aui; / 找到新的最短路徑 / Pathi = u; / 更新路徑長(zhǎng)度 / for (i=0; iVNum; i+) / 輸出該源結(jié)點(diǎn)到其他各點(diǎn)的最短路徑 / if (S & (1 i) != 0) k = i; while ( k != V) printf( %d - , k); k = Pathk; printf( %d , V); printf( = %d n, Disti); else printf( No Path

22、 : %d,i);main() int i,j,a,b; CreateGLink(G); printf(1.search the graph deep firstn); /打印菜單 / printf(2.search the graph broad firstn); printf(3.find the shortest pathn); printf(4.exitn); while(1) / 完成菜單功能/ printf(n please input a num from 1 to 4 : ); scanf(%d,&a); if(a=1) for (i=0; iVNum; i+) Visited

23、i = 0; printf(please input the first node: ); scanf(%d,&j); printf(n The Result of DFS is:); DFS(G,j); printf(n); if(a=2) for (i=0; iVNum; i+) Visitedi = 0; printf(please input the first node: ); scanf(%d,&j); printf(n The Result of BFS is:); BFS(G,j); printf(n); if(a=3) printf(please input the sour

24、ce node : ); scanf(%d,&b); printf(n The Result of Shortest path is:n); Short(G,b); if(a=4) break; 結(jié)果調(diào)試截圖：上機(jī)題四 檢索和排序在交互方式下完成下列任務(wù)：1、任意給定無序序列，用對(duì)半檢索法，交互檢索任意給定的關(guān)鍵字KEY；2、任意給定無序序列，用快速排序法對(duì)進(jìn)行排序，并統(tǒng)計(jì)交換次數(shù)；3、任意給定無序序列，用冒泡排序法對(duì)進(jìn)行排序，并統(tǒng)計(jì)交換次數(shù)和排序的趟數(shù)； 程序：#include #define M 100struct RedType int key; int other; ;int a;in

25、t Search ( struct RedType ST, int n, int key) / 用于進(jìn)行對(duì)半查找的子函數(shù) / int low, high, mid; low=0; high=n-1; while( low = high ) / 未檢索完畢 / mid=(low+high)/2; / 指向中間值 / if ( STmid.key = key) return(mid+1); / 檢索成功 / else if( key = high) / 待排序隊(duì)列空，結(jié)束/ return (0); i = low; j = high; temp = Li; while(i = temp.key)

26、& (j i) /從后向前找出第一個(gè)小于關(guān)鍵值的數(shù)據(jù)/ j -; if (i j) Li = Lj; t+; / 交換，同時(shí)交換次數(shù)加1 / while(Li.key i) /從前向后找出第一個(gè)大于關(guān)鍵值的數(shù)據(jù) / i +; if (i j) Lj = Li; t+; / 交換，同時(shí)交換次數(shù)加1 / Li = temp; printf(nnThe QukSort Loop%d is : ,i); for (j = 0; j a; j+) printf(%d , Lj.key); return(t+QuickSort(L, low, i-1)+QuickSort(L, i+1, high); /

27、對(duì)前后塊分別進(jìn)行快速排序 /void bubsort(struct RedType L , int n) / 用于冒泡排序的子函數(shù) / int i,j=0,m, fag=1,t=0; struct RedType x; while ( (j 0) ) fag=0; / 標(biāo)志有無交換 / for ( i=0; i n-1; i+) if ( Li+1.key Li.key ) / 滿足交換條件 / fag+; / 標(biāo)記發(fā)生交換 / x=Li; / 將相鄰數(shù)據(jù)交換 / Li=Li+1; Li+1=x; t+; / 交換次數(shù)加1 / if(fag) / 輸出交換過程 / j+; / 排序次數(shù)加1 /

28、 for(m=0;mn;m+) printf(%5d,Lm.key); printf(nn); printf(the sorted array is: ); / 輸出排序完之后的數(shù)據(jù) / for(m=0;mn;m+) printf(%5d,Lm.key); printf(n); printf(nthe times of sort is: %d,j); / 給出排序次數(shù) / printf(nthe total times of exchange is : %dn,t); / 給出交換次數(shù) / main() int b,m,n,i,j; struct RedType SM,TM; printf(input the length of the data:); / 預(yù)先給定數(shù)據(jù)的個(gè)數(shù) / scanf(%d,&a); printf(please input the data n); for(i=0;ia;i+) scanf(%d,&Si.key); printf(n1.quick sortn); / 打印菜單 / printf(2.bub so