7.1 堆内存分配
7.5 MFC对象和 Windows对象的关系
7.4二叉树
7.3 栈与队列的基本操作及其应用
7.2 链表与链表的基本操作第七章 动态内存分配
7.1 堆内存分配
7.1.1堆内存的分配与释放
7.1.2 堆对象与构造函数
7.1.3 浅拷贝与深拷贝
7.1.1 堆内存的分配与释放当程序运行到需要一个动态分配的变量或对象时,必须向系统申请取得堆中的一块所需大小的存贮空间,用于存贮该变量或对象 。 当不再使用该变量或对象时,也就是它的生命结束时,要显式释放它所占用的存贮空间,这样系统就能对该堆空间进行再次分配,做到重复使用有限的资源 。
在 C++中,申请和释放堆中分配的存贮空间,分别使用 new和
delete的两个运算符来完成,其使用的格式如下：
指针变量名 =new类型名 (初始化式 )；
delete 指针名 ;
new运算符返回的是一个指向所分配类型变量（对象）的指针。对所创建的变量或对象，都是通过该指针来间接操作的，而动态创建的对象本身没有名字。
7.1.1 堆内存的分配与释放
１．用初始化式 (initializer)来显式初始化例如：
int *pi=new int(0);
２,当 pi生命周期结束时,必须释放 pi所指向的目标：
delete pi;
注意这时释放了 pi所指的目标的内存空间，也就是撤销了该目标，
称动态内存释放（ dynamic memory deallocation），但指针 pi
本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放。
堆
０Ｐ i
１．用初始化式 (initializer)来显式初始化例如：
int *pi=new int(0);
２,当 pi生命周期结束时,必须释放 pi所指向的目标：
delete pi;
注意这时释放了 pi所指的目标的内存空间，也就是撤销了该目标，
称动态内存释放（ dynamic memory deallocation），但指针 pi
本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放。
7.1.1 堆内存的分配与释放堆
Ｐ i
7.1.1 堆内存的分配与释放对于数组进行动态分配的格式为：
指针变量名 =new 类型名 [下标表达式 ];
delete [ ] 指向该数组的指针变量名 ;
7.1.1 堆内存的分配与释放
【 例 7.1】 动态数组的建立与撤销
#include <iostream.h>
#include <string.h>
void main(){
int n;
char *pc;
cout<<"请输入动态数组的元素个数 "<<endl;
cin>>n;
pc=new char[n]; //
strcpy(pc,"堆内存的动态分配 ");
cout<<pc<<endl;
delete []pc; // 撤销并释放 pc所指向的 n个字符的内存空间
return ; }
7.1.1 堆内存的分配与释放动态分配的三个特点：首先，变量 n在编译时没有确定的值，而是在运行中输入，按运行时所需分配堆空间，这一点是动态分配的优点，可克服数组“大开小用”
的弊端，在第六章中表，排序与查找中的算法，若用动态数组，通用性更佳。 delete []pc是将 n个字符的空间释放，而用 delete pc则只释放了一个字符的空间；其次如果有一个 char *pc1，令 pc1=p，同样可用 delete
[] pc1来释放该空间。尽管 C++不对数组作边界检查，
但在堆空间分配时，对数组分配空间大小是纪录在案的。
第三，没有初始化式（ initializer），不可对数组初始化。
7.1.1 堆内存的分配与释放指针使用的几个问题：
１．动态分配失败。 返回一个空指针（ NULL），表示发生了异常，堆资源不足，分配失败。
２．指针删除与堆空间释放。删除一个指针 p（ delete p;）
实际意思是删除了 p所指的目标（变量或对象等），释放了它所占的堆空间，而不是删除ｐ本身，释放堆空 间后，ｐ成了空悬指针
7.1.1 堆内存的分配与释放
３,内存泄漏（ memory leak）和重复释放 。 new与
delete 是配对使用的,delete只能释放堆空间。
如果 new返回的指针值丢失，则所分配的堆空间无法回收，称内存泄漏，同一空间重复释放也是危险的，所以必须妥善保存 new返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放堆内存空间。
４．动态分配的变量或对象的生命期。 无名对象，它的生命期并不依赖于建立它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用。我们也称堆空间为自由空间（ free store）就是这个原因。
7.1.2 堆对象与构造函数通过 new建立的对象要调用构造函数，
通过 deletee删除对象也要调用析构函数。
正因为构造函数可以有参数，所以
new后面类（ class）类型也可以有参数。
这些参数即构造函数的参数。但对创建数组，则无参数，并只调用缺省的构造函数。
7.1.2 堆对象与构造函数如有 class CGoods{
char Name[21];
int Amount;
float Price;
float Total value;
public:
CGoods(){};
CGoods(char* name,int amount,float price){
strcpy(Name,name);
Amount=amount;
Price=price;
Total_value=price*amount; }
… …
}
7.1.2 堆对象与构造函数
void main(){
int n;
CGoods *pc,*pc1,*pc2;
pc=new CGoods(“夏利 2000”,10,118000);
pc1=new CGoods(); //调用缺省构造函数；
cout<<’输入商品类数组元素数 ’ <<endl;
cin>>n;
pc2=new CGoods[n];
……
delete pc;
delete pc1;
delete []pc2;
}
7.1.2 堆对象与构造函数这里再次强调：由堆区创建对象数组,只能调用缺省的构造函数,不能调用其他任何构造函数 。 如果没有缺省的构造函数,则不能创建对象数组 。
7.1.3 浅拷贝与深拷贝缺省拷贝构造函数，可用一个类对象初始化另一个类对象，
称为缺省的 按成员拷贝,而不是对整个类对象的 按位拷贝。 这称为浅拷贝。
P 堆对象 堆对象P
P
图 7.1 浅拷贝
7.1.3 浅拷贝与深拷贝如果类中有一个数据成员为指针，
该类的一个对象 obj1中的这个指针 p，
指向了动态分配的一个堆对象，（参见图 7.1拷贝前），如果用 obj1按成员拷贝了一个对象 obj2，这时 obj2.p也指向同一个堆对象。当析构时，如用缺省的析构函数，则动态分配的堆对象不能回收。如果在析构函数中有,delete
p;”语句，则如果先析构函数 obj1时，
堆对象已经释放，以后再析构 obj2时出现了二次释放的问题。这时就要重新定义拷贝的构造函数，给每个对象独立分配一个堆对象，称 深拷贝 。
堆对象P
P 堆对象图 7.2 深拷贝
7.1.3 浅拷贝与深拷贝
[例 7.3]定义拷贝构造函数（ copy structor）和拷贝赋值操作符（ copy Assignment Operator）实现深拷贝。
程序：Ｅ x7_3.cpp
堆内存是最常用的需要拷贝构造函数自定义的资源,如果类需要析构函数来析构资源，则类也需要一个自定义的拷贝构造函数。对象的拷贝就是深拷贝了。
7.2 链表与链表的基本操作线性表是最简单，最常用的一种数据结构。线性表的逻辑结构是 n个数据元素的有限序列（ a1,a2,…,an）。而线性表的物理结构，我们已经学习过顺序表，
也就是数组 ；另一种线性表的物理结构 ——链表
7.2 链表与链表的基本操作
7,2,1 单链表基本算法
7,2,3 双向链表
7,2,2单链表类型模板
7.2.1 单链表基本算法单链表 （ Singly Linked list） 也称线性链表 。 每个数据元素占用一个节点 （ Node） 。 一个节点包含两个域,一个域存放数据元素 info,其数据类型由应用问题决定,另一个存放指向该链表中下一个节点的指针 link。 节点定义如下：
typedef int Datatype; //数据为整型
struct node{
Datatype info;
node *link;
}
infon-1 ^info2info1info0 ……haed
图 7.3 单向链表结构
7.2.1 单链表基本算法单链表的第一个结点的地址可通过链表的表头指针 head找到,head在使用中必须妥善保存，
千万不可丢失，否则链表整个丢失，内存也发生泄漏。
单链表的插入与删除,只要改变链中结点指针的值，
无需移动表中的元素，就能实现插入和删除操作。
插入算法有三种情况，我们希望在单链表中包含数据 infoi的结点之前插入一个新元素，则 infoi
可在第一个结点，或在中间结点，也可把新结点插在链尾结点之后。
7.2.1 单链表基本算法插在链首首先新结点的 link指针指向 info0所在结点,然后,head指向新结点 。 即：
newnode→ link=head； //注意：链表操作次序非常重要
head=newnode；
newnode
infox
info0 info1 ············
·head
7.2.1 单链表基本算法插在链首首先新结点的 link指针指向 info0所在结点,然后,head指向新结点 。 即：
newnode→ link=head； //注意：链表操作次序非常重要
head=new node；
new node
infox
info0 info1
head
············
·
7.2.1 单链表基本算法插在中间首先用工作指针 p找到指定结点,而让指针 q指向紧跟其后的结点,令 infoi-1所在结点的 link指针指向新结点,而后让新结点的 link指向 infoi所在结点 。 即：
newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某结点之后
q→ link=newnode；
infox
infoi-1 infoi
p
ｑ
newnode
7.2.1 单链表基本算法插在中间首先用工作指针 p找到指定结点,而让指针 q指向紧跟其后的结点,令 infoi-1所在结点的 link指针指向新结点,而后让新结点的 link指向 infoi所在结点 。 即：
newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某结点之后
q→ link=newnode；
infox
infoi-1 infoi
p
ｑ
newnode
7.2.1 单链表基本算法插在队尾只要工作指针 p找到队尾,即可链在其后：
p→ link=newnode；
newnode.link=NULL;
Infon-1 ^
infoxnewnode
······
p
^
7.2.1 单链表基本算法
^head
p0
1,向后生成链表算法：
node *createdown(){
Datatype data;
Node*head,*tail,*p;
head=new node; //建立链表头结点
P0=head;
while(cin>>data){ //回车结束
p1=new(node);//每输入一个数申请一个结点
p1->info=data; //添入数据
p0->link= p1;
P0=p1
}
return head; //返回头指针
}
7.2.1 单链表基本算法
^ info0 ^
^
head
p0
p1
1,向后生成链表算法：
node *createdown(){
Datatype data;
Node*head,*tail,*p;
head=new node; //建立链表头结点
P0=head;
while(cin>>data){ //回车结束
p1=new(node);//每输入一个数申请一个结点
p1->info=data; //添入数据
p0->link= p1;
P0=p1
}
return head; //返回头指针
}
info1
7.2.1 单链表基本算法
^ info0 ^
^
head
p0
p1
1,向后生成链表算法：
node *createdown(){
Datatype data;
Node*head,*tail,*p;
head=new node; //建立链表头结点
P0=head;
while(cin>>data){ //回车结束
p1=new(node);//每输入一个数申请一个结点
p1->info=data; //添入数据
p0->link= p1;
P0=p1
}
return head; //返回头指针
}
info1
7.2.1 单链表基本算法
2,向前生成链表算法
node *createup(){
node *head,*p;
Datatype data;
head=new node; //建立头结点
head->link=NULL;
while(cin>>data){ //建立第一个结点
p=new node;
p->info=data;
p->link= head->link ;
head->link=p;
}
return head;
}
^head
7.2.1 单链表基本算法
2,向前生成链表算法
node *createup(){
node *head,*p;
Datatype data;
head=new node; //建立头结点
head->link=NULL;
while(cin>>data){ //建立第一个结点
p=new node;
p->info=data;
p->link= head->link ;
head->link=p;
}
return head;
}
info0 ^head
p info1
7.2.1 单链表基本算法
2,向前生成链表算法
node *createup(){
node *head,*p;
Datatype data;
head=new node; //建立头结点
head->link=NULL;
while(cin>>data){ //建立第一个结点
p=new node;
p->info=data;
p->link= head->link ;
head->link=p;
}
return head;
}
info0 ^
info1
head
p
7.2.1 单链表基本算法
3.链表查找算法 （ Traversal）,按数据 （ 关键字 ） 查找：
node *traversal(node *head,Datatype data){
node *p=head->link;
while(p!=NULL||p->info!=data) p=p->link;
return p; //p为 NULL则未找到
}
返回值为指针 p,指向链表中找到的结点 。
7.2.1 单链表基本算法
4,在单链表的 p节点后插入一个信息域为 x的新节点 （ 注意只有一种情况了 ） 。
void insert(node p,Datatype x){
node *q=new node;
q->info=x;
q->link=p->link;
p->link=q;
}
7.2.1 单链表基本算法
5,删除单链表节点 *p后面节点
void del (node *p){
node *q;
q=p->link;
p->link=q->link;
delete q; //如果要把该节点移入另一个链中,则可将
q返回 。
}
7.2.2 单链表类型模板
【 例 7.4_h】 单链表类模板，本例作为一个头文件。
程序：Ｅ x7_4.h.cpp
7.2.2 单链表类型模板
【 例 7.4】 由键盘输入 16个整数,以这些整数作为结点数据,生成两个链表,一个向前生成,一个向后生成,输出两个表 。 然后给出一个整数在一个链表中查找,找到后删除它,再输出该表 。 清空该表,
再按升序生成链表并输出 。
7.2.2 单链表类型模板
#include "Ex7_4.h"
void main(){
Node<int> * P1;
List<int> list1,list2;
int a[16],i,j;
cout<<"请输入 16个整数 "<<endl;
for(i=0;i<16;i++)cin>>a[i];
for(i=0;i<16;i++){
P1=list1.CreatNode(a[i]);
list1.InsertFront(P1);//向前生成 list1
P1=list2.CreatNode(a[i]);
list2.InsertRear(P1);
}
7.2.2 单链表类型模板
list1.PrintList();
cout<<"list1长度,"<<list1.Length()<<endl;
list2.PrintList();
cout<<"请输入一个要求删除的整数 "<<endl;
cin>>j;
P1=list1.Find(j);
if(P1!=NULL){P1=list1.DeleteNode(P1);
delete P1;
list1.PrintList();
cout<<"list1长度,"<<list1.Length()<<endl; }
else cout<<"未找到 "<<endl;
list1.MakeEmpty();//清空 list1
for(i=0;i<16;i++){P1=list1.CreatNode(a[i]);
list1.InsertOrder(P1);//升序创建 list1 }
list1.PrintList();
}
7.2.3 双向链表
7.3 栈与队列的基本操作及其应用栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。
7.3 栈与队列的基本操作及其应用
7,3,1 栈 与 应 用
7,3,2 队 列
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
a1top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-2
……
a1
top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-2
……
a1
an-1top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-1
an-2
……
a1
top
出栈
bottom
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-2
……
a1
top
bottom
出栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
a1top
bottom
出栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0top
bottom
出栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0top
bottom
出栈
7.3.1 栈与应用
【 例 7.6】 顺序栈的类模板 。
#include<assert.h>
#include<iostream.h>
template<typename T>class Stack{
int top;
T *elements;
int maxSize;
public:
Stack(int=20);
~Stack(){delete[] elements;}
void Push(const T &data);
T Pop();
T GetElem(int i);
void MakeEmpty(){top= -1;}
bool IsEmpty() const{return top== -1;}
bool IsFull() const{return top==maxSize-1;}
7.3.1 栈与应用
void PrintStack(); };
template<typename T> Stack<T>::Stack(int maxs){ maxSize=maxs;
top=-1;
elements=new T [maxSize];
assert(elements!=0); }
template<typename T> void Stack<T>::PrintStack(){
for(int i=0;i<=top;i++) cout<<elements[i]<<'\t';
cout<<endl;}
template<typename T> void Stack<T>::Push(const T &data){ assert(!IsFull());
elements[++top]=data; }
template<typename T> T Stack<T>::Pop(){ assert(!IsEmpty());
return elements[top--]; }
template<typename T> T Stack<T>::GetElem(int I){
assert(i<=top&&i>=0);
return elements[i];
}
7.3.1 栈与应用
【 例 7.7_h】 链栈的类模板，本例为头文件,Ex7_7.h”
程序,Ex7_7.h.cpp
7.3.1 栈与应用顺序栈和链栈逻辑功能是一样，尽管这里两个栈模板的成员函数功能选择稍有出入，因为顺序栈可以随机访问其中的元素，而链栈只能顺序访问，但逻辑上完全可以做到一样（物理结构不同）。顺序栈必须先开一定大小内存空间，执行起来简单，速度快，可能溢出。链栈内存空间随用随开，不会溢出，但执行复杂
（不断地动态分配），速度慢。
7.3.1 栈与应用
【 例 7.7】 模拟简单计算器,该计算器只认 + - * / 四个运算符,输入为整数 。 表达式使用＝号,清空栈用 ‘ c’
字符 。 使用 ‘ z’字符表示结束 。
程序,Ex7_7.cpp
7.3.2 队列队列 (Queue)也是一种限定存取位置的线性表。它只允许在表的一端插入，而在另一端删除。允许插入的一端称为队尾 (rear)，允许删除的一端叫做队头 (front)。每次在队尾加入新元素，加入称为进队，删除称为出队。
a0 a1 a2 … an-1…
front 元 素 移 动 方向
rear
图 7.15队列
7.3.2 队列
rear A
front
进队
7.3.2 队列
A
Brear
front
进队
7.3.2 队列
C
A
B
rear
front
进队
7.3.2 队列
D
C
A
B
进队
rear
front
7.3.2 队列
D
C
A
B
rear
front
出队
7.3.2 队列
D
C
B
rear
front
出队
7.3.2 队列
D
C
rear
front
出队
7.3.2 队列
Drear
front
出队
7.3.2 队列出队
7.4 二叉树树形结构是一类重要的非线性数据，树和二叉树是常用的树形结构。
7.4.2 二叉树的遍历
7.4.1 二叉树的概念
7.4.3 排序二叉树
7.4.1 二叉树的概念树（ Tree） 是由 n（ n≥0）个结点组成的有限集合。
如 n=0，称为空树。非空树有一个特定的结点，它只有直接后继，没有直接前驱，称之为根（ root）。除根以外的其它结点划分为 m（ m≥0）个互不相交的有限集合
T0,T1,……,Tm-1，每个集合又是一棵树，称为根的子树（ subtree）。每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。这是一个递归方法定义的数据结构。
7.4.1 二叉树的概念
A
B C D
E F G IH
J LK ONM
…………………
……… 0层
………
… 1层
……
2层
……
3层深度图 7.17 树的示意图下面介绍有关树的术语：
结点 （ node）,包括数据项和多个指针项,指针项数目并不固定,且无次序 。
结点的度 （ degree）,结点所拥有的子树数量 。
叶结点 （ leaf）,度为 0的结点,如 G,I,J,K,L,M，
N,O结点 。
分支结点 （ branch）,度 ≥1的结点 。
孩子结点 （ child）,若结点 x有子树,则子树根结点即为 x
的孩子结点 。
双亲结点 （ parent）,若结点 x有孩子,它即为孩子的双亲 。
兄弟结点 （ sibling）,同一双亲的结点互称为兄弟 。
结点的层次 （ level）,从根到该结点所经路径上的分支条数 。
树的深度 （ depth）,树中结点的层次数 。
树的度（ degree）,树中结点度的最大值。
7.4.1 二叉树的概念二叉树 （ Binary Tree） 是另一种独立的树形结构 。 二叉树是结点的一个有限集合,该集合或为空,或是由一个根结点及两棵树分别称为左子树和右子树的 （ 注意有左右之分 ） 互不相交的二叉树组成,其中左右子树分别可以为空子树或均为空树 。 这也是一个递归的定义 。 二叉树的特点是：每个结点最多两个孩子,并且子树有左右之分 。
二叉树的基本性质：
1,二叉树的第 i层上最多有 2i-1(i>=1)个结点；
2,深度为 h的二叉树中最多有 2h-1个结点；
3,在任一棵二叉树中,有 n0叶子结点,有 n2个度为 2的结点,则有 n0=n2+1。
7.4.1 二叉树的概念
【 例 7.9】 画出有三个结点的所有二叉树 。
解：结果见图 7.18,共 5种 。
图 7.18 5种不同的三结点二叉树
7.4.1 二叉树的概念二叉树有 满二叉树和完全二叉树,分别如图 7.19
和图 7.20，完全二叉树已有的结点排序与满二叉树相同。
1
2 3
4 5 6 7
98 1
0
1
1
1
4
1
3
1
2
1
5
图 7.19 满二叉树
1
2 3
4 5 6 7
98 1
0
图 7.20 完全二叉树
7.4.1 二叉树的概念下面给出链表储存方式的二叉树。每个结点有三个域：
数据域、左孩子指针和右孩子指针，见图 7.21。
lchild rchildinfo
图 7.21 二叉树结点
7.4.1 二叉树的概念二叉树类结点类模板定义如下：
template<typename T>class BinaryTree;
template<typename T>class Node{
Node<T> *lchild,*rchild;
T info;
public:
Node(){lchild=NULL;rchild=NULL;}
Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
info=data;
lchild=left;
rchild=right;
}
7.4.1 二叉树的概念
T Getinfo(){return info;}
void setinfo(const T &data){info=data
Node<T> *Getleft(){return lchild;}
Node<T> *Getright(){return rchild;}
void setleft(Node<T> *left){lchild=left;}
void setright<Node<T> *right){rchild=right;}
friend class BinaryTree<T>;
}
7.4.2 二叉树的遍历所 谓 二 叉 树 的 遍 历 （ binary tree
traversal）,就是遵从某种次序,查巡二叉树的所有结点,每个结点都被访问一次,而且仅访问一次 。 所谓,访问,指对结点施行某些操作,
但不破坏它原来的数据结构 。
遍历二叉树有不同次序，规定先左后右，令
L,R,V分别代表遍历一个结点的左右子树和访问该结点的操作，有三种方式,前序遍历
（ VLR），中序遍历（ LVR），后序遍历（ LRV） 。
7.4.2 二叉树的遍历例如：前序遍历访问次序为 ABDEGCFH。
A
B
D
C
E
G
F
H
图 7.22 二叉树遍历中序遍历结果为
D B G E A F H C。
后序遍历结果为
D G E B H F C A。
7.4.2 二叉树的遍历中序遍历 （ inorder traversal）,前序遍历
（ preorder traversal） 和后序遍历 （ postorder
traversal） 算法如下：
【 例 7.10】 二叉树类模板（其中二叉树生成借用二叉排序树，见下节）。特别注意插入结点时，第二参数为指针的引用！否则不能建立树。为什么？请读者自己思考。
程序,Ex7_10.cpp
7.4.2 二叉树的遍历
【 例 7.13】 某二叉树先序遍历为
ABCEFDGHIJK，中序遍历为
ECFBDGAIHJK绘出该二叉树。
解：由先序知 A为根结点,而 E F B D G为左子树,I H J K为右子树 。 由先序中的 B C E
F D G知 B为左子树根结点,由中序中的 E C
F B D G知 E C F为其左子树,而 DG为右子树 。
再由先序 C E F知 C为左子树根结点，由中序 E C F知 E为 C左子树,F为的右子树。再由先序 D G知,D为 B的右子树根结点，由中序 D G知 G为 D的右子树。按同样方法推出 A
的右子树。结果如图 7.23。可以证明已知先序和中序访问次序可以唯一确定一棵二叉树。
A
B
C D
E F G
H
I J
K
图 7.23 例 7.11二叉数
7.4.3 排序二叉树二叉排序树 （ Binary Sorting Tree） 又称二叉搜索树 （ Binary Search
Tree）,是一种特殊结构的二叉数,作为一种排序和查找的手段,对应有序表的对半查找,通常亦被称为数表 。 其定义也是递归的 。
二叉排序树的定义,二叉排序树或者是空树或者是具有下述性质的二叉数,
其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于等于根结点的数据值,左子树和右子树又各是一棵二叉排序树 。
二叉排序树的结点插入 （ 可生成排序二叉树 ） 生成算法：对任意一组数据元素序列 {a0,a1,a2,…,an-1}。 要生成一棵二叉排序树的过程为：
1,令 a0为二叉树的根结点 。
2,若 a1<a0,令 a1为 a0左子树的根结点,否则 a1为 a0右子树的根结点 。
3,如 ai小于根结点,则去左子树,否则去右子树,按此法查找,直到成为 空树,则安放此位置 。 这步就是插入算法 。
7.4.3 排序二叉树二叉排序树用中序遍历就可以得到由小到大的有序序列，如图 7.24可得有序序列｛ 8,10,11,12，
15,16,18,22,24,26,29｝。
10
18
26
8 12 22 29
11 2416
15
图 7.24 二叉排序树例
7.4.3 排序二叉树建立二叉排序树算法程序如下：
template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
if(b==NULL){
b=new Node<T>(data);
if(b==NULL){
cout<<"空间不足 "<<endl;
exit(1); } }
else if(data<b->info) Insert(data,b->lchild);
else Insert(data,b->rchild);
}
template<typename T>void BinaryTree<T>::Creat(T* data,int n){
for(int i=0;i<n;i++) Insert(data[i],root);
}
7.4.3 排序二叉树
【 例 7.15】 排序二叉树查找函数 。
算法：只要中序遍历即可,但递归慢,下面给出迭代的查找算法 。
template<typename T>Node<T> *BinaryTree<T>::Find(const T
&data,Node<T> *b){//查找
if(b!=NULL){
Node<T> *temp=b;
while(temp!=NULL){
if(temp->info==data)return temp;
if(temp->info<data)temp=temp->rchild;
else temp=temp->lchild;
}
}
return NULL;
}
7.5 MFC对象和 Windows对象的关系
MFC对象是 C++对象，而且是特指封装了 Window对象的
C++对象，不是任意的 C++对象。本节讨论 MFC对象与
Window对象的联系，以最典型的的窗口类（ CWnd）为例，讨论 CWnd类对象与 Windows窗口对象的关系。参见图 7.26。
.
.
.
.
其它成员
m_hWnd hwnd
CWnd类对象 HWND句柄类型
wnd
windows对象句柄
Windows
操作系统窗口对象图 7.26 MFC窗口对象与 Windows窗口对象的关系
7.5 MFC对象和 Windows对象的关系
MFC的窗口对象 wnd是 C++类的实例,即 CWnd类或其派生类的实例,
是由 CWnd类或其派生类的构造函数创建的,而最终由 CWnd类或其派生类的析构函数撤消 。 hwnd是 HWND句柄类型的实例,为它建立了一个
Windows操作系统的对象 。 然后把这个句柄放入 CWnd类对象 wnd的成员数据 m_hwnd中 。 这样 wnd就包含了一个 Windows操作系统的窗口对象 。 程序段如下：
CWnd wnd;//定义窗口类 （ CWnd） 的对象 wnd
HWND hwnd;//定义窗口句柄 hwnd
hwnd=CreateWindows(......);//调用 API函数 CreateWindows(...)建立一个 Windows窗口类实例
wnd.Attach(hwd);//把 Windows窗口实例的句柄链到 CWnd对象 hwnd
上
......
Destrory Window(hwnd);//调用 API函数撤消 Windows窗口
7.5 MFC对象和 Windows对象的关系
7.4二叉树
7.3 栈与队列的基本操作及其应用
7.2 链表与链表的基本操作第七章 动态内存分配
7.1 堆内存分配
7.1.1堆内存的分配与释放
7.1.2 堆对象与构造函数
7.1.3 浅拷贝与深拷贝
7.1.1 堆内存的分配与释放当程序运行到需要一个动态分配的变量或对象时,必须向系统申请取得堆中的一块所需大小的存贮空间,用于存贮该变量或对象 。 当不再使用该变量或对象时,也就是它的生命结束时,要显式释放它所占用的存贮空间,这样系统就能对该堆空间进行再次分配,做到重复使用有限的资源 。
在 C++中,申请和释放堆中分配的存贮空间,分别使用 new和
delete的两个运算符来完成,其使用的格式如下：
指针变量名 =new类型名 (初始化式 )；
delete 指针名 ;
new运算符返回的是一个指向所分配类型变量（对象）的指针。对所创建的变量或对象，都是通过该指针来间接操作的，而动态创建的对象本身没有名字。
7.1.1 堆内存的分配与释放
１．用初始化式 (initializer)来显式初始化例如：
int *pi=new int(0);
２,当 pi生命周期结束时,必须释放 pi所指向的目标：
delete pi;
注意这时释放了 pi所指的目标的内存空间，也就是撤销了该目标，
称动态内存释放（ dynamic memory deallocation），但指针 pi
本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放。
堆
０Ｐ i
１．用初始化式 (initializer)来显式初始化例如：
int *pi=new int(0);
２,当 pi生命周期结束时,必须释放 pi所指向的目标：
delete pi;
注意这时释放了 pi所指的目标的内存空间，也就是撤销了该目标，
称动态内存释放（ dynamic memory deallocation），但指针 pi
本身并没有撤销，它自己仍然存在，该指针所占内存空间并未释放。
7.1.1 堆内存的分配与释放堆
Ｐ i
7.1.1 堆内存的分配与释放对于数组进行动态分配的格式为：
指针变量名 =new 类型名 [下标表达式 ];
delete [ ] 指向该数组的指针变量名 ;
7.1.1 堆内存的分配与释放
【 例 7.1】 动态数组的建立与撤销
#include <iostream.h>
#include <string.h>
void main(){
int n;
char *pc;
cout<<"请输入动态数组的元素个数 "<<endl;
cin>>n;
pc=new char[n]; //
strcpy(pc,"堆内存的动态分配 ");
cout<<pc<<endl;
delete []pc; // 撤销并释放 pc所指向的 n个字符的内存空间
return ; }
7.1.1 堆内存的分配与释放动态分配的三个特点：首先，变量 n在编译时没有确定的值，而是在运行中输入，按运行时所需分配堆空间，这一点是动态分配的优点，可克服数组“大开小用”
的弊端，在第六章中表，排序与查找中的算法，若用动态数组，通用性更佳。 delete []pc是将 n个字符的空间释放，而用 delete pc则只释放了一个字符的空间；其次如果有一个 char *pc1，令 pc1=p，同样可用 delete
[] pc1来释放该空间。尽管 C++不对数组作边界检查，
但在堆空间分配时，对数组分配空间大小是纪录在案的。
第三，没有初始化式（ initializer），不可对数组初始化。
7.1.1 堆内存的分配与释放指针使用的几个问题：
１．动态分配失败。 返回一个空指针（ NULL），表示发生了异常，堆资源不足，分配失败。
２．指针删除与堆空间释放。删除一个指针 p（ delete p;）
实际意思是删除了 p所指的目标（变量或对象等），释放了它所占的堆空间，而不是删除ｐ本身，释放堆空 间后，ｐ成了空悬指针
7.1.1 堆内存的分配与释放
３,内存泄漏（ memory leak）和重复释放 。 new与
delete 是配对使用的,delete只能释放堆空间。
如果 new返回的指针值丢失，则所分配的堆空间无法回收，称内存泄漏，同一空间重复释放也是危险的，所以必须妥善保存 new返回的指针，以保证不发生内存泄漏，也必须保证不会重复释放堆内存空间。
４．动态分配的变量或对象的生命期。 无名对象，它的生命期并不依赖于建立它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用。我们也称堆空间为自由空间（ free store）就是这个原因。
7.1.2 堆对象与构造函数通过 new建立的对象要调用构造函数，
通过 deletee删除对象也要调用析构函数。
正因为构造函数可以有参数，所以
new后面类（ class）类型也可以有参数。
这些参数即构造函数的参数。但对创建数组，则无参数，并只调用缺省的构造函数。
7.1.2 堆对象与构造函数如有 class CGoods{
char Name[21];
int Amount;
float Price;
float Total value;
public:
CGoods(){};
CGoods(char* name,int amount,float price){
strcpy(Name,name);
Amount=amount;
Price=price;
Total_value=price*amount; }
… …
}
7.1.2 堆对象与构造函数
void main(){
int n;
CGoods *pc,*pc1,*pc2;
pc=new CGoods(“夏利 2000”,10,118000);
pc1=new CGoods(); //调用缺省构造函数；
cout<<’输入商品类数组元素数 ’ <<endl;
cin>>n;
pc2=new CGoods[n];
……
delete pc;
delete pc1;
delete []pc2;
}
7.1.2 堆对象与构造函数这里再次强调：由堆区创建对象数组,只能调用缺省的构造函数,不能调用其他任何构造函数 。 如果没有缺省的构造函数,则不能创建对象数组 。
7.1.3 浅拷贝与深拷贝缺省拷贝构造函数，可用一个类对象初始化另一个类对象，
称为缺省的 按成员拷贝,而不是对整个类对象的 按位拷贝。 这称为浅拷贝。
P 堆对象 堆对象P
P
图 7.1 浅拷贝
7.1.3 浅拷贝与深拷贝如果类中有一个数据成员为指针，
该类的一个对象 obj1中的这个指针 p，
指向了动态分配的一个堆对象，（参见图 7.1拷贝前），如果用 obj1按成员拷贝了一个对象 obj2，这时 obj2.p也指向同一个堆对象。当析构时，如用缺省的析构函数，则动态分配的堆对象不能回收。如果在析构函数中有,delete
p;”语句，则如果先析构函数 obj1时，
堆对象已经释放，以后再析构 obj2时出现了二次释放的问题。这时就要重新定义拷贝的构造函数，给每个对象独立分配一个堆对象，称 深拷贝 。
堆对象P
P 堆对象图 7.2 深拷贝
7.1.3 浅拷贝与深拷贝
[例 7.3]定义拷贝构造函数（ copy structor）和拷贝赋值操作符（ copy Assignment Operator）实现深拷贝。
程序：Ｅ x7_3.cpp
堆内存是最常用的需要拷贝构造函数自定义的资源,如果类需要析构函数来析构资源，则类也需要一个自定义的拷贝构造函数。对象的拷贝就是深拷贝了。
7.2 链表与链表的基本操作线性表是最简单，最常用的一种数据结构。线性表的逻辑结构是 n个数据元素的有限序列（ a1,a2,…,an）。而线性表的物理结构，我们已经学习过顺序表，
也就是数组 ；另一种线性表的物理结构 ——链表
7.2 链表与链表的基本操作
7,2,1 单链表基本算法
7,2,3 双向链表
7,2,2单链表类型模板
7.2.1 单链表基本算法单链表 （ Singly Linked list） 也称线性链表 。 每个数据元素占用一个节点 （ Node） 。 一个节点包含两个域,一个域存放数据元素 info,其数据类型由应用问题决定,另一个存放指向该链表中下一个节点的指针 link。 节点定义如下：
typedef int Datatype; //数据为整型
struct node{
Datatype info;
node *link;
}
infon-1 ^info2info1info0 ……haed
图 7.3 单向链表结构
7.2.1 单链表基本算法单链表的第一个结点的地址可通过链表的表头指针 head找到,head在使用中必须妥善保存，
千万不可丢失，否则链表整个丢失，内存也发生泄漏。
单链表的插入与删除,只要改变链中结点指针的值，
无需移动表中的元素，就能实现插入和删除操作。
插入算法有三种情况，我们希望在单链表中包含数据 infoi的结点之前插入一个新元素，则 infoi
可在第一个结点，或在中间结点，也可把新结点插在链尾结点之后。
7.2.1 单链表基本算法插在链首首先新结点的 link指针指向 info0所在结点,然后,head指向新结点 。 即：
newnode→ link=head； //注意：链表操作次序非常重要
head=newnode；
newnode
infox
info0 info1 ············
·head
7.2.1 单链表基本算法插在链首首先新结点的 link指针指向 info0所在结点,然后,head指向新结点 。 即：
newnode→ link=head； //注意：链表操作次序非常重要
head=new node；
new node
infox
info0 info1
head
············
·
7.2.1 单链表基本算法插在中间首先用工作指针 p找到指定结点,而让指针 q指向紧跟其后的结点,令 infoi-1所在结点的 link指针指向新结点,而后让新结点的 link指向 infoi所在结点 。 即：
newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某结点之后
q→ link=newnode；
infox
infoi-1 infoi
p
ｑ
newnode
7.2.1 单链表基本算法插在中间首先用工作指针 p找到指定结点,而让指针 q指向紧跟其后的结点,令 infoi-1所在结点的 link指针指向新结点,而后让新结点的 link指向 infoi所在结点 。 即：
newnode→ link=p； //或 newnode→ link=q→ link；可用于插入某结点之后
q→ link=newnode；
infox
infoi-1 infoi
p
ｑ
newnode
7.2.1 单链表基本算法插在队尾只要工作指针 p找到队尾,即可链在其后：
p→ link=newnode；
newnode.link=NULL;
Infon-1 ^
infoxnewnode
······
p
^
7.2.1 单链表基本算法
^head
p0
1,向后生成链表算法：
node *createdown(){
Datatype data;
Node*head,*tail,*p;
head=new node; //建立链表头结点
P0=head;
while(cin>>data){ //回车结束
p1=new(node);//每输入一个数申请一个结点
p1->info=data; //添入数据
p0->link= p1;
P0=p1
}
return head; //返回头指针
}
7.2.1 单链表基本算法
^ info0 ^
^
head
p0
p1
1,向后生成链表算法：
node *createdown(){
Datatype data;
Node*head,*tail,*p;
head=new node; //建立链表头结点
P0=head;
while(cin>>data){ //回车结束
p1=new(node);//每输入一个数申请一个结点
p1->info=data; //添入数据
p0->link= p1;
P0=p1
}
return head; //返回头指针
}
info1
7.2.1 单链表基本算法
^ info0 ^
^
head
p0
p1
1,向后生成链表算法：
node *createdown(){
Datatype data;
Node*head,*tail,*p;
head=new node; //建立链表头结点
P0=head;
while(cin>>data){ //回车结束
p1=new(node);//每输入一个数申请一个结点
p1->info=data; //添入数据
p0->link= p1;
P0=p1
}
return head; //返回头指针
}
info1
7.2.1 单链表基本算法
2,向前生成链表算法
node *createup(){
node *head,*p;
Datatype data;
head=new node; //建立头结点
head->link=NULL;
while(cin>>data){ //建立第一个结点
p=new node;
p->info=data;
p->link= head->link ;
head->link=p;
}
return head;
}
^head
7.2.1 单链表基本算法
2,向前生成链表算法
node *createup(){
node *head,*p;
Datatype data;
head=new node; //建立头结点
head->link=NULL;
while(cin>>data){ //建立第一个结点
p=new node;
p->info=data;
p->link= head->link ;
head->link=p;
}
return head;
}
info0 ^head
p info1
7.2.1 单链表基本算法
2,向前生成链表算法
node *createup(){
node *head,*p;
Datatype data;
head=new node; //建立头结点
head->link=NULL;
while(cin>>data){ //建立第一个结点
p=new node;
p->info=data;
p->link= head->link ;
head->link=p;
}
return head;
}
info0 ^
info1
head
p
7.2.1 单链表基本算法
3.链表查找算法 （ Traversal）,按数据 （ 关键字 ） 查找：
node *traversal(node *head,Datatype data){
node *p=head->link;
while(p!=NULL||p->info!=data) p=p->link;
return p; //p为 NULL则未找到
}
返回值为指针 p,指向链表中找到的结点 。
7.2.1 单链表基本算法
4,在单链表的 p节点后插入一个信息域为 x的新节点 （ 注意只有一种情况了 ） 。
void insert(node p,Datatype x){
node *q=new node;
q->info=x;
q->link=p->link;
p->link=q;
}
7.2.1 单链表基本算法
5,删除单链表节点 *p后面节点
void del (node *p){
node *q;
q=p->link;
p->link=q->link;
delete q; //如果要把该节点移入另一个链中,则可将
q返回 。
}
7.2.2 单链表类型模板
【 例 7.4_h】 单链表类模板，本例作为一个头文件。
程序：Ｅ x7_4.h.cpp
7.2.2 单链表类型模板
【 例 7.4】 由键盘输入 16个整数,以这些整数作为结点数据,生成两个链表,一个向前生成,一个向后生成,输出两个表 。 然后给出一个整数在一个链表中查找,找到后删除它,再输出该表 。 清空该表,
再按升序生成链表并输出 。
7.2.2 单链表类型模板
#include "Ex7_4.h"
void main(){
Node<int> * P1;
List<int> list1,list2;
int a[16],i,j;
cout<<"请输入 16个整数 "<<endl;
for(i=0;i<16;i++)cin>>a[i];
for(i=0;i<16;i++){
P1=list1.CreatNode(a[i]);
list1.InsertFront(P1);//向前生成 list1
P1=list2.CreatNode(a[i]);
list2.InsertRear(P1);
}
7.2.2 单链表类型模板
list1.PrintList();
cout<<"list1长度,"<<list1.Length()<<endl;
list2.PrintList();
cout<<"请输入一个要求删除的整数 "<<endl;
cin>>j;
P1=list1.Find(j);
if(P1!=NULL){P1=list1.DeleteNode(P1);
delete P1;
list1.PrintList();
cout<<"list1长度,"<<list1.Length()<<endl; }
else cout<<"未找到 "<<endl;
list1.MakeEmpty();//清空 list1
for(i=0;i<16;i++){P1=list1.CreatNode(a[i]);
list1.InsertOrder(P1);//升序创建 list1 }
list1.PrintList();
}
7.2.3 双向链表
7.3 栈与队列的基本操作及其应用栈和队都是特殊的线性表，限制存取位置的线性结构，可以由顺序表实现，也可以由链表实现。
7.3 栈与队列的基本操作及其应用
7,3,1 栈 与 应 用
7,3,2 队 列
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
a1top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-2
……
a1
top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-2
……
a1
an-1top
bottom
进栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-1
an-2
……
a1
top
出栈
bottom
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
an-2
……
a1
top
bottom
出栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0
a1top
bottom
出栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0top
bottom
出栈
7.3.1 栈与应用栈定义为只允许在表的末端进行插入和删除的顺序表。允许进行插入和删除的一端叫做栈顶 (top)，而另一端叫栈底 (bottom)。栈中没有任何元素时，称为空栈。
a0top
bottom
出栈
7.3.1 栈与应用
【 例 7.6】 顺序栈的类模板 。
#include<assert.h>
#include<iostream.h>
template<typename T>class Stack{
int top;
T *elements;
int maxSize;
public:
Stack(int=20);
~Stack(){delete[] elements;}
void Push(const T &data);
T Pop();
T GetElem(int i);
void MakeEmpty(){top= -1;}
bool IsEmpty() const{return top== -1;}
bool IsFull() const{return top==maxSize-1;}
7.3.1 栈与应用
void PrintStack(); };
template<typename T> Stack<T>::Stack(int maxs){ maxSize=maxs;
top=-1;
elements=new T [maxSize];
assert(elements!=0); }
template<typename T> void Stack<T>::PrintStack(){
for(int i=0;i<=top;i++) cout<<elements[i]<<'\t';
cout<<endl;}
template<typename T> void Stack<T>::Push(const T &data){ assert(!IsFull());
elements[++top]=data; }
template<typename T> T Stack<T>::Pop(){ assert(!IsEmpty());
return elements[top--]; }
template<typename T> T Stack<T>::GetElem(int I){
assert(i<=top&&i>=0);
return elements[i];
}
7.3.1 栈与应用
【 例 7.7_h】 链栈的类模板，本例为头文件,Ex7_7.h”
程序,Ex7_7.h.cpp
7.3.1 栈与应用顺序栈和链栈逻辑功能是一样，尽管这里两个栈模板的成员函数功能选择稍有出入，因为顺序栈可以随机访问其中的元素，而链栈只能顺序访问，但逻辑上完全可以做到一样（物理结构不同）。顺序栈必须先开一定大小内存空间，执行起来简单，速度快，可能溢出。链栈内存空间随用随开，不会溢出，但执行复杂
（不断地动态分配），速度慢。
7.3.1 栈与应用
【 例 7.7】 模拟简单计算器,该计算器只认 + - * / 四个运算符,输入为整数 。 表达式使用＝号,清空栈用 ‘ c’
字符 。 使用 ‘ z’字符表示结束 。
程序,Ex7_7.cpp
7.3.2 队列队列 (Queue)也是一种限定存取位置的线性表。它只允许在表的一端插入，而在另一端删除。允许插入的一端称为队尾 (rear)，允许删除的一端叫做队头 (front)。每次在队尾加入新元素，加入称为进队，删除称为出队。
a0 a1 a2 … an-1…
front 元 素 移 动 方向
rear
图 7.15队列
7.3.2 队列
rear A
front
进队
7.3.2 队列
A
Brear
front
进队
7.3.2 队列
C
A
B
rear
front
进队
7.3.2 队列
D
C
A
B
进队
rear
front
7.3.2 队列
D
C
A
B
rear
front
出队
7.3.2 队列
D
C
B
rear
front
出队
7.3.2 队列
D
C
rear
front
出队
7.3.2 队列
Drear
front
出队
7.3.2 队列出队
7.4 二叉树树形结构是一类重要的非线性数据，树和二叉树是常用的树形结构。
7.4.2 二叉树的遍历
7.4.1 二叉树的概念
7.4.3 排序二叉树
7.4.1 二叉树的概念树（ Tree） 是由 n（ n≥0）个结点组成的有限集合。
如 n=0，称为空树。非空树有一个特定的结点，它只有直接后继，没有直接前驱，称之为根（ root）。除根以外的其它结点划分为 m（ m≥0）个互不相交的有限集合
T0,T1,……,Tm-1，每个集合又是一棵树，称为根的子树（ subtree）。每棵子树的根结点有且仅有一个直接前驱，但可以有 0个或多个直接后继。这是一个递归方法定义的数据结构。
7.4.1 二叉树的概念
A
B C D
E F G IH
J LK ONM
…………………
……… 0层
………
… 1层
……
2层
……
3层深度图 7.17 树的示意图下面介绍有关树的术语：
结点 （ node）,包括数据项和多个指针项,指针项数目并不固定,且无次序 。
结点的度 （ degree）,结点所拥有的子树数量 。
叶结点 （ leaf）,度为 0的结点,如 G,I,J,K,L,M，
N,O结点 。
分支结点 （ branch）,度 ≥1的结点 。
孩子结点 （ child）,若结点 x有子树,则子树根结点即为 x
的孩子结点 。
双亲结点 （ parent）,若结点 x有孩子,它即为孩子的双亲 。
兄弟结点 （ sibling）,同一双亲的结点互称为兄弟 。
结点的层次 （ level）,从根到该结点所经路径上的分支条数 。
树的深度 （ depth）,树中结点的层次数 。
树的度（ degree）,树中结点度的最大值。
7.4.1 二叉树的概念二叉树 （ Binary Tree） 是另一种独立的树形结构 。 二叉树是结点的一个有限集合,该集合或为空,或是由一个根结点及两棵树分别称为左子树和右子树的 （ 注意有左右之分 ） 互不相交的二叉树组成,其中左右子树分别可以为空子树或均为空树 。 这也是一个递归的定义 。 二叉树的特点是：每个结点最多两个孩子,并且子树有左右之分 。
二叉树的基本性质：
1,二叉树的第 i层上最多有 2i-1(i>=1)个结点；
2,深度为 h的二叉树中最多有 2h-1个结点；
3,在任一棵二叉树中,有 n0叶子结点,有 n2个度为 2的结点,则有 n0=n2+1。
7.4.1 二叉树的概念
【 例 7.9】 画出有三个结点的所有二叉树 。
解：结果见图 7.18,共 5种 。
图 7.18 5种不同的三结点二叉树
7.4.1 二叉树的概念二叉树有 满二叉树和完全二叉树,分别如图 7.19
和图 7.20，完全二叉树已有的结点排序与满二叉树相同。
1
2 3
4 5 6 7
98 1
0
1
1
1
4
1
3
1
2
1
5
图 7.19 满二叉树
1
2 3
4 5 6 7
98 1
0
图 7.20 完全二叉树
7.4.1 二叉树的概念下面给出链表储存方式的二叉树。每个结点有三个域：
数据域、左孩子指针和右孩子指针，见图 7.21。
lchild rchildinfo
图 7.21 二叉树结点
7.4.1 二叉树的概念二叉树类结点类模板定义如下：
template<typename T>class BinaryTree;
template<typename T>class Node{
Node<T> *lchild,*rchild;
T info;
public:
Node(){lchild=NULL;rchild=NULL;}
Node(T data,Node<T> *left=NULL,Node<T> *right=NULL){
info=data;
lchild=left;
rchild=right;
}
7.4.1 二叉树的概念
T Getinfo(){return info;}
void setinfo(const T &data){info=data
Node<T> *Getleft(){return lchild;}
Node<T> *Getright(){return rchild;}
void setleft(Node<T> *left){lchild=left;}
void setright<Node<T> *right){rchild=right;}
friend class BinaryTree<T>;
}
7.4.2 二叉树的遍历所 谓 二 叉 树 的 遍 历 （ binary tree
traversal）,就是遵从某种次序,查巡二叉树的所有结点,每个结点都被访问一次,而且仅访问一次 。 所谓,访问,指对结点施行某些操作,
但不破坏它原来的数据结构 。
遍历二叉树有不同次序，规定先左后右，令
L,R,V分别代表遍历一个结点的左右子树和访问该结点的操作，有三种方式,前序遍历
（ VLR），中序遍历（ LVR），后序遍历（ LRV） 。
7.4.2 二叉树的遍历例如：前序遍历访问次序为 ABDEGCFH。
A
B
D
C
E
G
F
H
图 7.22 二叉树遍历中序遍历结果为
D B G E A F H C。
后序遍历结果为
D G E B H F C A。
7.4.2 二叉树的遍历中序遍历 （ inorder traversal）,前序遍历
（ preorder traversal） 和后序遍历 （ postorder
traversal） 算法如下：
【 例 7.10】 二叉树类模板（其中二叉树生成借用二叉排序树，见下节）。特别注意插入结点时，第二参数为指针的引用！否则不能建立树。为什么？请读者自己思考。
程序,Ex7_10.cpp
7.4.2 二叉树的遍历
【 例 7.13】 某二叉树先序遍历为
ABCEFDGHIJK，中序遍历为
ECFBDGAIHJK绘出该二叉树。
解：由先序知 A为根结点,而 E F B D G为左子树,I H J K为右子树 。 由先序中的 B C E
F D G知 B为左子树根结点,由中序中的 E C
F B D G知 E C F为其左子树,而 DG为右子树 。
再由先序 C E F知 C为左子树根结点，由中序 E C F知 E为 C左子树,F为的右子树。再由先序 D G知,D为 B的右子树根结点，由中序 D G知 G为 D的右子树。按同样方法推出 A
的右子树。结果如图 7.23。可以证明已知先序和中序访问次序可以唯一确定一棵二叉树。
A
B
C D
E F G
H
I J
K
图 7.23 例 7.11二叉数
7.4.3 排序二叉树二叉排序树 （ Binary Sorting Tree） 又称二叉搜索树 （ Binary Search
Tree）,是一种特殊结构的二叉数,作为一种排序和查找的手段,对应有序表的对半查找,通常亦被称为数表 。 其定义也是递归的 。
二叉排序树的定义,二叉排序树或者是空树或者是具有下述性质的二叉数,
其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于等于根结点的数据值,左子树和右子树又各是一棵二叉排序树 。
二叉排序树的结点插入 （ 可生成排序二叉树 ） 生成算法：对任意一组数据元素序列 {a0,a1,a2,…,an-1}。 要生成一棵二叉排序树的过程为：
1,令 a0为二叉树的根结点 。
2,若 a1<a0,令 a1为 a0左子树的根结点,否则 a1为 a0右子树的根结点 。
3,如 ai小于根结点,则去左子树,否则去右子树,按此法查找,直到成为 空树,则安放此位置 。 这步就是插入算法 。
7.4.3 排序二叉树二叉排序树用中序遍历就可以得到由小到大的有序序列，如图 7.24可得有序序列｛ 8,10,11,12，
15,16,18,22,24,26,29｝。
10
18
26
8 12 22 29
11 2416
15
图 7.24 二叉排序树例
7.4.3 排序二叉树建立二叉排序树算法程序如下：
template<typename T>void BinaryTree<T>::Insert(const T &data,Node<T> * &b){
if(b==NULL){
b=new Node<T>(data);
if(b==NULL){
cout<<"空间不足 "<<endl;
exit(1); } }
else if(data<b->info) Insert(data,b->lchild);
else Insert(data,b->rchild);
}
template<typename T>void BinaryTree<T>::Creat(T* data,int n){
for(int i=0;i<n;i++) Insert(data[i],root);
}
7.4.3 排序二叉树
【 例 7.15】 排序二叉树查找函数 。
算法：只要中序遍历即可,但递归慢,下面给出迭代的查找算法 。
template<typename T>Node<T> *BinaryTree<T>::Find(const T
&data,Node<T> *b){//查找
if(b!=NULL){
Node<T> *temp=b;
while(temp!=NULL){
if(temp->info==data)return temp;
if(temp->info<data)temp=temp->rchild;
else temp=temp->lchild;
}
}
return NULL;
}
7.5 MFC对象和 Windows对象的关系
MFC对象是 C++对象，而且是特指封装了 Window对象的
C++对象，不是任意的 C++对象。本节讨论 MFC对象与
Window对象的联系，以最典型的的窗口类（ CWnd）为例，讨论 CWnd类对象与 Windows窗口对象的关系。参见图 7.26。
.
.
.
.
其它成员
m_hWnd hwnd
CWnd类对象 HWND句柄类型
wnd
windows对象句柄
Windows
操作系统窗口对象图 7.26 MFC窗口对象与 Windows窗口对象的关系
7.5 MFC对象和 Windows对象的关系
MFC的窗口对象 wnd是 C++类的实例,即 CWnd类或其派生类的实例,
是由 CWnd类或其派生类的构造函数创建的,而最终由 CWnd类或其派生类的析构函数撤消 。 hwnd是 HWND句柄类型的实例,为它建立了一个
Windows操作系统的对象 。 然后把这个句柄放入 CWnd类对象 wnd的成员数据 m_hwnd中 。 这样 wnd就包含了一个 Windows操作系统的窗口对象 。 程序段如下：
CWnd wnd;//定义窗口类 （ CWnd） 的对象 wnd
HWND hwnd;//定义窗口句柄 hwnd
hwnd=CreateWindows(......);//调用 API函数 CreateWindows(...)建立一个 Windows窗口类实例
wnd.Attach(hwd);//把 Windows窗口实例的句柄链到 CWnd对象 hwnd
上
......
Destrory Window(hwnd);//调用 API函数撤消 Windows窗口
