∪∩deniable Design

个人JAVA版GAE(google app engine),struts2+jpa+jQuery开发,互相交流 http://iunbug.appspot.com/
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Visual C++ 6.0调试功能 图解教程(3)--实例二

Posted on 2008-08-19 17:30 ∪∩BUG 阅读(1842) 评论(2)  编辑  收藏 所属分类: VC++/MFC学习笔记

树和二叉树

  1. 实验目的

1.熟悉二叉树的二叉链表存储结构；

2.掌握构造二叉树的方法；

3.加深对二叉树的遍历的理解。

二.需求分析

    本程序演示用C++编写,完成按先序遍历生成二叉树,先序遍历打印输出二叉树, 后序遍历打印输出二叉树, 中序遍历打印输出二叉树, 层序遍历打印输出二叉树, 先序遍历方法交换左右子树,求树的高度,求树的叶子结点个数.

输入值的范围:建立一棵二叉时,要求结点的的左右孩子为空时输入0代替.所有输入值必须为整形.输入的结点个数:若为单边二叉树(全只有左结点或全只有右结点)则为任意个数;若非单边二叉则要求结点最多的层个数不得超过MAXSIZE的值.

输出形式:输出时如果结点的左右指针这空则以" #"代替输出.

程序所能完成的功能:程序能完成按先序遍历生成二叉树,先序遍历打印输出二叉树, 后序遍历打印输出二叉树, 中序遍历打印输出二叉树, 层序遍历打印输出二叉树, 先序遍历方法交换左右子树,求树的高度,求树的叶子结点个数.操作.

测试数据

A建立二叉树中输入1230000 生成一棵树123####

B交换左右子树得到一棵二叉树1#2#3##

C按层序遍历树得到一棵二叉树1#2#3##

D求二叉树的高度得到高度3

E求叶子结点个数得到个数1

三.设计概要

(1)为了实现上述程序的功能,需要定义二叉树的抽象数据类型:

ADT BiTree is{

数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
数据关系：R={<ai,ai+1>|ai,ai+1 ∈D}

基本操作:

creat()

操作结果:建立一棵二叉树

preorder()

初始条件:二叉树已经存在

操作结果:先序遍历显示二叉树

preordertswap()

初始条件: 二叉树已经存在

操作结果:交换二叉树的左右子树

theight()

初始条件: 二叉树已经存在

操作结果:输出二叉树的高度

tleaves()

初始条件:

操作结果:输出二叉树的叶子结点个数

levelorder()

初始条件: 二叉树已经存在

操作结果:层序遍历显示二叉树

}ADT BiTree

(2) 本程序包含两个类和一个结构体类型

A基类:队列类SeQueue有5个函数

    1.构造函数                            SeQueue()

    2.析构函数                            ~SeQueue()

    3.进队函数                            AddQ(NodeType x)

    4.出队函数                            DelQ()

    5.判断非空函数                            IsEmpty()

B派生类:二叉树类BiTree有20个函数

    1主函数                                main()

2. 构造函数                            BiTree()

    3. 析构函数                            ~BiTree()

    4. 建立树函数                            creat0()

    5. 先序遍历函数                        void preorder()

    6. 中序遍历函数                        inorder()

    7. 后序遍历函数                        postorder()

    8.层序遍历函数                            levelorder()

    9. 交换左右子树函数                    preordertswap()

    10. 求二叉树高度函数                    theight()

    11. 求二叉树叶子结点个数函数                tleaves()

    12. 建立二叉树递归算法函数                *creat()

    13. 先序遍历递归算法函数                preorder(NodeType *p)

    14. 中序遍历递归算法函数                inorder(NodeType *p)

    15. 后序遍历递归算法函数                postorder(NodeType *p)

    16. 按层遍历算法函数                    levelorder(NodeType *p)

    17. 先序遍历方法交换左右子树函数            preorderswap(NodeType *p)

    18. 求二叉树高度递归算法函数                height(NodeType *p)

    19. 求二叉树叶子结点个数的递归算法函数    leaves(NodeType *p)

    20. 删除二叉树所有结点函数                destroy(NodeType* &p)

C结构体类型NodeType

(3)本程序的三个文件

1.头文件BiTree.h

2.源文件     Queue.cpp

        BiTree.cpp

(4)函数之间的关系

 

 

