数据结构习题解答(1-8章)

PAGE111-数据结构习题解答计算机科学与工程学院2004年10月第0章C++基础一、基本概念题0-1函数和成员函数有什么区别？[解]:C++中有两种类型函数：常规函数和成员函数.二者既有区别又有联系。（1）二者作用不同：常规函数通常用于表示一个特定的功能；成员函数用于某个特定类方法的定义。（2）二者定义方法不同：常规函数通常可以存放在程序的任意位置；成员函数只能用于存放在特定类的实现文件中。（3）二者的调用规则不同：常规函数通常可以在其作用域内的任意调用；成员函数必须通过特定类或特定类的实例调用。（4）二者的作用域不同：常规函数通常具有全局作用域内；成员函数必须则具有封装性、继承性和多态性等特征。0-2在函数中，什么叫输入型参数？什么叫输出型参数？[解]:输入型参数：是指调用函数只通过该参数传送数据给被调用函数，被调用函数在执行过程中对该参数的修改不能传递给调用函数；输出型参数：是指调用函数只通过该参数把被调用函数处理后得到的结果数据传送给调用函数，由于这样的参数是从被调用函数得到数据的，所以称为输出型参数.0-3什么叫引用？函数的引用类型参数是怎样实现输出型参数功能的？[解]:所谓引用是给变量或对象起一个别名，即引用引人了一个变量或对象的同义词.由于函数被调用时，函数的引用类型参数传递给被调用函数的是调用函数中某个对象（实际参数）的引用，所以被调用函数种任何给引用参数的赋值就是给实际参数的赋值，所以引用参数能实现输出型参数的功能.0-4一个成员函数的参数类型为引用类型和常值引用类型有什么不同？[解]:C++中函数(包括常规函数和成员函数)的参数有四种方式：值参数、常值参数、引用参数和常值引用参数方式.其中，值参数、常值参数和常值引用参数均为输入型参数。即这些参数方式的函数调用不会改变对应形式参数的实际参数的值.但他们又各有不同的特点：值参数方式在运行时对应的实际参数的值拷贝给形式参数，被调用函数可以修改形式参数的值，当函数终止时，形式参数的值不拷贝回实际参数。常值参数方式在运行时将对应的实际参数的值拷贝给形式参数，被调用函数不能修改形式参数的值.常值引用参数方式在运行时将对应的实际参数的引用（地址）拷贝给形式参数，被调用函数不能修改形式参数的值.所以，当参数的存储空间较大时，常值引用参数方式将更节省存储空间和运行时间。0-5一个成员函数的返回值类型为引用类型和常值引用类型有什么不同？[解]:当成员函数返回值为引用方式时，由于引用型变量不是单独定义的，所以该成员函数返回值是一个已存在变量(或对象)的别名.当该成员函数被重新赋值时则其对应的变量(或对象)值将改变.当成员函数返回值为常值引用方式时，其返回值和引用方式的成员函数返回值类同，只是该成员函数返回值不能被重新赋值.0-6函数的返回值是全局变量还是局部变量？函数中能否用函数的返回值给其他变量对象赋值？为什么？[解]:函数的返回值属于全局变量.函数中可以用函数的返回值给其他变量对象赋值。0-7什么叫类？一个类中主要包括哪两部分？[解]:类是对具有相同属性和相同方法的一组对象的抽象.类定义包括类中成员变量(或称属性)的定义和成员函数(或称方法)的定义.C++中使用标识符class定义类。0-8类有哪几种访问权限？各种访问权限的定义有什么不同？[解]:类的成员变量和成员函数有三种访问权限：私有(private)、公有(public)和保护(protected).其中私有权限（private）成员是外部不可见的，只能由该类对象的成员函数以及被声明为友元的函数或声明为友元的类的对象的成员函数访问.公有权限(public)成员都是外部程序可见的.公有部分中的成员变量和成员函数既允许该类对象的成员函数访问，也允许程序中其他函数或其他类的对象的成员函数访问.一个类的公有部分构成了这个类的操作界面.外部函数和对象通过该操作界面对该类对象进行操作.保护权限(protected)成员和私有权限(private)成员一起构成类的私有部分，保护权限(protected)成员允许该类的派生类访问.0-9类的构造函数是什么时候执行的？类的析构函数是什么时候执行的？[解]:构造函数是当定义对象时被自动调用的特殊成员函数，用来在内存中建立类的具体对象(即在内存中为该对象分配适当的空间)并对其进行初始化赋值的成员函数.析构函数是当对象被撤销时被自动调用的特殊成员函数.当一个对象被撤销时，析构函数提供了释放该类对象占用内存空间的方法.0-10什么叫重载？在软件设计中，类的成员函数重载有什么作用？[解]:重载就是两个或两个以上的函数(或运算符)使用相同的名字.重载功能除了可以增强函数设计和类设计的灵活性和通用性以外，还可以支持类的多态性.0-11什么叫友元？哪些成分可以定义为一个类的友元？[解]:在C++中，一个类的友元可以存取这个类的私有成分.一个类的友元可以是其他类的成员函数、外部函数和其他类.0-12派生类有哪几种派生方式？[解]:派生类的派生方式主要有public派生方式和private派生方式两种.0-13什么叫多态性？什么叫虚函数？[解]:多态性是指当相同对象收到不同的消息或不同对象收到相同的消息时产生不同的方法调用的特性.C++支持两种多态性：一种是编译时的多态性，编译时的多态性是指这种多态性在编译时即进行了确认和绑定.编译时的多态性是通过重载函数来实现的.另一种是运行时的多态性.运行时的多态性是指这种多态性在运行时才进行识别和绑定.虚函数是在基类中被说明为virtual，并在派生类中重新定义的成员函数.系统在识别到虚函数时，在运行时才决定当前实际调用的是基类中的成员函数还是派生类中的成员函数，因此，虚函数实现多态性的方法也可看做是成员函数的动态重载.0-14什么叫纯虚函数？什么叫抽象类？[解]:纯虚函数是在基类中说明的虚函数，它在基类中没有定义，但要求任何派生类都要定义各自的实现方法.包含有纯虚函数的类称为抽象类.由于抽象类包含了没有函数定义的纯虚函数，所以不允许定义抽象类的对象.0-15抽象数据类型和模板各自是怎样实现程序的通用化设计的？[解]:在C++中，实现通用化的软件设计的方法主要有抽象数据类型法和模板法.抽象数据类型方法是在定义类时，其成员变量的数据类型使用抽象数据类型，当应用程序具体包含该类头文件前再对该抽象数据类型进行具体定义.模板方法是把函数或类中的数据类型作为参数设计模板函数或模板类，经过参数实例化，变为一个类型参数具体的函数或类的实例，完成具体的功能.0-16什么叫静态内存分配？什么叫动态内存分配？动态内存分配有什么优点？[解]:程序中使用的数组元素个数或占用内存单元的大小是在程序编译时就确定的，因此在程序运行时这些数组的元素个数或占用内存单元的大小是确定的，这种内存分配方法称做静态内存分配.静态内存分配的缺点是程序中数组个数或占用内存单元的大小是固定的，在程序运行过程中不能修改.动态内存分配是在程序运行时确定数组元素个数或占用内存单元的大小，从而可在程序运行时根据需要分配内存空间.0-17写出new运算符的语法格式和delete运算符的语法格式.[解]:new运算符的语法格式为：new类型名(初始值);其中，类型名指定了要分配存储空间的类型.delete运算符用于释放单个对象内存空间的语法格式为：delete指针;delete运算符用于释放对象数组内存空间的语法格式为：delete［］指针;二、上机实习．0-18定义和实现复数的C+＋类．要求：(1)复数的数据城包括复数的实部和虚部，复数的实部和虚部定义为浮点数.(2)构造函数包括三个：第一个构造函数没有参数．第二个构造函数有一个参数，即把一个浮点数赋给复数的实部，复数的虚部为0;第三个构造函数有两个参数，即把两个浮点数分别赋给复数的实部和复数的虚部.(3)复数的成员函数包括获取和修改复数的实部和虚部.(4)复数的成员函数还包括运算符重载形式的复数的+、-、*、／运算.(5)定义友元形式的重载的流函数来输入一个复数和输出一个复数.[解]:classComplex{private:floatmRealPart; //数据成员实部floatmVirtualPart; //数据成员虚部public:Complex(void); //构造函数一 Complex(floatrealPart); //构造函数二 Complex(floatrealPart,floatvirtualPart);//构造函数三 floatGetRealPart();//返回实部数据成员 floatGetVirtualPart(); //返回虚部数据成员 voidSetRealPart(floatRealPart);//设置实部数据成员 voidSetVirtualPart(floatvirtualPart);//设置虚部数据成员 floatMod();//返回复数的模 Complex&operator+(Complexc); //重载复数的加法运算 Complex&operator-(Complexc); //重载复数的减法运算 Complex&operator*(Complexc); //重载复数的乘法运算 Complex&operator/(Complexc); //重载复数的除法运算 //操作符>><<重载,定义为友元函数friendostream&operator<<（ostream&ostr，ComPlex&c);friendistream&operator>>（istream&istr，ComPlex&c);};Complex::Complex(void){ mRealPart=mVirtualPart=0;}Complex::Complex(floatrealPart){ mRealPart=realPart; mVirtualPart=0;}Complex::Complex(floatrealPart,floatvirtualPart){ mRealPart=realPart; mVirtualPart=virtualPart;}floatComplex::GetRealPart(){ returnmRealPart;}floatComplex::GetVirtualPart(){ returnmRealPart;}voidComplex::SetRealPart(floatrealPart){ mRealPart=realPart;}voidComplex::SetVirtualPart(floatvirtualPart){ mVirtualPart=virtualPart;}Complex&Complex::operator+(Complexc){ Complex*result=newComplex(); result->mRealPart=mRealPart+c.mRealPart; result->mVirtualPart=mVirtualPart+c.mVirtualPart; return*result;}Complex&Complex::operator-(Complexc){ Complex*result=newComplex(); result->mRealPart=mRealPart-c.mRealPart; result->mVirtualPart=mVirtualPart-c.mVirtualPart; return*result;}Complex&Complex::operator*(Complexc){ Complex*result; result=newComplex(); result->mRealPart=mRealPart*c.mRealPart-mVirtualPart*c.mVirtualPart; result->mVirtualPart=mRealPart*c.mVirtualPart+mRealPart*c.mVirtualPart; return*result;}Complex&Complex::operator/(Complexc){ Complex*result=newComplex(); floatm; m=c.Mod(); if(m==0) exit(0); result->mRealPart=(mRealPart*c.mRealPart+mVirtualPart*c.mVirtualPart)/m; result->mVirtualPart=(mRealPart*c.mVirtualPart-mRealPart*c.mVirtualPart)/m; return*result;}floatComplex::Mod(){ returnsqrt(mRealPart*mRealPart+mVirtualPart*mVirtualPart);}ostream&operator<<（ostream&ostr，constComplex&c)//输出流操作符<<重载{ cout<<“实部:“<<c.mRealPart; cout<<“虚部:“<<c.mVirtualPart<<endl; returnostr;}istream&operator>>（istream&istr，Complex&c)//输入流操作符>>重载{cout<<”输入实部：”cin>>c.mRealPart;cout<<”输入虚部：”cin>>c.mVirtualPart;returnistr;}

第1章数据结构绪论1-1什么叫数据？什么叫数据元素？什么叫数据项？[解]:数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。表示一个事物的一组数据称做一个数据元素；构成数据元素的数据称做该数据元素的数据项。1-2什么叫数据的逻辑结构？什么叫数据的存储结构？什么叫数据的操作？[解]:数据元素之间的相互联系方式称为数据的逻辑结构。数据元素在计算机中的存储方式称为数据的存储结构。对一种数据类型的数据进行的某种处理称做数据的操作；对一种数据类型的数据进行的所有操作称做数据的操作集合。1-3数据结构课程主要讨论哪三个方面的问题？[解]:数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型的常用数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。1-4分别画出线性结构、树结构和图结构的逻辑示意图。[解]:1-5什么叫类型？什么叫数据类型？什么叫抽象数据类型？[解]:类型是一组值的集合。数据类型是指一个类型和定义在这个类型上的操作集合。抽象数据类型(AbstractDataType,ADT)是指一个逻辑概念上的类型和这个类型上的操作集合。1-6怎样利用抽象数据类型设计大型软件？[解]:抽象数据类型使软件设计成为工业化流水线生产的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司(或专门设计人员)设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；另一方面，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司(或专门设计人员)可以安全、快速、方便地完成该应用软件系统的设计。软件的设计采用模块化方法，抽象数据类型(如表、堆栈、队列、串、数组、树、二叉树、图等)就是构造大型软件的最基本模块。用这些专门公司设计好的抽象数据类型，就可以安全、快速、方便地设计功能复杂的大型软件。数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等抽象数据类型的基本功能和实现方法。在C++语言中，类就是确定了数据元素存储结构的抽象数据类型的具体实现。1-7什么叫算法？算法的5个性质是什么？[解]:算法是描述求解问题方法的操作步骤集合。算法满足以下性质：(1)输入性：具有0个或若干个输入量；(2)输出性：至少产生一个输出或执行一个有意义操作；(3)有限性：执行语句的序列是有限的；图1-4例1-2算法实现方法图示(4)确定性：每一条语句的含义明确，无二义性；(5)可执行性：每一条语句都应在有限的时间内完成。1-8根据算法的性质解释算法和程序的区别。[解]:程序和算法的惟一区别是程序允许无限循环，而算法不允许无限循环。1-9评判算法的优劣有哪几种方法？[解]:算法设计应满足以下5个目标：(1)正确性：算法应确切地满足具体问题的需求，这是算法设计的基本目标。(2)可读性：算法的可读性有利于人们对算法的理解，这既有利于程序的调试和维护，也有利于算法的交流和移植。算法的可读性主要体现在两方面：一是变量名、常量名、函数名等的命名要见名知意；二是要有足够多的注释。(3)健壮性：当输入非法数据时算法要能做出适当的处理，而不应产生不可预料的结果。(4)高时间效率：算法的时间效率指算法的执行时间。对于同一个问题，如果有多个算法可供选择，应尽可能选择执行时间短的算法。执行时间短的算法称做高时间效率的算法。(5)高空间效率：算法在执行时一般要求额外的内存空间。对于同一个问题，如果有多个算法可供选择，应尽可能选择内存要求低的算法。内存要求低的算法称做高空间效率的算法。1-10什么叫算法的时间复杂度？怎样表示算法的时间复杂度？[解]:算法的时间复杂度也就是算法的时间效率，通常是算法所处理的数据元素个数n（亦称问题规模）的函数。算法的时间复杂度分析就是分析算法执行时间与算法所处理的数据元素个数n之间的关系。通常采用O(f(n))表示法。l-11设n为已在算法前边定义的整数类型，并已知n为正整数，分析下列各算法中加下划线语句的执行次数，并给出各算法的时间复杂度T(n)。(1)inti=1，k=0;while(i＜n-1){k=k+10*I;i=i+1；}(2)intI=1，k=0;do{k=k+10*i：i=i+1；｝while(i！=n)；(3)inti=1，J=1；while(i＜=n&&j＜=n)｛i=i+1；J=J+1}(4)intx=n；//n＞1inty=0；while(x＞=(y+1)*(y+1))y++；(5)inti,j，k，x=0；for(i=0；i＜n;I++)for(j=0;j＜i；j++)for(k=0;k＜j；k++)x=x+2；[解]:(1)语句的执行次数为n-2次，T(n)=0(n)。(2)语句的执行次数为n-1次，T(n)=0（n）。(3)语句的执行次数为n次，T(n)=0（n）。(4)语句的执行次数约为n1/2次,T(n)=0(n1/2).(5)语句的执行次数为（n(n-1)(n-2)）/6次，T(n)=0(n3)1-12设求解同一个问题有三种算法，三种算法各自的时间复杂度分别为0(n2),O(2n)和0(nlgn),哪种算法最可取？为什么？[解]:第三种算法最可取，因为三者比较起来，当n充分大时，T(n)=0(nlgn)时间效率最高。1-13按增长率从小到大的顺序排列下列各组函数：(1)2100，(3/2)n，(2/3)n，(4/3)n(2)n，n3/2，n2/3，n！，nn(3)1bn，nxlbn，nlbn,n[解]:(1)(2/3)n，2100,(4/3)n，(3/2)n(2)n2/3，n,n3/2，n！，nn、(3)lbn，n，nxlb，nlbn”1-14下面是几个典型的时间复杂度函数估值问题：(1)当n为正整数时，n取何值能使2n＞n3？(2)说明2n+n3是o(2n)。(3)给出5(n2+6)／(n+3)+7lgn的0值估计。[解]:（1）当n=1或n>=12时，2n＞n3(2)说明2n+n3是o(2n)。首先，2n+n3>2n总成立。反之，因为当n>12时，n3<2n总成立,所以2n+n3<2*2n成立.所以2n+n3是o(2n)。(3)5(n2+6)／(n+3)+7lgn的0值估计是O（n）。

第2章线性表一、基本概念题2-1什么叫线性表？[解]:线性表是一种可以在任意位置进行插入和删除数据元素操作、由n(n≥0)个相同类型数据示素ao，al，a2，…，an-1，组成的线性结构.2-2什么叫线性结构？线性表是线性结构吗？为什么？[解]:线性结构是除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素。线性表是一种可以在任意位置进行插入和删除数据元素操作、由n(n≥0)个相同类型数据示素ao，al，a2，…，an-1，组成的线性结构.2-3什么叫顺序存储结构？什么叫链式存储结构？[解]:顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。链式存储结构是使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上(即内存存储位置上)不一定相邻，数据间的逻辑关系表现在结点的链接关系上。2-4写出线性表的抽象数据类型.[解]:线性表的抽象数据类型数据集合：线性表的数据集合可以表示为ao，al，a2，…，an-1，每个数据元素的数据类型为抽象数据元素类型DataType.操作集合：（1）初始化Initiate（L）：初始化线性表Lo(2)求当前数据元素个数Size(L)：求线性表L的当前数据元素个数并由函数返回.(3)插入数据元素Insert（L,i，x）：在线性表L的第i个数据元素前插入数据元素x.(4)删除数据元素Delete(L,i):删除线性表L的第i个数据元素，所删除的数据元素由由函数返回.(5)取数据元素GetData(L,i，x):取线性表L的第i个数据元素，所取的数据元素由函数返回.2-5什么叫指针？什么叫头指针？什么叫头结点？[解]:指针是指向物理存储单元地址的变量.把指向单链表的指针称为头指针.头指针所指的不存放数据元素的第一个结点称做头结点.2-6画出有n个数据元素的带头结点的单链表、循环单链表和循环双向链表结构[解]:图2-5带头结点的单链表图2-15带头结点的循环单链表图2-17带头结点的循环双向链表2-7在链表设计中，为什么通常采用带头结点的链表结构？[解]:当选用带头结的单链表时，设头指针用head表示，则在第一个数据元素结点前插入结点时，不会改变头指针head的值.同时，删除第一个数据元素结点时，不会改变头指针head的值，改变的是头指针所指结点的指针域的值.但若选用不带头结点的单链表，在第一个数据元素前插入结点时，头指针head的值将改变为新插入结点的指针.类似地，删除不带头结点单链表第一个数据元素结点时，头指针head的值将改变为等于head->next,即指针head等于原head->next的值。所以采用带头结点的链表结构可以简化链表链表的插入删除等算法。2-8说明C++语言动态申请和动态释放内存空间的new运算符和delete运算符的功能和使用方法.[解]:在C++语言中，用new运算符进行动态内存的申请，用delete运算符进行动态内存的释放.使用方法如下：new运算符的语法格式为：new类型名(初始值);其中，类型名指定了要分配存储空间的类型.delete运算符用于释放单个对象内存空间的语法格式为：delete指针;delete运算符用于释放对象数组内存空间的语法格式为：delete［］指针;2-9在顺序表类中实现插入方法和删除方法时为什么必须移动数据元素？插入方法和删除方法移动数据元素的方向是否相同？[解]:顺序存储结构是把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。当插入和删除数据结点时，数据元素间的关系发生了改变，这也就要求数据的存储位置进行相应的改变以保持“逻辑上相邻的数据元素在物理上也相邻”。所以，在顺序表类中实现插入方法和删除方法时必须移动数据元素。插入方法和删除方法移动数据元素的方向恰好相反。2－10对比顺序表类和单链表类的设计，说明顺序表和单链表的主要优点和主要缺点.[解]:顺序表的主要优点是算法简单，空间单元利用效率高；主要缺点是需要预先确定数据元素的最大个数，并且进行插入和删除操作时需要移动较多的数据元素.单链表的主要优点是不需要预先确定数据元素的最大个数，插入和删除操作时不需要移动数据元素；主要缺点是每个结点中要有一个指针域，因此空间单元利用效率不高.另外，单链表操作的算法较复杂.二、算法设计题(说明：凡要求设计某个类成员函数的作业，均假设该成员函数已在相应类中定义过.）2-11编写一个逐个输出顺序表中所有数据元素的成员函数.[解]:voidSeqList：：List(void）//逐个输出顺序表中所有数据元素{inti;for(i=0;i<size;i++）{cout<<list[i];}}2-12编写一个逐个输出单链表中所有数据元素的成员函数.[解]:template<classT>voidLinList<T>：：List(void){//逐个输出单链表中所有数据元素ListNode<T>*P; P=head->next;//P指向第一个结点while(p！=NULL)//循环释放结点空间直至初始化状态{ cout<<p->data; p=p->next;｝｝2-13编写顺序表定位操作的成员函数.顺序表定位操作的功能是：在顺序表中查找是否存在数据元素x，如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号从0开始编号）；如果不存在，返回-1[解]:intSeqList：：Find(DataTypex){for(inti=0；i<size；i++){ if（list[i]==x） returni；//查找到元素xelse continue；} return-1；//未查找到元素x}2-14在有些应用中，允许线性表中存在值相同的数据元素.线性表的另一个删除操作GetDeleteMore(L,x)的功能是：删除线性表L中所有等于x的数据元素.要求编写实现带头结点单链表删除操作的成员函数.[解]:template<classT>LinList<T>：：GetDeleteMore（Tx）//删除线性表L中所有等于x的数据元素{ListNode<T>*s,*p=head；//p为指向头结点指针While(p!=NULL){While(p->next!=NULL&&p->next->data==x){s=p->next;p->next=s->next;deletes;size--;}p=p->next;}}2-15编写实现顺序表逆置的成员函数，即要求把顺序表A中的数据元素序列（ao,a1,….,an-1）逆置为（an-1,……,a1,a.），并把逆置后的数据元素存储到顺序表B中.[解]:voidSeqList::Converse(SeqLista,SeqListb){inti;b.size=a.size；for（i=0;i<a.size;i++）b.list[a.size–i-1]=a.list[i]；}2-16编写实现顺序表就地逆置的成员函数，即要求利用原顺序表的存储单元，把数据元素序列（ao,a1,….,an-1）逆置为（ao,a1,….,an-1）.[解]:voidSeqList::Converse(void){intmid，i;DataTypex；mid=size/2；for（i=0;i<mid;i++）{

x=list[i]；list[i]=list[size-1-i]；list[size-1-i]=x；}}2-17编写实现带头结点单链表逆置的成员函数，即要求把带头结点单链表la中的数据元素序列（ao,a1,….,an-1）逆置为（an-1,……,a1,a.），并把逆置后的数据元素存储到带头结点单链表lb中.[解]:template<classT>voidConverse(LinList<T>la,LinList<T>&lb){ListNode<T>*p，*q;lb.head=newListNode<T>();p=la.head->next；while(p！=NULL){q=newListNode<T>(p->data,lb->next);lb->next=q;P=P->next；}}2-18编写实现带头结点单链表就地逆置的成员函数，即要求利用原带头结点单链表的结点空间，把数据元素序列（ao,a1,….,an-1）逆置为（an-1,……,a1,a.）.[解]:template<classT>voidLinList<T>：：Converse(void){ListNode<T>*p，*g;p=head->next；head->next=NULL;while(p！=NULL){g=p；P=P->next；q->next=head->next；head->next=q；}}三、上机实习题2-19设计一个静态数组存储结构的顺序表类，要求：(1)包括和动态数组存储结构的顺序表类相同的成员函数.(2)用例2-1的问题要求进行测试.(3)用例2-2的问题要求进行测试.[解]:(1)包括和动态数组存储结构的顺序表类相同的成员函数.建立类实现文件SeqList.h.其内容如下：classSeqList{protected： DataType：list[maxSize]； //数组 intsize； //当前元素个数public： SeqList(void)； //构造函数~SeqList(void){}； //析构函数intSize(void)const； //取当前数据元素个数voidInsert（coastDataType&item,inti）；//插入DataTypeDelete（constintI）； //删除DataTypeGetData（inti）const； //取数据元素}；SeqList：：SeqList（void） //构造函数{size=0；｝intSeqList：：Size(void)const //取当前数据元索个数{ returnsize；}voidSeqList：：Insert（ConstDataType&item,inti）//播入//在指定位置I前播入一个数据元素item{if（size>=maxSize）{cout<<“顺序表已满无法插入！”<<endlexit(0)；}if（i<0||i>size=） //参数正确与否判断{cout<<“参数i越界出错！”<<endlexit（0）;}//从size-1至i逐个元素后移for（intj=size;j>i;j--）list[j]=list[j-1]；list[i]=item; //在i位置插入itemsize++; //当前元素个数加1}DataTypeSeqList：：Delete（constinti）//删除指定位置i的数据元素.删除的元素由函数返回{if（size==0）{cout<<“顺序表已空无元素可删！”<<endlexit(0)：}if（i<0||i>size-1）//参数正确与否判断{cout<<“参数i越界出错！”<<endlexit（0）；}DataTypex=list[i]； //取到要删除的元素//从i+1至size-1逐个元素前移for(intj=i;j<size-1;j++)list[j]=list[j+1]；size--; //当前元素个数减1returnx; //返回删除的元素}DataTypeSeqList：:GetData（inti）const //取数据元素//取位置i的教据元素.取到的数据元素由函数返回{if（i<O||i>size-1）//参数正确与否判断{cout（<<“参数i越界出错！”<<endlexit(0)；}returnlist[i]；//返回取到的元素}(2)用例2-1的问题要求进行测试.建立程序文件Exp2-1.cpp其内容如下：#include<iostream.h>#include<stdlib.h>typedefintDataType；//定义具体问题元素的数据类型#definemaxSize100#include“SeqList.h“//包含顺序表类voidmain（void){SeqListmyList（）；//定义顺序表类对象myListintn=10；for（inti=0；i<n；i++=//在myList中顺序插入10个元素myList.Insert（i+1,I）；myList.Delete(4)；//删除myList中数据元素5for（i=0；I<myList.Size（）；i++）//依次取myList中的元素并显示cout<<myList.GetData(i)<<””；}程序运行结果如下：12345678910(3)用例2-2的问题要求进行测试.建立程序文件Exp2-2.cpp其内容如下：#include<iostream，h>#include<stdlib.h>structStudentType//结构体StudentType{longnumber；//学号数据项charname[10]；//姓名数据项charsex[3]；//性别数据项intage； //年龄数据项}；typedefStudentTypeDataType；//定义DataType为StudentType数据类型#definemaxSize100#include"SeqList.h"//包含顺序表类voidmain(void){SeqListmyList()；StudentTypex[3]={{2000001，”张三”，”男”，20}{12000002，”李四”，”男”，21}{2000003，”王五”，”女”，22}}intn=3;DataTypes；for（inti=0：i<n；i++）//在myList中顺序插入3个元素myList.Insert（x[i].i）；for（i=0；i<myList.Size（）；i++）//依次取myList中的元素并显示{s=myList.GetData（i）；cout<<s.number<<<<s.sex<<s.age<<endl；}}2-20设计一个带头结点的循环单链表类，要求：(1)带头结点循环单链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素.(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性.[解]:(1)结点类的定义和实现如下,其实现文件为CircleList.htemplate<classT>classCircleList; //前视定义,否则友元无法定义template<classT>classListNode //模板类型为T{ friendclassCircleList<T>; //定义类LinList<T>为友元private: ListNode<T>*next; //指向下-结点的指针 Tdata; //定义为公有成员方便使用public: //构造函数!,用于构造头结点 ListNode(ListNode<T>*ptrNext=NULL){next=ptrNext;} //构造函数2,用于构造其他结点 ListNode(constT&item,ListNode<T>*ptrNext=NULL){data=item;next=ptrNext;} ~ListNode(void){} //析构函数};//单链表类的定义template<classT>classCircleList{private: ListNode<T>*head; //头指针 int size; //当前的数据元素个数 ListNode<T>*Index(inti); //定位public: CircleList(void); //构造函数 ~CircleList(void); //析构函数 intSize(void){returnsize;} //取当前数据元素个数 voidInsert(constT&item,inti); //插入 TDelete(inti); //删除 TGetData(inti); //取数据元素};//单链表类的实现template<classT>CircleList<T>::CircleList() //构造函数{ head=newListNode<T>(); //头指针指向头结点head->next=head; size=0; //size的初值为0}template<classT>CircleList<T>::~CircleList(void) //析构函数{ ListNode<T>*p,*q; p=head->next; //P指向第一个结点 while(p!=head) //循环释放结点空间直至初始化状态 { q=p; head->next=p->next; deleteq;p=head->next; } deletehead;}template<classT>ListNode<T>*CircleList<T>::Index(inti)//定位//返回指向第i个数据元素结点的指针//参数i的取值范围为:-l≤-i≤size-1;i=-1时返回头指针{ if(i<-1||i>size) { cout<<"参数i越界出错!"<<endl; exit(0); } if(i==-1) returnhead; //i为-1时返回头指针head ListNode<T>*p=head->next; //p指向第一个数据元素结点 intj=0; //从O开始计数 while(j<i) //寻找第i个结点 { p=p->next; j++; } returnp; //返回第i个结点的指针}template<classT>voidCircleList<T>::Insert(constT&item,inti)//插入//在第i个结点后插入一个元素值为item的新结点//参数i的取值范围为:０≤i≤size{ if(i<0||i>size) { cout<<"参数i越界出错!"<<endl; exit(0); } ListNode<T>*p=Index(i-1); //P为指向第i-1个结点的指针 //构造新结点p,p的data域值为item,next域值为p->next ListNode<T>*q=newListNode<T>(item,p->next); p->next=q; //新结点插入第i个结点前 size++; //元素个数加!}template<classT>TCircleList<T>::Delete(inti) //删除//删除第i个数据元索并由函数返回.参数土的取值范围为:0≤i≤size-1{ if(size==0) { cout<<"链表已空无元素可删!"<<endl; exit(0); } if(i<0||i>size-1) { cout<<"参数i越界出错!"<<endl; exit(0); } ListNode<T>*s,*p=Index(i-1); //p为指向第i-1个结点指针 s=p->next; //s指向第i个结点 p->next=p->next->next; //第i个结点脱链 Tx=s->data; deletes; //释放第i个结点空间 size--; //结点个数减! returnx; //返回第i个结点的data域值}template<classT>TCircleList<T>::GetData(inti) //取数据元素//取第i个数据元素并由函数返回.参数i的取值范围为:0≤i≤size-1{ if(i<0||i>size-1) { cout<<"参数i越界出错!"<<endl; exit(0); } ListNode<T>*p=Index(i); //p指向第i个结点 returnp->data;}(2)测试主函数文件，Ex2-3.cpp实际运行验证所设计循环单链表类的正确性.//CircleLinkList.cpp:定义控制台应用程序的入口点。#include"stdafx.h"#include<iostream.h>#include<stdlib.h>typedefstruct//结构体StudentType{ longnumber;//学号数据项 charname[10];//姓名数据项 charsex[3];//性别数据项 intage; //年龄数据项}StudentType;#include"CircleLinkList.h"//包含顺序表类intmain(){ CircleList<StudentType>myList; StudentTypex[3]={{2000001,"张三","男",20},{2000002,"李四","男",21},{2000003,"王五","女",22}}; intn=3; StudentTypes; for(inti=0;i<n;i++) //在myList中顺序插入3个元素 myList.Insert(x[i],i); for(inti=0;i<myList.Size();i++) //依次取myList中的元素并显示 { s=myList.GetData(i); cout<<s.number<<""<<<<""<<s.sex<<""<<s.age<<endl; } myList.Delete(0); for(inti=0;i<myList.Size();i++) //依次取myList中的元素并显示 { s=myList.GetData(i); cout<<s.number<<""<<<<""<<s.sex<<""<<s.age<<endl; } return0;}2-21设计一个不带头结点的单链表类，要求：(1)不带头结点单链表类的成员函数包括取数据元素个数、插入、删除、取数据元素.(提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素结点时与在其他位置插入和删除其他位置结点时的不同情况.）(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性.[解]:(1)结点类的定义和实现如下,其实现文件为NoHeadList.htemplate<classT>classNoHeadList; //前视定义,否则友元无法定义template<classT>classListNode //模板类型为T{ friendclassNoHeadList<T>; //定义类LinList<T>为友元private: ListNode<T>*next; //指向下-结点的指针 Tdata; //定义为公有成员方便使用public: //构造函数1,用于构造头结点 ListNode(ListNode<T>*ptrNext=NULL){next=ptrNext;} //构造函数2,用于构造其他结点 ListNode(constT&item,ListNode<T>*ptrNext=NULL){data=item;next=ptrNext;} ~ListNode(void){} //析构函数};//单链表类的定义template<classT>classNoHeadList{private: ListNode<T>*head; //头指针 int size; //当前的数据元素个数 ListNode<T>*Index(inti); //定位public: NoHeadList(void); //构造函数 ~NoHeadList(void); //析构函数 intSize(void)const{returnsize;} //取当前数据元素个数 voidInsert(constT&item,inti); //插入 TDelete(inti); //删除 TGetData(inti); //取数据元素};//单链表类的实现template<classT>NoHeadList<T>::NoHeadList() //构造函数{ head=NULL; //头指针指向头结点 size=0; //size的初值为0}template<classT>NoHeadList<T>::~NoHeadList(void) //析构函数{ ListNode<T>*q; while(head!=NULL) //循环释放结点空间直至初始化状态 { q=head; head=head->next; deleteq; }}template<classT>ListNode<T>*NoHeadList<T>::Index(inti)//定位//返回指向第i个数据元素结点的指针//参数i的取值范围为:-1≤i≤size-1;i=-1时返回头NULL指针{ if(i<-1||i>size-1) { cout<<"参数i越界出错1"<<endl; exit(0); } if(i==-1)returnNULL; //i为-1时返回头指针NULL ListNode<T>*p=head; //p指向第一个数据元素结点 intj=0; //从O开始计数 while(j<i) //寻找第i个结点 { p=p->next; j++; } returnp; //返回第i个结点的指针}template<classT>voidNoHeadList<T>::Insert(constT&item,inti)//插入//在第i个结点后插入一个元素值为item的新结点//参数i的取值范围为:０≤i≤size{ if(i<0||i>size) { cout<<"参数1越界出错!"<<endl; exit(0); } ListNode<T>*p=Index(i-1); //P为指向第i-1个结点的指针 //构造新结点P,P的data域值为item,next域值为p->next if(p==NULL) { ListNode<T>*q=newListNode<T>(item,head); head=q; } else { ListNode<T>*q=newListNode<T>(item,p->next); p->next=q; //新结点插入第i个结点前 } size++; //元素个数加1}template<classT>TNoHeadList<T>::Delete(inti) //删除//删除第i个数据元索并由函数返回.参数土的取值范围为:0≤i≤size-1{ ListNode<T>*p,*q; if(size==0) { cout<<"链表已空无元素可删!"<<endl; exit(0); } if(i<0||i>size-1) { cout<<"参数i越界出错!"<<endl; exit(0); } ListNode<T>*s; p=Index(i-1); //p为指向第i-1个结点指针 if(p==NULL) { q=head; head=head->next; } else { q=p->next; //s指向第i个结点 p->next=p->next->next; //第i个结点脱链 } Tx=q->data; deleteq; //释放第i个结点空间 size--; //结点个数减1 returnx; //返回第i个结点的data域值}template<classT>TNoHeadList<T>::GetData(inti) //取数据元素//取第i个数据元素并由函数返回.参数i的取值范围为:0≤i≤size-1{ if(i<0||i>size-1) { cout<<"参数i越界出错!"<<endl; exit(0); } ListNode<T>*p=Index(i); //p指向第i个结点 returnp->data;}(2)测试主函数文件，Ex2-4.cpp实际运行验证所设计循环单链表类的正确性.#include<iostream.h>#include<stdlib.h>usingnamespacestd;typedefstruct//结构体StudentType{ longnumber;//学号数据项 charname[10];//姓名数据项 charsex[3];//性别数据项 intage; //年龄数据项}StudentType;#include"NoHeadList.h"//包含顺序表类intmain(){ NoHeadList<StudentType>myList; StudentTypex[3]={{2000001,"张三","男",20},{2000002,"李四","男",21},{2000003,"王五","女",22}}; intn=3; StudentTypes; for(inti=0;i<n;i++) //在myList中顺序插入3个元素 myList.Insert(x[i],i); for(inti=0;i<myList.Size();i++) //依次取myList中的元素并显示 { s=myList.GetData(i); cout<<s.number<<""<<<<""<<s.sex<<""<<s.age<<endl; } myList.Delete(0); for(inti=0;i<myList.Size();i++) //依次取myList中的元素并显示 { s=myList.GetData(i); cout<<s.number<<""<<<<""<<s.sex<<""<<s.age<<endl; } return0;}2-22设计一个带头结点的循环双向链表类，要求：(1)带头结点循环双向链表类的成员函数包括：取数据元素个数、插入、删除、取数据元素.(2)设计一个测试主函数，实际运行验证所设计循环双向链表类的正确性.[解]:(1)结点类的定义和实现如下，其实现文件为DoubleList.htemplate<classT>classDoubleList;//前视定义,否则友元无法定义template<classT>classDListNode{ friendclassDoubleList<T>; //定义类DoubleList<T>为友元private: Tdata; //定义为公有成员方便使用 DListNode<T>*pre,*next; //指向下-结点的指针public: //构造函数1,用于构造头结点DListNode(DListNode<T>*ptrPre=NULL,DListNode<T>*ptrNext=NULL):pre(ptrPre),next(ptrNext){}; //构造函数2,用于构造其他结点 DListNode(constT&item,DListNode<T>*ptrPre,DListNode<T>*ptrNext):data(item),pre(ptrPre),next(ptrNext){}; ~DListNode(void){} //析构函数};//双链表类的定义template<classT>classDoubleList{private: DListNode<T>*head; //头指针int size; //当前的数据元素个数 DListNode<T>*Index(inti); //定位public: DoubleList(void); //构造函数 ~DoubleList(void); //析构函数 intSize(void)const{returnsize;}; //取当前数据元素个数 voidInsert(constT&item,inti); //插入 TDelete(inti); //删除 TGetData(inti); //取数据元素};//双链表类的实现template<classT>DoubleList<T>::DoubleList() //构造函数{ head=newDListNode<T>(); //头指针指向头结点head->pre=head;head->next=head; size=0; //size的初值为0}template<classT>DoubleList<T>::~DoubleList(void) //析构函数{ DListNode<T>*p,*q; p=head; //P指向第一个结点 while(p->next!=head) //循环释放结点空间直至初始化状态 { q=p->next;; p->next=q->next; deleteq; } deletehead;}template<classT>DListNode<T>*DoubleList<T>::Index(inti)//定位//返回指向第i个数据元素结点的指针//参数i的取值范围为;-l≤i≤size-1;i=-1时返回头指针{ if(i<-1||i>size-1) { cout<<"参数i越界出错1"<<endl; exit(0); } if(i==-1)returnhead; //i为-1时返回头指针head DListNode<T>*p=head->next; //p指向第一个数据元素结点 intj=0; //从O开始计数 while(p!=NULL&&j<i) //寻找第i个结点 { p=p->next; j++; } returnp; //返回第i个结点的指针}template<classT>voidDoubleList<T>::Insert(constT&item,inti)//插入//在第i个结点后插入一个元素值为item的新结点//参数i的取值范围为;０≤i≤size{ if(i<0||i>size) { cout<<"参数1越界出错!"<<endl; exit(0); } DListNode<T>*p=Index(i-1); //P为指向第i个结点的指针 //构造新结点q,q的data域值为item,pre域值为p->pre,next域值为p DListNode<T>*q=newDListNode<T>(item,p->pre,p); q->pre->next=q; //新结点插入第i个结点前 q->next->pre=q; size++; //元素个数加1}template<classT>TDoubleList<T>::Delete(inti) //删除//删除第i个数据元索并由函数返回.参数土的取值范围为;0≤i≤size-1{ if(size==0) { cout<<"链表已空无元素可删!"<<endl; exit(0); } if(i<0||i>size-1) { cout<<"参数i越界出错!"<<endl; exit(0); } DListNode<T>*s,*p=Index(i); //p为指向第i个结点指针 p->pre->next=p->next; //p前驱的后继指向第i+1个结点 p->next->pre=p->pre; //p后继的前驱指向第i-1个结点 Tx=p->data; deletep; //释放第i个结点空间 size--; //结点个数减1 returnx; //返回第i个结点的data域值}template<classT>TDoubleList<T>::GetData(inti) //取数据元素//取第i个数据元素并由函数返回.参数i的取值范围为;0≤i≤size-1{ if(i<0||i>size-1) { cout<<"参数i越界出错!"<<endl; exit(0); }; DListNode<T>*p=Index(i); //p指向第i个结点 returnp->data;}(2)测试主函数文件，Ex2-5.cpp实际运行验证所设计循环单链表类的正确性.//DoubleLinkList.cpp:定义控制台应用程序的入口点。#include"stdafx.h"#include<iostream>#include<stdlib.h>usingnamespacestd;typedefstruct//结构体StudentType{ longnumber;//学号数据项 charname[10];//姓名数据项 charsex[3];//性别数据项 intage; //年龄数据项}StudentType;#include"DbLinkList.h"//包含顺序表类intmain(){ DoubleList<StudentType>myList; StudentTypex[3]={{2000001,"张三","男",20},{2000002,"李四","男",21},{2000003,"王五","女",22}}; intn=3; StudentTypes; for(inti=0;i<n;i++) //在myList中顺序插入3个元素 myList.Insert(x[i],i); for(inti=0;i<myList.Size();i++) //依次取myList中的元素并显示 { s=myList.GetData(i); cout<<s.number<<""<<<<""<<s.sex<<""<<s.age<<endl; } myList.Delete(0); for(inti=0;i<myList.Size();i++) //依次取myList中的元素并显示 { s=myList.GetData(i); cout<<s.number<<""<<<<""<<s.sex<<""<<s.age<<endl; } return0;}*2-23约瑟夫环问题.问题描述：设编号为1,2,…，n(n>0)个人按顺时针方向围坐-圈，每人持有一个正整数密码.开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数.报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止.要求设计一个程序模拟此过程，并给出出列人的编号序列.测试数据：n=7,7个人的密码依次为3,1,7,2,4,8,4初始报数上限值m=20[解]:本题目可用多种方法求解。这里介绍一个利用数组的求解方法。

typedefstruct{ intNo;//编号 intcode;//密码}INFO;typedefINFOEntryType;voidJoseph(intcode[],intn){ LINK_LISTpeople; NODE*position,*pre;//position指向当前报数的结点 if(InitList(&people)==ERROR)exitERROR;//初始化链表people for(i=1;i<=n;i++)//以n个人的信息为数据域内容向链表插入n个结点 if(ListInsert(&people,i,code[i-1])==ERROR)exitERROR; position=people.head; //让position指向最后一个结点，以便报数从第一个开始 while(position->next!=people.head) position=NextElem(people,position); scanf("%d",&m);//输入最初的m for(i=1;i<n;i++){ count=0;//报数处理 do{