7C++第七章习题解答.docx

7C++第七章习题解答.docx

《7C++第七章习题解答.docx》由会员分享，可在线阅读，更多相关《7C++第七章习题解答.docx（54页珍藏版）》请在冰点文库上搜索。

7C++第七章习题解答

第七章动态内存分配习题

一、基本概念与基础知识自测题

7.1填空题

7.1.1C/C++定义了4个内存区间：

（1）、

（2）、（3）和（4）。

答案：

（1）代码区，存放程序代码；

（2）全局变量与静态变量区，存放全局变量或对象（包括静态）；

（3）局部变量区即栈（stack）区，存放局部变量；

（4）自由存储区（freestore），即动态存储区或堆（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所指向的无名对象占用的内存空间，也就是撤销了该无名对象，称动态内存释放（dynamicmemorydeallocation），但指针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什么是二叉树的遍历？

答：

所谓二叉树的遍历（binarytreetraversal），就是遵从某种次序，查巡二叉树的所有结点，每个结点都被访问一次，而且仅访问一次。

所谓“访问”指对结点施行某些操作，但不破坏它原来的数据结构。

二、编程与综合练习题

7.3给单链表类模板增加两个成员函数：

删除链表中所有数据域为指定值的结点和取出链表中第K个元素（从1开始计数）。

解：

这两个成员函数添在单链表类模板中（ep7_3.h）

本例数据域用了标准类string，也可以使用整数型。

//ep7_3.h

#include

usingnamespacestd;

//首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数作为成员函数

templateclassList;

templateclassNode{

Tinfo;//数据域

Node*link;//指针域

public:

Node（）;//生成头结点的构造函数

Node（constT&data）;//生成一般结点的构造函数

voidInsertAfter（Node*P）;//在当前结点后插入一个结点

Node*RemoveAfter（）;//删除当前结点的后继结点，返回该结点备用

T&Getinfo（）;//增加取数据域函数

friendclassList;

//以List为友元类，List可直接访问Node的私有函数，与结构一样方便，但更安全

};

templateNode:

:

Node（）{link=NULL;}

templateNode:

:

Node（constT&data）{

info=data;

link=NULL;

}

templatevoidNode:

:

InsertAfter（Node*p）{

p->link=link;

link=p;

}

templateNode*Node:

:

RemoveAfter（）{

Node*tempP=link;

if（link==NULL）tempP=NULL;//已在链尾,后面无结点

elselink=tempP->link;

returntempP;

}

templateT&Node:

:

Getinfo（）{returninfo;}//增加取数据域函数

//再定义链表类，选择常用操作：

包括建立有序链表、搜索遍历、插入、删除、取数据等

templateclassList{

Node*head,*tail;//链表头指针和尾指针

public:

List（）;//构造函数，生成头结点（空链表）

~List（）;//析构函数

voidMakeEmpty（）;//清空一个链表，只余表头结点

Node*Find（Tdata）;//搜索数据域与data相同的结点，返回该结点的地址

intLength（）;//计算单链表长度

voidPrintList（）;//打印链表的数据域

voidInsertFront（Node*p）;//可用来向前生成链表，在表头插入一个结点

voidInsertRear（Node*p）;//可用来向后生成链表，在表尾添加一个结点

voidInsertOrder（Node*p）;//按升序生成链表

Node*CreatNode（Tdata）;//创建一个结点（孤立结点）

Node*DeleteNode（Node*p）;//删除指定结点

Node*RemoveAll（T&）;//删除链表中所有数据域为指定值的结点

Node*GetNode（int）;//取出链表中第K个元素（从1开始计数）

};

templateList:

:

List（）{

head=tail=newNode（）;

}

templateList:

:

~List（）{

MakeEmpty（）;

deletehead;

}

templatevoidList:

:

MakeEmpty（）{

Node*tempP;

while（head->link!

=NULL）{

tempP=head->link;

head->link=tempP->link;//把头结点后的第一个节点从链中脱离

deletetempP;//删除（释放）脱离下来的结点

}

tail=head;//表头指针与表尾指针均指向表头结点，表示空链

}

templateNode*List:

:

Find（Tdata）{

Node*tempP=head->link;

while（tempP!

=NULL&&tempP->info!

=data）tempP=tempP->link;

returntempP;//搜索成功返回该结点地址，不成功返回NULL

}

templateintList:

:

Length（）{

Node*tempP=head->link;

intcount=0;

while（tempP!

=NULL）{

tempP=tempP->link;

count++;

}

returncount;

}

templatevoidList:

:

PrintList（）{

Node*tempP=head->link;

while（tempP!

=NULL）{

cout<info<<'\t';

tempP=tempP->link;

}

cout<

}

templatevoidList:

:

InsertFront（Node*p）{

p->link=head->link;

head->link=p;

if（tail==head）tail=p;

}

templatevoidList:

:

InsertRear（Node*p）{

p->link=tail->link;

tail->link=p;

tail=p;

}

templatevoidList:

:

InsertOrder（Node*p）{

Node*tempP=head->link,*tempQ=head;//tempQ指向tempP前面的一个节点

while（tempP!

=NULL）{

if（p->infoinfo）break;//找第一个比插入结点大的结点，由tempP指向

tempQ=tempP;

tempP=tempP->link;

}

tempQ->InsertAfter（p）;//插在tempP指向结点之前，tempQ之后

if（tail==tempQ）tail=tempQ->link;

}

templateNode*List:

:

CreatNode（Tdata）{//建立新节点

Node*tempP=newNode（data）;

returntempP;

}

templateNode*List:

:

DeleteNode（Node*p）{

Node*tempP=head;

while（tempP->link!

=NULL&&tempP->link!

=p）tempP=tempP->link;

if（tempP->link==tail）tail=tempP;

returntempP->RemoveAfter（）;//本函数所用方法可省一个工作指针

}

templateNode*List:

:

RemoveAll（T&p）{//利用已有的DeleteNode（）

Node*TempP=head->link,*TempR=NULL;

while（TempP!

=NULL）{//也可以利用尾指针

if（TempP->info==p）{

deleteTempR;//释放上次找到的结点，第1次时因TempR为NULL不会出错

TempR=DeleteNode（TempP）;

}

TempP=TempP->link;

}

returnTempR;//仅返回最后一次找到的结点

}

templateNode*List:

:

GetNode（inti）{//取出链表中第K个元素（从1计数）

Node*TempP=head->link;

intj=1;

if（i<0）returnNULL;

if（i==0）returnhead;

while（TempP!

=NULL&&j

TempP=TempP->link;

j++;

}

returnTempP;

}

//ep7_3.cpp

#include"ep7_3.h"

#include

usingnamespacestd;

intmain（）{

constinth=9;

inti;

Listlist1;

Node*n1,*P1;

stringm（"东南大学"）,sp[h]={"南京大学","东南大学","交通大学","清华大学",

"天津大学","东南大学","复旦大学","浙江大学","同济大学"};

cout<<"按原始数据次序输出：

"<

for（i=0;i

cout<

for（i=0;i

P1=list1.CreatNode（sp[i]）;

list1.InsertFront（P1）;//向前生成list1

}

cout<<"输出向前生成的链表：

"<

list1.PrintList（）;

n1=list1.RemoveAll（m）;

if（n1）{

cout<<"删除所有含“"<Getinfo（）<<"”的结点。

"<

deleten1;

}

elsecout<<"无要删除的结点！

"<

cout<<"输出删除所有指定结点后的链表：

"<

list1.PrintList（）;

cout<<"要求寻找第几个节点？

"<

cin>>i;

n1=list1.GetNode（i）;

if（n1!

=NULL）cout<Getinfo（）<

elsecout<<"链表出界！

"<

return0;

}

7.4为单链表类模板增加一个拷贝构造函数和拷贝赋值运算符（=）。

解：

为简单数据域使用整数型。

注意：

从7.3开始逐题完善单链表类模板，即前一题增加的成员函数在本题中全部保留。

拷贝构造函数先建立一个头结点，再以原链表的各结点的数据域来构造新链表的各对应结点。

如果看不懂拷贝构造函数请画一个空链表，逐步跟踪拷贝过程，只要跟踪几个结点就可以理解。

//ep7_4.h

#include

usingnamespacestd;

//首先看结点组织，采用结点类，凡与结点数据和指针操作有关函数作为成员函数

templateclassList;

//templateclassNode略

//再定义链表类，选择常用操作：

包括建立有序链表、搜索遍历、插入、删除、取数据等

templateclassList{

Node*head,*tail;//链表头指针和尾指针

public:

List（）;//构造函数，生成头结点（空链表）

List（List&）;//拷贝构造函数

~List（）;//析构函数

List&operator=（List&）;

voidMakeEmpty（）;//清空一个链表，只余表头结点

Node*Find（Tdata）;//搜索数据域与data相同的结点，返回该结点的地址

intLength（）;//计算单链表长度

voidPrintList（）;//打印链表的数据域

voidInsertFront（Node*p）;//可用来向前生成链表，在表头插入一个结点

voidInsertRear（Node*p）;//可用来向后生成链表，在表尾添加一个结点

voidInsertOrder（Node*p）;//按升序生成链表

Node*CreatNode（Tdata）;//创建一个结点（孤立结点）

Node*DeleteNode（Node*p）;//删除指定结点

Node*RemoveAll（T&）;//删除链表中所有数据域为指定值的结点/

Node*GetNode（int）;//取出链表中第K个元素（从1开始计数）

};

templateList:

:

List（List&ls）{//拷贝构造函数

Node*TempP=ls.head->link,*P1;

head=tail=newNode（）;

while（TempP!

=NULL）{

P1=newNode（TempP->info）;

P1->link=tail->link;//向后生成list1

tail->link=P1;

tail=P1;

TempP=TempP->link;

}

}

templateList&List:

:

operator=（List&ls）{

Node*TempP=ls.head->link,*P1;

MakeEmpty（）;

while（TempP!

=NULL）{

P1=newNode（TempP->info）;

P1->link=tail->link;//向后生成list1

tail->link=P1;

tail=P1;

TempP=TempP->link;

}

return*this;

}

//其它成员函数略

//ep7_4.cpp

#include"ep7_4.h"

intmain（）{

Node*P1;

Listlist1;

inta[16],i;

cout<<"请输入16个整数"<

for（i=0;i<16;i++）cin>>a[i];//随机输入16个整数

for（i=0;i<16;i++）{

P1=list1.CreatNode（a[i]）;

list1.InsertRear（P1）;//向前生成list1

}

cout<<"输出list1：

"<

list1.PrintList（）;

Listlist2（list1）,list3;

list3=list1;

list1.MakeEmpty（）;//清空原链表，看是否深拷贝

cout<<"如无输出list1已清空：

"<

list1.PrintList（）;

cout<<"输出list2：

"<

list2.PrintList（）;

cout<<"输出list3：

"<

list3.PrintList（）;

return0;

}

7.5试为单链表类模板设计一个将链表逆转的成员函数。

要求不删除原结点，也不另建一个链表来取代，而是通过改变指针域的链接方向来逆转链表。

解：

逆转链表函数在ep7_5.h的最后。

逆转链表的成员函数对空链表和单结点链表不处理。

对多结点链表，用尾指针指向第一个结点，找到该尾链表最后一个结点重新链到原头结点后面；再找到该尾链表