《第5章_数组和广义表07.ppt》由会员分享，可在线阅读，更多相关《第5章_数组和广义表07.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、孙克雷制作第第5 5章章 数组和广义表数组和广义表学习要点学习要点q了解数组在以行序为主的存储中的地址计算方法。了解数组在以行序为主的存储中的地址计算方法。q掌握特殊矩阵和稀疏矩阵的存储方法。掌握特殊矩阵和稀疏矩阵的存储方法。q掌握广义表的结构特点及其存储表示方法。掌握广义表的结构特点及其存储表示方法。孙克雷制作5.1数组的基本概念数组的基本概念a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1 Amn=v 数组是我们最熟悉的数据类型，在早期的高级语言中，数数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统
2、一组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组可看成由若干个行向量组成的向量的推广。例如，二维数组可看成由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。向量，也可以看成是若干个列向量组成的向量。孙克雷制作5.1数组的定义和特性数组的定义和特性v二维数组可看成一个线性表二维数组可看成一个线性表A=(a0，a1，ap)(p=m-1或或n-1)，其
3、中其中aj是一个列向量形式的线性表：是一个列向量形式的线性表：aj=（a0j，a1j，am-1,j），），0jn-1或或ai是一个行向量形式的线性表：是一个行向量形式的线性表：ai=（ai0，ai1，ai,n-1），），0im-1a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1 a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1 a0a1apa0a1ap孙克雷制作5.2数组的顺序表示与实现数组的顺序表示与实现v由于计算机的内存结构是一维的，用一维内存来表示多维由于计算机的内存结构是一维的，用一维内存来表示多维数组，就
4、必须按某种次序将数组元素排成一列序列，然后将数组，就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放在存储器中。通常有两种顺序存储方式：这个线性序列存放在存储器中。通常有两种顺序存储方式：1.行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1个行向量紧个行向量紧接在第接在第i个行向量后面。以二维数组为例，其存储线性序列为：个行向量后面。以二维数组为例，其存储线性序列为：a00,a01,a0,n-1,a10,a11,a1,n-1,am-1,0,am-1,n-12.列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1个列向个列向量紧接在第量
5、紧接在第j个列向量之后，二维数组按列优先顺序存储的线个列向量之后，二维数组按列优先顺序存储的线性序列为：性序列为：a00,a10,am-1,0,a01,a11,am-1,1,am-1,1,an-1,m-1孙克雷制作a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-1 am-1,n-1 am-1,1 am-1,0 a1,n-1 a11 a10 a0,n-1 a01 a00 am-1,n-1 a1,n-1 a0,n-1 am-1,1 a11 a01 am-1,0 a10 a00a00a01a0,n-1a10a11a1,n-1am-1,0am-1,1am-1,n-
6、1 行行优优先先顺顺序序列列优优先先顺顺序序&数组的顺序表示与实现数组的顺序表示与实现孙克雷制作v按上述两种方式顺序存储的数组，只要知道开始结点的地按上述两种方式顺序存储的数组，只要知道开始结点的地址，维数和每维的上、下界，以及每个数组元素所占用的单址，维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素存放地址表示为其下标的线性函数。元数，就可以将数组元素存放地址表示为其下标的线性函数。例如，二维数组例如，二维数组Amn按按“行优先顺序行优先顺序”存储在内存中，存储在内存中，假设每个元素占用假设每个元素占用L个存储单元。个存储单元。元素元素aij的存储地址应是数组的基地址加
7、上排在的存储地址应是数组的基地址加上排在aij前面的前面的元素所占用的单元数。因为元素所占用的单元数。因为aij位于第位于第i+1行、第行、第j+1列，前面列，前面i行一共有行一共有in个元素，第个元素，第i+1行上行上aij前面又有前面又有j个元素，故它前个元素，故它前面一共有面一共有in+j个元素，因此，个元素，因此，aij的地址计算函数为：的地址计算函数为：LOC(i,j)=LOC(0,0)+in+jL&数组的顺序表示与实现数组的顺序表示与实现孙克雷制作v在科学与工程计算问题中，矩阵是一种常用的数学对象，在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，就是将一个矩
8、阵描述为一个二维数在高级语言编制程序时，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单。但是在矩阵中非零元素呈某种规各种矩阵运算也非常简单。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，实际上占用律分布或者矩阵中出现大量的零元素的情况下，实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，会造成极大的浪费，为了节省存储空间，我们可以对这类矩我们可以对这类矩阵进行
9、压缩存储：阵进行压缩存储：即为多个相同的非零元素只分配一个存储即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间空间；对零元素不分配空间。5.3特殊矩阵的压缩存储特殊矩阵的压缩存储孙克雷制作v对称矩阵对称矩阵若若n阶阶矩矩阵阵A中中的的数数据据元元素素满满足足下下述述性性质质aij=aji(1i，jn)则则称称A为为n阶阶对对称称矩矩阵阵；因因aij与与aji相相等等，二二者者只只需需分分配配一一个个存存储单元。这样，可将储单元。这样，可将nn个存储单元压缩到个存储单元压缩到n(n+1)/2个单元。个单元。5.3.1对称矩阵对称矩阵1357326956387984 a11a12.a1
10、na21a22.a2n.an1an2.ann孙克雷制作为节约存储空间，只存对角线及对角线以为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的上的元素，或者只存对角线及对角线以下的元素。不失一般性，假设以行主序存储下三元素。不失一般性，假设以行主序存储下三角（包括对角线）中的元素。角（包括对角线）中的元素。以一维数组以一维数组san(n+1)/2作为作为n阶对称矩阵阶对称矩阵A的存储结构，则的存储结构，则sak和矩阵元和矩阵元aij之间存在之间存在着一一对应的关系：着一一对应的关系：i(i-1)/2+j-1当当ijj(j-1)/2+i-1当当ij&对称矩阵对称矩阵a11a
11、21a22a31a32an,1an,n01234n(n+1)/2-1kk=孙克雷制作若若ij，则，则aij在下三角形中。在下三角形中。aij之前的之前的i-1行（从第行（从第1行到第行到第i-1行）一共有行）一共有1+2+i-1=i(i-1)/2个元素，在第个元素，在第i行上，行上，aij之之前恰有前恰有j-1个元素，因此有：个元素，因此有：k=i(i-1)/2+j-1若若ij，则，则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij=aji，所以只要交换所以只要交换上述对应关系式中的上述对应关系式中的i和和j即可得到：即可得到：k=j(j-1)/2+i-1注意：注意：k从从0开始，开始
12、，i、j从从1开始。开始。&对称矩阵对称矩阵孙克雷制作5.3.2三角矩阵三角矩阵以主对角线划分，三角矩阵有上三角和下三角两种。以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是它的下三角（不包括主对角线）中的元素均上三角矩阵是它的下三角（不包括主对角线）中的元素均为常数或零。下三角矩阵正好相反，它的主对角线上方均为为常数或零。下三角矩阵正好相反，它的主对角线上方均为常数或零。三角矩阵中的重复元素常数或零。三角矩阵中的重复元素c可共享一个存储空间，其可共享一个存储空间，其余的元素正好有余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到个，因此，三角矩阵可压缩存储到一维数组一维数
13、组san(n+1)/2+1中。其中中。其中c存放在向量的最后一个分存放在向量的最后一个分量中。量中。孙克雷制作i(i-1)/2+j-1当当ijn(n+1)/2当当i1时，元素时，元素aij=0。主对角线元素主对角线元素aii所在位置分别是一维数组下标为所在位置分别是一维数组下标为0，3，6，9，。而主对角线上面元素。而主对角线上面元素ai,i+1所在位置分别是一维数组所在位置分别是一维数组下标为下标为1，4，7，10，。主对角线下面的那条对角线主对角线下面的那条对角线ai+1,i所在位置分别是一维数组下标为所在位置分别是一维数组下标为2，5，8，11，。3(i-1)+1当当i=j-13(i-1
14、)当当i=j3(i-1)-1当当i=j+1k=孙克雷制作设矩阵设矩阵Amn中有中有s个非零元素，若个非零元素，若s远远小于矩阵元素的总远远小于矩阵元素的总数数(即即smn)，则称则称A为稀疏矩阵。为稀疏矩阵。稀疏矩阵的三元组表表示稀疏矩阵的三元组表表示在存储稀疏矩阵时，为了节省存储单元，很自然地想到在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置行和列的位置(i，j)。一个三元
15、组一个三元组(i，j，aij)唯一确定了矩阵唯一确定了矩阵A的一个非零元素。因此，稀疏矩阵可由表示非零元素的三的一个非零元素。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。元组及其行列数唯一确定。5.4稀疏矩阵的压缩存储稀疏矩阵的压缩存储孙克雷制作例如：例如：M由由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)和矩阵维数和矩阵维数(6,7)唯一确定唯一确定。&稀疏矩阵稀疏矩阵012900000000000-3000014000240000018000001500-7000M=孙克雷制作三元
16、组顺序表三元组顺序表假设以顺序存储结构来表示三元组表，则可得到稀疏矩假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法阵的一种压缩存储方法三元顺序表。三元顺序表。#defineMAXSIZE12500/非零元个数最大值非零元个数最大值typedefstructinti,j;/行下标和列下标行下标和列下标ElemTypee;Triple;typedefstructTripledataMAXSIZE+1;/非零元三元组表非零元三元组表intmu,nu,tu;/行数、列数、非零元个数行数、列数、非零元个数TSMatrix;5.4.1三元组表三元组表孙克雷制作下面以矩阵的转置为例，说
17、明稀疏矩阵的存储。下面以矩阵的转置为例，说明稀疏矩阵的存储。o一个一个mn的矩阵的矩阵M，它的转置它的转置T是一个是一个nm的矩阵，且的矩阵，且T（i，j）=M（j，i），），1in，1jm，即，即M的行是的行是T的列，的列，T的列是的列是M的行。的行。o将将M转置为转置为T，就是将就是将M的三元组表的三元组表M.data置换为表置换为表T的三的三元组表元组表T.data，如果只是简单地交换如果只是简单地交换M.data中中i和和j的内容，的内容，那么得到的那么得到的T.data将是一个按列优先顺序存储的稀疏矩阵将是一个按列优先顺序存储的稀疏矩阵T，要得到按行优先顺序存储的要得到按行优先顺序存
18、储的T.data，就必须重新排列三元组就必须重新排列三元组的顺序。的顺序。&矩阵的转置矩阵的转置孙克雷制作012900000000000-3000014000240000018000001500-7000M=00-3001512000180900240000000000000-70014000000000T=三三元元组组表表M.data(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(1,3,9)(1,2,12)三三元元组组表表T.data(4,6,-7)(1,6,15)(2,5,18)(3,4,24)(5,3,14)(1,3,-3)(3,1,9
19、)(2,1,12)1234567812345678孙克雷制作由于由于M的列是的列是T的行，按的行，按M.data的列序转置，所得到的转置的列序转置，所得到的转置矩阵矩阵T的三元组表的三元组表T.data必定是按行优先存放。必定是按行优先存放。思路：反复扫描思路：反复扫描M.data中的列序，从小到大依次进行转置。中的列序，从小到大依次进行转置。&矩阵转置方法一矩阵转置方法一(1,3,-3)(1,6,15)(2,1,12)(2,5,18)(3,1,9)(3,4,24)(4,6,-7)(5,3,14)(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(
20、1,3,9)(1,2,12)三三元元组组表表a.data三三元元组组表表b.data1234567812345678孙克雷制作StatusTransPoseSMatrix(TSMatrixM,TSMatrix&N)T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;col+)for(p=1;p=M.tu;p+)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.value=M.datap.value;q+;returnOK;/TranposeSMa
21、trix;&矩阵转置算法矩阵转置算法孙克雷制作678012121139231-333614443245521866115764-78M.datai j v7 6 8 0 1 2 3 4 5 6 7 8T.datai j vppppppppppppppppqqqqq1 3-31 6 152 1 122 5 183 1 93 4 2446-76 3 14col=1col=2&矩阵的转置方法一的演示矩阵的转置方法一的演示孙克雷制作依次把依次把M.data中的元素直接送入中的元素直接送入T.data的恰当位置上（即的恰当位置上（即M三元组的三元组的p指针不回溯）。指针不回溯）。&矩阵转置方法二矩阵转置
22、方法二(1,3,-3)(2,1,12)(2,5,18)(3,1,9)(4,6,-7)(5,3,14)(1,6,15)(3,4,24)(6,4,-7)(6,1,15)(5,2,18)(4,3,24)(3,5,14)(3,1,-3)(1,3,9)(1,2,12)1234567812345678孙克雷制作设两个数组设两个数组numcol：表示矩阵表示矩阵M中第中第col列中非零元个数列中非零元个数cpotcol：指示指示M中第中第col列第一个非零元在列第一个非零元在T.data中位置中位置显然有：显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1;(1colM.nu)&矩
23、阵转置具体实现矩阵转置具体实现1357889colnumcolcpotcol12223241506170012900000000000-3000014000240000018000001500-7000M=孙克雷制作StatusFastTransposeSMatrix（TSMatirxM,TSMatirx&N）T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;col+)numcol=0;for(i=1;i=M.tu;i+)col=M.datai.j;+numcol;cpot1=1;for(col=2;col=M.nu;col+)c
24、potcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;p+)col=M.datap.j;q=cposcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.value=M.datap.value;+cpotcpot colcol;returnOK;&矩阵转置算法矩阵转置算法孙克雷制作&实现过程演示实现过程演示4629753colnumcolcpotcol112232352471580681790678012121139231-333614443245521866115764-78i j v 0 1 2 3 4 5 6
25、7 8i j v7 6 8pppppppp1 3-31 6 152 1 122 5 183 1 93 4 2446-76 3 14孙克雷制作v广义表是线性表的推广。即广义表中放松对表元素的原子限制，广义表是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。容许它们具有其自身结构。v广义表是广义表是n(n0)个元素个元素a1，a2，ai，an的有限序列。的有限序列。其中：其中：ai或者是原子或者是原子(单个元素单个元素)或者是一个广义表。或者是一个广义表。广义表记作广义表记作LS=(a1，a2，ai，an)，LS是广义是广义表的名字，表的名字，n为它的长度。为它的长度。若若
26、ai是广义表，则称它为是广义表，则称它为LS的子表。的子表。注意：注意：广义表通常用圆括号括起来，用逗号分隔其中的元素。广义表通常用圆括号括起来，用逗号分隔其中的元素。若广义表若广义表LS非空非空(n1)，则，则a1是是LS的表头，其余元素的表头，其余元素组成的表组成的表(a2，a3，an)称为称为LS的表尾。的表尾。广义表是递归定义的。广义表是递归定义的。5.5广义表广义表孙克雷制作1.A=()A是一个空表，其长度为零。是一个空表，其长度为零。2.B=(e)表表B只有一个原子只有一个原子e，B的长度为的长度为1。3.C=(a,(b,c,d)表表C的长度为的长度为2，两个元素分别为原子，两个元
27、素分别为原子a和子表和子表(b,c,d)。4.D=(A,B,C)表表D的长度为的长度为3，三个元素都是广义表。显，三个元素都是广义表。显然，将子表的值代入后，则有然，将子表的值代入后，则有D=(),(e),(a,(b,c,d)。5.E=(a,E)这是一个递归的表，它的长度为这是一个递归的表，它的长度为2，E相当于相当于一个无限的广义表一个无限的广义表E=(a,(a,(a,(a,)。5.5.1广义表的定义广义表的定义孙克雷制作由表头、表尾的定义可知：任何一个非空广义表其表头可由表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是广义表，而其表尾必定是广义表。能是原子，也可能是广义表
28、，而其表尾必定是广义表。A=(e)则：则：gethead(A)=egettail(A)=()B=(a,b),c,d,e,f)则：则：gethead(B)=(a,b)gettail(B)=(c,d,e,f)C=(a,(b,c,d)则：则：gethead(C)=agettail(C)=(b,c,d)注意：广义表注意：广义表()和和()不同。前者是长度为不同。前者是长度为0的空表，对的空表，对其不能做求表头的和表尾的运算；而后者是长度为其不能做求表头的和表尾的运算；而后者是长度为1的非空表的非空表(只不过该表中唯一的一个元素是空表只不过该表中唯一的一个元素是空表)。对其可进行分解，。对其可进行分解，
29、得到表头和表尾均为空表得到表头和表尾均为空表()。&广义表表示广义表表示孙克雷制作由于广义表由于广义表(a1,a2,a3,an)中的数据元素可以具有不同中的数据元素可以具有不同的结构的结构(或是原子，或是广义表或是原子，或是广义表)，因此，难以用顺序存储结，因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。点表示。由于广义表中有两种数据元素，原子或广义表，因此，需由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。要两种结构的结点：一种是表结点，一种是原子结点。下面
30、下面介绍两种广义表的链式存储结构。介绍两种广义表的链式存储结构。5.5.2广义表的存储结构广义表的存储结构孙克雷制作方法一：方法一：表结点由三个域组成：标志域、指示表头的指针域和指示表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。表尾的指针域；而原子域只需两个域：标志域和值域。&广义表的存储结构广义表的存储结构表结点表结点原子结点原子结点tag=1 hptptag=0 atom孙克雷制作其类型定义如下：其类型定义如下：typedefenumATOM，LISTElemtag;typedegstructGLNodeElemtagtag;unionatomtypeatom;structstructGLNode*hp,*tp;ptr;*GList;&广义表的存储结构广义表的存储结构孙克雷制作广义表的存储结构示例广义表的存储结构示例10 e110 a10 b10 c10 d11110 a1BDECA=NIL1.A=（）；（）；2.B=（e）；）；3.C=（a,(b,c,d)；4.D=（A，B，C）；）；5.E=（a，E）&广义表的存储结构广义表的存储结构