程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> SyBase數據庫 >> SyBase教程 >> 數據結構-數組、矩陣、廣義表存儲

數據結構-數組、矩陣、廣義表存儲

編輯:SyBase教程

數據結構-數組、矩陣、廣義表存儲


數組的定義

數組的定義
數組是下標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 ;      /* 廣義表結點類型  */

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved