《计算机软件技术基础上机编程》由会员分享，可在线阅读，更多相关《计算机软件技术基础上机编程（26页珍藏版）》请在金锄头文库上搜索。
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;printf(n
2、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 Inp ut 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
3、)inti=0; linklist *s; s=h; while(s!=NULL) i+;s=s-next; return(i);void Delete(linklist *h,int k) inti=0;linklist *p1,*p2;p仁h;if(k=1) h=h-next;free(p1); elsewhile(inext; p2-next=p1-next; free(p1);linklist *Nixu(linklist *h) linklist *r,*q,*p; r=h; p=r-next; q=p-n ext; if(h=NULL) printf(the linklist is
4、 emptyn); while(q!=NULL&h!=NULL) p-n ext=r;r=p; p=q; q=q-n ext; 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 lian b
5、iao 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
6、de chang du shi %d,Long(h);break;case 4:printf(lnput 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=c
8、reate();T-Rchild=create();/建立根结点/递归建立左子树/递归建立右子树return (T);void Pre (struct TreeNode *T) / if (T!= NULL) printf (%5d,T-data); /Pre (T-Lchild);/Pre 仃-Rchild);/用于进行先序遍历的子函数/访问根结点/递归访问左子树/递归访问右子树void Mid(struct TreeNode *T)/用于进行中序遍历的子函数if ( T != NULL) Mid (T-Lchild);/递归访问左子树/printf(%5d,T-data);/访问根结点/M
9、id 仃-Rchild); /递归访问右子树/void Post (struct TreeNode *T)/ if ( T != NULL)/用于进行后序遍历的子函数 Post 仃-Lchild);/递归访问左子树/Post 仃-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); printf(the r
10、esult 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
11、 (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();/ 建立二叉树 /
12、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 leavesin the tree is %dn,n);if(m=3)if(m=3)
13、p=deep(T); printf(the depth of the treeis %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 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:1
