《數(shù)據(jù)結(jié)構(gòu)與算法（C++版）課件第四章多維數(shù)組和廣義表.pptx》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)與算法（C++版）課件第四章多維數(shù)組和廣義表.pptx（47頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、第四章-多維數(shù)組與廣義表數(shù)據(jù)結(jié)構(gòu)與算法(C語言版)線性結(jié)構(gòu)非線性結(jié)構(gòu)前幾章介紹的數(shù)據(jù)結(jié)構(gòu)都是線性結(jié)構(gòu)，數(shù)據(jù)元素都屬于原子類型，其值不分解使用。本章討論的多維數(shù)組和廣義表是線性結(jié)構(gòu)的推廣，從整體上看它們是多個(gè)元素組成的線性表，而從局部上看線性表中的數(shù)據(jù)元素不一定是原子類型，即數(shù)據(jù)元素又可以具有某種數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)導(dǎo)引41 多維數(shù)組42 矩陣的壓縮存儲(chǔ)421 特殊矩陣422 稀疏矩陣43 廣義表431 廣義表的定義432 廣義表的運(yùn)算l理解二維數(shù)組的邏輯結(jié)構(gòu)特征，掌握二維數(shù)組的順序存儲(chǔ)地址公式。l理解特殊矩陣的壓縮存儲(chǔ)方式，掌握根據(jù)下標(biāo)計(jì)算存儲(chǔ)地址的方法。l了解稀疏矩陣的表示及存儲(chǔ)方法。l理解廣義表

2、的定義、分類及運(yùn)算。3主要內(nèi)容目標(biāo)一、多維數(shù)組的定義及存儲(chǔ)1.多維數(shù)組的邏輯結(jié)構(gòu)特征？數(shù)組中的元素具有相同類型，且下標(biāo)一般具有固定的上界和下界。數(shù)組可以是一維的，也可以是多維的。下面以二維數(shù)組為例來分析。二維數(shù)組可以看成是由多個(gè)一維數(shù)組組成的。二維數(shù)組Amn既可看成由m個(gè)行向量組成的線性表，也可看成是由n個(gè)列向量組成的線性表。二維數(shù)組的邏輯結(jié)構(gòu)具有如下特征：a00為開始結(jié)點(diǎn)，它沒有直接前趨；am-1,n-1為終端結(jié)點(diǎn)，它沒有直接后繼；結(jié)點(diǎn)a0,n-1和am-1,0都有一個(gè)直接前趨和一個(gè)直接后繼；除以上四個(gè)結(jié)點(diǎn)外，第一行和第一列的元素都有一個(gè)直接前趨和兩個(gè)直接后繼，最后一行和最后一列的元素都有兩

3、個(gè)直接前趨和一個(gè)直接后繼；其余的非邊界元素aij同時(shí)處于第i+1行的行向量中和第j+1列的列向量中，都有兩個(gè)直接前趨和兩個(gè)直接后繼。2.多維數(shù)組的存儲(chǔ)以二維數(shù)組為例：二維數(shù)組一般采用順序存儲(chǔ)，因?yàn)樵貍€(gè)數(shù)固定，不插入刪除。思考問題？如何讓非線性的二維數(shù)組保存在線性的內(nèi)存中？數(shù)據(jù)的排列原則方法：（1）先排列成線性序列；（2）再依次存放到內(nèi)存中。排列方法：行優(yōu)先和列優(yōu)先 （1）行優(yōu)先原則：一行一行排列。（2）列優(yōu)先原則：一列一列排列。問題：C語言的數(shù)組屬于哪種排列？行優(yōu)先存儲(chǔ)二維數(shù)組若二維數(shù)組Amn按行優(yōu)先原則排列，其線性序列為：a00，a01，a0,n-1，a10，a11，a1,n-1，am-1

