商大計算機專業(yè)天津商業(yè)課件

1、第五章數(shù)組和廣義表5.15.25.35.45.5數(shù)組的定義數(shù)組的順序矩陣的壓縮廣義表的定義表示廣義表的結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)Data Structure1考核要點識記：數(shù)組和廣義表的定義，數(shù)組的行主序、列主序排列順序理解：數(shù)組和廣義表的結(jié)構(gòu)應用：數(shù)組和矩陣運算DataStructure2數(shù)據(jù)結(jié)構(gòu)5.1 數(shù)組的定義數(shù)組概念：相同類型的數(shù)據(jù) a00a01.a0,的集合；2) 數(shù)組類型：a10a11.a1,一維、二維、 n維； .am 1,0am 1,1am n 1 n 1 . 1, n 1數(shù)據(jù)結(jié)構(gòu)Data Structure35.1 數(shù)組的定義二維數(shù)組的邏輯結(jié)構(gòu)：A為mn二維數(shù)組。P91A可看成下述線性表：

2、A=(d0，d1，dn-1)dj 是列向量線性表：圖5.1 (b)dj =(d0j ,d1j ,.,dm-1j )或di是行向量線性表：圖5.1 (c)di =(di0 ,di1 ,.,din-1 )數(shù)據(jù)結(jié)構(gòu)Data Structure45.1 數(shù)組的定義二維數(shù)組元素的邏輯關(guān)系：A中每個元素aij 均屬于兩個向量，第i行的向量第j列的向量。除邊界外，每個元素aij 都恰好有兩個直接前趨直接后繼。00010203101112132021222330313233和和數(shù)據(jù)結(jié)構(gòu)Data Structure55.1 數(shù)組的定義二維數(shù)組的基本運算：初始化銷毀讀：給定一組下標，存取相應元素的值。寫：給定一組

3、下標，修改相應元素的值。數(shù)據(jù)結(jié)構(gòu)Data Structure65.2數(shù)組的順序表示1)數(shù)組的結(jié)構(gòu)：P91數(shù)組一般不進行和刪除操作；由于單元是一維結(jié)構(gòu)，數(shù)組是結(jié)構(gòu)，將數(shù)組按某種次序排成一個線性序列，然后存入內(nèi)數(shù)組器。方式：順序；圖5.2FORTRAN；C、PASCAL；以列序為主序(a)：以行序為主序(b)：DataStructure7數(shù)據(jù)結(jié)構(gòu)數(shù)組的順序表示舉例00102030011121310212223203132333(1)按行(2) 按列數(shù)據(jù)結(jié)構(gòu)Data Structure8001020300111213102122232031323330001020310111213202122233

4、03132335.2數(shù)組的順序表示2)二維數(shù)組mn的任一元素aij的位置：行為主序：Loc(i,j)=loc(0,0)+(ni+j)列為主序：Loc(i,j)=loc(0,0)+(mj+i)LLLoc(0 ,0)二維數(shù)組的首地址Loc（i,j），是aij 的位置每個元素占L個單元0 im-1， 0 jn-1數(shù)據(jù)結(jié)構(gòu)Data Structure95.2數(shù)組的順序表示3)數(shù)組的順序表示：P93#define MAX_ARRAY_DIMtypedef structElemType *base ； dim；*bounds；*constants；Array；8DataStructure10數(shù)據(jù)結(jié)構(gòu)5.2

5、數(shù)組的順序表示4)數(shù)組的操作實現(xiàn)：P93構(gòu)造數(shù)組銷毀數(shù)組元素定位讀元素值元素賦值數(shù)據(jù)結(jié)構(gòu)Data Structure115.3矩陣的壓縮1.基本概念2.對稱矩陣3.三角矩陣4.稀疏矩陣數(shù)據(jù)結(jié)構(gòu)Data Structure121.基本概念1)壓縮基本一個：P95：在矩陣中為多個值相同的元素只分配單元，對零元不分配單元；2)特殊矩陣和稀疏矩陣：在一些階數(shù)很高的矩陣中，同時存在許多值相同的元素或零元素的分布有一定的規(guī)律，稱此矩陣為特殊矩陣，反之稱為稀疏矩陣；常見特殊矩陣：對稱矩陣和三角矩陣DataStructure13數(shù)據(jù)結(jié)構(gòu)2.對稱矩陣1)111213122212131211滿足下述性質(zhì)：n階矩陣

6、a =a1i,jn下三角元素；ijji結(jié)構(gòu)：2)用一維數(shù)組：san(n+1)/23)aij和位置sak的對應關(guān)系：ij：k=i(i-1)/2+j-1ij：k=j(j-1)/2+i-14)壓縮： 圖5.3 P96san(n+1)/2為n階對稱A的壓縮；DataStructure14數(shù)據(jù)結(jié)構(gòu)3.三角矩陣1)下(上)三角矩陣：矩陣的上(下)三角(不包括主對角線)的元素為常數(shù)或零的n階矩陣；a00a0111.c.a0,n11,n1. a00c.c c. c aaaa . c1011.an1,1an1,0an1,n1an1,n1上三角矩陣下三角矩陣DataStructure15數(shù)據(jù)結(jié)構(gòu)3.三角矩陣2)結(jié)

