Re: [問題] link, array, 比較取捨問題

[LPH66 (-858993460)]

※ 引述《tropical72 (藍影)》之銘言：
: link 與 array 概念基本上從自修上的書大致上都有說到
: 整理一下我所吸收到的東西
: (1) 新增移除資料：(double link == single?) > array
: (2) 插入資料：(double link >= single link?) > array
看你是在哪新增移除

尾巴的話幾乎沒差

開頭和中間才是 array 稍差 (因為要大搬家)

因此 stack 有時為了省事反而會用 array 來實作...

: (3) 做元素反排(reverse travel)：
:     這點標題不知怎麼打比較好，我所參考的書似乎也沒強調這點。
:     以array為例：
:     int arr1[CNT], arr2[CNT];
:     for(i=0; i<CNT; i++) arr2[CNT-i-1] = arr1[i];
:     array 只要做 CNT 次即可。
:     但若以 Single link 而言,每次都從 head 開始一直 travel 到後面,
:     不論要不要 assign 給另一個 link,
:     不就代表要花 CNT+(CNT-1)+....+1 = (1+CNT)*CNT/2 這麼久的時間？
:     (雖有版友提出我的確沒想過 recursive 完成, 時間複雜度會改善嗎？)
:     當然, double link 只要把 pre 和 next 對調就完成了(吧?)
呃...singly linked list 用遞迴就是線性啊 XD

動作是這樣的:

我要上面的人告訴我誰接我  換我接過去就好了...

: (4) 交換(swap)：
:     若array 形式為
:     struct person{
:        string name;
:        int age;
:        string address;
:        ...
:     };
:     person array[CNT];
:     在 swap 時 link 比較快，因不用逐一複製(當然可以用memcpy方式改善)
:     但實做上比較複雜 (pre1, next1, pre2, next2 交換，要注意順序)
這個大致正確

: (5) 排序(sort)：
:     這部份我所參考的書上也沒強調這點，所以我在想， link 不適合做排序的原因有二：
:     (5.1) 要做排序的話，應是一開始建立資料時便用 "插入" 之方式建立結點，
:           使整個 link 從頭到尾都是排好的狀態。
:     (5.2) link 要取 index 比 array 麻煩
:     以簡單的泡沫排序為例,
:     for(i=0; i<CNT-1; i++){
:         for(j=i+1; j<CNT; j++){
:           if(arr[i]>arr[j]) swap(a[i], a[j]);
:         }
:     }
(偷偷說一下, 其實這不是泡沫是選擇排序...

 for i=0 to CNT-1
   for j=0 to CNT-2-i
     if(arr[j]>arr[j+1]) swap(a[j],a[j+1]);

 這個才是泡沫)

:     但 link 要取得第i個、第j個元素，還是要重頭開始 travel,
:     所以覺得 "單純用" link 做排序 - 超．慢！
: (6) 若以排序做比較基準，我想 link 應該還是要再搭其它之資料結構
:     (ex: tree) 速度上才會有所改善。
: 以上，是我對 link 與 array 比較上的認知，
: 若有補充或覺不妥之地方，請不吝指教。
: 另不知各位版友在考量要用 link 或 array，
: 是否有其它因素之考量？
: 最後謝謝各位先進耐心看完與指教。
這裡就要講到什麼叫資料結構

通常我們會把「資料結構與演算法」放在一起講

因為資料結構本來就是為了演算法而設計出來的

為了某種特定的演算法操作而設計出一套讓操作順利的資料組合方式

這就是資料結構

就拿排序當例子  linked list 確實不易隨機存取

但存取元素並非只有 [] 存取一途啊

如果我能夠依序地取元素比較

那在 linked list 上實作插入、泡沫、選擇、甚至是快排都是可能的

時間複雜度不會比較差 (有時像插入排序反而可能會更好)

但相對的實際實作上就會和在陣列中實作這些演算法時不一樣

而說到依序取元素比較  合併排序法的操作正是如此

因此比起在陣列上做  在 linked list 上做合併排序法反而好寫很多

這就是資料結構和演算法互相配合的道理

選擇排序法就是需要陣列來發揮隨機存取能力

合併排序法就是需要 linked list 來實現那個「合併」的概念

因此你的問題  什麼時候要用 array? 什麼時候要用 linked list?

這就得看當時實際的需求  包含大型資料結構的設計、存取的需求、使用的演算法等等

有些時候 linked list 就是比較方便

有些時候 array 就是比較好用

並沒有哪一個在所有情況下都比另一個好這種事

--
有人喜歡邊玩遊戲邊上逼；        
    也有人喜歡邊聽歌邊打字。      
        但是，我有個請求，          
            選字的時候請專心好嗎？
                                      -- 改編自「古 火田 任三郎」之開場白

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.230.62
推 loveflames:array的程式比較好寫(逃
→ loveme00835:沒仔細看還真沒發現這是 selection sort XD
→ LPH66:我自己也有好一陣子常常搞混這兩個 XD
→ tropical72:非常感謝LPH66解說.
推 loveme00835:對了! linked list 其實就是樹...
→ tropical72:看到第一點有點問題了.若新增在頭或中間,array方式為
→ tropical72:remalloc(), 速度上仍是差不多的嗎？
→ tropical72:請無視6F,7F,我知道問題在哪了XD
→ loveme00835:@@
推 VictorTom:遞迴要小心爆啊XD 單向LL其實還是可以一個迴圈從頭到尾
→ VictorTom:讓整個LL變成反著串回來, 只是要多兩個temp pointer XD