數(shù)據(jù)結(jié)構(gòu)數(shù)組與廣義表5

1、第五章 數(shù)組第一節(jié) 數(shù)組的定義1定義 一個(gè) N 維數(shù)組是受 N 組線 性關(guān)系所制約的線性表。2示例：二維數(shù)組A=a00 a01. a0,n-1a10 a11. a1,n-1am-1,0. am-1,n-1單獨(dú)從行看,為一線性表；單獨(dú)從列看,也為一線性表。 因此，二維數(shù)組可形式地表示為： 2_Array=(D,R) D=aij | i=0.m-1, j=0.n-1 R=Row,Col Row= |0i m-1, 0 j n-2 Col = |1i m -2,0 j n-12ADT Array數(shù)據(jù)對(duì)象: D數(shù)據(jù)關(guān)系:R基本操作:initarray(&A,n,bound ); bound = b1,

2、b2.bn destroyarray (&A);value(A,&e,index ); index = i1,i2,.inassign(&A,e,index );3 N 維數(shù)組的抽象類型定義：3第二節(jié) 數(shù)組的順序存儲(chǔ)與實(shí)現(xiàn) 思想: 用一組連續(xù)的空間依次存放數(shù)組元素。 （按行或按列存儲(chǔ)） 假設(shè)數(shù)組元素為：Aj1，j2，.jn, 那么該元素存放在哪個(gè)地址空間中?4A=a00 a01. a0,n-1a10 a11. a1,n-1am-1,0. am-1,n-11 二維數(shù)組的按行存儲(chǔ)及地址計(jì)算a00 a01. a0,n-1 a10 a11. a1,n-1 . am-1,0. am-1,n-1 loc(

3、i,j)=loc(0,0)+(b2*i+j)Lb1=m;b2=n2 n維數(shù)組的按行存儲(chǔ)及地址計(jì)算5設(shè) b1, b2,.bn為各維的長(zhǎng)度;L為數(shù)組元素長(zhǎng)度; j1,j2,.jn為各維的下標(biāo)。loc(j1,j2,.jn)=loc(0,0,.0)+ (b2 b3 bn j1+ b3 bn j2+ bn jn-1+ jn)L可縮寫為： loc(j1,j2,.jn)=loc(0,0,.0)+ ci ji其中： cn =L， ci-1= bi ci, 1 基本操作的實(shí)現(xiàn)#define Max_Array_dim= 8typedef struct Elemtype *base; int dim; int *

