《广工数据结构实验报告抽象数据类型.doc》由会员分享，可在线阅读，更多相关《广工数据结构实验报告抽象数据类型.doc（14页珍藏版）》请在三一文库上搜索。
1、 数据结构设计性实验报告 课程名称_数据结构实验 _ 题目名称 树 学生学院_ 计算机学院_ 专业班级 13计科3班 _学 号_ _学生姓名_ _ _指导教师_ _2015 年 7 月 3 日（1）设计任务、要求及所用软件环境或工具；（2）抽象数据类型定义以及各基本操作的简要描述；（3）所选择的存储结构描述及在此存储结构上各基本操作的实现；（4）程序清单（计算机打印），输入的数据及各基本操作的测试结果；（5）实验总结和体会。实验报告以规定格式的电子文档书写、打印并装订，排版及图表要清楚、工整。3.9 思考题 对设计性实验进行总结和讨论，包括本实验的优、缺点，数据存储结构的特点，与其它存储结构之
2、间的比较等。通过总结，可以对抽象数据类型有更全面、深入的认识，这是设计性实验不可缺少的重要内容。这部分内容应作为实验报告中的一个组成部分。1. 题目:树所用软件为VS_2013基本操作：CreateTree(CSTree &T) 功能：创建一棵树 操作结果：输入根节点及孩子，构造一个用户自定义的树。DestroyTree(CSTree &T)初始条件：树T已存在。操作结果：销毁树T。TreeDepth(CSTree T)初始条件：树T已存在。操作结果：返回T的深度 。Empty(CSTree T) 初始条件：判断树T是否为空操作结果：空为返回TURE，不空则返回FALSESearch(CSTr
3、ee T, TElemType e) 初始条件：树T已存在操作结果：查找T的结点e并返回其指针若这样的元素不存在，则返回值为0。LevelOrderTraverse(const CSTree &T) 初始条件：树T已存在 操作结果：层次遍历树T InsertChild(CSTree T, int i, CSTree c) 初始条件：树T已存在且非空，1id+1操作结果：插入树作为T的第i棵子树2 存储结构定义公用头文件Header.h:#include#include#include#define MAX_TREE_SIZE 100#define TRUE 1#define FALSE 0#d
4、efine OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int TElemType;树操作头文件：Treefunction.h:#includeHeader.h#include #include #include /孩子兄弟表示的树typedef struct CSNodechar data;struct CSNode * firstchild, *nextsibling;*CSTree;3. 算法设计TreeFunction.h:#includeHeader.h#include #include #incl
5、ude /孩子兄弟表示的树typedef struct CSNodechar data;struct CSNode * firstchild, *nextsibling;*CSTree;/*-程序中用到的队列-*/typedef CSTree QElemType;/队中的元素 typedef struct QNodeQElemType data;struct QNode *next;QNode, *QueuePtr;/*typedef struct TreeNamechar name;struct CSNode * nametree;struct TreeName *next;TreeName
6、 ,*TreeNameP;*/typedef structQueuePtr front; /队头指针 QueuePtr rear; /队尾指针 LinkQueue;Status InitQueue(LinkQueue &Q)/构造一个空队列 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode);/队头结点 if (!Q.front)exit(OVERFLOW);Q.front-next = NULL;return OK;Status QueueEmpty(const LinkQueue &Q)/若队列为空，则返回TRUE，否则返回FALSE if
7、(Q.rear = Q.front)return TRUE;return FALSE;Status EnQueue(LinkQueue &Q, QElemType e) /插入元素e为Q的新队尾元素 QueuePtr p = (QueuePtr)malloc(sizeof(QNode);if (!p)exit(OVERFLOW);p-data = e;p-next = NULL;Q.rear-next = p;Q.rear = p;return OK;Status DeQueue(LinkQueue &Q, QElemType &e) /若队列不空，则删除Q的队头元素，用e返回其值，并返回OK
8、; if (Q.front = Q.rear)return ERROR; /队空 QueuePtr p = Q.front-next;e = p-data;Q.front-next = p-next;if (Q.rear = p)Q.rear = Q.front;free(p);return OK;/*-*/构造空树void init_cstree(CSNode *T)T-firstchild = NULL;T-nextsibling = NULL;/创建一棵树Status CreateTree(CSTree &T) /创建一棵树 LinkQueue Q;InitQueue(Q);/构造一个空
9、队列 char buffChild10; /用于存放孩子们的缓存 memset(buffChild, 0, 10); /初始化缓存数组，置为NULL printf(请输入树的根结点（字符,以#代表空）:n);scanf_s(%c, &buffChild0,10);if (buffChild0 != #)T = (CSTree)malloc(sizeof(CSNode);/为根结点开辟一个空间 if (!T)exit(OVERFLOW); /开辟失败，终止程序 T-data = buffChild0;T-nextsibling = NULL; /根结点无兄弟 EnQueue(Q, T); /根结
10、点入队 while (!QueueEmpty(Q)QElemType e;DeQueue(Q, e); /结点出队 /CSTree p = e; /用以指向队头结点 printf(请按长幼顺序输入结点%c的孩子(字符,以#结束):n, e-data);fflush(stdin); /清空输入流缓冲区的数据 gets_s(buffChild);/scanf(%s,buffChild); if (buffChild0 != #)/有孩子 CSTree q;q = (CSTree)malloc(sizeof(CSNode); /开辟孩子结点空间 if (!q)exit(OVERFLOW);q-dat
11、a = buffChild0; / e-firstchild = q; /指向第一个孩子 EnQueue(Q, q); /第一个孩子入队 CSTree p = q; /指向刚入队的孩子 for (size_t i = 1; i data = buffChildi; / p-nextsibling = q;EnQueue(Q, q);p = q; /指向刚入队的孩子 p-nextsibling = NULL;else/无孩子 e-firstchild = NULL;elseT = NULL;/空树 return OK;/销毁树void DestroyTree(CSTree T)/树T存在，销毁树
12、T if (T)/树不空 if (T-firstchild)/左子树存在，即销毁以长子为结点的子树 DestroyTree(T-firstchild);if (T-nextsibling)/右子树存在，即销毁以兄弟为结点的子树 DestroyTree(T-nextsibling);free(T); /释放根结点 T = NULL;/返回树的深度int TreeDepth(CSTree T)int dep1=0, dep2=0, dep=0;if (NULL = T)dep = 0;elsedep1 = TreeDepth(T-firstchild);dep2 = TreeDepth(T-nex
13、tsibling);dep = dep1 + 1 dep2 ? dep1 + 1 : dep2;return dep; /创建树CSTree Maketree(TElemType e, int n)int i;CSTree t, p;CSTreep1;va_list argptr; /argptr是存放变长信息的数组t = (CSTree)malloc(sizeof(CSNode);if (NULL = t)return NULL;t-data = e; /根节点的值为et-firstchild = t-nextsibling = NULL;if (n firstchild = p;p1 =
14、p;for (i = 1; i nextsibling = p;p1 = p;va_end(argptr);return t;/判空Status Empty(CSTree T)/树T存在，空树返回TRUE，否则返回FALSE if (T)return TRUE;elsereturn FALSE;/插入第i棵子树Status InsertChild(CSTree T, int i, CSTree c)int j;if (NULL = T | i nextsibling = T-firstchild;T-firstchild = c;/c成为T的第i棵子树elseT = T-firstchild;
15、for (j = 2; T != NULL & j nextsibling;/寻找插入位置if (j = i)c-nextsibling = T-nextsibling;T-nextsibling = c;else return ERROR;/参数i过大return OK;/查找T的结点e并返回其指针CSNode* Search(CSTree T, TElemType e)CSNode* result = NULL;if (NULL = T)return NULL;if (T-data = e)return T;if (result = Search(T-firstchild, e) != N
16、ULL)return result;return Search(T-nextsibling, e);Status LevelOrderTraverse(const CSTree &T)/层次遍历树 LinkQueue Q;InitQueue(Q);if (T)printf(%c, T-data);/访问结点 EnQueue(Q, T);/根结点排队 while (!QueueEmpty(Q)QElemType e, p;DeQueue(Q, e);p = e-firstchild;while (p)printf(%c, p-data);EnQueue(Q, p);p = p-nextsibli
17、ng;return OK;return ERROR;/空树 4测试printf(创建第一棵树:n);CSTree T;CreateTree(T);int select;for (;) printf(select 1 遍历该树 n);printf(select 2 求树的深度n);printf(select 3 查找结点 n);printf(select 4 删除该树 n);printf(select 5 退出 n);printf(select 6 创建一棵树 n);printf(input your select: );scanf_s(%d, &select,1);switch (select
18、) case 1: printf(遍历该树：n);LevelOrderTraverse(T); printf(n); break;case 2:printf(n树的深度为);printf(%d, TreeDepth(T); printf(n); break;case 3:printf(n查找结点：n请输入要查找的结点：n);CSNode* p;TElemType e;for (;)scanf_s(%c, &e, 1);if (e != n)break;p = Search(T, e);if (p=NULL)printf(该结点不存在n); break;if (p-data = e)printf
19、(查找成功n);printf(n); break;case 4:printf(n删除第一棵树n);DestroyTree(T);printf(判空：);int empty;empty = Empty(T);if (empty = 1)printf(该树为空n);else printf(该树不为空n);printf(n); break;case 5: exit(0); case 6:printf(重新创建一棵树n：);CSTree T;CreateTree(T); 创建树，层次遍历，求树的深度：查找结点：删除该树再次创建一棵树：6思考与小结（1）创建树的时候用到了队列的相关方法（2）在算法设计时，要注意判断有关参数值的合法性。（3）遍历树的时候只考虑了层次遍历，但是只有层次遍历是无法知道树的结构的，这个还是需要改进。应该增加先序遍历和中序遍历或者后序遍历。