第七章动态内存分配习题一、基本概念与基础知识自测题7.1 填空题7.1.1 C/C++定义了4个内存区间：（1）、（2）、（3）和（4）。
答案：（1）代码区，存放程序代码；（2）全局变量与静态变量区，存放全局变量或对象（包括静态）；（3）局部变量区即栈（stack）区，存放局部变量；（4）自由存储区（free store），即动态存储区或堆（heap）区。
7.1.2 静态定义的变量和对象用标识符命名，称为（1）；而动态建立的称为（2），动态建立对象的初始化是通过（3）实现（4）。
答案：（1）命名对象（2）无名对象（3）初始化式(initializer)（4）显式初始化7.1.3 在用new运算符建立一个三维数组15*30*10时，使用了（1）个下标运算符，对应的用delete运算符注销这个三维数组时使用了（2）个下标运算符。
new返回的指针是指向（3）的指针。
答案：（1）3个（2）1个（3）30行10列的2位数组7.1.4 当动态分配失败，系统采用（1）来表示发生了异常。
如果new返回的指针丢失，则所分配的自由存储区空间无法收回，称为（2）。
这部分空间必须在（3）才能找回，这是因为无名对象的生命期（4）。
答案：（1）返回一个空指针（NULL）（2）内存泄漏（3）重新启动计算机后（4）并不依赖于建立它的作用域7.1.5 按语义的默认复制构造函数和默认复制赋值操作符实现的复制称为（1），假设类对象obj中有一个数据成员为指针，并为这个指针动态分配一个堆对象，如用obj1按成员语义拷贝了一个对象obj2，则obj2对应指针指向（2）。
答案：（1）浅拷贝（2）同一个堆对象7.1.6 单链表的结点包含两个域：（1）和（2）。
使用链表的最大的优点是（3），即使是动态数组也做不到这一点。
答案：（1）数据域（2）指针域（3）用多少空间，开多少空间7.1.7 进入单链表必须通过单链表的（1），如果它丢失则（2），内存也（3），在单链表中进行的查找只能是（4）。
答案：（1）头指针（2）链表整个丢失（3）会发生泄漏（4）顺序查找7.1.8 对链栈，链的生成必须是向（1）生成，最新压栈的元素（结点），放在（2）位置，弹出时从（3）删除结点。
对链队，采用向（4）生成，新入队的结点放在链的（5），出队操作在（6）位置。
答案：（1）向前（2）链表头的位置（3）链表头（4）向后（5）尾部（6）链表头7.1.9 在计算机中进行表达式的计算，为解决优先级和运算的结合性，必须使用（1）和（2）。
在中缀表达式中，每个双目运算符放在（3）。
答案：（1）数栈（2）运算符栈（3）它的两个运算符之间7.1.10 为了能重复利用一个队空间，要求把队说明成一个逻辑上的（1）。
答案：（1）循环队列7.1.11 二叉树的特点是：（1）和（2）。
答案：（1）每个结点最多有两个孩子（2）子树有左右之分7.1.12 二叉树的遍历是按（1）分类，所谓中序遍历是（2）。
答案：（1）访问子树根节点次序（2）先遍历该子树根结点的左子树回来后，接着再访问根结点，最后遍历右子树7.1.13 二叉排序树又称（1）或（2）。
其左子树上的所有结点均小于根结点的数据值，而右子树上的所有结点均大于根结点的数据值时，采用（3）就可以得到一个（4）。
答案：（1）二叉搜索树（2）树表（3）中序遍历（4）升序序列7.2简答题7.2.1new运算符为一个变量或对象分配存储空间和为一个数组分配存储空间，使用方法上有什么不同？对应的delete运算符使用有什么不同？答：为一个变量或对象分配存储空间其使用的格式如下：指针变量名=new 类型名(初始化式)；对于数组进行动态分配和撤销的格式为：指针变量名=new 类型名[下标表达式];后者多一个[下标表达式]，同时不能进行初始化。
对应的delete运算符使用分别为：delete 指针名;delete [ ] 指向该数组的指针变量名;后者多一个方括号，如果delete语句中少了方括号，因编译器认为该指针是指向数组第一个元素的指针，会产生回收不彻底的问题（只回收了第一个元素所占空间），加了方括号后就转化为指向数组的指针，回收整个数组。
delete [ ]的方括号中不需要填数组元素数，系统自知。
即使写了，编译器也忽略。
7.2.2用delete删除p所指向的无名对象时，p指针也同时被删除了，对不对？为什么？答：不对。
注意这时释放了p所指向的无名对象占用的内存空间，也就是撤销了该无名对象，称动态内存释放（dynamic memory deallocation），但指针p本身并没有撤销，它仍然存在，该指针所占内存空间并未释放。
7.2.3为什么动态建立类对象数组时，类的定义一定要有缺省的构造函数？答：new后面类（class）类型也可以有参数。
这些参数即构造函数的参数。
但对创建数组，没有参数，只能调用缺省的构造函数。
7.2.4要实现深拷贝，自定义的拷贝构造函数应该怎样设计？答：如果类中有一个数据成员为指针，该类的一个对象中的这个指针p，指向了动态分配的一个堆对象。
深拷贝时要给新建立的对象独立分配一个堆对象。
这时拷贝的构造函数应该设计为：先拷贝对象主体，再为新建对象的指针分配一个堆对象，最后用原对象的堆对象拷贝新对象的堆对象。
即分三步完成。
7.2.5在单链表模板中为什么要把List类说明成Node的友元类？答：为了直接访问结点的私有成员数据，以简化程序。
7.2.6双向链表与单向链表相比，操作上有什么优点?答：双向链表可以很方便地找到表结点的前驱和后继。
单链表只能找后继。
如要找前驱，必须从表头开始搜索，并一般要用两个工作指针。
7.2.7对比顺序栈与链栈各自的长处和短处。
答：顺序栈可以随机访问其中的元素，而链栈只能顺序访问。
顺序栈必须先开一定大小内存空间，执行起来简单，速度快，但可能溢出。
链栈内存空间随用随开，不会溢出，但执行复杂（不断地动态分配），速度慢。
7.2.8写出二叉树的定义。
答：二叉树是结点的一个有限集合，该集合或为空，或是由一个根结点及两棵分别称为左子树和右子树的（注意有左右之分）互不相交的二叉树组成，其中左右子树分别可以为空子树或均为空树。
7.2.9什么是二叉树的遍历？答：所谓二叉树的遍历（binary tree traversal），就是遵从某种次序，查巡二叉树的所有结点，每个结点都被访问一次，而且仅访问一次。
所谓“访问”指对结点施行某些操作，但不破坏它原来的数据结构。
二、编程与综合练习题7.3给单链表类模板增加两个成员函数：删除链表中所有数据域为指定值的结点和取出链表中第K个元素（从1开始计数）。
解：这两个成员函数添在单链表类模板中（ep7_3.h）本例数据域用了标准类string，也可以使用整数型。
//ep7_3.h#include<iostream>using namespace std;//首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数作为成员函数template<typename T>class List;template<typename T>class Node{T info; //数据域Node<T> *link; //指针域public:Node(); //生成头结点的构造函数Node(const T & data);//生成一般结点的构造函数void InsertAfter(Node<T>* P); //在当前结点后插入一个结点Node<T>* RemoveAfter(); //删除当前结点的后继结点，返回该结点备用T & Getinfo();//增加取数据域函数friend class List<T>;//以List为友元类，List可直接访问Node的私有函数，与结构一样方便，但更安全};template <typename T> Node<T>::Node(){link=NULL;}template <typename T> Node<T>::Node(const T & data){info=data;link=NULL;}template<typename T>void Node<T>::InsertAfter(Node<T>* p){p->link=link;link=p;}template<typename T>Node<T>* Node<T>::RemoveAfter(){Node<T>* tempP=link;if(link==NULL) tempP=NULL; //已在链尾,后面无结点else link=tempP->link;return tempP;}template<typename T> T & Node<T>::Getinfo(){return info;}//增加取数据域函数//再定义链表类，选择常用操作：包括建立有序链表、搜索遍历、插入、删除、取数据等template<typename T>class List{Node<T> *head,*tail;//链表头指针和尾指针public:List(); //构造函数，生成头结点(空链表)~List(); //析构函数void MakeEmpty(); //清空一个链表，只余表头结点Node<T>* Find(T data); //搜索数据域与data相同的结点，返回该结点的地址int Length(); //计算单链表长度void PrintList(); //打印链表的数据域void InsertFront(Node<T>* p); //可用来向前生成链表，在表头插入一个结点void InsertRear(Node<T>* p); //可用来向后生成链表，在表尾添加一个结点void InsertOrder(Node<T> *p); //按升序生成链表Node<T>*CreatNode(T data); //创建一个结点(孤立结点)Node<T>*DeleteNode(Node<T>* p); //删除指定结点Node<T>*RemoveAll(T &); //删除链表中所有数据域为指定值的结点Node<T>*GetNode(int); //取出链表中第K个元素（从1开始计数）};template<typename T>List<T>::List(){head=tail=new Node<T>();}template<typename T>List<T>::~List(){MakeEmpty();delete head;}template<typename T>void List<T>::MakeEmpty(){Node<T> *tempP;while(head->link!=NULL){tempP=head->link;head->link=tempP->link; //把头结点后的第一个节点从链中脱离delete tempP; //删除(释放)脱离下来的结点}tail=head; //表头指针与表尾指针均指向表头结点，表示空链}template<typename T> Node<T>* List<T>::Find(T data){Node<T> *tempP=head->link;while(tempP!=NULL&&tempP->info!=data) tempP=tempP->link;return tempP; //搜索成功返回该结点地址，不成功返回NULL}template<typename T>int List<T>::Length(){Node<T>* tempP=head->link;int count=0;while(tempP!=NULL){tempP=tempP->link;count++;}return count;}template<typename T>void List<T>::PrintList(){Node<T>* tempP=head->link;while(tempP!=NULL){cout<<tempP->info<<'\t';tempP=tempP->link;}cout<<endl;}template<typename T>void List<T>::InsertFront(Node<T> *p){p->link=head->link;head->link=p;if(tail==head) tail=p;}template<typename T>void List<T>::InsertRear(Node<T> *p){p->link=tail->link;tail->link=p;tail=p;}template<typename T>void List<T>::InsertOrder(Node<T> *p){Node<T> *tempP=head->link,*tempQ=head; //tempQ指向tempP前面的一个节点while(tempP!=NULL){if(p->info<tempP->info)break; //找第一个比插入结点大的结点，由tempP指向tempQ=tempP;tempP=tempP->link;}tempQ->InsertAfter(p); //插在tempP指向结点之前，tempQ之后if(tail==tempQ) tail=tempQ->link;}template<typename T>Node<T>* List<T>::CreatNode(T data){//建立新节点Node<T>*tempP=new Node<T>(data);return tempP;}template<typename T>Node<T>* List<T>::DeleteNode(Node<T>* p){Node<T>* tempP=head;while(tempP->link!=NULL&&tempP->link!=p) tempP=tempP->link;if(tempP->link==tail) tail=tempP;return tempP->RemoveAfter(); //本函数所用方法可省一个工作指针} template<typename T> Node<T>* List<T>::RemoveAll(T &p){//利用已有的DeleteNode() bool b=false;Node<T>*TempP=head->link,*TempR=NULL;while(TempP!=NULL){ //也可以利用尾指针if(TempP->info==p){delete TempR; //释放上次找到的结点，第1次时因TempR为NULL不会出错TempR=DeleteNode(TempP);}TempP=TempP->link;}return TempR; //仅返回最后一次找到的结点}template<typename T> Node<T>* List<T>::GetNode(int i){//取出链表中第K个元素(从1计数)Node<T>*TempP=head->link;int j=1;if(i<0) return NULL;if(i==0) return head;while(TempP!=NULL&&j<i){TempP=TempP->link;j++;}return TempP;}//ep7_3.cpp#include"ep7_3.h"#include<string>using namespace std;int main(){const int h=9;int i;List<string> list1;Node<string> *n1,*P1;string m("东南大学"),sp[h]={"南京大学","东南大学","交通大学","清华大学", "天津大学","东南大学","复旦大学","浙江大学","同济大学"};cout<<"按原始数据次序输出："<<endl;for(i=0;i<h;i++) cout<<sp[i]<<'\t';cout<<endl;for(i=0;i<h;i++){P1=list1.CreatNode(sp[i]);list1.InsertFront(P1); //向前生成list1}cout<<"输出向前生成的链表："<<endl;list1.PrintList();n1=list1.RemoveAll(m);if(n1){cout<<"删除所有含“"<<n1->Getinfo()<<"”的结点。
