数据结构第2章数组

《数据结构第2章数组》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章数组一、复习要点本章主要讨论数组抽象数据类型及利用数组实现的顺序表、字符串等数据结构。它们都是线性结构。但数组是直接存取结构，可以根据数组元素的下标直接在数组中存取该元素，而利用它实现的顺序表是顺序存取结构，所有数据元素集中存储于表的前端。字符串是顺序表的特化。本章复习的要点：1、基本知识点理解作为抽象数据类型定义的数组类，掌握在C++中数组的定义和初始化方法，明确静态数组和动态数组的不同特点和使用，特别需要注意的是数组的存储结构不一定是一个连续的存储空间，当数组存放于一个连续的存储空间时叫做数组的顺序存储方式

2、。要求掌握一维数组、二维数组、三维数组的地址计算方法。需要明确：数组是一种实现级的结构。其次，需要理解顺序表的定义和特点，顺序表的类定义及其主要操作，如搜索、插入和删除的实现，掌握对它们的性能估计，包括搜索算法的平均搜索长度，插入与删除算法中的对象平均移动次数。还要掌握顺序表实例的定义和使用事例。接着，需要掌握稀疏矩阵的三元组表示，并理解稀疏矩阵的转置运算的实现及其性能。此外，需要理解字符串的定义，字符串抽象数据类型的类定义，字符串中各种重载操作的实现和使用，简单的模式匹配算法和匹配事例。2、算法设计Ø静态数组对象的

3、定义，动态数组对象的定义Ø数组中数组元素的原地逆置Ø递归计算数组长度、数组中所有元素的和及平均值Ø在顺序表中搜索值为item的元素，在有序顺序表中搜索值为item的元素Ø在有序顺序表中插入新元素item到第i个位置Ø在有序顺序表中删除第i个元素Ø两个有序顺序表的合并，m个有序顺序表的合并二、难点与重点1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储Ø确定数组元素的三要素：行号、列号、元素值Ø数组元素的存放地址计算2、顺序表：顺序表的定义、搜索、插入与删除Ø顺序表搜索算法、平均比较次数的计算Ø插

4、入与删除算法、平均移动次数的计算3、字符串：字符串的定义及其操作的实现Ø串重载操作的定义与实现三、教材中习题的解析2-1设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m44个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n,s和m，求出这n个人的出局序列。请以n=9,s=1,m=5为例，人工模拟Josephus的求解过程以求得问题的解。【解答】出局人的顺序为5,1,7,4,3,6,9,2,

5、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){cerr<<"m=0是无效的参数！"<

6、(i=0;i1;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;j

7、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=244k=2289634715第2人出局,i=0829634715第8人出局,i=0逆置517436928最终出局顺序例：n=9,s=1,m=0报错信息m=0是无效的参数！例：n=9,s=1,m=1

8、0012345678k=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人出