4、,n-1存儲(chǔ)后的內(nèi)存狀態(tài)如圖所示:aij的地址為：LOC（aij）=LOC（a00）+（in+j）d 特點(diǎn)：隨機(jī)存取。列優(yōu)先存儲(chǔ)二維數(shù)組若二維數(shù)組Amn按列優(yōu)先原則排列，則線性序列為：a00，a10，am-1,0，a01，a11，am-1,1，am-1,n-1存儲(chǔ)后的內(nèi)存狀態(tài)如圖所示:aij的地址為：LOC（aij）=LOC（a00）+（jm+i）d 二維數(shù)組的推廣二維數(shù)組的邏輯特征可以推廣到多維數(shù)組。三維數(shù)組中元素最多有三個(gè)前趨、三個(gè)后繼二維數(shù)組的存儲(chǔ)方法可以推廣到多維數(shù)組。行優(yōu)先或列優(yōu)先排列，然后依次存儲(chǔ)。二、矩陣的壓縮存儲(chǔ)工程中的矩陣（二維數(shù)組）往往階數(shù)較大；而有效數(shù)據(jù)（非零元素）很少；

5、且分布沒有規(guī)律；直接存儲(chǔ)浪費(fèi)大壓縮存儲(chǔ)。壓縮存儲(chǔ)方法壓縮方法：只存儲(chǔ)非零元素，對(duì)零元素不分配空間；為多個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間。分別討論特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)。1.特殊矩陣特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣，可以根據(jù)規(guī)律來壓縮存儲(chǔ)。（1）對(duì)稱矩陣（重點(diǎn)*）（2）三角矩陣（上三角陣和下三角陣）（3）對(duì)角矩陣不同的特殊矩陣中元素的分布規(guī)律不同，壓縮存儲(chǔ)的方法也不同。（1）對(duì)稱矩陣滿足aij=aji（1i，jn）的n階方陣稱為對(duì)稱矩陣。壓縮存儲(chǔ)方法：對(duì)稱矩陣中的數(shù)據(jù)元素按主對(duì)角線對(duì)稱，只需存儲(chǔ)下三角或上三角中的元素即可（重復(fù)元素只分配一個(gè)單元）。對(duì)稱矩陣對(duì)于上三角或下三角

6、中的元素可按行優(yōu)先或列優(yōu)先存儲(chǔ)。由此可得四種存儲(chǔ)方法：行優(yōu)先順序存儲(chǔ)下三角 列優(yōu)先順序存儲(chǔ)下三角 行優(yōu)先順序存儲(chǔ)上三角 列優(yōu)先順序存儲(chǔ)上三角。aij可以通過公式計(jì)算出來：隨機(jī)存取。重點(diǎn)：地址公式的推導(dǎo)。（1）行優(yōu)先順序存儲(chǔ)下三角 （a）n階對(duì)稱矩陣 （b）行優(yōu)先順序存儲(chǔ)下三角（c）對(duì)應(yīng)的一維數(shù)組思考？（1）數(shù)組的大小？：n（n+1）/2（2）對(duì)應(yīng)關(guān)系是什么？元素aij 存儲(chǔ)在sa數(shù)組中的哪里？（3）下標(biāo)k與i、j之間的關(guān)系：k=i（i+1）/2+j（4）上三角的aij怎么處理？答：上三角與下三角對(duì)應(yīng)，例如a58=a85,若求上三角元素的值，那么將下標(biāo)交換求地址。其他三種方法的下標(biāo)計(jì)算公式(學(xué)會(huì)

7、推導(dǎo))（2）列優(yōu)先順序存儲(chǔ)下三角（3）行優(yōu)先順序存儲(chǔ)上三角（4）列優(yōu)先順序存儲(chǔ)上三角 （2）三角矩陣包括上三角陣和下三角陣兩種。上三角陣的主對(duì)角線以下（不包括對(duì)角線）元素均為常數(shù)C，通常為0。圖中為上三角陣。如何壓縮存儲(chǔ)？跟對(duì)稱陣有什么區(qū)別與聯(lián)系？三角矩陣壓縮方法：相同元素只分配一個(gè)存儲(chǔ)單元。上三角矩陣壓縮存儲(chǔ)：上三角沒規(guī)律，依次存儲(chǔ)，行優(yōu)先或列優(yōu)先。常數(shù)C=0，不分配空間；C0分配一個(gè)單元。則若C0，圖中的上三角陣定義一個(gè)長度n（n+1）/2+1的數(shù)組，最后一個(gè)單元存儲(chǔ)常數(shù)C。上三角矩陣地址公式 若上三角陣以行優(yōu)先順序存儲(chǔ)，則地址公式為：若上三角陣以列優(yōu)先順序存儲(chǔ)，地址公式會(huì)推導(dǎo)。下三角陣的

