杭电软件技术基础实验报告.docx

1、软件技术基础上机实验报告 2018至2019学年，第1学期 学生姓名：*班 级：*学 号：*授课教师：*指导教师：* 报告完成时间：2018年12月9日实验一：链式二叉排序树的创建和遍历一实验目的和要求1. 加深理解数据结构的目的和概念，以及逻辑结构和物理结构的关系；2. 练习数据结构操作算法的编程实现；3. 练习链表的程序设计，掌握二叉链表的设计技术；4. 练习递归函数的设计方法；5. 巩固二叉排序树的概念；6. 熟悉软件功能的分析设计方法。二功能分析与设计利用C或C+，设计程序，定义二叉链表，存储二叉排序树，声明并定义相应的函数，实现链式二叉排序树的下列操作：1. 输入数据个数DataCo

2、unt（要求在10和20之间）和数据最大值MaxData（在50和100之间）。算法实现：该任务需要限制输入的DataCount在10和20之间，MaxData在50和100之间，只有当两者均满足要求时，程序才会向下执行。若不满足时，会提示“输入不正确，请重新输入！”，并继续输入DataCount和MaxData，直至满足要求。这里用while(1)死循环，不得到正确输入不退出。部分代码如下：while(1)printf(请输入DataCount:);scanf(%d,&DataCount);printf(请输入Maxdata:);scanf(%d,&Maxdata);if(DataCount

3、=10&DataCount=50&Maxdata=100) break;printf(输入不正确，请重新输入! n);fflush(stdin); /清空输入 2. 在0和MaxData之间，随机产生DataCount个不重复的整数，按产生先后顺序形成一个数据序列，并输出该序列。算法实现：因为输入的DataCount具有随机性，数组的长度无法确定，因此想到要申请分配动态数组。这里需要在0和MaxData之间，随机产生DataCount个不重复的整数，使用c语言中的rand语句，生成一组随机数，并赋值给数组。要保证不重复，引入下表j，若两数相等，则i自减，继续产生数据。部分代码如下： if(ar

4、r=(int *)malloc(DataCount*sizeof(int)=NULL) /申请动态数组 printf(分配内存空间失败，程序退出！); return 0; for(i=0;iDataCount;i+) /向申请成功的数组中赋值 arri=rand()%(Maxdata+1); for(j=0;ji;j+) /保证随机数不重复 if(arri=arrj) i-; printf(输出不重复的数据序列：n); for(i=0;idata = data;(*r)-lchild=NULL;(*r)-rchild=NULL;else if(datadata) /当前值小于根结点，建左子树

5、insertTree(&(*r)-lchild),data);else if(data(*r)-data) /当前值大于根结点，建右子树 insertTree(&(*r)-rchild),data);void Creatree(Tnode *r,int a,int n) /调用插入函数，实现二叉排序树的创建int i;for(i=0;ilchild); /求左子树高度hr = GetHeight(r-rchild);/求右子树高度max = hl hr ? hl : hr;return (max + 1); else return 0;5. 设计函数，输出该二叉树的叶子节点。算法实现：当节点的

6、左右子树同时为空时，即为叶子结点。对二叉树进行遍历，判断被访问的节点是否为叶子节点，若是，将叶子节点对应的数值输出。部分代码如下：if(r=0) return ;else if(r-lchild=NULL&r-rchild=NULL) /节点的左右子树同时为空，即为叶子 printf(%d ,r-data); outleaf(r-lchild) ;outleaf(r-rchild) ;6. 设计中序遍历函数，遍历该二叉排序树，输出遍历序列，验证创建的二叉排序树是否正确。算法实现：首先按中序遍历的顺序递归左子树，然后访问根节点，最后按中序遍历的顺序递归遍历右子树，即可设计中序遍历函数。由于二叉排

7、序树的中序遍历结果应为从小到大排序，所以只需观察中序遍历序列，即可验证正确性。部分代码如下：void inorder(Tnode *r) /定义实现中序遍历的函数 if(r)inorder(r-lchild);printf(%d ,r-data);inorder(r-rchild);三算法流程图根据上述功能的分析，设计出本实验的算法流程图如下所示：图1 算法流程图四程序源代码#include#include#includetypedef struct node /节点数据类型 int data;struct node *lchild,*rchild;Tnode;void insertTree(