四.详细设计

 

  1//BiTree.h
  2//#include <iostream.h>
  3#include <iostream>    // Visual Studio 2008中要求的
  4#include "stdlib.h"
  5#define MAXSIZE 2    
  6typedef int ElemType;
  7using namespace std;    // Visual Studio 2008中要求的
  8
  9struct NodeType                           //定义结点结构体
 10{       
 11    ElemType   data;                    
 12    NodeType  *lch,*rch;
 13};
 14
 15//队列
 16class SeQueue                                //定义队列类SeQueue
 17{  
 18private:
 19       NodeType elem[MAXSIZE];        //存储队列的数组个数
 20        int front,rear;                //队头,队尾
 21public:
 22        SeQueue();
 23        ~SeQueue();
 24        void AddQ(NodeType x);        //入队函数
 25        NodeType DelQ();            //出队函数
 26        int IsEmpty()                //判断队列非空函数
 27        {
 28            return front == rear;
 29        }
 30};
 31
 32//二叉树
 33class BiTree:public SeQueue              //定义二叉树类BiTree 作为队列类SeQueue的派生类
 34{
 35 public:
 36     BiTree(){    root = NULL;    }                //构造函数
 37     ~BiTree(){    destroy(root);    }        //析构函数
 38     void preorder()                    //先序遍历
 39     {        preorder(root);        }
 40     void inorder()                          //中序遍历
 41      {     inorder(root);  }                
 42     void postorder()                     //后序遍历
 43     {        postorder(root);    }
 44
 45     void preordertswap()                   //交换左右子树
 46      {     preorderswap(root);  }
 47     int  theight()                          //求二叉树高度
 48      {     return height(root);  }
 49     int tleaves()                         //求二叉树叶子结点个数
 50     {        return leaves( root );    }
 51     void levelorder()                       //按层遍历
 52     {        levelorder(root);    }    
 53      void creat0();                        //建立树函数
 54  private:
 55     NodeType *root;                    //数据成员，根结点
 56     NodeType *creat();                    //建立二叉树递归算法
 57    void    preorder(NodeType *p);            //先序遍历递归算法
 58     void    inorder(NodeType *p);            //中序遍历递归算法
 59    void    postorder(NodeType *p);            //后序遍历递归算法
 60    void    levelorder(NodeType *p);            //按层遍历算法
 61     void    preorderswap(NodeType *p);       //利用先序遍历方法交换左右子树
 62     int    height(NodeType *p);            //求二叉树高度递归算法
 63    int    leaves(NodeType *p);            //求二叉树叶子结点个数的递归算法
 64     void destroy(NodeType* &p);            //删除二叉树所有结点
 65};
 66
 67//BiTree.cpp
 68#include "BiTree.h"
 69
 70void  BiTree::creat0()                         //建立树函数，
 71   {  
 72    cout << "请按照树的先序遍历顺序组织数据" << endl;
 73     cout << "若结点信息是int，把每个结点的空孩子以输入;" << endl;
 74     cout << "一个结点的二叉树，输入：0 0;" << endl;
 75     root = creat();          //调用私有creat()(工具函数);
 76     }
 77NodeType * BiTree::creat()      //递归建立二叉树算法
 78{ 
 79    NodeType *p;   
 80    ElemType x;
 81    cout << "\n 输入数据："; 
 82    cin >> x;
 83    if( x == 0 )        //若左或右孩子为空,置当前指针这空.
 84        p = NULL;
 85    else {
 86            p = new NodeType; 
 87            p->data = x;
 88            p->lch = creat();                  //递归调用自身
 89            p->rch = creat();
 90          }
 91   return p;
 92}
 93
 94//先序遍历递归算法
 95void BiTree::preorder(NodeType *p)              //先序遍历显示
 96{
 97    if( p != NULL)
 98    {
 99        cout << p->data;
100        preorder( p->lch );        //递归调用自身
101        preorder( p->rch );        //递归调用自身
102    }
103    else
104        cout <<"#";
105}
106//中序遍历递归算法
107void BiTree::inorder(NodeType *p)     //中序遍历显示
108{  
109 
110    if( p != NULL )
111    {
112        inorder( p->lch );        //递归调用自身
113        cout << p->data;
114        inorder( p->rch );        //递归调用自身
115    }
116    else
117        cout << "#";    
118
119}
120//后序遍历递归算法
121void BiTree::postorder(NodeType *p)
122{
123    if( p != NULL )
124    {
125        
126        postorder( p-> lch );        //递归调用自身
127        postorder( p-> rch );        //递归调用自身
128        cout << p->data;
129    }
130    else
131        cout <<"#";
132}
133void BiTree::preorderswap(NodeType *p)         //利用先序遍历方法交换左右子树
134{      
135    if( p != NULL )
136    {       
137        NodeType *r; 
138        r = p->lch;
139        p->lch = p->rch; 
140        p->rch = r;
141//上面几条语句可以认为对结点的访问（交换左右孩子）
142//替换了原来的：cout<<p->data<<" ";  语句
143        preorderswap( p->lch );        //递归调用自身
144        preorderswap( p->rch );
145    }
146}
147void  BiTree::destroy(NodeType* &p)            //删除二叉树所有结点
148{
149    if(p != NULL)
150    {    destroy( p->lch );
151        destroy( p->rch );
152        delete p;
153        p = NULL;
154    }
155}
156int BiTree::height(NodeType *p)                //求二叉树高度递归算法
157{       
158    int hl,hr;
159    if( p != NULL )
160    {
161        hl = height( p->lch );
162        hr = height( p->rch );
163        return ( hl > hr ? hl : hr ) + 1;        //当前结点高度是以最大的(左右)子树的高度加得到
164        
165    }
166    else
167        return 0;
168
169}
170//求二叉树叶子结点个数的递归算法
171int BiTree::leaves(NodeType *p)
172{
173    if( p == NULL )            //当前结点是否为空,当为空时就没有左右孩子
174        return 0;
175    if( ( p-> lch == NULL ) && ( p-> rch == NULL ))    //当前结点是否有左右孩子
176    {
177        return 1;
178    }
179    return leaves( p-> lch ) + leaves( p-> rch );    //递归调用自身累加叶子结点个数
180}
181
182//按层遍历算法
183void BiTree::levelorder(NodeType *p)
184{
185    SeQueue q;            //初始化一个队列
186    NodeType *t = p;
187    if (p)
188    {
189        q.AddQ(*p);        //根结点非空则入队
190    }
191    while (!q.IsEmpty())
192    {
193        t = &(q.DelQ());    //队非空则将结点指针出队
194        cout << t->data;    //并打印输出结点的数据值
195        if (t->lch)
196        {
197            q.AddQ(*(t->lch));    //存在左孩子则将其进队
198        }
199        else
200            cout << "#";
201
202        if (t->rch)
203        {
204            q.AddQ(*(t->rch));    //存在右孩子则将其进队
205        }
206        else
207            cout << "#";
208    }
209}
210
211//---------------------------------------------------------------------------
212int main()
213{ 
214  int k;    
215  BiTree root0;                     //声明创建二叉树对象，调用构造函数
216  do{ cout<<"\n\n";
217      cout<<"\n\n     1. 建立二叉树";
218      cout<<"\n\n     2. 交换左右子树";
219      cout<<"\n\n     3. 按层序遍历树";  
220      cout<<"\n\n     4. 求二叉树深度 ";
221      cout<<"\n\n     5. 求叶子结点个数";  
222      cout<<"\n\n     6. 结束程序运行";
223      cout<<"\n======================================";
224      cout<<"\n     请输入您的选择(0,1,2,3,4,5,6):"; 
225      cin>>k;
226      switch(k)
227         {  
228          case 1:{  
229                    cout << "\n\t 输入（0）结束：";
230                    root0.creat0();
231                     cout << "\n\t 先序遍历结果:";
232                    root0.preorder();
233                    cout << "\n\t 中序遍历结果:"; 
234                    root0.inorder();
235                    cout << "\n\t 后序遍历结果:"; 
236                    root0.postorder();                    
237                   } break;
238           case 2:{  
239                    cout <<"\n\t 交换左右子树结果:";
240                    root0.preordertswap();
241                    cout << "\n\t 先序遍历结果:";
242                    root0.preorder();             
243                    cout << "\n\t 中序遍历结果:";
244                    root0.inorder();
245                    cout << "\n\t 后序遍历结果:"; 
246                    root0.postorder();    
247                   } break;
248           case 3:{  
249                    cout << "\n\t 按层序遍历结果:";
250                    root0.levelorder();    
251                   } break;   
252           case 4:{  
253                   int deep;
254                   deep = root0.theight();
255                   cout << "\n\t 树的深度是:" << deep;
256                  } break;
257           case 5:{
258                    int leaf;
259                    leaf = root0.tleaves();
260                    cout << "\n\t 树的叶子结点个数是:" << leaf;
261                  } break;
262           case 6: exit(0);
263          } //  switch
264cout<<"\n ----------------";
265      } while(k>=0 && k<6); 
266   return 0;
267}//-----  
268
269//Queue.cpp
270#include "BiTree.h"
271SeQueue::SeQueue()        //初始化队列
272{  
273    front=0;
274    rear=0;
275}
276
277SeQueue::~SeQueue(){};
278//进队
279void SeQueue::AddQ(NodeType x)    
280{   
281    if((rear+1) % MAXSIZE==front)
282         cout<<"QUEUE IS FULL\n";
283    else
284    {
285           rear=(rear+1) % MAXSIZE;
286           elem[rear]=x;        //将结点指针入队
287    }
288}
289
290//出队
291NodeType SeQueue::DelQ()
292{        
293    NodeType q;
294    NodeType *t = NULL;
295    if(front==rear)
296    {
297        return *t;    //返回空指针
298    }
299
300    else
301    {
302        front = (front+1) % MAXSIZE;
303        q = elem[front];
304        return q;        //返回出栈的指针结点
305    }
306

 

五.心得:

    这次实验不仅能巩固理解递归的方法,另一方面很能考验运用指针的能力,还有就是数据类型要使用得当.从levelorder(NodeType *p)函数来看,首先, DelQ()的返回类型要与BiTree二叉树结点指针的类型一至.其次,在递归过程中,传入AddQ(NodeType x)是整个结点的内容而不是一个指针.值得讨论的是,在定义存储队列的数组时如何节省存储空间?因为输入的结点个数:若为单边二叉树(全只有左结点或全只有右结点)则为任意个数(实验上这时只需要两个存储空间);若非单边二叉则要求结点最多的层个数不得超过MAXSIZE的值.后者时MAXSIZE的值(由性质2得)应该为2(h-1) (h为树的高度).这一点如何实现呢?BiTree类是SeQueue类的子类,height()函数是BiTree类的函数,如果能把高度传入SeQueue类的构造函数就可以通过一个for()语句来求得一个合适的值用以初始化MAXSIZE.那么就大大的节省了内存空间,并且还能实现输入节点的个数为任意的.但把高度传入SeQueue类的构造函数如何实现?还有其他要考虑的问题,我在今后的学习中深入了解.

六.使用说明

    程序名为No4.exe运行环境为DOS,执行后显示:

在" 请输入您的选择(0,1,2,3,4,5,6):"后输入数字选择执行的功能.

测试结果:

1)选择1.后输入1240003500600.(如右图的一棵二叉树)

