}
cout<<"请选择选项:
";
cin>>choice;
}
return0;
}
实验结果
实验分析
在实验过程中,出现了许多大大小小的错误,有的是语法错误,有的是逻辑错误,不过在编程过程中也更加透彻地了解和学习了单链表的存储结构及其函数功能实现,比如计算单链表长度、清空、查找等。
还要掌握没函数功能实现的基本思想和程序思路,掌握单链表操作的实质,灵活运用指针。
下面是编程过程中遇到的部分错误和解决方法:
错误1:
出现下列错误的原因是指针使用不恰当,没正确匹配变量的类型,变量p是定义的LinkList类型的,但是我却使用了一个指针,并不是结点类型。
解决方法:
LinkList*p改为LinkListp
错误2:
计算长度值比实际值少一个,不合逻辑,原因是在写while循环语句的时候判断条件是结点指针为空即为尾结点,但是没有计算最后一个结点,所以比实际值少了1,需要修改判断条件。
错误
解决方法:
把while(p->next!
=NULL)改为while(p!
=NULL),这样要到尾结点的下一个位置才会跳出循环,计数正确。
错误3:
大小写没区分导致运行显示变量未定义,分号缺少,花括号个数不统一,while和if分开的语句的内容没有用括号括起来,逻辑错误使执行结果出错。
解决方法:
认真仔细,注意细节问题,区分大小写,上下对称匹配。
错误4:
在使用后插发建立单链表时,发现插入时会导致整个单链表混乱,原因是在编写后插法时,修改指针前没有先保存结点再修改,出现如下错误:
解决方法:
实验总结
上机实验是时间理论的一个必不可少的环节了,数据结构是一种算法思想,建立在我们已有的C语言和C++的知识基础上,只有通过编程实践才能真正将这种算法思想付诸实践。
编程过程中能够让我们熟悉学习语法规定、掌握程序设计方法、提高程序开发能力。
通过实验我也发现了自己不少的问题,这都是只看书上的程序而没有自己亲身上机编写程序而无法得知的。
我主要存在以下的这些缺点:
1、学习耐心与细心不足,如scanf(“%d”,&n);中的“&”有时候会忘了。
而在最后输出时又错写成printf(“%d”,&n);从而错误得输出了地址而不是我原来想要的答案。
2、编程思想不够发散,看着题目有时想不出解答的方法,更不用说编写程序来解题了。
3、基本功不够,有些函数的表达不太精通,需要看书来核实,以致耗时较多。
4、知识不够广,有些内容没有学好,不能要用到时及时反映出来,认识程度不够深刻。
5、有时候不够精简,有一点用处不大或者说没有也可以的文字存在。
在今后学习中我要更多的动脑,综合运用所学,多看相关东西,多上机练习,增强自学能力,把已会的东西掌握好。
实验中我深刻意识到完成程序的编写,决不意味着万事大吉。
认为万无一失的程序,实际上机运行时可能会出现很多意想不到的问题。
有时编译程序检测出一大堆错误,有时程序能够顺利运行,但是运行结果并不是你预期中想要的。
因为开发环境所提供的编译系统无法发现程序逻辑错误,或者是你原来所设计时的理论错误,这就只能靠自己的上机经验来分析判断错误的所在了。
所以程序的调试是一个技巧性很强的工作,它可能比编一个程序耗时更多。
由此可看出上机实践的重要性。
实验2二叉树基本操作
实验目的
1.熟悉二叉树结点的结构和对二叉树的基本操作。
2.掌握对二叉树每一种操作的具体实现.
3.学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
4.在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法。
5.掌握构造哈夫曼树以及哈夫曼编码的方法。
实验地点
科技图书馆四楼
实验内容
该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。
该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。
/*定义DataType为char类型*/
typedefcharDataType;
/*二叉树的结点类型*/
typedefstructBitNode
{DataTypedata;
structBitNode*lchild,*rchild;
}BitNode,*BitTree;
/*初始化二叉树,即把树根指针置空*/
voidBinTreeInit(BitTree*BT)
/*按先序次序建立一个二叉树*/
voidBinTreeCreat(BitTree*BT)
/*检查二叉树是否为空*/
intBinTreeEmpty(BitTree*BT)
/*按任一种遍历次序(包括按先序、中序、后序、按层次)输出二叉树中的所有结点*/
voidBinTraverse(BitTree*BT)
/*求二叉树的深度*/
intBinTreeDepth(BitTreeBT)
/*求二叉树中所有结点数*/
intBinTreeCount(BitTreeBT)
程序流程图
遍历方式
前序遍历
中序遍历
后序遍历
层次遍历
递归
循环调用“根结点—左孩子—右孩子”
循环调用“左孩子—根结点—右孩子”
循环调用“左孩子—右孩子—根结点”
无
非递归
访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
T是要遍历树的根指针,先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。
T是要遍历树的根指针,先将T入栈,遍历左子树;遍历完左子树返回时,再访问右子树
访问p指向的结点,退出队列,如果左子树不空,将左子树入队,右子树不空,将右子树入队
实验代码
#include
#include
#include
usingnamespacestd;
//二叉树结点
typedefstructBiTNode
{
chardata;//数据
structBiTNode*lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//按先序序列创建二叉树
intCreateBiTree(BiTree&T)
{
chardata;
//按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
scanf("%c",&data);
if(data=='#')
{
T=NULL;
}
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=data;//生成根结点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return0;
}
//输出
voidVisit(BiTreeT)
{
if(T->data!
='#')
{
printf("%c",T->data);
}
}
//先序遍历
voidPreOrder(BiTreeT)
{
if(T!
=NULL)
{
Visit(T);//访问根节点
PreOrder(T->lchild);//访问左子结点
PreOrder(T->rchild);//访问右子结点
}
}
//中序遍历
voidInOrder(BiTreeT)
{
if(T!
=NULL)
{
InOrder(T->lchild);//访问左子结点
Visit(T);//访问根节点
InOrder(T->rchild);//访问右子结点
}
}
//后序遍历
voidPostOrder(BiTreeT)
{
if(T!
=NULL)
{
PostOrder(T->lchild);//访问左子结点
PostOrder(T->rchild);//访问右子结点
Visit(T);//访问根节点
}
}
/*先序遍历(非递归)
思路:
访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,再先序遍历T的右子树。
*/
voidPreOrder2(BiTreeT)
{
stackstack;
BiTreep=T;//p是遍历指针
while(p||!
stack.empty())//栈不空或者p不空时循环
{
if(p!
=NULL)
{
stack.push(p);//存入栈中
printf("%c",p->data);//访问根节点
p=p->lchild;//遍历左子树
}
else
{
p=stack.top();//退栈
stack.pop();
p=p->rchild;//访问右子树
}
}//while
}
/*中序遍历(非递归)
思路:
T是要遍历树的根指针,中序遍历要求在遍历完左子树后,访问根,再遍历右子树。
先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。
*/
voidInOrder2(BiTreeT)
{
stackstack;
//p是遍历指针
BiTreep=T;
//栈不空或者p不空时循环
while(p||!
stack.empty()){
if(p!
=NULL){
//存入栈中
stack.push(p);
//遍历左子树
p=p->lchild;
}
else{
//退栈,访问根节点
p=stack.top();
printf("%c",p->data);
stack.pop();
//访问右子树
p=p->rchild;
}
}//while
}
//后序遍历(非递归)
typedefstructBiTNodePost
{
BiTreebiTree;
chartag;
}BiTNodePost,*BiTreePost;
voidPostOrder2(BiTreeT)
{
stackstack;