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

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

3、:");scanf("%d",&Maxdata);if(DataCount>=10&&DataCount<=20&&Maxdata>=50&&Maxdata<=100) break;printf("输入不正确，请重新输入! n");fflush(stdin); /清空输入 2. 在0和MaxData之间，随机产生DataCount个不重复的整数，按产生先后顺序形成一个数据序列，并输出该序列。算法实现：因为输入的DataCount具有随机性，数组的长度无法确定，因此想

4、到要申请分配动态数组。这里需要在0和MaxData之间，随机产生DataCount个不重复的整数，使用c语言中的rand语句，生成一组随机数，并赋值给数组。要保证不重复，引入下表j，若两数相等，则i自减，继续产生数据。部分代码如下： if(arr=(int *)malloc(DataCount*sizeof(int)=NULL) /申请动态数组 printf("分配内存空间失败，程序退出！"); return 0; for(i=0;i<DataCount;i+) /向申请成功的数组中赋值 arri=rand()%(Maxdata+1); for(j=0;j<i;

5、j+) /保证随机数不重复 if(arri=arrj) i-; printf("输出不重复的数据序列：n"); for(i=0;i<DataCount;i+) /输出不重复的数据序列 printf("%d t",arri);3. 利用上述数据序列，创建一个二叉排序树。算法实现：首先需要定义节点数据结构，然后根据二叉排序树的特点(左子树节点值小于根节点值，右子树节点值大于等于根节点值)，定义插入二叉排序树的insertTree函数，最后定义Creatree函数，并在其中调用insertTree函数，实现了二叉排序树的创建。部分代码如下：void in

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

7、;(*r)->rchild),data);void Creatree(Tnode *r,int a,int n) /调用插入函数，实现二叉排序树的创建int i;for(i=0;i<n;i+) insertTree(&(*r),ai);4. 设计函数，统计该二叉树的高度。算法实现：二叉树的高度为二叉树中节点层次的最大值，因此需要分别遍历左、右子树，并求高度。二叉树的高度为左子树高度、右子树高度中较大的那个。部分代码如下：int GetHeight(Tnode *r) /定义统计二叉树的高度的函数 int hl, hr, max;if (r!= NULL)hl = GetHe

8、ight(r->lchild); /求左子树高度hr = GetHeight(r->rchild);/求右子树高度max = hl > hr ? hl : hr;return (max + 1); else return 0;5. 设计函数，输出该二叉树的叶子节点。算法实现：当节点的左右子树同时为空时，即为叶子结点。对二叉树进行遍历，判断被访问的节点是否为叶子节点，若是，将叶子节点对应的数值输出。部分代码如下：if(r=0) return ;else if(r->lchild=NULL&&r->rchild=NULL) /节点的左右子树同时为空，即

9、为叶子 printf("%d ",r->data); outleaf(r->lchild) ;outleaf(r->rchild) ;6. 设计中序遍历函数，遍历该二叉排序树，输出遍历序列，验证创建的二叉排序树是否正确。算法实现：首先按中序遍历的顺序递归左子树，然后访问根节点，最后按中序遍历的顺序递归遍历右子树，即可设计中序遍历函数。由于二叉排序树的中序遍历结果应为从小到大排序，所以只需观察中序遍历序列，即可验证正确性。部分代码如下：void inorder(Tnode *r) /定义实现中序遍历的函数 if(r)inorder(r->lchild)

10、;printf("%d ",r->data);inorder(r->rchild);三算法流程图根据上述功能的分析，设计出本实验的算法流程图如下所示：图1 算法流程图四程序源代码#include<stdio.h>#include<stdlib.h>#include<time.h>typedef struct node /节点数据类型 int data;struct node *lchild,*rchild;Tnode;void insertTree(Tnode *r,int data) /插入二叉排序树if(*r=NULL)