2)选择4得

3)选择5得

4)选择2得

5)选择3得

6)选择6或输入非"0,1,2,3,4,5,6"的数字

七.调试过程

    本程序主要对按层序遍历操作功能进行调试.用Visual Studio 2008演示.首先把BiTree.h中的" #define MAXSIZE 30"改成" #define MAXSIZE 4",目的是从Visual Studio 2008的监视(Watch)窗口中得到更好的观察效果.

  1. 将光标移置BiTree.cpp文件的void BiTree::levelorder(NodeType *p)和第一条语句处Ctrl+F10开始调试
  2. 选择1.后输入1240003500600.(如右图的一棵二叉树)再选择3.
  3. 这时Debugger仍停留在void BiTree::levelorder(NodeType *p)的第一条语句上.可以从自动监视窗口中看到已经建立了一棵二叉树,指针P指向二叉树的根结点.

  4. 在监视窗口1中输入变量名:q,t进行观察,F10单步调试,这时Debugger停留在    SeQueue q;    语句处

    可以在监视1窗口中看到对象q的指针t都未合法初始化.

  5. 断续F10单步调试两步,这时Debugger停留在if(p)语句处,如图:

    在监视1窗口输入!p进行观察,这时!p值为0,即if(p)判断语句值为真.

    可以进入f(p)执行,F10断续,当Debugger停留在q.AddQ(*p)语句时可以从调用堆栈窗口中看到现在调用的函数为F11步入SeQueue类的AddQ(*p)函数.

  6. 这进Debugger停留在AddQ(*p)函数的第一条语句上.同可以从调用堆栈窗口中看到现在调用的函数为AddQ(*p)

    在监视2窗口中输入rear, elem[rear]进行观察.同时在自动窗口中可以看到变量X已经指向二叉树的根结点.

     

  7. 断续F10真到AddQ(NodeType x)结束语句处,可以从监视2窗口看到根结点已经入队

  8. F10后可以看到调用堆栈窗口中当前调用的是levelorder(NodeType *p)函数,同时在监视1窗口中输入!q.IsEmpty()观察到值为true,即可以进入while()控制语句执行.

    F10单步至    t = &(q.DelQ())处,并F11步入q.DelQ(),这时Debugger停留在DelQ()的第一条语句上,可以从调用堆栈窗口中看到当前调用的是DelQ()函数.

  9. 在监视3窗口中输入q进行观察.断续F10到Debugger停留在DelQ()函数的return q语句时可以从监视窗口3中看到根结点已经出队

    同时在自动窗口中可以看到从DelQ()函数返回了出队结点并赋给了指针t

  10. F10单步调试直到Debugger停留在levelorder(NodeType *p)函数的cout << t->data语句上,这时可以在调用堆栈窗口中看到当前调用的是levelorder(NodeType *p)函数,在监视窗口1中输入t->date进行观察,已经取得根结点数据域的值

  11. F10单步调试一步可以在DOS窗口中看到已经输出根结点

  12. Shift+F5退出调试,完成调试演示.

