首页 > 数据库 > Sybase > 正文
数据结构-数组、矩阵、广义表存储
2015-04-30       个评论    来源:王照陆博客  
收藏    我要投稿

数组的定义

数组的定义
数组是下标index 和值value 组成的序对的集合。
在数组中,每个有定义的下标都与一个值对应,这个值称做数组元素。
每个序对形如: (index,value)

数组的顺序表示和实现

由于计算机的内存结构是一维的,因此用一维内存来表示多维数组,就必须按某种次序将数组元素排成一列序列,然后将这个线性序列存放在存储器中。
一般都是采用顺序存储的方法来表示数组

一维数组的顺序表示
设第一个数组元素a[0]的存储地址是loc(a[0]),若已知每个数组元素占k个存储单元,则下标为i的数组元素a[i]的存储地址loc(a[i])为
loc(a[i])=loc(a[0])+i*k
i=0,1,2,…,n-1。

二维数组的顺序表示
二维数组a[m][n]映射到一维的存储空间时有两种顺序:行优先和列优先。
大多数语言如PASCAL、BASIC、C、C++等都是按行优先顺序存储的,FORTRAN是按列优先顺序存储的。

矩阵的压缩存储

矩阵的存储——二维数组
考虑:若矩阵阶数很高,且有许多值相同的元素或零元素,怎么提高存储效率?
特殊矩阵——值相同的元素或者零元素在矩阵中的分布有一定规律
稀疏矩阵——矩阵中有大量零元素,非零元素比较少。
压缩存储:为多个相同的非零元素只分配一个存储空间;对零元素不分配空间。

对称矩阵的压缩存储

若i≧j,则aij 在下三角矩阵中。 aij 之前的i-1行(从第1行到第i-1行)一共有1+2+…+i-1=i(i-1)/2个元素,在第i行上, aij 之前恰有j-1个元素(即ai0,ai1,ai2,…,aij-1),因此有:
               k=i*(i-1)/2+j-1                 当 i≧j
 若i<j,则aij 是在上三角矩阵中。因为aij=aji,所以只要交换上述对应关系式中的i和j即可得到:
              k=j*(j-1)/2+i-1                  当 i<j
    根据上述的下标对应关系,对于矩阵中的任意元素aij,均可在一维数组sa中唯一确定其位置k;反之,对所有k=0,1, …, n(n+1)/2-1,都能确定sa[k]中的元素在矩阵中的位置(i,j)。

三角矩阵的压缩存储

三角矩阵中的重复元素c可共享一个存储空间,其余的元素正好有n(n+1)/2个,因此,三角矩阵可压缩存储到一维数组sa[n(n+1)/2+1]中,其中c存放在数组的第1个位置(亦可放在最后一个位置)。
上三角矩阵元素aij保存在数组sa中时,下标值k与(i,j)之间的对应关系是?
下三角矩阵元素aij保存在数组sa中时,下标值k与(i,j)之间的对应关系是?

稀疏矩阵的存储

解决方法:在存储非零元素的同时,同时记下它所在的行和列的位置(i, j)。
由于三元组(i, j, aij)唯一确定了矩阵A的一个非零元。因此,稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
例如,下列三元组表
( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (4,6,2), (5,2,18), (6,7,-7), (7,4,-6) ) 和行列信息(7,8,9)便可描述如图5.6所示的稀疏矩阵
注:行列信息(7,8,9)中,7:行;8:列;9:非零元个数

三元组顺序表

以顺序存储结构来表示三元组表,则得到稀疏矩阵的一种压缩存储方法——三元顺序表。

⑴ 三元组结点定义    
  #define MAX_SIZE 1000
  typedef int elemtype ;
  typedef struct
{    int   row ;     /*  行下标  */
      int   col ;        /*  列下标  */
elemtype value;      /*  元素值  */
}Triple ;
⑵  三元组顺序表定义    
typedef struct 
{   int  rn ;         /*   行数   */
int  cn;         /*   列数   */
int  tn ;         /*    非0元素个数   */
Triple   data[MAX_SIZE] ; 
}TMatrix ; 
TMatrix  a;//定义了一个用三元组顺序表表示的稀疏矩阵

矩阵的转置

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

转置矩阵的算法

按方法一求转置矩阵的算法如下:
void TransMatrix(TMatrix a , TMatrix * b)
{   int i , j , 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{   j=0; //b中三元组 数组下标
for  (col=1; col<=a.cn ; col++)
/*   每次循环扫描 a的第col 列非零元,得到b的第col行非零元  */
      for  (i=0 ;i<a.tn ; i++)  /*   循环次数是非0元素个数   */
                                 if  (a.data[i].col==col)
                                   {    b-> data[j].row=a.data[i].col ;
                                         b-> data[j].col=a.data[i].row ; 
                                         b-> data[j].value=a.data[i].value; 
                                         j++ ;
                                     }
                    }  }