8、Tnode *r,int data) /插入二叉排序树if(*r=NULL) /如果树为空，则建树*r=(Tnode *)malloc(sizeof(Tnode);(*r)-data = data;(*r)-lchild=NULL;(*r)-rchild=NULL;else if(datadata) /当前值小于根结点，建左子树 insertTree(&(*r)-lchild),data);else if(data(*r)-data) /当前值大于根结点，建右子树 insertTree(&(*r)-rchild),data);void Creatree(Tnode *r,int a,int n

9、) /调用插入函数，实现二叉排序树的创建int i;for(i=0;ilchild);/求左子树高度 hr = GetHeight(r-rchild);/求右子树高度 max = hl hr ? hl : hr;return (max + 1); else return 0;void outleaf(Tnode *r) /定义输出二叉树的叶子节点的函数if(r=0) return ;else if(r-lchild=NULL&r-rchild=NULL) /节点的左右子树同时为空，即为叶子 printf(%d ,r-data); outleaf(r-lchild) ; outleaf(r-rc

10、hild) ; void inorder(Tnode *r) /定义实现中序遍历的函数 if(r)inorder(r-lchild);printf(%d ,r-data);inorder(r-rchild);int main() srand(time(NULL); Tnode *r=NULL; int DataCount,Maxdata,i,j; int *arr; while(1) /死循环，不得到正确输入不退出 printf(请输入DataCount:); scanf(%d,&DataCount); printf(请输入Maxdata:); scanf(%d,&Maxdata); if(D

11、ataCount=10&DataCount=50&Maxdata=100) break; printf(输入不正确，请重新输入! n); fflush(stdin); /清空输入 if(arr=(int *)malloc(DataCount*sizeof(int)=NULL) /申请动态数组 printf(分配内存空间失败，程序退出！); return 0; for(i=0;iDataCount;i+) /向申请成功的数组中赋值 arri=rand()%(Maxdata+1); for(j=0;ji;j+) /保证随机数不重复 if(arri=arrj) i-; printf(输出不重复的数据

12、序列：n); for(i=0;idata=r-data; copyr-lchild=mycopy(r-lchild); copyr-rchild=mycopy(r-rchild); return copyr; ;3. 通过键盘输入数据，指定查找的目标二叉树（源二叉树和二叉树副本），在目标二叉树中查找是否存在该数据，若存在，则输出提示以及该数据节点的地址，若不存在，则输出提示。算法实现：首先，通过定义变量k，选择查找哪一棵树。k=1，表明在源二叉树中查找；k=2，表明在二叉树副本中查找；k=其他值，提示“选择错误”，并且重新输入，直到查找的二叉树为源二叉树或副本。因为需要在目标二叉树中查找是否存

13、在某数据，所以要定义一个查找节点的函数。这里编写了search函数，首先判断根节点数值与要查找数值是否相等，若等，则输出找到；若不等，则对左子树、右子树递归调用上面函数。部分代码如下：Tnode *search(Tnode *r,int key) /在二叉排序树中查找值为key的节点 if(r=NULL) printf(没有找到！);return NULL; else if(r!=NULL&key=r-data) printf(Find it ! n); printf(输出数据在内存中的地址：); printf(%d,&r); return r; else if(keydata) return

14、 search(r-lchild,key); else if(keyr-data) return search(r-rchild,key);4. 删除数据操作：通过键盘输入数据；如果二叉树副本中存在该数据，则从二叉树副本中删除该数据节点，输出提示，并输出源二叉树和删除操作后的二叉树副本的中序遍历结果和高度；如果二叉树副本中不存在该数据，输出提示，并输出提示源二叉树中是否存在该数据节点以及节点地址。算法实现：对二叉树的节点进行删除操作，要分下面三种情况：1)当删除的节点是叶子节点时，只要把删除节点的父节点对应的指针指向NULL即可，然后释放掉删除节点的空间。2)当删除的节点只有一个子节点(左子树

15、或右子树)，把删除节点的父节点中对应的指针指向删除节点的子节点即可。然后释放掉删除节点的空间;3)当删除的节点左右子树都有，这种情况下，必须要找到一个替代删除节点的替代节点，并且保证二叉树的排序性。根据二叉树的排序性，可知替代节点的键值必须最接近删除节点键值。比删除节点键值小的所有键值中最大那个，或者是比删除节点键值大的所有键值中最小的那个，是符合要求的。这两个键值所在的节点分别在删除节点的左子树中最右边的节点，删除节点右子树中最左边的节点；部分代码如下：/获得其父节点Tnode *getFather(Tnode *r, Tnode *s) Tnode *sf; if(r=NULL|r=s)

