数据结构与C++算法设计案例教程课件

《数据结构与C++算法设计案例教程课件》由会员分享，可在线阅读，更多相关《数据结构与C++算法设计案例教程课件（81页珍藏版）》请在金锄头文库上搜索。

1、模块五 数组、串和广义表数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 书名：数据结构与C+算法设 计案例教程 作者：赖俊峰 ISBN：978-7-111-31755-5 出版社：机械工业出版社数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v任务一 数组v任务二 串 v任务三 广义表 数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 任务一 数组v子任务1 数组的定义v子任务2 数组的基本操作 v子任务3 特殊矩阵的压缩存储 数据结构与C+算法设计案例

2、教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 子任务1 数组的定义v在早期的高级语言中，数组是唯一可供使用的数据类型。由 于数组中各元素具有统一的类型，并且数组元素的下标一般 具有固定的上界和下界，因此，数组的处理比其它复杂的结 构更为简单。v数组作为一种数据结构，其特点是结构中的元素本身可以是 具有某种结构的数据，但属于同一数据类型，v一维数组可以看作一个线性表，二维数组可以看作“数据元 素是一维数组”的一维数组，三维数组可以看作“数据元素是 二维数组”的一维数组，以此类推。如图5-1表示一个m行n列 的二维数组。数据结构与C+算法设计案例教程 赖俊峰 978-7-1

3、11-31755-5 高职高专ppt课件 v图5-1中的A数组可看成是由m个行向量或者n个列向量组成的线性表。v对于上述二维数组A，这里可以将A看成是下述线性表 A =(d1,d2,dn) 其中每一个数据元素dj本身也是一个线性表 dj=(d1j,d2j,dmj) 1jn。该线性表是二维数组A的第j个列向量。v同样，也可将二维数组A看成线性表A =(s1,s2,sm),其中每个si本身 也是一个线性表si=(si1,si2,sin) 1im，si是二维数组A的第i个行向 量。v类似地，一个三维数组可以看成是数据元素为二维数组的线性表。一般 地，一个n维数组可视为其数据元素为n-1维数组的线性表

4、。Amn =a 21 a22 。 。 a2n a m1 am2 。 。 amn a11 a12 。 。 a1n 。 。 。 。 。图5-1数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v二维数组中每个元素ai,j均属于两个向量，第i行的行向量和第j列的列向 量。因此，除边界外，每个元素ai,j都恰好有两个直接前趋和直接后继： 行向量上的直接前趋ai,j-1和直接后继ai,j+1，列向量上的直接前趋ai-1,j 和直接后继ai+1,j；v二维数组中有且仅有一个开始结点a11，它没有直接前趋；有且仅有一 个终端结点amn，它没有直接后继；v边界上的

5、结点(开始结点和终端结点除外)只有一个直接前趋或者只有一 个直接后继。即除开始结点a11外，第一行和第一列上的结点 a1j(j=2,.,n),ai1(i=2,.,m)都只有一个直接前趋；除终端结点amn外，第 m行和第n列上的结点amj(j=1,.,n-1),ain(i=1,.,m-1)都只有一个直接后 继。数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v数组一旦被定义，它的维数和维界就不再改变。因 此，除了结构的初始化和销毁之外，数组只有存取 元素和修改元素值的操作。v数组通常只有两种基本运算读和写。读：给定一组下标，读取相应的数据元素。写：

6、给定一组下标，修改相应的数据元素。数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 数组上的基本操作有：v(1) 数组的输入：ArInput ()初始条件：数组存在。操作结果：向数组元素中输入元素。v(2) 求数组的长度：ArLength ()初始条件：数组存在。操作结果：显示数组中有效元素的个数。v(3) 取数组元素：ArGetElem(int n)初始条件：数组存在。操作结果：显示数组指定元素，如果没有则显示空。v(4) 按值查找：ArLocateElem(int m)，m是给定的一个数据元素初始条件：数组存在。操作结果：显示m所在的位置，如果

7、没有则显示空。数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v(5) 地址操作：ArAddress(int i)初始条件：数组存在。操作结果：显示第i号元素的地址v(6) 插入操作：ArInsertElem(int i,int j,int k,char*e)初始条件：数组存在 。操作结果：在第i个的第j个的第k个位置插入元素e。v(7) 删除操作：void ArDeleteElem(int i,int j,int k)初始条件：数组存在。操作结果：在第i个的第j个的第k个位置插入元素。数据结构与C+算法设计案例教程 赖俊峰 978-7-111-

