Добавление элементов в односвязный линейный список

@M4753 · Регистрация: 24.04.2015

Author24 — интернет-сервис помощи студентам

Всем добрый день! Написала функцию, которая добавляет элементы в список, причем каждый элемент добавляется по принципу, чтобы список был упорядочен по возрастанию. Иногда функция работает, иногда нет. Знаю, что ошибка в цикле while, т.к. в итоге current = NULL и дальше добавление элемента влечет ошибку. Как поступить?

C++ (Qt)

void addBegin(node *&head, node *&current, int value)
{
    node *pred;
 
    if (!head) // Если нет головного узла
    {
        head = new node;
        head->key = value;
        head->next = NULL; // Нет следующего узла
        current = head; // Текущий узел
    }
        
    else
    {
        if (value > current->key)
        {
            node *new_el = new node;
            new_el->key = value;
            current->next = new_el;
            new_el->next = NULL;
            current = new_el;
        }
 
        else
        {
            current = head;
            while (current != NULL)
            {
                if (value < current->key)
                {
                    node *new_el = new node;
                    new_el->key = value;
                    pred->next = new_el;
                    new_el->next = current;
                }
                pred = current;
                current = current->next;
            }
        }
    }
}

@Черный мечник · 21.06.2015, 12:22

Эх люблю списки ша будем разбираться

Добавлено через 56 секунд
хотелось глянуть бы весь код

Добавлено через 3 минуты

Сообщение от M4753

Иногда функция работает, иногда нет.

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

@M4753 · 21.06.2015, 12:25 **[ТС]**

C++ (Qt)

#include <iostream>
using namespace std;
 
struct node
{
    int key;
    node *next;
};
 
int n = 10;
 
void addBegin(node *&head, node *&current, int value)
{
    node *pred;
 
    if (!head) // Если нет головного узла
    {
        head = new node;
        head->key = value;
        head->next = NULL; // Нет следующего узла
        current = head; // Текущий узел
    }
        
    else
    {
        if (value > current->key)
        {
            node *new_el = new node;
            new_el->key = value;
            current->next = new_el;
            new_el->next = NULL;
            current = new_el;
        }
 
        else
        {
            current = head;
            while (current != NULL)
            {
                if (value < current->key && current != head)
                {
                    node *new_el = new node;
                    new_el->key = value;
                    pred->next = new_el;
                    new_el->next = current;
                }
 
                pred = current;
                current = current->next;
            }
        }
    }
}
 
void print(node *head, node *current)
{
    current = head;
 
    while (current != NULL)
    {
        cout << current->key << ' ';
        current = current->next;
    }
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
 
    node *head = NULL; // Хранит адрес головного узла
    node *current = head; // Хранит адрес текущего узла
 
    for (int i = 0; i < n; ++i)
    {
        addBegin(head, current, rand()%20 + 1);
    }
 
    cout << "Список: ";
    print(head, current);
 
    cout << endl;
 
    system ("pause");
}

Добавлено через 1 минуту
Уже одну ошибку я нашла, зайдя в режим отладки) Когда добавляем перед самым первым - появляется ошибка. Но опять же как исправить:

вот эта строчка

C++ (Qt)

1 2	pred = current; current = current->next;

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

@Черный мечник · 21.06.2015, 12:36

утето да

Добавлено через 41 секунду
все гениальное просто, а я тут уже построил такие умозаключения

Добавлено через 34 секунды

C++

int n=3;  //у тебя не была инициализированна
    for (int i = 0; i < n; ++i)
    {
        addBegin(head, current, rand()%20 + 1);
    }

@M4753 · 21.06.2015, 12:36 **[ТС]**

была) в начале n = 10)

@Черный мечник · 21.06.2015, 12:44

до n=4 работает правильно

Добавлено через 2 минуты
так глобальные переменные нельзя я туда и не смотрел

@M4753 · 21.06.2015, 12:45 **[ТС]**

Я знаю, что ошибка в следующем: когда мы заходим в цикл while, то current = current->next - сдвигаем указатель. И когда current == NULL, мы выходим из цикла. Затем мы хотим добавить ещё один элемент и проверяем условие в строчке 26 и здесь появляется ошибка, т.к. current->key == ???, ведь цикл установил значение current == NULL

@Черный мечник · 21.06.2015, 14:18

C++

#include <iostream>
using namespace std;
 
struct node
{
    int key;
    node *next;
};
 
 
 
