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

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