數(shù)據(jù)結(jié)構(gòu)5_arrayandglist.ppt

1、第五章 數(shù)組和廣義表,5.1 數(shù)組的定義 5.2 數(shù)組的順序表示和實現(xiàn) 5.3 矩陣的壓縮存儲 5.4 廣義表,5.1 數(shù)組的定義,ADT Array 數(shù)據(jù)對象：ji=0,bi-1,i=1,2,.,n, D=aj1j2jn|n(0)為數(shù)組的維數(shù),bi是數(shù)組 第i維的長度,ji是數(shù)組元素的第i維下標(biāo), aj1j2jnElemSet 數(shù)據(jù)關(guān)系：R=R1,R2,Rn,基本操作： 詳見P90 ADT Array,n維數(shù)組中含有元素：,5.1 數(shù)組的定義,Amxn二維數(shù)組，可以看成一個線性表： A=(0, 1, p) (p=m-1或n-1),j =(0j, 1j, 2j, m-1j) 0jn-1,其中每

2、個元素j是一個列向量形式的線性表：,或行向量：,i =(i0, i1, i2, in-1) 0im-1,5.2 數(shù)組的順序表示和實現(xiàn),一、數(shù)組元素的定位,列優(yōu)先存儲 行優(yōu)先存儲,以行優(yōu)先存儲： loc(i,j)=loc(i,j-1)+L=loc(i,j-2)+L+L= =loc(0,0)+(b2*i+j)*L,數(shù)據(jù)關(guān)系：R1，R2 R1=| 0 j2 b2-1, 0 j1b1-2 R2=|0 j1b1-1, 0 j2 b2-2,n維數(shù)組地址公式,推廣到n維數(shù)組，有： loc(j1,j2,jn)=loc(0,0,0)+ (b2*bn*j1+ b3*bn*j2+ bn*bn-1*jn)*L,cn=

3、L, ci-1=bi*ci,二、數(shù)組的順序存儲表示和實現(xiàn),數(shù)組順序存儲表示,# include # define MAX_ARRAY_DIM 8 typedef struct ElemType *base; int dim; int *bounds; int *constants; Array;,數(shù)組維界基址，boundsi存放第i維大小bi,數(shù)組映像函數(shù)常量基址，共dim個,基本操作的函數(shù)原型說明,Status InitArray(Array /若下標(biāo)不超界，將e的值賦予指定的A的元素并返回OK,準(zhǔn)備知識,typedef void *va_list /變長參數(shù)表類型 va_start(ap,

4、parmN) (ap=) /va_list類型數(shù)組ap中存放有函數(shù)的變長參數(shù)列表的每個值，將指針指向parmN后； va_arg(ap,type) (*(type*)(ap)+) /返回ap數(shù)組當(dāng)前指針?biāo)竼卧闹?，且指針下移一位?va_end(ap) (),2. 基本操作的算法描述,初始化 Status InitArray(Array ,續(xù),va_end(ap); / 各維長度獲取完 A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType); if(!A.base) exit(OVERFLOW); A.constants=(int*)mallo

5、c(dim*sizeof(int); if(!A.constants) exit(OVERFLOW); A.constantsdim-1=1; /指針移動是以元素計算的 for(i=dim-2;i=0;- -i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK;,求相對地址Locate(A, ap, off),Status Locate(Array A, va_list ap, int ,獲取某個元素,Status Value(Array A, Elemtype ,給某個元素重新賦值,Status Assign(Array ,5.3 矩陣的

6、壓縮存儲,一、特殊矩陣 1. n階對稱陣 特征：aij=aji , 1 i , j n 存儲空間個數(shù)：,在數(shù)值分析中經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時矩陣中有許多值相同的元素或者零元素，為了節(jié)省存儲空間，可以對這類矩陣進(jìn)行壓縮存儲。 特殊矩陣：值相同的元素或零元素在矩陣中的分布有一定的規(guī)律。,稀疏矩陣,n(n+1)/2,？如果是上三角對稱矩陣呢,續(xù)前,以下三角為例，設(shè)San(n+1)/2作為n階對稱陣A的存儲結(jié)構(gòu)，則Sak和aij的關(guān)系為：,5.3 矩陣的壓縮存儲,2. 對角矩陣,d:半帶寬 2d+1：帶寬,n*(2d+1)-d(d+1) 個非零元,二、稀疏矩陣,什么是稀疏矩陣？簡單說，設(shè)矩陣A

7、中有s個非零元素，若s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)（即smn），則稱A為稀疏矩陣。 設(shè)在的矩陣A中，有t個非零元素。令 =t/(m*n), 稱為矩陣的稀疏因子,通常認(rèn)為 0.05時稱之為稀疏矩陣。,二、稀疏矩陣,1. 抽象數(shù)據(jù)類型稀疏矩陣的定義（教材P9697） 2. 稀疏矩陣的三元組表示 由于非零元素的分布一般是沒有規(guī)律的，因此在存儲非零元素aij的同時，還必須同時記下它所在的行和列的位置（i,j)。 一個三元組(i,j,aij)唯一確定了矩陣A的一個非零元。因此，稀疏矩陣可由表示非零元的三元組及其行列數(shù)唯一確定。,續(xù),#define MAXSIZE 12500 typedef struct in

8、t i,j; Elemtype v;Triple;,typedef struct Triple dataMAXSIZE+1; int mu,nu,tu;TSMatrix;,3. 稀疏矩陣的轉(zhuǎn)置算法,Status TransposeSMatrix(TSMatrix M,TSMatrix ,O(nu*tu),三、十字鏈表,1. 稀疏矩陣的十字鏈表表示,typedef struct OLNode int r,c; ElemType v; struct OLNode *right,*down; OLNode, *OLink;,typedef struct OLink *rhead,*chead; in

9、t mu,nu,tu; CrossList;,5.4 廣義表,廣義表（Lists，又稱列表）是線性表的推廣。 一、廣義表的定義 LS是n（n0）個元素的有限序列 LS=（1, 2, 3, n) n是LS的長度 i（1i n）既可以是單個元素，也可以是表。,原子,子表,LS是由表頭元素（Head）加后面的表尾（Tail）構(gòu)成。,續(xù),A=（） 空表，n=0， 深度為1 B=（a,(b,c)） n=2，Head=a, Tail=(b,c)，深度為2 C=(A,B,B) n=3, 3個子表，A，B，C，深度為3 D=(a,D) n=2，是一個遞歸表，深度為 E=() n=1, 深度為2 二、抽象數(shù)據(jù)類

10、型廣義表的定義 詳見書P107108,5.4 廣義表,三、廣義表的鏈?zhǔn)奖硎?表節(jié)點的表頭指針,下一個元素節(jié)點,typedef enumATOM,LIST ElemTag /ATOM=0;LIST=1 typedef struct GLNode ElemTag tag; union ATomType atom; struct GLNode *hp;ptr; struct GLNode *tp;*GList;,續(xù),A=（）；B=（a,(b,c)）；C=(A,B,B) ； D=(a,D) ；E=(),四、廣義表的算法,1. 求廣義表的長度 int GList_Length(GList L) if(!

11、L) return 0; p=L-ptr.hp; len=0; while(p) p=p-tp; len+; return len; ,續(xù),2. 求廣義表的深度 int GList_Depth(GList L) if(!L) return 0; dep=0; if(L-tag=LIST) p=L-ptr.hp; dep+; else p=L-tp; if(!p) return dep; if(p-tag=ATOM) return(dep+GList_Depth(p-tp) ; else dep1=dep+GList_Depth(p-ptr.hp); dep2=dep+GList_Depth(p-tp);