第一篇：二叉树的类定义
实验一、二叉树的类定义
程序说明
1、改程序用二叉链存储结构将其生成一棵二叉树；
2、分别用三种遍历算法将二叉树的遍历序列输出；
3、用括号表示法输出二叉树。
二叉树的形状
A
程序代码
#include “stdafx.h” #include
char data;
struct CZYP_BTNode *left;
//左孩子指针
struct CZYP_BTNode *right;// 右孩子指针
} *BiTree;
void CreateBiTree(BiTree &T){
// 在先序遍历二叉树的过程中输入二叉树的“先序字符串”，// 建立根指针为 T的二叉链表存储结构。在先序字符串中，// 字符'#'表示空树，其它字母字符为结点的数据元素
char ch;
cin >> ch;
if(ch=='#')
{
T=NULL;// 建空树
} else {
T = new CZYP_BTNode;
// “访问”操作为生成根结点
T->data = ch;
CreateBiTree(T->left);
// 递归建(遍历)左子树
CreateBiTree(T->right);
// 递归建(遍历)右子树
}
}
//先序遍历以T为根指针的二叉树 void PreOrder(BiTree &T){
if(T)
{
// T=NULL时，二叉树为空树，不做任何操作
cout<< T->data << “ ”;// 通过函数指针 *visit 访问根结点
PreOrder(T->left);
// 先序遍历左子树
PreOrder(T->right);
// 先序遍历右子树
} }
//中序遍历以T为根指针的二叉树 void InOrder(BiTree &T){
if(T){
// T=NULL时，二叉树为空树，不做任何操作
InOrder(T->left);// 先序遍历左子树
cout<< T->data << “ ”;// 通过函数指针 *visit 访问根结点
InOrder(T->right);// 先序遍历右子树
} } //后序遍历以T为根指针的二叉树 void PostOrder(BiTree &T){
if(T){
// T=NULL时，二叉树为空树，不做任何操作
PostOrder(T->left);// 先序遍历左子树
PostOrder(T->right);// 先序遍历右子树
cout<< T->data << “ ”;// 通过函数指针 *visit 访问根结点
} } //用括号表示法输出二叉树 void DispBTree(BiTree &bt){ if(bt!=NULL){
cout<
if(bt->right!=NULL||bt->left!=NULL)
{
cout<<“(”;程序结果
DispBTree(bt->left);
if(bt->right!=NULL)cout<<“,”;
DispBTree(bt->right);
cout<<“)”;
} } }
int main(){
cout << “请依次输入字符: ABD#G##E##C#FH###” << endl;
BiTree T;
CreateBiTree(T);
cout << “先序遍历: ” << endl;
PreOrder(T);
cout << endl << “中序遍历: ” << endl;
InOrder(T);
cout << endl << “后序遍历: ” << endl;
PostOrder(T);
cout<<“n用括号表示法输出二叉树:n”;DispBTree(T);cout< return(0);} 心得体会 在这次实验中，我花了很多的时间。最重要的体会就是我的知识却是很少。在做这次试验之前我仔细的看了一遍树的三种遍历的伪代码。对程序中用到的递归思想有了更深刻的认识，并且我也借鉴了老师PPT上的很多程序的写法。再者就是我从网上找了一些二叉树的写法，然后通过自己修改、调试。在这里我想说一下，我调试的时候很多错误都不知道从哪里找，后来我就把出现的错误信息输入到baidu里，事实证明这样确实很有效。终于没有错误了。Happy！！ 今天调试了一上午，虽说很累，但是我确确实实感到学到了很多知识。不足之处 这个程序的int isEmpty()函数没有实现，需要改天写出来。 一、给定二叉树如下图所示，编程完成下列要求： 1、用二叉链存储结构将其生成一棵二叉树； 2、分别用三种遍历算法将二叉树的遍历序列输出； 3、用括号表示法输出二叉树。G D B E A C F H 上面是个图。。由于我分不多了，所以不是很多。但是我很想学这方面知识，到时我有分了再给你叫啊。高手帮忙啊。问题补充： 我把图详细说下。A是树根；B、C分别是A的左右孩子；D、E分别是B的左右孩子；G是D的右孩子；F是C的右孩子；H是F的左孩子。相信我已经表达清楚了吧。谢谢各位大虾了。 VC++怎样定义类对象 如果你定义了一个类（假设是A）那么声明一个A的对象的方法就是： A a;// a 就是一个A的对象 A *a;// a 就是一个A的对象的指针 A a[N];// a 就是一个A的对象的数组 A fuctionName（）;// 返回A的一个对象的函数 上面是说如何定义对象，下面说如何定义一个类 最基本的：（运用关键字class） class A{ public://公有变量及函数（没声明是public，private，protected的都默认为public，这个与Java是不同的，后者默认为protected）（可以在任意位置被访问） ......private://私有变量及函数（只能在类里面被访问） ......protecte：//受保护的变量及函数（可以在派生类中被访问） };//注意分号 一般构造函数，析构函数，复制构造函数都是在public里被声明的（不用我说什么是构造函数（construct）和什么是析构函数（destruct）了吧）。 更往深一层会有派生类，友元类，抽象类的概念。 派生类就是有一个已经存在的类来derive一个新的类，一般新的类跟原来的是被包含与包含的关系（否则声明一个派生类就没什么意义）具体实现如下： class A： public B{ ......//跟一个普通的类没什么区别 } 声明一个友元类是这样的： class A： { friend B ......}（A就成了B的友元类，友元函数的声明也类似） 不过要注意到，友元函数、友元类的大量使用破坏了类里的数据及函数的稳定性，或是可靠性。使得private类型的都可能被篡改。 最后抽象类： 它是通过虚函数来实现的，所谓虚函数就是加上virtual关键字在前面的函数；含有虚函数的类就是抽象类，注意到如果要实现一个函数的动态绑定对象必须要以地址的形式来传递。好吧，短短几句是不能把声明类的注意事项说清楚的，太多了（像什么封装，继承，抽象）。不过，你只要多编写多看书就会的。 在定义银行类时,若取钱数大于余额则作为异常处理(InsufficientFundsException).思路:产生异常的条件是余额少于取额, 因此是否抛出异常要判断条件 取钱是withdrawal（[wið'drɔ:əl, wiθ-]n.撤退，收回；提款；取消；退股）方法中定义的动作,因此在该方法中产生异常.处理异常安排在调用withdrawal的时候,因此withdrawal方法要声明异常,由上级方法调用 要定义好自己的异常类class Bank {double balance; public void deposite(double dAmount) {if(dAmount>0.0){balance+=dAmount;}} public void withdrawal(double dAmount) throws InsufficientFundsException{if(balance throw new InsufficientFundsException(this,dAmount);} balance=balance-dAmount; } public void show_balance() { System.out.println(“The balance is ”+(int)balance);} } public class ExceptionDemo { public static void main(String args[]) { try { Bank ba=new Bank(50); ba.withdrawal(100); System.out.println(“Withdrawal successful!”); }catch(Exception e) {System.out.println(e.toString());} }public class InsufficientFundsException extends Exception{private Bankexcepbank; private double excepAmount; InsufficientFundsException(Bank ba, doubledAmount){ excepbank=ba; excepAmount=dAmount; } public StringexcepMesagge() {String str=“The balance”+ excepbank.showBalance()+“The withdrawal was”+excepAmount;return str;} 如何组织编写模板程序 前言 常遇到询问使用模板到底是否容易的问题，我的回答是：“模板的使用是容易的，但组织编写却不容易”。看看我们几乎每天都能遇到的模板类吧，如STL, ATL, WTL, 以及Boost的模板类，都能体会到这样的滋味：接口简单，操作复杂。 我在5年前开始使用模板，那时我看到了MFC的容器类。直到去年我还没有必要自己编写模板类。可是在我需要自己编写模板类时，我首先遇到的事实却是“传统”编程方法(在*.h文件声明，在*.cpp文件中定义)不能用于模板。于是我花费一些时间来了解问题所在及其解决方法。 本文对象是那些熟悉模板但还没有很多编写模板经验的程序员。本文只涉及模板类，未涉及模板函数。但论述的原则对于二者是一样的。 问题的产生 通过下例来说明问题。例如在array.h文件中有模板类array： // array.h template 然后在main.cpp文件中的主函数中使用上述模板： // main.cpp #include “array.h” int main(void){ array 将array.h文件分裂成为array.h和array.cpp二个文件(main.cpp保持不变)// array.h template // array.cpp #include “array.h” template 编译时会出现3个错误。问题出来了： 为什么错误都出现在第一个地方？ 为什么只有3个链接出错？array.cpp中有4个成员函数。 要回答上面的问题，就要深入了解模板的实例化过程。模板实例化 程序员在使用模板类时最常犯的错误是将模板类视为某种数据类型。所谓类型参量化(parameterized types)这样的术语导致了这种误解。模板当然不是数据类型，模板就是模板，恰如其名： 编译器使用模板，通过更换模板参数来创建数据类型。这个过程就是模板实例化(Instantiation)。 从模板类创建得到的类型称之为特例(specialization)。 模板实例化取决于编译器能够找到可用代码来创建特例(称之为实例化要素，point of instantiation)。 要创建特例，编译器不但要看到模板的声明，还要看到模板的定义。模板实例化过程是迟钝的，即只能用函数的定义来实现实例化。 再回头看上面的例子，可以知道array是一个模板，array 现在，编译array.cpp时会发生什么问题呢？编译器可以解析模板定义并检查语法，但不能生成成员函数的代码。它无法生成代码，因为要生成代码，需要知道模板参数，即需要一个类型，而不是模板本身。 这样，链接程序在main.cpp 或 array.cpp中都找不到array 至此，我们回答了第一个问题。但还有第二个问题，在array.cpp中有4个成员函数，链接器为什么只报了3个错误？回答是：实例化的惰性导致这种现象。在main.cpp中还没有用上operator[]，编译器还没有实例化它的定义。解决方法 认识了问题，就能够解决问题： 在实例化要素中让编译器看到模板定义。 用另外的文件来显式地实例化类型，这样链接器就能看到该类型。使用export关键字。 前二种方法通常称为包含模式，第三种方法则称为分离模式。 第一种方法意味着在使用模板的转换文件中不但要包含模板声明文件，还要包含模板定义文件。在上例中，就是第一个示例，在array.h中用行内函数定义了所有的成员函数。或者在main.cpp文件中也包含进array.cpp文件。这样编译器就能看到模板的声明和定义，并由此生成array 第二种方法，通过显式的模板实例化得到类型。最好将所有的显式实例化过程安放在另外的文件中。在本例中，可以创建一个新文件templateinstantiations.cpp： // templateinstantiations.cpp #include “array.cpp” template class array array Stroustrup的书中读到export时，感到非常兴奋。但很快就发现VC 6.0不支持它，后来又发现根本没有编译器能够支持这个关键字(第一个支持它的编译器要在2002年底才问世)。自那以后，我阅读了不少关于export的文章，了解到它几乎不能解决用包含模式能够解决的问题。欲知更多的export关键字，建议读读Herb Sutter撰写的文章。 结论 要开发模板库，就要知道模板类不是所谓的“原始类型”，要用其它的编程思路。本文目的不是要吓唬那些想进行模板编程的程序员。恰恰相反，是要提醒他们避免犯下开始模板编程时都会出现的错误。 ////////////////////////////// http://www.xiexiebang.com,.cxx）扩展名。 这种组织方式工作的很好：它使得在编程时可以方便地访问所需的类型定义，并且避免了来自链接器的“变量或函数重复定义”的错误。 由于以上组织方式约定的影响，模板编程新手往往会犯一个同样的错误。下面这一小段程序反映了这种错误。就像对待“普通代码”那样，我们在头文件中定义模板： // basics/myfirst.hpp #ifndef MYFIRST_HPP #define MYFIRST_HPP // declaration of template template // basics/myfirst.cpp #include 大部分C++编译器（Compiler）很可能会接受这个程序，没有任何问题，但是链接器（Linker）大概会报告一个错误，指出缺少函数print_typeof()的定义。 这个错误的原因在于，模板函数print_typeof()的定义还没有被具现化（instantiate）。为了具现化一个模板，编译器必须知道哪一个定义应该被具现化，以及使用什么样的模板参数来具现化。不幸的是，在前面的例子中，这两组信息存在于分开编译的不同文件中。因此，当我们的编译器看到对print_typeof()的调用，但是没有看到此函数为double类型具现化的定义时，它只是假设这样的定义在别处提供，并且创建一个那个定义的引用（链接器使用此引用解析）。另一方面，当编译器处理myfirst.cpp时，该文件并没有任何指示表明它必须为它所包含的特殊参数具现化模板定义。头文件中的模板 解决上面这个问题的通用解法是，采用与我们使用宏或者内联函数相同的方法：我们将模板的定义包含进声明模板的头文件中。对于我们的例子，我们可以通过将#include “myfirst.cpp”添加到myfirst.hpp文件尾部，或者在每一个使用我们的模板的点C文件中包含myfirst.cpp文件，来达到目的。当然，还有第三种方法，就是删掉myfirst.cpp文件，并重写myfirst.hpp文件，使它包含所有的模板声明与定义： // basics/myfirst2.hpp #ifndef MYFIRST_HPP #define MYFIRST_HPP #include 从这个方法中我们可以得到一些观察结果。最值得注意的一点是，这个方法在相当程度上增加了包含myfirst.hpp的开销。在这个例子中，这种开销并不是由模板定义自身的尺寸引起的，而是由这样一个事实引起的，即我们必须包含我们的模板用到的头文件，在这个例子中是 这在实践中确实是一个问题，因为它增加了编译器在编译一个实际程序时所需的时间。我们因此会在以后的章节中验证其他一些可能的方法来解决这个问题。但无论如何，现实世界中的程序花一小时来编译链接已经是快的了（我们曾经遇到过花费数天时间来从源码编译的程序）。 抛开编译时间不谈，我们强烈建议如果可能尽量按照包含模式组织模板代码。 另一个观察结果是，非内联模板函数与内联函数和宏的最重要的不同在于：它并不会在调用端展开。相反，当模板函数被具现化时，会产生此函数的一个新的拷贝。由于这是一个自动的过程，编译器也许会在不同的文件中产生两个相同的拷贝，从而引起链接器报告一个错误。理论上，我们并不关心这一点：这是编译器设计者应当关心的事情。实际上，大多数时候一切都运转正常，我们根本就不用处理这种状况。然而，对于那些需要创建自己的库的大型项目，这个问题偶尔会显现出来。 最后，需要指出的是，在我们的例子中，应用于普通模板函数的方法同样适用于模板类的成员函数和静态数据成员，以及模板成员函数。 实验报告 二叉树 一 实验目的 1、进一步掌握指针变量，动态变量的含义； 2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。 4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。 二 实验原理 树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。遍历二叉树的实质是将非线性结构转为线性结构。 三 使用仪器，材料 计算机 2 Wndows xp 3 VC6.0 四实验步骤 【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。 【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。 五实验过程原始记录 基本数据结构描述； 2 函数间的调用关系； 用类C语言描述各个子函数的算法； 附录：源程序。 六 试验结果分析 将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会，写在实验报告上。第二篇：VC类定义
第三篇：定义银行类
第四篇：类声明和定义
第五篇：实验报告：二叉树
点击咨询 