1、第五章 數(shù)組與廣義表,數(shù)組的定義及使用 特殊矩陣 *廣義表的定義及使用,【教學(xué)目的】掌握一維、二維及多維數(shù)組的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)；特殊矩陣的壓縮存儲(chǔ)；稀疏矩陣的順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其操作；廣義表的邏輯結(jié)構(gòu)理解、存儲(chǔ)結(jié)構(gòu)及應(yīng)用 【教學(xué)重點(diǎn)】二維數(shù)組、特殊矩陣、稀疏矩陣存儲(chǔ)及操作、廣義表的；邏輯結(jié)構(gòu)及物理結(jié)構(gòu) 【教學(xué)難點(diǎn)】稀疏矩陣的三元組和十字鏈表表示存儲(chǔ)方法、廣義表的理解及存儲(chǔ)結(jié)果 。,5.1 數(shù)組,一、 數(shù)組定義 同類型的數(shù)據(jù)元素的集合 從邏輯結(jié)構(gòu)上看，數(shù)組是線性表的推廣： n維數(shù)組可以看成是一個(gè)特殊的一維數(shù)組，每個(gè)數(shù)組元素又是一個(gè)n-1維的數(shù)組 （書上定義：是由n(n1)個(gè)相同類型數(shù)據(jù)元素a

2、0，a1，an-1組成的有限序列，且該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中，是順序存儲(chǔ)結(jié)構(gòu)。）,二、數(shù)組的內(nèi)存映像 采用順序存儲(chǔ)結(jié)構(gòu) 元素存放次序的約定 以行為主序的存儲(chǔ)方式 以列為主序的存儲(chǔ)方式 -隨機(jī)存取,數(shù)組中的數(shù)據(jù)元素地址的計(jì)算： (1) 一維數(shù)組an: 元素按下標(biāo)從小到大存儲(chǔ) Loc(ai)= Loc(a0)+i*s ；(元素占s個(gè)字節(jié)) DataType v; triple;,typedef struct triple datamaxsize; int m,n,t; tripletable;,例：稀疏矩陣轉(zhuǎn)置 一個(gè)mn的矩陣A，它的轉(zhuǎn)置B是一個(gè)nm的矩陣， 且aij=bji,fo

3、r(i=0;im;i+) for(j=0;jn;j+) bji= aij;,稀疏矩陣轉(zhuǎn)置：將矩陣稀疏A轉(zhuǎn)置為稀疏B，并且保持存儲(chǔ)的行序優(yōu)先順序，及B的存儲(chǔ)順序表也是按照B的行序優(yōu)先,轉(zhuǎn)置算法1： 算法思想：按列 col(1coln)掃描三元表a.data,找出所有列號(hào)等于col的那些三元組,將它們的行號(hào)和列號(hào)互換后依次放入b.data中 跳著找，順著存,1 23,2 17,2 46,4 14,5 31,轉(zhuǎn)置算法1的算法,void transmatrix(tripletable *b, tripletable *a) /* 將稀疏矩陣a轉(zhuǎn)置，結(jié)果通過函數(shù)名返回 */ int p,q,col; b

4、-m=a-n; b-n=a-m; b-t=a-t; /* 初始化 */ if(b-t) /* 把a(bǔ)中每一個(gè)非零元素轉(zhuǎn)換到b中相應(yīng)位置 */ q=0; A（轉(zhuǎn)置每一個(gè)非零元） ,轉(zhuǎn)置算法1的算法的A for(col=1;coln;col+) /* 按列號(hào)作掃描，做cols趟 */ for(p=0;pt;p+) /* 在數(shù)據(jù)中找列號(hào)為col的三元組 */ if(a-datap.j=col) b-dataq.i=a-datap.j; /* 新三元組的行號(hào) /* b-dataq.j=a-datap.i; /* 新三元組的列號(hào) /* b-dataq.v=a-datap.v; /* 新三元組的值/* q+

5、; O(a-n*a-t) 其中t為稀疏矩陣元素個(gè)數(shù)，當(dāng)tm*n 時(shí)間代價(jià)為O(m*n2)；本算法適用于Tm*n,轉(zhuǎn)置算法2（快速轉(zhuǎn)置）： 算法思想：假設(shè)知道每個(gè)非零元在轉(zhuǎn)置后的三元組中的位置，則可以按行掃描A的三元表的元素順著找，跳著存,1 23,2 17,2 46,4 14,5 31,轉(zhuǎn)置算法2： 算法思想：快速轉(zhuǎn)置 轉(zhuǎn)換為求個(gè)非零元在轉(zhuǎn)置后三元組中的位置，其實(shí)不必知道每個(gè)非零元在轉(zhuǎn)置后的位置，只要知道原A矩陣的每一列的第一個(gè)非零元在轉(zhuǎn)置后的三元組中的位置即可。,1 23,2 17,2 46,4 14,5 31,2,4,1,5,3,快速轉(zhuǎn)置的原A矩陣的每一列（B的每一行）的第一個(gè)非零元的位置

6、的求法： numj表示矩陣A中的第j列非零元素個(gè)數(shù) potj表示A矩陣中第j列下一個(gè)非零元素在B中應(yīng)存放的位置（初值為該列第一個(gè)非零元素在B中應(yīng)存放的位置循環(huán)中動(dòng)態(tài)的改變）有： pot1=0 potj=potj-1+numj-1 2ja.n,1 2 0 1 1,0,1,3,3,4,快速轉(zhuǎn)置的算法,void fasttranstri(tripletable *b ,tripletable *a) int p,q,col,k; int numN+1,potN+1; /* 建立輔助數(shù)組 */ b-m=a-n; b-n=a-m; b-t=a-t; if(b-t) . .,快速轉(zhuǎn)置的算法,/求pot f

