2022年浙江自考數據結構復習資料第五章：多維數組和廣義表

時間：2022-09-22 10:21:20 作者：儲老師

　　以下自考復習資料均由浙江自考網整理并發布，考生想要了解更多關于浙江自考報名、考試、成績查詢、畢業、歷年真題、常見問答等相關信息請關注浙江自考網，獲取浙江自考更多信息。
　　數組一般用順序存儲的方式表示。存儲的方式有： ·行優先順序，也就是把數組逐行依次排列。PASCAL、C
　·列優先順序，就是把數組逐列依次排列。FORTRAN

　地址的計算方法： ·按行優先順序排列的數組：LOCa(ij)=LOCa(11)+((i-1)*n+(j-1))*d。
·按列優先順序排列的數組：LOCa(ij)=LOCa(11)+((j-1)*n+(i-1))*d。

　矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間；對零元素不分配空間。
特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規律的矩陣。
稀疏矩陣的概念：一個矩陣中若其非零元素的個數遠遠小于零元素的個數，則該矩陣稱為稀疏矩陣。特殊矩陣的類型： ·對稱矩陣：滿足a(ij)=a(ji)。元素總數n(n+1)/2。I=max(i,j)，J=min(i,j)，LOCa(ij)=LOC(sa[0])+(I*(I+1)/2+J)*d。
·三角矩陣： ·上三角陣：k=i*(2n-i+1)/2+j-i，LOCa(ij)=LOC(sa[0])+k*d。
·下三角陣：k=i*(i+1)/2+j，LOCa(ij)=LOC(sa[0])+k*d。
·對角矩陣：k=2i+j，LOCa(ij)=LOC(sa[0])+k*d。

　　稀疏矩陣的壓縮存儲方式用三元組表把非零元素的值和它所在的行號列號做為一個結點存放在一起，用這些結點組成的一個線性表來表示。但這種壓縮存儲方式將失去隨機存儲功能。加入行表記錄每行的非零元素在三元組表中的起始位置，即帶行表的三元組表。

　廣義表是n(n≥0)個元素的有限序列，其中的元素是原子或者是一個廣義表。
廣義表表頭和表尾的概念： ·若廣義表LS非空(n≥1),則這個廣義表的第一個元素就是表頭。
·其余的元素組成的表稱為LS的表尾，所以表尾必是一個子表。
廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。
廣義表與樹(形結構)相對應，這個廣義表就是純表。
如果一個廣義表的結點又可以被其他結點所共享，則這個表稱為再入表。
允許遞歸的表稱為遞歸表。
線性表∈純表(樹)∈再入表∈遞歸表。可見，廣義表是對線性表和樹的推廣。
廣義表有兩個特殊的基本運算： ·取表頭head(LS)：取表中的第一個數據元素，不能對空表操作。
·取表尾tail(LS)；取除表頭外，其余數據元素構成的子表，不能對空表操作。

聲明：

（一）由于考試政策等各方面情況的不斷調整與變化，本網站所提供的考試信息僅供參考，請以權威部門公布的正式信息為準。

（二）本網站在文章內容來源出處標注為其他平臺的稿件均為轉載稿，免費轉載出于非商業性學習目的，版權歸原作者所有。如您對內容、版權等問題存在異議請與本站聯系，我們會及時進行處理解決。