数据结构课程实验报告

1、-. z.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.3Cr

2、eateBiTree功能与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值：1.3.4ClearBiTree功能与DestroyBiTree类似但是又有不同，ClearBiTree并不销毁物理空间，而是修改逻辑关系值1.3.5BiTreeEmpty功能判空功能，判断表是否为空表。时间复杂度为1，因为只需判断一次就可以知道是否为空。实现如下：1.3.6BiTreeDepth功能求二叉链表深度的功能，由于创立过程中已经把表长信息包含在头结点中，所以直接调用并显示即可1.3.7Root(BiTree T)功能获取二叉链表的根节点的元素，通过遍历二

3、叉链表中的元素，来逐个判断，时间复杂度为n。1.3.8Value(BiTree T,TElemType e)功能求指定元素的前一个元素的容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。主要思路是递归算法。时间复杂度为O(n)。具体实现如下：1.3.9Assign功能求指定元素的后一个元素的容，传入头结点值、包含指定元素信息的一个临时表结点值、存储前一个元素的表结点地址。找到后，把新的数据值赋给所找到的节点。时间复杂度为O(n)。具体实现如下：1.3.10Parent功能找双亲节点，找到后输出1.3.11LeftChild功能查找左孩子，利用递归的算法，与遍历的

4、时间复杂度为一样O(n)1.3.12RightChild功能查找右孩子，利用递归的算法，与遍历的时间复杂度为一样O(n)1.3.13LeftSibling功能查找节点的左边的堂兄弟的，找到后输出该节点的数据1.3.14RightSibling功能查找节点的右边的堂兄弟的，找到后输出该节点的数据函数在二叉链表中插入新的节点1.3.15DeleteChild功能删除指定编号的数据元素，传入头结点地址、编号i、表结点类型构造体地址来返回被删除元素容。执行前先判断传入的编号是否在可寻找围。执行删除操作之后，进展移位运算。时间复杂度仍为O(n)。如下：1.3.16PreOrderTraverse功能前序

5、遍历二叉链表中的数据，采用先遍历左孩子，再访问根节点，后访问右孩子的思想来实现前序遍历的算法的。1.3.17InOrderTraverse功能中序遍历的函数，对二叉链表的数据进展访问，并且利用PreOrderTraverse函数1.3.18PostOrderTraverse功能采用后续遍历的思想，利用先序遍历的函数进展1.3.19LevelOrderTraverse功能完全遍历二叉链表中的数据，并进展输出的1.3.20Point功能定位节点的函数，在需要查找二叉链表二叉树的节点的时候，可以直接调用该函数，进展处理，相应的代码如下1.3.21FILE * fileOpen功能读取功能，通过fsc

6、anf实现格式化读取，同时结合CreateList函数实现顺序1.3.22BiTNode * Create(FILE *fp)功能把二叉链表二叉树的数据写入到文件中去1.4效率分析在上面介绍各功能时已经提到时间复杂度的计算了，这里再简单分析一下。具有同数量级复杂度的功能在实现方法上一般近似。比方InOrderTraverse，PostOrderTraverse，BiTreeDepth，LevelOrderTraverse它们都是基于PreOrderTraverse来设计的，所以效率都是O(n)；而Root，Value，Assign，Parent，LeftChild，RightChild，Lef

7、tSiblingRightSibling，InsertChild，DeleteChild是基于VisitPoint，平均效率为O(n)； InitTree DestroyBiTree所需信息，所以效率为O(1)；CreateBiTreeClearBiTreeBiTreeEmpty都要对二叉链表，平均效率为O(n)。实验总结与评价我做了这个实验发现自己的编程能力很不好，自己的脑袋中有相应的想法和主意，但是因为自己的编程能力很不好也就实现不了自己的想法。 二叉链表的二叉树的时候，实现二叉链表线性的对我来说还可以实现，因为线性的所用到方法和技术，在学习十字链表的时候练习的比拟少，实现起来难度是很大。

