在雙向串列加入資料:
如果是第一筆的話，非常的簡單。
 |
| 我們的指標(它們都是全或變數) |
 |
| 新增第一筆資料的程式碼 |
我們能用前幾篇教過的，看看first是否為NULL，用以判斷現在加入的是不是第一筆資料。
PS:程式碼裡的n是使用者輸入的資料。
 |
| 如果first跟last不現在指著的話，之後會有錯 |
 |
| 可能使用者輸入第一筆資料後就結束了，所以先把struct裡的兩個指標都指向NULL |
加入第一筆後，我們每再加一筆資料之前，都要跟串列裡的資料去做比較，看看新增的資料是要加在串列最前面(最小)、某兩筆資料中間、或是串列最後(最大)。
假如我們想新增5在某個串列裡，會遇到三種情況。
情況一:
在比對後發現，trave所指的struct的值比我們想加入的數還要大，而且trave所指的又是第一筆資料(從trave是否等於first來判斷)，由於我們資料預定就是從小(左)排到大(右)，因此可以確定，要加入的數會是最小的一個，所以要加在最左邊。
重要:因為新加入的資料才是最小的，所以要把first重新指向新的struct的位置。
我就有犯過這個錯，在加入新資料時(那資料跟串列裡現有的資料比起來，是最小的)沒把first重新指向最小的值，之後在測試時，輸入 10 7 6 5 0 Y，你猜怎麼樣?first一直指著值為10的struct的位置，所以，最後從小到大開始輸出時，它只有輸出一個 10。
情況二:
這就是把新增的struct插在兩個struct中間，這就比較簡單了，還是用那個trave，從first找起。
 |
| 用trave=trave->next就可以讓trave指向右一個struct |
現在的trave不等於first，所以可以知道trave所指的並不是第一個struct。
 |
| 我們必需先建立cur與trave前個struct的連結 |
 |
| 之後才建立cur與trave之間的連結 |
然後trave就不用再走下去了，因為資料已經新增完成了。
下面那張圖是補充
 |
| 補充部分 |
有人問，要建立cur與trave前個struct的連結，怎麼不用first來做就好了?為什麼要那麼麻煩，用trave->front->next?
如果我們是新增的資料是要加在第2第3個struct中間呢?
很明顯的，根據上圖，如果我們想建立cur與trave前個struct之間的連結，用first是行不通的，所以還是要用trave->front->next比較正確。
情況三:
最後一種情況就是把資料加在串列最後(右)了，所以我們可以知道，新加入的資料一定比串列裡的所有資料都大，trave會一直走下去，直到指到NULL(因為我們的停止條件是trave所指struct的資料大於或等於新加入的資料，看一下情況二就可以明白了)。
我們可以根據trave是否等於NULL，來判斷新資料是否要加在串列最後。
把last重新指向cur的原因跟情況一的first一差不多。
輸出:
如果想讓串列由小到大輸出的話，就先把trave指向first，然後輸出trave->data，之後trave=trave->next，如此重覆，一直到trave指向NULL。
如果想讓串列由大到小輸出的話，就先把trave指向last，然後輸出trave->data，之後trave=trave->front，如此重覆，一直到trave指向NULL。
PS:程式的最後，要記得釋放串列的記憶體。
結語:
能講的都講完了，最後就是程式碼部分了，我會PO在最後一篇。
沒有留言:
張貼留言