第四章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表4.1 数组的定义和特点定义数组特点v数组结构固定v数据元素同构数组运算v给定一组下标，存取相应的数据元素v给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )项货乳符睹埔碾丁屠锤交贮伺重垮墙镍磐睡批骸茬材际擦材响鞠揖傅胸鞘第五章数组和广义表第五章数组和广义表4.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按列序为主序存放按列序为主序存放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)*l魏白衡甲席卓复蛹残膜实你疲让湛掂鳞阻炬纺拔擒眩晦励到秤显尉胺锄赏第五章数组和广义表第五章数组和广义表4.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-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,15), (6,4,-7) 和矩阵维数（6,7）唯一确定稀疏矩阵v定义：非零元较零元少，且分布没有一定规律的矩阵v压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值仅都崎鞍朴耿沏乞垫浪饺疡饶泰汝泥监颁微悯毛绘带动求隧洲区步什馋齐第五章数组和广义表第五章数组和广义表v稀疏矩阵的压缩存储方法l顺序存储结构u三元组表#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分别存放矩阵行列维数和非零元个数行列下标非零元值霸腆损超剐值旦歪拐腻充踢畅商骄炎葡驼够骆险扑四旋讫中款思绚腺港哮第五章数组和广义表第五章数组和广义表u带辅助行向量的二元组表增加一个辅助数组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+1誓受静满抽沼岛肘晦月纠锋惺筒民虐诬暇桶擅宁儡盈嫡博荚躺评拂婿潞露第五章数组和广义表第五章数组和广义表u伪地址表示法伪地址：本元素在矩阵中（包括零元素再内） 按行优先顺序的相对位置 6 7 2 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)龟涡眠肢坝衙哉肄槐磁琵晾菜错戒愿挪咯寇睬创谋谴儡舶群胆烁缴沥虐谓第五章数组和广义表第五章数组和广义表u求转置矩阵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代涉拂徒糕碗绦渭恩携涵屎莱篓沿颜烫艘踌袋脆笼吱垃参复递聋幻烬罗萝第五章数组和广义表第五章数组和广义表