計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程_第1頁(yè)
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程_第2頁(yè)
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程_第3頁(yè)
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程_第4頁(yè)
計(jì)算機(jī)軟件技術(shù)基礎(chǔ)上機(jī)編程_第5頁(yè)
已閱讀5頁(yè),還剩14頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論