void addBegin(node *&head, node *&current, int value)
{
    node *pred;
 
    if (!head) // Если нет головного узла
      {
        head = new node;
        head->key = value;
        head->next = NULL; // Нет следующего узла
        current = head;    // Текущий узел
     }
       else
     { 
        current = head;
        while (current->next != NULL)
            {
               current = current->next;
            }
             node *new_el = new node; 
             new_el->key = value;
             new_el->next = NULL;
             current->next = new_el;
     }
 
#if 0
   else
        {
                if (value < current->key && current != head)
                {
                    node *new_el = new node;
                    new_el->key = value;
                    pred->next = new_el;
                    new_el->next = current;
                    cout<<"3\n";
                }
             pred = current;
                current = current->next;
             
            }
    #endif      
}
 
void print(node *head, node *current)
{
    current = head;
 
    while (current != NULL)
    {
        cout << current->key << ' ';
        current = current->next;
    }
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
 
    node *head = NULL; // Хранит адрес головного узла
    node *current = head; // Хранит адрес текущего узла
  int n = 12;
    for (int i = 0; i < n; ++i)
    {
        addBegin(head, current, rand()%20 + 1);
    }
 
    cout << "Список: ";
    print(head, current);
 
    cout << endl;
 
    system ("pause");
}

неправильно делает добавление элемента у тебя

сечас список просто в конец доболяет нет времени часика через полтора только свободным буду

Добавлено через 2 минуты
23-34 это если число больше посуте в твоей задумкой это должно быть в if (value > current->key)

Добавлено через 43 минуты
Эм пораскинул мозгами я понял что твоя сортировка неправильная смотри как происходит, запускается программа:
первый элемент 5 он становится главой и указывает на ноль,идет второе добавление например число 15 исходя из сравнения программа делает его головой которая указывает на элемент с 5 который в свою очередь на ноль,дальше программа добавляет число 10 например сравнивает видит что меньше, и добовляет в конец, в итоге твой список такой 15->5->10->0список не отсартированый получился хотя программа отработала на ура...
как бы я написал-придумал функцию(или блок добавления переписать заново) в которой сравнива элементы и давала координаты какие надо изменить 15->5->0 тоесть одним указателем(элемента 15) на следуший элемент стояшим на 5 изменяла на 10,а указатель(элемента 10) на 5...

@M4753 · 21.06.2015, 16:08 **[ТС]**

Всё, спасибо, проблема решена. Оказывается условие для сортировки не было верным. Пришлось блок вообще с нуля переписать. Зато разобралась со списком. Тему можно закрыть

@Черный мечник 55 / 56 / 34 Регистрация: 29.12.2012 Сообщений: 478
	21.06.2015, 12:22	2
	Эх люблю списки ша будем разбираться Добавлено через 56 секунд хотелось глянуть бы весь код Добавлено через 3 минуты Сообщение от M4753 Иногда функция работает, иногда нет. думаю тут зависит от данных которые вводят, а так как у тебя он упорядочный скорее всего какаято ошибка в построении списка тоесть, или в голову или в хвост гдето неправильно добавляется 0

@M4753 2 / 2 / 0 Регистрация: 24.04.2015 Сообщений: 102
	21.06.2015, 12:36 [ТС]	5
	была) в начале n = 10) 0

@Черный мечник 55 / 56 / 34 Регистрация: 29.12.2012 Сообщений: 478
	21.06.2015, 12:44	6
	до n=4 работает правильно Добавлено через 2 минуты так глобальные переменные нельзя я туда и не смотрел 0

@M4753 2 / 2 / 0 Регистрация: 24.04.2015 Сообщений: 102
	21.06.2015, 12:45 [ТС]	7
	Я знаю, что ошибка в следующем: когда мы заходим в цикл while, то current = current->next - сдвигаем указатель. И когда current == NULL, мы выходим из цикла. Затем мы хотим добавить ещё один элемент и проверяем условие в строчке 26 и здесь появляется ошибка, т.к. current->key == ???, ведь цикл установил значение current == NULL 0

@M4753 2 / 2 / 0 Регистрация: 24.04.2015 Сообщений: 102
	21.06.2015, 16:08 [ТС]	9
	Всё, спасибо, проблема решена. Оказывается условие для сортировки не было верным. Пришлось блок вообще с нуля переписать. Зато разобралась со списком. Тему можно закрыть 0