一  数组

数组是一组偶对(下标值，数据元素值)的集合。在数组中，对于一组有意义的下标，都存在一个与其对应的值。一维数组对应着一个下标值，二维数组对应着两个下标值。

       数组是由n(n>1)个具有相同数据类型的数据元素a₁，a₂，_…，a_n组成的有序序列，且该序列必须存储在一块地址连续的存储单元中

 

1 数组中的数据元素具有相同数据类型。

2 数组是一种随机存取结构，给定一组下标，就可以访问与其对应的数据元素。

3 数组中的数据元素个数是固定的

 

二 抽象数据类型

ADT Array{

数据对象：j_i= 0,1,…,b_i-1 , 1,2, …,n ;

D = { a_j1j2…jn | n>0称为数组的维数，b_i是数组第i维的长度，j_i是数组元素第i维的下标，a_j1j2…jn∈ElemSet }

数据关系：R = {R₁, R₂, …, R_n}

R_i = {<a_{j1j2 …ji…jn} , a_{j1j2 …ji+1…jn}>|0≦j_k≦b_k-1 ， 1≦k≦n且k≠i，0≦j_i≦b_i-2，a_{j1j2 …ji+1…jn}∈D }           

基本操作：……

} ADT Array。

 

 

2.1 二维数组

2.2 数组的操作与存储

数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。

2.2.1行优先存储方式

行优先顺序(Row Major Order) ：将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。对二维数组，按行优先顺序存储的线性序列为

    a₁₁,a₁₂,…,a_1n,  a₂₁,a₂₂,…a_2n   ,……,  a_m1,a_m2,…,a_mn  

2.2.2列优先顺序(Column Major Order)

将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，对二维数组，按列优先顺序存储的线性序列为：

      a₁₁,a₂₁,…,a_m1,     a₁₂,a₂₂,…a_m2,    ……,   a_n1,a_n2,…,a_nm

 

若每个元素占用的存储单元数为l(个)，LOC[a₁₁]表示元素a₁₁的首地址

 

以“行优先顺序”存储:

第m行中的每个元素对应的(首)地址是：

LOC[a_mj]=LOC[a₁₁]+(m-1)´n´l +(j-1)´l     j=1,2,…,n    

三维数组任意元素aijk的首地址:

LOC(a_ijk)=LOC[a₁₁₁]+[(i-1)´n´p+(j-1)´p+(k-1)]´l

 

推而广之，对n维数组A=(a_j1j2…jn)，若每个元素占用的存储单元数为l(个)，LOC[a_{11 …1}]表示元素a_{11 …1}的首地址。则

以“行优先顺序”存储在内存中

n维数组中任一元素a_j1j2…jn的(首)地址是：

    LOC[a_j1j2…jn]=LOC[a_{11 …1}]+[(b₂´…´b_n)´(j₁-1)

                             + (b₃´…´b_n)´(j₂-1)+…

                             + b_n´(j_n-1-1)+(j_n-1)] ´l 

以“列优先顺序”存储

⑴ 第1列中的每个元素对应的(首)地址是：

      LOC[a_j1]=LOC[a₁₁]+(j-1)´l        j=1,2,…,m

(2) 第2列中的每个元素对应的(首)地址是：

      LOC[a_j2]=LOC[a₁₁]+m´l +(j-1)´l      j=1,2,…,m

⑶ 第n列中的每个元素对应的(首)地址是：

LOC[a_jn]=LOC[a₁₁]+(n-1)´m´l +(j-1)´l     j=1,2,…,m

由此可知，二维数组中任一元素a_ij的(首)地址是：

LOC[a_ij]=LOC[a₁₁]+[(i-1)´m+(j-1)]´l      

i=1,2,…,n    j=1,2,…,m   

2.3 矩阵的压缩存储

 

对于高阶矩阵，若其中非零元素呈某种规律分布或者矩阵中有大量的零元素，若仍然用常规方法存储，可能存储重复的非零元素或零元素，将造成存储空间的大量浪费。对这类矩阵进行压缩存储：

◆ 多个相同的非零元素只分配一个存储空间；

◆ 零元素不分配空间。

 

