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

计算机软件技术基础上机编程上机题一：线性表1. 建立单向链表；表长任意；2. 可交互输出单链表中的内容；3. 编写算法计算出自己所建单链表的长度并输出；4. 输出自己所建立单链表中的第K个结点，并将剩余结点输出；5. 将单链表倒排并输出结果#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 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(linklist *h) /计算链表的长度/ int i=0; linklist *s; s=h; while(s!=NULL) i+; s=s-next; return(i); void Delete(linklist *h,int k) /删除链表中第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 emptyn); / /空表/ while(q!=NULL&h!=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); 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); 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);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:exit(0);break; /退出程序/ while(1);退出程序；上机题二：二叉树1. 动态交互建立二叉树，结点个数任意；2. 分别用DLR,LDR,LRD三种方式对二叉树进行遍历并输出结果；3. 计算二叉树中结点个数并输出；4. 计算二叉树深度并输出源程序：#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( ); / 递归建立左子树 / 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); / 访问根结点 / 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) / 用于访问二叉树的子函数 / 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) / 用于计算叶子结点的子函数 / 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 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=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 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; 调试结果：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.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 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上机题三 图在交互方式下完成下列任务：1、根据教材上算法，完成图的深度和广度优先遍历，要求任意给定起始点，输出结果；2、根据教材上算法，完成图的单源最短路径的算法，要求任意给定源点，输出结果程序：#include #include #define M 1000#define VNum 6struct GLink int No; int Right; struct GLink *Relat; ;int GVNumVNum = 1 / 对图进行初始化 / 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 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; 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); / 仍有未必访问过的点，访问该点 / 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 ,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;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; for (i=0; iVNum; 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 = 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 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) 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 source node : ); scanf(%d,&b); printf(n The Result of Shortest path is:n); Short(G,b); if(a=4) break; 结果调试截图：上机题四 检索和排序在交互方式下完成下列任务：1、任意给定无序序列，用对半检索法，交互检索任意给定的关键字KEY；2、任意给定无序序列，用快速排序法对进行排序，并统计交换次数；3、任意给定无序序列，用冒泡排序法对进行排序，并统计交换次数和排序的趟数； 程序：#include #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); 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+QuickSort(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.key Li.key ) / 满足交换条件 / fag+; / 标记发生交换 / x=Li; / 将相邻数据交换 / Li=Li+1; Li+1=x; t+; / 交换次数加1 / if(fag) / 输出交换过程 / j+; / 排序次数加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); / 给出交换次数 / main() int b,m,n,i,j; struct 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 so