数据结构与算法分析幻灯片.ppt

《数据结构与算法分析幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析幻灯片.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法分析数据结构与算法分析第1页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组 4.1.1 数组定义数组定义 数组是数据结构的基本结构形式，它是一种顺序式的结构，数组是存储同一类型数据的数据结构，使用数组时需要定义数组的大小和存储数据的数据类型，数组分为一维数组和多维数组。数组的维数是由数组的下标的个数确定的，一个下标称为一维数组，一个下标以上的数组称为多维数组。从这个意义上讲，确定了对于数组的一个下标总有一个相应的数值与之对应的关系；或者说数组是有限个同类型数据元素组成的序列。数组的基本操作包括：initarray（&A）；/初始化数组destroyarray

2、（&A）；/销毁数组assign（&A，e）；/数组赋值value（A，&e）；/取数组的某个元素 copyarray（M，&T）；/复制一个数组printarray（M）；/打印数组的元素 第2页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4.1.1 数组定义数组定义一维数组一维数组一维数组是指下标的个数只有一个的数组，一维数组是指下标的个数只有一个的数组，有时称为向量，是最基本的数据类型，在有时称为向量，是最基本的数据类型，在java 中需要事先声名，程序才能够在编译中需要事先声名，程序才能够在编译过程中预留内存空间。声明的格式一般是：过程中预留内存空间。声明的格式

3、一般是：=new ；第3页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4.1.1 数组定义数组定义多维数组多维数组多维数组是指下标的个数有两个以上，我们多维数组是指下标的个数有两个以上，我们比较常用的是二维数组（因为三维以上的数比较常用的是二维数组（因为三维以上的数组存储可以简化为二维数组的存储）。下面组存储可以简化为二维数组的存储）。下面以二维数组为例说明多维数组。二维数组的以二维数组为例说明多维数组。二维数组的声明同一维数组。格式为：声明同一维数组。格式为：=new size1 size2;第4页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4

4、.1.2 数组的存储数组的存储一维数组的存储一维数组的数据存储按照顺序存储，逻辑地址和物理地址都是连续的。如果已知第一个数据元素的地址loc(a1)，则第i个元素的地址loc(ai)为：loc(ai)=loc(a1)+（i-1）*c假设数组的下标从1开始，只要求出第i个元素之前存放了多少个数据元素即可（实际上有i-1个元素），每个元素占有c个存储单元，再乘以c，就是第i个元素的起始地址。如果下标从0开始，则第i个元素之前就有i个元素，此时上面的公式就变为：loc(ai)=loc(a1)+i*c由此可见，求数组中数据元素的地址，已知条件必须是知道第一个元素的地址，然后主要是找出该元素之前已经存储

5、了多少个数据元素。在一维数组中，只要知道任何一个元素的地址即可求出其它元素的地址，但在多维数组中，已知条件必须是第一个数据元素地址。第5页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4.1.2 数组的存储数组的存储多维数组以二维数组的顺序存储为例说明，二维数组在顺序存储时一般有两种：行优先顺序：存储时先按行从小到大的顺序存储，在每一行中按列号从小到大存储。列优先顺序：存储时先按列从小到大的顺序存储，在每一列中按行号从小到大存储。以上的两种存储顺序中，第一个被存放的元素总是第一行第一列的数据元素，所以该元素的地址是我们的已知条件。同样在二维数组中比较典型的是计算数据的存储

6、位置。第6页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4.1.2 数组的存储数组的存储多维数组假设二维数组是m*n的二维数组（共有m行，每行有n列）。第一个数据元素的地址是loc(a11)，则第i行第j列的数据元素的地址的计算公式应为（按照行优先顺序存储）：loc(aij)=loc(a11)+（i-1）*n+j-1*c假设下标从1开始，我们需要计算出i行前面已经存储了i-1行元素，每行有n个元素，共有（i-1）*n个数据元素，在第i行元素中，j列之前有j-1个数据元素，共有（i-1）*n+j-1个元素，每个元素占有c个存储单元，只要乘以c就可以了。其中loc(aij)

7、表示第i 行第j列数据元素的内存的起始位置，loc(a11)表示第一个数据元素的内存位置，c表示每个数据元素所占有的内存空间的大小，如果下标从0开始，只要不用减1即可。第7页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4.1.2 数组的存储数组的存储多维数组如果按列优先顺序存储，则地址的计算为：loc(aij)=loc(a11)+（j-1）*m+i-1*c假设下标从1开始，其中loc(aij)表示第i 行第j列的数据元素的内存起始位置，loc(a11)表示第一个数据元素的内存位置，c表示每个数据元素所占有的内存空间的大小；主要还是计算第i行j列元素之前有多少个数据元素。