4、bounds; int *constants;Array;7Status initarray(Array &A,int n,int bound ); if(n Max_Array_dim) return Error; A.dim=n; A.bounds=(int *)malloc(n*sizeof(int); if(!A.bounds) return Error; elemtotal=1; for (i=0;in;+i) A.boundsi=boundi; if (boundi=0;-i) A.constantsi=A.boundsi+1*A.constantsi+1; return OK;9

5、Status destroyarray(Array &A)if (!A.base) return Error; free(A.base); A.base=Null; if(!A.bounds) return Error; free(A.bounds);A.bounds=Null; if(!A.constants) return Error; free(A.constants);A. constants =Null; return OK;10Status value(Array A,elemtype &e,int index ); off=0; for(i=0;iA.dim;+i) if(ind

6、exi=A.boundsi) return Error; off+=A.constantsi*indexi; e=*(A.base+off); return OK; 11Status Assign(Array &A,elemtype e,int index ); off=0; for(i=0;iA.dim;+i) if(indexi=A.boundsi) return Error; off+=A.constantsi*indexi; *(A.base+off) = e; return OK; 12第三節(jié) 矩陣的壓縮存儲(chǔ) 定義:若矩陣中存在大多數(shù)值相同的元素,且在矩陣中的分布有一定規(guī)律,稱這種矩

7、陣為特殊矩陣。 若矩陣中存在少量的非零元素，且在矩陣中的分布無(wú)規(guī)律,稱這種矩陣為稀疏矩陣。13一 對(duì)稱矩陣 aij=aji 0i,j n-1A=a00 a01. a0,n-1a10 a11. a1,n-1an-1,0. an-1,n-1只需存儲(chǔ)對(duì)稱矩陣的下半部分。所需空間數(shù)為 n（n+1）/2。a00a10 a11. an-1,0 an-1,1 . an-1,n-1 SASAk= aijK=i(i+1)/2+j i=jj(j+1)/2+i i 稀疏矩陣的順序存儲(chǔ)結(jié)構(gòu)表示 三元組空間: 行數(shù) : m 列數(shù) : n 非零個(gè)數(shù) : num 三元組:三元組1 三元組2 行號(hào) 列號(hào) 元素值16#defi

8、ne Maxsize=1000typedef struct int i , j; elemtype e; tripletypedef struct triple dataMaxsize+1 int m , n , num; TSmatrix三元組:三元組順序矩陣172 稀疏矩陣的基本操作CreatSmatrix(&M)DestroySmatrix (&M)PrintSmatrix (M)CopySmatrix (M,&M1)AddSmatrix (M1,M2,&M)SubSmatrix (M1,M2,&M)MultSmatrix (M1,M2,&M)TransposeSmatrix (M,&T

9、)183 稀疏矩陣相加070040000050000004000mn000020003000000004000mn+070060003050000008000mn=19+=(152)(223)(344)(475)(ije)m n num 4 7 4(127)(156)(223)(245)(348)(439)(477)(ije)m n num 4 7 7(127)(154)(245)(344)(439)(472)(ije)m n num 4 7 6 M1 M2 Mp1p2p20void AddSmatrix (TSmatrix M1, TSmatrix M2, TSmatrix &M) M.n=

10、M1.n; M.m=M1.m; p1=1;p2=1;p=0; while (p1=M1.num &p2=M2.num) if (m1. datap1.i= m2. datap2.i& m1. datap1.j= m2. datap2.j) M.data+p=M1.datap1+; M.datap.e+=M2.datap2+.e; else if (m1. datap1.i m2. datap2.i| m1. datap1.i= m2. datap2.i & m1. datap1.j m2. datap2.j) M.data+p=M1.datap1+; else M.data+p=M1.data

11、p2+; while (p1=M1.num ) M.data+p=M1.datap1+; while (p2 稀疏矩陣轉(zhuǎn)置運(yùn)算1000030000000040200000050006 7 4 10002000300000000400047=T22(111)(152)(223)(344)(465)(476)(ije)m n num 4 7 6(111)(223)(434)(512)(645)(746)(ije)m n num7 4 6轉(zhuǎn)置算法思想: (1) i , j 互換;(2) m , n 互換; (3) 重排三元組順序;23Status TransposeSmatrix (TSmatrix

12、 M, TSmatrix &T) T.m=M.n; T.n=M.m; T.num=M.num; pt=1; for (col=1;col=M.n;+col) for(pm=1;pm=M.num;+pm) if(M.datapm.j=col) T.datapt.i=M.datapm.j; T.datapt.j=M.datapm.i; T.datapt.e=M.datapm.e; +pt; return OK;24第四節(jié) 廣義表一 概念 定義: 廣義表是一種擴(kuò)展線性表: Lists=（d1，d2，.dn) lists 為表名; n 為表長(zhǎng); D=d1，d2，.dn; D0=基本數(shù)據(jù)對(duì)象; 若diD

13、0,稱di為L(zhǎng)ists 的單元素; 若di 廣義表,稱di為L(zhǎng)ists的子表; d1 為表頭; （d2，.dn)為表尾。 習(xí)慣上,用大寫字母表示表名,小寫字母表示單元素。25廣義表示例: A=( ) ; 空表 B=(e) ; n=1, 表頭=e, 表尾=( ) C=(a,(b,c,d) ; n=2, 表頭=a, 表尾=(b,c,d) ) D=(A,B,C) ; n=3, 表頭=A, 表尾=(B,C ) E=(a,E) ; n=2, 表頭=a, 表尾=(E ) E 稱為遞歸表26二 廣義表的基本操作InitGlist(&L) CreatGlist(&L,S)Destro y Glist (&L)PrintGlist (L)CopyGlist (&L1, L)Glistlength (L)Glistdepth(L)Glistempty (L)Gethead (L)Gettail(L)insertfirst(&L,e)deletefirst(&L,&e)TraverseGlist (L)27三 廣義表鏈?zhǔn)酱鎯?chǔ)表示 di 有兩種類型:單元素,表。 表可以分成表首和表尾。單元素結(jié)點(diǎn)：（原子結(jié)點(diǎn)）表結(jié)點(diǎn)： 表首指針 表尾指針 tag=1 hp tp tag=0atom