※ 引述《one1130 (小柔)》之銘言： : 我想問一下各位大大 : 我現在要寫個具有英譯德及德譯英之雙向字典 : 以binary search tree建立以提升查詢速度, : 然後 : 字典內容由一input file 叫hw2.in輸入 : 字典的功能: 新增.刪除.修改.翻譯查詢(德英互翻) : 那請問我要怎麼寫這各程式 : 非常感恩 我要先裝熟一下， 我幾天前系上學弟也因為一模一樣的作業題目有問題來問我， 如果真的這麼巧的話，我會說有興趣的話可以來北極光切磋討論。XD 基本上我自己是覺得這個問題用BS比較好做啦， 不過他們助教認為BST比較方便，what ever 反正差異在資料的結構上。 你要寫的程式喔，把握一個重點，雙向的意思就是key跟value互換， 也就是排序的依序是不同的，我會建議你用兩個list維護。 如果BS的話基本上排序資料然後用BS找到插入點跟目標就好。 BST的話要實做樹狀結構(跟LinkedList有點像，去翻翻資結書)， 用root對資料作比對，依序對樹做travel。 我自己在觀摩這題時是有做語言跟語系的相關介面， 字典是採用"主要語言"的方式來區隔德英跟英德， 這樣比較方便擴展三種以上的單字查詢，這是題外話就是了。 --- 話說我本來是明天要跟學弟去跟助教聊一下這個問題，順便也在這裡聊一聊好了。 寫樹狀結構的實做成本不計(假設結構都已經做好了)， 以Binary Search應用在排序的List上，新增應該是O(log2N)，刪除也是O(log2N)。 查詢跟刪除是一樣的嘛，也是O(log2n) BST 根據我的認知要在best case(每一顆樹剛好二分左右子樹總數) 才是 log2n (也就是 Ω(log2n)) worst case 是 O(n) (剛好是形成一個完全傾斜的樹) 不管怎麼看，BS好像都比BST好做吧， 因為助教是說BST在新增刪除方面比較容易使用， 所以我在想是不是有甚麼成本我沒算到。 是有想到， 是差在插入跟刪除還有指到特定目標的成本嗎(在LinkedList時指定元素要一一循覽) ArrayList則是刪除時後面跟著往前移動，以及新增時跟著往後挪。 我在想是不是因為這兩個因素，如果有人對這個結構比較熟的可以討論一下， 很多成本都很容易讓人遺忘啊Q_Q -- 　▄▅▆▇███▇▆▅▄▃　　　　　　　　╰┼╯─╮ ╮　　　　　 　 　◥███████████◣　　　　　　　╰┼╯＝│=│　　　　　　　　 ◥██████───────◣　　　　＊．　╯　 ╯ ╯ の　物　語　．＊ 　◥███████──────◣　～　◢◣　　　　　　　　　　　　 ◢◣ 　◥██████───────◤　　　◥◤＊　　空白的世界．翼 ＊◥◤ 　◥██▁▂▃▄▅▆▇███▆▅▄▃▂▂～telnet://tony1223.no-ip.info --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.132.59.247