16、sf=NULL; else if(s=r-lchild|s=r-rchild) sf= r; else if(s-data r-data) sf=getFather(r-rchild,s); else sf=getFather(r-lchild,s); return sf; /二叉树删除 void DeleteNode(Tnode *r,int key)Tnode *L,*LL; /在删除左右子树都有的结点时使用；Tnode *p=r;Tnode *parent=r;int child=0; /0表示左子树，1表示右子树；if(!r) /如果排序树为空，则退出；return ;while(p)

17、 /二叉排序树有效；if(p-data=key)if(!p-lchild&!p-rchild) /叶结点(左右子树都为空)；if(p=r) /被删除的结点只有根结点；free(p);else if(child=0) parent-lchild=NULL; /设置父结点左子树为空；free(p); /释放结点空间；else /父结点为右子树；parent-rchild=NULL; /设置父结点右子树为空；free(p); /释放结点空间； else if(!p-lchild) /左子树为空，右子树不为空；if(child=0) /是父结点的左子树；parent-lchild=p-rchild;e

18、lse /是父结点的右子树；parent-rchild=p-rchild;free(p); /释放被删除的结点； else if(!p-rchild) /右子树为空，左子树不为空；if(child=0) /是父结点的左子树；parent-lchild=p-lchild;else /是父结点的右子树；parent-rchild=p-lchild;free(p); /释放被删除的结点；elseLL=p; /保存左子树的结点；L=p-rchild; /从当前结点的右子树进行查找；if(L-lchild) /左子树不为空；LL=L;L=L-lchild; /查找左子树；p-data=L-data; /

19、将左子树的数据保存到被删除结点；LL-lchild=L-lchild; /设置父结点的左子树指针为空；for(;L-lchild;L=L-lchild);L-lchild=p-lchild;p-lchild=NULL;elsep-data=L-data;LL-rchild=L-rchild;p=NULL;else if(keydata) /需删除记录的关键字小于结点的数据；/要删除的结点p是parent的左子树；child=0; /标记在当前结点左子树；parent=p;/保存当前结点作为父结点；p=p-lchild; /查找左子树；else /需删除记录的关键字大于结点的数据；/要删除的结点

20、p是parent的右子树；child=1; /标记在当前结点右子树查找；parent=p; /保存当前结点作为父结点；p=p-rchild; /查找右子树；5. 将源二叉树视为一个图数据结构，编写函数实现该图的邻接表存储（注意程序需确保该操作不会被重复操作）。算法实现：首先对每个顶点Vi建立一个单链表，这个单链表由邻接于Vi的所有顶点构成。这个表头节点通常以顺序存储结构存储，以便随机访问任一顶点的链表。6. 编写函数实现该图的拓扑排序，并输出拓扑序列。算法实现：首先在有向图中选取一个没有前驱的顶点(即入度为0的顶点)，并输出该顶点；然后从有向图中删除该顶点和以它为尾的所有弧；重复前两步，直到全