8、31755-5 高职高专ppt课件 二维数组的两种存储方式 v一种是以列序为主序的存储方式v一种是以行序为主序的存储方式数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v(a)列序为主序：a11 a21 am1 a12 a22 Am2a1n a2n amn v(b)行序为主序：a11 a12 a1n a21 a22 A2nam1 am2 amn v以上规则可以推广到多维数组的情况：优先顺序可规 定为先排最右的下标，从右到左，最后排最左下标： 列优先顺序与此相反，先排最左下标，从左向右，最 后排最右下标。数据结构与C+算法设计案例教程 赖俊峰 97

9、8-7-111-31755-5 高职高专ppt课件 v按上述两种方式顺序存储的数组，只要知道开始结 点的存放地址（即基地址），维数和每维的上、下 界，以及每个数组元素所占用的单元数，就可以将 数组元素的存放地址表示为其下标的线性函数。v因此，数组中的任一元素可以在相同的时间内存取 ，即顺序存储的数组是一个随机存取结构。数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 举例v二维数组Amn按“行优先顺序”存储在内存中，假设每个元素 占用d个存储单元。元素aij的存储地址应是数组的基地址加 上排在aij前面的元素所占用的单元数。因为aij位于第i行、第

10、 j列，前面i-1行一共有(i-1) n个元素，第i行上aij前面又有j-1 个元素，故它前面一共有(i-1) n+j-1个元素，v因此，aij的地址计算函数为： LOC(aij)=LOC(a11)+(i-1)*n+j-1*d数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v三维数组Aijk按“行优先顺序”存储，其地址计算函数 为： LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*dv上述讨论均是假设数组各维的下上界是1的情况，更 一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一 定是1。aij

11、前一共有i-c1行，二维数组一共有d2-c2+1 列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上 aij前一共有j-c2个元素，v因此，aij的地址计算函数为： LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 v在C+语言中，数组各维下标的下界是0，因 此在C语言中，二维数组的地址计算公式为 ：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职

12、高专ppt课件 子任务2 数组的基本操作v数组的主要基本操作包括：v1、向数组元素中输入元素v2、显示数组中有效元素的个数v3、插入元素v4、删除元素数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 【案例】对学生宿舍楼（包括层数，每层宿舍 数，每宿舍学生数）管理创建一个三维数组#include using namespace std; class DormArray /宿舍楼数组类 private:int cnt; /当前有效元素的个数char* Dormitory6306; /学生宿舍数组，每座宿舍楼有6层，每层有30个宿舍，每个宿舍住6个学生

13、 public: void ArInput(); /向数组元素中输入元素， void ArLength(); /显示数组中有效元素的个数 void ArInsertElem(int i,int j,int k,char*e); /在第i号楼、第j号宿舍、k号床位插入元素e void ArDeleteElem(int i,int j,int k); /在第i号楼、第j号宿舍、k号床位删除元素e ;数据结构与C+算法设计案例教程 赖俊峰 978-7-111-31755-5 高职高专ppt课件 1、向数组元素中输入元素void DormArray:ArInput() int i,j,k; for(i

14、=0;ii; if(i=-1) break; cinj; cink; coutname; Dormitoryi-1j-1k-1=name; cout=j，则ai j在下三角形中。ai j之前的i行（从第0 行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上， ai j之前恰有j个元素（ 即ai0,ai1,ai2,aij-1），因此有关系式：k=i*(i+1)/2+j 0jv下三角矩阵的存储和对称矩阵类似sak 和aij对应关系是：i(i+1)/2+j ijn(n+1)/2 i=0)个元素d1，d2，dn的有限 序列，其中di或者是原子项，或者是一个广义表 。v通常记作LS=(

15、d1，d2，dn)。LS是广义表的 名字，n为它的长度。若di是广义表，则称它为 LS的子表，为了区别原子和广义表，书写时用大 写字母表示广义表，用小写字母表示原子。广义表具有如下的结构特点:v（1） 广义表中的数据元素有相对次序。v（2） 广义表的长度定义为最外层包含的元素个数。v（3） 广义表的深度定义为所含括弧的重数。在广义表中“原子”的深度为“0”；“空表”的深度为1。v（4） 表头可以是原子或列表;表尾必定是列表。v（5） 广义表可以是一个递归的表，递归表的深度是 无穷 值，长度是有限值。 v（6） 任何一个非空广义表LS =(d1，d2，dn) 均可分解为：表头 Head(LS) = d1和表尾Tail(LS) = ( 2, , n)两部分。例子vA=( ) A是一个空表,它的长度为零vB=(e) 列表B只有一个原子e,B的长度为1.vC=(a,(b,c,d) 列表C的长度为2,两个元素分别为 原子a和子表(b,c,d)vD=(A,B,C)