數(shù)據(jù)結(jié)構(gòu)C語言版.ppt

中國網(wǎng)頁設(shè)計 ,數(shù) 據(jù) 結(jié) 構(gòu) （C語言版）,嚴蔚敏、吳偉民編著 清華大學(xué)出版社 學(xué)習(xí)網(wǎng)站：/list.asp?id=301,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,主要內(nèi)容： 一、數(shù)組的定義 二、數(shù)組的表示和實現(xiàn) 三、矩陣的壓縮存儲 四、廣義表的定義 五、廣義表的存儲結(jié)構(gòu),中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,數(shù)組是由n(n1)個具有相同數(shù)據(jù)類型的數(shù)據(jù)元素a1，a2，an組成的有序序列。這n個數(shù)據(jù)元素占用一塊地址連續(xù)的存儲空間。 數(shù)組中的數(shù)據(jù)元素具有相同數(shù)據(jù)類型。 數(shù)組是一種隨機存取結(jié)構(gòu)，給定一組下標，就可以訪問與其對應(yīng)的數(shù)據(jù)元素。 數(shù)組中的數(shù)據(jù)元素個數(shù)是固定的。 數(shù)組是一種特殊的線性表，表中的元素可以是原子類型，也可以是一個線性表。,中國網(wǎng)頁設(shè)計 ,數(shù)組的定義,數(shù)組中的數(shù)據(jù)元素可以是原子類型的，如整型、字符型、浮點型等，這種類型的數(shù)組稱為一維數(shù)組；也可以是一個線性表。二維數(shù)組可以看成是線性表的線性表。,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,二、數(shù)組的表示和實現(xiàn) 1、數(shù)組類型特點 1)數(shù)組除了初始化和銷毀外，只有存取元素和修改元素值的操作，不對數(shù)組進行插入和刪除操作。 2) 數(shù)組是多維的結(jié)構(gòu)，而存儲空間是一個一維的結(jié)構(gòu)。 2、兩種順序映像方式 1)以行序為主序(低下標優(yōu)先)； 2)以列序為主序(高下標優(yōu)先)。,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,以行序為主序的求址公式： 假設(shè)每個數(shù)據(jù)元素占L個存儲單元，則二維數(shù)組A中任一元素aij的存儲位置可由下式確定： LOC(i, j) = LOC(0, 0) + (ni + j)*L 式中，LOC(i, j)是aij的存儲位置，LOC(0, 0)是a00的存儲位置，即二維數(shù)組A的起始存儲位置，也稱為基地址或基址。b2是數(shù)組第二維的長度，即數(shù)組A(mn)中的列數(shù)n。,中國網(wǎng)頁設(shè)計 ,思考題：設(shè)有數(shù)組Ai,j,數(shù)組每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，且數(shù)組從內(nèi)存首地址BA開始順序存放。 以列序為主存放時，元素A5，8的存儲首地址為（ ） 以行序為主存放時，元素A5，8的存儲首地址為（ ）。,中國網(wǎng)頁設(shè)計 ,以列序為主序的求址公式： LOC(i, j) = LOC(0, 0) + (jm + i)*L,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,三、矩陣的壓縮存儲 所謂的壓縮存儲是指：為多個值相同的元只分配一個存儲空間；對零元不分配存儲空間。 若值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則稱此類矩陣為特殊矩陣；反之稱為稀疏矩陣。,中國網(wǎng)頁設(shè)計 ,特殊矩陣,(1)對稱矩陣：,定義 若n階矩陣A中的元滿足下述性質(zhì)： aijaji 1i，jn 則稱為n階對稱矩陣。,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,壓縮存儲 由于對稱矩陣中的元素關(guān)于主對角線對稱，因此，在對矩陣存儲時， 可以只存儲對稱矩陣中的上三角或者下三角的元素，使得對稱的元素共享一個存儲單元，則可將n2 個元壓縮存儲 到n(n+1)/2個元的空間中。我們以行序為主序存儲其下三角（包 括對角線）中的元。,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,中國網(wǎng)頁設(shè)計 ,有一個10階的對稱矩陣A，采用壓縮存儲方式以行序為主序存儲，A11為第一元素，其存儲地址為1，每個元素占一個地址空間，求A75和A56的地址。,隨堂練習(xí),中國網(wǎng)頁設(shè)計 ,對角矩陣的壓縮存儲,對角矩陣,也稱帶狀矩陣，是另一類特殊的矩陣。所謂對角矩陣，就是所有的非零元素都集中在以主對角線兩側(cè)的帶狀區(qū)域內(nèi)（對角線的個數(shù)為奇數(shù)）。也就是說除了主對角線和主對角線兩邊的對角線外，其他元素的值均為0.,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,2、稀疏矩陣 (1) 定義：假設(shè) m 行 n 列的矩陣含 t 個非零元素， 則稱 為稀疏因子。 通常認為 0.05 的矩陣為稀疏矩陣。,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,(2) 稀疏矩陣的存儲： 若按常規(guī)方法進行存儲，零值元素會占了很大空間 因此對于稀疏矩陣的存儲通常采用以下兩種方式： 三元組表和十字鏈表進行存儲。,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,四、廣義表的定義,中國網(wǎng)頁設(shè)計 ,廣義表中所包含的元素(包括原子和子表)的個數(shù)稱為表的長 度。 廣義表中括號的最大層數(shù)稱為表深 (度)。,中國網(wǎng)頁設(shè)計 ,2、廣義表表示,（1）廣義表常用表示 E=() E是一個空表，其長度為0。 L=(a，b) L是長度為2的廣義表，它的兩個元素都是原子，因此它是一個線性表 A=(x，L)=(x，(a，b) A是長度為2的廣義表，第一個元素是原子x，第二個元素是子表L。 B=(A，y)=(x，(a，b)，y) B是長度為2的廣義表，第一個元素是子表A，第二個元素是原子y。,中國網(wǎng)頁設(shè)計 , C=(A，B)=(x，(a，b)，(x，(a，b)，y) C的長度為2，兩個元素都是子表。 D=(a，D)=(a，(a，(a，() D的長度為2，第一個元素是原子，第二個元素是D自身，展開后它是一個無限的廣義表。 （2）廣義表的深度 一個表的“深度“是指表展開后所含括號的層數(shù)。 【例】表L、A、B、C的深度為分別為1、2、3、4，表D的深度為。,中國網(wǎng)頁設(shè)計 ,取廣義表頭的操作是getHead（） 取表尾的操作是getTail()，,中國網(wǎng)頁設(shè)計 ,隨堂練習(xí),1.設(shè)廣義表L=()，()，試問GetHead(L)，GetTail(L)的值，求L的長度和深度各為多少?,GetHead(L)和GetTail(L)的值是()和()。 L的長度和深度都是2。,中國網(wǎng)頁設(shè)計 ,2.廣義表(a,(a,b),d,e,(i,j),k)的長度是_ ，深度是_ 3.設(shè)廣義表L=（a,b,c），則L的長度和深度分別為（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3,5,3,c,中國網(wǎng)頁設(shè)計 ,3.求下列廣義表運算的結(jié)果：,(1) GetHead (p，h，w) GetTail(b，k，p，h) GetHead(GetTail(a，b)，(c，d) GetTail(GetHead(a，b)，(c，d),【解答】 (1) GetHead (p,h,w)=p (2) GetTail(b,k,p,h)=(k,p,h) (3) GetHead(GetTail(a，b)，(c，d)= GetHead(c,d)=(c,d) (4) GetTail(GetHead(a，b)，(c，d)=GetTail(a,b)=(b),中國網(wǎng)頁設(shè)計 ,第5章 數(shù)組和廣義表,思考題： 1、廣義表L=（a，（b，c），進行Tail（L）操作后的結(jié)果為（ ）。 A. c B. b，c C.（b，c） D.（b，c） 2、已知廣義表：A=（a,b），B=（A，A），C=（a,(b,A),B），則tail(head(tail(C)的運算結(jié)果為（ ）； 3、已知廣義表LS=（a，b，c）,（d，e，f ），則運用head和tail 函數(shù)取出LS中原子e的運算表達式為:,D,(A),(head(tail(head(tail(LS) ),中國網(wǎng)頁設(shè)計 ,4.