Программа списка C++ замерзает, когда я вызываю функцию

Question

Этот код должен вставить символ 'p' перед символом 'q', сколько раз «q» появляется в списке.

Когда я вызываю функцию insert_before (insert_before('q','p')) моя программа зависает. Здесь я не пишу весь код. Остальная часть программы работает нормально.

struct node 
{ 
    char character; 
    node* next; 
}; 
node *fisrt , *end; 
void insert_before(char val_search,char val_inserted) 
{ 
    node *c,*a; 
    c=first; 
    do { 
     if (c->next->character==val_search) 
     { 
      a= new node ; 
      a->character=val_inserted ; 
      a->next=c->next; 
      c->next=a; 
      c=c->next; 
     } 
     else 
      c=c->next; 
    } while (c) ; 
} 

Answer 1

Проблемы

Давайте предположим, что у вас есть список с уникальным элементом «д» в нем: first и last бы оба указывают на этот единый узел. И указателем next узла будет nullptr.

Когда вы выполните insert_before(), вы начинаете с c=first. Таким образом, c указывает на этот уникальный узел, у которого next есть nullptr. К сожалению, эта инструкция: if (c->next->character==val_search) будет разыменовывать nullptr. Это неопределенное поведение и может вызывать симптомы, которые вы описываете.

Если ваше искомое значение не является первым элементом, ваш код будет работать в принципе. К сожалению, после того, как вы вставили элемент, вы продолжаете цикл: вы должны зациклиться на новом элементе, и условие будет истинным снова, так что вы снова введете новый элемент и так далее, бесконечно зацикливая, пока ваш список не исчерпает всю память. Это также приведет к замораживанию. Кстати, вы действительно хотите вставить 'p' перед всеми 'q в списке?

Первая поправка

Просто исправить петлю, быть более осторожным:

void insert_before(char val_search,char val_inserted) 
{ 
    node *c,*a; 
    for (c=first; c && c->next; c=c->next) { 
     if (c->next->character==val_search) 
     { 
      a= new node ; 
      a->character=val_inserted ; 
      a->next=c->next; 
      c->next=a; 
      c=a; 
     } 
    } 
} 

Обратите внимание, что этот код, точно так, как ваш код, не обрабатывает должным образом вставку в передней части списка ,

Второе исправление:

Чтобы иметь возможность вставить впереди, вам нужно что-то вроде этого:

void insert_before(char val_search,char val_inserted) 
{ 
    node *c,*a, *prev=nullptr; 
    for (c=first; c ; prev=c, c=c->next) { 
     if (c->character==val_search) 
     { 
      a= new node ; 
      a->character=val_inserted ; 
      a->next=c; 
      if (prev) 
      prev->next=a; 
      else first=a; 
     } 
    } 
} 

Live demo

Answer 2

Внутри, если {}, измените c = c-> рядом с c = a-> next.

Answer 3

Когда вы найдете значение p, вы вносите новую запись до найденной записи.

Это означает, что в следующий раз вы увидите тот же элемент снова и вставить другую новую запись перед тем найденную запись

+---+ +---+ 
| x |->| p | 
+---+ +---+ 
    c 

станет

+---+ +---+ +---+ 
| x |->| q |->| p | 
+---+ +---+ +---+ 
     c 

, а затем он станет

+---+ +---+ +---+ +---+ 
| x |->| q |->| q |->| p | 
+---+ +---+ +---+ +---+ 
       c 

и так далее.

Поскольку это никогда не закончится (пока не закончится память), программа, похоже, замерзнет.