第七章 动态内存分配
本章首先介绍程序运行时 动态内存分配 （ dynamic
memory allocation）的概念与方法。到目前为止，本教材介
绍的程序设计中，变量和对象在 内存中的分配 都是编译器在 编
译程序时安排 好了的，这带来了极大的不便，如数组必须大开
小用，指针必须指向一个已经存在的变量或对象。动态内存分
配解决了这个问题。本章将进一步讨论拷贝构造函数；还要学
习有关 数据结构 的 链表 和 栈 的基本知识、算法和应用。
7.1 堆内存分配
7.2 链表与链表的基本操作
7.3 栈的概念和 应用
7.1 堆内存分配
C/C++定义了 4个内存区间：代码区，全局变
量与静态变量区，局部变量区即栈区,动态存储区，
即堆（ heap）区或自由存储区（ free store） 。
通常定义变量（或对象），编译器在编译时都可以根
据该变量（或对象）的类型知道所需内存空间的大小，
从而系统在适当的时候为他们分配确定的存储空间。
这种内存分配称为 静态存储分配
有些操作对象只有在程序运行时才能确定，这
样编译器在编译时就无法为他们预定存储空间，只能
在程序运行时，系统根据运行时的要求进行内存分配，
这种方法称为 动态存储分配 。所有动态存储分配都在
堆区中进行。
7.1.1 堆内存的分配与释放
当程序运行到需要一个动态分配的变量或对象时, 必须
向系统 申请取得 堆中的一块所需大小的存贮空间, 用于存贮
该变量或对象 。 当不再使用该变量或对象时, 也就是它的生
命结束时, 要 显式释放 它所占用的存贮空间, 这样系统就能
对该堆空间进行再次分配, 做到重复使用有限的资源 。
在 C++中, 申请和释放堆中分配的存贮空间, 分别使用
new和 delete的两个运算符来完成, 其使用的格式如下：
指针变量名 =new 类型名 (初始化式 )；
delete 指针名 ;
new运算符 返回 的是一个指向所分配类型变量（对象）
的 指针 。对所创建的变量或对象，都是通过该指针来间接操
作的，而 动态创建的对象本身没有名字。
7.1.1 堆内存的分配与释放
一般定义变量和对象时要用标识符命名，称 命名对象,
而动态的称 无名对象 (请注意与栈区中的临时对象的区别，两
者完全不同：生命期不同，操作方法不同，临时变量对程序
员是透明的 )。堆区是不会自动在分配时做初始化的（包括清
零），所以必须用初始化式 (initializer)来显式初始化。 new
表达式的操作序列如下,从堆区分配对象，然后用括号中的
值初始化该对象 。从堆区分配对象时,new表达式调用库操
作符 new()。例如：
int *pi=new int(0);
它与下列代码序列 大体 等价：
int ival=0;
int *pi=&ival;
只是 pi现在所指向的变量是由库操作符 new()分配的，位于
程序的堆区中，并且该 对象未命名 。
7.1.1 堆内存的分配与释放
堆
０Ｐ i
下面看演示：
１．用初始化式 (initializer)来显式初始化
int *pi=new int(0);
２, 当 pi生命周期结束时,
必须释放 pi所指向的目标：
delete pi;
注意这时释放了 pi所指的目标的内存空间，也就是撤销了
该目标，称动态内存释放（ dynamic memory
deallocation），但 指针 pi本身并没有撤销,它自己仍然
存在，该指针所占内存空间并未释放。
7.1.1 堆内存的分配与释放
对于数组进行动态分配的格式为：
指针变量名 = new 类型名 [下标表达式 ];
delete [ ] 指向该数组的指针变量名 ;
两式中的 方括号 是非常重要的，两者必须配对使用，
如果 delete语句中少了方括号，因编译器认为该指针是指
向数组第一个元素的指针，会产生 回收不彻底 的问题（ 只
回收了第一个元素所占空间 ）,加了方括号后就转化为指
向数组的指针，回收整个数组 。 delete [ ]的方括号中 不需
要 填 数组元素数,系统自知。即使写了，编译器也忽略。
请注意,下标表达式”不是常量表达式,即它的值不必在
编译时确定,可以在运行时确定 。
7.1.1 堆内存的分配与释放
动态数组的建立与撤销
#include <iostream.h>
#include <string.h>
void main()
{ int n;
char *pc;
cout <<,请输入动态数组的元素个数,";
cin >> n; //在运行时确定，可输入 17
pc = new char[n]; //申请 17个字符（可装 8个
汉字和一个结束符）的内存空间
strcpy(pc,"堆内存的动态分配 ");
cout << pc << endl;
delete []pc; //释放 pc所指向的 n个字符的内存空间
return ;
}
7.1.1 堆内存的分配与释放
动态分配数组有三个特点：
1,变量 n在编译时没有确定的值，而是在运行中输入,按运
行时所需分配堆空间,这一点是动态分配的优点，可克服
数组“大开小用”的弊端，在表、排序与查找中的算法，
若用动态数组，通用性更佳。 delete []pc 是将 n个字符
的空间释放，而用 delete pc 则只释放了一个字符的空间；
2,如果有一个 char *pc1，令 pc1=p，同样可用 delete []
pc1来释放该空间。尽管 C++不对数组作边界检查，但 在
堆空间分配时，对数组分配空间大小是纪录在案的 。
3,没有初始化式（ initializer）,不可对动态数组进行初始
化 。
7.1.1 堆内存的分配与释放
指针使用的几个问题：
１．动态分配失败。 返回一个空指针（ NULL），表示发生了异常，堆资源
不足，分配失败。
２．指针删除与堆空间释放。删除一个指针 p（ delete p;） 实际意思
是删除了 p所指的目标（变量或对象等），释放了 它所占的堆空间，而不
是删除ｐ本身，释放堆空间后，ｐ成了 空悬指针 。
３,内存泄漏（ memory leak）和重复释放。 new与 delete 是配对使用
的,delete只能释放堆空间。如果 new返回的指针值丢失，则所分配的堆
空间无法回收，称内存泄漏，同一空间重复释放也是危险的，因为 该空间
可能已另分配,所以必须妥善保存 new返回的指针，以保证不发生内存泄
漏，也必须保证不会重复释放堆内存空间。
４．动态分配的变量或对象的生命期。 无名对象的生命期并不依赖于建立
它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用。 我们
也称堆空间为自由空间（ free store）就是这个原因。 但必须记住释放该
对象所占堆空间，并只能释放一次，在函数内建立，而在函数外释放是一
件很容易 失控 的事，往往会出错。
7.1.2 堆对象与构造函数
通过 new 建立的对象要调用构造函数，通过 deletee 删
除对象也要调用析构函数。例如：
CGoods *pc; // 定义一个物资类的指针
pc = new CGoods; //分配堆空间，并构造一个无名的
CGoods 对象，并调用构造函数；
…….
delete pc; //先析构，然后将内存空间返回给堆；
堆对象的生命期并不依赖于建立它的作用域，所以除非程
序结束，堆对象（无名对象）的生命期不会到期，并且需要显
式地用 delete语句析构堆对象，上面的堆对象在执行 delete语
句时,C++自动调用其析构函数。
正因为构造函数可以有参数，所以 new后面类（ class）类
型也可以有参数。这些参数即构造函数的参数。但对创建数组，
则无参数，并只调用缺省的构造函数。见下例类说明：
7.1.2 堆对象与构造函数
class Cgoods {
private:
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];
//动态建立数组, 不能初始化, 调用 n次缺省构造函数
……
delete pc;
delete pc1;
delete []pc2;
}
这里再次强调,由堆区创建对象数组, 只能调用缺省的
构造函数, 不能调用其他任何构造函数 。
7.1.3 浅拷贝与深拷贝
缺省拷贝构造函数,可用一个类对象初始化另一个
类对象，称为缺省的 按成员拷贝,而不是对整个类对象
的 按位拷贝。 这称为 浅拷贝。
P 堆对象 堆对象P
P
图 7.1 浅拷贝
拷贝前
拷贝后
7.1.3 浅拷贝与深拷贝
如果类中有一个数据成员为指针，
该类的一个对象 obj1中的这个指针 p，
指向了动态分配的一个堆对象，（参见
上图拷贝前），如果用 obj1按成员拷贝
了一个对象 obj2，这时 obj2.p也指向同
一个堆对象。当析构时，如用缺省的析
构函数，则动态分配的堆对象不能回收。
因为该堆对象还在被 obj1使用，如果在
析构函数中有,delete p;”语句，则如
果先析构函数 obj1时，堆对象已经释放，
以后再析构 obj2时出现了二次释放的问
题。这时就要重新定义拷贝的构造函数，
给每个对象独立分配一个堆对象，称 深
拷贝。 这时 先拷贝对象主体，再为 obj2
分配一个堆对象，最后用 obj1的堆对象
拷贝 obj2的堆对象 。
堆对
象P
P 堆对象
图 7.2 深拷贝
7.1.3 浅拷贝与深拷贝
定义拷贝（ copy structor）和拷贝赋值操作符（ copy
Asignment Operator）实现深拷贝。
学生类定义：
class student {
private:
char *pName; //指针成员
public:
student() {
cout << "Constructor";
pName = NULL;
cout <<,缺省” << endl;
}
student(char *pname);
student(student &s); //拷贝构造函数
~student();
student & operator=(student &s); //拷贝赋值操作符
};
7.1.3 浅拷贝与深拷贝
带参数 构造函数：
student::student(char *pname)
{ cout << "Constructor";
if(pName = new char[strlen(pname)+1])
strcpy(pName,pname);
cout << pName << endl;
}
拷贝构造函数：
student::student(student &s)
{ cout << "Copy Constructor";
if(s.pName) {
if(pName = new char[strlen(s.pName)+1])
strcpy(pName,s.pName);
} //加一不可少，否则串结束符冲了其他信息，析构会出错！
else pName=NULL;
cout << pName << endl;
}
7.1.3 浅拷贝与深拷贝
析构函数：
student::~student()
{ cout << "Destructor,<< pName << endl;
if(! pName) delete []pName; //释放字符串
}
拷贝赋值操作符：
student &student::operator=(student &s)
{ cout << "Copy Assign operator";
delete []pName; //如原来已分配，应先撤销，再重分配
if(s.pName) {
if(pName = new char[strlen(s.pName)+1])
strcpy(pName,s.pName);
}
else pName=NULL;
cout << pName << endl;
return *this;
}
7.2 链表与链表的基本操作
在数据结构的描述中,线性表 是最简单，最常
用的一种数据结构。线性表的逻辑结构是 n个数据
元素的有限序列（ a1,a2,…,an ）。而线性表的 物
理结构,我们已经学习过顺序表，也就是 数组 ；
另一种线性表的物理结构 ——链表 。
动态内存分配 的一个重要应用，就是如何用它
来表达一类复杂的数据结构 -链表，那什么是链表
呢？链表是一种常用的数据结构，它不同于数组，
数组的长度必须事先确定的，并且它的数据是顺序
存放的。但有时候在处理数据时，由于事先不知道
所处理的数据个数，所以往往将数组定的足够大来
处理所有情况，这很容易造成内存空间浪费，而链
表是一种动态进行存储分配的数据结构，每个结点
也不需要顺序存放，它们是通过指针相互连接而成
的表，所以叫链表。
7.2.1 单链表基本算法
单链表 （ Singly Linked list） 也称线性链表 。 每个数据元
素占用一个节点 （ Node） 。 一个节点包含两部分域, 一部分域
存放数据对象的数据成员, 其内容由应用问题决定, 另一部分存
放指向该链表中下一个节点的指针 next。 节点定义如下：
struct node {
Datatype1 info1;
Datatype2 info2;
Datatype2 info2;
……
struct node *next;
}
在 C/C++中允许结构 （ 或对象 ） 成员是 结构自身的指针类
型, 通过指针引用自身这种类型的结构 。 但结构成员决不能是结
构自身类型, 即结构不能自己定义自己, 这会导致一个无穷递归
的定义 。
struct student {
int num;
float score;
strcut student *next;
} // 学生节点定义
7.2.1 单链表基本算法
单向链表特点：
1、每个结点都是个结构，里面包含着结构指针
2、链表都有个头指针，不然无法访问链表
3、每个结点里的指针都是指向下一个结点的地址
4、链表的最后结点结构指针应为空，表示该链表已结束
单链表的第一个结点的地址可通过链表的表头指针 head找到，
head在使用中必须妥善保存，千万不可丢失，否则链表整个丢失，
内存也发生泄漏。
链表操作,建立链表, 显示链表内容,在链表 插入结点, 删
除链表结点,等操作。
head num
score
next
num
score
next
num
score
NULL
...
节点
7.2.1 单链表基本算法
建立链表：
下面以建立学生情况的单向链表为例进行说明，假设从键盘
输入时，如果学号为 0表示，链表建立结束。我先讲一下算法：
1、先设置三个指向 student的结构变量指针：
struct student *head,*p1,*p2;
2、使用 new 函数动态申请一个结点的空间，并使 p1和 p2 都
指向新结点 p1 = p2 = new struct student;
3、有了第一结点后，从键盘上输入数据给新结点成员
cin >> p1->num >> p1->score;
然后将 p1赋给 head，让 head也指向第一个结点
4、接着再申请第二个结点，并使 p1指向新结点，再从键盘输
入数据，通过下述方法将新结点链入链表，即使第一个结点
p2中的 next指向新结点 p2->next = p1; 然后让 p2指向 p1，
即 p2=p1
5、然后再申请第三个 …….,重复 4的步骤，直到最后输入的学
号为 0为止
6、最后将 p2->next = NULL
7.2.1 单链表基本算法
head
int n = 0; // 7-2-1.cpp
struct student *create(void)
{ struct student *head,*p1,*p2;
p1 = p2 = new struct student;
cin >> p1->num >> p1->score;
head = NULL;
while(p1->num != 0) {
n ++;
if(n == 1) head = p1;
else p2->next = p1;
p2 = p1;
p1 = new struct student;
cin >> p1->num >> p1->score;
}
p2->next = NULL;
return(head);
}
7.2.1 单链表基本算法
那么我们在主函数中可以：
main()
{ struct student *head;
head = create();
print(head);
}
输出链表：
将链表中各结点数据进行遍历输出，它的程序如下：
void print(struct student *head)
{ struct student *p = head;
if(head != NULL)
do {
cout << p->num <<,,,<< p->score << endl;
p = p->next;
} while(p!=NULL);
}
7.2.1 单链表基本算法
删除结点：
就是删除已知链表中的结点, 譬如要删除某个学号的结点,
首先通过寻找该学号所在的结点, 先设置两个结构指针 p1和
p2,并使 p1指向第一个结点, 并检查该结点是否要删除的结
点, 如果不是, 则将 p1指针赋给 p2,并将 p1指针指向下一个
结点, 如果指针 p1所指向的结点还不是要删除的结点, 则再将
p1赋给 p2,p1再下移一个结点, 直到链表搜索完毕 。 找到后
要分两种情况进行分析：
1,如果要删除的是头结点, 那么只需将 p1->next赋给头指针
head,就是说让头指针指向原链表中的第二个结点, 这时相当
于第一个结点被, 删除, 或架空不起作用, 然后用 delete p1
函数将第一结点空间释放 。
2,如果要删除的 p1结点不是头结点, 那么则将 p1->next赋
给 p2->next,这样就跳过 p1结点, 相当于 P1被删除 。
7.2.1 单链表基本算法
struct student *delete(struct student *head,int num)
{ struct student *p1,*p2;
if(head == NULL) {
cout <<,This list is NULL” << endl;
return(NULL);
}
p1 = head;
while(p1->num != num && p1->next != NULL){
p2 = p1;
p1 = p1->next;
}
if(p1->num == num) {
if(p1 == head) head = p1->next; // 删除首结点
else p2->next = p1->next; // 删除中间或尾结点
cout <<,delete:” << num << endl;
delete p1;
} else cout << num <<, not been found !” << endl;
return(head);
}
7.2.1 单链表基本算法
插入节点：
就是将一个已知的 p0结点插入到一个已存在的链表中, 假
设已有链表按照从小到大的学号来排列 。 当然, 在插入操作中
要根据学号找到合适的插入位置 。 算法如下：
要找到插入的位置：设置两个结构指针 p1和 p2,并使 p1指
向第一个结点, 将 p0->num与 p1->num进行比较, 如果前者
大于后者, 则将指针 p2指向 p1所在的结点, 然后将 p1指针后移
到下一个, 然后继续进行比较, 并移动 p1和 p2指针, 直到 p0-
>num,= p1->num为止 。 那么就是说已经找到要插入的位置,
即将 p0插入到 p1指针所指向的结点之前, p2之后 。
将 p0结点插入到指定位置, 有三种情况：
1,当插入的位置在首结点之前, 则将 p0赋给 head,再将 p1赋
给 p0->next ；
2,当插入的位置在尾结点之后, 则将 p0赋给 p1->next,再将
NULL赋给 p0->next ；
3,当插入位置位于 p2和 p1之间, 则将 p0赋给 p2->next,再
将 p1赋给 p0->next；
7.2.1 单链表基本算法
struct student insert(struct student *head,struct
student *stud)
{ struct student *p0,*p1,*p2;
p1 = head; p0 = stud;
if(head == NULL) {
head = p0; p0->next = NULL; return(head);
}
while((p0->num > p1->num) &&
(p1->next != NULL)) {
p2 = p1; p1 = p1->next;
}
if(p0->num <= p1->num) {
if(head == p1) head = p0; // 插在头部 //
else p2->next = p0; // 插在 p2和 p1之间 //
p0->next = p1;
} else { // 插到最后 //
p1->next = p0; p0->next = NULL; }
return(head);
}
7.2.2 单链表操作提问
已知两条同类型的链表的头指针分别是 heada
和 headb,请编程将这两条独立的链表串联起来,
即 headb接在 heada的末尾, 形成的合并后的新链
表头指针为 heada。
heada
……
headb
……
7.2.2 单链表操作提问
Struct student * combineList(heada,headb)
Struct student *heada,*headb;
{ Struct student *p;
p = heada;
if(p != NULL) {
while(p->next != NULL) p = p->next;
p->next = headb;
else heada = headb;
return heada;
}
7.3 栈与应用
栈定义为只允许在表的一端进行插入和删除的线性表 。它占用一段
连续的的内存空间，有两个端点,允许进行插入和删除的一端叫做 栈顶
(top)，而另一端固定的叫 栈底 (bottom)。 栈中没有任何元素时，称为空
栈，操作只能在栈顶进行。参见下图，设给定栈 s=(a0,a1,……, an-
1)，称 a0为栈底,an-1为栈顶。进栈时最先进栈的 a0在最下面,an-1在
最上面，后来居上。而出栈时顺序相反，最后进栈的 an-1最先出栈，而
最先进栈的 a0最后出栈。所以栈又称作 后进先出（ LIFO,Last In First
Out）的线性表 。
a0
an-2
……
a1
an-1
bottom
进栈
top
sp
出栈
7.3.1 栈的概念
栈的操作有两种,push（压入或进栈） 和 pop（弹出或出
栈） 。在栈刚开始建立时,栈顶指针 sp是指向栈底，如下图 a，
如果向栈内 push一个数据 8，则系统把 8写入 sp所指向的内存，
然后 sp++，如下图 b所示。如再压入数据 5，则系统把 5写入
sp所指向的内存，然后 sp++，如下图 c所示，总之，栈顶 sp所
指向的内存是存放最新需要压入的数据。由栈内弹出数据时，
先执行 sp=sp-1，然后返回 sp所指向的数据，就是 5，如下图 d
所示，如果现在还有一个数据 20需要压入的，那么就将 5数据
覆盖，结果如下图 e，因为数据 5已经被弹出，所以覆盖是没有
问题的。
sp
图 a
8
sp
图 b
5
8
sp
图 c
5
8
sp
图 d
20
8
sp
图 e
7.3.1 栈的建立
栈类的数据定义：
#define STACKSIZE 10
Class Stack {
private:
long buffer[STACKSIZE];
long *sp;
public:
Stack() { sp = buffer; }
~Stack() { };
void push(long data) {
if(sp >= buffer+STACKSIZE)
cerr <<,Stack overflow !” << endl;
else {
*sp ++ = data;
cout << data <<, is pushed !” << endl;
}
}
7.3.1 栈的建立
long pop() {
if(sp <= buffer) {
cerr <<,Stack is Empty!” << endl;
return 0;
}
else return *--sp;
}
};
main()
{ Stack a;
a.push(351); a.push(7075461); a.push(3225);
cout << endl;
cout << a.pop() <<, is poped” << endl;
cout << a.pop() <<, is poped” << endl;
cout << a.pop() <<, is poped” << endl;
cout << a.pop() <<, is poped” << endl;
}
N
c
b
a
＊
＋
O
＊
＋ a
t1
d
e
N
a
t1
d
e
＋＋
／
－
O
／
－ －
＋
O
－
＋
N
t1
a
t2
t1
a
t2
t3
a
N
t3
a
N
＋
O
＋
O
b*c->t1 d/e->t2 t
1-t2->t3 a+t3->t4
N：数栈 O：运算符
(a) (b) (c) (d) (e)
表达式运算
栈可用于 表达式的计算 。现考虑最简单的 +,-,*,/四个运算符和结束
符＝组成的算术表达式，只有 两个优先级,先 */，后 +-。设有,a+b*c-d/e=
为实现运算符的优先级，采用两个栈：一个 数栈,一个 运算符栈 。数
栈暂存操作数，运算符栈暂存运算符。 从左向右扫描算术表达式,遇到 操作
数, 压入数栈 ；遇到 运算符,则 与运算符栈栈顶的运算符比较优先级,若新
的运算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符出栈，与数
字栈出栈的两个数据进行运算，结果压入数栈，再将新运算符压栈。继续扫
描，直到遇到＝号，扫描结束。栈中数据继续按前面规则出栈。
7.3.2 栈的应用
7.3.2 栈的应用
模拟简单计算器, 该计算器只认 + - * / 四个运算符, 输入为整数 。 表达式
结束符使用＝号, 清空栈用 ‘ c’字符 。 使用 ‘ z’字符表示结束 。
简易计算器类定义,// 7-3-2.cpp
class Calculator {
private:
Stack Nstack; // 处理操作数
Stack Ostack; // 处理运算符
public:
Calculator(void) { };
void Cal(void); //计算器运算程序
void GetTwoNum(int &Num1,int &Num2);
void Compute(char Opr);
void Clear(void);
};
void Calculator::Clear() {
Nstack.Empty(); Ostack.Empty();
}
void Calculator::GetTwoNum(int &Num1,int &Num2) {
Num1=Nstack.Pop(); Num2=Nstack.Pop();
}
7.3.2 栈的应用
void Calculator::Compute(char Opr) {
int Num1,Num2;
if(Opr != ‘=‘ ) GetTwoNum(Num1,Num2);
switch(Opr) {
case '+',Nstack.Push(Num2 + Num1); break; //结果压栈
case '-',Nstack.Push(Num2 - Num1); break;
case '*',Nstack.Push(Num2 * Num1); break;
case '/',Nstack.Push(Num2 / Num1); break;
case '=',cout << Nstack.Pop() << endl; //输出结果
}
}
最重要的计算函数：
void Calculator::Cal() {
bool b1=true,b2=true;
char ch1,ch2,str[50];
int k = -1;
while(b2) {
cin >> ch1;
if(ch1 >= '0‘ && ch1 <= '9') {
k++;
str[k] = ch1;
} //数字字符添入串中
7.3.2 栈的应用
else {
if(k>=0) {
str[k+1] = '\0'; //数字串生成
Nstack.Push(atoi(str)); //数字串转换为整数后压栈
k=-1;
}
switch(ch1) {
case 'c',Clear();break;
case '+',case '-':
while(! Ostack.IsEmpty()) {
ch2=Ostack.Pop(); //不会有比 '＋ ' '－ '优先级低的
Compute(ch2);
}
Ostack.Push(ch1); break;
case '*':case '/':
while(!Ostack.IsEmpty() && b1) {
ch2=Ostack.Pop(); //把栈顶运算符弹出
if(ch2 == '*‘ || ch2 == '/') //比较优先级
Compute(ch2); //新的优先级并不高
else { //新的优先级高
Ostack.Push(ch2); //先把原栈中的
b1=false; //运算符压回去
}
}
Ostack.Push(ch1); //再把新的运算符压栈
b1=true; break; //将 b1复原
case '=':
while(!Ostack.IsEmpty()) {
ch2=Ostack.Pop();
Compute(ch2);
}
Compute(ch1); break;
}
if(ch1 == 'z') b2=false;
}
}
7.3.2 栈与应用
本章首先介绍程序运行时 动态内存分配 （ dynamic
memory allocation）的概念与方法。到目前为止，本教材介
绍的程序设计中，变量和对象在 内存中的分配 都是编译器在 编
译程序时安排 好了的，这带来了极大的不便，如数组必须大开
小用，指针必须指向一个已经存在的变量或对象。动态内存分
配解决了这个问题。本章将进一步讨论拷贝构造函数；还要学
习有关 数据结构 的 链表 和 栈 的基本知识、算法和应用。
7.1 堆内存分配
7.2 链表与链表的基本操作
7.3 栈的概念和 应用
7.1 堆内存分配
C/C++定义了 4个内存区间：代码区，全局变
量与静态变量区，局部变量区即栈区,动态存储区，
即堆（ heap）区或自由存储区（ free store） 。
通常定义变量（或对象），编译器在编译时都可以根
据该变量（或对象）的类型知道所需内存空间的大小，
从而系统在适当的时候为他们分配确定的存储空间。
这种内存分配称为 静态存储分配
有些操作对象只有在程序运行时才能确定，这
样编译器在编译时就无法为他们预定存储空间，只能
在程序运行时，系统根据运行时的要求进行内存分配，
这种方法称为 动态存储分配 。所有动态存储分配都在
堆区中进行。
7.1.1 堆内存的分配与释放
当程序运行到需要一个动态分配的变量或对象时, 必须
向系统 申请取得 堆中的一块所需大小的存贮空间, 用于存贮
该变量或对象 。 当不再使用该变量或对象时, 也就是它的生
命结束时, 要 显式释放 它所占用的存贮空间, 这样系统就能
对该堆空间进行再次分配, 做到重复使用有限的资源 。
在 C++中, 申请和释放堆中分配的存贮空间, 分别使用
new和 delete的两个运算符来完成, 其使用的格式如下：
指针变量名 =new 类型名 (初始化式 )；
delete 指针名 ;
new运算符 返回 的是一个指向所分配类型变量（对象）
的 指针 。对所创建的变量或对象，都是通过该指针来间接操
作的，而 动态创建的对象本身没有名字。
7.1.1 堆内存的分配与释放
一般定义变量和对象时要用标识符命名，称 命名对象,
而动态的称 无名对象 (请注意与栈区中的临时对象的区别，两
者完全不同：生命期不同，操作方法不同，临时变量对程序
员是透明的 )。堆区是不会自动在分配时做初始化的（包括清
零），所以必须用初始化式 (initializer)来显式初始化。 new
表达式的操作序列如下,从堆区分配对象，然后用括号中的
值初始化该对象 。从堆区分配对象时,new表达式调用库操
作符 new()。例如：
int *pi=new int(0);
它与下列代码序列 大体 等价：
int ival=0;
int *pi=&ival;
只是 pi现在所指向的变量是由库操作符 new()分配的，位于
程序的堆区中，并且该 对象未命名 。
7.1.1 堆内存的分配与释放
堆
０Ｐ i
下面看演示：
１．用初始化式 (initializer)来显式初始化
int *pi=new int(0);
２, 当 pi生命周期结束时,
必须释放 pi所指向的目标：
delete pi;
注意这时释放了 pi所指的目标的内存空间，也就是撤销了
该目标，称动态内存释放（ dynamic memory
deallocation），但 指针 pi本身并没有撤销,它自己仍然
存在，该指针所占内存空间并未释放。
7.1.1 堆内存的分配与释放
对于数组进行动态分配的格式为：
指针变量名 = new 类型名 [下标表达式 ];
delete [ ] 指向该数组的指针变量名 ;
两式中的 方括号 是非常重要的，两者必须配对使用，
如果 delete语句中少了方括号，因编译器认为该指针是指
向数组第一个元素的指针，会产生 回收不彻底 的问题（ 只
回收了第一个元素所占空间 ）,加了方括号后就转化为指
向数组的指针，回收整个数组 。 delete [ ]的方括号中 不需
要 填 数组元素数,系统自知。即使写了，编译器也忽略。
请注意,下标表达式”不是常量表达式,即它的值不必在
编译时确定,可以在运行时确定 。
7.1.1 堆内存的分配与释放
动态数组的建立与撤销
#include <iostream.h>
#include <string.h>
void main()
{ int n;
char *pc;
cout <<,请输入动态数组的元素个数,";
cin >> n; //在运行时确定，可输入 17
pc = new char[n]; //申请 17个字符（可装 8个
汉字和一个结束符）的内存空间
strcpy(pc,"堆内存的动态分配 ");
cout << pc << endl;
delete []pc; //释放 pc所指向的 n个字符的内存空间
return ;
}
7.1.1 堆内存的分配与释放
动态分配数组有三个特点：
1,变量 n在编译时没有确定的值，而是在运行中输入,按运
行时所需分配堆空间,这一点是动态分配的优点，可克服
数组“大开小用”的弊端，在表、排序与查找中的算法，
若用动态数组，通用性更佳。 delete []pc 是将 n个字符
的空间释放，而用 delete pc 则只释放了一个字符的空间；
2,如果有一个 char *pc1，令 pc1=p，同样可用 delete []
pc1来释放该空间。尽管 C++不对数组作边界检查，但 在
堆空间分配时，对数组分配空间大小是纪录在案的 。
3,没有初始化式（ initializer）,不可对动态数组进行初始
化 。
7.1.1 堆内存的分配与释放
指针使用的几个问题：
１．动态分配失败。 返回一个空指针（ NULL），表示发生了异常，堆资源
不足，分配失败。
２．指针删除与堆空间释放。删除一个指针 p（ delete p;） 实际意思
是删除了 p所指的目标（变量或对象等），释放了 它所占的堆空间，而不
是删除ｐ本身，释放堆空间后，ｐ成了 空悬指针 。
３,内存泄漏（ memory leak）和重复释放。 new与 delete 是配对使用
的,delete只能释放堆空间。如果 new返回的指针值丢失，则所分配的堆
空间无法回收，称内存泄漏，同一空间重复释放也是危险的，因为 该空间
可能已另分配,所以必须妥善保存 new返回的指针，以保证不发生内存泄
漏，也必须保证不会重复释放堆内存空间。
４．动态分配的变量或对象的生命期。 无名对象的生命期并不依赖于建立
它的作用域，比如在函数中建立的动态对象在函数返回后仍可使用。 我们
也称堆空间为自由空间（ free store）就是这个原因。 但必须记住释放该
对象所占堆空间，并只能释放一次，在函数内建立，而在函数外释放是一
件很容易 失控 的事，往往会出错。
7.1.2 堆对象与构造函数
通过 new 建立的对象要调用构造函数，通过 deletee 删
除对象也要调用析构函数。例如：
CGoods *pc; // 定义一个物资类的指针
pc = new CGoods; //分配堆空间，并构造一个无名的
CGoods 对象，并调用构造函数；
…….
delete pc; //先析构，然后将内存空间返回给堆；
堆对象的生命期并不依赖于建立它的作用域，所以除非程
序结束，堆对象（无名对象）的生命期不会到期，并且需要显
式地用 delete语句析构堆对象，上面的堆对象在执行 delete语
句时,C++自动调用其析构函数。
正因为构造函数可以有参数，所以 new后面类（ class）类
型也可以有参数。这些参数即构造函数的参数。但对创建数组，
则无参数，并只调用缺省的构造函数。见下例类说明：
7.1.2 堆对象与构造函数
class Cgoods {
private:
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];
//动态建立数组, 不能初始化, 调用 n次缺省构造函数
……
delete pc;
delete pc1;
delete []pc2;
}
这里再次强调,由堆区创建对象数组, 只能调用缺省的
构造函数, 不能调用其他任何构造函数 。
7.1.3 浅拷贝与深拷贝
缺省拷贝构造函数,可用一个类对象初始化另一个
类对象，称为缺省的 按成员拷贝,而不是对整个类对象
的 按位拷贝。 这称为 浅拷贝。
P 堆对象 堆对象P
P
图 7.1 浅拷贝
拷贝前
拷贝后
7.1.3 浅拷贝与深拷贝
如果类中有一个数据成员为指针，
该类的一个对象 obj1中的这个指针 p，
指向了动态分配的一个堆对象，（参见
上图拷贝前），如果用 obj1按成员拷贝
了一个对象 obj2，这时 obj2.p也指向同
一个堆对象。当析构时，如用缺省的析
构函数，则动态分配的堆对象不能回收。
因为该堆对象还在被 obj1使用，如果在
析构函数中有,delete p;”语句，则如
果先析构函数 obj1时，堆对象已经释放，
以后再析构 obj2时出现了二次释放的问
题。这时就要重新定义拷贝的构造函数，
给每个对象独立分配一个堆对象，称 深
拷贝。 这时 先拷贝对象主体，再为 obj2
分配一个堆对象，最后用 obj1的堆对象
拷贝 obj2的堆对象 。
堆对
象P
P 堆对象
图 7.2 深拷贝
7.1.3 浅拷贝与深拷贝
定义拷贝（ copy structor）和拷贝赋值操作符（ copy
Asignment Operator）实现深拷贝。
学生类定义：
class student {
private:
char *pName; //指针成员
public:
student() {
cout << "Constructor";
pName = NULL;
cout <<,缺省” << endl;
}
student(char *pname);
student(student &s); //拷贝构造函数
~student();
student & operator=(student &s); //拷贝赋值操作符
};
7.1.3 浅拷贝与深拷贝
带参数 构造函数：
student::student(char *pname)
{ cout << "Constructor";
if(pName = new char[strlen(pname)+1])
strcpy(pName,pname);
cout << pName << endl;
}
拷贝构造函数：
student::student(student &s)
{ cout << "Copy Constructor";
if(s.pName) {
if(pName = new char[strlen(s.pName)+1])
strcpy(pName,s.pName);
} //加一不可少，否则串结束符冲了其他信息，析构会出错！
else pName=NULL;
cout << pName << endl;
}
7.1.3 浅拷贝与深拷贝
析构函数：
student::~student()
{ cout << "Destructor,<< pName << endl;
if(! pName) delete []pName; //释放字符串
}
拷贝赋值操作符：
student &student::operator=(student &s)
{ cout << "Copy Assign operator";
delete []pName; //如原来已分配，应先撤销，再重分配
if(s.pName) {
if(pName = new char[strlen(s.pName)+1])
strcpy(pName,s.pName);
}
else pName=NULL;
cout << pName << endl;
return *this;
}
7.2 链表与链表的基本操作
在数据结构的描述中,线性表 是最简单，最常
用的一种数据结构。线性表的逻辑结构是 n个数据
元素的有限序列（ a1,a2,…,an ）。而线性表的 物
理结构,我们已经学习过顺序表，也就是 数组 ；
另一种线性表的物理结构 ——链表 。
动态内存分配 的一个重要应用，就是如何用它
来表达一类复杂的数据结构 -链表，那什么是链表
呢？链表是一种常用的数据结构，它不同于数组，
数组的长度必须事先确定的，并且它的数据是顺序
存放的。但有时候在处理数据时，由于事先不知道
所处理的数据个数，所以往往将数组定的足够大来
处理所有情况，这很容易造成内存空间浪费，而链
表是一种动态进行存储分配的数据结构，每个结点
也不需要顺序存放，它们是通过指针相互连接而成
的表，所以叫链表。
7.2.1 单链表基本算法
单链表 （ Singly Linked list） 也称线性链表 。 每个数据元
素占用一个节点 （ Node） 。 一个节点包含两部分域, 一部分域
存放数据对象的数据成员, 其内容由应用问题决定, 另一部分存
放指向该链表中下一个节点的指针 next。 节点定义如下：
struct node {
Datatype1 info1;
Datatype2 info2;
Datatype2 info2;
……
struct node *next;
}
在 C/C++中允许结构 （ 或对象 ） 成员是 结构自身的指针类
型, 通过指针引用自身这种类型的结构 。 但结构成员决不能是结
构自身类型, 即结构不能自己定义自己, 这会导致一个无穷递归
的定义 。
struct student {
int num;
float score;
strcut student *next;
} // 学生节点定义
7.2.1 单链表基本算法
单向链表特点：
1、每个结点都是个结构，里面包含着结构指针
2、链表都有个头指针，不然无法访问链表
3、每个结点里的指针都是指向下一个结点的地址
4、链表的最后结点结构指针应为空，表示该链表已结束
单链表的第一个结点的地址可通过链表的表头指针 head找到，
head在使用中必须妥善保存，千万不可丢失，否则链表整个丢失，
内存也发生泄漏。
链表操作,建立链表, 显示链表内容,在链表 插入结点, 删
除链表结点,等操作。
head num
score
next
num
score
next
num
score
NULL
...
节点
7.2.1 单链表基本算法
建立链表：
下面以建立学生情况的单向链表为例进行说明，假设从键盘
输入时，如果学号为 0表示，链表建立结束。我先讲一下算法：
1、先设置三个指向 student的结构变量指针：
struct student *head,*p1,*p2;
2、使用 new 函数动态申请一个结点的空间，并使 p1和 p2 都
指向新结点 p1 = p2 = new struct student;
3、有了第一结点后，从键盘上输入数据给新结点成员
cin >> p1->num >> p1->score;
然后将 p1赋给 head，让 head也指向第一个结点
4、接着再申请第二个结点，并使 p1指向新结点，再从键盘输
入数据，通过下述方法将新结点链入链表，即使第一个结点
p2中的 next指向新结点 p2->next = p1; 然后让 p2指向 p1，
即 p2=p1
5、然后再申请第三个 …….,重复 4的步骤，直到最后输入的学
号为 0为止
6、最后将 p2->next = NULL
7.2.1 单链表基本算法
head
int n = 0; // 7-2-1.cpp
struct student *create(void)
{ struct student *head,*p1,*p2;
p1 = p2 = new struct student;
cin >> p1->num >> p1->score;
head = NULL;
while(p1->num != 0) {
n ++;
if(n == 1) head = p1;
else p2->next = p1;
p2 = p1;
p1 = new struct student;
cin >> p1->num >> p1->score;
}
p2->next = NULL;
return(head);
}
7.2.1 单链表基本算法
那么我们在主函数中可以：
main()
{ struct student *head;
head = create();
print(head);
}
输出链表：
将链表中各结点数据进行遍历输出，它的程序如下：
void print(struct student *head)
{ struct student *p = head;
if(head != NULL)
do {
cout << p->num <<,,,<< p->score << endl;
p = p->next;
} while(p!=NULL);
}
7.2.1 单链表基本算法
删除结点：
就是删除已知链表中的结点, 譬如要删除某个学号的结点,
首先通过寻找该学号所在的结点, 先设置两个结构指针 p1和
p2,并使 p1指向第一个结点, 并检查该结点是否要删除的结
点, 如果不是, 则将 p1指针赋给 p2,并将 p1指针指向下一个
结点, 如果指针 p1所指向的结点还不是要删除的结点, 则再将
p1赋给 p2,p1再下移一个结点, 直到链表搜索完毕 。 找到后
要分两种情况进行分析：
1,如果要删除的是头结点, 那么只需将 p1->next赋给头指针
head,就是说让头指针指向原链表中的第二个结点, 这时相当
于第一个结点被, 删除, 或架空不起作用, 然后用 delete p1
函数将第一结点空间释放 。
2,如果要删除的 p1结点不是头结点, 那么则将 p1->next赋
给 p2->next,这样就跳过 p1结点, 相当于 P1被删除 。
7.2.1 单链表基本算法
struct student *delete(struct student *head,int num)
{ struct student *p1,*p2;
if(head == NULL) {
cout <<,This list is NULL” << endl;
return(NULL);
}
p1 = head;
while(p1->num != num && p1->next != NULL){
p2 = p1;
p1 = p1->next;
}
if(p1->num == num) {
if(p1 == head) head = p1->next; // 删除首结点
else p2->next = p1->next; // 删除中间或尾结点
cout <<,delete:” << num << endl;
delete p1;
} else cout << num <<, not been found !” << endl;
return(head);
}
7.2.1 单链表基本算法
插入节点：
就是将一个已知的 p0结点插入到一个已存在的链表中, 假
设已有链表按照从小到大的学号来排列 。 当然, 在插入操作中
要根据学号找到合适的插入位置 。 算法如下：
要找到插入的位置：设置两个结构指针 p1和 p2,并使 p1指
向第一个结点, 将 p0->num与 p1->num进行比较, 如果前者
大于后者, 则将指针 p2指向 p1所在的结点, 然后将 p1指针后移
到下一个, 然后继续进行比较, 并移动 p1和 p2指针, 直到 p0-
>num,= p1->num为止 。 那么就是说已经找到要插入的位置,
即将 p0插入到 p1指针所指向的结点之前, p2之后 。
将 p0结点插入到指定位置, 有三种情况：
1,当插入的位置在首结点之前, 则将 p0赋给 head,再将 p1赋
给 p0->next ；
2,当插入的位置在尾结点之后, 则将 p0赋给 p1->next,再将
NULL赋给 p0->next ；
3,当插入位置位于 p2和 p1之间, 则将 p0赋给 p2->next,再
将 p1赋给 p0->next；
7.2.1 单链表基本算法
struct student insert(struct student *head,struct
student *stud)
{ struct student *p0,*p1,*p2;
p1 = head; p0 = stud;
if(head == NULL) {
head = p0; p0->next = NULL; return(head);
}
while((p0->num > p1->num) &&
(p1->next != NULL)) {
p2 = p1; p1 = p1->next;
}
if(p0->num <= p1->num) {
if(head == p1) head = p0; // 插在头部 //
else p2->next = p0; // 插在 p2和 p1之间 //
p0->next = p1;
} else { // 插到最后 //
p1->next = p0; p0->next = NULL; }
return(head);
}
7.2.2 单链表操作提问
已知两条同类型的链表的头指针分别是 heada
和 headb,请编程将这两条独立的链表串联起来,
即 headb接在 heada的末尾, 形成的合并后的新链
表头指针为 heada。
heada
……
headb
……
7.2.2 单链表操作提问
Struct student * combineList(heada,headb)
Struct student *heada,*headb;
{ Struct student *p;
p = heada;
if(p != NULL) {
while(p->next != NULL) p = p->next;
p->next = headb;
else heada = headb;
return heada;
}
7.3 栈与应用
栈定义为只允许在表的一端进行插入和删除的线性表 。它占用一段
连续的的内存空间，有两个端点,允许进行插入和删除的一端叫做 栈顶
(top)，而另一端固定的叫 栈底 (bottom)。 栈中没有任何元素时，称为空
栈，操作只能在栈顶进行。参见下图，设给定栈 s=(a0,a1,……, an-
1)，称 a0为栈底,an-1为栈顶。进栈时最先进栈的 a0在最下面,an-1在
最上面，后来居上。而出栈时顺序相反，最后进栈的 an-1最先出栈，而
最先进栈的 a0最后出栈。所以栈又称作 后进先出（ LIFO,Last In First
Out）的线性表 。
a0
an-2
……
a1
an-1
bottom
进栈
top
sp
出栈
7.3.1 栈的概念
栈的操作有两种,push（压入或进栈） 和 pop（弹出或出
栈） 。在栈刚开始建立时,栈顶指针 sp是指向栈底，如下图 a，
如果向栈内 push一个数据 8，则系统把 8写入 sp所指向的内存，
然后 sp++，如下图 b所示。如再压入数据 5，则系统把 5写入
sp所指向的内存，然后 sp++，如下图 c所示，总之，栈顶 sp所
指向的内存是存放最新需要压入的数据。由栈内弹出数据时，
先执行 sp=sp-1，然后返回 sp所指向的数据，就是 5，如下图 d
所示，如果现在还有一个数据 20需要压入的，那么就将 5数据
覆盖，结果如下图 e，因为数据 5已经被弹出，所以覆盖是没有
问题的。
sp
图 a
8
sp
图 b
5
8
sp
图 c
5
8
sp
图 d
20
8
sp
图 e
7.3.1 栈的建立
栈类的数据定义：
#define STACKSIZE 10
Class Stack {
private:
long buffer[STACKSIZE];
long *sp;
public:
Stack() { sp = buffer; }
~Stack() { };
void push(long data) {
if(sp >= buffer+STACKSIZE)
cerr <<,Stack overflow !” << endl;
else {
*sp ++ = data;
cout << data <<, is pushed !” << endl;
}
}
7.3.1 栈的建立
long pop() {
if(sp <= buffer) {
cerr <<,Stack is Empty!” << endl;
return 0;
}
else return *--sp;
}
};
main()
{ Stack a;
a.push(351); a.push(7075461); a.push(3225);
cout << endl;
cout << a.pop() <<, is poped” << endl;
cout << a.pop() <<, is poped” << endl;
cout << a.pop() <<, is poped” << endl;
cout << a.pop() <<, is poped” << endl;
}
N
c
b
a
＊
＋
O
＊
＋ a
t1
d
e
N
a
t1
d
e
＋＋
／
－
O
／
－ －
＋
O
－
＋
N
t1
a
t2
t1
a
t2
t3
a
N
t3
a
N
＋
O
＋
O
b*c->t1 d/e->t2 t
1-t2->t3 a+t3->t4
N：数栈 O：运算符
(a) (b) (c) (d) (e)
表达式运算
栈可用于 表达式的计算 。现考虑最简单的 +,-,*,/四个运算符和结束
符＝组成的算术表达式，只有 两个优先级,先 */，后 +-。设有,a+b*c-d/e=
为实现运算符的优先级，采用两个栈：一个 数栈,一个 运算符栈 。数
栈暂存操作数，运算符栈暂存运算符。 从左向右扫描算术表达式,遇到 操作
数, 压入数栈 ；遇到 运算符,则 与运算符栈栈顶的运算符比较优先级,若新
的运算符优先级高，或运算符栈空，则压栈。否则将栈顶运算符出栈，与数
字栈出栈的两个数据进行运算，结果压入数栈，再将新运算符压栈。继续扫
描，直到遇到＝号，扫描结束。栈中数据继续按前面规则出栈。
7.3.2 栈的应用
7.3.2 栈的应用
模拟简单计算器, 该计算器只认 + - * / 四个运算符, 输入为整数 。 表达式
结束符使用＝号, 清空栈用 ‘ c’字符 。 使用 ‘ z’字符表示结束 。
简易计算器类定义,// 7-3-2.cpp
class Calculator {
private:
Stack Nstack; // 处理操作数
Stack Ostack; // 处理运算符
public:
Calculator(void) { };
void Cal(void); //计算器运算程序
void GetTwoNum(int &Num1,int &Num2);
void Compute(char Opr);
void Clear(void);
};
void Calculator::Clear() {
Nstack.Empty(); Ostack.Empty();
}
void Calculator::GetTwoNum(int &Num1,int &Num2) {
Num1=Nstack.Pop(); Num2=Nstack.Pop();
}
7.3.2 栈的应用
void Calculator::Compute(char Opr) {
int Num1,Num2;
if(Opr != ‘=‘ ) GetTwoNum(Num1,Num2);
switch(Opr) {
case '+',Nstack.Push(Num2 + Num1); break; //结果压栈
case '-',Nstack.Push(Num2 - Num1); break;
case '*',Nstack.Push(Num2 * Num1); break;
case '/',Nstack.Push(Num2 / Num1); break;
case '=',cout << Nstack.Pop() << endl; //输出结果
}
}
最重要的计算函数：
void Calculator::Cal() {
bool b1=true,b2=true;
char ch1,ch2,str[50];
int k = -1;
while(b2) {
cin >> ch1;
if(ch1 >= '0‘ && ch1 <= '9') {
k++;
str[k] = ch1;
} //数字字符添入串中
7.3.2 栈的应用
else {
if(k>=0) {
str[k+1] = '\0'; //数字串生成
Nstack.Push(atoi(str)); //数字串转换为整数后压栈
k=-1;
}
switch(ch1) {
case 'c',Clear();break;
case '+',case '-':
while(! Ostack.IsEmpty()) {
ch2=Ostack.Pop(); //不会有比 '＋ ' '－ '优先级低的
Compute(ch2);
}
Ostack.Push(ch1); break;
case '*':case '/':
while(!Ostack.IsEmpty() && b1) {
ch2=Ostack.Pop(); //把栈顶运算符弹出
if(ch2 == '*‘ || ch2 == '/') //比较优先级
Compute(ch2); //新的优先级并不高
else { //新的优先级高
Ostack.Push(ch2); //先把原栈中的
b1=false; //运算符压回去
}
}
Ostack.Push(ch1); //再把新的运算符压栈
b1=true; break; //将 b1复原
case '=':
while(!Ostack.IsEmpty()) {
ch2=Ostack.Pop();
Compute(ch2);
}
Compute(ch1); break;
}
if(ch1 == 'z') b2=false;
}
}
7.3.2 栈与应用