21、部顶点都被输出，或者有向图中没有入度为0的顶点为止。部分代码如下：void TopoSort(adjlist GL,int n) int i,j,k,top,m=0; /*m用来统计拓扑序列中的顶点数*/ struct edgenode *p; /*单链表*/ int *d=(int *)malloc(n*sizeof(int);/*定义存储图中每个顶点入度的一维整形数组d*/ for(i=0;in;i+) di=0; /*初始化数组*/ for(i=0;iadjvex; dj+; p=p-next; top=-1; /*初始化用于链接入度为0的元素的栈的栈顶指针为-1*/ for(i=0;i

22、adjvex; /*vk是vj的一个邻接点*/ dk-; /*vk入度减一*/ if(dk=0) /*把入度为0的元素进栈，对应着图看更容易明白*/ dk=top; top=k; p=p-next; printf(n); if(mn) printf(有回路)； free(d); /*删除动态分配的数组d*/3 算法流程图根据上述功能的分析，设计出本实验的算法流程图如下所示：图1 算法流程图四程序源代码#include#include#include#includetypedef struct node /节点数据类型 int data;struct node *lchild,*rchild;T

23、node;Tnode *mycopy(Tnode*r) /二叉树的复制 if(!r) return NULL; Tnode*copyr=(Tnode*)malloc(sizeof(Tnode); copyr-data=r-data; copyr-lchild=mycopy(r-lchild); copyr-rchild=mycopy(r-rchild); return copyr; ;Tnode *search(Tnode *r,int key) /在二叉排序树中查找值为key的节点 if(r=NULL) printf(没有找到！);return NULL; else if(r!=NULL&k

24、ey=r-data) printf(Find it ! n); printf(输出数据在内存中的地址：); printf(%d,&r); return r; else if(keydata) return search(r-lchild,key); else if(keyr-data) return search(r-rchild,key); /获得其父节点Tnode *getFather(Tnode *r, Tnode *s) Tnode *sf; if(r=NULL|r=s) sf=NULL; else if(s=r-lchild|s=r-rchild) sf= r; else if(s-

25、data r-data) sf=getFather(r-rchild,s); else sf=getFather(r-lchild,s); return sf; /二叉树删除 void DeleteNode(Tnode *r,int key)Tnode *L,*LL; /在删除左右子树都有的结点时使用；Tnode *p=r;Tnode *parent=r;int child=0; /0表示左子树，1表示右子树；if(!r) /如果排序树为空，则退出；return ;while(p) /二叉排序树有效；if(p-data=key)if(!p-lchild&!p-rchild) /叶结点(左右子树

26、都为空)；if(p=r) /被删除的结点只有根结点；free(p);else if(child=0) parent-lchild=NULL; /设置父结点左子树为空；free(p); /释放结点空间；else /父结点为右子树；parent-rchild=NULL; /设置父结点右子树为空；free(p); /释放结点空间； else if(!p-lchild) /左子树为空，右子树不为空；if(child=0) /是父结点的左子树；parent-lchild=p-rchild;else /是父结点的右子树；parent-rchild=p-rchild;free(p); /释放被删除的结点；

27、else if(!p-rchild) /右子树为空，左子树不为空；if(child=0) /是父结点的左子树；parent-lchild=p-lchild;else /是父结点的右子树；parent-rchild=p-lchild;free(p); /释放被删除的结点；elseLL=p; /保存左子树的结点；L=p-rchild; /从当前结点的右子树进行查找；if(L-lchild) /左子树不为空；LL=L;L=L-lchild; /查找左子树；p-data=L-data; /将左子树的数据保存到被删除结点；LL-lchild=L-lchild; /设置父结点的左子树指针为空；for(;L

28、-lchild;L=L-lchild);L-lchild=p-lchild;p-lchild=NULL;elsep-data=L-data;LL-rchild=L-rchild;p=NULL;else if(keydata) /需删除记录的关键字小于结点的数据；/要删除的结点p是parent的左子树；child=0; /标记在当前结点左子树；parent=p;/保存当前结点作为父结点；p=p-lchild; /查找左子树；else /需删除记录的关键字大于结点的数据；/要删除的结点p是parent的右子树；child=1; /标记在当前结点右子树查找；parent=p; /保存当前结点作为父结

29、点；p=p-rchild; /查找右子树；void insertTree(Tnode *r,int data) /插入二叉排序树if(*r=NULL) /如果树为空，则建树*r=(Tnode *)malloc(sizeof(Tnode);(*r)-data = data;(*r)-lchild=NULL;(*r)-rchild=NULL;else if(datadata) /当前值小于根结点，建左子树 insertTree(&(*r)-lchild),data);else if(data(*r)-data) /当前值大于根结点，建右子树 insertTree(&(*r)-rchild),dat

30、a);void Creatree(Tnode *r,int a,int n) /调用插入函数，实现二叉排序树的创建int i;for(i=0;ilchild);/求左子树高度 hr = GetHeight(r-rchild);/求右子树高度 max = hl hr ? hl : hr;return (max + 1); else return 0;void outleaf(Tnode *r) /定义输出二叉树的叶子节点的函数if(r=0) return ;else if(r-lchild=NULL&r-rchild=NULL) /节点的左右子树同时为空，即为叶子 printf(%d ,r-da

31、ta); outleaf(r-lchild) ; outleaf(r-rchild) ; void inorder(Tnode *r) /定义实现中序遍历的函数 if(r)inorder(r-lchild);printf(%d ,r-data);inorder(r-rchild);int main() srand(time(NULL); Tnode *r=NULL,*copyr=NULL,*r1,*r2; int DataCount,Maxdata,i,j,k,m,key,key1; int *arr; while(1) /死循环，不得到正确输入不退出 printf(请输入DataCount:); scanf(%d,&DataCount); printf(请输入Maxdata:); scanf(%d,&Maxdata); if(DataCount=10&DataCount=50&Maxdata=100) break; printf(输入不正确，请重新输入! n); fflush(stdin); /清空输入 if(arr=(int *)malloc(DataCount*sizeof(int)=NULL) /申请动态数组 printf(分配内存空间失败，程序退出！); return 0; for(i=0;iDataCount;i+)