※ 引述《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