8数据结构

数据结构与算法数组的定义数组的顺序存储结构矩阵的压缩存储广义表的定义广义表的存储结构第五章数组和广义表数据结构2第一节数组的定义数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表定义mnmmnnnmaaaaaaaaaA.................................212222111211数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值()()()()()()()()()数据结构3第二节数组的顺序存储结构次序约定以行序为主序以列序为主序a11a12……..a1na21a22……..a2nam1am2……..amn………………….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*la12…a1na11a22…a2na21am2…annan1…a21…am1a11a22…am2a12a2n…amna1n…Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l数据结构4第三节矩阵的压缩存储对称矩阵三角矩阵对角矩阵稀疏矩阵稀疏矩阵的压缩存储方法数据结构5对称矩阵jiijjjijiik,12/)1(12/)1(，a11a12….……..a1na21a22……..…….a2nan1an2……..ann………………….a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：数据结构6三角矩阵a1100……..0a21a220……..0an1an2an3……..ann………………….0Loc(aij)=Loc(a11)+[(+(j-1)]*li(i-1)2a11a21a22a31a32an1ann…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：数据结构7对角矩阵a11a120…………….0a21a22a230……………000…an-1,n-2an-1,n-1an-1,n00……an,n-1ann.0a32a33a340………0……………………………Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11a12a21a22a23ann-1ann…...…...k=012343(n-1)按行序为主序：数据结构8稀疏矩阵7600070015000001800000240001400003000000000009120MM由{(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）唯一确定定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值数据结构9稀疏矩阵的压缩存储方法三元组表#defineM20typedefstructnode{introl,col;intval;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数678121213931-3361443245218611564-7maijv012345678ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数行列下标非零元值7600070015000001800000240001400003000000000009120M数据结构10增加一个辅助数组NRA[m+1],其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）显然有：NRA[1]=1NRA[i]=NRA[i-1]+第i-1行非零元个数(i2)0123456NRA133567678212391-36143242181154-7majv012345678矩阵列数和非零元个数列下标和非零元值NRA[0]不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+17600070015000001800000240001400003000000000009120M带辅助行向量的二元组表数据结构11伪地址表示法伪地址：本元素在矩阵中（包括零元素在内）按行优先顺序的相对位置672123915-3201424243018361539-7maaddrv伪地址非零元值矩阵行列维数012345678伪地址表示法需存储单元个数为2(t+1)7600070015000001800000240001400003000000000009120M数据结构12问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;coln;col++)for(row=0;rowm;row++)n[col][row]=m[row][col];T(n)=O(mn)求转置矩阵数据结构137600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N678121213931-3361443245218611564-7ijv012345678maijv76813-3161521122518319342446-76314012345678mb?数据结构14解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以N的行(M的列)为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序算法分析：T(n)=O(M的列数n非零元个数t)若t与mn同数量级，则)()(2nmOnT数据结构15678121213931-3361443245218611564-7ijv012345678ma76813-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2数据结构16方法二：快速转置即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数实现：设两个数组num[col]：表示矩阵M中第col列中非零元个数cpot[col]：指示M中第col列第一个非零元在mb中位置显然有：cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1];(2colma[0].j)1357889colnum[col]cpot[col]122232415061707600070015000001800000240001400003000000000009120M数据结构17算法分析：T(n)=O(M的列数n+非零元个数t)若t与mn同数量级，则T(n)=O(mn)数据结构18678121213931-3361443245218611564-7ijv012345678maijv012345678mbcolnum[col]cpot[col]11223235247158068179076813-3161521122518319342446-76314pppppppp4629753数据结构19带行指针向量的单链表表示每行的非零元用一个单链表存放设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;0200000000000210010070003A^13573-11-12-242^^^^需存储单元个数为3t+m链式存储结构数据结构20设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义typedefstructnode{introw,col,val;structnode*down,*right;}JD;rowcolvaldownright34008000450003A113418225234^^^^^^^十字链表数据结构21418^^234^^m=4,n=31,1,32,2,52,3,44,1,82,1,7113^^217^^225^^从键盘接收信息建立十字链表算法数据结构22第四节广义表的定义顾名思义，广义表是线性表的推广，也有人称之为列表(Lists用复数形式以示与统称的表list的区别)。LS=(a1,a2,…,an)其中,LS是广义表(a1,a2,…,an)的名称,n是它的长度。在线性表的定义中，ai(1≤i≤n)只限于是单个元素。而在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子。当广义表LS非空时，称第一个元素a1为LS的表头(Head)，称其余元素组成的表为LS的表尾(Tall)。数据结构23广义表的定义广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。数据结构24广义表的特征根据前述对表头、表尾的定义可知：任何一个非空列表其表头可能是原子，也可能是列表．而其表尾是必定为列表。值得提醒的是列表()和(())不同。前者为空表．长度n＝0;后者长度n＝1，可分解得到其表头、表尾均为空表()。数据结构25第五节广义表的存储结构通常采用链式存储结构每个数据元素可用一个结点表示数据结构26广义表的存储例1在这种存储结构中有几种情况：(1)除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hP域指示列表表头(或为原子结点，或为表结点)，tp域指向列表表尾(除非表尾为空，则指针为空，否则必为表结点)；(2)容易分清列表中原子和子表所在层次。(3)最高层的表结点个数即为列表的长度。数据结构27广义表的链式存储2扩展的线性表表示数据结构28广义表的存储例2