Представление отношений в списке слов в списке смежности для быстрого поиска - PullRequest
Новая
       47

Представление отношений в списке слов в списке смежности для быстрого поиска

0 голосов
/ 09 октября 2018

Я пишу программу, которая должна прочитать файл слов и затем найти самое короткое из одного слова в другое, перейдя от начального слова к соседнему слову, которое будет отличаться на одну букву, простой пример: Стартовое слово: конечное слово собаки: for может быть: "dog -> fog -> for".

Моя идея - создать BFS в соседнем списке.Все работает в моем коде, кроме моего графика (смежный список).Проблема в том, что я хочу хешировать слова в индексе на графике, но для этого нужно знать конечный размер списка.

Я начинаю с добавления вектора, который будет содержать весь список слов.используйте размер этого вектора, чтобы установить размер массива, а затем я перебираю вектор, чтобы хэшировать слова в массив.

Мой соседний список имеет тип: 

    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;

Hashfunction: 

   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;

У меня естьсильное чувство, что просто идея добавить вектор, чтобы извлечь из него элементы и добавить его в массив, достаточно глупа.Хотя я не могу придумать более хороших рабочих идей (и та, которая у меня есть сейчас, тоже не работает).Должен ли я использовать список смежности вообще?Это хорошая идея, чтобы хэшировать слова или есть лучшие способы?Кто-нибудь понимает, какую программу я пытаюсь создать, и есть идеи, которые могут быть полезны?

...