數(shù)據(jù)結(jié)構(gòu)與算法（C++版）課件第四章 多維數(shù)組和廣義表

第四章-多維數(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)引4．1多維數(shù)組4．2矩陣的壓縮存儲(chǔ)4．2．1特殊矩陣4．2．2稀疏矩陣4．3廣義表4．3．1廣義表的定義4．3．2廣義表的運(yùn)算理解二維數(shù)組的邏輯結(jié)構(gòu)特征，掌握二維數(shù)組的順序存儲(chǔ)地址公式。理解特殊矩陣的壓縮存儲(chǔ)方式，掌握根據(jù)下標(biāo)計(jì)算存儲(chǔ)地址的方法。了解稀疏矩陣的表示及存儲(chǔ)方法。理解廣義表的定義、分類及運(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è)直接后繼，最后一行和最后一列的元素都有兩個(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,n-1存儲(chǔ)后的內(nèi)存狀態(tài)如圖所示:

aij的地址為：LOC（aij）=LOC（a00）+（i×n+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）+（j×m+i）×d

二維數(shù)組的推廣二維數(shù)組的邏輯特征可以推廣到多維數(shù)組。三維數(shù)組中元素最多有三個(gè)前趨、三個(gè)后繼二維數(shù)組的存儲(chǔ)方法可以推廣到多維數(shù)組。行優(yōu)先或列優(yōu)先排列，然后依次存儲(chǔ)。二、矩陣的壓縮存儲(chǔ)工程中的矩陣（二維數(shù)組）往往階數(shù)較大；而有效數(shù)據(jù)（非零元素）很少；且分布沒有規(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（1≤i，j≤n）的n階方陣稱為對(duì)稱矩陣。壓縮存儲(chǔ)方法：對(duì)稱矩陣中的數(shù)據(jù)元素按主對(duì)角線對(duì)稱，只需存儲(chǔ)下三角或上三角中的元素即可（重復(fù)元素只分配一個(gè)單元）。對(duì)稱矩陣對(duì)于上三角或下三角中的元素可按行優(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ì)推導(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，不分配空間；C≠0分配一個(gè)單元。則若C≠0，圖中的上三角陣定義一個(gè)長(zhǎng)度n（n+1）/2+1的數(shù)組，最后一個(gè)單元存儲(chǔ)常數(shù)C。上三角矩陣地址公式若上三角陣以行優(yōu)先順序存儲(chǔ)，則地址公式為：若上三角陣以列優(yōu)先順序存儲(chǔ)，地址公式會(huì)推導(dǎo)。下三角陣的存儲(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ì)角矩陣01234…12…3n-3a00a01a10a11a12…a44…an-1,n-12.稀疏矩陣

定義：非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于矩陣元素的總個(gè)數(shù)。若m×n的矩陣中有t個(gè)非零元素，則定義矩陣的稀疏因子為δ=t/（m×n），通常取δ≤0.05的矩陣為稀疏矩陣。稀疏矩陣的三元組表示壓縮存儲(chǔ)：通常采用只存儲(chǔ)非零元素的方法。但是非零元素的分布沒有規(guī)律，如何表示？答：三元組。稀疏矩陣A6×7的三元組表可表示為（（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)先的順序排列成一個(gè)序列；（2）采用順序存儲(chǔ)方法存儲(chǔ)該線性表；稱為三元組順序表。矩陣A的三元組順序表如右圖所示：

01234i13346j21643v11-3765三元組順序表存儲(chǔ)結(jié)構(gòu)的C語言描述

#defineMAX16typedefintDataType;typedefstruct{inti,j;DataTypev; }Node; /*三元組類型*/typedefstruct{intm,n,t;Nodedata[MAX]; }Matrix; /*三元組順序表的存儲(chǔ)類型*/MatrixA,B;.（2）十字鏈表鏈接存儲(chǔ)結(jié)構(gòu)：插入、刪除效率較高。結(jié)點(diǎn)結(jié)構(gòu)如圖所示。ijvdownright十字鏈表小節(jié)重點(diǎn)排列原則（行優(yōu)先和列優(yōu)先）地址公式（會(huì)推導(dǎo)）練習(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（n≥0）個(gè)元素a1，a2，…，ai，…，an的有限序列，元素ai可以是原子或者是子表（子表亦是廣義表）。符號(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ū)別？其他表示方法（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)表示展開寫法帶名字的廣義表表示長(zhǎng)度備注A=（）A=（）A（）0空表B=（a，b）B=（a，b）B（a，b）2線性表C=（c，B）C=（c，（a，b））C（c，B（a，b））2樹D=（B，C）D=（（a，b），（c，（a，b）））D（B（a，b），C（c，（a，b）））3圖E=（a，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求表長(zhǎng)Length（LS）：括號(hào)嵌套的層數(shù)注：廣義表的表頭（Head）為廣義表的第一個(gè)元素，廣義表的表尾（Tail）為廣義表中除第一個(gè)元素外，剩下所有的元素組成的廣義表。廣義表的運(yùn)算四個(gè)特殊的運(yùn)算：取表頭Head（LS）、取表尾Tail（LS）、求表深、求表長(zhǎng)。廣義表的表頭（Head）為廣義表的第一個(gè)元素，廣義表的表尾（Tail）為廣義表中除第一個(gè)元素外，剩下所有的元素組成的廣義表。舉例廣義表展開寫法表頭表尾表深A(yù)=（）A=（）

B=（a，b）B=（a，b）a（b）1C=（c，B）C=（c，（a，b））c（（a，b））2D=（B，C）D=（（a，b），（c，（a，b）））（a，b）（（c，（a，b）））3E=（a，