数组可以看成是一种特殊的线性表

1、第四章 数组数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表4.1 数组的定义和特点定义mnmmnnnmaaaaaaaaaA.212222111211数组特点v数组结构固定v数据元素同构数组运算v给定一组下标，存取相应的数据元素v给定一组下标，修改数据元素的值( )( )( )( )( )( )( )( )( )4.2 数组的顺序存储结构次序约定v以行序为主序v以列序为主序 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放按行序为主序存放 amn . a

2、m2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n 按列序为主序存放按列序为主序存放01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 4.3 矩阵的压缩存储对称矩阵jiijjjijiik, 12/ ) 1(12/ ) 1(， a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a2

3、2 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：三角矩阵 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0Loc(aij)=Loc(a11)+( +(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：对角矩阵 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann. 0 a32 a

4、33 a34 0 0 Loc(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 按行序为主序：7600070015000001800000240001400003000000000009120MM由(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、数和每个非零元的行列下标及其值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分别存放矩阵行列维数和非零元个数行列下标非零元值7600070015000001800000240001400003000000000009120M

6、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)7600070015000001800000240001400003000000000009120Mu求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表Y问题分析一般矩阵转置算法：for(col=0;coln;col+) for(row=0;rowm;row+) ncolrow=

7、mrowcol;T(n)=O(mn)7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N6 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 8mai 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 8mb?Y解决思路：只要做到

8、将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序方法一：按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序Y算法描述：Y算法分析：T(n)=O(M的列数n非零元个数t) 若 t 与mn同数量级，则)()(2nmOnTCh4_1.c6 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

9、 8ma7 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 8mbkppppppppkkkkppppppppcol=1col=2int trans_sparmat(JD ma, JD mb) int col,p,n,t,k; if(ma0.v=0) return(0); n=ma0.j; mb0.i=n; mb0.j=ma0.i; mb0.v=ma0.v; k=1; for(col=1;col=n;col+) for(p=1;p=t;p+) if(map.j=col) mbk.i=m

10、ap.j; mbk.j=map.i; mbk.v=map.v; k+; return(1);方法二：快速转置即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数实现：设两个数组numcol：表示矩阵M中第col列中非零元个数cpotcol：指示M中第col列第一个非零元在mb中位置显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2col ma0.j)1357889colnumcolcpotcol1222324150617076000700150000018

11、00000240001400003000000000009120MY算法分析：T(n)=O(M的列数n+非零元个数t) 若 t 与mn同数量级，则T(n)=O(mn)Y算法描述：Ch4_2.cint fast_transpos(JD ma,JD mb) int n,col,p,k,t; int numM,cpotM; n=ma0.j; t=ma0.v; mb0.i=n; mb0.j=ma0.i; mb0.v=t; if(t=0) return(0); for(col=0;col=n;col+) numcol=0;for(p=1;p=t;p+) k=map.j;numk+;cpot0=0; cp

12、ot1=1; for(col=2;col=n;col+) cpotcol=cpotcol-1+numcol-1; for(p=1;pp-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;void crt_linkedmat(JD *rh

13、,JD *ch,int *hs,int *ls) int m,n,i,r,c,v; JD *p,*q,*s; printf(Input m,n:); scanf(%d,%d,&m,&n); for(i=0;im;i+) rhi=NULL; for(i=0;im)|(cn) continue; s=(JD *)malloc(sizeof(JD); s-row=r; s-col=c; s-val=v; s-right=s-down=NULL; q=NULL; p=rhr-1; while(p!=NULL)&(cp-col) q=p; p=p-right; if(p=NULL

14、) if(q=NULL) rhr-1=s; else q-right=s; else if(c=p-col) p-val=v; free(s); continue; else if(q=NULL) rhr-1=s; s-right=p; else s-right=p; q-right=s; q=NULL; p=chr-1; while(p!=NULL)&(rp-row) q=p; p=p-down; if(p=NULL) if(q=NULL) chc-1=s; else q-down=s; else if(q=NULL) chc-1=s; s-down=p; else s-down=p

15、; q-down=s; 418234m=4,n=31,1,32,2,52,3,44,1,82,1,7Ch4_3.c11321722554 广义表 5. 4 广义表 5. 3 . 1 广义表的概念 5. 3 . 2 广义表的存储结构 5. 3 . 2 广义表的基本操作5.4.1 广义表的概念广义表的概念 1 什么是广义表什么是广义表 广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。 记作：LS= (d0, d1, d2, . . . . . .dn-1)。其中di既可以是单个元素，也可以是广义表。说明 1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表； 2）在线性表

16、中数据元素是单个元素，而在广义表中， 元素可以是单个元素, 称为单元素(原子)，也可以是广义表，称为广义表的子表； 3）n 是广义表长度；54 广义表54 广义表4）下面是一些广义表的例子； A = ( ) 空表，表长为0； B = (a,(b,c,d) B的表长为2，两个元素分别为 a 和子表（b,c,d)； C = (e) C中只有一个元素e，表长为1； D = (A,B,C,f ) D 的表长为4，它的前三个元素 A，B，C 广义表,第四个 是单元素； E=( a ,E ) 递归表.5）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表 对非空广义表：称第一个元素为L

17、的表头，其余元素组成的表称为LS的表尾；B = (a,(b,c,d) 表头：a 表尾 (b,c,d) 即 HEAD（B）=a, TAIL(B)=(b,c,d),C = (e) 表头：e 表尾 ( )D = (A,B,C,f ) 表头：A 表尾 (B,C,f )运算可以嵌套，如：HEAD（TAIL（B）=b, TAIL(TAIL(B)=(c, d) 。广义表的元素之间除了存在次序关系外，还存在层次关系。如：DABCfaDebcd2 广义表的基本操作广义表的基本操作 1） 创建广义表L； 2） 销毁广义表L； 3） 已有广义表L，由L复制得到广义表T； 4） 求广义表L的长度； 5） 求广义表L的

18、深度； 6） 判广义表L是否为空； 7） 取广义表L的表头； 8） 取广义表L的表尾； 9） 在L中插入元素作为L的第i个元素； 10）删除广义表L的第i个元素； 11）遍历广义表L，用函数 traverse( )处理每个元素；5.4.2 广义表的存储结构广义表的存储结构 由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采用链表存储方式 如何设定链表结点？广义表中的数据元素可能为单元素(原子)或子表，由此需要两种结点：一种是表结点，用以表示广义表；一种是单元素结点，用以表示单元素（原子）。表结点单元素结点Tag=0 atomTag=1 hp tp链表结点的类型定义如下： struct node int tag; /标志域：用于区分原子结点和表结点标志域：用于区分原子结点和表结点 union int atom;