计算机软件技术基础上机编程

《计算机软件技术基础上机编程》由会员分享，可在线阅读，更多相关《计算机软件技术基础上机编程（26页珍藏版）》请在装配图网上搜索。

1、计算机软件技术基础上机编程 计算机软件技术基础上机编程上机题一：线性表1. 2. 3. 4. 5. 建立单向链表；表长任意； 可交互输出单链表中的内容； 编写算法计算出自己所建单链表的长度并输出； 输出自己所建立单链表中的第 K 个结点，并将剩余结点输出； 将单链表倒排并输出结果#includestdio.h #includemalloc.h typedef int datatype; typedef struct node datatype data; struct node *next; linklist; linklist*Creatlist() int x; linklist *h,

2、*s; h=NULL; printf(&n please input 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) linklist *s; s=h; while(s!=NULL) printf(&%4d&,s-data); s=s-n

3、ext; int Long(linklist *h) int i=0; linklist *s; s=h; while(s!=NULL) i+;/建立链表/输出单链表中的内容/计算链表的长度/1s=s-next; return(i); void Delete(linklist *h,int k) int i=0; linklist *p1,*p2; p1=h; if(k=1) h=h-next;free(p1); else while(ik-1p1!=NULL) i+; p2=p1; p1=p1-next; p2-next=p1-next; free(p1); /删除链表中第 k 个结点/ l

4、inklist *Nixu(linklist *h) linklist *r,*q,*p; r=h; p=r-next; q=p-next; if(h=NULL) printf(&the linklist is emptyn&); while(q!=NULLh!=NULL) p-next=r; r=p; p=q; q=q-next; h-next=NULL; p-next=r; return(p); main() int k,x; linklist *h; do printf(&nqing shu ru ming ling:n&); printf(&1.jian li lian biao;n&

5、); printf(&2.shu chu lian biao zhong de nei rong;n&); 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&);/逆序输出链表/ /空表/返回根结点/输出菜单/2printf(&qing shu ru 1-6 de shu zi:n&); scanf(&%d&,x);

6、 if(x1|x6) printf(&error!n&); else switch(x) case 1:h=Creatlist();break; case 2:Putlist(h);break; 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:e

7、xit(0);break; /退出程序/ while(1);退出程序；3上机题二：二叉树1. 动态交互建立二叉树，结点个数任意； 2. 分别用 DLR,LDR,LRD 三种方式对二叉树进行遍历并输出结果； 3. 计算二叉树中结点个数并输出； 4. 计算二叉树深度并输出 源程序：#include &stdio.h&4#include &malloc.hstruct TreeNode int data; struct TreeNode *Lchild ; struct TreeNode *Rchild; ; struct TreeNode *create( ) / 用于建立二叉树的子函数 / st

8、ruct TreeNode *T; int a; scanf(&%d&,a); if (a=0) return NULL; else / 动态建立二叉树 / T=(struct TreeNode *)malloc(sizeof(struct TreeNode); T-data=a; / 建立根结点 / T-Lchild=create( ); / 递归建立左子树 / T-Rchild=create( ); / 递归建立右子树 / return (T); void Pre (struct TreeNode *T) / if (T!= NULL) printf (&%5d&,T-data); / P

9、re (T-Lchild); / Pre (T-Rchild); / void Mid(struct TreeNode *T) / if ( T != NULL) Mid (T-Lchild); / printf(&%5d&,T-data); / 用于进行先序遍历的子函数/ 访问根结点 / 递归访问左子树 / 递归访问右子树/ 用于进行中序遍历的子函数/ 递归访问左子树 / 访问根结点5/ Mid (T-Rchild); void Post (struct TreeNode *T) / if ( T != NULL) Post (T-Lchild); / Post (T-Rchild); pr

10、intf(&%5d&,T-data); void visit(struct TreeNode *T) / 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) / 用于计算

11、叶子结点的子函数 / int a,b; if(T=NULL) return (0); else if(T-Lchild=NULLT-Rchild=NULL) / 判断该结点是叶子结点 / return (1); else a=leaf(T-Lchild); / 递归计算左子树上叶子数 / b=leaf(T-Rchild); / 递归计算右子树上叶子数 / return (a+b+1); int max(int x,int y) if(xy) return (x); else return (y); / 用于取两数的较大值的子函数 /6 int deep(struct TreeNode *T)

12、/ 用于计算二叉树深度的子函数 / int k=0; if(T=NULL) return (0); else if(T-Lchild=NULLT-Rchild=NULL)/ 该结点有孩子， 深度增加 1 / return (1); else return (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&); / 打印菜单