7、構(gòu)：下/上三角元素；用一維數(shù)組：Mn(n+1)/2+13)下三角aij和位置Mk的對應關(guān)系：(0in-1)ij：k=i(i+1)/2+jij：k=n(n+1)/2(常數(shù)C的位置)4)上三角aij和位置Mk的對應關(guān)系：(0in-1)ij：k=i(2n-i+1)/2+j-iij：k=n(n+1)/2(常數(shù)C的位置)DataStructure16數(shù)據(jù)結(jié)構(gòu)4.稀疏矩陣稀疏矩陣：P96含義：非零元素較零元素少，且分布沒有一定規(guī)律；稀疏因子：=t/(mn)稀疏矩陣： 0.05數(shù)據(jù)結(jié)構(gòu)Data Structure174.稀疏矩陣2)稀疏矩陣壓縮方法：三元組順序表：順序結(jié)構(gòu)不僅位置；非0元素，還要它所在行和列

8、的行邏輯的順序表：順序結(jié)構(gòu)，P100；鏈表：鏈式結(jié)構(gòu)，P103；DataStructure18數(shù)據(jù)結(jié)構(gòu)4.稀疏矩陣3)三元組結(jié)點： (i, j, aij)稀疏矩陣零元的三元組及其行列數(shù)唯一確定；i：為v所在的行數(shù)；j：為v所在的列數(shù)；aij：為非0元素；舉例：三元組表(1,2,12),(1,3,9),(3,1,-3), (3,6,14), (4,3,24),(5,2,18), (6,1,15), (6,4,-7),(6,7,8)123 90000000000M 00240000 00DataStructure19數(shù)據(jù)結(jié)構(gòu)ijaij4.稀疏矩陣5)三元組順序表表示：#define MAXSIZE

9、typedef struct12500i,j；ElemType e；Triple；/*定義結(jié)點*/typedef struct Triple dataMAXSIZE+1；/ mu,nu,tu；TSMatrix； /*定義三元組*/data0不用DataStructure20數(shù)據(jù)結(jié)構(gòu)5.4 廣義表的定義廣義表的定義和基本概念：P106含義： lists，也稱列表，線性表的推廣；應用：AI的LISP語言；表示：LS=(a1，a2，an)LS：表名,用大寫字母表示；n：表的長度；術(shù)語： ai(1in)原子(小寫)(線性表為單個元素)子表表頭表尾；數(shù)據(jù)結(jié)構(gòu)Data Structure215.4廣義表的

10、定義2)廣義表的基本運算：創(chuàng)建一個空表；判斷表空；表；元素刪除元素取廣義表的表頭；取廣義表的表尾；DataStructure22數(shù)據(jù)結(jié)構(gòu)5.4 廣義表的定義廣義表舉例：A =（）：空表，n=0；B =（e）：1個原子，n=1；C =（a,(a,b,c,d)）：1個原子和1個子表，n=2D =（A,B,C）：3個列表，n=3；E =（a,E）：遞歸表，n=2；數(shù)據(jù)結(jié)構(gòu)Data Structure235.4 廣義表的定義廣義表的特點：廣義表是一個多層次的數(shù)據(jù)結(jié)構(gòu)，可以用圖形象表示，圖5.7；廣義表可以為其它列表所共享，通過子表的名稱用；廣義表可以是一個遞歸的表；任何一個非空列表，表頭可能是原子，也

11、可能是表，而其表尾必定為列表。地引子數(shù)據(jù)結(jié)構(gòu)Data Structure245.4 廣義表的定義廣義表運算舉例：GetHead(B) = eGetTail(B) = ( )GetHead(D) = AGetTail(D) = (B,C)GetHead(GetTail(D) = BGetTail(B,C) = (C)數(shù)據(jù)結(jié)構(gòu)Data Structure255.4廣義表的定義6)注意：不能對空表求表頭和表尾運算；表尾用( )擴起來；列表LS=()和LS=()的區(qū)別：LS=()：為空表，n=0；LS=()：n=1,表頭和為空表()；數(shù)據(jù)結(jié)構(gòu)Data Structure265.5廣義表的結(jié)構(gòu)1)廣義表

12、的采用鏈式結(jié)構(gòu)：結(jié)構(gòu)頭尾鏈表表示擴展線性鏈表表示每個數(shù)據(jù)元素用一個結(jié)點表示結(jié)點如何表示？DataStructure27數(shù)據(jù)結(jié)構(gòu)5.5廣義表的結(jié)構(gòu)2)頭尾鏈表結(jié)點結(jié)構(gòu)：需要兩種結(jié)構(gòu)；P109表結(jié)點：表示列表,3個指針域標志域表頭表尾原子結(jié)點：表示原子,2個指針域值域標志域數(shù)據(jù)結(jié)構(gòu)Data Structure28tag=0atomtag=1hptp5.5 廣義表的結(jié)構(gòu)3)頭尾鏈表的表示：typedef enumATOM，LISTtypedef struct GLNode ElemTag tag； unionAtomType atom ；ElemTag；struct； *Glist；GLNode *hp,*tp；ptr；DataStructure29數(shù)據(jù)結(jié)構(gòu)廣義表結(jié)構(gòu)示例A=NILCB11DE圖 5