11、/如果树为空，则建树*r=(Tnode *)malloc(sizeof(Tnode);(*r)->data = data;(*r)->lchild=NULL;(*r)->rchild=NULL;else if(data<(*r)->data) /当前值小于根结点，建左子树 insertTree(&(*r)->lchild),data);else if(data>(*r)->data) /当前值大于根结点，建右子树 insertTree(&(*r)->rchild),data);void Creatree(Tnode *r,i

12、nt a,int n) /调用插入函数，实现二叉排序树的创建int i;for(i=0;i<n;i+) insertTree(&(*r),ai);int GetHeight(Tnode *r) /定义统计二叉树的高度的函数 int hl, hr, max;if (r!= NULL)hl = GetHeight(r->lchild);/求左子树高度 hr = GetHeight(r->rchild);/求右子树高度 max = hl > hr ? hl : hr;return (max + 1); else return 0;void outleaf(Tnode

13、*r) /定义输出二叉树的叶子节点的函数if(r=0) return ;else if(r->lchild=NULL&&r->rchild=NULL) /节点的左右子树同时为空，即为叶子 printf("%d ",r->data); outleaf(r->lchild) ; outleaf(r->rchild) ; void inorder(Tnode *r) /定义实现中序遍历的函数 if(r)inorder(r->lchild);printf("%d ",r->data);inorder(r-

14、>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(DataCount>=10&&DataCount&l

15、t;=20&&Maxdata>=50&&Maxdata<=100) break; printf("输入不正确，请重新输入! n"); fflush(stdin); /清空输入 if(arr=(int *)malloc(DataCount*sizeof(int)=NULL) /申请动态数组 printf("分配内存空间失败，程序退出！"); return 0; for(i=0;i<DataCount;i+) /向申请成功的数组中赋值 arri=rand()%(Maxdata+1); for(j=0;j<

16、;i;j+) /保证随机数不重复 if(arri=arrj) i-; printf("输出不重复的数据序列：n"); for(i=0;i<DataCount;i+) /输出不重复的数据序列 printf("%d t",arri); Creatree(&r,arr,i);printf("输出二叉树的高度：n"); printf("%dn",GetHeight(r); /输出二叉树的高度 printf("输出二叉树的叶子节点: n");outleaf(r); /输出二叉树的叶子节点pr

17、intf("n"); printf("输出中序遍历序列：n"); inorder(r); /输出中序遍历序列 printf("n"); free(arr); /使用完后要释放所申请的空间 return 0;五调试方法和调试过程调试过程中，出现了大大小小的问题：第一次编译，很多错误，仔细检查后发现是头文件缺失造成的。修改后，错误明显少多了。还有语句后面忘记加分号或者中英文没有区分，导致了一些编译错误。耐心的调试后，所有的错误都解决了。六程序运行主要截图1. 输入DataCount和MaxData，若输入的两个值再指定的范围内(即)，则程

18、序向下执行；若不再指定范围内，则提示重新输入。运行窗口如下：图2 输入正确的数值2. 创建二叉树，输出高度、叶子节点，对二叉排序树进行中序遍历。运行窗口如下：图3 高度、叶子节点、中序遍历七总结与体会这次上机练习，感受之一就是手生，好长时间不用c语言编程，有一种陌生感，所以这次练习调试程序过程中也遇到了大大小小的困难，不过通过自己网上查找资料都解决了。对一些c语言编程用法加深了理解，比如动态分配数组，生成随机数，结构体，递归等内容，现在能够熟练应用，并在实际问题中实现。其次，深刻认识了二叉排序树的结构，运用递归定义函数实现了二叉树的构建，求解树的高度、叶子节点等内容，有关二叉树的三种遍历方法也

19、清楚了具体的遍历顺序。实验二：链式二叉排序树的查找和删除一实验目的和要求1.加深理解数据结构的目的和概念，以及逻辑结构和物理结构的关系；2.锻炼较为复杂数据结构算法的设计和编程实现；3.练习链表的程序设计，掌握二叉链表的设计技术；4.熟悉图结构的物理存储和应用的编程方法；5.熟悉软件功能的分析设计方法和测试方法。二功能分析与设计1. 创建一棵二叉排序树（以下称为源二叉树）。算法实现：创建方法与实验一相同，这里不做叙述。2. 从源二叉树拷贝一个二叉树（以下称为二叉树副本）。算法实现：首先判断二叉树是否为空，若二叉数为空，则没有任何操作；若二叉树不为空，开辟内存空间，依次复制根节点，左子树和右子树

20、，至此完成二叉树的复制。部分代码如下：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; ;3. 通过键盘输入数据，指定查找的目标二叉树（源二叉树和二叉树副本），在目标二叉树中查找是否存在该数据，若存在，则输出提示以及该数据节点

21、的地址，若不存在，则输出提示。算法实现：首先，通过定义变量k，选择查找哪一棵树。k=1，表明在源二叉树中查找；k=2，表明在二叉树副本中查找；k=其他值，提示“选择错误”，并且重新输入，直到查找的二叉树为源二叉树或副本。因为需要在目标二叉树中查找是否存在某数据，所以要定义一个查找节点的函数。这里编写了search函数，首先判断根节点数值与要查找数值是否相等，若等，则输出找到；若不等，则对左子树、右子树递归调用上面函数。部分代码如下：Tnode *search(Tnode *r,int key) /在二叉排序树中查找值为key的节点 if(r=NULL) printf("没有找到！&q

22、uot;);return NULL; else if(r!=NULL&&key=r->data) printf("Find it ! n"); printf("输出数据在内存中的地址："); printf("%d",&r); return r; else if(key<r->data) return search(r->lchild,key); else if(key>r->data) return search(r->rchild,key);4. 删除数据操作：通过键

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

24、都有，这种情况下，必须要找到一个替代删除节点的替代节点，并且保证二叉树的排序性。根据二叉树的排序性，可知替代节点的键值必须最接近删除节点键值。比删除节点键值小的所有键值中最大那个，或者是比删除节点键值大的所有键值中最小的那个，是符合要求的。这两个键值所在的节点分别在删除节点的左子树中最右边的节点，删除节点右子树中最左边的节点；部分代码如下：/获得其父节点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

25、 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) /二叉排序树有效；if(p->data=key)if

26、(!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-&

27、gt;rchild;else /是父结点的右子树；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) /

28、左子树不为空；LL=L;L=L->lchild; /查找左子树；p->data=L->data; /将左子树的数据保存到被删除结点；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(key<p->data) /需删除记录的关键字小于结点的数据

29、；/要删除的结点p是parent的左子树；child=0; /标记在当前结点左子树；parent=p;/保存当前结点作为父结点；p=p->lchild; /查找左子树；else /需删除记录的关键字大于结点的数据；/要删除的结点p是parent的右子树；child=1; /标记在当前结点右子树查找；parent=p; /保存当前结点作为父结点；p=p->rchild; /查找右子树；5. 将源二叉树视为一个图数据结构，编写函数实现该图的邻接表存储（注意程序需确保该操作不会被重复操作）。算法实现：首先对每个顶点Vi建立一个单链表，这个单链表由邻接于Vi的所有顶点构成。这个表头节点通常

30、以顺序存储结构存储，以便随机访问任一顶点的链表。6. 编写函数实现该图的拓扑排序，并输出拓扑序列。算法实现：首先在有向图中选取一个没有前驱的顶点(即入度为0的顶点)，并输出该顶点；然后从有向图中删除该顶点和以它为尾的所有弧；重复前两步，直到全部顶点都被输出，或者有向图中没有入度为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);/*定义存储图中每个顶点入

31、度的一维整形数组d*/ for(i=0;i<n;i+) di=0; /*初始化数组*/ for(i=0;i<n;i+) /*利用数组d中的对应元素统计出图中每个顶点的入度*/ p=GLi; while(p!=NULL) j=p->adjvex; dj+; p=p->next; top=-1; /*初始化用于链接入度为0的元素的栈的栈顶指针为-1*/ for(i=0;i<n;i+) /*建立初始化栈*/ if(di=0) di=top; top=i; while(top!=-1) /*每循环一次删除一个顶点及所有以它为弧尾的顶点入度减一*/ j=top /*j的值为

32、一个入度为0的顶点序号*/ top=dtop; /*得到下一个入度为0的顶点下标*/ printf("%d",j); /*输出一个顶点*/ m+; /*输出的顶点个数加1*/ p=GLj; /*p指向vj顶点邻接表的第一个节点，目的是开始把以它为弧尾的顶点入度减一*/ while(p!=NULL) k=p->adjvex; /*vk是vj的一个邻接点*/ dk-; /*vk入度减一*/ if(dk=0) /*把入度为0的元素进栈，对应着图看更容易明白*/ dk=top; top=k; p=p->next; printf("n"); if(m&

33、lt;n) printf("有回路")； free(d); /*删除动态分配的数组d*/3 算法流程图根据上述功能的分析，设计出本实验的算法流程图如下所示：图1 算法流程图四程序源代码#include<stdio.h>#include<stdlib.h>#include<time.h>#include<string.h>typedef struct node /节点数据类型 int data;struct node *lchild,*rchild;Tnode;Tnode *mycopy(Tnode*r) /二叉树的复制 if(

34、!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&

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

36、sf; if(r=NULL|r=s) 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表

37、示左子树，1表示右子树；if(!r) /如果排序树为空，则退出；return ;while(p) /二叉排序树有效；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); /释放结点空间； el

