[計程] 雙班hw9題目參考解法

看板b98902HW作者barry800414 (小銘)時間14年前 (2009/12/24 23:23)推噓6(6推 0噓 5→)

留言11則, 8人參與討論串1/1

雙班hw9 common friends http://palcourse.csie.ntu.edu.tw/judgegirl/problem/c2009/homework/ assignment9/CommonFriend.htm 我想說有人問而且我的讀書會是在雙班deadline之後所以就想說PO版了希望有所幫助這一題的瓶頸就在於你沒辦法開int relation[25000][25000]; 這麼大的空間而且這方法效率也不好所以要用鏈結串列來節省空間了想法大致是這樣: 先有一個結構裡面存index 和一個指向自己結構的指標(即鏈結串列的node) typedef struct node { int index; struct node *next; } 接著我開兩個 25001大小的"指標"陣列 25001個都是Node 指標即 Node *relation[25001]; 和 Node *tail[25001]; 用途? 假設 5這個人有10 20 15這三個朋友 8這個人有15 10 19這三位朋友那結構會長這樣: relation pointer array : ───────────────────── │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │.... ───────────────────── ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ── ── │10│ │15│ ── ── ↓ ↓ ── ── │20│ │10│ ── ── tail[5] =↓ tail[8] =↓ ── ── │15│ │19│ ── ── ↓ ↓ 意即 relation[5]下面所指到的index(10 20 15)都是他的朋友那麼為什麼要tail pointer array呢? 我每次都把tail指到最後一個節點那麼我在新增節點時候就不用從頭開始找結尾了直接tail[i]->next=newptr; tail[i]=tail[i]->next; 就OK了!! 絕對可以省很多時間那如何尋找共同朋友呢? 就舉上面為例我想知道5和8的共同朋友那麼因為大小沒有排序如果 5的每一個朋友都向8的朋友爆搜會非常沒有效率(O(n^2)) 所以先開個陣列叫befriend[25001]; 以及計數器 count=0; 先將其歸0 接著把5的所有朋友即10 20 15 befriend[10]=1; befriend[20]=1; befriend[15]=1; 那麼再找 8的所有朋友即 15 10 19 檢查 if(befriend[15]==1) count++; if(befriend[19]==1) count++; if(befriend[10]==1) count++; 也就是先把5的朋友在陣列上做記號再看看8的朋友有幾個跟5一樣這樣檢查完count會是2 接著printf("%d\n",count); 就可以了然後其實這個方法在資料結構上是有專有名詞的叫adjacency list 相鄰串列是一種常見的存圖方法 (另一種是我們較直覺想到的即relation[a][b]=1 表示a b是朋友) 叫 adjacency matrix 相鄰矩陣有興趣的人可以上網查看看然後當你拿到9分之後(而且是第一筆測資錯) 趕快去問資工之王王挺宇吧XD 這題很心機其實是多筆測資 (只有第一筆測資是多筆測資="=) 感謝資工之王王挺宇的幫助=) 剩下的大家加油!! coding 還是要自己來的 Happy Christmas Eve! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.241.197

→

robertabcd

12/24 23:34, , 1^F

12/24 23:34, 1^F

→

robertabcd

12/24 23:34, , 2^F

12/24 23:34, 2^F

推

bang5115

12/25 00:42, , 3^F

12/25 00:42, 3^F