Связанный список Алфавитная вставка

Question

Я пытаюсь вставить узлы в связанный список, чтобы строки, содержащиеся в данных каждого узла, сортировались в алфавитном порядке. Если вводится дублирующее слово, вместо этого увеличивается число «count» узла. Мне дана функция makeLnode(), которая создает узел, функцию isGreater(), которая сравнивает две строки, и функцию getLnodeValue(), которая возвращает строку с каждым узлом.

lnode insertWord(char * word, lnode head) { 
    /* Your code to insert a word in the linked list goes here */ 

    lnode temp = makeLnode(word); 

    if(head == NULL) // if head is null, make head=temp 
    { 
      head = temp; 
    } 

    else if(isGreater(getLnodeValue(temp),getLnodeValue(head)) == -1) // if temp < head, place temp before head 
    { 
      temp->next = head; 
      head = temp; 
    } 

    else 
    { 
      lnode curr; 
      for(curr = head; curr; curr = curr->next) // loop through linked list 
      { 

        if(isGreater(getLnodeValue(temp),getLnodeValue(curr)) == 0) // if curr = temp, increment curr 
        { 
          curr->count++; 
          break; 
        } 

        else if(isGreater(getLnodeValue(temp),getLnodeValue(curr)) == -1) // if temp < curr, place temp before curr 
        { 
          temp->next = curr->next; 
          curr->next = temp; 
          break; 
        } 

        else if(curr->next == NULL) // if we reach the end of the list and temp > all other nodes, place temp at end of list 
        { 
          curr->next = temp; 
          break; 

        } 
      } 
    } 


    return head; 
} 

Только несколько слов имеют приращение и кратны некоторые слова. Мой выход следующим образом:

1. - 2 - a 
2. - 2 - is 
3. - 1 - broadcasting 
4. - 1 - emergency 
5. - 1 - be 
6. - 1 - for 
7. - 2 - this 
8. - 1 - system 
9. - 1 - system 
10. - 1 - the 
11. - 1 - testing 
12. - 1 - seconds 
13. - 1 - sixty 
14. - 1 - next 
15. - 1 - the 
16. - 1 - test 
17. - 1 - only 
18. - 1 - test 
19. - 1 - well 

Answer 1

Вы говорите // if temp < curr, place temp before curr, но на самом деле положить его после того, как:

temp->next = curr->next; 
curr->next = temp; 

Как вы видите ваш вывод не заказывали из-за этого.

Также может возникнуть проблема с isGreater, и есть утечки памяти, но это должно быть первое, что нужно исправить.

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

Answer 2

Во-первых, вы создаете узел, прежде чем даже проверите, нужно ли его создать: в случае, если слово присутствует в списке, вам не нужен этот новый узел.

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

Например:

// check for the following base cases : no node, one node, then : 
lnode node = head; 
while (node->next && (isGreater(word,getLnodeValue(node->next)) == 1)) 
{ 
    node = node->next; 
} 

// check if the next node value is the same as your word and if it is, increment its count. 
if (isGreater(word,getLnodeValue(node->next)) == 0) 
{ 
    node->next->count++; 
} 

// Else, create a node with the word and insert the new node after the current node : 
else 
{ 
    lnode new_node = makeLnode(word); 
    new_node->next = node->next; 
    node->next = new_node; 
} 

Этот код не является полным и не очень хорошо, но вы можете начать с этого.