這次作業是希望我們研讀並實做出
一種特別的資料結構 "Growing Array"
並以此資料結構做出具有能add / delete item的功能
Add為加入array中第一個unused slot.
Delete則是刪除array中第一個符合的item 。程式需能提供檢視
Array的資訊。要求如下
1)Prompt for Adding item
success or failure report
2) Prompt for Deleting item
Success or non-exist report
3)Display any item identity by array subscript or unused array entry
report
4)Error handling : out of array Boundary check
因為這次作業有要求另外交一篇有關Growing Array的 研讀報告
所以我就直接把那份報告作成筆記
1.何謂Growing Array?
Growing array為一可以隨著資料量做動態增減的資料結構，
(類似C++裡的vector)在這次的範例，一開始尚未分配任何空間
給Nameval 的structure ,當第一筆資料加入後，就分配一塊
擁有Nameval大小的記憶體空間，並放入使用者所輸入的字串
或數值，之後若輸入資料量超過已分配空間時，
就再多分配出現有空間大小的記憶體空間(及原來空間數量的兩倍)
，以提供之後新進資料的空間。
2.Growing Array示意圖：
3.Growing Array的增加機制理由
因為呼叫分配記憶體空間的函式（ex:malloc,realloc），
所需的系統負載較大，若使用頻率太過頻繁，會造成效率過低，
故採取資料量即將飽和時就再多分配出一倍的空間的方式（預期成本一定）
而不是新增一筆資料就分配一次(O(n^2))，
讓新進資料能不必經過再一次的函式呼叫便能存入陣列。
因為若使用陣列來做儲存資料的資料結構，對陣列中任一資料做存取只需O(1)，
對於像排序等應用有極大的助益，但一般陣列，空間大小在compiler time便以決定
，較無彈性，而Growing array則是利用動態分配空間的方式去實現陣列資料的增減。
4.實做方式
Growing array這個結構是在"The Practice of Programming"
（Brian W. Kernighan, Rob Pike）
這本書裡所介紹的 這本書也有出中文版 叫"程式設計專家手冊"
剛好也在之前學長所開的書單中 所以藉此機會去看他
這本書主要是教已經會撰寫程式的人 藉由設計過的資料結構或是coding style
讓我們所寫的程式更有效率也更好看懂
我在寫這次作業所看的感想是不會太艱澀 只要有C的基礎應該都能很容易了解他的意思
算是不錯的一本程式書
一種特別的資料結構 "Growing Array"
並以此資料結構做出具有能add / delete item的功能
Add為加入array中第一個unused slot.
Delete則是刪除array中第一個符合的item 。程式需能提供檢視
Array的資訊。要求如下
1)Prompt for Adding item
success or failure report
2) Prompt for Deleting item
Success or non-exist report
3)Display any item identity by array subscript or unused array entry
report
4)Error handling : out of array Boundary check
因為這次作業有要求另外交一篇有關Growing Array的 研讀報告
所以我就直接把那份報告作成筆記
1.何謂Growing Array?
Growing array為一可以隨著資料量做動態增減的資料結構，
(類似C++裡的vector)在這次的範例，一開始尚未分配任何空間
給Nameval 的structure ,當第一筆資料加入後，就分配一塊
擁有Nameval大小的記憶體空間，並放入使用者所輸入的字串
或數值，之後若輸入資料量超過已分配空間時，
就再多分配出現有空間大小的記憶體空間(及原來空間數量的兩倍)
，以提供之後新進資料的空間。
2.Growing Array示意圖：
3.Growing Array的增加機制理由
因為呼叫分配記憶體空間的函式（ex:malloc,realloc），
所需的系統負載較大，若使用頻率太過頻繁，會造成效率過低，
故採取資料量即將飽和時就再多分配出一倍的空間的方式（預期成本一定）
而不是新增一筆資料就分配一次(O(n^2))，
讓新進資料能不必經過再一次的函式呼叫便能存入陣列。
因為若使用陣列來做儲存資料的資料結構，對陣列中任一資料做存取只需O(1)，
對於像排序等應用有極大的助益，但一般陣列，空間大小在compiler time便以決定
，較無彈性，而Growing array則是利用動態分配空間的方式去實現陣列資料的增減。
4.實做方式
addname:
當使用者輸入欲新增的字串，及分配一個字串大小的記憶體空間(malloc)，
並將新Nameval中的char* name指向此空間。之後再至現有陣列尋找
是否有unused的空間，若有則填入，無則在分配新的記憶體空間，將新值放入。
當搜尋到要刪除的字串時（若未找到欲刪除字串，則顯示錯誤訊息並跳出程式）
，將該structure的字元指標name指向NULL，作為此空間可以被新進資料所覆蓋（unused）
，並將nvtab.nval(已存在資料數目)減一，表示表示已被刪除。
5.參考資料
Growing array這個結構是在"The Practice of Programming"
（Brian W. Kernighan, Rob Pike）
這本書裡所介紹的 這本書也有出中文版 叫"程式設計專家手冊"
剛好也在之前學長所開的書單中 所以藉此機會去看他
這本書主要是教已經會撰寫程式的人 藉由設計過的資料結構或是coding style
讓我們所寫的程式更有效率也更好看懂
我在寫這次作業所看的感想是不會太艱澀 只要有C的基礎應該都能很容易了解他的意思
算是不錯的一本程式書
全站熱搜
留言列表
