《第五章 数组`特殊矩阵和广义表 51 多维数组.ppt》由会员分享，可在线阅读，更多相关《第五章 数组`特殊矩阵和广义表 51 多维数组.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第五章 数组、特殊矩阵和广义表5.1 多维数组5.2 特殊矩阵的压缩存储5.3 稀疏矩阵5.4 广义表数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表5.1.1 数组的定义和特点定义数组特点v数组结构固定v数据元素同构数组运算v取值操作：给定一组下标，存取相应的数据元素v赋值操作：给定一组下标，修改数据元素的值()()()()()()()()()5.1 多维数组5.2.2 数组的顺序存储结构次序约定v以行序为主序v以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为
2、主序存放 amn .am2 am1 .a2n .a22 a21 a1n .a12 a1101n-1m*n-1n按列序为主序存放按列序为主序存放01m-1m*n-1m amn .a2n a1n .am2 .a22 a12 am1 .a21 a11a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l5.2.1对称矩阵a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：5.2 特殊矩阵
3、的压缩存储aij=aji5.2.2三角矩阵a1100.0a21a220.0an1an2an3.ann.0a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：k=+(j-1)i(i-1)2ij5.2.3 带状矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400Loc(aij)=Loc(a11)+2i+j-3a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
4、按行序为主序：A由(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）唯一确定v定义：非零元较零元少，且分布没有一定规律的矩阵v压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值5.3 稀疏矩阵#define SMAX 1024typedef struct node int i,j;datatype v;SPNode;typedef struct int mu,nu,tu;SPNode dataSMAX;SPMatrix;将三元组按行优先，同一行中列号从小到大的规律排列成一个线
5、性表，称为三元组表。5.3.1 稀疏矩阵的三元组表存储1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 三元组表i j v0 1 2 3 4 5 6 7 8u求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+)for(row=0;rowm;row+)ncolrow=mrowcol;T(n)=O(mn)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3
6、 4 5 6 7 8A三元组i j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8B三元组?Y解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使B三元组中元素以B的行(A的列)为主序方法一：按A的列序转置for（col=1；colnu;col+)for(p=1;ptu;p+)if(找到第col列)赋值给B;6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1
7、 2 3 4 5 6 7 8A三元组7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8B三元组kppppppppkkkkppppppppcol=1col=2Y算法描述：见P73算法5-1Y算法分析：T(n)=O(A的列数n非零元个数t)若 t 与mn同数量级，则方法二：快速转置即按A中三元组次序转置，转置结果放入B中三元组恰当位置实现：设两个数组numcol：表示矩阵A中第col列中非零元个数cpotcol：指示A中第col列第一个非零元在mb中位置显然有：cpot1=1;cpo
8、tcol=cpotcol-1+numcol-1;(2col A.nu)1357889colnumcolcpotcol122232415061706 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8A三元组i j v0 1 2 3 4 5 6 7 8B三元组colnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753Y算
9、法描述：1、B-nu=A-mu；B-mu=A-nu；B-tu=A-tu；2、求num、cpot数组值；3、for(i=1;itu;i+)计算该元素在B三元组表中位置k；B-datak=A-datai;#define SMAX 1024typedef struct node int i,j;datatype v;SPNode;typedef struct int mu,nu,tu;SPNode dataSMAX;SPMatrix;见P75算法5-2Y结点定义typedef struct node int row,col;datatype v;struct node *down,*right;MN
10、ode;rowcolvdownright11354-823-13125.3.2 稀疏矩阵的十字链表存储14700 H100 H200 H300 H400 H5H100 11354-823-131214700 H200 H3H500 00 H454 HAtypedef struct node int row,col;struct node *down,*right;union v_next datatype v;struct node *next;Mnode,*MLink;rowcolv/nextdownrightY建立十字链表算法（1）输入行数、列数建立头结点HA；（2）建立行（列）头结点并形
11、成循环链表；（3）输入t个三元组（i，j，a ij）申请结点并输入值；插入第i行链表；插入第j列链表；（4）返回HA；5.4 广义表中国举办的某体育项目国际邀请赛:(俄罗斯,巴西,(国家,河北,四川),古巴,美国,(),日本)5.4.1广义表的定义和基本运算 广义表:是n个数据元素a1,a2,ai,an的有限序列,记作:ls=(a1,a2,ai,an)说明:1、ls为广义表名称，n是它的长度；2、ai可以是单个元素，也可以是广义表；3、当广义表非空时，第一个元素a1为表头，其余元素组成的表(a2,ai,an)为表尾。例子：A=（）B=（e）C=（a，（b，c，d）D=（A，B，C）E=（a，E
12、）F=（）通常用大写字母表示广义表，用小写字母表示单个数据元素上述广义表的长度分别是多少？表头、表尾分别是什么？5.4.2 广义表的存储 由于广义表中的数据元素可以具有不同的结构，因此难以用顺序存储结构来表示，所以通常采用链式的存储结构来存储。按结点形式的不同，广义表的链式存储结构又可以分为两种不同的存储方式：1、头尾表示法2、孩子兄弟表示法v孩子兄弟表示法tag=1hptp表元素：有孩子结点指向孩子的指针指向兄弟的指针typedef enumATOM,LIST Elemtag;typedef struct GLENode Elemtag tag;union datatype data;struct GLENode *hp;ptr;struct GLENode *tp;*EGList;tag=0datatp单元素：无孩子结点例子：A=（）B=（e）C=（a，（b，c，d）A1 B10eD=（A，B，C）C10a10b0c0dD1110例子：E=（a，E）E10a1F11 F=（）