8、如果下标从0开始，只要不用减1即可。按此公式可以推广到多维数组的数据元素的地址计算（假设按照行优先顺序存储）：m行n 列纵标为k的三维数组，假设第一个元素的地址是loc(a111)，如果按行优先顺序存储，i行j列纵标为p的数据元素的地址为（可以将它分解为二维数组）：loc(aijp)=loc(a111)+(i-1)*n*k+(j-1)*k+p-1*c;如果下标从0开始，只要不用减1即可。读者可以从以上的地址公式中可以找出一定的地址计算规律：多维数组中按行优先计算公式用一个下标乘以后面的最大值。第8页，共23页，编辑于2022年，星期六4.1 4.1 多维数组多维数组4.1.3 显示二维数组的内

9、容显示二维数组的内容一般情况下，只要定义了数组的存储顺序，一般情况下，只要定义了数组的存储顺序，数组的存储顺序就不会改变了，所以对数组数组的存储顺序就不会改变了，所以对数组的各种操作后，应按照数组的已定义的存储的各种操作后，应按照数组的已定义的存储顺序存储；也就是说，如果是按行优先顺序顺序存储；也就是说，如果是按行优先顺序存储，在对数组操作后，即使改变了存储顺存储，在对数组操作后，即使改变了存储顺序，应加以改变仍然按照行优先顺序存储。序，应加以改变仍然按照行优先顺序存储。第9页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩

10、存储所谓矩阵的压缩存储，也就是在存储数组时，尽量减所谓矩阵的压缩存储，也就是在存储数组时，尽量减少存储空间，但是数组中的每个元素必须存储，所以少存储空间，但是数组中的每个元素必须存储，所以在矩阵存储中，如果有规律可寻，只要存储其中一部在矩阵存储中，如果有规律可寻，只要存储其中一部分，而另一部分的存储地址可以通过相应的算法将它分，而另一部分的存储地址可以通过相应的算法将它计算出来，从而占有比较少的存储空间达到存储整个计算出来，从而占有比较少的存储空间达到存储整个矩阵的目的，称为矩阵的压缩存储。矩阵的目的，称为矩阵的压缩存储。矩阵的压缩存储仅是针对特殊矩阵的；而对于没有规矩阵的压缩存储仅是针对特殊

11、矩阵的；而对于没有规律可循的二维数组则不能够使用压缩存储。律可循的二维数组则不能够使用压缩存储。二维数组（矩阵）的压缩存储一般有三种，它们分别二维数组（矩阵）的压缩存储一般有三种，它们分别是对称矩阵、稀疏矩阵和三角矩阵。三种矩阵中以稀是对称矩阵、稀疏矩阵和三角矩阵。三种矩阵中以稀疏矩阵比较常见。疏矩阵比较常见。第10页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵若若n 阶矩阵阶矩阵A中的元素满足以下条件：中的元素满足以下条件：aij=aji i1，j1则称为则称为n阶对称矩阵。阶对称矩阵。对于对称矩阵

12、，如果不采用压缩存储，占有的存储单对于对称矩阵，如果不采用压缩存储，占有的存储单元有元有n2个，因为是对称矩阵，所以只要存储对角的数个，因为是对称矩阵，所以只要存储对角的数据元素和一半的数据元素即可，占有的存储单元有据元素和一半的数据元素即可，占有的存储单元有n（n-1）/2个存储单元中。如果我们以行序为主序存个存储单元中。如果我们以行序为主序存储其下三角（包括对角线）的元素，其上三角的元素储其下三角（包括对角线）的元素，其上三角的元素可以推算出来。可以推算出来。第11页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储特

13、殊矩阵特殊矩阵如果用一维数组存储一个对称矩阵，只要将如果用一维数组存储一个对称矩阵，只要将对称矩阵存储在一个最大下标为对称矩阵存储在一个最大下标为n（n-1）/2的一维数组的一维数组S中即可。此时按照行优中即可。此时按照行优先顺序存储，数据元素先顺序存储，数据元素aij与数组与数组S的下标的下标k的对应关系为：的对应关系为：i(i-1)/2+j-1 当当ij时时 k=j(j-1)/2+i-1 当当ij时时第12页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵对于任意给定的一组下标（对于任意给定的一组下标

14、（i，j），均可在），均可在S中找到元素中找到元素aij，反之，对所有元素都能够确定在，反之，对所有元素都能够确定在S中位置，当中位置，当ij时，时，根据对称矩阵的性质推算即可。由此可以看出对称矩阵的根据对称矩阵的性质推算即可。由此可以看出对称矩阵的存储可以使用一维数组存储可以使用一维数组S存储，占用的空间不再是存储，占用的空间不再是n2，而，而是是n（n-1）/2空间减少了接近一半，实现了二维数组的压空间减少了接近一半，实现了二维数组的压缩存储。缩存储。所谓对角矩阵是指，矩阵的所有非零元素都集中在以主对角所谓对角矩阵是指，矩阵的所有非零元素都集中在以主对角线为中心的带状区域中，即除了主对角线

