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

看板C_and_CPP作者tropical72 (藍影)時間15年前 (2010/11/17 00:44)推噓1(1推 0噓 20→)

留言21則, 4人參與討論串1/2 (看更多)

link 與 array 概念基本上從自修上的書大致上都有說到整理一下我所吸收到的東西 (1) 新增移除資料：(double link == single?) > array (2) 插入資料：(double link >= single link?) > 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 對調就完成了(吧?) (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]); } } 但 link 要取得第i個、第j個元素，還是要重頭開始 travel, 所以覺得 "單純用" link 做排序 - 超．慢！ (6) 若以排序做比較基準，我想 link 應該還是要再搭其它之資料結構 (ex: tree) 速度上才會有所改善。以上，是我對 link 與 array 比較上的認知，若有補充或覺不妥之地方，請不吝指教。另不知各位版友在考量要用 link 或 array，是否有其它因素之考量？最後謝謝各位先進耐心看完與指教。 ref: (1) 演算法入門與進階 - 使用C語言(含資料結構), 初版, 張紹勳蔡志敏著, 松崗, 1991 (2) Data Sturctures and the Standard Template Library, William J.Collins, Mc Graw Hill, 2003 -- YouLoveMe() ? LetItBe() : LetMeFree(); -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.142

→

akasan

11/17 00:54, , 1^F

11/17 00:54, 1^F

→

akasan

11/17 00:58, , 2^F

11/17 00:58, 2^F

→

akasan

11/17 00:59, , 3^F

11/17 00:59, 3^F