数据结构习题解析第2章.pdf
- 文档编号:14652110
- 上传时间:2023-06-25
- 格式:PDF
- 页数:18
- 大小:292.31KB
数据结构习题解析第2章.pdf
《数据结构习题解析第2章.pdf》由会员分享,可在线阅读,更多相关《数据结构习题解析第2章.pdf(18页珍藏版)》请在冰点文库上搜索。
27第2章数组一一、复习要点复习要点本章主要讨论数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构。
它们都是线性结构。
但数组是直接存取结构,可以根据数组元素的下标直接在数组中存取该元素,而利用它实现的顺序表是顺序存取结构,所有数据元素集中存储于表的前端。
字符串是顺序表的特化。
本章复习的要点:
1、基本知识点理解作为抽象数据类型定义的数组类,掌握在C+中数组的定义和初始化方法,明确静态数组和动态数组的不同特点和使用,特别需要注意的是数组的存储结构不一定是一个连续的存储空间,当数组存放于一个连续的存储空间时叫做数组的顺序存储方式。
要求掌握一维数组、二维数组、三维数组的地址计算方法。
需要明确:
数组是一种实现级的结构。
其次,需要理解顺序表的定义和特点,顺序表的类定义及其主要操作,如搜索、插入和删除的实现,掌握对它们的性能估计,包括搜索算法的平均搜索长度,插入与删除算法中的对象平均移动次数。
还要掌握顺序表实例的定义和使用事例。
接着,需要掌握稀疏矩阵的三元组表示,并理解稀疏矩阵的转置运算的实现及其性能。
此外,需要理解字符串的定义,字符串抽象数据类型的类定义,字符串中各种重载操作的实现和使用,简单的模式匹配算法和匹配事例。
2、算法设计静态数组对象的定义,动态数组对象的定义数组中数组元素的原地逆置递归计算数组长度、数组中所有元素的和及平均值在顺序表中搜索值为item的元素,在有序顺序表中搜索值为item的元素在有序顺序表中插入新元素item到第i个位置在有序顺序表中删除第i个元素两个有序顺序表的合并,m个有序顺序表的合并二二、难点与重点难点与重点1、作为抽象数据类型的数组:
数组的定义、数组的按行顺序存储与按列顺序存储确定数组元素的三要素:
行号、列号、元素值数组元素的存放地址计算2、顺序表:
顺序表的定义、搜索、插入与删除顺序表搜索算法、平均比较次数的计算插入与删除算法、平均移动次数的计算3、字符串:
字符串的定义及其操作的实现串重载操作的定义与实现三三、教材中习题的解析教材中习题的解析282-1设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,如此反复直到所有的人全部出局为止。
下面要解决的Josephus问题是:
对于任意给定的n,s和m,求出这n个人的出局序列。
请以n=9,s=1,m=5为例,人工模拟Josephus的求解过程以求得问题的解。
【解答】出局人的顺序为5,1,7,4,3,6,9,2,8。
2-2试编写一个求解Josephus问题的函数。
用整数序列1,2,3,n表示顺序围坐在圆桌周围的人,并采用数组表示作为求解过程中使用的数据结构。
然后使用n=9,s=1,m=5,以及n=9,s=1,m=0,或者n=9,s=1,m=10作为输入数据,检查你的程序的正确性和健壮性。
最后分析所完成算法的时间复杂度。
【解答】函数源程序清单如下:
voidJosephus(intA,intn,s,m)inti,j,k,tmp;if(m=0)cerrm=0是无效的参数!
endl;return;for(i=0;i1;i-)/逐个出局,执行n-1次if(i=k)i=0;i=(i+m-1)%k;/寻找出局位置if(i!
=k-1)tmp=Ai;/出局者交换到第k-1位置for(j=i;jk-1;j+)Aj=Aj+1;Ak-1=tmp;for(k=0;kn/2;k+)/全部逆置,得到出局序列tmp=Ak;Ak=An-k+1;An-k+1=tmp;例:
n=9,s=1,m=5012345678k=9123456789第5人出局,i=4k=8123467895第1人出局,i=0k=7234678915第7人出局,i=4k=6234689715第4人出局,i=2k=5236894715第3人出局,i=1k=4268934715第6人出局,i=1k=3289634715第9人出局,i=2k=2289634715第2人出局,i=029829634715第8人出局,i=0逆置517436928最终出局顺序例:
n=9,s=1,m=0报错信息m=0是无效的参数!
例:
n=9,s=1,m=10012345678k=9123456789第1人出局,i=0k=8234567891第3人出局,i=1k=7245678931第6人出局,i=3k=6245789631第2人出局,i=0k=5457892631第9人出局,i=4k=4457892631第5人出局,i=1k=3478592631第7人出局,i=1k=2487592631第4人出局,i=0847592631第8人出局,i=0逆置136295748最终出局顺序当m=1时,时间代价最大。
达到(n-1)+(n-2)+1=n(n-1)/2O(n2)。
2-3设有一个线性表(e0,e1,en-2,en-1)存放在一个一维数组AarraySize中的前n个数组元素位置。
请编写一个函数将这个线性表原地逆置,即将数组的前n个原址内容置换为(en-1,en-2,e1,e0)。
【解答】templatevoidinverse(TypeA,intn)Typetmp;for(inti=0;i=(n-1)/2;i+)tmp=Ai;Ai=An-i-1;An-i-1=tmp;2-4假定数组AarraySize中有多个零元素,试写出一个函数,将A中所有的非零元素依次移到数组A的前端Ai(0iarraySize)。
【解答】因为数组是一种直接存取的数据结构,在数组中元素不是像顺序表那样集中存放于表的前端,而是根据元素下标直接存放于数组某个位置,所以将非零元素前移时必须检测整个数组空间,并将后面变成零元素的空间清零。
函数中设置一个辅助指针free,指示当前可存放的位置,初值为0。
先给出作为抽象数据类型数组的类声明。
#include/在头文件“array.h”中#includeconstintDefaultSize=30;templateclassArray/数组是数据类型相同的n(size)个元素的一个集合,下标范围从0到n-1。
对数组中元素/可按下标所指示位置直接访问。
private:
30Type*elements;/数组intArraySize;/元素个数public:
Array(intSize=DefaultSize);/构造函数Array(constArray&x);/复制构造函数Array()deleteelements;/析构函数Array&operator=(constArray&a);/数组整体赋值(复制)Type&operator(inti);/按下标访问数组元素intLength()constreturnArraySize;/取数组长度voidcompact();/数组压缩voidReSize(intsz);/修改数组长度templatevoidArray:
compact()intfree=0;/非零元素存放地址for(inti=0;iArraySize;i+)/检测整个数组if(elementsi!
=0)/发现非零元素elementsfree=elementsi;/前移free+;elementsi=0;2-5顺序表的插入和删除要求仍然保持各个元素原来的次序。
设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?
删除一个元素,又平均需要移动多少个元素?
【解答】若设顺序表中已有n=last+1个元素,last是顺序表的数据成员,表明最后表项的位置。
又设插入或删除表中各个元素的概率相等,则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加),每个元素位置插入的概率为1/(n+1),但在删除时只能在已有n个表项范围内删除,所以每个元素位置删除的概率为1/n。
插入时平均移动元素个数AMN(AveragyMovingNumber)为删除时平均移动元素个数AMN为根据上述推导,插入时平均移动127/2=63.5个元素,删除时平均移动(127-1)/2=63个元素。
2-6若矩阵Amn中的某一元素Aij是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵的一个鞍点。
假设以二维数组存放矩阵,试编写一个函数,确定鞍点在数组中的位置(若鞍点存在时),并分析该函数的时间复杂度。
【解答】intminmax(intA,constintm,constintn)/在二维数组Amn中求所有鞍点,它们满足在行中最小同时在列中最大int*row=newintm;int*col=newintn;inti,j;2n21)n(n1n1)01)1n(n(1n1in1n1AMNn0i1n0i21n21)n(nn10)12)(n1)(nn11)i(nn1AMN31for(i=0;im;i+)/在各行中选最小数组元素,存于rowirowi=Ai0;for(j=1;jn;j+)if(Aijrowi)rowi=Aij;for(j=0;jn;j+)/在各列中选最大数组元素,存于coljcoli=A0j;for(i=1;icolj)colj=Aij;for(i=0;im;i+)/检测矩阵,寻找鞍点并输出其位置for(j=0;jn;j+)if(rowi=colj)cout“Thesaddlepointis:
(”i“,”j“)”endl;deleterow;deletecol;此算法有3个并列二重循环,其时间复杂度为O(mn)。
2-7设有一个二维数组Amn,假设A00存放位置在644(10),A22存放位置在676(10),每个元素占一个空间,问A33(10)存放在什么位置?
脚注(10)表示用10进制表示。
【解答】设数组元素Aij存放在起始地址为Loc(i,j)的存储单元中。
Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.n=(676-2-644)/2=15Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.2-8利用顺序表的操作,实现以下的函数。
(1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值。
空出的位置由最后一个元素填补,若顺序表为空则显示出错信息并退出运行。
(2)从顺序表中删除第i个元素并由函数返回被删元素的值。
如果i不合理或顺序表为空则显示出错信息并退出运行。
(3)向顺序表中第i个位置插入一个新的元素x。
如果i不合理则显示出错信息并退出运行。
(4)从顺序表中删除具有给定值x的所有元素。
(5)从顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素,如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(6)从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素,如果s或t不合理或顺序表为空则显示出错信息并退出运行。
(7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。
(8)从顺序表中删除所有其值重复的元素,使表中所有元素的值均不相同。
【解答】顺序表的类定义#ifndefSEQLIST_H/定义在头文件“seqlist.h”中#defineSEQLIST_H#include#includetemplateclassSeqList32private:
Type*data;/顺序表的存放数组intMaxSize;/顺序表的最大可容纳项数intlast;/顺序表当前已存表项的最后位置intcurrent;/顺序表的当前指针(最近处理的表项)public:
SeqList(intMaxSize);/构造函数SeqList()deletedata;/析构函数intMaxLength()constreturnMaxSize;/求表的最大长度intLength()constreturnlast+1;/计算表长度intFind(Typex)const;/定位函数:
找x位置,置为当前表项voidLocate(inti)i=0&i=last?
current=i:
exit
(1);/定位函数:
第i项置为当前表项intIsIn(Typex);/判断x是否在表中,不置为当前表项Type*GetData()returncurrent=-1?
NULL:
datacurrent;/取当前表项的值intInsert(Typex);/插入x在表当前表项之后,置为当前表项intAppend(Typex);/追加x到表尾,置为当前表项Type*Remove();/删除当前表项,置下一表项为当前表项Type*First();/取表中第一个表项的值,置为当前表项Type*Next()returncurrent0?
&data-current:
NULL;/取当前表项前驱表项的值,置为当前表项intIsEmpty()returnlast=-1;/判断顺序表空否,空则返回1;否则返回0intIsFull()returnlast=MaxSize-1;/判断顺序表满否,满则返回1;否则返回0#endif
(1)实现删除具有最小值元素的函数如下:
templateType*DelMin(SeqList*L)if(L-Length()=0)/表空,中止操作返回cerr“ListisEmpty!
”First(),*temp;/假定0号元素的值最小for(inti=1;iLength();i+)/循环,寻找具有最小值的元素temp=L-Next();/下一个表项定位为当前表项if(*tempFind(min);temp=L-Remove();/定位于min所在表项,删除之returntemp;
(2)实现删除第i个元素的函数如下(设第i个元素在datai,i=0,1,last):
templateType*DelNo#i(SeqList*L,inti)if(L-Length()=0|i=L-Length()/表空或i不合理,中止操作cerr“ListisEmptyorParameterisoutrange!
”Locate(i);/定位于第i个元素Type*temp=L-Remove();/删除returntemp;33(3)实现向第i个位置插入一个新的元素x的函数如下(设第i个元素在datai,i=0,1,last):
templatevoidInsNo#i(SeqList*L,inti,Typex)if(L-IsFull()|i=L-Length()/表满或参数i不合理,中止操作返回cerr“ListisFullorParameterisoutrange!
”Locate(i);/定位于第i个元素L-Insert(x);/在第i个位置插入(4)从顺序表中删除具有给定值x的所有元素。
templatevoidDelValue(SeqList*L,Typex)inti=0;Type*temp=L-First();while(iLength()/循环,寻找具有值x的元素并删除它if(*temp=x)L-Remove();/删除具有值x的元素elsetemp=L-Next();i+;(5)实现删除其值在给定值s与t之间(要求s小于t)的所有元素的函数如下:
templatevoidDelNo#sto#t(SeqList*L,Types,Typet)if(L-Length()=0|s=t)cerr“Listisemptyorparametersareillegal!
”First();while(iLength()/循环,寻找界于s与t之间的元素并删除它if(*temp=s&*tempRemove();elsetemp=L-Next();i+;(6)实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下:
templatevoidDelNo#sto#t1(SeqList*L,Types,Typet)if(L-Length()=0|s=t)cerr“Listisemptyorparametersareillegal!
”First();while(iLength()/循环,寻找值s的第一个元素if(*temp=s)break;/退出循环时,该元素成为当前表项elsetemp=L-Next();i+;/否则,继续寻找while(iLength()&*tempRemove();temp=L-GetData();(7)实现将两个有序顺序表合并成一个新的有序顺序表的函数如下:
templateSeqListMerge(SeqListA,SeqListB)/合并有序顺序表A与B成为一个新的有序顺序表并由函数返回SeqListtemp;if(A.Length()+B.Length()temp.MaxLength()cerr“ThesummaryofThelengthofListsisoutMaxSize!
”endl;exit
(1);Type*value1=A.First(),*value2=B.First();inti=0,j=0;while(iA.length()&jB.length()/循环,两两比较,小者存入结果表if(*value1=*value2)34temp.Append(*value1);*value1=A.Next();i+;elsetemp.Append(*value2);*value2=B.Next();j+;while(iA.Length()/当A表未检测完,继续向结果表传送temp.Append(*value1);*value1=A.Next();i+;while(jB.Length()/当B表未检测完,继续向结果表传送temp.Append(*value2);*value2=B.Next();j+;returntemp;(8)实现从表中删除所有其值重复的元素的函数如下:
templatevoidSeqList:
DelDouble()if(L-IsEmpty()cerr“Listisempty!
”First(),*temp2;while(iLength()-1)/循环检测j=i+1;temp2=L-Next();while(jLength()/对于每一个i,重复检测一遍后续元素if(*temp1=*temp2)/如果相等,删除L-Remove();*temp2=L-GetData();else*temp2=L-Next();j+;L-Locate(+i);*temp1=L-GetData();2-9设有一个nn的对称矩阵A,如图(a)所示。
为了节约存储,可以只存对角线及对角线以上的元素,或者只存对角线或对角线以下的元素。
前者称为上三角矩阵,后者称为下三角矩阵。
我们把它们按行存放于一个一维数组B中,如图(b)和图(c)所示。
并称之为对称矩阵A的压缩存储方式。
试问:
(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素?
(2)若在一维数组B中从0号位置开始存放,则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b)应存于一维数组的什么下标位置?
给出计算公式。
(3)若在一维数组B中从0号位置开始存放,则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下(图(c)应存于一维数组的什么下标位置?
给出计算公式。
【解答】
(1)数组B共有n+(n-1)+1=n*(n+1)/2个元素。
(2)只存上三角部分时,若ij,则数组元素Aij前面有i-1行(1i-1,第0行第0列不算),第1行有n个元素,第2行有n-1个元素,第i-1行有n-i+2个元素。
在第i行中,从对角线算起,第j号元素前面有j-i个元素,因此,数组元素Aij在数组B中的存放位置为n+(n-1)+(n-2)+(n-i+2)+j-i=(2n-i+2)*(i-1)/2+j-i=(2n-i)*(i-1)/2+j-1351111121110122222212011211111101020100000nnnnnnnnnnnnnbaaaabbaaabbbaabbbbaC时当时当,jiijCjijiCjiA若ij,数组元素Aij在数组B中没有存放,可以找它的对称元素Aji。
在数组B的第(2n-j)*(j-1)/2+i-1位置中找到。
如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素Aij在数组B中的存放位置可以改为当ij时,=(2n-i+1)*i/2+j-i=(2n-i-1)*i/2+j当ij时,=(2n-j-1)*j/2+i(3)只存下三角部分时,若ij,则数组元素Aij前面有i-1行(1i-1,第0行第0列不算),第1行有1个元素,第2行有2个元素,第i-1行有i-1个元素。
在第i行中,第j号元素排在第j个元素位置,因此,数组元素Aij在数组B中的存放位置为1+2+(i-1)+j=(i-1)*i/2+j若ij,数组元素Aij在数组B中没有存放,可以找它的对称元素Aji。
在数组B的第(j-1)*j/2+i位置中找到。
如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素Aij在数组B中的存放位置可以改为当ij时,=i*(i+1)/2+j当ij时,=j*(j+1)/2+i2-10设A和B均为下三角矩阵,每一个都有n行。
因此在下三角区域中各有n(n+1)/2个元素。
另设有一个二维数组C,它有n行n+1列。
试设计一个方案,将两个矩阵A和B中的下三角区域元素存放于同一个C中。
要求将A的下三角区域中的元素存放于C的下三角区域中,B的下三角区域中的元素转置后存放于C的上三角区域中。
并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。
【解答】计算公式2-11在实际应用中经常遇到的稀疏矩阵是三对角矩阵,如右图所示。
在该矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外,所有其它元素均为0。
现在要将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中,且a11存放于B0。
试给出计算A在三条对角时当时当,1,1jijiCjiijCjiB111110111000nnnnaaaaaaA111110111000nnnnbbbbbbB36线上的元素aij(1in,i-1ji+1)在一维数组B中的存放位置的计算公式。
【解答】在B中的存放顺序为a11,a12,a21,a22,a23,a32,a33,a34,ann-1,ann,总共有3n-2个非零元素。
元素aij在第i行,它前面有3(i-1)-1个非零元素,而在本行中第j列前面有j-i+1个,所以元素aij在B中位置为2*i+j-3。
2-12设带状矩阵是nn阶的方阵,其中所有的非零元素都在由主对角线及主对角线上下各b条对角线构成的带状区域内,其它都为零元素。
试问:
(1)该带状矩阵中有多少个非零元素?
(2)若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题 解析
![提示](https://static.bingdoc.com/images/bang_tan.gif)