15、上和直接在主对角线为中心的带状区域中，即除了主对角线上和直接在主对角线上、下方若干条对角线上的元素之外，其余元素皆为零。线上、下方若干条对角线上的元素之外，其余元素皆为零。第13页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储特殊矩阵特殊矩阵也可以按照某个原则（或者以行序为主序，或者以列序为主序，或也可以按照某个原则（或者以行序为主序，或者以列序为主序，或者按对角线的顺序）将对角矩阵者按对角线的顺序）将对角矩阵B的所有非零元素压缩存储到一个的所有非零元素压缩存储到一个一维数组一维数组LTB13n-2中。这里不妨仍然以行

16、序为主序的原则对中。这里不妨仍然以行序为主序的原则对B进行压缩存储，当进行压缩存储，当B中任一非零元素中任一非零元素bij与与LTBk之间存在着如下一之间存在着如下一一对应关系：一对应关系：k=2*i+j-2时，则有时，则有bij=LTBk。称。称LTB13n-2为对角矩阵为对角矩阵B的压缩存储。的压缩存储。上面讨论的几种特殊矩阵中，非零元素的分布都具有明显的规律，上面讨论的几种特殊矩阵中，非零元素的分布都具有明显的规律，因而都可以被压缩存储到一个一维数组中，并能够确定这些矩阵因而都可以被压缩存储到一个一维数组中，并能够确定这些矩阵的每个非零元素在一维数组中的存储位置。但是，对于那些非零的每个

17、非零元素在一维数组中的存储位置。但是，对于那些非零元素在矩阵中的分布没有规律的特殊矩阵元素在矩阵中的分布没有规律的特殊矩阵(如稀疏矩阵如稀疏矩阵)，则需要，则需要寻求其他方法来解决压缩存储问题。寻求其他方法来解决压缩存储问题。第14页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵对稀疏矩阵很难下一个确切的定义，它只是一个凭人们对稀疏矩阵很难下一个确切的定义，它只是一个凭人们的直觉来理解的概念。一般认为，一个较大的矩阵中，的直觉来理解的概念。一般认为，一个较大的矩阵中，零元素的个数相对于整个矩阵元素的总个

18、数所占比例较零元素的个数相对于整个矩阵元素的总个数所占比例较大时，该矩阵就是一个稀疏矩阵。例如，有一个大时，该矩阵就是一个稀疏矩阵。例如，有一个66阶阶的矩阵的矩阵A，其，其36个元素中只有个元素中只有8个非零元素，那么，可个非零元素，那么，可以称矩阵以称矩阵A为稀疏矩阵。为稀疏矩阵。稀疏矩阵一般是指矩阵中的大部分元素为零，仅有少稀疏矩阵一般是指矩阵中的大部分元素为零，仅有少量元素非零的矩阵称为稀疏矩阵；或者说矩阵量元素非零的矩阵称为稀疏矩阵；或者说矩阵A（m n）中有）中有S个非零元素，如果个非零元素，如果S远远小于矩阵的元素远远小于矩阵的元素总数，称总数，称A为稀疏矩阵。稀疏矩阵的存储一般

19、只要保为稀疏矩阵。稀疏矩阵的存储一般只要保存非零元素即可，对于零元素可以不与保存，这样可存非零元素即可，对于零元素可以不与保存，这样可以实现稀疏矩阵的压缩存储。以实现稀疏矩阵的压缩存储。第15页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则如下：稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则如下：每一个非零元素占有一行，每行中包含非零元素所在的行号、列号、非每一个非零元素占有一行，每行中包含非零元素所在的行号、列号、非零元素的数值。为完整描述稀疏矩阵

20、，一般在第一行描述矩阵的行数、零元素的数值。为完整描述稀疏矩阵，一般在第一行描述矩阵的行数、列数和非零元素的个数。其逻辑描述为：列数和非零元素的个数。其逻辑描述为：（row col value）其中其中row表示行号，表示行号，col表示列号，表示列号，value表示非零元素的值。表示非零元素的值。如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如如果每个非零元素按照此种方法存储，虽然能够完整地描述非零元素，但如果矩阵中有整行（或整列）中没有非零元素，此时可能不能够还原成原来的果矩阵中有整行（或整列）中没有非零元素，此时可能不能够还原成原来的矩阵，所以为了完整地描述稀疏矩阵，在