快速转置算法

快速转置算法如下
   void  FastTransMatrix(TMatrix a, TMatrix b)
{    int p , q , col , k ;
int num[N] , copt[N] ;  //N为矩阵列数
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=0 ; k<a.tn ; ++k) 
      ++num[ a.data[k].col] ;
           /*   求原矩阵中每一列非0元素个数  */
for (cpot[1]=0, col=2 ; col<=a.cn ; ++col)
       cpot [col]=cpot[col-1]+num[col-1] ;
      /*  求第col列中第一个非0元在b.data中的序号 */
for (p=0 ; p<a.tn ; ++p)
    {   col = a.data[p].col ; 
         q=cpot[col] ; //矩阵b的第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] ;      /*至关重要!!当本列中增加新元素时,位置即变为下一个非零元素的位置  */
     }
}
}

十字链表(链式存储)

    对于稀疏矩阵,当非0元素的个数和位置在操作过程中变化较大时,采用链式存储结构表示比三元组的线性表更方便。
   矩阵中非0元素的结点所含的域有:行、列、值、行指针(指向同一行的下一个非0元)、列指针(指向同一列的下一个非0元)。其次,十字交叉链表还有一个头结点

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

此外,用两个一维数组rhead和chead分别存储行链表的头指针和列链表的头指针。
结点的描述如下:
typedef struct  OLnode  
{   int  row , col ;   /*  行号和列号  */     
elemtype value ;    /*  元素值  */
struct  OLnode  *down , *right ;
} OLNode, *OLink ;   /*  非0元素结点  */

typedef struct
{   int   rn;        /*  矩阵的行数  */     
int   cn;        /*  矩阵的列数  */
int   tn;        /*  非0元素总数  */
OLink  * rhead ;      //行链表头指针向量基址
OLink  * chead ;    //列链表头指针向量基址
} CrossList 

广义表

广义表是线性表的推广和扩充,在人工智能领域中应用十分广泛。
第2章中的线性表定义为n(n≧0 )个元素a1, a2 ,…, an的有穷序列,该序列中的所有元素具有相同的数据类型且只能是原子项(Atom)。所谓原子项可以是一个数或一个结构,在结构上不可再分。若放松对元素的这种限制,容许它们具有其自身结构,就产生了广义表的概念。
广义表(Lists,又称为列表 ):是由n(n ≧0)个元素组成的有穷序列: LS=(a1,a2,…,an) ,其中ai或者是原子项,或者是一个广义表。LS是广义表的名字,n为它的长度。若ai是广义表,则称为LS的子表。
习惯上:原子项用小写字母,子表用大写字母。
若广义表LS非空时:
◆ a1(表中第一个元素)称为表头;
◆ 其余元素组成的子表称为表尾;(a2,a3,…,an)
◆ 广义表中所包含的元素(包括原子和子表)的个数称为表的长 度。
◆ 广义表中括号的最大层数称为表深 (度)

广义表的元素可以是原子项,也可以是子表,子表的元素又可以是子表, …。即广义表是一个多层次的结构。表5-2中的广义表D的图形表示如图5-12所示。
广义表可以被其它广义表所共享,也可以共享其它广义表。广义表共享其它广义表时不必列出子表的值,而是通过表名引用。如:D=(A,B,C)
广义表本身可以是一个递归表。如:E=(a,E)
根据对表头、表尾的定义,任何一个非空广义表的表头可以是原子,也可以是子表, 而表尾必定是广义表。

广义表的存储结构

由于广义表中的数据元素具有不同的结构,通常用链式存储结构表示,每个数据元素用一个结点表示。因此,广义表中就有两类结点:
◆ 一类是表结点,用来表示广义表项,由标志域,表头指针域,表尾指针域组成;
◆ 另一类是原子结点,用来表示原子项,由标志域,原子的值域组成。如图5-13所示。
只要广义表非空,都是由表头和表尾组成。即一个确定的表头和表尾就唯一确定一个广义表。

相应的数据结构定义如下:
typedef struct GLNode
{  int   tag ;     /*  标志域,为1:表结点;为0 :原子结点  */
union
{  Atomtype atom;     /* 原子结点的值域  */
struct
    {  struct GLNode  *hp , *tp ;
     }ptr ;   /*  ptr和atom两成员共用  */
}Gdata ; 
} GLNode ;      /* 广义表结点类型  */
点击复制链接 与好友分享!回本站首页
上一篇:几种backup小结
下一篇:【机房重构】—存储过程当媒人
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站