8、存儲(chǔ)同理。（3）對(duì)角矩陣（了解）所有非零元素都集中在主對(duì)角線及主對(duì)角線兩側(cè)對(duì)稱的帶狀區(qū)域，其余部分全部為零的n階方陣為對(duì)角矩陣。常見的對(duì)角矩陣有三對(duì)角陣。如圖：壓縮存儲(chǔ)方法：只存非零元。具體方法：也可以按照行優(yōu)先順序、列優(yōu)先順序或?qū)蔷€順序來進(jìn)行存儲(chǔ)，每一種地址公式不同。行優(yōu)先順序存儲(chǔ)n階三對(duì)角陣的一維數(shù)組如下：地址公式：k=2i+j。對(duì)角矩陣0 01 12 23 34 412123n-33n-3a a0000a a0101a a1010a a1111a a1212a a4444a a n-1,n-1n-1,n-12.稀疏矩陣定義：非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總個(gè)數(shù)。若mn的矩陣中有t個(gè)非

9、零元素，則定義矩陣的稀疏因子為=t/（mn），通常取0.05的矩陣為稀疏矩陣。稀疏矩陣的三元組表示壓縮存儲(chǔ)：通常采用只存儲(chǔ)非零元素的方法。但是非零元素的分布沒有規(guī)律，如何表示？答：三元組。稀疏矩陣A67的三元組表可表示為（1，2，11），（3，1，-3），（3，6，7），（4，4，6），（6，3，5）。若要唯一的表示一個(gè)稀疏矩陣，在存儲(chǔ)三元組表的同時(shí)，還需要存儲(chǔ)該矩陣的行數(shù)和列數(shù)，同時(shí)為了運(yùn)算方便，一般還要存儲(chǔ)非零元素的個(gè)數(shù)。稀疏矩陣的表示：三元組表+m+n+t稀疏矩陣的存儲(chǔ)稀疏矩陣的存儲(chǔ)就是三元組表的存儲(chǔ)。三元組順序表：順序存儲(chǔ)十字鏈表。：鏈接存儲(chǔ)（1）三元組順序表（1）將三元組按照行優(yōu)先的

10、順序排列成一個(gè)序列；（2）采用順序存儲(chǔ)方法存儲(chǔ)該線性表；稱為三元組順序表。矩陣A的三元組順序表如右圖所示：0 01 12 23 34 4i i1 13 33 34 46 6j j2 21 16 64 43 3v v1111-3-37 76 65 5三元組順序表存儲(chǔ)結(jié)構(gòu)的C語言描述#define MAX 16 typedef int DataType;typedef struct int i,j;DataType v;Node;/*三元組類型*/typedef struct int m,n,t;Node dataMAX;Matrix;/*三元組順序表的存儲(chǔ)類型*/Matrix A,B;.（2）十

11、字鏈表鏈接存儲(chǔ)結(jié)構(gòu)：插入、刪除效率較高。結(jié)點(diǎn)結(jié)構(gòu)如圖所示。i ij jv vdowndownrightright十字鏈表小節(jié)重點(diǎn)排列原則（行優(yōu)先和列優(yōu)先）地址公式（會(huì)推導(dǎo)）練習(xí)練習(xí)二維數(shù)組在采用順序存儲(chǔ)時(shí)，元素的排列方式有_和_兩種。在特殊矩陣和稀疏矩陣中，經(jīng)過壓縮存儲(chǔ)后會(huì)失去隨機(jī)存取的特性的是_。設(shè)有一個(gè)10階的對(duì)稱矩陣A，以行優(yōu)先順序存儲(chǔ)下三角元素，其中a00為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)字節(jié)，則a85的地址為_；若a11為第一元素，那么a85的地址為_。三、廣義表1、廣義的定義及表示：線性表的推廣定義：n（n0）個(gè)元素a1，a2，ai，an的有限序列，元素ai可以是原子或者是