8、特别是有了教师给的框架以后，我们要做的任务就是向里面填我们自己写的函数，在填写的过程中，我深深的感受到了，认真的重要性，因为我在写好调试的中发现了很多，因为自己的不小心和在敲代码的过程中的不认真而造成的很不应该的错误，这些错误也给自己在调试的过程中也造成了很大的麻烦，因为是不认真而犯的错误，因此调试的过程中也很不好发现。对我来说，因为我的C语言的功底很不好，运用指针和链表的能力还没有能到达运用自如，理解深刻的地步，所以在顺序链表的链表的实现中，对我来说是一个很大的挑战，我有很多不会的地方通过自己看书，问室友和上网查询，一点一点的写了出来，肯定现在还是会有很多的问题，但是这也是我一直在努力把它做

9、的更好，在调试的中出现了很多的BUG，自己一个个的慢慢的消除掉了，做出了，现在的程序。 如果问自己的体会，那一定是希望我自己以后多多的动手，把以前C语言的书好好再复习一遍，还有就是把现在正在学习的数据构造的书上各个程序，自己要一个个的敲一遍，练习一下自己的熟悉程度。总的来说，我对这次的实验是很有感触的。因为，这次实验让我认识到了，自己的编程能力的低下，如果自己再不下一下功夫的话，则数据构造的考试自己就十分的危险了。因此，我要加紧复习C语言的知识和数据构造学过的容，争取自己能在接下来的学习中能有些进步。附录：参考书数据构造C语言版严蔚敏 吴伟民编著 C语言程序设计 计昌，开编著实验心得体会对于这

10、两次的实验，我自己的体会是很深刻的，也是记忆深刻的。因为，正是因为这两次的实验深深地让我认识到了自己的水平是多么的低下，以前，自己还有点夜郎自大的认为，自己对所学的东西，自己掌握的还差不多了呢。但是，经过这次的实验，我真的是清楚的发现自己对所学的知识的掌握还差的很多，自己还有很多的功课要补。第一，以前无论是学习C语言还是数据构造，我的方法是拿着书本看，还有就是拿着练习本写一写，而自己家上机的实践的时间是非常少的，因为我感觉上机得到的构造一定会和自己想的和写的一样呢，显然，我是错误的，因为在这次的实验里我就发现，即使是书上一模一样的代码，在机子上也是有很大 的可能出错的，更不用说是自己写的了，在

11、写线性表，线性链表和二叉链表的时候，我出现了用书上的代码不能用的情况，而且是非常严重的错误。有些声明和指针的问题会出现很大的不同。我的体会是，从现在起，重视上机的过程，多书上的程序一定要在机子上跑一下，然后再分析一下，出现这种结果的原因和整个程序的流程。第二，就是实验的 时候的规的问题，由于，自己写代码没有很好的习惯和规则，于是，在自己写好的程序出现错误后自己不能够很快的 找到出现错误的位置，比方，对全局变量声明的时候，全局变量的位置问题，在构造和联合声明指针的时候，指针的形式和指针的命名的形式问题，这些错误都有在自己的实验的过程中出现，而且，也给自己带来了很大的麻烦。我的体会是，以后再写程序

12、的时候一定遵守一定的规则和习惯，例如关键词的命名习惯，指针的使用形式和构造联合中的一些形式的问题，应该遵循一定的规则和习惯，因为，只有这样的自己在写好的调试和检查的过程中才不会走则多 的弯路，才会把做事的速度提高上去。 最后，就是自己的一些心得体会对这次的实验。做什么事情都要认真对待，无论事情的大小，因为只有这样自己才会养成认真做事的习惯，这次的数据构造的实验让我深深的意识到了这一点。附录：实验三代码：#include #include #include #include#include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10#de

13、fine TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASTABLE -1#define OVERFLOW -2#define MA*_TREE_SIZE 100typedef int Status;typedef int TElemType; /数据元素类型定义,注意这里是整型的，可以使chartypedef TElemType SqBiTreeMA*_TREE_SIZE;SqBiTree bt;typedef structTElemType *base;TElemType *top;int stacksize;Sq

