第六章 模板与数据结构习题
一、.基本概念与基础知识自测题
6.1 填充题
6.1.1 模板是为了实现代码的 （1） ，它把数据类型改为一个 （2） ，称为 （3） 程
序设计。模板包括 （4） 和 （5） 。
答案：（1）重用 （2）设计参数
（3）参数化(parameterize) （4）函数模板(function template) （5）类模板(class template)
6.1.2 调用函数模板时，可以显式指定模板参数类型，也可以隐式进行，称为 （1） ，这是
根据 （2） 来决定的。 答案：（1）模板实参推演(template argument deduction)
（2）一组实际类型或（和）值
6.1.3 顺序查找可以用于 （1） 线性表，而对半查找可以用于 （2） 线性表。 答案：（1）无序的（所有）
（2）有序的
6.1.4 最常见的排序方式有 （1） 、 （2） 和 （3） 。如果现有一个已排好序的线
性表，在表尾添加了一个元素，采用 （4） 排序法使它重新成为有序的所需工作量最小。
答案：（1）选择
（2）插入
（3）交换
（4）交换（可利用原来的有序性）
6.1.5 给出以下指针的说明方式：指向一个4元素整型数组的指针为 （1） ；指向一个返
回整型数，参数为两个整型数的函数的指针 （2） ；指向一个数组的指针，而该数组元素都是指向一个返回整型指针的无参函数 （3） 。
答案：（1）int(*p)[4]
（2）int(*p)(int,int)
（3）以指向6元素数组为例：int*(*)() (*p)[6]
6.2简答题
6.2.1 需要编写一个对多维数组通用的算法（即各维的大小未定），怎样才能把实参多维数
组的信息全部传递到函数中去？ 答：最佳方法是用函数模板，多维数组用模板类型参数传递，各维的大小作为参数传递。也可以用一维数组加各维的大小都作为参数传递。
6.2.2 什么叫函数模板？什么叫模板函数？什么叫类模板？什么叫模板类？
答：不受数据类型限制的通用型的函数使代码的可重用性大大提高。把数据类型改为
第六章 模板与数据结构题 2
一个设计参数是一个可行的方案。这种程序设计类型称为参数化(Parameterize) 程序设计。这样的软件模块由模板(Template) 构造。包括函数模板和类模板。
函数模板定义如下：
template<模板参数表> 返回类型 函数名(形式参数表){
……;//函数体 }
模板参数主要是模板类型参数。模板类型参数代表一种潜在的内置或用户定义的类型，由
关键字typename或class后加一个标识符构成。函数模板可以用来创建一个通用功能
的函数，以支持多种不同形参，简化重载函数的设计。
由调用函数模板(functron template) 而生成的函数，称为模板函数(template function)。 类模板定义如下：
template<模板参数表> class 类名{
……;//类声明体
};
模板参数有两种：模板类型参数和模板非类型参数。模板类型参数(template type parameter)，它代表一种类型，由关键字 typename或class后加一个标识符。模板非类型参数由一个普通的参数声明构成。模板非类型参数表示该参数名代表了一个潜在的常量。如数组类模板，可以有一个数组长度的非类型参数。
为通用的类模板定义中的模板类型参数指定了具体类型而生成的类称为模板类。
6.2.3
什么叫线性表？其基本操作包括哪些？其中插入一个元素的关键在哪儿？
答：线性表是数据结构中的概念：每两个相邻元素之间都有直接前驱和直接后继的关系。这里除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱；除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素无后继。这样的特性称为线性关系。
基本操作包括：计算表长度，寻找变量或对象x（其类型与表元素相同）在表中的位置（下标值），判断x是否在表中，删除x，将x插入列表中第i个位置，寻找x的后继，寻找x的前驱，判断表是否空，判断表是否满，取第i个元素的值等。
当需要在顺序表的指定位置i插入一个数据x时，必须为它腾出这个位置，把从该位置开始向后的所有元素数据，后移一个位置，最后才插入。关键是后移时从最后一个元素开始。否则先移的数据会冲掉未移的数据。
6.2.4
采用索引查找有哪些优点？它需要被查找数据有序吗？
答：索引，就象一本书的目录，找到标题，再看一下页号，立即可以翻到。索引查找不要求被查找数据有序，只要求索引有序。
6.2.5
简单叙述阅读理解复杂指针的方法。设Node为类，下面两个标识符fa和pa分别代表什么？Node* (*fa(int))(); Node* (*(*pa)[])();
答：理解和构造对象说明的方法是：先撇开标识符，按从右到左的顺序逐个解释每个说明符，如果有括号则改变解释的先后，先解释括号内再解释括号外。
fa是有一个整型参数的函数，其返回值是指针，该指针是指向无参函数的指针，而该无参函数的返回值是指向Node类的指针。pa是指向数组的指针，该数组的元素均为函数指针，所指向的函数无参、返回值是指向Node类的指针。
二、.编程与综合练习题
第六章 模板与数据结构题 3
6.3 使用自定义字符串类，编写求数组元素中最大值的函数模板。
解：函数模板有三种应用方式：
1．类模板的成员函数，在模板类型参数中重载函数和运算符，直接访问私有数据成员，实
现通用算法。这是标准的面向对象的方法。
2．函数模板处理模板类，以类模版为参数，用模板类型参数中重载的函数或运算符，实现通用算法。但调用类模板的接口函数间接访问私有数据成员，也是常见的。
3．函数模板处理普通数据，往往要用函数作为参数，实现通用算法。这是面向过程的方法。 解：使用独立的函数模板，相对简单。 #include const int n=256; class mystring{//为简单只保留用到的函数 char str[n]; //存放字符串的数组容器 int maxsize; //最大可用元素数，可防止数组出界，提高健壮性 int last; //已用元素数 mystring(){ last=-1; maxsize=n; str[0]='\\0'; cout<<\"缺省构造函数\"< } mystring(char *s){//当C字符串过长，初始化时采用截尾处理 } mystring(mystring & ms){ last=-1; } ~mystring(){ cout<<\"析构函数\"< do{ last++; str[last]=ms.str[last]; }while(last }while(s[last]!='\\0'&&last void show(){//如需重载<<，则请参见9.3节，暂时未学到,替代方法是改用show()函数 cout< }; mystring & mystring::operator=(char* ms){ //用C字符串赋值自定义字符串 last=-1; do{ last++; str[last]=ms[last]; }while(ms[last]!='\\0'&&last return *this; }//这里返回值为引用，不调用拷贝构造函数 mystring& mystring::operator=(mystring & ms){ last=-1; do{ } last++; str[last]=ms.str[last]; }while(last do{ k=str[i]-ms.str[i]; i++; }while(k==0&&i } template int i; char sp[6][10]= {\"南京大学\东南大学\交通大学\清华大学\天津大学\复旦大学\Groap max_val=r_array[0]; for (int i=1;i mystring ms[6];// 对象数组 for(i=0;i<6;i++) ms[i]=sp[i]; cout<<\"打印学校名称：\"< } 6.4 将自定义字符串类用于对半查找的函数模板。 解1：为简化，使用独立的函数模板 #include using namespace std; const int n=256; class mystring{//为简单只保留用到的函数 char str[n]; //存放字符串的数组容器 int maxsize; //最大可用元素数，可防止数组出界，提高健壮性 int last; //已用元素数 mystring(){ last=-1; maxsize=n; str[0]='\\0'; cout<<\"缺省构造函数\"< } mystring(char *s){//当C字符串过长，初始化时采用截尾处理 last=-1; maxsize=n; do{ last++; str[last]=s[last]; }while(s[last]!='\\0'&&last mystring(mystring & ms){ } last=-1; maxsize=n; do{ last++; str[last]=ms.str[last]; }while(last ~mystring(){ cout<<\"析构函数\"< void show(){//如需重载<<，则请参见9.3节，暂时未学到，替代方法是改用show()函数 cout< mystring & operator=(char * ms);//这里重载的=是把C风格字符串赋给mystring mystring& operator=(mystring &); bool operator<(mystring &); }; mystring & mystring::operator=(char* ms){ //用C字符串赋值自定义字符串 last=-1; do{ last++; str[last]=ms[last]; }while(ms[last]!='\\0'&&last return *this; }//这里返回值为引用，不调用拷贝构造函数 mystring& mystring::operator=(mystring & ms){ last=-1; do{ last++; str[last]=ms.str[last]; }while(last bool mystring::operator<(mystring & ms){ int i=0,k; do{ k=str[i]-ms.str[i]; i++; }while(k==0&&i } template int high=size-1 ,low=0,mid; // size 当前有序表元素数量 while(low<=high){ mid=(low+high)/2; if(x else return mid; } return mid; } int main(){//此例为了简化未用对象数组类模板 } int i; char sp[6][10]= {\"东南大学\复旦大学\交通大学\南京大学\清华大学\天津大学\ mystring ms[6],x=\"交通大学\南京大学\"; for(i=0;i<6;i++) ms[i]=sp[i]; for(i=0;i<6;i++) ms[i].show(); i=BinarySearch(ms,x,6); cout< const int n=256; class mystring{//为简单只保留用到的函数 char str[n]; //存放字符串的数组容器 int maxsize; //最大可用元素数，可防止数组出界，提高健壮性 int last; //已用元素数 mystring(){ last=-1; maxsize=n; str[0]='\\0'; cout<<\"缺省构造函数\"< } mystring(char *s){//当C字符串过长，初始化时采用截尾处理 last=-1; maxsize=n; do{ last++; str[last]=s[last]; }while(s[last]!='\\0'&&last mystring(mystring & ms){ 第六章 模板与数据结构题 8 last=-1; maxsize=n; do{ last++; str[last]=ms.str[last]; }while(last ~mystring(){ cout<<\"析构函数\"< void show(){//如需重载<<，则请参见9.3节，暂时未学到，替代方法是改用show()函数 cout< bool operator<(mystring &); }; mystring & mystring::operator=(char* ms){ //用C字符串赋值自定义字符串 last=-1; do{ last++; str[last]=ms[last]; }while(ms[last]!='\\0'&&last return *this; }//这里返回值为引用，不调用拷贝构造函数 mystring& mystring::operator=(mystring & ms){ last=-1; do{ } last++; str[last]=ms.str[last]; }while(last int i=0,k; do{ k=str[i]-ms.str[i]; i++; }while(k==0&&i 第六章 模板与数据结构题 9 return false; } template T slist[size]; int getlast(){return last;} T getslist(int k){return slist[k];} void putslist(T t,int k){slist[k]=t;} Orderedlist(){last=-1;maxsize=size;} bool Insert(T & elem,int i); public: void print(); int BinarySearch(T); // 无关成员函数省略,缺省的=等不必定义 };//再次指出分号不可少 template } last++; for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; return true; template for(i=0;i<=last;i++){ slist[i].show(); if(i%5==4) cout< cout< while(low<=high){ mid=(low+high)/2; if(x return mid; 第六章 模板与数据结构题 10 int main(){ } const int h=8; int i; Orderedlist char sp[h][10]={\"东南大学\复旦大学\交通大学\南京大学\清华大学\ \"天津大学\同济大学\浙江大学\for(i=0;i mystring x(\"交通大学\"),y(\"东南大学\"); i=ordlist.BinarySearch(x); cout< 也可用大于比较，冒泡采用从下往上。 解：用小于比较，冒泡采用从上往下。使用字符串类string。 #include template Orderedlist(){last=-1;maxsize=size;} void BubbleSort(); bool Insert(T & elem,int i); void print(); // 无关成员函数省略,缺省的=等不必定义 };//再次指出分号不可少 template if (i<0||i>last+1||last==maxsize-1) return false; else{ } last++; for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; return true; 第六章 模板与数据结构题 11 } template cout< template bool noswap; int i,j; T temp; for (i=last;i>0;i--){//从上往下冒泡，对比例6.8有何不同？ noswap=true; //未交换标志为真 } for(j=0;j noswap=false; } } if(noswap) break; //本趟无交换，则终止算法。 int main(){ const int h=8; int i; } Orderedlist string sp[h]={\"南京大学\东南大学\交通大学\清华大学\ \"天津大学\复旦大学\浙江大学\同济大学\ for(i=0;i cout<<\"已排序表：\"< 6.6 现有两个已升序排好的数组，将它们合并为一个升序排序的数组（归并），请用函数模 板实现。该方法可以演变成归并排序。 算法：两数组合并时，可为每个数组各安排一个指针，从第一个元素开始比较两数组对应元素，小的取下来，顺序放入新的数组；取下所指元素的指针后移，再比较，依此类推；直到其中一个数组的元素已全部放入新数组，再把另一数组余下的元素全部 顺序放入新数组，归并完成。 解：此处是面向对象的方法 #include template int last; T slist[size]; public: Orderedlist(){last=-1;maxsize=size;} void BubbleSort(); bool Insert(T & elem,int i); void print(); void Merge(Orderedlist &,Orderedlist &); // 无关成员函数省略,缺省的=等不必定义 };//再次指出分号不可少 template } for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; last++; return true; } template int i; for(i=0;i<=last;i++){ cout< cout< template bool noswap; int i,j; T temp; 第六章 模板与数据结构题 13 for (i=last;i>0;i--){//从上往下冒泡，对比例6.8有何不同？ } noswap=true; //未交换标志为真 for(j=0;j temp=slist[j]; slist[j]=slist[j+1]; slist[j+1]=temp; noswap=false; } if(noswap) break; //本趟无交换，则终止算法。 } template while((i<=ls1.last)&&(j<=ls2.last)){ if(ls1.slist[i] } while(i<=ls1.last) {//复制第一个表的剩余元素 slist[k]=ls1.slist[i];i++; k++;last++; } while(j<=ls2.last) {//复制第二个表的剩余元素 } slist[k]=ls2.slist[j];j++; k++;last++; } int main(){ \ const int h=15; int i,h1=8,h2=5; Orderedlist char sp1[h][10]={\"南京大学\东南大学\交通大学\清华大学\天津大学\复旦大学\"浙江大学\同济大学\ for(i=0;i 第六章 模板与数据结构题 14 cout<<\"已排序表：\"< char sp2[h][10]={\"南开大学\吉林大学\中山大学\武汉大学\科技大学\for(i=0;i cout<<\"已排序表：\"< 6.7 希尔排序（shell sort），又称缩小增量排序（diminishing increment sort）。其思想如下： 设线性表L长度为n，取增量gap=n/2，即以L[0]和L[gap]为一组，L[1]和L[gap+1]为一组，L[2]和L[gap+2]为一组，……，L[n-gap]和L[n]为一组，分别进行插入排序。 再取gap=gap/2，则分组成为L[0]，L[gap]，L[2gap]，……为一组，L[1]，L[gap+1]，L[2gap+1]，……为一组，等等，分别进行插入排序。直到gap=1，这时分组成为整个表，并只有一个组，再插入排序，完成全部任务。参见下图： 初始 1 2 20 20 20 20 6 26 – 26 15 15 15 49 – – 49 6 6 20 21 21 – – 21 21 21 15 15 – 26 26 26 6 6 49 49 49 分组1，gap=3 分组2 分组3 结果 gap=1 结果 全部采用函数模板，包括希尔插入子程序。分组直接用增量控制在原线性表中进行 插入排序。 解：本解希尔排序是成员函数，是C++的标准用法，标准模板库（STL）就是如此用的。是纯面向对象的方法 #include using namespace std; template int maxsize; int last; T slist[size]; void Shellinsert(const int); public: 第六章 模板与数据结构题 15 int getlast(){return last;} T getslist(int k){return slist[k];} void putslist(T t,int k){slist[k]=t;} Orderedlist(){last=-1;maxsize=size;} bool Insert(T & elem,int i); void print(); void Shellsort(); // 无关成员函数省略,缺省的=等不必定义 };//再次指出分号不可少 template if (i<0||i>last+1||last==maxsize-1) return false; else{ for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; last++; return true; } } template int i; for(i=0;i<=last;i++){ } cout< int gap=(last+1)/2; while(gap){ Shellinsert(gap);//一趟排序 } gap/=2; template T temp; //注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号， //插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。 for(i=gap;i<=last;i++){//从第一个子序列开始直接插入排序，但不是完成一个子序列， //再做下一个子系列，而是先做每个子序列的第一步，再做每个子序列的第二步，等等， //穿插完成。直接插入排序总是从后逐个向前，找到第一个比待插元素大的，则插在前面。 temp=slist[i];//待插元素放temp中 j=i; 第六章 模板与数据结构题 16 } } while(j>=gap&&temp slist[j]=temp;//将temp插入正确的空位 int main(){ const int h=8; int i; Orderedlist char sp[h][10]={\"南京大学\东南大学\交通大学\清华大学\天津大学\复旦大学\\"浙江大学\同济大学\ for(i=0;i 解2：这里希尔排序是独立的函数，而线性类模板作为形参，也是一种常见的用法。 #include using namespace std; template int last; T slist[size]; public: int getlast(){return last;} T getslist(int k){return slist[k];} void putslist(T t,int k){slist[k]=t;} Orderedlist(){last=-1;maxsize=size;} bool Insert(T & elem,int i); void print(); // 无关成员函数省略,缺省的=等不必定义 };//再次指出分号不可少 template 第六章 模板与数据结构题 17 } } for (int j=last;j>i;j--) slist[j]=slist[j-1]; slist[i]=elem; last++; return true; template int i; for(i=0;i<=last;i++){ cout< cout< template int gap=(list.getlast()+1)/2; while(gap){ Shellinsert(list,gap);//一趟排序 gap/=2; } }//int size必须保留 template //注意每一趟排序包含若干子序列,其中第一个子序列第一个元素是0号,第二个元素是gap号， //插入排序认为单个元素是排好序的，所以从每个子序列的第二个元素开始插入排序。 for(i=gap;i<=list.getlast();i++){//从第一个子序列开始直接插入排序，但不是完成一个 //子序列，再做下一个子系列，而是先做每个子序列的第一步，再做每个子序列的第二步， //等等,穿插完成。直接插入排序总是从后逐个向前,找到第一个比待插元素大的,则插在前面。 temp=list.getslist(i);//待插元素放temp中 } int main(){ } j=i; while(j>=gap&&temp } list.putslist(temp,j);//将temp插入正确的空位 const int h=8; int i; Orderedlist 第六章 模板与数据结构题 18 } string n[h]; char sp[h][10]={\"南京大学\东南大学\交通大学\清华大学\天津大学\复旦大学\\"浙江大学\同济大学\ for(i=0;i cout<<\"已排序表：\"< 因篇幅问题不能全部显示，请点此查看更多更全内容