12、子表（子表亦是廣義表）。符號(hào)表示：LS=（a1，a2，ai，an）廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，因?yàn)閺V義表中的數(shù)據(jù)元素還可以是廣義表。廣義表與線性表廣義表與線性表的區(qū)別與聯(lián)系：線性表中的元素必須是原子。廣義表允許表中的元素具有結(jié)構(gòu)。當(dāng)廣義表中的所有元素都是原子時(shí)，此廣義表就是線性表（廣義表包含線性表）。廣義表舉例（1）A=（）空表（2）B=（a，b）只包含原子（3）C=（c，B）=（c，（a，b）既有原子，又有子表（4）D=（B，C，d）=（a，b），（c，（a，b），d）（5）E=（a，E）=（a，（a，（a，（）遞歸表一般：大寫字母表示“表”，小寫字母表示“原子”。大家觀察：D和E有什么區(qū)別

13、？其他表示方法（1）帶名字的廣義表表示：在每個(gè)表的前面冠以該表的名字A（）B（a，b）C（c，B（a，b）D（B（a，b），C（c，（a，b），d）E（a，E（a，E（a，E（）其他表示方法（2）廣義表的圖形表示：用非分支結(jié)點(diǎn)表示原子，用分支結(jié)點(diǎn)表示廣義表（空表除外，空表中不含元素，所以也用非分支結(jié)點(diǎn)表示）。2、廣義表的分類線性表：元素全為原子純表：沒有共享和遞歸（樹）再入表：允許結(jié)點(diǎn)的共享但不允許遞歸（圖）遞歸表舉例嵌套括號(hào)表嵌套括號(hào)表示示展開寫法展開寫法帶名字的廣義表表示帶名字的廣義表表示長度長度備注備注A=A=（）（）A=（）A（）0空表B=B=（a a，b b）B=（a，b）B（a，b

14、）2線性表C=C=（c c，B B）C=（c，（a，b）C（c，B（a，b）2樹D=D=（B B，C C）D=（a，b），（c，（a，b）D（B（a，b），C（c，（a，b）3圖E=E=（a a，E E）E=（a，（a，（a，（）E（a，E（a，E（a，E（）遞歸表3、廣義表的運(yùn)算四個(gè)特殊的運(yùn)算：取表頭Head（LS）：第一個(gè)元素a1取表尾Tail（LS）：（a2，ai，an）求表深Depth（LS）：n求表長Length（LS）：括號(hào)嵌套的層數(shù)注：廣義表的表頭（Head）為廣義表的第一個(gè)元素，廣義表的表尾（Tail）為廣義表中除第一個(gè)元素外，剩下所有的元素組成的廣義表。廣義表的運(yùn)算四個(gè)特殊的

15、運(yùn)算：取表頭Head（LS）、取表尾Tail（LS）、求表深、求表長。廣義表的表頭（Head）為廣義表的第一個(gè)元素，廣義表的表尾（Tail）為廣義表中除第一個(gè)元素外，剩下所有的元素組成的廣義表。舉例廣義表廣義表展開寫法展開寫法表頭表頭表尾表尾表深表深A(yù)=A=（）（）A=（）B=B=（a a，b b）B=（a，b）a（b）1C=C=（c c，B B）C=（c，（a，b）c（a，b）2D=D=（B B，C C）D=（a，b），（c，（a，b）（a，b）（c，（a，b）3E=E=（a a，E E）E=（a，（a，（a，（）a（E）練習(xí)練習(xí)下面說法正確的是：A.廣義表的表尾通常是一個(gè)廣義表，但有時(shí)也可以是一個(gè)原子；B.廣義表的表尾總是一個(gè)廣義表；C.廣義表的表頭總是一個(gè)廣義表；D.廣義表的表頭總是一個(gè)原子。廣義表常分成四類，分別是_、_、再入表和_。廣義表（a,b）,（c,d）的表頭是_，表尾是_，表長是_，表深_。本章重點(diǎn)重點(diǎn)重點(diǎn)矩陣壓縮存儲(chǔ)地址公式廣義表的特點(diǎn)及運(yùn)算