Re: 雙層排序問題

看板C_and_CPP (C/C++)作者softwind (software everywhere)時間16年前 (2009/06/24 01:59)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串3/6 (看更多)

※ 引述《yauhh (喲)》之銘言： : ※ 引述《aoaay (低調奢華簡約時尚)》之銘言： : : 不好意思小弟新手 : : 最近遇到一個問題 : : 問題如下: : : 若英文字母的priority的大小如下BROYGLPW : : 要將12組資料依序排好: 先依priority,再依數值由小至大,將結果輸出至檔案. : : 結果檔案內容應如下: : : B 81 : : B 99 : : R 23 : : R 56 : : O 72 : : W 15 : : L 11 : : Y 55 : : O 78 : : W 89 : : P 98 : : G 56 : : 該如何寫請板上大大教一下給個方向謝謝這個問題滿好玩的因為多層排序在很多struct中常常出現通常過了第一關(排兩層) 後面要排3 4 層都比較能接受還有一個問題如果排序方式不是依據原本的連續性像是你給的 BROYGLPW 或是中文的排序(用注音排) 都會有跳躍區間的情形依據你給的問題其實 "BROYGLPW" 是跳躍的prior 想像你用下列結構去承接 typedef struct{ char ch; unsigned int prior; }S_CHAR_PRIOR_PAIR; 用資料庫的看法這兩個欄位都可以當key 你用 ch去查一個特定 'B' 必定存在一組也只能有一組紀錄用 prior = 1去查結果亦同所以你用 "BROYGLPW" 和他的prior並行array <1,2,3,4,5,6,7,8> 來看兩個是一樣的 but 最大的差別是 {1,2,3,4,5,6,7,8} 是嚴格遞增所以用 array 對回 ch 是 O(1) 但是 "BROYGLPW" 並不連續所以頂多用我之前敲過的 compiling-time fixed array -> poweron-time qsort -> run-time bsearch 降到 O(logN) --------------------------------------------------------------------- 假設你接一組 <'B',81> 用的是 typedef struct{ char ch; int value; }S_CHAR_VAL_PAIR; 字母比對自行實作 int getPrior_byChar( char ch ); //如果覺得麻煩就用線性search吧 cmp func: int cmp_byChVal( const void *pL, const void *pR){ int pr1 = getPrior_byChar( ((S_CHAR_PRIOR_PAIR*)pL)->ch ); int pr2 = getPrior_byChar( ((S_CHAR_PRIOR_PAIR*)pR)->ch ); int res=0; if ( (res=pr1-pr2)!=0 ) return res; return ((S_CHAR_PRIOR_PAIR*)pL)->value - ((S_CHAR_PRIOR_PAIR*)pR)->value; } -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.166.121.159