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

'第2章线性表及其应用第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。-.53.- 第2章线性表及其应用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．顺序表概念一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方式是将线性表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。设顺序表中元素的首地址为，每个元素需要占用的字节数为，则表中任一元素的存储位置可用下面的公式算出：顺序表中各元素在内存中所占的位置如图2.2所示。2．顺序表的结构定义-.53.- 第2章线性表及其应用顺序表的存储结构和一维数组的存储结构极为相近；但是由于在线性表中允许执行插入和删除等操作，也就是说一个线性表的长度是可变的，为适应这种情况在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;}-.53.- 第2章线性表及其应用2．提取操作GetElem_Sq(L,i,&e)该操作将顺序表L中第i个元素的值赋值到e中，如果提取成功返回1否则返回0。算法实现intGetElem_Sq(SqListL,inti,ElemType&e){if(i<1||i>L.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(i<1||i>L.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+1)return0;//插入位置不合理时返回0值if(L.length==L.listsize)IncSize(L);for(k=L.length,i--;k>i;k--)L.elem[k]=L.elem[k-1];//为第i个元素的插入留出一个空位L.elem[i]=e;L.length++;//修改长度return1;}算法分析从以上算法可见，在不考虑扩容的情况下，插入运算的时间主要花费在元素的向后移动上。假定表的长度为n,每个位置插入的机会都是相同的，即第i个位置插入的概率为-.53.- 第2章线性表及其应用，那么插入操作平均移动元素的次数为：。插入操作的时间复杂度是按最坏的情况考虑，即插入到表中开始的位置，所以元素的移动次数为n次,时间复杂度为。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(i<1||i>L.length)return0;//如果删除的位置i不合理返回0e=L.elem[i-1];//置e的值为L中第i个元素的值while(i>n;cout<<"输入"<>e;InsertList_Sq(L,i,e);}}2．综合演示主程序voidmain_Sq(){SqListL;ElemTypee;inti,num;Create_Sq(L);cout<<"顺序表的初始数据为:n";-.53.- 第2章线性表及其应用TraverseList_Sq(L);while(1){cout<<"1--提取第i个元素，2--修改第i个元素的值，3--插入第i个元素n";cout<<"4--删除第i个元素的值，5--查找元素e的位置，6--显示当前表的内容n";cout<<"7--退出演示程序：";cout<<”输入选择:”;cin>>num;switch(num){case1:cout<<"输入位置i:";cin>>i;if(GetElem_Sq(L,i,e))cout<<"第"<>i>>e;if(!SetElem_Sq(L,i,e))cout<<"输入的位置不合理,修改不成功n";break;case3:cout<<"输入插入位置i和值e:";cin>>i>>e;if(!InsertList_Sq(L,i,e))cout<<"插入的位置不合理,操作不成功n";break;case4:cout<<"输入删除位置i:";cin>>i;if(!DeleteList_Sq(L,i,e))cout<<"删除位置不合理,删除操作失败n";elsecout<<"位置:"<>e;if(!(i=LocateElem_Sq(L,e)))cout<<"查找不成功n";elsecout<<"表中位置:"<>n>>m;//输入n、m的值InitList_Sq(L);//初始化Lfor(i=1;i<=n;i++)//置第i个人的编号为iInsertList_Sq(L,i,i);cout<<"所求编号序列为:n";k=0;for(i=0;inext=NULL;//置头结点的指针域为空}2．提取操作GetElem_L(L,i,&e)提取操作的功能为提取链表L中第i个结点的数据域（data）的值到e中。如果提取成功（即位置i合理）返回1否则返回0。算法实现intGetElem_L(LinkListL,inti,ElemType&e){intk;LinkListp=L->next;for(k=1;knext;if(i<1||!p)return0;//位置i不合理返回0e=p->data;return1;}3．修改操作SetElem_L(&L,i,e)修改操作修改单链表L中第i结点数据域data的值为e的值。如果修改成功（即位置i合理）返回1否则返回0。算法实现intSetElem_L(LinkList&L,inti,ElemTypee){intk;LinkListp=L->next;for(k=1;knext;//取第i个结点的指针pif(i<1||!p)return0;//位置i不合理返回0p->data=e;return1;}4．查找操作LocateElem_L(L,e)该操作查找单链表L中第一个数据域的值与e相同的结点的位置。如果查找成功返回该结点的指针（地址），否则返回空指针（NULL）。-.53.- 第2章线性表及其应用算法实现LinkListLocateElem_L(LinkListL,ElemTypee){LinkListp=L->next;while(p&&p->data!=e)p=p->next;//查找第一个值相同的结点returnp;}5．插入操作InsertList_L(&L,i,e)插入操作的功能是，在单链表L的第i个结点前面插入一个数据域的值为e的结点。如果插入成功返回1，否则返回0。算法思想（1）在单链表L中找到第i-1个结点的指针p；（2）如果查找不成功（即位置i不合理）返回0；（3）在堆空间中分配新的结点q；（4）置q的数据域的值为e；（5）将q插入到L中p->next之前、p之后。用语句q->next=p->next;和p->next=q;实现。（6）返回1表示插入成功。操作结果如图2.6所示。算法实现intInsertList_L(LinkList&L,inti,ElemTypee){LinkListp=L,q;intk;for(k=1;knext;k++)p=p->next;//查找L中第i个结点的直接前驱结点的指针pif(i<1||kdata=e;//置q中数据域的值为eq->next=p->next;//将q插入L中第i个结点之前p->next=q;return1;}6．删除操作DeleteList_L(&L,i,&e)操作的功能是将单链表L中第i个结点的值赋值给e，并将该结点从链表中删除。如果操作成功返回1，否则返回0。-.53.- 第2章线性表及其应用算法思想（1）在单链表L中找到第i-1个结点的指针p；（2）如果查找不成功（即位置i不合理）返回0；（3）置q的值为p->next（4）置e的值为q中数据域的值；（5）将结点q从链表中摘除。用语句p->next=q->next;实现。（6）释放结点q所占的堆空间并返回1表示删除成功。操作结果如图2.7(a)、2.7(b)、2.7(c)所示。算法实现intDeleteList_L(LinkList&L,inti,ElemType&e){LinkListp=L,q;intk;for(k=1;knext;k++)p=p->next;if(i<1||!p->next)return0;q=p->next;e=q->data;p->next=q->next;deleteq;return1;}7．求表长操作Length_L(L)该操作返回链表L的长度，如果L为空链表则返回0。算法实现intLength_L(LinkListL){inti=0;LinkListp=L->next;while(p){i++;p=p->next;}returni;}8．遍历操作TraverseList_L(L)-.53.- 第2章线性表及其应用该操作依次显示输出L中每个结点中数据域的值。算法实现voidTraverseList_L(LinkListL){LinkListp=L->next;if(!p)cout<<"链表为空表.n";else{cout<<"链表中的数据有:n";while(p){cout<data<<"";p=p->next;}cout<>n;cout<<"输入"<>e;InsertList_L(L,i,e);}}2．单链表的综合演示主程序voidmain_L(){LinkListL;ElemTypee;inti,num;Create_L(L);TraverseList_L(L);while(1){cout<<"1-提取第i个结点的值，2-修改第i个结点的值，3-插入第i个结点n";-.53.- 第2章线性表及其应用cout<<"4-删除第i个结点，5-查找第一个数据为e的结点，6-显示当前链表的内容n";cout<<"7-退出演示程序n";cin>>num;switch(num){case1:cout<<"输入位置i:";cin>>i;if(GetElem_L(L,i,e))cout<<"第"<>i>>e;if(!SetElem_L(L,i,e))cout<<"输入的位置不合理,修改不成功n";break;case3:cout<<"输入插入位置i和值e:";cin>>i>>e;if(!InsertList_L(L,i,e))cout<<"插入的位置不合理,操作不成功n";break;case4:cout<<"输入删除位置i:";cin>>i;if(!DeleteList_L(L,i,e))cout<<"删除位置不合理,操作失败n";elsecout<<"第"<>e;if(!LocateElem_L(L,e))cout<<"查找不成功n";elsecout<<"数据为"<next==NULL，而在循环链表中空表的条件为h->next==h。（2）指向链尾结点的指针p在单链表中满足的条件是p->next==NULL,而在循环链表中满足的条件是p->next==h.2.5.2双向链表在有n个结点的单链表或单向循环链表中，求一个结点的直接后继结点的时间复杂度为O(1)，而求它的直接前驱结点的时间复杂度均为O(n)。其原因是在结点中只有一个指向直接后继结点的指针，而不含指向直接前驱结点的指针信息。为此给出以下双向链表的概念。1．双向链表双向链表中，结点的结构在单链表结点结构(data,next)的基础上再增加一个指向直接前驱结点的指针域prior。带有头结点的双向链表的结构如图2.9所示。在C++语言中用以下结构类型来表示双向链表中一个结点的结构类型：typedefstructDNode{ElemTypedata;DNode*next,*prior;}*DLinkList;其中，DNode为双向链表的结点结构类型，DLinkList为指向该结点的指针类型。2．双向循环链表与单向循环链表类似，在双向链表中，使头结点的prior指针指向尾结点且使尾结点的next指针指向头结点，这样就构成一个双向循环链表。带有头结点的双向循环链表的结构如图2.10所示。双向链表的特点是可以直接求得链表中任意一个结点的直接前驱结点和直接后继结点。但是由于增加了一个指针域，相对于单向链表而言，其存储密度有所降低。2.5.3静态链表1．静态链表的概念-.53.- 第2章线性表及其应用在有些计算机高级语言中没有设置指针类型，所以不能直接使用线性表的链式存储结构。在这样的语言环境中可借用一维数组来描述线性链表的存储结构，即静态链表存储方式。在C++语言中静态链表的结构类型定义如下：constintMAXSIZE=1000;//链表的最大长度typedefstructSNode{ElemTypedata;intcur;}SLinkList[MAXSIZE];其中，SNode为静态链表的结点类型（相当于链表的结点类型），数据域data中存放元素的数据，下标（游标）域cur中存放下一个元素（直接后继）的下标；SLinkList为静态链表存储空间Space的定义类型（相当于链表中堆空间的类型）。2．静态链表的存储域（1）静态存储空间Space的初始化InitSpace_S(&Space)该操作将静态链表的存储域Space设置成一个带头结点的空闲“单循环链表”。其中以第一个元素a0作为头结点，该结点的cur<=1,a1的cur<=2,…,an-1的cur<=0(n为最大存储长度）。其存储结构如图2.10（a）所示。存储空间初始化算法如下：voidInitSpace_S(SLinkList&Space){intn=MAXSIZE,i;for(i=0;i>n;cout<<"输入"<>e;if(!InsertList_S(SS,p,i+1,e)){cout<<"空间已满!n";break;}}cout<<"链表的初始内容为:n";TraverseList_S(SS,p);cout<<"1-在第i个结点前插入一个结点,2-删除第i个结点n";cout<<"3-显示当前链表的内容,4-显示可用空间长度n";cout<<"5-退出演示程序.";while(1){cout<<“输入选择:”;cin>>num;switch(num){case1:cout<<"输入插入位置i和值e:";cin>>i>>e;if(!InsertList_S(SS,p,i,e))cout<<"插入的位置不合理,或空间已满。n";break;case2:cout<<"输入删除位置i:";cin>>i;if(!DeleteList_S(SS,p,i,e))cout<<"删除位置不合理,或链表已空n";elsecout<<"第"<>n>>m;p=L;for(i=1;i<=n;i++)//建立有n个结点的单链表并且依次赋于相应的编号值-.53.- 第2章线性表及其应用{p->next=newNode;p=p->next;p->data=i;}p->next=NULL;//最后一个结点的指针域为NULLp=L;cout<<"所求编号序列为:n";for(i=0;inext)p=L;p=p->next;}if(!p->next)p=L;q=p->next;//以下语句实现：删除结点q并输出其编号的值p->next=q->next;cout<data<<"";deleteq;}cout<>n>>m;//输入n、m的值InitList_L(L);//初始化L为空链表for(i=1;i<=n;i++)InsertList_L(L,i,i);//置第i个人的编号为icout<<"所求编号序列为:n";for(k=0,i=n;i>0;i--)//i为当前的链表长度{k=(k+m-1)%i;//计算出圈人结点在链表L中的前驱结点位置kDeleteList_L(L,k+1,e);//删除第k+1个结点并提取其编号到e中cout<next||!L->next->next)return;LinkListp=L->next,q=p->next,r;p->next=NULL;while(r=q->next){q->next=p;p=q;q=r;}q->next=p;L->next=q;}算法分析设链表的长度为n，由算法设计过程可知该算法的时间复杂度为O(n)，空间复杂度为O(1)。【例2.8】现有两个递增有序的带有头结点的单链表L1、L2，要求将L2中的结点归并到L1中并保持L1仍然有序，并且在归并过程中不另设结点。算法思想总的想法是，从前往后将L2中的结点逐个插入到L1中，如果在此过程中有一个结点插入到L1的末尾，则将L2中剩余的部分链接到L1的尾部即可。算法实现voidMerger_L(LinkList&L1,LinkList&L2){LinkListp=L1,q=L2->next,r;-.53.- 第2章线性表及其应用L2->next=NULL;while(p->next&&q){if(p->next->datadata)p=p->next;else{r=q;q=q->next;r->next=p->next;p->next=r;p=r;}}if(q)p->next=q;}算法分析设L1的长度为m，L2的长度为n。算法的时间复杂度为O(m+n)，空间复杂度为O(1)。【例2.9】用线性表表示一元多项式并实现多项式的加法、减法和乘法运算。1．多项式的线性表示法在数学上，一个n次多项式Pn(x)可按升幂写成：，可见，由其n+1个系数组成的系数向量唯一确定。因此，在计算机中一个n次多项式可用一个长度为n+1的线性表P来表示，其中表示多项式中的系数。设多项式的系数向量为且mnext=NULL;p->data.expn=-1;}3．多项式加单项式的操作（poly<=poly+data）算法思想计算Poly+data的方法是：从前往后将poly->data.expn项逐个取出并与data.expn项进行比较，将其插入到poly中的适当位置（按指数expn由小到大）。如果在poly中存在相同的指数域（expn），则求相应的系数域（coef）的和，如果和为零，则删除掉poly中相应的结点。算法实现voidInsertAddPData(Poly&poly,PDatadata){Polyp=poly,q;while(p->next&&p->next->data.expnnext;if(!p->next||p->next->data.expn>data.expn)//插入一项到结点p的后面{q=newPNode;q->data=data;q->next=p->next;p->next=q;-.53.- 第2章线性表及其应用}else//与对应项的系数相加{p->next->data.coef+=data.coef;if(fabs(p->next->data.coef)<1e-8)//删除系数为零的项{q=p->next;p->next=q->next;deleteq;}}}4．按序创建一个多项式voidCreatePoly(Poly&poly){PDatadata;InitPoly(poly);cout<<"输入多项式的系数和相应的指数(expn=-1结束):n";while(1){cin>>data.coef>>data.expn;if(data.coef==0||data.expn<0)break;InsertAddPData(poly,data);}}5．按指数形式显示一个多项式voidDispPoly(Polypoly){Polyp=poly;if(!p->next)cout<<"当前为一个0多项式:P=0n";else{cout<<"P=";while(p->next){p=p->next;if(p->data.coef>0)cout<<"+";cout<data.coef<<"X^"<data.expn;}cout<next;while(pp){InsertAddPData(p,pp->data);pp=pp->next;}}7．多项式减多项式操作（p<=p-p1）voidSubPoly(Poly&p,Polyp1){Polypp=p1->next;PDatadata;while(pp){data=pp->data;data.coef*=-1;InsertAddPData(p,data);pp=pp->next;}}8．多项式乘以多项式操作（p<=p1×p2）（1）操作：p<=p+p1×dvoidMulData(Poly&p,Polyp1,PDatad){PDatadd;Polyh=p1->next;while(h){dd=h->data;dd.coef*=d.coef;dd.expn+=d.expn;InsertAddPData(p,dd);h=h->next;}}（2）操作：返回p×p1的值PolyMulPoly(Polyp,Polyp1){Polypm,pp=p1->next;-.53.- 第2章线性表及其应用InitPoly(pm);while(pp){MulData(pm,p,pp->data);pp=pp->next;}returnpm;}9．多项式操作的综合演示主程序-.53.-第2章线性表及其应用voidmain(){Polyp,p1,p2,p3,p4;cout<<"createp:n";CreatePoly(p);DispPoly(p);cout<<"createp1:n";CreatePoly(p1);DispPoly(p1);/////p2<=p+p1//////////InitPoly(p2);AddPoly(p2,p);AddPoly(p2,p1);cout<<"p2=p+p1:n";DispPoly(p2);/////p3<=p-p1//////////InitPoly(p3);AddPoly(p3,p);SubPoly(p3,p1);cout<<"p3=p-p1:n";DispPoly(p3);/////p4<=p*p1/////////p4=MulPoly(p,p1);cout<<"p4=p*p1:n";DispPoly(p4);}程序运行结果为：createp:输入多项式的系数和相应的指数(expn=-1结束):2158-3.11100P=+2X^1+5X^8-3.1X^11createp1:输入多项式的系数和相应的指数(expn=-1结束):70-5811900P=+7X^0-5X^8+11X^9p2=p+p1:P=+7X^0+2X^1+11X^9-3.1X^11p3=p-p1:P=-7X^0+2X^1+10X^8-11X^9-3.1X^11p4=p*p1:P=+14X^1+35X^8-10X^9+22X^10-21.7X^11-25X^16+55X^17+15.5X^19-34.1X^20-.53.-第2章线性表及其应用2.7习题一、简答题1．分别从线性表的存储密度、访问操作、修改和删除操作，这三个方面讨论其顺序存储和链式存储各有哪些优缺点？2．描述链表中，头结点、头指针、首元结点（第一个元素结点）三个概念的区别。3．简述在单链表中设置头结点的作用（至少说出两条好处）。4．在单链表、单循环链表、双链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除掉？若可以，其时间复杂度各是多少？5．画出执行下列各语句后各指针及链表的示意图。L=newLNode;P=L;-.53.- 第2章线性表及其应用for(i=1;i<=4;i++){P->next=newLNode;P=P->next;P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++)Del_LinkList(L,i);6．间述以下算法的功能。intFunc(LinkList&L){//L是无表头结点的单链表if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;return(1);}elsereturn(0);}二、填空题1．对于线性表的两种基本存储结构，如果表中元素的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度提取或修改线性表中的元素，应该选用（）存储结构。2．在长度为n的顺序表中插入或删除一个元素，分别需要平均移动（）个元素，执行以上操作时，移动元素的具体个数与（）有关。3．顺序表中逻辑上相邻的数据元素的物理位置（）紧相邻。单链表中逻辑上相邻的数据元素的物理位置（）紧相邻。4．如果系统语言不支持指针类型的变量，并且在元素总数变化不大的情况下，要求以最快的速度对线性表执行插入和删除操作，那么线性表应该选用（）存储结构。5．已知L是带头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试从下面提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是（）。b.删除P结点的直接前驱结点的语句序列是（）。c.删除P结点的语句序列是（）。d.删除首元结点的语句序列是（）。e.删除尾元结点的语句序列是（）。⑴P=P->next;⑵P->next=P;⑶P->next=P->nexe->next;⑷P=P->next->next;⑸while(P!=NULL)P=P->next;⑹while(Q->next!=NULL){P=Q;Q=Q->next;}⑺while(P->next!=Q)P=P->next;⑻while(P->next->next!=Q)P=P->next;⑼while(P->next->next!=NULL)P=P->next;-.53.- 第2章线性表及其应用⑽Q=P;⑾Q=P->next;⑿P=L;⒀L=L->next;⒁deleteQ;三、解答题1．编写一函数，在线性顺序表L中求出最大元素以及该元素在表中的位置（假设L中的元素不重复）。2．编程实现，逆置顺序表L中的所有元素（假设L中的元素为整数），并求出所用算法中基本操作的频度。3．编程实现，将一个顺序表A（假设A中的元素为整数）分拆成两个顺序表B、C，使A中大于等于0的元素存放到B中，小于0的元素存放到C中。4．编写一函数，将两个递增有序的顺序表A和B归并成一个顺序表C，要求C是按元素值不减有序排列的（允许C中有相同值的元素）。5．编程实现，求单链表L中的最大元素，并且删除该元素所在的结点。要求算法中基本操作的次数越少越好。6．试编写一程序，将带有头结点的单循环链表逆置。7．已知线性表A中的数据元素按照值非递减有序。编写一个算法，将元素e插入到线性表A中适当位置并仍然保持A有序。试分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。8．在线性表L中可能有相同的元素。试设计一个算法删除表中所有多余的元素（相同元素仅保留第一个），使删除后表中的元素各不相同。分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。9．所谓约瑟夫（Josephu）问题是：设有n个人围成一圈并依次进行编号1，2，3，……，n。从某个位置i上的人开始报数，数到m的人出列。下一个人（第m+1个）又从1开始报数，再数到m的人又出列，依次重复下去，直到最后一个人出列为止。按照出列的先后可得一新的序列。试用循环链表作为存储结构，编出求解这一问题的程序。10．在本章[例2.9]（1）的基础上，编出实现两个多项式和相乘的程序。其中，每个多项式都用单链表表示。2.8上机实验本章上机实验的主要目的在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用为重点内容。实验题目约瑟夫(Joseph)环【问题描述】约瑟夫(Joseph)问题的一种描述是：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每人有一个密码（正整数）。首先输入一个整数m，从第一个人开始报数1,2,3,…，报到m时停止报数。让报m的人出圈，显示输出该人的密码，并将该密码作为新的m值-.53.- 第2章线性表及其应用，从该位置顺时针方向上的下一个人开始重新从1开始报数，如此下去，直到所有人全部出圈为止。设计一个程序模拟该过程。【基本要求】（1）用顺序存储结构模拟约瑟夫问题，按照出圈的顺序依次输出每人的编号和密码；（2）利用单向循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人的编号和密码；（3）用静态循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人原来的编号和密码。【测试数据】m的初值为20，n=7，7个人的密码依次为：3,1,7,2,4,8,4，首先m的值为6，正确测试结果的编号序列为：6,1,4,7,2,3,5。【实现提示】程序运行后，首先要求用户输入人数n和报数上限的初始值m，然后依次读入n个人的密码。此题对于单向循环链表存储结构不需要“头结点”，并注意空表和非空表的判定。第2章、部分习题参考答案一、简答题1．分别从线性表的存储密度、访问操作、插入（修改）和删除操作，这三个方面讨论其顺序存储和链式存储各有哪些优缺点？（1）存储密度：相对于顺序存储而言，链表中的一个结点比顺序表中的一个记录要多一个指针存储空间，所以通常情况下，链表的存储密度比顺序表的存储密度低。但是，如果顺序表的最大长度远大于实际的记录数时其存储密度将会大大降低。另一方面，顺序表要求较大的连续存储空间，这种分配方法会使系统空间中产生许多不可利用的空闲碎块，降低了空间资源的利用率。而链表中的结点在内存中不要求连续存放。（2）访问操作：顺序表中的元素存储在一个连续的地址空间中，可以对表中的元素进行随机访问。由于链式存储结构的特点，不能随机访问链表中的每一个结点，只能从链表的头指针开始逐个向后访问。（3）插入和删除操作：对顺序表进行插入或删除操作时，往往需要向后或向前移动大量元素，所以该操作的时间开销很大；而对于链表在进行插入或删除操作时，仅仅是简单的指针赋值运算即可完成。2．描述链表中，头结点、头指针、首元结点（第一个元素结点）三个概念的区别。（1）首元结点：是指链表中存储线性表中第一个数据元素的结点。（2）头结点：在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素。（3）头指针：头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。3．简述在单链表中设置头结点的作用（至少说出两条好处）。在单链表中设置头结点的作用是：（1）可以统一表示空链表和非空链表；（2）对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。4．在单链表、单循环链表、双链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除掉？若可以，其时间复杂度各是多少？（1）在单链表中若仅知道指针p指向某结点，不知道头指针，则不-.53.- 第2章线性表及其应用能将结点p从相应的链表中删除掉。（2）在有n个结点的单循环链表中，删除结点p的时间复杂度为O(n)。（3）在有n个结点的双链表中，删除结点p的时间复杂度为O(1)。5．画出执行下列各语句后各指针及链表的示意图。（1）LinkListL=newLNode,p=L;for(i=1;i<5;i++){p->next=newLNode;p=p->next;p->data=i*2-1;}p->next=NULL;运行结果为：（2）在程序段(1)的基础上画出以下程序段运行结果的示意图。for(i=4;i>0;i--)Ins_LinkList(L,i+1,i*2);运行结果为：（3）在程序段(2)的基础上画出以下程序段运行结果的示意图。for(i=1;i<4;i++)Del_LinkList(L,i);运行结果为：6．间述以下算法的功能。intFunc(LinkList&L){//L是无表头结点的单链表if(L&&L->next){Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;return(1);}elsereturn(0);}二、填空题1．对于线性表的两种基本存储结构，如果表中元素的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度提取或修改线性表中的元素，应该选用（顺序）存储结构。2．在长度为n的顺序表中插入或删除一个元素，分别需要平均移动（插入操作平均移动元素的次数为：n/2，删除操作平均移动元素的次数为：(n-1)/2）个元素，执行以上操作时，移动元素的具体个数与（具体位置）有关。3．顺序表中逻辑上相邻的数据元素的物理位置（一定）紧相邻。单链表中逻辑上相邻的数据元素的物理位置（不一定）紧相邻。4．如果系统语言不支持指针类型的变量，并且在元素总数变化不大的情况下，要求以最快的速度对线性表执行插入和删除操作，那么线性表应该选用（静态链表）存储结构。5．-.53.- 第2章线性表及其应用已知L是带头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试从下面提供的答案中选择合适的语句序列。a.删除P结点的直接后继结点的语句序列是（）。b.删除P结点的直接前驱结点的语句序列是（）。c.删除P结点的语句序列是（）。d.删除首元结点的语句序列是（）。e.删除尾元结点的语句序列是（）。⑴P=P->next;⑵P->next=P;⑶P->next=P->nexe->next;⑷P=P->next->next;⑸while(P!=NULL)P=P->next;⑹while(Q->next!=NULL){P=Q;Q=Q->next;}⑺while(P->next!=Q)P=P->next;⑻while(P->next->next!=Q)P=P->next;⑼while(P->next->next!=NULL)P=P->next;⑽Q=P;⑾Q=P->next;⑿P=L;⒀L=L->next;⒁deleteQ;三、解答题1．编写一函数，在线性顺序表L中求出最大元素以及该元素在表中的位置（假设L中的元素不重复）。-.53.-第2章线性表及其应用intfunc1(SqListL,int&max){if(L.length==0)return(0);inti,k=0;for(i=0;iL.elem[k])k=i;max=L.elem[k];return(k+1);}voidmain(){SqListL;intnum,max;Create_Sq(L);cout<<"当前线性表中的元素为:n";TraverseList_Sq(L);if(num=func1(L,max))cout<<"最大元素为:"<=0)InsertList_Sq(B,j++,num);elseInsertList_Sq(C,k++,num);}}voidmain(){SqListLA,LB,LC;Create_Sq(LA);cout<<"当前线性表中的元素为:n";TraverseList_Sq(LA);func3(LA,LB,LC);cout<<"线性表LB中的元素为:n";TraverseList_Sq(LB);cout<<"线性表LC中的元素为:n";TraverseList_Sq(LC);}-.53.-第2章线性表及其应用4．编写一函数，将两个递增有序的顺序表A和B归并成一个顺序表C，要求C是按元素值不减有序排列的（允许C中有相同值的元素）。voidfunc4(SqListA,SqListB,SqList&C){inti=0,j=0,k=1;InitList_Sq(C);while(inext,r=L;while(r&&r->next){if(r->next->data>q->data){p=r;q=r->next;}r=r->next;-.53.- 第2章线性表及其应用}max=q->data;p->next=q->next;deleteq;}-.53.-第2章线性表及其应用-.53.-第2章线性表及其应用voidmain(){LinkListL;intnum;Create_L(L);TraverseList_L(L);func5(L,num);cout<<"max="<next,*q,*r;if(p==L||p->next==L)return;q=p->next;p->next=L;while((r=q->next)!=L){q->next=p;p=q;q=r;}q->next=p;L->next=q;}7．已知线性表A中的数据元素按照值非递减有序。编写一个算法，将元素e插入到线性表A中适当位置并仍然保持A有序。试分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。voidfunc7_1(SqList&L,ElemTypex)//将x插入到有序顺序表L中并保持仍然有序{inti;for(i=0;idata=e;while(p&&p->next&&p->next->datanext;q->next=p->next;p->next=q;}voidmain(){LinkListL;ElemTypee;inti,n=10;InitList_L(L);-.53.- 第2章线性表及其应用cout<<"输入10个整数:";for(i=0;i>e;func7_2(L,e);}TraverseList_L(L);}8．在有序线性表L中可能有相同的元素。试设计一个算法删除表中所有多余的元素（相同元素仅保留第一个），使删除后表中的元素各不相同。分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。voidfunc8_1(SqList&L){ElemTypee;inti=0;while(inext,q;if(!p)return;while(p->next){if(p->data==p->next->data){q=p->next;p->next=q->next;cout<data<<"";deleteq;}elsep=p->next;}}9．所谓约瑟夫（Josephu）问题是：设有n个人围成一圈并依次进行编号1，2，3，……，n。从某个位置i上的人开始报数，数到m的人出列。下一个人（第m+1个）又从1开始报数，再数到m的人又出列，依次重复下去，直到最后一个人出列为止。按照出列的先后可得一新的序列。试用循环链表作为存储结构，编出求解这一问题的程序。程序代码参见本章【例2.6】中的两种方法。10．在本章[例2.9]（1）的基础上，编出实现两个多项式和相乘的程序。其中，-.53.-第2章线性表及其应用每个多项式都用单链表表示。2.8上机实验实验题目约瑟夫(Joseph)环【问题描述】约瑟夫(Joseph)问题的一种描述是：编号为1,2,3,…-.53.- 第2章线性表及其应用,n的n个人按顺时针方向围坐一圈，每人有一个密码（正整数）。首先输入一个整数m，从第一个人开始报数1,2,3,…，报到m时停止报数。让报m的人出圈，显示输出该人的密码，并将该密码作为新的m值，从该位置顺时针方向上的下一个人开始重新从1开始报数，如此下去，直到所有人全部出圈为止。设计一个程序模拟该过程。【基本要求】（1）用顺序存储结构模拟约瑟夫问题，按照出圈的顺序依次输出每人的编号和密码；（2）利用单向循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人的编号和密码；（3）用静态循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人原来的编号和密码。【测试数据】m的初值为20，n=7，7个人的密码依次为：3,1,7,2,4,8,4，首先m的值为6，正确测试结果的编号序列为：6,1,4,7,2,3,5。【实现提示】程序运行后，首先要求用户输入人数n和报数上限的初始值m，然后依次读入n个人的密码。此题对于单向循环链表存储结构不需要“头结点”，并注意空表和非空表的判定。-.53.-第2章线性表及其应用（1）用顺序存储结构模拟约瑟夫问题，按照出圈的顺序依次输出每人的编号和密码；-.53.-第2章线性表及其应用#include"iostream.h"structLDate{intnum,mima;};//定义线性表的元素类型voidmain_J1(){inti,m,n,k=0,len;//k表示初始位置,len表示当前的表长LDate*Jp;cout<<"输入初始位置m和人数n:";cin>>m>>n;Jp=newLDate[n];cout<<"按序输入"<>Jp[i].mima;}len=n;cout<<"每个出队人的编号和密码依次为:n";while(len){k=(k+m-1)%len;m=Jp[k].mima;cout<<"编号="<>m>>n;p=L=newJNode;//建立一个具有n个结点的循环队列，编号num为:1,2,3,...,ncout<<"按序输入"<next=newJNode;p=p->next;p->num=i+1;cin>>p->mima;}p->next=L;p=L;cout<<"每个出队人的编号和密码依次为:n";for(i=0;inext==L)p=L;p=p->next;}if(p->next==L)p=L;q=p->next;m=q->mima;cout<<"编号="<num<<",密码="<next=q->next;deleteq;}}（运行演示结果如方法一）（3）用静态循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人原来的编号和密码。-.53.- 第2章线性表及其应用structJJNode{intnum,mima,next;};//定义静态链表的结点类型voidmain_J3(){intm,n,i,k,p,q;JJNode*L;cout<<"输入初始位置m和人数n:";cin>>m>>n;/*以下程序的功能是，建立静态循环链表L*/L=newJJNode[n];cout<<"顺序输入"<>L[i].mima;L[i].num=L[i].next=i+1;}L[n-1].next=0;//形成一个静态循环链表/*以下程序的功能是，依次输出每一个出队人员的密码*/cout<<"出队的密码序列为:n";p=n-1;//p指向最后一个结点for(i=0;i