[問題] 排序字典檔

[jimmyoic (jimmyoic)]

因為程式上的需求

而網路上抓到的字典又雜亂無章 有的有很多太偏門的單字不需要

所以打算自己寫一個可以把單字照字典規則排好的程式

以下是我的CODE  http://codepad.org/JFpbqHv6#line-70

sortByLength 是先將整個字典按照長度排好

因為預設長度不會超過30

所以我試著用counting sort 避免因為檔案太大排很慢

其中我在一開始讀檔時已經排除掉\' 已及將所有單字改成大寫以便我要用


在按照長度排完以後

接著按照一般字典規則 就是從A開頭單字排到Z開頭

然後在排完A~Z以後 A~Z的單字中再以單字的第二個字母按照A~Z排序

這裡我也是利用counting sort

因為字元A=65 ~ Z=90  我可以運用一點 假設最大值不超過90

就可以利用counting sort快一點排好 而且又可以運用他的

stable 特性 讓排序達成我要的效果(這裡不知道這樣O不OK@@)


然後因為我想要在按照第一個字母排完以後 再排第二個字母

所以在sortDic裡面有一個recurrsive 然後他吃的參數可以依照設定要從

哪個index往後開始照順序排(start,end)

以及我要依照第幾位字母sort(num) 所以在main裡我是起點給0 終點給總資料數

並且num=0 從第一位開始

recurrsive的地方我的想法是 因為已經將字母第一位按照順序排好

接著我要排第二位字母 所以要確認第一位什麼時候換成第二位 才能確定我排序要從

哪裡排到哪

譬如說

ABC
ADD
AWAKE
AWARE
ACCORDING
BAD
BED
.
.

我就要先確認A系列到哪 然後將終點記錄在mem2  起點mem當然就是從start開始

跑一個從start到end的迴圈 尋找A系列~B系列的各個切割點 然後呼叫

sortDic(dic,num+1,mem1,mem2) 同時在跑完以後將mem1設成下一個系列的起始點

其中第一個if(strlen(dic[i])-1 < num+1) 是判斷如果我要按照第num+1排單字

但是其實這個單字沒那麼長 那我就直接把起點mem1++ 加上我之前按照長度排完所有

資料 所以短資料一定會在最前面 所以可以用這個判斷直接先將這些跳過

接下來

if( i!=0 &&  dic[i-1][num]!=dic[i][num] && number >1)

就是避免i=0 起點 我還去對i-1的index判斷造成seg falut

以及他們是不是不同系列的單字 以剛剛的例子就是

dic[i-1][num]  == A    dic[i][num] == B

number是紀錄我總共有幾個單字要再加進去排 (剛剛才發現忘記在排完一系列歸0@@)

避免說我第num系列剩一個字我還丟去排 沒意義





大概就是這樣

我遇到的問題是 我先測小範圍資料時很正常 (start =0 , end = 100)

但end一改大 不知道跑到哪邊時 電腦就會變很當 然後卡住當掉

我有注意到有極少數的資料變成 ?  一個字元

我想應該跟這個有關 但我對更動字串都是用strcpy 而且看不出來有哪邊的index

有超出原本array的範圍  再加上變成 ? 的單字真的很少




文章有點長@@ 希望有高手能夠幫忙 感恩!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.221.40
→ rebaudiana:用內建函式庫解決你的問題不好嗎？
→ jimmyoic:@@?
→ bigpigbigpig:為什麼不用 strcmp ？
推 cody880528:呃  其實可以用quicksort就可以
推 cody880528:不然如果是用c++用string 更簡單
想要什麼功能沒想這麼多就試著去寫寫看@@ 可是我真的不知道code哪裡有問題
※ 編輯: jimmyoic        來自: 123.195.221.40       (11/02 22:01)
推 cody880528:呃  雖然用你的方法也能解的出來  但是真的把問題複雜
→ cody880528:話許多  而且內建函數應該也比較快
我還真的是剛剛才知道可以用qsort + strcmp 實作..
不過真的想知道這問題出在哪

→ CCWck:先給簡單的case 多印些log慢慢看吧
我有一個簡單的未排好字典檔 不知道怎麼上傳@@
※ 編輯: jimmyoic        來自: 123.195.221.40       (11/02 22:54)
推 yvb:sortDic() 中又叫用 sortDic(), 不知會叫用到幾層, 叫用幾次?
→ yvb:每次 sortDic() 開頭叫用要了一堆記憶體, 結束不釋放,
→ yvb:也沒檢查有沒有要成功, 所以大量資料時會發生什麼事沒人知道.
→ yvb:置底十三誡的第6誡.
記憶體真的是一個問題... 雖然改好以後還是會有少數變問號的問題

但是電腦不會死當 感謝
※ 編輯: jimmyoic        來自: 123.195.221.40       (11/03 14:43)