數組、矩陣、廣義表
目錄
數組、矩陣、廣義表
? 一、數組
? ? ? ? 二.矩陣
三、廣義表
? 一、數組
????????這一章節理解基本概念即可。數組要看清其實下標是多少，并且二維數組，存取數據，要先看清楚是按照行存還是按列存，按行則是正常一行一行的去讀寫，按列則是，從左至右，一列一列的弄。
????????此外，數組中具體坐標的空間大小要會計算，每塊存儲單元，算到該數組坐標的前一位的數組大小：如A[5][3]，起始位A[0][0]，則計算A[5][3]的時候，先計算0-4行的空間大小，再計算第5行的大小，第五行的時候，是計算0-2列即0，1，2，三列，所以第五行空間個數為3，將其加上即可。
二、矩陣
????????則是掌握基本矩陣的代碼，矩陣相加，相乘，轉置。
- 其次要會壓縮矩陣，壓縮矩陣的目的是減少存儲單元
- 方法是，給矩陣中的有效數據，存進一維數組中去。
- 這個時候就需要壓縮矩陣的計算了，一般計算特殊矩陣：
- 對稱陣，上三角下三角，畫一個簡單的矩陣，然后根據按行存或者按列存，進行存儲，然后計算，一般是等差數列，然后加上最后一行或最后一列的有效數據，這個就看具體是多少了。一般遇到選擇題，讓求規律的，在看清矩陣和一維數組起始下標的前提下，找具體坐標試一下，如A[0][0]---0,在一維數組里面是第0個，給（行）i=0,（列）j=0，代入試一下即可。如果遇到算具體數值的，則是畫一個大概矩陣，然后找規律。按行排列，則先計算0到i-1行的個數（一般為等差數列，第0行有1個，第1行有2個第i-1行有i個，則共0到i-1，總個數為i個，a1=1,an=i所以等差數列為(
）,這是第0到i-1行的總個數，再計算第i行的個數，按列算，j+1個，所以總個數為
- 對三角矩陣，則是待定系數法，為了省事直接k=ai+bj+c，其中k為存進一維數組的下標，i為矩陣的行，j為矩陣的列，c為常數，然后再去帶具體坐標去解方程組即可。但上面設的公式，還要看具體情況去設置，如果有的個數為等差數列，則肯定有行的平方或者列的平方。
- 之后是稀疏矩陣：矩陣中大部分都是0的矩陣。
稀疏矩陣的壓縮，就是給矩陣中非零元素，存起來。
稀疏矩陣的順序存儲（設成結構體，里面包含各種變量）
1.三元組表示法
按行優先存儲，所以稀疏矩陣三元組，不好逆置，逆置的話，需要按列重新搞一下。
????????三元組，就是數組結構體里定義三個變量，分別是行，列，以及坐標值。其中數組結構體，第一個里面存的是，矩陣信息，即共幾行幾列，有幾個非零元素。因此如果題中有5個非零元素，則三元組數組，要5+1個數組空間。
稀疏矩陣轉化三元組步驟：
????????1.先計算矩陣中非零元素個數。即二維數組遍歷，非零的，count（計數器）+1。最后返回count。
? ? ? ? 2.之后定義一個三元組數組，然后開始寫轉換函數，返回類型為三元組指針類型，即返回三元組。先存儲矩陣信息，再三元組數組第一個位置，隨后定義個記錄器，index=1，表示實際非零元素個數的下標，隨后開始遍歷，當矩陣元素不等于零的時候，存進index坐標下，隨后行和列也記錄，之后，index+1，后移動，直到遍歷結束。
2.偽地址存儲
數據結構體，里面變量為偽地址變量以及具體值。偽地址計算方法，可直接查，按照行或者列，從1開始，哪個位置非零，就記錄。
稀疏矩陣的鏈式存儲
1.鄰接表法。
用一維數組（矩陣行）去索引，索引內容，坐標值，列下標，以及同行下一個非零元。
即同一行，串成一個鏈，只串同行非零元素。
2.十字鏈表
三、廣義表
廣義表時線性表的推廣，不是線性表，而是層次結構，樹。
每個廣義表用（）括住，廣義表里面可以套廣義表，每個廣義表是一個小整體。廣義表里面，可以由原子元素（單個值），可以是廣義表。
廣義表的深度，長度和表頭表尾
深度：最多的層數，即廣義表包含幾個，查括號。化成樹的話，為最底下的那個廣義表。
長度：第一層元素個數，化成樹的話，是第二層結點.
表頭：廣義表非空時，第一個元素。即表頭為取第一個元素的值。
表尾：實際上是除了表頭以外，其他構成的新的廣義表。是個廣義表。
例如：（（a）,(b,f),(v)）
表頭為：（a）//只包含a的廣義表，? 不是a，a是原子元素。
表尾：（（b，f）(v)），新構成的廣義表.
再對表尾求
表頭：（b,f），廣義表。? ?不是（（b，f）），表頭為取第一個元素
表尾：( (v) ),是個廣義表，由廣義表（v）構成，即刪除表頭，剩下組成的新的廣義表，
廣義表的鏈式存儲
有兩個結點，第一個為廣義表結點，包含標記域，表頭，表尾指針，第二個是原子元素結點，包含標記域，和具體值。其中標記域為1，表示廣義表，標記域為0表示原子元素。
一般，先畫出第一個廣義表結點，然后頭節點指向出來，尾指針指向尾結點，以此類推。
擴展的線性表存儲結構
跟鏈式存儲差不多，只不過后面的指針變成了，左孩子又兄弟了，頭指針指向最左邊的孩子，之后孩子的尾指針，指向同級的右兄弟。（這種一般先畫成樹的形式，好判斷）
)
 Crack)