38、se if(!p->lchild) /左子树为空，右子树不为空；if(child=0) /是父结点的左子树；parent->lchild=p->rchild;else /是父结点的右子树；parent->rchild=p->rchild;free(p); /释放被删除的结点； else if(!p->rchild) /右子树为空，左子树不为空；if(child=0) /是父结点的左子树；parent->lchild=p->lchild;else /是父结点的右子树；parent->rchild=p->lchild;free(p); /

39、释放被删除的结点；elseLL=p; /保存左子树的结点；L=p->rchild; /从当前结点的右子树进行查找；if(L->lchild) /左子树不为空；LL=L;L=L->lchild; /查找左子树；p->data=L->data; /将左子树的数据保存到被删除结点；LL->lchild=L->lchild; /设置父结点的左子树指针为空；for(;L->lchild;L=L->lchild);L->lchild=p->lchild;p->lchild=NULL;elsep->data=L->data;

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

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

42、),data);void Creatree(Tnode *r,int a,int n) /调用插入函数，实现二叉排序树的创建int i;for(i=0;i<n;i+) insertTree(&(*r),ai);int GetHeight(Tnode *r) /定义统计二叉树的高度的函数 int hl, hr, max;if (r!= NULL)hl = GetHeight(r->lchild);/求左子树高度 hr = GetHeight(r->rchild);/求右子树高度 max = hl > hr ? hl : hr;return (max + 1); e

