Array and Link List

陣列與鏈結串列

這在資料結構和演算法當中，扮演著重要的工具角色。
觀念與使用技術格外重要。

About Array

計算一維陣列起始位置：
宣告方式A(C,P)A[i]= l + ( i – C ) * d
l：起始位置；d：元素大小；C：第一個元素
Ex：A陣列宣告：A(-3,9)，元素大小=4，起始位置=100，詢問A[5]的起始位置？
A[5]=100+(5-(-3))*4=100+32=132

記算二維陣列起始位置：
宣告方式A(1…c,1…p)列row；行column
Row Major：l + [(i-c)*n+(j-p)]*d
Column Major：l + [(j-1)*m+(i-1)]*d
多項式利用陣列儲存技術
依陣列儲存次序，存入最高次方項，最高次方項係數，依序降冪排列直到0次方項[常數]。
非零次方項儲存法：
X的100次方項加8
不宜用上述方式儲存，應依陣列順序儲存非零次方項數，首位係數+次方項…依次方項降冪排列至0。
利用陣列表示稀疏舉陣：
首列儲存列數.行數.非零元素
從第二列開始儲存所在列數.所在行數.該元素值
直到稀疏矩陣中所有非零元素都被儲存為止
特殊矩陣儲存：上三角或下三角.對稱矩陣

About Link List

Array v.s. Link List
陣列特色：必連續性配置、隨機存取、刪除插入不易、合併不易
鏈結特色：可以不連續配置、只能循序存取、插入刪除容易、合併容易、每筆資料多占一格空間

Link List Cycle
可用來實做環狀佇列

Double Link List
雙向鏈結串列與單向鏈結串列比較
雙鍵可知前後元素、較為強固、刪除無須告知前面節點、插入刪除較麻煩、空間耗損多一。
利用單鏈節串列進行多項式表示法
依序儲存多項式係數、多項式指數、下一個節點位置，重複步驟直到多項式所以元素皆被儲存
鏈結的實際操作…新增節點.刪除節點.串成環狀