Вставка узла в n-й позиции в связанном списке - PullRequest
Новая
       82

Вставка узла в n-й позиции в связанном списке

0 голосов
/ 15 января 2019 
#include<iostream>
using namespace std;

struct node {
    int data;
    node *link;
};
node *head = NULL;

void insert(int data, int n)
{
    node *temp = new node();
    temp->data = data;

    if (n == 1)
    {
        temp->link = head;
        head = temp;
    }

    else 
    {
        node* ptr = head;
        for (int i = 1; i <= n - 1; i++)
            ptr = ptr->link;
        temp->link = ptr->link;
        ptr->link = temp;
    }
}

void print()
{
    cout << "list is: ";
    node *temp = head;
    while (temp != NULL)
    {
        cout << temp->data << " ";
        temp = temp->link;
    }
    cout << endl;
}

int main()
{
    insert(2, 1);
    insert(3, 2);
    insert(4, 3);
    insert(5, 4);
    insert(6, 5);

    print();
    return 0;
}

Это код для реализации вставки в связанный список в n-й позиции. Данные и позиция передаются с основной позиции.

Я не понимаю, какую возможную ошибку я допустил, это как-то связано с for loop.

Не выполняется, однако, если я сделаю следующее изменение: 

for(int i=0;i<n-2;i++)

отлично работает.

Ответы [ 2 ]

0 голосов
/ 15 января 2019

Первый insert(2,1) работает нормально. Итак, вы связали список, как это 

(2)->NULL
 |
head

Во второй вставке, давайте следовать за кодом, 

1. else 
2. {
3.    node* ptr = head;
4.    for (int i = 1; i <= n - 1; i++)
5.        ptr = ptr->link;
6.    temp->link = ptr->link;
7.    ptr->link = temp;
8. }

Строка 3, ptr указывает на head. n составляет 2 

(2)->NULL
 |
head
 |
ptr

Строка 4, 1 <= (2-1) равна true, потому что 1 == 1, поэтому для цикла выполняется один раз

Строка 5, ptr перемещается на один шаг, поэтому она указывает на NULL

(2)->NULL
 |    |
head  |
      |
     ptr

Строка 6, ptr->link называется, что NULL->link. Так что он падает здесь.

Когда вы делаете for(int i=0;i<n-2;i++), n равно 2, поэтому 0 < (2-2) равно false, поэтому он работает нормально. Примечание. Работает только в том случае, если вызовы вставок выполняются в порядке, подобном вашему примеру. Если они вызваны в неправильном порядке, это не сработает.

Изменение строки 6 на temp->link = ptr; также должно работать без изменения цикла.

0 голосов
/ 15 января 2019

«Вставка узла в n-ю позицию в связанном списке»:

Используйте std::list вместо того, чтобы свернуть свое собственное.Затем используйте std :: list :: insert .

Также;рассмотрите возможность использования std:: vector.Список - это структура данных ужасная (погоня за указателем, промах кэша) для использования на современных процессорах.A std::vector почти всегда побьет его (независимо от того, что ваши учебники говорят о теоретической эффективности).

...