43、lse 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->rchild) ; void inorder(Tnode *r) /定义实现中序遍历的函数 if(r)inorder(r->lchild);printf("

44、%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("

45、;%d",&Maxdata); if(DataCount>=10&&DataCount<=20&&Maxdata>=50&&Maxdata<=100) break; printf("输入不正确，请重新输入! n"); fflush(stdin); /清空输入 if(arr=(int *)malloc(DataCount*sizeof(int)=NULL) /申请动态数组 printf("分配内存空间失败，程序退出！"); return 0; for(i=0;i<

46、;DataCount;i+) /向申请成功的数组中赋值 arri=rand()%(Maxdata+1); for(j=0;j<i;j+) /保证随机数不重复 if(arri=arrj) i-; printf("输出不重复的数据序列：n"); for(i=0;i<DataCount;i+) /输出不重复的数据序列 printf("%d t",arri); Creatree(&r,arr,i);printf("输出源二叉树的高度："); printf("%dn",GetHeight(r); /输出源

47、二叉树的高度 printf("输出源二叉树的叶子节点: ");outleaf(r); /输出源二叉树的叶子节点printf("n"); printf("输出源二叉树中序遍历序列："); inorder(r); /输出源二叉树中序遍历序列 printf("n"); copyr=mycopy(r); /从源二叉树拷贝二叉树副本 printf("输出二叉树副本中序遍历序列："); inorder(copyr); /输出二叉树副本中序遍历序列，并与源二叉树进行比较 printf("n");while(1)printf("如果在源二叉树中查找，请输入1；如果在二叉树副本中查找，请输入2： "