13、 / printf(&2.putout the total number of noden&); printf(&3.putout the depth of the treen&); printf(&4.exitn&); while(1) printf(&nplease input 1-4: &); / 完成菜单的相应功能 / 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

14、); printf(&the depth of the tree is %dn&,p); if(m=4) break; 调试结果：create a tree 1 0 2 5 0 4 0 6 8 96 0 0 0 56 85 0 0 69 0 0 0 2 5 0 0 0 1.visit the tree72.putout the total number of node 3.putout the depth of the tree 4.exitplease input 1-4: the total number of leaves in the tree is 10please input 1-

15、4: please input 1-4: please input 1-4: please input 1-4: please input 1-4: 1 the result of DLR: 85 69 1 5 4 96 8 6 85 56 1 2 5 4 6 8 96 56the result of LDR: 69 2the result of LRD: 2 1968856956645please input 1-4: 2 the total number of leaves in the tree is 10please input 1-4: 38the depth of the tree

16、 is 7please input 1-4: 4 Press any key to continue上机题三图在交互方式下完成下列任务： 1、根据教材上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果； 2、根据教材上算法，完成图的单源最短路径的算法，要求任意给定源点，输出结果 程序：#include stdio.h #include malloc.h #define M 1000 #define VNum 6 struct GLink int No; int Right; struct GLink *Relat; ; int GVNumVNum = 进行初始化 / 1 , 31

17、, 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; / 建 1 / 对图void CreateGLink(int GVNumVNum) 立邻接表 / int i,j; struct GLink *p,*q; for (i=0; iVNum; i+) GLi = q = NULL; for (j=0; jVNum; j+)9 有向路径 /if

18、(i != j) if (Gij 0) (Gij M) / 该两点存在p = (struct GLink *)malloc(sizeof(struct GLink); p-No = j; / 将该点加 p-Right = Gij; if (GLi = NULL) GLi = p; else q-Relat = p; q = p; 入邻接表 / void DFS(int AVNumVNum, int V) / 用于进行深度优先遍历的子函数， V 是起点 / int i; printf(%d &, V); VisitedV = 1; / 将其标记 为已访问 / for (i = 0; i VNum

19、; i+) if (AVi 0) (AVi M) (Visitedi != 1) / 该结点未 被访问过 / DFS(A,i); / 访问该点 / for (i = 0; i VNum; i+) if (Visitedi != 1) DFS(A,i); / 仍有未必访问过的点， 访问该点 / void BFS(int AVNumVNum, int V) / 用于广度优先遍历 的子函数 / int CQVNum; int a=0,b,c; int i,k=1; for (i=0;iVNum;i+) CQi=M; VisitedV = 1; / 标志为访问过 / CQ0=V; printf(&%d

20、 &,V); / 将该结点放 入队列 / while(k6ak) / 仍有结点未被访问并且队列中仍有结点的后继结点 未被访问 / b=CQa;10for(c=0;cVNum;c+) / 依次将队列中以结点为首的邻接表中的结点 插入队列 / if(Visitedc=0AbcMAbc!=0) printf(&%d &, c); CQ+k=c; / 未被访问过， 将其插入 到队列中 / Visitedc=1; / 标志为访问过 / a+; for(i=0;iVNum;i+) if(Visitedi=0) BFS(A,i); void Short(int AVNumVNum,int V) / 用于计算

21、最短路径的子函数， V 是起点 / int DistVNum, PathVNum; int S = 0; int i, k; int wm, u; for (i=0; iVNum; i+) Disti = AVi; / 默认这两点之间即为 最短路径 / if (Disti M) Pathi = V; / 存储该 路径 / 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) / 该两点间 存在路径 / u = i; wm = Disti; S = S |

22、 (1 u); for (i=0; iVNum; i+) if (S (1 i)=0) (Distu + Aui) Disti) Disti = Distu + Aui; / 找到新的 最短路径 / Pathi = u; / 更新路 径长度 / for (i=0; iVNum; i+) / 输出该源结点到其他各点的 最短路径 / if (S (1 i) != 0)11k = i; while ( k != V) printf(%d - &, k); k = Pathk; printf(%d &, V); printf(= %d n&, Disti); else printf(No Path :

23、 %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

24、; i+) Visitedi = 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) p

