数据结构实验报告 (800字)
- 格式：doc
- 大小：3.23 KB
- 文档页数：3
数据结构及应用算法教程
（实验报告）
专 业 名 称 计算机
班 级计算机1002
姓 名 张星宇
学 号 3101110041
指 导 教 师 王新宇
2011年11月4日
实验目的：
1．进一步掌握指针变量的使用；
2．掌握二叉树的结构特征以及各种存储结构的特点及使用范围。
3．掌握用指针类型描述、访问和处理二叉树的运算；
4．掌握栈或队列的使用。
实验能容：
二叉树的建立，二叉树的遍历。
实验题目:
本实验要求实现以下功能：
1．按前序次序建立一颗二叉树，以‘＃’表示空。
2．中序、后序遍历该二叉树，输出遍历序列。
3．求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。
[测试数据]：
输入以下字符串，建立二叉树：abc##de#g##f###
输出中序遍历序列应为：cbegdfa
输出后序遍历序列应为：cgefdba
输出二叉树的深度应为：5
输出二叉树的叶子数目应为：3
实验原理： # include <stdio.h> # include <stdlib.h> # define ok 1 #
define error -1
# define overflow -1 typedef int elemtype;
typedef int status;typedef struct bitnode {
elemtype data;//此处elem type 根据数据类型实际情况而定 struct bitnode
*lchild,*rchild;//定义左右孩子指针 }bitnode,*bitree;
status createtree(bitree &t)//先序输入二叉树中节点 { char ch;
ch=getchar();
if(ch==#) t=null;
else {
if(!(t=(bitnode *)malloc(sizeof(bitnode))))
exit(overflow);
t->data=ch;
createtree(t->lchild);
createtree(t->rchild); } return ok; } status midtraverse(bitree t)// {
if(t)
{
midtraverse(t->lchild); printf(%c,t->data);}
return ok;
} status posttraverse(bitree t) {
if(t)
{
posttraverse(t->lchild);
posttraverse(t->rchild);
printf(%c,t->data);
}
return ok; }
status countleaf(bitree t,int &count) {
if(t)
{
if((!t->lchild)&&(!t->rchild)) count++;
countleaf(t->lchild,count); countleaf(t->rchild,count);
}
return ok; } int depth(bitree t) {
int depthval=0,depthleft=0,depthright=0;depthval=0;
else
{
depthleft=depth(t->lchild); depthright=depth(t->rchild);
depthval=1+(depthleft>depthright?depthleft:depthright); }
return depthval;
} int main() {
bitree t;
int count=0;//统计叶子数
printf(输入以下字符串，建立二叉树：);
createtree(t); printf(\n);
printf(\n输出中序遍历序列应为：);
midtraverse(t);
printf(\n);
printf(\n输出后序遍历序列应为：);
posttraverse(t);
printf(\n\n);
printf(输出二叉树的叶子数目应为：);
countleaf(t,count);
printf(%d,count);
printf(\n\n);
printf(输出二叉树的深度应为：);printf(%d,depth(t));
printf(\n\n);
return ok;
}
实验总结：
这次的程序实设计实验是对我们学习c++6.0程序设计结果的一次检验。自己动手，自己发现和解决问题。发现了自己的许多不足。平时没有掌握好的知识在这次实验中彻底暴露出来，经过不断思考，不断查阅资料和上机 运行，解决其中大部分问题，当然还存在一些问题没有解决。我相信在以后的学 习能够解决好它们。但是，收获还是不小的，我不仅对c++6.0的操作有了进一步的掌握，还了解到了程序设计的书写风格及其注释的格式。还有一点体会就是，书上和老师教的内容是有限的，我们需要不断地靠自己去学习， 向他人请教，了解和掌握更多的知识，这样我们才能编出更好的c++6.0程序。最后，要感谢学校为我们提供这次实验机会，也要感谢老师的教导和朋友们 对我的帮助与支持。
vi