14、Stack;Status InitStack(SqStack*S);Status Pop(SqStack*S,TElemType e);Status Push(SqStack*S,TElemType e);Status StackEmpty(SqStack*S);/全局变量的声明char *m_pCharBuf = NULL;int m_nList100;int m_nCount = 0;char* openFileOnlyRead(char * fileName);void writeQuickSortResult(char *pResult);char* openFileOnlyRead(

15、char * fileName) int nLen = 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); e*it(

16、0); /读取文件容/读取的长度和源文件长度有可能有出入，这里自动调整 nLen nLen = fread(m_pCharBuf, sizeof(char), nLen, pFile); m_pCharBufnLen = 0; /添加字符串结尾标志 /printf(%sn, pchBuf); /把读取的容输出到屏幕 fclose(pFile); /关闭文件 /free(pchBuf); /释放空间 return m_pCharBuf;/写入排序完成后的结果void writeQuickSortResult(char *pResult) FILE *pFile = fopen(QuickSort

17、Result.t*t, w); /翻开文件 fputs(pResult, pFile); /写入数据 fclose(pFile); /关闭文件typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef BiTree QElemType;typedef struct QNode QElemType data; struct QNode *ne*t;QNode,*QueuePtr;typedef struct LinkQueue QueuePtr front,rear;Lin

18、kQueue;void InitTree(BiTree*T);void DestroyBiTree(BiTree *T);void CreateBiTree(BiTree *T);Status ClearBiTree(BiTree T);Status BiTreeEmpty(BiTree T);Status BiTreeDepth(BiTree T);Status Root(BiTree T);Status Value(BiTree T,TElemType e);Status Assign(BiTree T,TElemType e,int value);Status Parent(BiTree

19、 T,TElemType e);Status LeftChild(BiTree T,TElemType e);Status RightChild(BiTree T,TElemType e);Status LeftSibling(BiTree T,TElemType e);Status RightSibling(BiTree T,TElemType e);Status InsertChild(BiTree T,int LR,BiTree C);Status DeleteChild(BiTree T,int LR);Status PreOrderTraverse(BiTree T,Status(*

20、Visit)(TElemType e);Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e);Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e);Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e);Status Visit(TElemType e);BiTree Point(BiTree T,TElemType s); /返回二叉树中指向元素值为s的结点的指针void InitQueu

21、e(LinkQueue Q);/构造一个空队列Status QueueEmpty(LinkQueue Q);/判断队列是否为空void EnQueue(LinkQueue Q,QElemType e);/插入元素为新的队尾元素Status DeQueue(LinkQueue Q,QElemType e);/删除队头元素BiTNode * Create(FILE *fp);FILE * fileOpen();void main(void) int i; /文件容读取出来 char *pTe*t = openFileOnlyRead(resource.t*t); printf(%snn, pTe*

22、t); BiTree T; FILE *p; TElemType e; int n; int value; int op=1; while(op)system(cls); printf(nn);printf( Menu for Linear Table On Sequence Structure n);printf(-n);printf( 1. InitTree 11. LeftChildn);printf( 2. DestroyBiTree 12. RightChildn);printf( 3. CreateBiTree 13. LeftSiblingn);printf( 4. ClearB

23、iTree 14. RightSiblingn);printf( 5. BiTreeEmpty 15. InsertChildn);printf( 6. BiTreeDepth 16. DeleteChildn);printf( 7. Root 17. PreOrderTraversen);printf( 8. Value 18. InOrderTraversen);printf( 9. Assign 19. PostOrderTraversen);printf( 10. Parent 20. LevelOrderTraversen);printf( 0. E*itn);printf(-n);

24、 printf( 请选择你的操作020:);scanf(%d,&op); switch(op) case 1: InitTree(&T); BiTNode * Create(p); FILE * fileOpen(); if(!(T)=NULL) printf(n-二叉树初始化成功！n);else printf(二叉树创立失败！n); getchar();getchar(); break; case 2: printf(是否要销毁二叉树！(1为是，0是否)n); scanf(%d,&n); if(n=1) DestroyBiTree(&T); else return 0; if(T!=NULL

25、) printf(n-二叉树成功销毁实现！n);else printf(n-DestroyList功能待实现); getchar();getchar(); break; case 3: /InitTree(&T); printf(Please input the char:e=n); scanf(%d,&e); CreateBiTree(T); if(T)!=NULL) printf(n-CreateBiTree功能实现！n); else printf(n-CreateBiTree功能待实现！n); getchar();getchar(); break; case 4: ClearBiTree

