陣列與鏈結串列
這在資料結構和演算法當中，扮演著重要的工具角色。
觀念與使用技術格外重要。
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
雙向鏈結串列與單向鏈結串列比較
雙鍵可知前後元素、較為強固、刪除無須告知前面節點、插入刪除較麻煩、空間耗損多一。
利用單鏈節串列進行多項式表示法
依序儲存多項式係數、多項式指數、下一個節點位置，重複步驟直到多項式所以元素皆被儲存
鏈結的實際操作…新增節點.刪除節點.串成環狀
2007年2月1日 星期四
Recursive program and Interactive program
遞迴程式與反覆程式
簡而化之的說明:
遞廻就是使用重複呼叫副程式(subroutine)的概念。
遞迴會使用到堆疊(Stack)的技術，所以他是堆疊應用之ㄧ。
反覆則是使用廻圈(loop)處理問題。像是for.whiile...等語法。
遞迴演算法精隨：費柏納西數列實作.遞迴階乘實作
費柏納西數列特性一定要記憶：F(n)=F(n-1)+F(n-1)，n是項數。
費柏納西數列：1,1,2,3,5,8,13,21,34,55…
費柏納西數列推導請使用數學歸納法！
補充：其實遞廻這個概念時常被使用，不只是用在程式上。網路環境中也經常使用遞廻的概念。
簡而化之的說明:
遞廻就是使用重複呼叫副程式(subroutine)的概念。
遞迴會使用到堆疊(Stack)的技術，所以他是堆疊應用之ㄧ。
反覆則是使用廻圈(loop)處理問題。像是for.whiile...等語法。
遞迴演算法精隨：費柏納西數列實作.遞迴階乘實作
費柏納西數列特性一定要記憶：F(n)=F(n-1)+F(n-1)，n是項數。
費柏納西數列：1,1,2,3,5,8,13,21,34,55…
費柏納西數列推導請使用數學歸納法！
補充：其實遞廻這個概念時常被使用，不只是用在程式上。網路環境中也經常使用遞廻的概念。
Time Complexity and Space Complexity
T(n) and S(n) 時間複雜度與空間複雜度
Algorithm的時間複雜度和遞迴程式
Time Complexity（時間複雜度）：於演算法中常用漸進式符號來表示其執行時間的複雜度。
時間函數：T（n）指計算程式中指令所執行的次數。
Time Complexity時間複雜度問題請使用代數解決之。
複雜度的大小排序：O(C) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!)
解時間複雜度方法：遞迴代數
Algorithm的時間複雜度和遞迴程式
Time Complexity（時間複雜度）：於演算法中常用漸進式符號來表示其執行時間的複雜度。
時間函數：T（n）指計算程式中指令所執行的次數。
Time Complexity時間複雜度問題請使用代數解決之。
複雜度的大小排序：O(C) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(2^n) < O(n!)
解時間複雜度方法：遞迴代數
Data Structure and Algorithms Definition
資料結構與演算法的定義
何謂資料結構？
資料結構是電腦存儲、組織資料的方式。通常情況下，精心選擇的資料結構可以帶來更高的運行或者存儲效率的演算法。資料結構往往同高效的檢索演算法和指標技術有關。
何謂演算法？
所謂的演算法則是指一組個數有限的步驟，用來描述完成某一個工作或解決某一個問題所使用的方法；如果逐一正確的執行每一動作之後，就能完成一個特定的工作或解決一個特定的問題。
每一個正確的演算法則，皆須具備有以下五個特性：
1. 輸入性（Input）
2. 輸出性（Output）
3. 明確性（Precision）
4. 有限性（Finiteness）
5. 有效性（Determinism）
何謂資料結構？
資料結構是電腦存儲、組織資料的方式。通常情況下，精心選擇的資料結構可以帶來更高的運行或者存儲效率的演算法。資料結構往往同高效的檢索演算法和指標技術有關。
何謂演算法？
所謂的演算法則是指一組個數有限的步驟，用來描述完成某一個工作或解決某一個問題所使用的方法；如果逐一正確的執行每一動作之後，就能完成一個特定的工作或解決一個特定的問題。
每一個正確的演算法則，皆須具備有以下五個特性：
1. 輸入性（Input）
2. 輸出性（Output）
3. 明確性（Precision）
4. 有限性（Finiteness）
5. 有效性（Determinism）
Data Structure and Algorithms
資料結構與演算法
程式？何謂程式呢？ 除了程式語言以外
程式可以分成資料結構和演算法兩大領域
Program = Data Structure + Algorithms
這兩個領域有哪些重點呢？
DATA STRUCTURE
資料結構重點一覽
1. Algorithm的時間複雜度和遞迴程式
2. Array（陣列）
3. Stack and Queue（堆疊和佇列）
4. Link List（鏈結）
5. Tree and Binary Tree（樹以及二元樹）
6. Graph（圖形）
7. Searching and Sort（搜尋和排序）
8. Hashing（雜湊）
9. Advanced Tree（高等樹）
ALGORITHMS
演算法重點一覽
1. Mathematics for Algorithms（演算法的數學）
2. Data Structures（資料結構）
3. Divide and Conquer（分開與征服）
4. Searching（搜尋）
5. Sorting and Selection（排序與選擇）
6. Greedy Algorithms（貪婪演算法）
7. Dynamical Programming（動態規劃）
8. Text Searching（文字搜尋）
9. P and NP（P與NP問題）
10. Coping with NP-Completeness（完全NP的複製）
11. Parallel and Distributed Algorithms（平行和分散演算法）
這樣的歸類方式其實不太好！尤其對於考試或是工具的使用，幾乎沒有什麼整合和交集...
於是我試想將把這兩塊領域的重點自己整理一下。多出了文章群組Data Structure and Algoriths！
程式？何謂程式呢？ 除了程式語言以外
程式可以分成資料結構和演算法兩大領域
Program = Data Structure + Algorithms
這兩個領域有哪些重點呢？
DATA STRUCTURE
資料結構重點一覽
1. Algorithm的時間複雜度和遞迴程式
2. Array（陣列）
3. Stack and Queue（堆疊和佇列）
4. Link List（鏈結）
5. Tree and Binary Tree（樹以及二元樹）
6. Graph（圖形）
7. Searching and Sort（搜尋和排序）
8. Hashing（雜湊）
9. Advanced Tree（高等樹）
ALGORITHMS
演算法重點一覽
1. Mathematics for Algorithms（演算法的數學）
2. Data Structures（資料結構）
3. Divide and Conquer（分開與征服）
4. Searching（搜尋）
5. Sorting and Selection（排序與選擇）
6. Greedy Algorithms（貪婪演算法）
7. Dynamical Programming（動態規劃）
8. Text Searching（文字搜尋）
9. P and NP（P與NP問題）
10. Coping with NP-Completeness（完全NP的複製）
11. Parallel and Distributed Algorithms（平行和分散演算法）
這樣的歸類方式其實不太好！尤其對於考試或是工具的使用，幾乎沒有什麼整合和交集...
於是我試想將把這兩塊領域的重點自己整理一下。多出了文章群組Data Structure and Algoriths！
訂閱：
文章 (Atom)
