c++第六章习题解答

第六章模板与数据结构习题一、基本概念与基础知识自测题61填充题611模板是为了实现代码的（1），它把数据类型改为一个（2），称为（3）程序设计。模板包括（4）和（5）。答案（1）重用（2）设计参数（3）参数化PARAMETERIZE（4）函数模板FUNCTIONTEMPLATE（5）类模板CLASSTEMPLATE612调用函数模板时，可以显式指定模板参数类型，也可以隐式进行，称为（1），这是根据（2）来决定的。答案（1）模板实参推演TEMPLATEARGUMENTDEDUCTION（2）一组实际类型或（和）值613顺序查找可以用于（1）线性表，而对半查找可以用于（2）线性表。答案（1）无序的（所有）（2）有序的614最常见的排序方式有（1）、（2）和（3）。如果现有一个已排好序的线性表，在表尾添加了一个元素，采用（4）排序法使它重新成为有序的所需工作量最小。答案（1）选择（2）插入（3）交换（4）交换（可利用原来的有序性）615给出以下指针的说明方式指向一个4元素整型数组的指针为（1）；指向一个返回整型数，参数为两个整型数的函数的指针（2）；指向一个数组的指针，而该数组元素都是指向一个返回整型指针的无参函数的指针（3）。答案（1）INTP4（2）INTPINT,INT（3）以指向6元素数组为例INTP662简答题621需要编写一个对多维数组通用的算法（即各维的大小未定），怎样才能把实参多维数组的信息全部传递到函数中去答最佳方法是用函数模板，多维数组用模板类型参数传递，各维的大小作为参数传递。也可以用一维数组加各维的大小都作为参数传递。622什么叫函数模板什么叫模板函数什么叫类模板什么叫模板类答不受数据类型限制的通用型的函数使代码的可重用性大大提高。把数据类型改为一个设计参数是一个可行的方案。这种程序设计类型称为参数化PARAMETERIZE程序设计。这样的软件模块由模板TEMPLATE构造。包括函数模板和类模板。函数模板定义如下TEMPLATE返回类型函数名形式参数表/函数体模板参数主要是模板类型参数。模板类型参数代表一种潜在的内置或用户定义的类型，由关键字TYPENAME或CLASS后加一个标识符构成。函数模板可以用来创建一个通用功能的函数，以支持多种不同形参，简化重载函数的设计。由调用函数模板FUNCTRONTEMPLATE而生成的函数，称为模板函数TEMPLATEFUNCTION。类模板定义如下TEMPLATECLASS类名/类声明体模板参数有两种模板类型参数和模板非类型参数。模板类型参数TEMPLATETYPEPARAMETER，它代表一种类型，由关键字TYPENAME或CLASS后加一个标识符。模板非类型参数由一个普通的参数声明构成。模板非类型参数表示该参数名代表了一个潜在的常量。如数组类模板，可以有一个数组长度的非类型参数。为通用的类模板定义中的模板类型参数指定了具体类型而生成的类称为模板类。623什么叫线性表其基本操作包括哪些其中插入一个元素的关键在哪儿答线性表是数据结构中的概念每两个相邻元素之间都有直接前驱和直接后继的关系。这里除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱；除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素无后继。这样的特性称为线性关系。基本操作包括计算表长度，寻找变量或对象X（其类型与表元素相同）在表中的位置（下标值），判断X是否在表中，删除X，将X插入列表中第I个位置，寻找X的后继，寻找X的前驱，判断表是否空，判断表是否满，取第I个元素的值等。当需要在顺序表的指定位置I插入一个数据X时，必须为它腾出这个位置，把从该位置开始向后的所有元素数据，后移一个位置，最后才插入。关键是后移时从最后一个元素开始。否则先移的数据会冲掉未移的数据。624采用索引查找有哪些优点它需要被查找数据有序吗答索引，就象一本书的目录，找到标题，再看一下页号，立即可以翻到。索引查找不要求被查找数据有序，只要求索引有序。625简单叙述阅读理解复杂指针的方法。设NODE为类，下面两个标识符FA和PA分别代表什么NODEFAINTNODEPA答理解和构造对象说明的方法是先撇开标识符，按从右到左的顺序逐个解释每个说明符，如果有括号则改变解释的先后，先解释括号内再解释括号外。FA是有一个整型参数的函数，其返回值是指针，该指针是指向无参函数的指针，而该无参函数的返回值是指向NODE类的指针。PA是指向数组的指针，该数组的元素均为函数指针，所指向的函数无参、返回值是指向NODE类的指针。二、编程与综合练习题63使用自定义字符串类，编写求数组元素中最大值的函数模板。解函数模板有三种应用方式1类模板的成员函数，在模板类型参数中重载函数和运算符，直接访问私有数据成员，实现通用算法。这是标准的面向对象的方法。2函数模板处理模板类，以类模版为参数，用模板类型参数中重载的函数或运算符，实现通用算法。但调用类模板的接口函数间接访问私有数据成员，也是常见的。3函数模板处理普通数据，往往要用函数作为参数，实现通用算法。这是面向过程的方法。解使用独立的函数模板，相对简单。INCLUDEUSINGNAMESPACESTDCONSTINTN256CLASSMYSTRING/为简单只保留用到的函数CHARSTRN/存放字符串的数组容器INTMAXSIZE/最大可用元素数，可防止数组出界，提高健壮性INTLAST/已用元素数PUBLICMYSTRINGLAST1MAXSIZENSTR00COUTGROAPMAXGROAPR_ARRAY,INTSIZE/这里是一个独立的函数模板GROAPMAX_VALR_ARRAY0FORINTI1IMS,6SHOWRETURN064将自定义字符串类用于对半查找的函数模板。解1为简化，使用独立的函数模板INCLUDEUSINGNAMESPACESTDCONSTINTN256/CLASSMYSTRING定义略TEMPLATEINTBINARYSEARCHTARRAY,T/SIZE当前有序表元素数量WHILELOWUSINGNAMESPACESTDCONSTINTN256/CLASSMYSTRING定义略TEMPLATECLASSORDEREDLISTINTMAXSIZEINTLASTTSLISTSIZEPUBLICINTGETLASTRETURNLASTTGETSLISTINTKRETURNSLISTKVOIDPUTSLISTTT,INTKSLISTKTORDEREDLISTLAST1MAXSIZESIZEBOOLINSERTTVOIDPRINTINTBINARYSEARCHT/无关成员函数省略,缺省的等不必定义/再次指出分号不可少TEMPLATEBOOLORDEREDLISTINSERTTELSELASTFORINTJLASTJIJSLISTJSLISTJ1SLISTIELEMRETURNTRUETEMPLATEVOIDORDEREDLISTPRINTINTIFORI0IINTORDEREDLISTBINARYSEARCHTX/成员函数模板INTHIGHLAST,LOW0,MID/SIZE当前有序表元素数量WHILELOWORDLISTMYSTRINGNHCHARSPH10“东南大学“,“复旦大学“,“交通大学“,“南京大学“,“清华大学“,“天津大学“,“同济大学“,“浙江大学“FORI0IINCLUDEUSINGNAMESPACESTDTEMPLATECLASSORDEREDLISTINTMAXSIZEINTLASTTSLISTSIZEPUBLICORDEREDLISTLAST1MAXSIZESIZEVOIDBUBBLESORTBOOLINSERTTVOIDPRINT/无关成员函数省略,缺省的等不必定义/再次指出分号不可少/INSERTTINTI,JTTEMPFORILASTI0I/从上往下冒泡，对比例68有何不同NOSWAPTRUE/未交换标志为真FORJ0JORDLISTSTRINGNHSTRINGSPH“南京大学“,“东南大学“,“交通大学“,“清华大学“,“天津大学“,“复旦大学“,“浙江大学“,“同济大学“FORI0IINCLUDEUSINGNAMESPACESTDTEMPLATECLASSORDEREDLISTINTMAXSIZEINTLASTTSLISTSIZEPUBLICORDEREDLISTLAST1MAXSIZESIZEVOIDBUBBLESORTBOOLINSERTTVOIDPRINTVOIDMERGEORDEREDLIST/无关成员函数省略,缺省的等不必定义/再次指出分号不可少/INSERTTINTI,JTTEMPFORILASTI0I/从上往下冒泡，对比例68有何不同NOSWAPTRUE/未交换标志为真FORJ0JVOIDORDEREDLISTMERGEORDEREDLISTWHILEIORDLIST,ORDLIST1,ORDLIST2STRINGNH,MHCHARSP1H10“南京大学“,“东南大学“,“交通大学“,“清华大学“,“天津大学“,“复旦大学“,“浙江大学“,“同济大学“FORI0IINCLUDEUSINGNAMESPACESTDTEMPLATECLASSORDEREDLISTINTMAXSIZEINTLASTTSLISTSIZEVOIDSHELLINSERTCONSTINTPUBLICINTGETLASTRETURNLASTTGETSLISTINTKRETURNSLISTKVOIDPUTSLISTTT,INTKSLISTKTORDEREDLISTLAST1MAXSIZESIZEBOOLINSERTTVOIDPRINTVOIDSHELLSORT/无关成员函数省略,缺省的等不必定义/再次指出分号不可少TEMPLATEBOOLORDEREDLISTINSERTTELSEFORINTJLASTJIJSLISTJSLISTJ1SLISTIELEMLASTRETURNTRUETEMPLATEVOIDORDEREDLISTPRINTINTIFORI0IVOIDORDEREDLISTSHELLSORT/成员函数INTGAPLAST1/2WHILEGAPSHELLINSERTGAP/一趟排序GAP/2TEMPLATEVOIDORDEREDLISTSHELLINSERTCONSTINTGAPINTI,JTTEMP/注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是GAP号，/插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。FORIGAPIGAPSTRINGNHCHARSPH10“南京大学“,“东南大学“,“交通大学“,“清华大学“,“天津大学“,“复旦大学“,“浙江大学“,“同济大学“FORI0IINCLUDEUSINGNAMESPACESTDTEMPLATECLASSORDEREDLISTINTMAXSIZEINTLASTTSLISTSIZEPUBLICINTGETLASTRETURNLASTTGETSLISTINTKRETURNSLISTKVOIDPUTSLISTTT,INTKSLISTKTORDEREDLISTLAST1MAXSIZESIZEBOOLINSERTTVOIDPRINT/无关成员函数省略,缺省的等不必定义/再次指出分号不可少TEMPLATEBOOLORDEREDLISTINSERTTELSEFORINTJLASTJIJSLISTJSLISTJ1SLISTIELEMLASTRETURNTRUETEMPLATEVOIDORDEREDLISTPRINTINTIFORI0IVOIDSHELLSORTORDEREDLISTWHILEGAPSHELLINSERTLIST,GAP/一趟排序GAP/2/INTSIZE必须保留TEMPLATEVOIDSHELLINSERTORDEREDLISTTTEMP/注意每一趟排序包含若干子序列,其中第一个子序