26、(T); if(T) printf(n-ClearBiTree功能待实现！n); else printf(n-ClearBiTree功能实现！n);0- getchar();getchar(); break; case 5: BiTreeEmpty(T); if(T) printf(n-BiTreeEmpty功能实现！n); else printf(n-BiTreeEmpty功能待实现！n); getchar();getchar(); break; case 6: BiTreeDepth(T); if(T) printf(n-BiTreeDepth功能实现！n); else printf(n-

27、BiTreeDepth功能待实现！n); getchar();getchar(); break; case 7: Root(T); if(T) printf(n-Root功能实现！n); else printf(n-Root功能待实现！n); getchar();getchar(); break; case 8: printf(Please input the node of you want:e=n); scanf(%c,&e); Value(T,e); if(T=NULL) printf(n-Value功能实现！n); else printf(n-Value功能待实现！n); getcha

28、r();getchar(); break; case 9: printf(Please input the node and number of you want:e=nvalue=n); scanf(%c%d,&e,&value); Assign(T,e,value); if(T=NULL) printf(n-Assign功能实现！n); else printf(n-Assign功能待实现！n); getchar();getchar(); break; case 10: printf(Please input the node of you want:e=n); scanf(%c,&e);

29、Parent(T,e); if(T=NULL) printf(n-Parent功能实现！n); elseprintf(n-Parent功能待实现！n); getchar();getchar(); break; case 11: printf(Please input the node of you want:e=n); scanf(%c,&e); LeftChild(T,e); if(T!=NULL) printf(n-LeftChild功能实现！n); else printf(n-LeftChild功能待实现n); getchar();getchar(); break; case 12: p

30、rintf(Please input the node of you want:e=n); scanf(%c,&e); RightChild(T,e); if(T!=NULL) printf(n-RightChild功能实现n); else printf(n-RightChild功能待实现！n); getchar();getchar(); break; case 13: printf(Please input the node of you want:e=n); scanf(%c,&e); LeftSibling(T,e); if(T!=NULL) printf(n-LeftSibling功能

31、实现！n); else printf(n-LeftSibling功能待实现n); getchar();getchar(); break; case 14: printf(Please input the node of you want:e=n); scanf(%c,&e); RightSibling(T,e); if(T!=NULL) printf(n-LeftSibling功能实现！n); else printf(n-LeftSibling功能待实现！n); getchar();getchar(); break; case 15: /printf(Please input the node

32、 of you want:p,e,LR and C=n); / scanf(%c,&e); / InsertChild(T,P,LR,C); printf(线性表是空表！n); getchar();getchar(); break; case 16: printf(线性表是空表！n); getchar();getchar(); break; case 17: printf(线性表是空表！n); getchar();getchar(); break; case 18: printf(线性表是空表！n); getchar();getchar(); break; case 19: printf(Pl

33、ease input the node of you want:e=n); scanf(%c,&e); PostOrderTraverse(T,e); if(T!=NULL) printf(功能实现了！n);elseprintf(功能待实现了！n); getchar();getchar(); break; case 20: printf(线性表是空表！n); getchar();getchar(); break; case 0: break;/end of switch /end of while char result1000 = QuickSortResult: ; for(i = 0;

34、i data=NULL;return OK; void DestroyBiTree(BiTree *T) if(T!=NULL) DestroyBiTree(*T)-lchild); DestroyBiTree(*T)-rchild); free(T); T=NULL; return OK; void CreateBiTree(BiTree *T) /* 算法6.4:按先序次序输入二叉树中结点的值可为字符型或整型，在主程中 */ /* 定义，构造二叉链表表示的二叉树T。变量Nil表示空子树。有改动 */ TElemType ch; #ifdef CHAR scanf(%c,&ch); #end

35、if #ifdef INT scanf(%d,&ch); #endif if(ch= ) /* 空 */ *T=NULL; else *T=(BiTree)malloc(sizeof(BiTNode); if(!*T) e*it(OVERFLOW); (*T)-data=ch; /* 生成根结点 */ CreateBiTree(&(*T)-lchild); /* 构造左子树 */ CreateBiTree(&(*T)-rchild); /* 构造右子树 */ Status ClearBiTree(BiTree T) BiTree pl,pr; if(T=NULL) return ; if(T)

36、 pl=T-lchild; pr=T-rchild; T-lchild=NULL; T-rchild=NULL; free(T); T=NULL; ClearBiTree(pl); ClearBiTree(pr); return OK;Status BiTreeEmpty(BiTree T) if(T=NULL) return TRUE; else return FALSE;Status BiTreeDepth(BiTree T) int lchildHigh,rchildHigh; if(T=NULL)return 0; else lchildHigh=BiTreeDepth(T-lchil

37、d); rchildHigh=BiTreeDepth(T-rchild); return lchildHighrchildHigh (lchildHigh+1):(rchildHigh+1);Status Root(BiTree T) if(T=NULL)return ERROR; printf(%c,T-data); Root(T-lchild); Root(T-rchild); return OK;Status Value(BiTree T,TElemType e) if(T=NULL)return ERROR; else if(T-data=e)return (T-data); Valu