7、or(col=1;coln;+col) numcol=0; /* 對(duì)數(shù)組num初始化 */ for(k=0;kt;+k) /計(jì)算a中每一列含非零元素的個(gè)數(shù) +numa-datak.j; pot1=0; for(col=2;coln;+col) potcol= potcol-1+numcol-1;,快速轉(zhuǎn)置的算法,/ 把a(bǔ)中每一個(gè)非零元素插入到b中的相應(yīng)位置 for(p=0;pt;+p) col=a-datap.j; q=potcol; b-dataq.i=a-datap.j; b-dataq.j=a-datap.i; b-dataq.v=a-datap.v; +potcol; /修改為下次該列

8、元素該存儲(chǔ)的位置 ,2、十字鏈表 對(duì)三元組采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 每個(gè)非零元素-包含5個(gè)域的結(jié)點(diǎn),三元組：row行col列值為value 兩個(gè)鏈域： right指向本行下一個(gè)非零元 down指向本列下一個(gè)非零元,結(jié)點(diǎn)結(jié)構(gòu)： typedef struct node int row,col; DataType value; struct node *down, *right; crossnode; 例：,typedef struct crossnode *rheadM,*cheadM; int m,n,t; crosslist;,typedef struct crossnode *rhead,*chea

9、d; int m,n,t; crosslist;,crosslist *creatclinkmat( ) int m, n, t, i, j, k, c; crosslist *head, *p,*q,*ph; scanf(“%d,%d, %d”, ,for( j=1;jrow=p-col=p-value=0; p-down=p; pright= head-right; head-right=p; for (k=0;krow=i; p-col=j; p-value=v;,qh=head; c=0; while(qh-down!=head ,三、 廣義表,1、定義：是n0個(gè)元素a1，a1，an的

10、有限序列，即： Ls(a1，a2，an) 其中：,（1）Ls是廣義表的名稱，n是它的長(zhǎng)度。ai可以是單個(gè)元素，也可以是廣義表 （2）若ai是單個(gè)元素，則稱為表Ls的原子，若ai是廣義表，則稱為L(zhǎng)s的子表。 當(dāng)Ls非空時(shí)，a1為L(zhǎng)s的表頭(Head)，其余元素組成的表(a2，a3，an)為表尾(Tail),1、定義：是n0個(gè)元素a1，a1，an的有限序列，即： Ls(a1，a2，an),（1）Ls是廣義表的名稱，n是它的長(zhǎng)度。ai可以是單個(gè)元素，也可以是廣義表 （2）若ai是單個(gè)元素，則稱為表Ls的原子，若ai是廣義表，則稱為L(zhǎng)s的子表。 當(dāng)Ls非空時(shí)，a1為L(zhǎng)s的表頭(Head)，其余元素組成

11、的表(a2，a3，an)為表尾(Tail),注意：表尾一定是廣義表,遞歸定義,2、例子：,A（ ） A是一個(gè)空表，其長(zhǎng)度為0。 B（b , c） B是一個(gè)長(zhǎng)度為2的列表。 C（a ,（d , e , f）C是一個(gè)長(zhǎng)度為2的列表，其中第一個(gè)元素是原子a，第二個(gè)元素是子表（d , e , f）。 D=(A , B , C) D是一個(gè)長(zhǎng)度為3的列表，其中三個(gè)元素都是子表。 E（a , E） E是一個(gè)長(zhǎng)度為2的列表，它是一個(gè)遞歸表,一般大寫字母表示廣義表（或子表），小寫字母表示單個(gè)元素（或原子）,廣義表的特點(diǎn)： 廣義表中的元素可以是原子也可以是子表，廣義表是一個(gè)多層次結(jié)構(gòu) 廣義表是可以共享的。如廣義表

12、B是D的子表 廣義表允許遞歸，如廣義表E是一個(gè)遞歸表 廣義表的元素間存在次序關(guān)系和層次關(guān)系，廣義表展開后包含的括號(hào)層數(shù)稱為廣義表的深度。如C的深度為2，E的深度為,3、廣義表的圖形表示：,4、廣義表的存儲(chǔ)結(jié)構(gòu),typedef struct GenealNode int tag; /* 0.1；取0表示原子節(jié)點(diǎn) ，取1表示子表節(jié)點(diǎn)*/ union DataType data; struct struct GenealNode *hp,*tp;ptr; ld; *GList;,注：tag0，tag分量和DataType分量有效 tag1， tag分量和 *hp、*tp分量有效,5、廣義表的基本算法

13、,（1）取表頭GetHead()和取表尾GetTail(),如：GetHead(B)=b GetTail(B)=(c) GetHead(C)=a GetTail(C)=(d,e,f) GetHead(D)=A GetTail(D)=(B,C),5、廣義表的基本算法,GList GetHead(GList p) /*表空時(shí)返回null， 否則返回表頭指針*/ if (!p) printf(“空表”); return (NULL); return(p-hp); ,Glist GetTail(Glist p) /*空表或是單個(gè)原子,函數(shù) 無意義否則返回表尾指針*/ if (!p|!p-tag) printf(“空表或是單個(gè)原子”); return (NULL); return(p-tp); ,取表頭GetHead()和取表尾GetTail()算法,5、廣義表的基本算法,求廣義表深度算法,深度定義：指廣義表中所含括號(hào)的重?cái)?shù) 。廣義表是遞歸定義的，求深度也采用遞歸思想,int depth(Glist ls) /廣義表的基本深度算法 int max,dep;G