第三章 多维数组和广义表.ppt

《第三章 多维数组和广义表.ppt》由会员分享，可在线阅读，更多相关《第三章 多维数组和广义表.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 多维数组和广义表多维数组和广义表 数组可以看成是一种特殊的线性表，即线性表中数据元数组可以看成是一种特殊的线性表，即线性表中数据元数组可以看成是一种特殊的线性表，即线性表中数据元数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表。素本身也是一个线性表。素本身也是一个线性表。素本身也是一个线性表。例如二维数组例如二维数组例如二维数组例如二维数组()()()()()()()()()3.1多维数组多维数组 数组的两种顺序存储结构数组的两种顺序存储结构数组的两种顺序存储结构数组的两种顺序存储结构l l以行序为主序（行优先顺序）以行序为主序（行优先顺序）以行序为主序（行优

2、先顺序）以行序为主序（行优先顺序）l l以列序为主序（列优先顺序）以列序为主序（列优先顺序）以列序为主序（列优先顺序）以列序为主序（列优先顺序）数组特点数组特点数组特点数组特点 数组结构固定数组结构固定数组结构固定数组结构固定 数据元素同构数据元素同构数据元素同构数据元素同构数组运算数组运算数组运算数组运算 给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值给定一组下标，修改数据元素的值Loc(aij)=Loc(a11)+(i

3、-1)*n+(j-1)*d按行序为主序存放按行序为主序存放 amn .am2 am1 .a2n .a22 a21 a1n .a12 a11a11a12.a1na21a22.a2nam1am2.amn.若行列下标均从若行列下标均从0开始，则开始，则Loc(aij)=Loc(a00)+(i*n+j)*d am-1n-1 .am-11 am-10 .a1n-1 .a11 a10 a0n-1 .a01 a00按列序为主序存放按列序为主序存放 amn .a2n a1n .am2 .a22 a12 am1 .a21 a11Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*da11a12.a1

4、na21a22.a2nam1am2.amn.am-1n-1 .a1n-1 a0n-1 .am-11 .a11 a01 am-10 .a10 a00若行列下标均从若行列下标均从0开始，则开始，则Loc(aij)=Loc(a00)+(j*m+i)*d3.2 矩阵的压缩存储矩阵的压缩存储3.2.13.2.1 特殊矩阵特殊矩阵特殊矩阵特殊矩阵1.1.对称矩阵对称矩阵对称矩阵对称矩阵a00a01.a0n-1a10a11.a1n-1an-10an-11.an-1n-1.k=0 1 2 3 4 5 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：0in,0jn,(aij=aji)a00a

5、10a11a20a21a22.an-1,0.an-1,n-12.2.三角矩阵三角矩阵三角矩阵三角矩阵(下三角下三角下三角下三角)a00c c.ca10a11c.can-10an-11an-12.an-1n-1.cLoc(aij)=Loc(a00)+i(i+1)/2+j*d共占用n(n+1)/2+1个单元按行序为主序按行序为主序：k=0 1 2 3 4 5 n(n-1)/2 n(n+1)/2-1 a00a10a11a20a21a22.an-1,0.an-1,n-1c 三角矩阵三角矩阵三角矩阵三角矩阵(上三角上三角上三角上三角)a00a01a02.a0,n-1ca11a12.a1,n-1cccan

6、-1,n-1.Loc(aij)=Loc(a00)+i(2n-i+1)/2+j-i*d按行序为主序：按行序为主序：k=0 1 2 n-1 n(n+1)/2-1 n(n+1)/2共占用n(n+1)/2+1个单元前i 行上三角元素个数：n+(n-1)+.(n-i+1)=i(n+n-i+1)/2=i(2n-i+1)/2a00a01a02.a0n-1a11a12.an-1n-1c3 3对角矩阵对角矩阵对角矩阵对角矩阵a00a010.0a10a11a120000an-2,n-3an-2,n-2an-2,n-100 an-1,n-2an-1,n-10a21a22a2300按行序为主序：按行序为主序：k=0

