Dynamical Memory Allocation動態記憶體配置

        由於陣列所占記憶體大小必須在宣告前決定，因此對記憶體使用效率不佳，且當陣列中想要插入一元素，則必須搬動該元素之後的所有元素，所以運算需要的時間複雜度較告。為了解決以上問題，必須使用動態記憶體配置。
        動態記憶體配置主要是利用Linklist的方法來解決一些無法事先預測處理資料多寡的問題，或是想要以比較經濟的方法來處理記憶體空間的問題。
        靜態記憶體配置是在編譯階段時就配置記憶體空間，而動態記憶體配置則是等到執行階段，才向作業系統要求配置所需的記憶體空間，它可以讓程式設計者靈活運用程式所需的記憶體空間。

Array & Linklist差異與適用時機

• 差異
• Linklist
• 利用指標來連結各個元素。
• 以不連續的空間表示。
• Array
• 不是指標方式連結個元素。
• 以連續的空間表示。
• 適用時機
• Linklist：資料內容經常變動者。
• Array：資料內容不常變動者。

資料結構Array,Linked List

資料結構可分為靜態結構與動態結構。

• Array是靜態結構。Array的大小(或是很準的估計值)必須在使用前就知道，且其大小是無法擴充的。從另一方面看，Array的存取是非常有效率的。
• Linked List則是動態結構。其大小可輕易地擴充或減少。Linked List是可以具備任意的大小(只要不高過實際可用記憶體即可)。

資料結構可進一步細分成一維結構與多維結構。

• Array與Linked List就是一維結構，所能表示的就是元素間可能的順序關係。當然還是有辦法建構多維的Array與Linked List。
• Tree可表達得比一維結構還多一點---如層級關係。
• Graph甚至可表達更精細的結構。

*延伸應用：

B-Tree structures on flash memory(吳晋賢 Chin-Hsien Wu,National Taiwan University of Science and Technology)

正規表示式(Regular Expressions)

什麼是正規表示式

• 正規表示式(Regular Expressions) 可簡稱為 regexp 、regex 或 RE。
• 常見的翻譯有 「正規表示式」、「正則表達式」、「常規表示式」、「正規運算式」、「規則運算式」等。
• 意譯為「字串樣版」，是處理【有規律的文字檔】的利器。
• 表示法： /[A-Z]+(abc|xyz)*/ 或是 "[A-Z]+(abc|xyz)" 。
• 通常以斜線(forward slashes)或引號(quote)將RE含括起來

RE的用途 

• 觀念在於利用RE指定搜尋的字串樣板，然後從檔案中找出符合該樣板的字串, 再加以處理，常見用途有 將檔案中類似的字串取代掉，如 color , colour。
• 搜尋檔案中的單字是否重複繕打，如 Paris in the the Spring。
• 檢查使用者輸入是否符合指定樣版，如Email格式檢查。
• 更改日期的顯示格式，如 12/06/2018 => 2018-12-06。
• 搜尋指定目錄下是否有符合字串樣版的檔案。

學習RE到底值得否

• RE不是程式語言也不是應用軟體，它只是一種表示法。
• 只要有國中英文的程度與幾個小時的投資就可以學會RE。
• 學習一種可以跨平台的觀念，就可以使用幾十年。
• 從20年前的vi編輯器，到現在的Open Office, UltraEdit, ...都支援RE。
• 從最早支援的Script Language:Perl到PHP，甚至現在物件導向最火紅的語言:Java, .NET也都可以使用這一套表示法。

如何學好RE 

• 學會RE很容易，學好就有些難了。有人說過：「若你有一個難題，覺得可以使用RE來解決，此時你便有了二個難題」。
• 無須學會全部RE的觀念就可以拿來使用，多練習是學好的不二法門。
• 就算現在無法熟練的使用RE來解決問題，但可以觀察問題是否能使用RE來解決的感覺。
• 去除文件中所有的空行
• 去除文件中每一列最後的空白
• 將在Linux下編輯的文件其換列符號由\0D=>\0D\0A

RE的樣版符號介紹 

範例1：比對指定的字串

• car ： 找出所有含car這個字的單字
• \ ： 只找出car這個字
• ^car： 找出以car開頭的單字
• car$ ： 找出以car結束的單字
• 「.」句號(period) 代表任意一個字元，如 /.at/ 可符合 bat, cat, rat等任何字開頭，結尾是at的單字。
• 「[ ]」中括號(brackets)代表集合中的任一字元，如/[01256]/ 代表0,1,2,5,6這個集合中的任何一個字元。
• 「-」連字號(dash)在中括號內表示「範圍」，如/[0-9]/代表0到9的任一個單一的數字。
• 「^」(carat)在中括號內表示「否定」，/[^aeiou]/ 代表除了a,e,i,o,u這幾個母音之外的字元。
• 「|」(pipe)表示可選擇的，如/cat|dog|bird/代表cat, dog, bird 其中之一皆可(or的概念)。

• 「?」問號(question mark) 表示前面的字元或集合出現0次或1次，如/colou?r / 代表u這個字可出現也可不出現。
• 「+」加號(plus) 表示前面的字元或集合出現1次或多次，如/ap+le / 代表p這個字至少出現1次。
• 「*」星號(asterisk)表示前面的字元或集合出現0次或多次，如/section [0-9]*/ 代表數字可出現也可不出現。
• 「{}」大括號(curly-braces)表示前面的字元或集合出現的次數，如/c{5,8} / 代表c這個字重複出現5到8次。

結論 

由於 Regular Expression 具有極佳的字串表示能力。若能多利用Regular Expression 的工具，且靈活應 用 Regular Expression，則可避免撰寫程式進行複雜字串判斷 (parsing)的麻煩。如此，才能減輕資料處理時的負擔，並增加資料處理的效率。

*本筆記文節錄自:自由軟體應用於教學課程:朱孝國