《《数据结构(清华版)》4第四章 串和数组.ppt》由会员分享，可在线阅读，更多相关《《数据结构(清华版)》4第四章 串和数组.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表v4.1 数组的定义和特点定义数组特点v数组结构固定v数据元素同构数组运算v给定一组下标，存取相应的数据元素v给定一组下标，修改数据元素的值()()()()()()()()()v4.2 数组的顺序存储结构次序约定v以行序为主序v以列序为主序a11a12.a1na21a22.a2nam1am2.amn.Loc(aij)=Loc(a11)+(i-1)n+(j-1)*l按行序为主序存放按行序为主序存放 amn .am2 am1 .a2n .a22 a21 a1n .a12 a1101n-1m*n-1n按列序为主序存放按列
2、序为主序存放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)*lv4.3 矩阵的压缩存储对称矩阵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 按行序为主序：三角矩阵a1100.0a21a220.0an1an2an3.ann.0Loc(aij)=Loc(a11)+(+(j-1)*li(i-
3、1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann.0a32a33a3400Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：M由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1
4、,15),(6,4,-7)和矩阵维数（6,7）唯一确定稀疏矩阵v定义：非零元较零元少，且分布没有一定规律的矩阵v压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值v稀疏矩阵的压缩存储方法顺序存储结构v三元组表#define M 20typedef struct node int i,j;int v;JD;JD maM;三元组表所需存储单元个数为3(t+1)其中t为非零元个数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 mai j v0 1 2 3 4 5 6 7 8ma0.i,ma0.j,ma0.v分别存放矩
5、阵行列维数和非零元个数行列下标非零元值v带辅助行向量的二元组表增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）显然有：NRA1=1NRAi=NRAi-1+第i-1行非零元个数(i2)0 1 2 3 4 5 6 NRA1335676 7 8 2 12 3 9 1 -3 6 14 3 24 2 18 1 15 4 -7 maj v0 1 2 3 4 5 6 7 8矩阵列数和非零元个数列下标和非零元值NRA0不用或存矩阵行数二元组表需存储单元个数为2(t+1)+m+1v伪地址表示法伪地址：本元素在矩阵中（包括零元素再内）按行优先顺序的相对位置 6 7 2
6、 12 3 9 15 -3 20 14 24 24 30 18 36 15 39 -7 maaddr v伪地址非零元值矩阵行列维数0 1 2 3 4 5 6 7 8伪地址表示法需存储单元个数为2(t+1)v求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+)for(row=0;rowp-col时，p和q右移（2）插入：a、若p=NULL且q=NULL，即本行空，则rhr-1=s;b、若p=NULL,q!=NULL，即走到行末，则q-right=sc、若c=p-col，则修改p-vald、若ccol且q=NULL，则在p之前插入s，即s是行链表中 第一个结点，令rhr-1=s;s-right=p;e、若ccol且q!=NULL，则在p之前插入s，即 s-right=p;q-right=s;418234m=4,n=31,1,32,2,52,3,44,1,82,1,7Ch4_3.c113217225