理論程式設計——對Editor的操作最佳化

第一篇中講過編輯器中主要操作，尤其是對字元的插入跟刪除。原理是要將所有的字元往後挪動，然後騰出位置。

當字元數量不多的時候，這個是個很快的操作。試想，如果字元數量達上百萬，那麼我在第二個字元處新插入一個字元，則後續的上百萬個字元都要做一個相同的動作——向後挪動一位。這個動作需要做100萬次。假設一次需要0。001s，則需要1000秒才能挪動完畢。一分鐘60s，則需要16。666。。。分鐘。這只是插入一個字元的時間。這在生產環境中肯定是不可能存在的。那麼有什麼辦法對此操作進行最佳化呢？

回顧一下我們平時寫作，如果漏寫了一個字怎麼處理：

我們寫完這個句子的時候，發現少寫了個“期”字。此時我們有兩種方式處理。第一種，將“期”後面的內容塗掉，重新寫。第二，就是使用插入符號：

顯然第二種辦法好多了，如果你寫的是一段話，總不能把整段話都劃掉。^符號的意思是，星字讀完後，由/開始讀期字，讀完後，讀\後面的字。用更形象的圖表示讀的順序，應該是：

這樣就可以在不改變原有內容的前提下，插入新的一個元素。

回到editor的例子。有下列一串字元：

按剛剛介紹的做法，我們要插入位元組B：

因為A要告訴編輯器A下一個字元是B，那麼存A的地方就不能只存下A，還需要記錄下A接下來應該去找到B這個字元。而同樣的B也要有個地方存B接下來要接哪個字元。因此，B插入後應該是A->B->C。

由於每一個字元都存在插入的可能，因此我們將上述的字元結構視覺化，應該是長這樣：

這樣有了地方存放下一個字元的地址（或者說位置），我們也就可以不再考慮這個一串字元是否是陣列了。因為我們可以不透過下標來找到某一個元素。

而插入B元素可以看成下圖：

這種儲存元素時，將下一個元素的地址一起存起來，透過地址將每個元素連結起來的結構體，我們成為

連結串列

。

剛剛談到我們不只是要儲存一個位元組，還要存放一個地址。我們假定存放這些資料的變數為Cell，那麼一個Cell的結構應該是這樣的：

用程式碼表示這個Cell，是這樣的：

struct

Cell

{

char

ch

；

Cell

*

link

；

}；

跟陣列一樣，我們也需要找到連結串列的頭，才能順著頭往下找到元素位置。因此我們必須知道頭元素的地址。頭元素的地址也存放在一個cell中，不過這樣的cell可以不需要元素內容。它只有一個內容，存放第一個元素的地址。因此A->B->C 可以表示為下圖：

這個頭元素，我們通常用Header表示。我們可以看到，如果C是最後一個元素，那麼C下面是沒有下一個元素地址的，這個元素跟Header元素的情況相反。

下一篇將介紹一下連結串列的刪除跟插入跟之前的騰空位置操作有何區別。