代码之家  ›  专栏  ›  技术社区  ›  zkalman

通过邻接列表表示单词列表中的关系,以便快速搜索

  •  0
  • zkalman  · 技术社区  · 6 年前

    我正在编写一个程序,该程序应该读取一个单词文件,然后从一个单词到另一个单词,通过从startword到一个相邻的单词,找到最短的单词,该单词将与一个字母不同,简单的示例:startword:dog endword:for可以是:“dog->fog->for”。

    我的想法是在相邻的列表中做BFS。在我的代码中,除了我的图形(相邻列表)之外,其他一切都正常工作。问题是,我想将单词散列到图中的索引中,但为此需要知道列表的endsize。

    我首先添加一个向量,它将包含整个单词列表,我使用这个向量的大小来设置arraylist的大小,然后我迭代这个向量,将单词散列到arraylist中。

    我旁边的列表类型为:

        ArrayList<LinkedList<String>> adj_list;
    

    以下是我如何使用它:

        public void adda(Vector<String> v){
        M = v.size();
        adj_list = new ArrayList<LinkedList<String>>(M);
        for (int i = 0; i < M; i++){
            add(v.get(i));
        }
    
        void add (String word){
        int z = hash(word);
        for (int i = z; i < M; i++){
            if(adj_list.get(i)== null){
                z=i;
                adj_list.add(new LinkedList<String>());
                break;
    

    哈希函数:

       public static int hash(String key) {
            int i;
            int v = 0;
            for (i = 0; i < key.length(); i++) {
                v += key.charAt(i);
            }
            return v % M;
    

    0 回复  |  直到 6 年前
    推荐文章