7、1 2 3 4 5 6 7 3(n-1)-1 3(n-1)a00a01a10a11a12a21a22a23.an-1,n-2an-1,n-13.2.2 特殊矩阵的抽象数据类型特殊矩阵的抽象数据类型ADT ADT SpecialSpecialMatrixMatrix is is Data:Data:特殊矩阵线性表（特殊矩阵线性表（a a1 1,a,an n,a,an+1n+1),),MatrixMatrix为类型描述符为类型描述符 Operations:Operations:void void InitInitMatrixMatrix(MatrixMatrix&m,&m,intint type,

8、type,intint n);/n);/初始化初始化 ElemTypeElemType GetGetMatrixMatrixElemElem(MatrixMatrix m,m,intint i,i,intint j);/j);/取元素取元素 Void Void SetSetMatrixMatrixElemElem(MatrixMatrix&m,&m,intint i,i,intint j,j,ElemTypeElemType v);/v);/赋元素值赋元素值 Void Void ClearClearMatrixMatrix (MatrixMatrix&m);&m);清除特殊矩阵清除特殊矩阵en

9、d end SpecialSpecialMatrixMatrixstructstruct Matrix /Matrix /特殊矩阵线性表数据类型特殊矩阵线性表数据类型 ElemTypeElemType*data;/*data;/定义线性表向量指针定义线性表向量指针 intint type,size;/type,size;/特殊矩阵类型和规模特殊矩阵类型和规模;/;/type=1type=1对称矩阵；对称矩阵；type=2type=2下三角矩阵；下三角矩阵；type=3type=3上三角矩阵上三角矩阵3.2.3 特殊矩阵基本算法描述特殊矩阵基本算法描述 void void InitInitMat

10、rixMatrix(MatrixMatrix&m,&m,intint type,type,intint size);/size);/初始化初始化 intint row,row,colcol,value,n=,value,n=size(size+1)/2;m.type=type;m.type=type;m.size=size;m.size=size;m.data=new ElemTypen+1;m.data=new ElemTypen+1;for(for(intint i=0;i=0;i irowrowcolcolvalue;value;SetSetMatrixMatrixElemElem(m,

11、row,(m,row,colcol,value);,value);if(m.type=2)if(m.type=2)cincinvalue;/value;/输入上三角相同值输入上三角相同值 SetSetMatrixMatrixElemElem(m,1,2,value);/(m,1,2,value);/给上三角赋值给上三角赋值 if(m.type=3)/if(m.type=3)/输入下三角相同值输入下三角相同值 cincinvalue;value;SetSetMatrixMatrixElemElem(m,2,1,value);/(m,2,1,value);/给下三角赋值给下三角赋值 ElemTyp

12、eElemType GetGetMatrixMatrixElemElem(MatrixMatrix m,m,intint i,i,intint j);j);/取取特殊矩阵特殊矩阵元素元素 if(m.type=1)/if(m.type=1)/对称矩阵 if(i=j)return m.dataiif(i=j)return m.datai(i+1)/2+j;(i+1)/2+j;else return m.dataj else return m.dataj(j+1)/2+i;(j+1)/2+i;else if(m.type=2)/else if(m.type=2)/下三角矩阵 if(i=j)retur

13、n m.dataiif(i=j)return m.datai(i+1)/2+j);(i+1)/2+j);else return m.datam.size else return m.datam.size(m.size+1)/2;(m.size+1)/2;else /else /上三角矩阵 if(j=i)return m.dataiif(j=i)return m.datai(2(2 m.size-i+1)/2+j-i;m.size-i+1)/2+j-i;else return m.datam.size else return m.datam.size(m.size+1)/2;(m.size+1)

14、/2;Void Void SetSetMatrixMatrixElemElem(MatrixMatrix&m,&m,intint i,i,intint j,j,ElemTypeElemType v)v)/赋赋特殊矩阵特殊矩阵元素值元素值 if(m.type=1)/if(m.type=1)/对称矩阵 if(i=j)m.dataiif(i=j)m.datai(i+1)/2+j=v;(i+1)/2+j=v;else m.dataj else m.dataj(j+1)/2+i=v;(j+1)/2+i=v;else if(m.type=2)/else if(m.type=2)/下三角矩阵 if(i=j)

15、m.dataiif(i=j)m.datai(i+1)/2+j)=v;(i+1)/2+j)=v;else m.datam.size else m.datam.size(m.size+1)/2=v;(m.size+1)/2=v;else /else /上三角矩阵 if(j=i)m.dataiif(j=i)m.datai(2(2 m.size-i+1)/2+j-i=v;m.size-i+1)/2+j-i=v;else m.datam.size else m.datam.size(m.size+1)/2=v;(m.size+1)/2=v;Void Void ClearClearMatrixMatrix

16、 (MatrixMatrix&m)/&m)/清除特殊矩阵清除特殊矩阵 m.type=-1;m.size=0;delete m.data;稀疏矩阵的压缩存储原则：只存矩阵的行列数和每个非零元的行列下稀疏矩阵的压缩存储原则：只存矩阵的行列数和每个非零元的行列下标及其值。矩阵标及其值。矩阵MM可可由由(0 0,1 1,12),(,12),(0 0,2 2,9),(,9),(2 2,0 0,-3),(,-3),(2 2,5 5,14),(,14),(3 3,2 2,24),24),(4 4,1 1,18),18),(5 5,0 0,15),(,15),(5 5,3 3,-7),-7)和矩阵和矩阵行列数

17、行列数(6,76,7)唯一确定唯一确定。定义：若矩阵的非零元素个数远远少于它的零元素个数，且定义：若矩阵的非零元素个数远远少于它的零元素个数，且非零元素的分布没有一定规律，则该矩阵为稀疏矩阵。非零元素的分布没有一定规律，则该矩阵为稀疏矩阵。3.2.4 稀疏矩阵稀疏矩阵稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法1.1.三元组表（顺序存储结构）三元组表（顺序存储结构）三元组表（顺序存储结构）三元组表（顺序存储结构）#define define MaxTermsMaxTerms 100/100/非零元素的最大个数非零元素的最大个数typedeftyped

18、ef intint ElemTypeElemType;structstruct Triple Triple intint row,row,colcol;/;/行号、列号行号、列号 ElemType valElemType val;/;/非零元素非零元素;structstruct SMatrixSMatrix intint m,n,t;/m,n,t;/行数、列数、非零元素个数行数、列数、非零元素个数 Triple dataMaxTerms+1;/Triple dataMaxTerms+1;/结点数组结点数组;row col val0 1 2 3 4 5 6 7行列下标非零元值 m n t dat

19、a +SMatrixMM矩阵的三元组存储结构矩阵的三元组存储结构矩阵的三元组存储结构矩阵的三元组存储结构011202920-32514322441185 01553-7678求转置矩阵求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表。矩阵的三元组表。矩阵的三元组表。矩阵的三元组表。问题分析：转置矩阵问题分析：转置矩阵问题分析：转置矩阵问题分析：转置矩阵B B B B中的元素中的元素中的元素中的元素b b b bijiji

20、jij即为即为即为即为矩阵矩阵矩阵矩阵A A A A中的元素中的元素中的元素中的元素a a a ajijijiji。B B B B的行数等于的行数等于的行数等于的行数等于A A A A的列数，的列数，的列数，的列数，B B B B的列数等于的列数等于的列数等于的列数等于A A A A的行数的行数的行数的行数 ，将，将，将，将A A A A三元组中三元组中三元组中三元组中的的的的i i i i和和和和j j j j互换后拷贝到互换后拷贝到互换后拷贝到互换后拷贝到B B B B三元组中三元组中三元组中三元组中，重排重排重排重排B B B B三元组次序，使其三元组次序，使其三元组次序，使其三元组次序

21、，使其中元素以中元素以中元素以中元素以i i i i（行行行行)为主序。为主序。为主序。为主序。121213931-3361443245218611564-7211231913-3631434242518161546-713-3161521122518319342446-76314拷贝排序 row col valA row col valBrow col valBSMatrixSMatrix *TransMatTransMat(SMatrixSMatrix *a)/a)/求矩阵求矩阵a a转置矩阵转置矩阵b b intint colcol,n;,n;SMatrixSMatrix *b=new

22、SMatrix1;/b=new SMatrix1;/为转置矩阵为转置矩阵B B申请内存申请内存 b bm=am=an;n;b bn=an=am;m;b bt=at=at;t;if(b if(bt=0)return b;t=0)return b;for(for(colcol=1,n=1;=1,n=1;colcol=a=am;m;colcol+)/+)/按按A A的列次序拷贝的列次序拷贝 for(for(intint k=1;k=a k=1;k=at;k+)/t;k+)/扫描整个三元组扫描整个三元组 if(aif(adatak.datak.colcol=colcol)/)/拷贝第拷贝第colcol

23、列的列的三元组三元组 b bdatan.datan.colcol=a=adatak.row;datak.row;b bdatan.row=adatan.row=adatak.datak.colcol;b bdatan.datan.valval=a=adatak.datak.valval;n+;n+;return b;return b;/算法分析：算法分析：T(n)=O(AT(n)=O(A的列数的列数 非零元个数非零元个数)矩阵转置的改进算法矩阵转置的改进算法矩阵转置的改进算法矩阵转置的改进算法 按按a a中三元组次序一次转置并拷贝到中三元组次序一次转置并拷贝到b b三元组三元组中中，将，将a

24、a中的中的每个三元组转置后放入每个三元组转置后放入b b中恰当位置中恰当位置，此法关键是要预先确此法关键是要预先确定定a a中每一列第一个非零元在中每一列第一个非零元在b b中位置，为确定这些位置，转中位置，为确定这些位置，转置前应先求得置前应先求得a a中每一列的非零元个数。中每一列的非零元个数。121213931-3361443245218611564-7 row col val222101135788列 元素个数 b中起始位置123456121213931-33614432452186 11564-713-3161521122518319342446-76314135788b中起始位置A

25、B 1 2 3 4 5 6 row col val row col valSMatrixSMatrix *TransMatTransMat(SMatrixSMatrix *a)/a)/矩阵矩阵a a转置改进算法转置改进算法 intint *pos=new intapos=new intan+1n+1;SMatrixSMatrix *b=new SMatrix1;/b=new SMatrix1;/为转置矩阵为转置矩阵B B申请内存申请内存 b bm=am=an;n;b bn=an=am;m;b bt=at=at;t;if(b if(bt=0)return b;t=0)return b;for(f

26、or(intint k=0;k=a k=0;k=an;k+)posk=0;n;k+)posk=0;for(for(intint k=1;k=a k=1;k=at;k+)/t;k+)/扫描三元组扫描三元组a a posa posadatak.datak.colcol+;/A+;/A各列非各列非0 0元素计数元素计数 intint add=1;add=1;for(for(intint k=1;k=b k=1;k=bm;k+)/m;k+)/计算计算B B三元组各行起始位置三元组各行起始位置 intint n=posk;posk=add;add+=n;n=posk;posk=add;add+=n;fo

27、r(for(intint k=1;k=a k=1;k=at;k+)/t;k+)/扫描三元组扫描三元组 intint n=posa n=posadatak.datak.colcol+;+;b bdatan.row=adatan.row=adatak.datak.colcol;b bdatan.datan.colcol=a=adatak.row;datak.row;b bdatan.datan.valval=a=adatak.datak.valval;return b;return b;/算法分析：算法分析：T(n)=O(2T(n)=O(2 非零元个数非零元个数+行数行数+列数列数)在十字链表中，

28、每一个非零元素用一个结点表示，分别在十字链表中，每一个非零元素用一个结点表示，分别存放该元素的行、列、元素值、指向本行下一非零元素的指存放该元素的行、列、元素值、指向本行下一非零元素的指针、指向本列下一非零元素的指针。为索引各行和各列的第针、指向本列下一非零元素的指针。为索引各行和各列的第一个非零元素，设置一组同样结构的行列头结点，每个头结一个非零元素，设置一组同样结构的行列头结点，每个头结点的行指针指向本行第一个非零元结点，列指针指向本列第点的行指针指向本行第一个非零元结点，列指针指向本列第一个非零元结点，若本行或本列无非零元，则相应指针域为一个非零元结点，若本行或本列无非零元，则相应指针域

29、为空。十字链表结点类型定义如下：空。十字链表结点类型定义如下：structstruct MatLink MatLink intint row,row,colcol;MatLinkMatLink*down,down,*right;right;ElemTypeElemType value;value;2.2.十字链表（链式存储结构）十字链表（链式存储结构）十字链表（链式存储结构）十字链表（链式存储结构）l l稀疏矩阵的结点稀疏矩阵的结点稀疏矩阵稀疏矩阵元素结点元素结点rightvaluedownrawcol稀疏矩阵的正交链表表示示例稀疏矩阵的正交链表表示示例稀疏矩阵的正交链表表示示例稀疏矩阵的正交

30、链表表示示例 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 00 03 2 -21 5 81 2 50 02 3 32 1 14 1 60 0建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表建立稀疏矩阵的十字链表MatLinkMatLink *CreateLinkMatCreateLinkMat()()MatLinkMatLink *p,p,*q,q,*cp;cp;int int i,j,m,n,t,s;i,j,m,n,t,s;ElemTypeElemType v;v;coutcout输入行数、列数、非零元素个数输入行数、列数、非零元素个数”mnt;mnt;s=

31、(mn)?m:n;s=(mn)?m:n;cp=new cp=new MatLinkMatLink*s+1;/s+1;/开辟头指针数组开辟头指针数组 cp0=new cp0=new MatLinkMatLink;cp0 cp0row=m;cp0row=m;cp0col=n;col=n;for(i=1;i=s;i+)/for(i=1;i=s;i+)/构造头结点单链表构造头结点单链表 cpi=new cpi=new MatLinkMatLink;cpi cpirow=cpirow=cpicolcol=0;=0;cpi cpiright=cpiright=cpidown=cpi;/down=cpi;/

32、初始指向自身初始指向自身 for(i=1;i=t;i+)for(i=1;i=t;i+)coutcout”输入行、列、元素值输入行、列、元素值”ijv;ijv;p=p=new new MatLinkMatLink;p prow=i;row=i;p pcolcol=j;=j;p pvalue=v;value=v;q=cpi;/q=cpi;/取取i i行表头行表头 while(qwhile(qright!=cpi&qright!=cpi&qrightrightcolcolj)/j)/判判q q的下一个的下一个 q=qq=qright;/right;/寻找行插入位置寻找行插入位置 p pright=q

33、right=qright;/right;/插入操作插入操作(q q结点之后结点之后)q qright=p;right=p;q=cpj;/q=cpj;/取取j j列表头列表头 while(qwhile(qdown!=cpj&qdown!=cpj&qdowndownrowi)row0时，时，表的第一个表元素表的第一个表元素a1称为广义表的称为广义表的表头表头(head)，除此之外，其它表元素组成的表除此之外，其它表元素组成的表(a2,a3,an)称为广义表的称为广义表的表尾表尾(tail)。3.3 广义表的概念广义表的概念广义表的特性广义表的特性l有次序性有次序性l有长度有长度l有深度有深度l l

34、可递归可递归l l可共享可共享A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F)各种广义表的示意图各种广义表的示意图广义表的表示广义表的表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示只包括整数和字符型数据的广义表链表表示 表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示表中套表情形下的广义表链表表示广义表结点定义广义表结点定义l l标志域标志域 utype,表明结点类型。表明结点类型。0为表头结点，为表头结点，1 为整型原子结点，为整型原子

35、结点，2为字符型原子结点，为字符型原子结点，3为子表为子表结点。结点。l l值域值域 value。当当 utype=0 时为时为表引用计数表引用计数，=1时为时为整数值整数值，=2 时为时为字符值字符值，=3 时为时为指向子指向子表的表头结点的指针表的表头结点的指针。l l尾指针域尾指针域 tlink。当当 utype=0 时为指向该表表时为指向该表表头元素的指针；当头元素的指针；当 utype 0 时为指向同一层下时为指向同一层下一个表结点的指针。一个表结点的指针。utype=0/1/2/3value=ref/intgrinfo/charinfo/hlink tlink广义表的带表头结点的存

36、储表示广义表的带表头结点的存储表示广义表结点类型定义广义表结点类型定义Struct GLNode unsigned char utype;union ElemType data;GLNode*sublist;GLNode*next;作业作业1.1.分别用两个一维数组存放一个上三角矩阵和一个下三角矩阵，完分别用两个一维数组存放一个上三角矩阵和一个下三角矩阵，完成两矩阵的乘法并输出结果成两矩阵的乘法并输出结果(使用特殊矩阵基本算法使用特殊矩阵基本算法)。2.2.用三元组存放输入的两个稀疏矩阵用三元组存放输入的两个稀疏矩阵A A3434和和B B3434，将稀疏矩阵将稀疏矩阵A A转置后转置后与稀疏矩阵与稀疏矩阵B B相乘，结果存放三元组相乘，结果存放三元组C C，并输出结果。并输出结果。3.3.输入并建立两个稀疏矩阵输入并建立两个稀疏矩阵A A和和B B的十字链表的十字链表,输出稀疏矩阵输出稀疏矩阵,两完两完成两稀疏矩阵的加法运算成两稀疏矩阵的加法运算,结果存放在稀疏矩阵结果存放在稀疏矩阵A A中中,要求相加结要求相加结果为果为0 0的元素从结果稀疏矩阵的十字链表中删除的元素从结果稀疏矩阵的十字链表中删除,输出输出A A稀疏矩阵。稀疏矩阵。