《第2章线性表及其应用》习题解答

第2章线性表及其应用-.13.-第2章线性表及其应用本章学习要点◆掌握线性表的逻辑结构及相关概念。◆掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。◆熟练掌握顺序表和链表上各种基本操作的实现过程。◆灵活运用顺序表和链表的特点解决实际应用问题。线性表（LinearList）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本操作及其算法实现，最后给出线性表的应用实例。2.1线性表的定义和基本运算2.1.1线性表的定义线性表是n(n≥0)个同类型数据元素（记录或结点）的有限序列：a0,a1,a2,…,an-1。记为：Ln=(a0,a1,a2,…,an-1)。其中：a0是开始结点，an-1是终端结点，ak是ak+1的直接前驱结点，而ak+1是ak的直接后继结点(k=0,1,2,…,n-2)；终端结点an-1没有后继结点，开始结点a0没有前驱结点；元素ai(i=0,1,2…,n-1)在表中的位置为i+1；元素的个数n称为线性表L的长度，长度为零的线性表叫空表。需要说明的是：在C/C++语言中，数组元素的下标是从0开始的，具有n个数据元素的数组A的所有元素为A[0],A[1],…,A[n-1]。在线性表的定义中，第i个元素的下标为i-1,即元素的位置等于其下标加1。日常生活中，线性表的例子很多：【例2.1】L10=（1，3，5，7，9，2，4，6，8，10）是一个线性表。其中的数据元素是整数，该线性表的长度为10。按表中的排列顺序，元素1是第一个元素没有前驱，元素10是最后一个元素没有后继。【例2.2】L36=（0,1,2,3,4,5,6,7,8,9,A,B,C,D,…,X,Y,Z）是一个线性表。其中的数据元素是所有数字字符和所有大写字母字符，线性表的长度为36。按表中的排列顺序，元素‘0’是第一个元素没有前驱，元素‘Z’是最后一个元素没有后继。【例2.3】由图2.1所示的学生基本情况表L7也是一个线性表。线性表中的元素是由5个数据项组成的纪录，表的长度为7。《数据结构与算法》-.14.-2.1.2线性表的基本操作线性表的基本运算主要有以下几种：（1）初始化InitList（&L）：构造一个空线性表L的运算。（2）提取GetElem(L,i,&e)：提取表L中第i个元素的值到e的运算。（3）修改SetElem(&L,i,e)：修改表L中第i个元素的值为e的运算。（4）查找LocateElem(L,e)：查找表L中第一个值与e相同的元素的位置。（5）插入InsertList(&L,i,e)：将e插入到表L中的第i个位置。（6）删除DeleteList(&L,i,&e)：删除表L中的第i元素，并用e返回该元素的值。（7）求表长Length(L):返回线性表L的长度。（8）遍历TraverseList(L)：依次输出L中每个元素的值。在线性表的其它操作中，有些操作可以通过调用基本操作来实现，有些操作比如线性表的排序和归并等操作的实现将在以后的章节中进行。2.2线性表的顺序存储表示与实现2.2.1线性表的顺序存储1．顺序表概念一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方式是将线性表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。设顺序表110,,,nnaaaL中元素0a的首地址为)(0aLOC，每个元素需要占用的字节数为l，则表中任一元素ia的存储位置)(iaLOC可用下面的公式算出：)1,,2,1,0()()(0niliaLOCaLOCi顺序表中各元素在内存中所占的位置如图2.2所示。2．顺序表的结构定义第2章线性表及其应用-.15.-顺序表的存储结构和一维数组的存储结构极为相近；但是由于在线性表中允许执行插入和删除等操作，也就是说一个线性表的长度是可变的，为适应这种情况在C++语言中用以下结构类型来表示顺序表。typedefintElemType;//为了方便上机调试程序，本章假定数据元素的类型为整型constintMAXLEN=100;//定义顺序表存储空间大小的初始分配常量constintINCSIZE=50;//定义顺序表存储空间的扩充常量值structSqList//定义顺序表的结构类型为SqList{ElemType*elem;//存储空间的基址intlength;//线性表的长度intlistsize;//当前表的存储容量intincsize;//一次增补的容量值};在以上结构表示下，许多关于线性表的运算（如存、取、求线性表的长度和置表空等操作）极易实现。以下主要讨论关于顺序表的插入、删除、查找和遍历等操作。2.2.2顺序表中基本操作的实现1．初始化操作InitList_Sq(&L)该操作的功能是构造一个空线性顺序表L。算法思想（1）在堆空间中为线性表动态分配一块连续的存储单元，返回首地址到elem;（2）置线性表的长度值length为0;（3）置表的当前容量listsize为动态分配时的大小；（4）置容量扩充值incsize的大小为INCSIZE。线性表L的初始化存储结构如图2.3所示。算法实现voidInitList_Sq(SqList&L,intmaxlength=MAXLEN,intincsize=INCSIZE){L.elem=newElemType[maxlength];//动态分配一个长度为maxlength的连续存储空间，类型为ElemType，返回首地址到L.elemL.length=0;L.listsize=maxlength;L.incsize=incsize;}《数据结构与算法》-.16.-2．提取操作GetElem_Sq(L,i,&e)该操作将顺序表L中第i个元素的值赋值到e中，如果提取成功返回1否则返回0。算法实现intGetElem_Sq(SqListL,inti,ElemType&e){if(i1||iL.length)return0;//如果位置i不合理时返回0值else{e=L.elem[i-1];//通过参数e得到第i个元素的值return1;}}3．修改操作SetElem_Sq(&L,i,e)修改操作将线性表L中第i个元素的值修改为e，如果修改成功返回1否则返回0。算法实现intSetElem_Sq(SqList&L,inti,ElemTypee){if(i1||iL.length)return0;else{L.elem[i-1]=e;return1;}}4．查找操作LocateElem_Sq(L,e)查找操作的功能是查找顺序表L中第一个值与e相同的元素的位置，如果查找成功返回1查找失败返回0。算法实现intLocateElem_Sq(SqListL,ElemTypee){inti=0;while(iL.length&&L.elem[i]!=e)i++;if(iL.length)returni+1;elsereturn0;}算法分析查找运算的基本操作为表中元素与数据e的比较。假定表的长度为n,每个位置找到的机会都是相同的，即第i个位置找到的概率为nip1，那么查找操作的平均比较次数为：211nniiip。查找的时间复杂度是按最坏的情况来考虑，即查找的是最后一个元素或找第2章线性表及其应用-.17.-不到该元素，其比较次数为n次,所以查找的时间复杂度为：)()(nnT。5．插入操作InsertList_Sq(&L,i,e)插入操作的功能是将元素e插入到顺序表L中L.elem的第i个位置，同时修改L的长度。如果插入成功返回1，不成功返回0。算法思想(1)先编写函数IncSize(&L),其功能是将顺序表L的最大存储量增加L.incsize个元素的空间；(2)如果插入的位置i不合理返回0，表示插入不成功；(3)如果当前线性表的长度已经达到最大容量值L.listsize，则调用函数IncSize(&L)扩充容量；(4)将L.elem中第i个以后的所有元素都依次向后移动一个位置，为第i个元素的插入留出一个空位；(5)置L中第i个元素的值为e；(6)将表的长度加1；(7)返回值1表示插入成功。算法实现voidIncSize(SqList&L){//该函数的功能是另分配一个存储区并将L的最大存储量增加L.incsize个记录的空间ElemType*a=newElemType[L.listsize+L.incsize];for(inti=0;iL.length;i++)a[i]=L.elem[i];//将L.elem中的元素复制到数组a中delete[]L.elem;//收回L.elem所占空间L.elem=a;//让L.elem指向aL.listsize+=L.incsize;//修改最大存储空间}intInsertList_Sq(SqList&L,inti,ElemTypee){intk;if(i1||iL.length+1)return0;//插入位置不合理时返回0值if(L.length==L.listsize)IncSize(L);for(k=L.length,i--;ki;k--)L.elem[k]=L.elem[k-1];//为第i个元素的插入留出一个空位L.elem[i]=e;L.length++;//修改长度return1;}算法分析从以上算法可见，在不考虑扩容的情况下，插入运算的时间主要花费在元素的向后移动《数据结构与算法》-.18.-上。假定表的长度为n,每个位置插入的机会都是相同的，即第i个位置插入的概率为11nip，那么插入操作平均移动元素的次数为：211)1(nniiinp。插入操作的时间复杂度是按最坏的情况考虑，即插入到表中开始的位置，所以元素的移动次数为n次,时间复杂度为)()(nnT。6．删除操作DeleteList_Sq(&L,i,&e)删除操作的功能是删除顺序表L中的第i元素，并返回该元素的值到e中。如果操作成功返回1，否则返回0。算法思想（1）如果删除的位置i不合理返回0，表示删除操作不成功；（2）置e的值为L中第i个元素的值；（3）将L中第i个以后的所有元素都依次向前移动一个位置；（4）将表的长度减1；（5）返回值1表示删除成功。算法实现intDeleteList_Sq(SqList&L,inti,ElemType&e){if(i1||iL.length)return0;//如果删除的位置i不合理返回0e=L.elem[i-1];//置e的值为L中第i个元素的值while(iL.length)//将L中第i个以后的所有元素都依次向前移动一个位置{L.elem[i-1]=L.elem[i];i++;}L.length--;//将表的长度减1return1;}算法分析删除运算的时间主要花费在元素的向前移动上。假定表的长度为n,每个位置删除的机会都是相同的，即第i个位置删除的概率为nip1，那么删除操作平均移动元素的次数为：211)(nniiinp。删除操作的时间复杂度是按最坏的情况考虑，即删除表中第一个元素，此时的元素移动次数为n-1次,时间复杂度为：)()(nnT。7．求表长的操作Length_Sq(L)该操作的功能是返回顺序表L的长度，如果当前L是空表则返回0。算法实现第2章线性表及其应用-.19.-intLength_Sq(SqListL){returnL.length;}8．遍历操作TraverseList_Sq(L)该操作的功能是顺序显示输出顺序表L中每个元素的值。算法实现#include“iostream.h”//将C++的输入输出流库头文件包含进来voidTraverseList_Sq(SqListL){if(!L