2.3.1对称矩阵

若一个n阶方阵A=(a_ij)_n´n中的元素满足性质： a_ij=a_ji   1≦i,j≦n且i≠j

若i≧j：a_{i j}在下三角形中，直接保存在sa中。a_{i j}之前的i-1行共有元素个数：

1+2+…+(i-1)=i´(i-1)/2

而在第i行上，a_{i j}之前恰有j-1个元素，因此，元素a_{i j}保存在向量sa中时的下标值k之间的对应关系是：

         k=i´(i-1)/2+j-1          i≧j

若i<j：则a_ij是在上三角矩阵中。因为a_ij=a_ji，在向量sa中保存的是a_ji。依上述分析可得：

         k=j´(j-1)/2+i-1         i<j

对称矩阵元素a_{i j}保存在向量sa中时的下标值k与（i,j）之间的对应关系是：  

所以矩阵中的元素压缩存储后的位置。

2.3.2三角矩阵

三角矩阵中的重复元素c可共享一个存储空间,也就是常量c单独放在一个存储空间中，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0…n(n+1)/2]中，其中c存放在向量的第1个分量中。

上三角矩阵元素a_{i j}保存在向量sa中时的下标值k与（i,j）之间的对应关系是：

2.3.3对角矩阵

矩阵中，除了主对角线和主对角线上或下方若干条对角线上的元素之外，其余元素皆为零。即所有的非零元素集中在以主对角线为了中心的带状区域。

对这种矩阵，当以按“行优先顺序”存储时， 第1行和第n行是2个非零元素，其余每行的非零元素都要是3个，则需存储的元素个数为3n-2

2.3.4 稀疏矩阵

稀疏矩阵(Sparse Matrix)：对于稀疏矩阵，目前还没有一个确切的定义。设矩阵A是一个n´m的矩阵中有s个非零元素，设  δ=s/(n´m)，称δ为稀疏因子，如果某一矩阵的稀疏因子δ满足δ≦0.05时称为稀疏矩阵。

 

一个三元组(i, j, a_ij)唯一确定稀疏矩阵的一个非零元素。的稀疏矩阵A的三元组线性表为

((1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) )

 

三元租数据结构:

#define MAX_SIZE 101

typedef int elemtype ;

typedef struct

{  

int   row ;    /*  行下标  */

int  col ;       /*  列下标  */

elemtype value;      /* 元素值  */

}Triple ;

 

一个m´n的矩阵A，它的转置B是一个n´m的矩阵，且b[i][j]=a[j][i]，0≦i≦n，0≦j≦m，即B的行是A的列，B的列是A的行。

   设稀疏矩阵A是按行优先顺序压缩存储在三元组表a.data中，若仅仅是简单地交换a.data中i和j的内容，得到三元组表b.data，b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组表b.data中元素的顺序。

 

伪码描述:

voidTransMatrix(TMatrix a , TMatrix b)

{   int p , q , col ;

b.rn=a.cn;  b.cn=a.rn ;  b.tn=a.tn ;

/*    置三元组表b.data的行、列数和非0元素个数*/

if  (b.tn==0)   printf(“ The Matrix A=0\n” );

else

{   q=0;

for  (col=1; col<=a.cn ; col++)

      /*  每循环一次找到转置后的一个三元组  */

for  (p=0 ;p<a.tn ; p++)

      /*  循环次数是非0元素个数   */

    if (a.data[p].col==col)

        { b.data[q].row=a.data[p].col ;

            b.data[q].col=a.data[p].row ;

             b.data[q].value=a.data[p].value;

             q++ ;

         }

}

}

 

算法分析：本算法主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(cn´tn)，即矩阵的列数和非0元素的个数的乘积成正比。

而一般传统矩阵的转置算法为：

for(col=1; col<=n ;++col)

for(row=0 ; row<=m ;++row)

b[col][row]=a[row][col] ;

    其时间复杂度为O(n´m)。当非零元素的个数tn和m´n同数量级时，算法TransMatrix的时间复杂度为O(m´n²)。

由此可见，虽然节省了存储空间，但时间复杂度却大大增加。所以上述算法只适合于稀疏矩阵中非0元素的个数tn远远小于m´n的情况。

 

