[分享] qsort
這幾天寫了幾題的DFS
發現qsort對於需要某些特殊需求的DFS來說實在好用
比如說當DFS要求有兩個以上子節點時
先輸出編號小的
那麼先sort好再用adjacent list實作非常簡單
但是sort怎麼弄最簡捷有力呢?
小弟不才提供個小方法:
1.首先儲存edge的方法:
typedef struct List{
int head,tail;
}LIST;
存完後呼叫qsort
2.qsort compare的寫法:
int com(const void *a,const void *b)
{
LIST c,d;
c=*(LIST*)(a);
d=*(LIST*)(b);
if(c.head!=d.head) //先排好頭
return c.head>d.head?1:-1;
else{ //頭一樣大的話
if(c.tail!=d.tail)
return c.tail>d.tail?1:-1; //比尾巴
else
return 0;
}
}
上面稍作修改
就可以快速做出字典排序的效果
省去了許多打code的麻煩
時間又是 n log n而已
提出一點膚淺的想法> <
如果有人有更好的修正法麻煩幫忙修改> <
謝謝> <
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.200.13
→
08/27 23:05, , 1F
08/27 23:05, 1F
→
08/27 23:06, , 2F
08/27 23:06, 2F
→
08/27 23:07, , 3F
08/27 23:07, 3F
→
08/27 23:08, , 4F
08/27 23:08, 4F
→
08/27 23:10, , 5F
08/27 23:10, 5F
→
08/27 23:10, , 6F
08/27 23:10, 6F
→
08/27 23:12, , 7F
08/27 23:12, 7F
→
08/27 23:13, , 8F
08/27 23:13, 8F
→
08/27 23:16, , 9F
08/27 23:16, 9F
→
08/27 23:17, , 10F
08/27 23:17, 10F
→
08/27 23:17, , 11F
08/27 23:17, 11F
→
08/27 23:17, , 12F
08/27 23:17, 12F
→
08/27 23:18, , 13F
08/27 23:18, 13F
像我
比如說輸入
1 2
3 6
4 9
1 7
2 6
我會把它全部弄成雙向
弄成
1 2
1 7
2 1
2 6
3 6
4 9
6 2
6 3
7 1
然後存每個開頭有幾個
比如說1就是有2個
然後存每個開頭在第幾個
比如說3就是4
然後去跑DFS
這樣真的不會比較方便嗎??
※ 編輯: flere 來自: 140.114.200.13 (08/27 23:23)
→
08/27 23:22, , 14F
08/27 23:22, 14F
推
08/27 23:22, , 15F
08/27 23:22, 15F
推
08/27 23:23, , 16F
08/27 23:23, 16F
→
08/27 23:24, , 17F
08/27 23:24, 17F
推
08/27 23:24, , 18F
08/27 23:24, 18F
→
08/27 23:24, , 19F
08/27 23:24, 19F
→
08/27 23:24, , 20F
08/27 23:24, 20F
→
08/27 23:24, , 21F
08/27 23:24, 21F
→
08/27 23:25, , 22F
08/27 23:25, 22F
→
08/27 23:26, , 23F
08/27 23:26, 23F
→
08/27 23:27, , 24F
08/27 23:27, 24F
→
08/27 23:28, , 25F
08/27 23:28, 25F
→
08/27 23:38, , 26F
08/27 23:38, 26F
→
08/27 23:39, , 27F
08/27 23:39, 27F
→
08/27 23:41, , 28F
08/27 23:41, 28F
→
08/27 23:41, , 29F
08/27 23:41, 29F
→
08/27 23:41, , 30F
08/27 23:41, 30F
→
08/27 23:43, , 31F
08/27 23:43, 31F
→
08/27 23:44, , 32F
08/27 23:44, 32F
→
08/27 23:46, , 33F
08/27 23:46, 33F
推
08/28 06:59, , 34F
08/28 06:59, 34F