评论

# re: Visual C++ 6.0调试功能 图解教程(3)--实例二  回复  更多评论   

2008-12-14 23:33 by 小初初
#include<iostream.h>
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct tnode//定义二叉树类型
{
ElemType data;
struct tnode *lchild,*rchild;
} BTNode;
void CreateBTree(BTNode * &bt,char *str)//创建二叉树
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
bt=NULL;
ch=str[j];
while (ch!='\0')
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;p->lchild=p->rchild=NULL;
if (bt==NULL)
bt=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTree(BTNode *bt)//输出二叉树
{
if(bt!=NULL)
{
cout << bt->data;
if(bt->lchild!=NULL || bt->rchild!=NULL)
{
cout << "(";
DispBTree(bt->lchild);
if(bt->rchild!=NULL) cout << ",";
DispBTree(bt->rchild);
cout << ")";
}
}
}
int BTHeight(BTNode *bt)//求二叉树的高度
{
int lchilddep,rchilddep;
if (bt==NULL) return(0);
else
{
lchilddep=BTHeight(bt->lchild);
rchilddep=BTHeight(bt->rchild);
return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);

}
}
int NodeCount(BTNode *bt)//求二叉树的结点数
{
int num1,num2;
if(bt==NULL)
return 0;
else
{
num1=NodeCount(bt->lchild);
num2=NodeCount(bt->rchild);
return (num1+num2+1);
}

}
int LeafCount(BTNode *bt)//求二叉树的叶子结点数
{
int num1,num2;
if(bt==NULL)
return 0;
else if (bt->lchild==NULL && bt->rchild==NULL)
return (1);
else
{
num1=LeafCount(bt->lchild);
num2=LeafCount(bt->rchild);
return (num1+num2);
}
}
void PreOrder(BTNode *bt)//先序遍历
{
if (bt!=NULL)
{ cout << bt->data;
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
void InOrder(BTNode *bt)//中序遍历
{
if (bt!=NULL)
{
InOrder(bt->lchild);
cout << bt ->data;
InOrder(bt->rchild);
}

}
void PostOrder(BTNode *bt)//后序遍历
{ if (bt!=NULL)
{ PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout << bt->data;
}
}
void main()//主函数
{
BTNode *b;
char *str;
cout <<"输出括号表示法的二叉树为："<< endl;
str="A(B(C(E,F)),D(G))";
CreateBTree(b,str);
DispBTree(b);cout << endl;
cout << "二叉树的高为:" << BTHeight(b) << endl;
cout << "二叉树的结点数为:" << NodeCount(b) << endl;
cout << "二叉树的叶子结点数为:" << LeafCount(b) << endl;
cout << "二叉树的先序遍历序列:" << PreOrder(b) << endl;
cout << "二叉树的中序遍历序列:"<< InOrder(b) << endl;
cout << "二叉树的后序遍历序列:"<< PostOrder(b) << endl;
}
有3个错误怎么改啊？

# re: Visual C++ 6.0调试功能 图解教程(3)--实例二  回复  更多评论   

2008-12-15 11:53 by ∪∩BUG
@小初初
慢慢调试吧,以前我也是问老师,后来问老师效果不怎么好,我学习了调试就再不用问老师了,在调试中你可以学到很多东西..

只有注册用户登录后才能发表评论。
网站导航: