Re: 杰哥..
※ 引述《darkguy (我討厭香港人..)》之銘言：
> 杰哥恕我駑鈍..我還有一些問題要問..
千萬別自慚形穢，只要有心，人人可以是食神.......
> 首先我真的沒有linked-list的概念,
> 1. element可以是一個變數或陣列,結構嗎??
壹、A.
我之前用「element」這個詞是指array裡面的元素。因為是array，
所以元素不能太複雜，可以是變數（最簡單的結構）或者是另一層陣列
（多維陣列的時候），如果要複雜一點的話，通常就是存指標，例如
pointer for function、pointer for struct，不過這不太實際，
也很少見，所以不必去理它。
如果要用linked-list做，習慣上是用「node」這個詞來指每個單一元素，
它的型態就可以很複雜：
在用C實作時，通常是用struct來實作出node，所以資料內容是變數或陣列
沒有問題，如果要再包一層struct當然也沒問題，看有沒有必要而已。
在用C++實作的話，通常就是把node做成一個class，所以node裡面要放什麼
東西就更不是問題了，除了可以是變數或陣列，也可以是struct，
甚至可以是function。（看有沒有必要而已，當然一般也不會寫成這麼複雜。）
> 為什麼每個element要link起來..而且還是用指標將他們串在一起
> 可以舉個實例說明一下嗎??
壹、B.
例如一個array aANIMAL：
┌———┬———┬———┬———┬———┐
aANIMAL｜mouse ｜cow ｜tiger ｜rabbit｜dragon｜......
└———┴———┴———┴———┴———┘
我們知道 aANIMAL[0]就是指mouse，aANIMAL[3]就是rabbit。
如果是一堆nodes在那邊：
┌———┐
｜mouse ｜
└———┘
┌———┐
｜cow ｜
└———┘
┌———┐
｜tiger ｜......
└———┘
你要怎麼指出哪一個是mouse？哪一個rabbit？
如果為每個node都取名字，不就乾脆宣告每個node都是變數就好了嗎？
但是這樣存取也很麻煩，變數名稱太多。
所以要把nodes串在一起，變成一個linked-list bANIMAL：
┌———┬┐ ┌———┬┐ ┌———┬┐ ┌———┬┐ ┌
bANIMAL-->｜mouse ｜-->｜cow ｜-->｜tiger ｜-->｜rabbit｜-->｜....
└———┴┘ └———┴┘ └———┴┘ └———┴┘ └
每個node除了自己本身的資料（mouse、cow、tiger....）以外，
還要有個指標（圖中的箭頭-->）指向下一個node，我們才能方便地找到
每個node來存取。
> 2. 再來queue和stack可以講深入一點嗎??我不太了解他們的意義
貳、A.
array 是每個element都可以被存取：
┌—┬—┬—┬—┬—┐
└—┴—┴—┴—┴—┘......
↑↓↑↓↑↓↑↓↑↓ （箭頭表示可以存取的位置）
存取存取 存 取
貳、B.
queue 是 FIFO (First In, First Out)，只能從一端存，另一端取：
取 ←┌—┬—┬—┬—┬—┐← 存
└—┴—┴—┴—┴—┘
貳、C.
stack 是 FILO (First In, Last Out)，只能由某一端存和取：
┌—┬—┬—┬—┬—┐← 存
└—┴—┴—┴—┴—┘→ 取
> 3. 另外你舉的"指標在動態記憶體配置上的彈性"的例子
> 每增加或刪除一個客戶的資料要如何將"車廂"串起來或拿掉勒?
例如宣告了 ANI_Node 這個class：
（我這是寫個簡單的例子，如果要考慮安全性什麼的，最好參考書上的寫法）
class ANI_Node
{
public:
char data[6]; // 每個node裡的資料用長度為6的
// char陣列存，資料名稱就是data
ANI_Node *next; // *next 是指向下一個node的指標
}
參、A.建立1
一開始先宣告一個指標bANIMAL，指向火車，並當作火車的名稱：
ANI_Node *bANIMAL = new ANI_Node ;
然後就可以填入值。這時候 bANINAL指向第一個車廂，所以：
bANINAL->data = "mouse" ; // 第一個車廂的data是"mouse"
bANINAL->next = NULL ; // 該車廂之後沒有車廂了
最後一個車廂的*next記得要指向NULL，才知道list已經結束。
經過上述步驟，我們已經建出下面這只有一個node的list：
┌———┬┐
bANIMAL-->｜mouse ｜--> NULL
└———┴┘
再來宣告並設定第二個車廂：
bANIMAL->next = new ANI_Node ; // 第一個車廂的下一個是車廂
bANIMAL->next->data = "cow" ; // 該車廂的data是"cow"
bANIMAL->next->next = NULL ; // 該車廂之後沒有車廂了
這樣就完成了有兩個nodes的list如下：
┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜cow ｜--> NULL
└———┴┘ └———┴┘
參、B.建立2
很明顯這樣做下去串到後面的node時程式裡會出現一堆"->next"字樣，太混亂，
因此通常會再另外宣告一個指標來做操作，而像bANIMAL這樣最前面的指標
就用來指示LL的名稱和開頭，不用來做操作。因此上面的code
（除了class的定義之外）最好改寫成：
ANI_Node *bANIMAL = new ANI_Node ;
ANI_Node *f = new ANI_Node ; // 宣告f這個pointer來做操作
f = bANIMAL ; // f一開始是指到第一個車廂
f->data = "mouse" ; // 第一個車廂的data是"mouse"
f->next = NULL ; // 第一個車廂之後沒有車廂
在加第二個車廂時：
f->next = new ANI_Node ; // 第一個車廂之後有個車廂
f = f->next ; // f指向第二個車廂
f->data = "cow" ; // 第二個車廂的data是"cow"
f->next = NULL ; // 第二個車廂之後沒有車廂
這樣就完成了有兩個nodes的list如下：
┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜cow ｜--> NULL
└———┴┘ └———┴┘
↑
f (f現在指向最後，也就是第二個車廂）
參、C.刪除
以上是建立起來的過程。
假設已經建立好下面這個LL：
┌———┬┐ ┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜cow ｜-->｜tiger ｜--> NULL
└———┴┘ └———┴┘ └———┴┘
如果要刪掉data內容為"cow"的車廂，需要先用f指標指到它的上一個車廂，
這是searching時要做的動作，例如這樣做（下面程式不考慮只有一個車廂，
而該車廂data就是"cow"）：
f = bANIMAL ;
while( (f->next != NULL) && (f->next->data != "cow") )
{
f = f->next ;
}
這樣就可以把f指向data是"cow"的車廂的上一個車廂：
┌———┬┐ ┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜cow ｜-->｜tiger ｜--> NULL
└———┴┘ └———┴┘ └———┴┘
↑
f
然後就可以拿掉"cow"車廂。
把f指向車廂的"下下一個車廂"指定為"下一個車廂"，
也就是原來的"下一個車廂"被拿掉了。
f->next = f->next->next ;
就可以得到：
┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜tiger ｜--> NULL
└———┴┘ └———┴┘
↑
f
參、D.插入
要插入一個車廂的話，要先知道插入位置的前一個車廂在哪，再用指標指過去，
和前述一樣，我就不講了。
假設已經有下面的LL，要在"cow"之後間插入一個data是"cat"的車廂，
而且已經用f指標指向"cow"車廂了：
┌———┬┐ ┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜cow ｜-->｜tiger ｜--> NULL
└———┴┘ └———┴┘ └———┴┘
↑
f
插入的方法是先做出新車廂，
ANI_Node *x = new ANI_Node ; // 宣告一個x指標指向新車廂
x->data = "cat" ; // 新車廂的data是"cat"
然後再連接前後車廂：
x->next = f->next ; // 原來f指向車廂的下一個"tiger"車廂
// 變成新車廂的下一個車廂
f->next = x ; // 新車廂變成f指向車廂的下一個車廂
就可以得到：
┌———┬┐ ┌———┬┐ ┌———┬┐ ┌———┬┐
bANIMAL-->｜mouse ｜-->｜cow ｜-->｜cat ｜-->｜tiger ｜--> NULL
└———┴┘ └———┴┘ └———┴┘ └———┴┘
↑
f
就完成insert了。
然後x指標就不需要了，所以可以delete掉。
delete x ;
> 4. 還有不用的指標若不delete掉,造成garbage又會造成什麼傷害?
肆、
基本上garbage問題是記憶體管理上的問題。如果garbage多，就是會佔掉
記憶體造成浪費。這在早期記憶體不多的時候比較受重視，現在記憶體太多了，
比較沒有人在管記憶體夠不夠的問題，而是比較care程式可能出錯的問題。
因為沒有delete掉的話，那個pointer還存在，還指著某個記憶體位址abc﹔
但是在跑過一些code之後，abc那個位址可能已經不是原來的data或者function，
這時候如果不小心又用到那個pointer，就會造成不可預期的結果，
例如程式當掉或者是當機之類的。
其實像win95的記憶體管理就沒有做好，所以開久了memory就會被吃掉一堆，
跑得越來越慢，常常當機，因此不夠穩定、不適合當server。
> 5. Trace 一個程式我應該如何開始??從那裡下手??該注意那些地方??
> 這個問題好像有點大,不過我覺得我目前非常需要建立這個概念,
> 有了這個概念將來看程式的時候應該會事半功倍吧..我之前真是繞了
> 一大段遠路呢..想想真是浪費不少時間
我不知道你的確切問題在哪，而且我覺得要trace程式首先當然要先會寫程式，
不會寫程式的話當然trace的每一步都看不懂。所以我想分享一下我個人的
寫程式經驗，這和前文比較沒關係，因此我考慮考慮之後，決定獨立出來
在下一篇談談。
> 順帶一提..你不說我還真忘了有洪炯宗這一號人物
> 他是電機系的老師嗎??
洪迥宗是資工系的。
上了研究所才知道他是專門在搞生物資訊的，聽說還撈了不少錢，羨煞人也。
--
我閉上眼睛嘆了一口像印加的井一般深的嘆息。
然後再回到《紅與黑》。
失去的東西既然已經失去，再想東想西也不會再回來。
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: 140.115.50.10
※ 編輯: GAMRYA 來自: 140.115.50.10 (01/09 02:57)
※ 編輯: GAMRYA 來自: 140.115.50.10 (01/09 03:02)
討論串 (同標題文章)