快速转置:

 

◆ num[col]：统计A中第col列中非0元素的个数；

◆ cpot[col] ：指示A中第一个非0元素在b.data中的恰当位置。

伪代码:

void  FastTransMatrix(TMatrix a, TMatrix b)

{    int p , q , col , k ;

intnum[MAX_SIZE] , copt[MAX_SIZE] ;

b.rn=a.cn; b.cn=a.rn ; b.tn=a.tn ;

 /*   置三元组表b.data的行、列数和非0元素个数 */

if  (b.tn==0)   printf(“ The Matrix A=0\n” ) ;

else

{  for (col=1 ; col<=a.cn ; ++col)    num[col]=0 ;

   /*  向量num[]初始化为0   */

               for (k=1 ; k<=a.tn ; ++k)

      ++num[ a.data[k].col] ;

           /*  求原矩阵中每一列非0元素个数 */

for(cpot[0]=1, col=2 ; col<=a.cn ; ++col)

       cpot[col]=cpot[col-1]+num[col-1] ;

         /* 求第col列中第一个非0元在b.data中的序号 */

for(p=1 ; p<=a.tn ; ++p)

    {  col=a.data[p].col ;  q=cpot[col] ;

          b.data[q].row=a.data[p].col ;

          b.data[q].col=a.data[p].row ;

           b.data[q].value=a.data[p].value ;

           ++cpot[col] ;    

 /*至关重要!!当本列中  */

/*同一列中有多个非零元素的*/

}

 

 

矩阵乘法

设有两个矩阵：A=(a_ij)_m´n ，B=(b_ij)_n´p

则： C=(c_ij)_m´p       其中 c_ij=∑a_ik´b_kj

          1≦k≦n ， 1≦i≦m ，1≦j≦p

经典算法是三重循环：

for  ( i=1 ; i<=m ; ++i)

for ( j=1 ; j<=p ; ++j)

{            c[i][j]=0 ;

for ( k=1 ; k<=n ; ++k)

          c[i][j]=c[i][j]+a[i][k]´b[k][j];

}

此算法的复杂度为O(m´n´p)。

a.data[p].col=b.data[q].row的元素b.data[q]，求得a.data[p].value´b.data[q].value，该乘积是c_ij中的一部分。求得所有这样的乘积并累加求和就能得到c_ij。

 

三元组数据结构

typedefstruct 

{ 

Triple data[MAX_SIZE] ;     /*  非0元素的三元组表  */ 

int    rpos[MAX_ROW];     /* 各行第一个非0位置表 */

int   rn ,cn , tn ;       /*  矩阵的行、列数和非0元个数 */

}RLSMatrix;

 

 

三元组的算法:

       两个稀疏矩阵A=(a_ij)_m´n ，B=(b_ij)_n´p，其存储结构采用行逻辑链接的三元组顺序表。

算法思想：对于A中的每个元素a.data[p](p=1, 2, … , a.tn)，找到B中所有满足条件：

a.data[p].col=b.data[q].row的元素b.data[q]，求得a.data[p].value´b.data[q].value，该乘积是c_ij中的一部分。求得所有这样的乘积并累加求和就能得到c_ij。

    为得到非0的乘积，只要对a.data[1…a.tn] 中每个元素(i，k，a_ik)(1≦i≦a.rn，1≦k≦a.cn) ，找到b.data中所有相应的元素(k，j，b_kj)(1≦k≦b.rn，1≦j≦b.cn) 相乘即可。则必须知道矩阵B中第k行的所有非0元素，而b.rpos[ ]向量中提供了相应的信息。

        b.rpos[row]指示了矩阵B的第row行中第一个非0元素在b.data[]中的位置(序号)，显然，b.rpos[row+1]-1指示了第row行中最后一个非0元素在b.data[ ]中的位置(序号) 。最后一行中最后一个非0元素在b.data[]中的位置显然就是b.tn 。

 

 

voidMultsMatrix(RLSMatrix a, RLSMatrix b, RLSMatrix c)

      /* 求矩阵A 、B的积C=A´B，采用行逻辑链接的顺序表 */

{   elemtype ctemp[Max_Size] ;

int  p , q , arow , ccol , brow , t ;

if  (a.cn!=b.rn)  {   printf(“Error\n”) ;exit(0);  }

else        

{    c.rn=a.rn ; c.cn=b. n ; c.tn=0 ;     /* 初始化C  */

if(a.tn*b.tn!=0)        /* C  是非零矩阵 */

{   for (arow=1 ; arow<=a.rn ; ++arow)

        {  ctemp[arow]=0 ;  /*  当前行累加器清零   */

                    c.rpos[arow]=c.tn+1;

              p=a.rops[arow];

             for ( ; p<a.rpos[arow+1];++p)

                              /* 对第arow行的每一个非0元素  */

                       {   brow=a.data[p].col ;

                                        /*   找到元素在b.data[]中的行号  */

                      if (brow<b.cn) t=(b.rpos[brow+1];

       for (q=b.rpos[brow] ; q<t ; ++q)

                   {  ccol=b.data[q].col ;

                               /*   积元素在c中的列号  */           ctemp[ccol]+=a.data[p].value*b.data[q].value ;

            }

}       /* 求出c中第arow行中的非0元素  */

for(ccol=1 ; ccol<=c.cn ; ++ccol)

if (ctemp[ccol] !=0 )

   {   if( ++c.tn>MAX_SIZE)

           {   printf(“Error\n”) ; exit(0);   }

       else

c.data[c.tn]=(arow, ccol , ctemp[ccol]) ;

    }

}

}

}

 

 

三 十字链表

     稀疏矩阵中同一行的非0元素的由right指针域链接成一个行链表，由down指针域链接成一个列链表。则每个非0元素既是某个行链表中的一个结点，同时又是某个列链表中的一个结点，所有的非0元素构成一个十字交叉的链表。称为十字链表

typedefstruct  Clnode 

{  

int row , col ;   /*  行号和列号  */    

elemtype value ;    /*  元素值  */

struct Clnode  *down , *right ;

}OLNode;   /* 非0元素结点  */

 

 

四 广义表

广义表(Lists，又称为列表 )：是由n(n ≧0)个元素组成的有穷序列： LS=(a₁，a₂，…，a_n)其中a_i或者是原子项，或者是一个广义表。LS是广义表的名字，n为它的长度。若a_i是广义表，则称为LS的子表。

习惯上：原子用小写字母，子表用大写字母。

若广义表LS非空时：

◆ a₁(表中第一个元素)称为表头；

◆ 其余元素组成的子表称为表尾；(a₂，a₃，…，a_n)

◆ 广义表中所包含的元素(包括原子和子表)的个数称为表的长度。

◆ 广义表中括号的最大层数称为表深 (度)。

广义表的重要结论：

⑴ 广义表的元素可以是原子，也可以是子表，子表的元素又可以是子表。即广义表是一个多层次的结构。

(2) 广义表可以被其它广义表所共享，也可以共享其它广义表。广义表共享其它广义表时通过表名引用。

(3) 广义表本身可以是一个递归表。

(4) 根据对表头、表尾的定义，任何一个非空广义表的表头可以是原子，也可以是子表， 而表尾必定是广义表。

 

存储结构

typedefstruct GLNode

{  int  tag ;     /*  标志域，为1：表结点;为0 ：原子结点  */

Union 

{  elemtype value;     /* 原子结点的值域  */

struct

             struct GLNode *hp , *tp ;

           }ptr;   /* ptr和atom两成员共用  */

}Gdata ;

}GLNode ;      /* 广义表结点类型  */

 

(1) 若广义表为空，表头指针为空；否则，表头指针总是指向一个表结点，其中hp指向广义表的表头结点(或为原子结点，或为表结点) ，tp指向广义表的表尾(表尾为空时，指针为空，否则必为表结点)。

(2)  这种结构求广义表的长度、深度、表头、表尾的操作十分方便。

(3)  表结点太多，造成空间浪费。

 

Union

内部地址长度取决与最大元素的地址长度的字节数，然后在构造变量时是只存放一个被选中的成员。