《《数据结构(清华版)》4第四章串和数组.ppt》由会员分享，可在线阅读，更多相关《《数据结构(清华版)》4第四章串和数组.ppt（20页珍藏版）》请在三一办公上搜索。
1、第四章 数组,数组可以看成是一种特殊的线性表，即线性表中数据元素本身也是一个线性表4.1 数组的定义和特点定义,数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值,4.2 数组的顺序存储结构次序约定以行序为主序以列序为主序,4.3 矩阵的压缩存储对称矩阵,三角矩阵,对角矩阵,Loc(aij)=Loc(a11)+2(i-1)+(j-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）唯一确定,稀疏矩阵定义：非零元较零元少，且分布
2、没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值,稀疏矩阵的压缩存储方法顺序存储结构三元组表,#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,ma0.i,ma0.j,ma0.v分别存放矩阵行列维数和非零元个数,带辅助行向量的二元组表,增加一个辅助数组NRAm+1,其物理意义是第i行第一个非零元在二元组表中的起始地址（m为行数）
3、显然有：,6,NRA0不用或存矩阵行数,二元组表需存储单元个数为2(t+1)+m+1,伪地址表示法,伪地址：本元素在矩阵中（包括零元素再内）按行优先顺序的相对位置,伪地址表示法需存储单元个数为2(t+1),求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：,for(col=0;coln;col+)for(row=0;rowm;row+)ncolrow=mrowcol;T(n)=O(mn),解决思路：只要做到 将矩阵行、列维数互换 将每个三元组中的i和j相互调换 重排三元组次序，使mb中元素以N的行(M的列)为主序,方法一：按M的列序转置即按mb
4、中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序,算法描述：,算法分析：T(n)=O(M的列数n非零元个数t)若 t 与mn同数量级，则,Ch4_1.c,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,col=1,col=2,方法二：快速转置即按ma中三元组次序转置，转置结果放入b中恰当位置此法关键是要预先确定M中每一列第一个非零元在mb中位置，为确定这些位置，转置前应先求得M的每一列中非零元个数
5、,实现：设两个数组numcol：表示矩阵M中第col列中非零元个数cpotcol：指示M中第col列第一个非零元在mb中位置显然有：,1,3,5,7,8,8,9,算法分析：T(n)=O(M的列数n+非零元个数t)若 t 与mn同数量级，则T(n)=O(mn),算法描述：,Ch4_2.c,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,4,6,2,9,7,5,3,链式存储结构带行指针向量的单链表表示每行的非零元用一个单链表存放 设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空表头结点与单链表结点类型定义
6、,需存储单元个数为3t+m,十字链表设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义,tpedef struct node int row,col,val;struct node*down,*right;JD;,从键盘接收信息建立十字链表算法,算法分析：T(n)=o(ts)其中：t非零元个数 s=max(m,n),Ch4_3.c,令q=NULL,p=rhr-1,（1）寻找插入位置：当p!=NULL且cp-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;,m=4,n=31,1,32,2,52,3,44,1,82,1,7,Ch4_3.c,