25、rintf(&please input the source node : &); scanf(&%d&,b); printf(&n The Result of Shortest path is:n&); Short(G,b); if(a=4) break; 12结果调试截图：上机题四检索和排序 在交互方式下完成下列任务： 1、任意给定无序序列，用对半检索法，交互检索任意给定的关键字 KEY； 2、任意给定无序序列，用快速排序法对进行排序，并统计交换次数； 3、任意给定无序序列，用冒泡排序法对进行排序，并统计交换次数和排序的趟数； 程序：#include stdio.h #define M 1

26、00 struct RedType int key; int other; ; int a; int Search ( struct RedType ST, int n, int key) 于进行对半查找的子函数 / 用13 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 STmid.key) high=mid-1; / 待查找值小于

27、中间值，到前一半查找 / else low = mid+1; / 待查找值大于 中间值，到后一半查找 / return (0); int QuickSort(struct RedType L, int low, int high) / 用于快速排序的子函数 / int i, j, t=0; struct RedType temp; if(low = high) / 待排序队列空，结束/ return (0); i = low; j = high; temp = Li; while(i j) while(Lj.key = temp.key) (j i) /从后向前找出第一 个小于关键值的数据/

28、j -; if (i j) Li = Lj; t+; / 交换， 同时交换次数加 1 / while(Li.key = temp.key) (j i) /从前向后找出第 一个大于关键值的数据 / i +; if (i j) Lj = Li; t+; / 交换，同时 交换次数加 1 / Li = temp; printf(&nnThe QukSort Loop%d is : &,i); for (j = 0; j a; j+)14printf(&%d &, Lj.key); return(t+QuickSort(L, low, i-1)+QuickSort(L, i+1, high); /对前后

29、 块分别进行快速排序 / void bubsort(struct RedType L , int n) / 用于冒泡排序的子函数 / int i,j=0,m, fag=1,t=0; struct RedType x; while ( (j n) (fag0) ) fag=0; / 标志有无交换 / for ( i=0; i n-1; i+) if ( Li+1.key Li.key ) / 满足交换条件 / fag+; / 标记发生交换 / x=Li; / 将 相邻数据交换 / Li=Li+1; Li+1=x; t+; / 交换次数加 1 / if(fag) / 输出交换过程 / j+; /

30、排序次数加 1 / for(m=0;mn;m+) printf(&%5d&,Lm.key); printf(&nn&); printf(&the sorted array is: &); / 输出排序完之后的数据 / for(m=0;mn;m+) printf(&%5d&,Lm.key); printf(&n&); printf(&nthe times of sort is: %d&,j); / 给出排序次数 / printf(&nthe total times of exchange is : %dn&,t); / 给出交换次数 /15 main() int b,m,n,i,j; struc

31、t RedType SM,TM; printf(&input the length of the data:&); / 预先给定数据的个数 / 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 sortn&); printf(&3.search the data you want to seen&); printf(&4.exitn&); while(1) / 完成菜单功能 /

32、printf(&nplease input a number from 1 to 4: &); scanf(&%d&,b); if(b=1) for(i=0;ia;i+) Ti.key=Si.key; j=QuickSort( T, 0, a-1); printf(&nthe total times of exchange is :%dn&,j); if(b=2) for(i=0;ia;i+) Ti.key=Si.key; bubsort(T,a); if(b=3) printf(&please input the the key value: &); / 输入欲查找的关键值 / scanf(

33、&%d&,m); n=Search(T,a,m); if(n=0) printf(&cant find the key valuen&); else printf(&the location of the key value is: %dn&, n); if(b=4) break; 结果调试截图：161718心得体会：在这学期的计算机软件技术的实验中，我学会了很多。 一开始拿到实验题目时感觉有点无从下手，后来静下心来慢慢分 析这些题目，发现要用到的知识都是平时学的东西，只是程序比 较复杂，要分成几个部分。于是我在编一个程序前把程序的流程 在纸上整理好，突然间也发现了流程图在这时候的重要性，因为

34、 以前编的程序大多相对简单，思路可以在脑海里记着，现在发现 流程图可以把程序里面的主程序和子程序分清楚，把各个程序段 的嵌套调用关系理清，这是编程序一个很好的方法。 同时还认识到学好语言和学好数据结构有联系，但是却是不 同的两个概念，数据结构是一个新的内容，而语言知识提供一个平 台去描述这个内容的。在认识到这些后，我关掉了其他的网页，认真 的投入实验中，编程，调试，修改，运行，不停的循环，枯燥但也不 乏趣味，错的多也不用怕，那样你可以见到很多没见过的错误，争取 以后避免。 编程，调试，修改，调试再修改，过程也许有些枯燥，但你得 承认，当你运行出结果时，真的很有成就感。以后会更加努力的！19 26