Блог

Главная - Вопросы по программированию - C : как вставить узел в определенную позицию в связанном списке?

C : как вставить узел в определенную позицию в связанном списке?

#c #linked-list

#c #связанный список

Вопрос:

Необходимо вставить новый узел, содержащий заданное значение данных, таким образом, чтобы новый узел занимал указанное смещение. Все узлы, которые уже были в списке с этим смещением и за его пределами, сдвигаются вниз на единицу.Это должно иметь тот же эффект, что и добавление, и никакого эффекта, если оно находится за пределами конца списка.

 void LinkedList::InsertData(int offset, int data){
  shared_ptr<node> curr(top_ptr_);
  shared_ptr<node> temp(new node);
  temp->data = data;
  temp->next = shared_ptr<node>(NULL);

  if(offset == 0) {
    temp->next = top_ptr_;
    top_ptr_ = temp;
  }
  offset--;
  while(offset-- amp;amp; curr->next!=NULL)  {
    curr = curr->next;
  }
  temp->next = curr->next;
  curr->next = temp;
}

Комментарии:

1. вы пробовали это: while(--offset amp;amp; curr->next!=NULL) и удалить offset-- перед циклом.

2. curr->next!=NULL почти всегда плохая идея в связанном списке, потому что это требует дополнительного тестирования, чтобы убедиться, что curr это действительно, прежде чем вы сможете протестировать curr->next . Вы должны переработать логику так, чтобы она проверяла curr != NULL вместо этого.

Ответ №1:

Вы близки. Поскольку вы обрабатываете offset==0 специально, вам нужно переместить свой while цикл внутри else блока, например:

 void LinkedList::InsertData(int offset, int data) {
  if (offset < 0)
    return; // or throw...

  shared_ptr<node> temp(new node);
  temp->data = data;

  if (offset == 0) {
    temp->next = top_ptr_;
    top_ptr_ = temp;
  }
  else {
    shared_ptr<node> curr = top_ptr_;
    while ((--offset > 0) amp;amp; curr->next) {
      curr = curr->next;
    }
    temp->next = curr->next;
    curr->next = temp;
  }
}

Живая демонстрация

Однако InsertData() можно упростить, полностью исключив if (offset == 0) блок, например:

 void LinkedList::InsertData(int offset, int data) {
  if (offset < 0)
    return; // or throw...

  shared_ptr<node> temp(new node);
  temp->data = data;

  shared_ptr<node> *curr = amp;top_ptr_;

  while ((offset-- > 0) amp;amp; *curr)
    curr = amp;((*curr)->next);

  temp->next = *curr;
  *curr = temp;
}

Живая демонстрация