前面我們學習的 線性表 棧 隊列 和 串 都是 線性結構 本章起學習的是非線性結構它們的邏輯特征是一個數據元素可能有多個直接前趨和多個直接後繼
本章 重點 是熟悉 多維數組 的 存儲方式 矩陣的 壓縮存儲方式 廣義表 的定義及其求表頭和表尾的運算 難點 是 稀疏矩陣 的壓縮存儲表示下實現的算法
多維數組( 領會 )
多維數組 的 邏輯結構特征 一個m維數組 An n n m的每個元素都屬於m個向量最多可以有m個直接前趨和m個直接後繼
多維數組 的 順序存儲結構 及其 地址計算方式 :計算機的內存結構是一維的因此將數組元素排成線性序列然後將這個線性序列存放在存儲器中排列的方式有兩種一是 行優先順序 也就是把數組按一行一行的順序依次排列二是 列優先順序 就是把數組按一列列的順序依次排列
地址的計算方法我們按行優先順序排列的數組是這樣計算的假設每個元素占用d個存儲單元某個元素的地址就是它前面所有行所占的單元加上它所在行前面所有列元素所占的單元數之和不必去死記公式
數組是一種 隨機存儲結構 的原因因為在順序存儲的情況下每一個元素都有與其下標相對應的地址因此可以對數組中的元素進行隨機存儲
矩陣的壓縮存儲( 領會 )
特殊矩陣 的概念所謂特殊矩陣是指非零元素或零元素分布 有一定規律 的矩陣
稀疏矩陣 的概念一個矩陣中若其非零元素的個數 遠遠小於 零元素的個數則該矩陣稱為稀疏矩陣
我們在本章學習了對稱矩陣三角矩陣對角矩陣這三種特殊矩陣這三種特殊矩陣可以進行壓縮存儲主要要理解的是其下標變換方法
稀疏矩陣 的壓縮存儲方式 三元組表 就是把非零元素的值和它所在的行號列號做為一個結點存放在一起用這些結點組成的一個線性表(三元組表)來表示這個稀疏矩陣但是這種壓縮存儲方式將失去隨機存儲功能
相關算法的理解要建立在對三元組表的結構的全面掌握的基礎上但是本章的算法考試應不作要求
廣義表的概念( 領會 )
廣義表 又稱列表(Lists)是線性表的推廣就是說廣義表中的元素不僅可以是數或一個結構而且推廣到可以是一個表(這個表又可以是廣義表)所以廣義表是n(n≥)個元素aaaan的有限序列其中的ai或者是原子或者是一個廣義表(為什麼叫原子?因為原子是作為結構上不可分割的成分)
廣義表 表頭 和 表尾 的概念若廣義表LS非空(n≥ )則這個廣義表的 第一個 元素就是表頭(這個表頭可以是原子也可以是該廣義表的子表)而 其余的元素 組成的表稱為LS的表尾(要注意不是最後一個元素這和隊列的隊尾是不同的)所以表尾必是一個子表
廣義表有兩種表示法一種是 括號表示 法一種是 圖形表示 法括號表示時一般以大寫字母表示廣義表以小寫字母表示原子如A(xL(ab))用圖形表示時圖形中的分支結點對應廣義表非分支結點一般表示原子如果一個廣義表與樹(形結構)相對應這個廣義表就是純表如果一個廣義表的結點又可以被其他結點所共享則這個表稱為再入表允許遞歸的表稱為遞歸表
有一個關系式 遞歸表(包含)再入表(包含)純表(樹)(包含)線性表 可見 廣義表是對線性表和樹的推廣
廣義表有兩個特殊的基本運算 取表頭head(LS) 和 取表尾tail(LS) (我們看到tail這個詞就是尾巴是一條尾巴而不是末尾它可能是一個原子但這個原子是作為子表來看待的)
取表頭和表尾的運算要在 廣義表非空 的情況下進行注意廣義表()表示是空表(())則表示有一個元素的廣義表這個元素是一個空表
這兩個運算很容易理解也應該掌握
第五章 多維數組和廣義表 復習要點
本章復習要點是
多維數組和廣義表的邏輯結構特征它們是復雜的非線性結構一個數據元素可能有多個直接前趨和多個直接後繼
多維數組的兩種順序存儲方式行優先順序和列優先順序這兩種存儲方式下的地址計算方法
幾種特殊矩陣的特征及其壓縮存儲地址對應關系
稀疏矩陣的三元組表示(畫圖形表示)
廣義表是線性表的推廣也是樹的推廣
能畫出廣義表的圖形表示法
廣義表的取表頭運算與取表尾運算要注意表頭是廣義表的第一個元素它不一定是原子表尾則必是子表
本章可能出選擇題填空題和應用題
From:http://tw.wingwit.com/Article/program/sjjg/201311/23666.html