21、以上描述的情况下，如果增加一行矩阵，所以为了完整地描述稀疏矩阵，在以上描述的情况下，如果增加一行的内容，该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个的内容，该行包括矩阵的总的行数、矩阵的总的列数，矩阵中非零元素的个数，就可以还原为原来的矩阵描述了。数，就可以还原为原来的矩阵描述了。第16页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.1 矩阵的压缩存储矩阵的压缩存储稀疏矩阵稀疏矩阵归纳起来，若一个稀疏矩阵有归纳起来，若一个稀疏矩阵有t个非零元素，个非零元素，则需要用则需要用t+1行的三元组来表示稀疏矩阵。行的三元组来表示稀疏矩阵。到底矩

22、阵何时使用三元组存储呢？一般对到底矩阵何时使用三元组存储呢？一般对mn的矩阵来说，只要满足（的矩阵来说，只要满足（t+1）*3m*n这个条件，使用三元组存储可以节省空间，这个条件，使用三元组存储可以节省空间，否则更加浪费空间，也就没有必要使用三元否则更加浪费空间，也就没有必要使用三元组存储，所以稀疏矩阵中的非零元素的个数组存储，所以稀疏矩阵中的非零元素的个数t是能否使用三元组存储的关键。是能否使用三元组存储的关键。第17页，共23页，编辑于2022年，星期六4.2 4.2 矩阵的压缩存储矩阵的压缩存储 4.2.2 稀疏矩阵转换为三元组存储稀疏矩阵转换为三元组存储 首先应该将稀疏矩阵转换为三元组

23、存储，然后才利用三元组的存储，实现对矩阵的各种运算。对于矩阵的运算一般有矩阵的转置，在转置时值得注意的是：在矩阵的存储规则已经确定的情况下（如按行优先存储），实现矩阵的运算（如转置）时，应仍然保留原来的存储规则。改进的转置方法可以利用对原始的三元组的元素的扫描，直接确定该元素在转置后的三元组中的行，这样可以将原始三元组中的元素直接放在转置后的三元组中即可。这种方法需要增加两个一维数组的结构开销，称为快速转置。第18页，共23页，编辑于2022年，星期六4.3 4.3 广义表广义表 4.3.1 广义表的定义广义表是线性表的扩展，具体定义为n（n0）个元素的有限集合。其中元素有以下两种类型：1）一

24、个原子元素（指不可再分的元素）；2）一个可以再分的元素（或称为一个子表）。如果所有元素都是原子元素，则称为线性表，如果含有子表则是广义表。第19页，共23页，编辑于2022年，星期六4.3 4.3 广义表广义表 4.3.1 广义表的定义广义表的基本操作：initGlist(&L)/创建空的广义表creatGlist(&L,S)/由S创建广义表LdestroyGlist(&L)/销毁广义表LGlistlength（L）/求广义表的长度Glistdepth（L）/求广义表的深度Gethead(L)/求广义表L的头Gettail(L)/求广义表的表尾Insertfirst_Glist(&L,e)/插

25、入元素e作为广义表L的第一个元素Deletefirst_Glist(&L,&e)/删除广义表L的第一个元素，并用e返回其值 第20页，共23页，编辑于2022年，星期六4.3 4.3 广义表广义表 4.3.1 广义表的定义广义表一般记作：LS=（a1，a2，an）其中LS是广义表的名称，n是广义表的长度。常见的广义表为：A=（）B=（）C=（a,b）D=（A，B，C）E=（a,E）广义表中含有元素的个数称为广义表的长度，广义表中含有的括号对数称为广义表的深度。第21页，共23页，编辑于2022年，星期六4.3 4.3 广义表广义表 4.3.1 广义表的定义三个重要结论：列表的元素可以是子表，而

26、子表的元素还可以是子表。由此，列表是一个多层次的结构，可以用图形象地表示。例如图4-1表示的是列表D。图中以圆圈表示列表，以方块表示原子元素。列表可为其它列表所共享。例如在上述例子中，列表A、B和C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。列表可以是一个递归的表，即列表也可以是其本身的一个子表。例如列表E就是一个递归的表。第22页，共23页，编辑于2022年，星期六4.3 4.3 广义表广义表 4.3.2 广义表的存储广义表的存储方法有很多种，一般采广义表的存储方法有很多种，一般采用链表存储。用链表存储。采用链表存储时的结点存储的逻辑结构（如图所示）一般是：其中flag表示标志位，当flag为0时，该结点表示原子元素，当flag为1时，该结点表示子表；当flag为0时，info表示原子元素的值，当flag为1时，info表示指针，指向该子表的第一个结点；link表示指针，指向广义表的下一个元素。Flaginfolink第23页，共23页，编辑于2022年，星期六