Добавление узла в односвязные списки (поддерживает добавление впереди, в конце и в середине) - PullRequest
Новая
       49

Добавление узла в односвязные списки (поддерживает добавление впереди, в конце и в середине)

1 голос
/ 31 октября 2019

Я пытаюсь написать функцию «add», которая принимает значение, хранящееся в узле (обозначается как «n»), и позицию, в которой узел должен быть добавлен в связанный список (обозначается как «pos»).

Я видел код, в котором есть 3 отдельные функции добавления - addAtBeginning, addAtMiddle, addAtEnd, но я хочу одну функцию добавления, которая выполняет все эти функции.

Я написал код для надстройки (int n, int pos), но он не дает ожидаемого результата.

Например, в моем главном у меня есть: 

LinkedList num;
num.add(5,1);


num.add(6,2);

num.add(7,2);
num.printList();

И я ожидаю выхода: 5 7 6, (так как 7 сместится во вторую позицию, а 6затем переместится в третью позицию), за исключением того, что я получаю вывод: 5 6 7, где 7 добавляется в 3-ю позицию.

Кроме того, я уже написал свой класс Node и класс LinkedList. Я тестировал свои функции в этих классах с небольшими приращениями, и все остальное вроде бы нормально, кроме моей функции добавления. 

Node * newNode = new Node();

newNode->setValue(n); //Node gets value n

int i=1; //ie. first position is 1, not 0

Node * current = head;

if (current == nullptr) //ie. then new node IS the head
{
    head = newNode;
    head->next=nullptr;
    return;
}

if (current->next==nullptr) //adding to end of list
{

    current->next = newNode;
    newNode->next = nullptr;

}
else //if inserting Node at middle, (neither at beginning or end)
{


    while ( i<pos && current->next != nullptr) //traverse thru list
    {
        current=current->next;
        i = i+1;
    }

    Node * oldNext = current->next; 

    current -> next = newNode;

    newNode -> next = oldNext;



}

При компиляции сообщений об ошибках нет.

Ответы [ 2 ]

2 голосов
/ 03 ноября 2019

В вашем состоянии while есть небольшая проблема, которая описана ниже: 

i=1;
while ( i<pos && current->next != nullptr) //traverse thru list
{
    current=current->next;
    i = i+1;
}

Теперь подумайте об этом сценарии, где я хочу вставить узел в место 6, которое находится вpos 2.

Vivid Idea

Согласно вашему коду, мой pos будет 2 верно? Вот где проблема возникает в соответствии с вашим кодом:

while (i

Что произойдет:

  • , когда i = 1, i
  • Теперь я стал 2, потому что i = i + 1;
  • Теперь я не меньше, чем pos, так чтовыходит из цикла, помня, что текущий узел указывает на следующий узел головы.

Node * oldNext = current-> next; 

current -> next = newNode;

newNode -> next = oldNext;

Здесь происходит следующее: ваш старый следующий указывает на 3-й узел, поскольку текущий узел является 2-м узлом.

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

0 голосов
/ 03 ноября 2019

Вам не нужно писать отдельное условие для вставки в конце. Все, что вам нужно сделать, это

  1. Сначала проверьте, будет ли это головной узел (проверив, если позиция == 1).
  2. В противном случае, просто перейдите на позицию на единицу меньше, чемПозиция, которую вы хотите вставить, например, если вставка находится на 5-м месте, затем перейдите на 4-е и затем выполните следующие действияПредположим, что мы пересекаем список по temp2, а вставляемый узел - это узел temp1. Сейчас temp2 находится на 4-й позиции. Так что в temp1-> next поставь temp2-> next. В этот момент оба указывают на требуемую 5-ю позицию. Теперь просто разорвите связь между temp2 и позицией с помощью сильного temp1 в temp2-> next. Ниже приведена реализация. 
NODE* insert_n(NODE* head,int data,int position)
{
    int i;
    NODE* temp1 = (NODE*)malloc(sizeof(NODE));
    temp1->data=data;
    temp1->next = NULL;
    if(position==1)
    {
        temp1->next = head;

        head = temp1;
        return head;
    }
    NODE* temp2 = head;
    for(i=0;i<position-2;i++)
    {
        temp2= temp2->next;
    }
    temp1->next =temp2->next;
    temp2->next = temp1;
    return (head);
}
...