2007年2月1日 星期四

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

沒有留言: