数据结构第2章数组

27第2章数组一、复习要点本章主要讨论数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构。它们都是线性结构。但数组是直接存取结构，可以根据数组元素的下标直接在数组中存取该元素，而利用它实现的顺序表是顺序存取结构，所有数据元素集中存储于表的前端。字符串是顺序表的特化。本章复习的要点：1、基本知识点理解作为抽象数据类型定义的数组类，掌握在C++中数组的定义和初始化方法，明确静态数组和动态数组的不同特点和使用，特别需要注意的是数组的存储结构不一定是一个连续的存储空间，当数组存放于一个连续的存储空间时叫做数组的顺序存储方式。要求掌握一维数组、二维数组、三维数组的地址计算方法。需要明确：数组是一种实现级的结构。其次，需要理解顺序表的定义和特点，顺序表的类定义及其主要操作，如搜索、插入和删除的实现，掌握对它们的性能估计，包括搜索算法的平均搜索长度，插入与删除算法中的对象平均移动次数。还要掌握顺序表实例的定义和使用事例。接着，需要掌握稀疏矩阵的三元组表示，并理解稀疏矩阵的转置运算的实现及其性能。此外，需要理解字符串的定义，字符串抽象数据类型的类定义，字符串中各种重载操作的实现和使用，简单的模式匹配算法和匹配事例。2、算法设计静态数组对象的定义，动态数组对象的定义数组中数组元素的原地逆置递归计算数组长度、数组中所有元素的和及平均值在顺序表中搜索值为item的元素，在有序顺序表中搜索值为item的元素在有序顺序表中插入新元素item到第i个位置在有序顺序表中删除第i个元素两个有序顺序表的合并，m个有序顺序表的合并二、难点与重点1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储确定数组元素的三要素：行号、列号、元素值数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除顺序表搜索算法、平均比较次数的计算插入与删除算法、平均移动次数的计算3、字符串：字符串的定义及其操作的实现串重载操作的定义与实现三、教材中习题的解析2-1设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；28然后从出局的下一个人重新开始报数，数到第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;in;i++)A[i]=i+1;//初始化，执行n次i=s-1;//报名起始位置for(k=n;k1;i--){//逐个出局，执行n-1次if(i==k)i=0;i=(i+m-1)%k;//寻找出局位置if(i!=k-1){tmp=A[i];//出局者交换到第k-1位置for(j=i;jk-1;j++)A[j]=A[j+1];A[k-1]=tmp;}}for(k=0;kn/2;k++){//全部逆置,得到出局序列tmp=A[k];A[k]=A[n-k+1];A[n-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=229k=2289634715第2人出局,i=0829634715第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)/2O(n2)。2-3设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为(en-1,en-2,…,e1,e0)。【解答】templateclassTypevoidinverse(TypeA[],intn){Typetmp;for(inti=0;i=(n-1)/2;i++){tmp=A[i];A[i]=A[n-i-1];A[n-i-1]=tmp;}}2-4假定数组A[arraySize]中有多个零元素,试写出一个函数,将A中所有的非零元素依次移到数组A的前端A[i]（0iarraySize）。【解答】因为数组是一种直接存取的数据结构，在数组中元素不是像顺序表那样集中存放于表的前端，而是根据元素下标直接存放于数组某个位置，所以将非零元素前移时必须检测整个数组空间，并将后面变成零元素的空间清零。函数中设置一个辅助指针free，指示当前可存放的位置，初值为0。先给出作为抽象数据类型数组的类声明。#includeiostream.h//在头文件“array.h”中#includestdlib.hconstintDefaultSize=30;templateclassTypeclassArray{//数组是数据类型相同的n（size）个元素的一个集合,下标范围从0到n-1。对数组中元素//可按下标所指示位置直接访问。30private:Type*elements;//数组intArraySize;//元素个数public:Array(intSize=DefaultSize);//构造函数Array(constArrayType&x);//复制构造函数~Array(){delete[]elements;}//析构函数ArrayType&operator=(constArrayType&a);//数组整体赋值(复制)Type&operator[](inti);//按下标访问数组元素intLength()const{returnArraySize;}//取数组长度voidcompact();//数组压缩voidReSize(intsz);//修改数组长度}templateclassTypevoidArrayType::compact(){intfree=0;//非零元素存放地址for(inti=0;iArraySize;i++)//检测整个数组if(elements[i]!=0){//发现非零元素elements[free]=elements[i];//前移free++;elements[i]=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若矩阵Amn中的某一元素A[i][j]是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存放矩阵，试编写一个函数，确定鞍点在数组中的位置（若鞍点存在时），并分析该函数的时间复杂度。【解答】intminmax(intA[][],constintm,constintn){//在二维数组A[m][n]中求所有鞍点,它们满足在行中最小同时在列中最大2n21)n(n1n1)01)1n(n(1n1in1n1AMNn0i1n0i21n21)n(nn10)12)(n1)((nn11)i(nn1AMN31int*row=newint[m];int*col=newint[n];inti,j;for(i=0;im;i++){//在各行中选最小数组元素,存于row[i]row[i]=A[i][0];for(j=1;jn;j++)if(A[i][j]row[i])row[i]=A[i][j];}for(j=0;jn;j++){//在各列中选最大数组元素,存于col[j]col[i]=A[0][j];for(i=1;im;i++)if(A[i][j]col[j])col[j]=A[i][j];}for(i=0;im;i++){//检测矩阵，寻找鞍点并输出其位置for(j=0;jn;j++)if(row[i]==col[j])cout“Thesaddlepointis:(”i“,”j“)”endl;delete[]row;delete[]col;}此算法有3个并列二重循环，其时间复杂度为O(mn)。2-7设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。【解答】设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(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”中#define