38、e(T-lchild,e); Value(T-rchild,e); return OK; Status Assign(BiTree T,TElemType e,int value) if(T=NULL)return ERROR; if(T-data=e) T-data=value; else Assign(T-lchild,e,value); Assign(T-rchild,e,value); return OK;Status Parent(BiTree T,TElemType e) if(T=NULL)return ERROR; if(T-data=e) if(T-lchild | T-rc

39、hild) return (T-data); else Parent(T-lchild,e); Parent(T-rchild,e); return OK;Status LeftChild(BiTree T,TElemType e) if(T=NULL) return; if(T-data=e) if(!(T-lchild) printf(%c,T-lchild); else return NULL; else T-lchild; LeftChild(T-lchild,e); T-rchild; LeftChild(T-rchild,e); return OK;Status RightChil

40、d(BiTree T,TElemType e)if(T=NULL) return; if(T-data=e) if(!(T-rchild) printf(%c,T-rchild); else return NULL; else T-lchild; RightChild(T-lchild,e); T-rchild; RightChild(T-rchild,e); return OK;Status LeftSibling(BiTree T,TElemType e) /返回左兄弟 TElemType a; BiTree p; if(T) a=Parent(T,e);/a为e的双亲 if(a!=NUL

41、L) p=Point(T,a);/p指向结点a的指针 if(p-lchild&p-rchild&p-rchild-data=e)/p存在左右孩子而且右孩子是e return p-lchild-data; return NULL;Status RightSibling(BiTree T,TElemType e)TElemType a; BiTree p; if(T) a=Parent(T,e);/a为e的双亲 if(a!=NULL) p=Point(T,a);/p为指向结点的a的指针 if(p-lchild&p-rchild&p-lchild-data=e) return p-lchild-da

42、ta; return NULL;Status InsertChild(BiTree T,int LR,BiTree C) if(T) if(LR=0) C-rchild=T-lchild; T-lchild=C; else C-rchild=T-rchild;/T指结点的原有右子树成为C的右子树 T-rchild=C; return OK; return ERROR;Status DeleteChild(BiTree T,int LR) if(T) if(LR=0)DestroyBiTree(T-lchild);else DestroyBiTree(T-rchild);return OK;re

43、turn ERROR;Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e) Status PrintElement(TElemType e) printf(e); return OK; if(T) if(Visit(T-data) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /PreOrderTraaverseStatus InOrderTrave

44、rse(BiTree T,Status(*Visit)(TElemType e) Status PrintElement(TElemType e) printf(e); return OK; if(T) if(PreOrderTraverse(T-lchild,Visit) if(Vist(T-data); if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /InOrderTraverseStatus PostOrderTraverse(BiTree T,Status(*Visit)(TEl

45、emType e) Status PrintElement(TElemType e) printf(e); return OK; if(T) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) if(Vist(T-data) return OK; return ERROR; else return OK; /PostOrderTraverseStatus LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e) BiTree p,newNode; S

46、tatus PrintElement(TElemType e) printf(e); return OK; if(T) if(p=T-lchild) newNode=(BiTree)malloc(sizeof(BiTNode); newNode-data=e; newNode-rchild=NULL; newNode-lchild=p; T-lchild=newNode; else return ERROR; else return ERROR; return OK;/LevelOrderTraverse/Status Visit(TElemType e)/ printf(%c,e);/BiT

47、ree Point(BiTree T,TElemType s)/返回二叉树T中指向元素值为S的结点指针 LinkQueue q; QElemType a; if(T) InitQueue(q);/初始化队列 EnQueue(q,T);/根指针入队 while(!QueueEmpty(q)/队不空 DeQueue(q,a);/出队，队列元素赋给e if(a-data=s)/a所指结点为的值为s return a; if(a-lchild)/有左孩子 EnQueue(q,a-lchild);/入队左孩子 if(a-rchild)/有右孩子 EnQueue(q,a-rchild);/入队右孩子 return NULL;void I