数据结构 数组和广义表幻灯片.ppt

数据结构数据结构 数组和数组和广义表广义表第1页，共27页，编辑于2022年，星期六n n一维数组具有线性表的结构，但操作简单，一般不一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和进行插入和删除操作，只定义给定下标读取元素和修改元素的操作修改元素的操作n n二维数组中，每个数据元素对应一对数组下标，在二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。是以线性表为数据元素的线性表。n nn维数组中，每个数据元素对应维数组中，每个数据元素对应n个下标，受个下标，受n个关个关系的制约，其中任一个关系都是线性关系。可看作系的制约，其中任一个关系都是线性关系。可看作是数据元素为是数据元素为n-1维数组的一维数组。维数组的一维数组。n n因此，多维数组和广义表是对线性表的扩展：线性因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。表中的数据元素本身又是一个多层次的线性表。第2页，共27页，编辑于2022年，星期六n5.1 数组的定义n5.2 数组的顺序表示和实现n5.3 矩阵的压缩存储第3页，共27页，编辑于2022年，星期六5.1 数组的定义数组的定义nADT Array数据对象：ji=0,bi-1,i=1,2,n,uD=aj1j2jn|n(0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标，aj1j2jnElemSet数据关系：R=R1,R2,RnRi=|0jkbk-1,1kn 且ki,0jibi-2,aj1jijn,aj1ji+1jnD,i=2,n第4页，共27页，编辑于2022年，星期六 基本操作：uInitArray(&A,n,bound1,boundn)uDestroyArray(&A)uValue(A,&e,index1,indexn)uAssign(&A,e,index1,indexn)ADT Array第5页，共27页，编辑于2022年，星期六5.2 数组的顺序表示数组的顺序表示n n多维数组用一维的存储单元存放需约定次序。多维数组用一维的存储单元存放需约定次序。PASCAL和和C语言是以行序为主序，语言是以行序为主序，FORTRAN以以列序为主序。列序为主序。n n给定维数和各维长度，数组的存储空间确定。给定维数和各维长度，数组的存储空间确定。n n二维数组中任一元素二维数组中任一元素aij的存储地址的存储地址:uuLoc(i,j)=Loc(0,0)+(b2*i+j)*Ln nn维数组：教材维数组：教材p93uuLocLoc（j1,j2,jn)=Loc(0,0,0)+j1,j2,jn)=Loc(0,0,0)+ci ij ji iuu其中其中其中其中 c cn n=L,c=L,ci-1i-1=b=bi i*c*ci i,1i,1in n第6页，共27页，编辑于2022年，星期六类型定义类型定义n#include n#define MAX_ARRAY_DIM 8ntypedef structuElemType*base;uint dim;uint*bounds;uint*constants;nArray;第7页，共27页，编辑于2022年，星期六5.3 矩阵的压缩存储矩阵的压缩存储n n矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。n n压缩存储：为多个值相同的元只分配一个存储空间，压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间。对零元不分配空间。n n特殊矩阵：值相同的元素或者零元素在矩阵中的分布特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律有一定规律n n稀疏矩阵：非零元较零元少，且分布没有一定规律的稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵矩阵第8页，共27页，编辑于2022年，星期六5.3.1.特殊矩阵特殊矩阵n n对称矩阵：对称矩阵：对称矩阵：对称矩阵：aij=aji 1 aij=aji 1 i,ji,j n nuu压缩存储方法：为每一对对称元分配一个存储空间压缩存储方法：为每一对对称元分配一个存储空间压缩存储方法：为每一对对称元分配一个存储空间压缩存储方法：为每一对对称元分配一个存储空间FF将下三角的元素，按行存储到一维数组将下三角的元素，按行存储到一维数组将下三角的元素，按行存储到一维数组将下三角的元素，按行存储到一维数组sasa中中中中FF共有共有共有共有n(n+1)/2n(n+1)/2个存储单元，个存储单元，个存储单元，个存储单元，FFaijaij在一维数组中的位置在一维数组中的位置在一维数组中的位置在一维数组中的位置k k为：为：为：为：i(i-1)/2+j-1 i(i-1)/2+j-1 当当当当i=j i=j 否则否则否则否则 j(j-1)/2+i-1 j(j-1)/2+i-1n n三角矩阵：三角矩阵：三角矩阵：三角矩阵：上（下）三角中的元均为常数上（下）三角中的元均为常数上（下）三角中的元均为常数上（下）三角中的元均为常数c c或或或或0 0uu压缩存储方法：同上，只存储上（下）三角元素。压缩存储方法：同上，只存储上（下）三角元素。压缩存储方法：同上，只存储上（下）三角元素。压缩存储方法：同上，只存储上（下）三角元素。uu下三角：下三角：下三角：下三角：k=i*(i-1)/2+j-1k=i*(i-1)/2+j-1uu上三角：上三角：上三角：上三角：k=(2n-i)(i-1)/2+j-1 (k=(2n-i)(i-1)/2+j-1 (按行按行按行按行)k=j(j-1)/2+i-1 k=j(j-1)/2+i-1（按列）（按列）（按列）（按列）uu注意：注意：注意：注意：k k从零开始，从零开始，从零开始，从零开始，i,ji,j从从从从1 1开始开始开始开始n n对角矩阵：所有非零元都集中在以主对角线为中心的带状区域对角矩阵：所有非零元都集中在以主对角线为中心的带状区域对角矩阵：所有非零元都集中在以主对角线为中心的带状区域对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。中。中。中。uu压缩方法：压缩存储到一维数组压缩方法：压缩存储到一维数组压缩方法：压缩存储到一维数组压缩方法：压缩存储到一维数组sa sa 中，三对角矩阵有中，三对角矩阵有中，三对角矩阵有中，三对角矩阵有3n-23n-2个元素。个元素。个元素。个元素。uuk=2*i+j-3 k=2*i+j-3 第9页，共27页，编辑于2022年，星期六5.3.2.稀疏矩阵稀疏矩阵1.三元组的表示三元组的表示uu 稀疏矩阵可由表示非零元的三元组及其行列数稀疏矩阵可由表示非零元的三元组及其行列数稀疏矩阵可由表示非零元的三元组及其行列数稀疏矩阵可由表示非零元的三元组及其行列数 唯一确定。唯一确定。唯一确定。唯一确定。uu t t个非零元，个非零元，个非零元，个非零元，t/(m*n)t/(m*n)称为稀疏因子称为稀疏因子称为稀疏因子称为稀疏因子 0.05 mu*nu,mu*nu,则不必用三元组表示则不必用三元组表示则不必用三元组表示则不必用三元组表示 mu,nu,tumu,nu,tu第14页，共27页，编辑于2022年，星期六(3)三元组表稀疏矩阵的转置运算三元组表稀疏矩阵的转置运算n n方法：按照方法：按照b.data中的三元组的次序，即中的三元组的次序，即M的列序，依次在的列序，依次在a.data中找到相应的三中找到相应的三元组进行转置。元组进行转置。n n步骤：从步骤：从k=1开始依开始依次扫描找寻所有列号为次扫描找寻所有列号为k的项，将其行号变列号、列号变行号，的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。顺次存于转置矩阵三元组表。n n其时间复杂度为其时间复杂度为 O(a.nu*a.tu)。n n例：若矩阵有例：若矩阵有200行，行，200列，列，10,000个非个非零元素，总共有零元素，总共有2,000,000次处理。次处理。第15页，共27页，编辑于2022年，星期六稀疏矩阵的转置稀疏矩阵的转置 (算法算法5.1)Status TransposeSMatrix(TSMatrix M,TSMatrix&T)int q,col,p;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=T.mu;+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.e=M.datap.e;+q;return OK;第16页，共27页，编辑于2022年，星期六快速转置算法快速转置算法n n方法：按方法：按a.data中三元组的次序进行转置，并将转中三元组的次序进行转置，并将转置后的三元组置入置后的三元组置入b中恰当的位置。中恰当的位置。n n建立辅助数组建立辅助数组num和和cpot，numcol表示矩阵第表示矩阵第col列中非零元的个数，列中非零元的个数，cpotcol指示第指示第col列的第一个列的第一个非零元素在非零元素在b.data中的恰当位置。中的恰当位置。n n按行扫描矩阵三元组表，根据某项的列号，确定它按行扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查转置后的行号，查cpot表，按查到的位置直接将该表，按查到的位置直接将该项存入转置三元组表中。项存入转置三元组表中。n n转置时间复杂度为转置时间复杂度为 O(nu+tu+nu+tu)=O(tu)。若矩。若矩阵有阵有200列，列，10000个非零元素，总共需个非零元素，总共需10000次处次处理。理。第17页，共27页，编辑于2022年，星期六n ncpot1=1n ncpotcol=cpotcol-1+numcol-1第18页，共27页，编辑于2022年，星期六稀疏矩阵的快速转置稀疏矩阵的快速转置(算法算法5.2)Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)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(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;return OK;第19页，共27页，编辑于2022年，星期六2.十字链表十字链表n n当矩阵中非零元素的当矩阵中非零元素的个数个数和和位置位置经过运经过运算后算后变化较大变化较大时，就不宜采用顺序存储结时，就不宜采用顺序存储结构，而应采用构，而应采用链式存储结构链式存储结构来表示三元组。来表示三元组。n n稀疏矩阵的链接表示采用十字链表：稀疏矩阵的链接表示采用十字链表：行链行链表表与与列链表列链表十字交叉。十字交叉。n n行链表与列链表都是行链表与列链表都是带表头结点的循环链带表头结点的循环链表表。用表头结点表征是第几行，第几列。用表头结点表征是第几行，第几列。第20页，共27页，编辑于2022年，星期六n n元素结点元素结点uright指向同一行中下一个非零元素的指针（向右域）udown指向同一列中下一个非零元素的指针（向下域）n n表头结点表头结点u行表头结点u列表头结点unext用于表示头结点的链接rowcolvaldownrightcol=0 nextrightrow=0nextdown第21页，共27页，编辑于2022年，星期六n由于行、列表头结点由于行、列表头结点互相不冲突，所以可互相不冲突，所以可以合并起来：以合并起来：n总表头结点：总表头结点：row=0 col=0 nextdownrightrowcolnext第22页，共27页，编辑于2022年，星期六类型定义：类型定义：类型定义：类型定义：typedef struct typedef struct int i,j;/int i,j;/非零元的行下标和列下标非零元的行下标和列下标非零元的行下标和列下标非零元的行下标和列下标ElemType e;ElemType e;Triple;Triple;typedef struct OLNode typedef struct OLNode /元素结点元素结点元素结点元素结点union Triple triple;OLNode*next;union Triple triple;OLNode*next;struct OLNode*right,*down;struct OLNode*right,*down;/该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域OLNode,*OLink;OLNode,*OLink;OLink MOLink M；第23页，共27页，编辑于2022年，星期六稀疏矩阵的十字链表表示的示例稀疏矩阵的十字链表表示的示例第24页，共27页，编辑于2022年，星期六n n需要辅助结点作链表的表头，同时每个结点要增加需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。起到节省空间的效果。n n分别用两个一维数组存储行链表的头指针和列链表分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。的头指针，可加快访问速度。第25页，共27页，编辑于2022年，星期六十字链表的类型定义十字链表的类型定义typedef struct OLNode /元素结点元素结点int i,j;/非零元的行和列下标非零元的行和列下标ElemType e;struct OLNode*right,*down;/该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域该非零元所在行表和列表的后继链域 OLNode,*OLink;typedef struct OLink*rhead,*chead;/行和列链表头指针数组行和列链表头指针数组行和列链表头指针数组行和列链表头指针数组int mu,nu,tu;CrossList;第26页，共27页，编辑于2022年，星期六十字链表的建立十字链表的建立(算法算法5.4)n自学第27页，共27页，编辑于2022年，星期六