搜索
4实验一基于二叉链表的二叉树的实现4.1问题描述基于二叉链表和队列及其堆栈存储结构，实现二叉链表的二叉树的对数据进行各种必要的操作。4.2系统设计1.2.1提供20个功能，分别是：1.2.2二叉链表的结构试一堆栈和队列的形式进行储存的分别是：1.2.3在程序中所定义的数据结构有：2.3系统实现1.3.1InitTree功能初始二叉链表，传入的是头结点地址。申请一个存储空间，并用头结点中的首结点指针指向该空间首地址，相应的时间复杂度为1。具体实现如下：1.3.2DestroyTree功能销毁头结点中首结点址针指向的线性存储空间，传入的是头结点地址。具体实现如下：1.3.3CreateBiTree功能与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值：1.3.4ClearBiTree功能与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值1.3.5BiTreeEmpty功能判空功能，判断表是否为空表。时间复杂度为1，因为只需判断一次就可以知道是否为空。实现如下：1.3.6BiTreeDepth功能求二叉链表深度的功能，由于创建过程中已经把表长信息包含在头结点中，所以直接调用并显示即可1.3.7Root(BiTreeT)功能获取二叉链表的根节点的元素，通过遍历二叉链表中的元素，来逐个判断，时间复杂度为（n）。1.3.8Value(BiTreeT,TElemTypee)功能求指定元素的前一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是递归算法。时间复杂度为O(n)。具体实现如下：1.3.9Assign功能求指定元素的后一个元素的内容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。找到后，把新的数据值赋给所找到的节点。时间复杂度为O(n)。具体实现如下：1.3.10Parent功能找双亲节点，找到后输出1.3.11LeftChild功能查找左孩子，利用递归的算法，与遍历的时间复杂度为相同O(n)1.3.12RightChild功能查找右孩子，利用递归的算法，与遍历的时间复杂度为相同O(n)1.3.13LeftSibling功能查找节点的左边的堂兄弟的，找到后输出该节点的数据1.3.14RightSibling功能查找节点的右边的堂兄弟的，找到后输出该节点的数据1.3.15InsertChild函数在二叉链表中插入新的节点1.3.15DeleteChild功能删除指定编号的数据元素，传入头结点地址、编号i、表结点类型结构体地址来返回被删除元素内容。执行前先判断传入的编号是否在可寻找范围内。执行删除操作之后，进行“移位”运算。时间复杂度仍为O(n)。如下：1.3.16PreOrderTraverse功能前序遍历二叉链表中的数据，采用先遍历左孩子，再访问根节点，后访问右孩子的思想来实现前序遍历的算法的。1.3.17InOrderTraverse功能中序遍历的函数，对二叉链表的数据进行访问，并且利用PreOrderTraverse函数1.3.18PostOrderTraverse功能采用后续遍历的思想，利用先序遍历的函数进行1.3.19LevelOrderTraverse功能完全遍历二叉链表中的数据，并进行输出的1.3.20Point功能定位节点的函数，在需要查找二叉链表二叉树的节点的时候，可以直接调用该函数，进行处理，相应的代码如下1.3.21FILE*fileOpen功能读取功能，通过fscanf实现格式化读取，同时结合CreateList函数实现顺序1.3.22BiTNode*Create(FILE*fp)功能把二叉链表二叉树的数据写入到文件中去1.4效率分析在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。具有同数量级复杂度的功能在实现方法上一般近似。比如InOrderTraverse，PostOrderTraverse，BiTreeDepth，LevelOrderTraverse它们都是基于PreOrderTraverse来设计的，所以效率都是O(n)；而Root，Value，Assign，Parent，LeftChild，RightChild，LeftSiblingRightSibling，InsertChild，DeleteChild是基于VisitPoint，平均效率为O(n)；InitTreeDestroyBiTree所需信息，所以效率为O(1)；CreateBiTreeClearBiTreeBiTreeEmpty都要对二叉链表，平均效率为O(n)。实验总结与评价我做了这个实验发现自己的编程能力很不好，自己的脑袋中有相应的想法和主意，但是因为自己的编程能力很不好也就实现不了自己的想法。二叉链表的二叉树的时候，实现二叉链表线性的对我来说还可以实现，因为线性的所用到方法和技术，在学习十字链表的时候练习的比较少，实现起来难度是很大。特别是有了老师给的框架以后，我们要做的任务就是向里面填我们自己写的函数，在填写的过程中，我深深的感受到了，认真的重要性，因为我在写好调试的中发现了很多，因为自己的不小心和在敲代码的过程中的不认真而造成的很不应该的错误，这些错误也给自己在调试的过程中也造成了很大的麻烦，因为是不认真而犯的错误，因此调试的过程中也很不好发现。对我来说，因为我的C语言的功底很不好，运用指针和链表的能力还没有能达到运用自如，理解深刻的地步，所以在顺序链表的链表的实现中，对我来说是一个很大的挑战，我有很多不会的地方通过自己看书，问室友和上网查询，一点一点的写了出来，肯定现在还是会有很多的问题，但是这也是我一直在努力把它做的更好，在调试的中出现了很多的BUG，自己一个个的慢慢的消除掉了，做出了，现在的程序。如果问自己的体会，那一定是希望我自己以后多多的动手，把以前C语言的书好好再复习一遍，还有就是把现在正在学习的数据结构的书上各个程序，自己要一个个的敲一遍，练习一下自己的熟悉程度。总的来说，我对这次的实验是很有感触的。因为，这次实验让我认识到了，自己的编程能力的低下，如果自己再不下一下功夫的话，那么数据结构的考试自己就十分的危险了。因此，我要加紧复习C语言的知识和数据结构学过的内容，争取自己能在接下来的学习中能有些进步。附录：参考书《数据结构》（C语言版）严蔚敏吴伟民编著《C语言程序设计》曹计昌，李开编著实验心得体会对于这两次的实验，我自己的体会是很深刻的，也是记忆深刻的。因为，正是因为这两次的实验深深地让我认识到了自己的水平是多么的低下，以前，自己还有点夜郎自大的认为，自己对所学的东西，自己掌握的还差不多了呢。但是，经过这次的实验，我真的是清楚的发现自己对所学的知识的掌握还差的很多，自己还有很多的功课要补。第一，以前无论是学习C语言还是数据结构，我的方法是拿着书本看，还有就是拿着练习本写一写，而自己家上机的实践的时间是非常少的，因为我感觉上机得到的结构一定会和自己想的和写的一样呢，显然，我是错误的，因为在这次的实验里我就发现，即使是书上一模一样的代码，在机子上也是有很大的可能出错的，更不用说是自己写的了，在写线性表，线性链表和二叉链表的时候，我出现了用书上的代码不能用的情况，而且是非常严重的错误。有些声明和指针的问题会出现很大的不同。我的体会是，从现在起，重视上机的过程，多书上的程序一定要在机子上跑一下，然后再分析一下，出现这种结果的原因和整个程序的流程。第二，就是实验的时候的规范的问题，由于，自己写代码没有很好的习惯和规则，于是，在自己写好的程序出现错误后自己不能够很快的找到出现错误的位置，比如，对全局变量声明的时候，全局变量的位置问题，在结构和联合声明指针的时候，指针的形式和指针的命名的形式问题，这些错误都有在自己的实验的过程中出现，而且，也给自己带来了很大的麻烦。我的体会是，以后再写程序的时候一定遵守一定的规则和习惯，例如关键词的命名习惯，指针的使用形式和结构联合中的一些形式的问题，应该遵循一定的规则和习惯，因为，只有这样的自己在写好的调试和检查的过程中才不会走那么多的弯路，才会把做事的速度提高上去。最后，就是自己的一些心得体会对这次的实验。做什么事情都要认真对待，无论事情的大小，因为只有这样自己才会养成认真做事的习惯，这次的数据结构的实验让我深深的意识到了这一点。附录：实验三代码：#includestdio.h#includemalloc.h#includestdlib.h#includemath.h#includeassert.h#defineLIST_INIT_SIZE100#defineLISTINCREMENT10#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASTABLE-1#defineOVERFLOW-2#defineMAX_TREE_SIZE100typedefintStatus;typedefintTElemType;//数据元素类型定义,注意这里是整型的，可以使chartypedefTElemTypeSqBiTree[MAX_TREE_SIZE];SqBiTreebt;typedefstruct{TElemType*base;TElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack*S);StatusPop(SqStack*S,TElemTypee);StatusPush(SqStack*S,TElemTypee);StatusStackEmpty(SqStack*S);//全局变量的声明char*m_pCharBuf=NULL;intm_nList[100];intm_nCount=0;char*openFileOnlyRead(char*fileName);voidwriteQuickSortResult(char*pResult);char*openFileOnlyRead(char*fileName){intnLen=0;FILE*pFile=fopen(fileName,r);//打开文件fseek(pFile,0,SEEK_END);//文件指针移到文件尾nLen=ftell(pFile);//得到当前指针位置,即是文件的长度rewind(pFile);//文件指针恢复到文件头位置//动态申请空间,为保存字符串结尾标志\0,多申请一个字符的空间m_pCharBuf=(char*)malloc(sizeof(char)*nLen+1);if(!m_pCharBuf){perror(内存不够!\n);exit(0);}//读取文件内容//读取的长度和源文件长度有可能有出入，这里自动调整nLennLen=fread(m_pCharBuf,sizeof(char),nLen,pFile);m_pCharBuf[nLen]='\0';//添加字符串结尾标志//printf(%s\n,pchBuf);//把读取的内容输出到屏幕fclose(pFile);//关闭文件//free(pchBuf);//释放空间returnm_pCharBuf;}//写入排序完成后的结果voidwriteQuickSortResult(char*pResult){FILE*pFile=fopen(QuickSortResult.txt,w);//打开文件fputs(pResult,pFile);//写入数据fclose(pFile);//关闭文件}typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefBiTreeQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}