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

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

2、tf(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-next;int Long(linklis

3、t *h) int i=0;linklist *s;s=h;while(s!=NULL) i+;s=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(inext;p2-next=p1-next;free(p1);linklist *Nixu(linklist *h) linklist *r,*q,*p;r=h;p=r-next;q=p-next;if(h=NULL)printf(the linklist is em

4、ptyn); while(q!=NULL&h!=NULL) p-next=r;r=p;p=q;q=q-next;h-next=NULL;p-next=r;return(p);/计算链表的长度 /删除链表中第 k 个结点 /逆序输出链表 / /空表 /返回根结点 /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);printf(3.shu chu lia

5、n 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);elseswitch(x) case 1:h=Creatlist();break;case 2:Putlist(h);break;case 3:printf(lian biao de

6、 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);退出程序；上机题二：二叉树1. 动态交互建立二叉树，结点个数任意；2. 分别用 DLR,LDR,LRD 三种方式对二叉树进行遍历并输出结果；3.计算二叉树中结点个数并输出；4.计算二叉树深度并输出 源程序：#

7、include stdio.h#include malloc.hstruct TreeNode int data;struct TreeNode *Lchild ;struct TreeNode *Rchild;struct TreeNode *create( ) / 用于建立二叉树的子函数 struct 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(

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

9、问根结点/Mid (T-Rchild); / 递归访问右子树 /void Post (struct TreeNode *T) / if ( T != NULL)/ 用于进行后序遍历的子函数 Post (T-Lchild);/ 递归访问左子树/Post (T-Rchild);printf(%5d,T-data); void visit(struct TreeNode *T)/ 递归访问右子树 /Pre(T);/ 用于访问二叉树的子函数/ printf(the result of DLR:);printf(n);printf(the result of LDR:);Mid(T);printf(n)

10、;printf(the result of LRD:);Post(T);printf(n);int leaf(struct TreeNode *T)/ 用于计算叶子结点的子函数/ int a,b;if(T=NULL) return (0);else if(T-Lchild=NULL&T-Rchild=NULL) / 判断该结点是叶子结点 /return (1);else a=leaf(T-Lchild); / 递归计算左子树上叶子数 /b=leaf(T-Rchild);/return (a+b+1);/ 递归计算右子树上叶子数/ 用于取两数的较大值的子函数 /int max(int x,int

11、 y) if(xy) return (x); else return (y);int deep(struct TreeNode *T)/ 用于计算二叉树深度的子函数/ int k=0;if(T=NULL) return (0);else if(T-Lchild=NULL&T-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

12、=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 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 tr

13、ee 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;调试结果：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 tree2. putout the total number of node3. putout the depth of the tree4. exit please input 1-4: the total number of leaves

14、 in the tree is 10 please input 1-4:please input 1-4:please input 1-4:please input 1-4: please input 1-4: 1the result of DLR:125468965685 69the result of LDR:1549686855669 2the result of LRD:96885695664521please input 1-4: 2 the total number of leaves in the tree is 10please input 1-4: 3the depth of

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

16、1, 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,0struct GLink*GLVNum;int VisitedVNum;void CreateGLink(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;p-Right = Gij; if (GLi = NULL) GLi = p;else q-Relat = p;

17、 q = p;/ 将该点加void DFS(int AVNumVNum, int V)/ 用于进行深度优先遍历的子函数，V 是起点 / int i;printf( %d , V);VisitedV = 1;/ 将其标记为已访问 /for (i = 0; i 0) & (AVi M) & (Visitedi != 1)/ 该结点未被访问过 /DFS(A,i); / 访问该点 / 仍有未必访问过的点，for (i = 0; i VNum; i+)if (Visitedi != 1) DFS(A,i);11访问该点 /void BFS(int AVNumVNum, int V) 的子函数 / int

18、 CQVNum;int a=0,b,c;int i,k=1;for (i=0;iVNum;i+)CQi=M;VisitedV = 1;CQ0=V;printf(%d ,V); 入队列 / 用于广度优先遍历/ 标志为访问过 / 将该结点放while(k6&ak) / 仍有结点未被访问并且队列中仍有结点的后继结点 未被访问 / b=CQa;for(c=0;cVNum;c+) / 依次将队列中以结点为首的邻接表中的结点 插入队列 /if(Visitedc=0&AbcM&Abc!=0) printf(%d , c); CQ+k=c;到队列中 / Visitedc=1;a+; for(i=0;iVNum

19、;i+) if(Visitedi=0)BFS(A,i);void Short(int AVNumVNum,int V)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;12for (i=0; iVN

20、um; i+)if (S & (1 i)=0) & (Disti wm)/ 该两点间存在路径 / u = i; wm = Disti;S = S | (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) k = i;while ( k != V) printf( %d - , k); k

21、 = Pathk;printf( %d , V); printf( = %d n, Disti);else printf( No Path : %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

22、 1 to 4 : );scanf(%d,&a);if(a=1) for (i=0; iVNum; 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)13 for (i=0; iVNum; i+) Visitedi = 0; printf(please input the first node: ); scanf(%d,&j);printf(n The Result of BFS is:);BFS

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

24、#define M 100struct RedType int key;int other;int a;int Search ( struct RedType ST, int n, int key) / 用 于进行对半查找的子函数 / 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) / 待排序队列空，结束 /return (0)

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

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

27、f(fag) / 输出交换过程 / 排序次数加 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 / 给出排序次数printf(nthe/ 给出交换次数 main() int b,m,n,i,j;struct RedType SM,TM;printf(input the length / 预先给定数据的个数 /scanf(%d,&a);printf(please input the data n); for(i=0;ia;i+) scanf(%d,&Si.key);printf(n1.quick/ 打印菜单 /times/total times of/ofsortis:exchangeofprintf(2.bub sortn);printf(3.search the data you want to seen);isthej+;/%d,j);%dn,t);data: