Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
#1

Вставка в начало списка - C++

09.02.2014, 13:51. Просмотров 911. Ответов 18
Метки нет (Все метки)

Народ, поскажите как реализовать вставку в начало списка? текст вставки в конец сделал, а в начало не пойму как! Вот вставка в конец:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int list_push_back(list_head *list, const void *data, int data_size){
    if (list==NULL || data==NULL){ // Обязательная проверка указателей
        return 0;
    }
    /*
     * Выделение динамической памяти для хранения данных.
     * Копирование данных в новую область памяти (data_copy).
     */
    void *data_copy = malloc(data_size);
    if (data_copy==NULL){
        return 0;
    }
    memcpy(data_copy, data, data_size);
    /*
     * Выделение памяти для элемента списка.
     * Инициализация полей элемента.
     */
    list_node *node = (list_node*)malloc(sizeof(list_node));
    node->data = data_copy;
    node->next = NULL;
    list->list_size++;
    /*
     * Если список пуст, тогда добавляемый элемент
     * является первым в списке.
     */
    if (list->head==NULL){
        list->head = node;
        list->current = list->head;
        return 1;
    }
    /*
     * Если список не пуст, проходим до конца списка,
     * добавляем элемент в конец списка
     */
    list_node *current = list->head;
    while (current->next!=NULL){
        current = current->next;
    }
    current->next = node;
    return 1;
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.02.2014, 13:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вставка в начало списка (C++):

Вставка элемента в начало односвязного списка - C++
Помогите вставить элемент в начало односвязного списка. Написана функция Insert, но она работает только для вставки в середину и конец...

Получить указатель на элемент двунаправленного списка, добавить значение в начало списка и очистить его - C++
Нужно создать двунаправленный список //вроде так, но не уверен struct Double_List {//структура данных int Data;...

Удалить из списка все элементы с нечётными значениями и вывести указатель p2 на начало преобразованного списка. - C++
Здравствуйте. Не получается решить задачу. Условие. Дан непустой двусвязный список. Удалить из списка все элементы с нечётными ...

Разработать класс Итератор, методы которого: переход в начало списка, в конец, к текущему элементу списка, к с - C++
Разработать класс Итератор, методы которого: переход в начало списка, в конец, к текущему элементу списка, к следующему элементу, к...

"Сортировка двусвязного списка путем исключения элемента с минимальным значением и включения его в начало нового списка - C++
Здравствуйте! Возникла проблема с программой. Тема: "Сортировка двусвязного списка путем исключения элемента с минимальным значением и...

Вставка в начало одномерного массива - C++
Добрый день Подскажите в чём я не прав при вставке в начало массива Вставить хочу 2 цифры - 9 в начало а остальное повинуть. ...

18
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 13:58 #2
Ваша структура List, как лично я понял, хранит только один указатель - на head листа. Обычно List реализуют так, что всегда есть доступ по указателю и к началу и к концу списка.
0
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 14:01  [ТС] #3
Цитата Сообщение от parsila Посмотреть сообщение
Ваша структура List, как лично я понял, хранит только один указатель - на head листа. Обычно List реализуют так, что всегда есть доступ по указателю и к началу и к концу списка.
C++
1
2
3
4
5
6
typedef struct {
    list_node *head;    // Указатель на голову списка
    list_node *current; // Указатель на текущий элемент списка
    int list_size;      // Кол-во элементов списка
    compare_func_t func_cmp; // Указатель на функцию сравнения элементов
} list_head;
0
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 14:05 #4
Тогда для добавления в начало создайте новый экземпляр list_node, инициализируйте current указателем на него, а в новосозданном экземпляре list_node пропишите ссылку на бывший current.
0
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 14:08  [ТС] #5
Цитата Сообщение от parsila Посмотреть сообщение
Тогда для добавления в начало создайте новый экземпляр list_node, инициализируйте current указателем на него, а в новосозданном экземпляре list_node пропишите ссылку на бывший current.
извините за тупость - всмысле поменять в самой структуре?
0
zss
Модератор
Эксперт С++
6531 / 6093 / 2007
Регистрация: 18.12.2011
Сообщений: 15,845
Завершенные тесты: 1
09.02.2014, 14:10 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
А чтобы вставить в начало, не надо проходить весь список.
C++
1
2
node->next = list->head; // переносим адрес текущего первого на вставляемый элемент
list->head=node;// делаем вставляемый первым
0
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 14:12 #7
yurets17, Да. Смотрите - у Вас есть экземпляр структуры list - он хранит характерные только для него параметры - head, current и проч. Когда Вы добавляете, удаляете элементы в этот экземпляр - Вы работаете именно с ними. Поэтому изменения проводятся именно в экземпляре, а не как Вы сказали "в структуре".
0
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 14:37  [ТС] #8
Цитата Сообщение от zss Посмотреть сообщение
А чтобы вставить в начало, не надо проходить весь список.
C++
1
2
node->next = list->head; // переносим адрес текущего первого на вставляемый элемент
list->head=node;// делаем вставляемый первым
Подозреваю что не правильно, но все же сброшу
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int list_push_start(list_head *list, const void *data, int data_size){
    if (list==NULL || data==NULL){ // Обязательная проверка указателей
        return 0;
    }
    /*
     * Выделение динамической памяти для хранения данных.
     * Копирование данных в новую область памяти (data_copy).
     */
    void *data_copy = malloc(data_size);
    if (data_copy==NULL){
        return 0;
    }
    memcpy(data_copy, data, data_size);
    /*
     * Выделение памяти для элемента списка.
     * Инициализация полей элемента.
     */
    list_node *node = (list_node*)malloc(sizeof(list_node));
    node->data = data_copy;
    list->list_size++;
    node->next = list->head->next; // переносим адрес следующего на вставляемый элемент
    list->head=node;
           return 0;}
Добавлено через 7 минут
Цитата Сообщение от parsila Посмотреть сообщение
инициализируйте current указателем на него, а в новосозданном экземпляре list_node пропишите ссылку на бывший current.
обьясните пожалуйста как прописать в новосозданном экземпляре list_node ссылку на бывший current?

Добавлено через 13 минут
Цитата Сообщение от zss Посмотреть сообщение
А чтобы вставить в начало, не надо проходить весь список.
C++
1
2
node->next = list->head; // переносим адрес текущего первого на вставляемый элемент
list->head=node;// делаем вставляемый первым
Подскажите, что неправильно в коде, который я сбросил? А то с тем что вы скинули все равно не работает
0
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 14:40 #9
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
yurets17,

Я не знаю, как у вас называется указатель в list_node на следующий за ним экземпляр list_node.
Пусть это будет переменная next.
Кажется, так.
C++ (Qt)
1
2
3
list_node *new_node;
new_node->next = list.current;
list.current = new_node;
0
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 14:57  [ТС] #10
parsila,

так?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int list_push_start(list_head *list, const void *data, int data_size){
    if (list==NULL || data==NULL){ // Обязательная проверка указателей
        return 0;
    }
    /*
     * Выделение динамической памяти для хранения данных.
     * Копирование данных в новую область памяти (data_copy).
     */
    void *data_copy = malloc(data_size);
    if (data_copy==NULL){
        return 0;
    }
    memcpy(data_copy, data, data_size);
    /*
     * Выделение памяти для элемента списка.
     * Инициализация полей элемента.
     */
    list_node *node = (list_node*)malloc(sizeof(list_node));
    node->data = data_copy;
    node->next = NULL;
    list->list_size++;
 
    list_node *new_node;
    new_node->next = list->current;
    list->current = new_node;
    return 1;
}
0
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 15:04 #11
yurets17, чуть подправлю

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    int list_push_start(list_head *list, const void *data, int data_size){
    if (list==NULL || data==NULL){ // Обязательная проверка указателей
        return 0;
    }
    /*
     * Выделение динамической памяти для хранения данных.
     * Копирование данных в новую область памяти (data_copy).
     */
    void *data_copy = malloc(data_size);
    if (data_copy==NULL){
        return 0;
    }
    memcpy(data_copy, data, data_size);
    /*
     * Выделение памяти для элемента списка.
     * Инициализация полей элемента.
     */
    list_node *new_node = (list_node*)malloc(sizeof(list_node));
    new_node->data = data_copy;
    list->list_size++;
    new_node->next = list->current;
    list->current = new_node;
    return 1;
}
0
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 15:09  [ТС] #12
Цитата Сообщение от parsila Посмотреть сообщение
yurets17, чуть подправлю

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
    int list_push_start(list_head *list, const void *data, int data_size){
    if (list==NULL || data==NULL){ // Обязательная проверка указателей
        return 0;
    }
    /*
     * Выделение динамической памяти для хранения данных.
     * Копирование данных в новую область памяти (data_copy).
     */
    void *data_copy = malloc(data_size);
    if (data_copy==NULL){
        return 0;
    }
    memcpy(data_copy, data, data_size);
    /*
     * Выделение памяти для элемента списка.
     * Инициализация полей элемента.
     */
    list_node *new_node = (list_node*)malloc(sizeof(list_node));
    new_node->data = data_copy;
    list->list_size++;
    new_node->next = list->current;
    list->current = new_node;
    return 1;
}
все равно не работает! вставляет всё по очереди, а не в начало
0
zss
Модератор
Эксперт С++
6531 / 6093 / 2007
Регистрация: 18.12.2011
Сообщений: 15,845
Завершенные тесты: 1
09.02.2014, 15:20 #13
У Вас уже есть node
C
1
list_node *node = (list_node*)malloc(sizeof(list_node));
Новый создавать не надо
0
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 15:26  [ТС] #14
Цитата Сообщение от zss Посмотреть сообщение
У Вас уже есть node
C
1
list_node *node = (list_node*)malloc(sizeof(list_node));
Новый создавать не надо
я сделал, так как вы говорили! Посмотрите, это правильно? Работает правильно
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int list_push_start(list_head *list, const void *data, int data_size){
    if (list==NULL || data==NULL){ // Обязательная проверка указателей
        return 0;
    }
    /*
     * Выделение динамической памяти для хранения данных.
     * Копирование данных в новую область памяти (data_copy).
     */
    void *data_copy = malloc(data_size);
    if (data_copy==NULL){
        return 0;
    }
    memcpy(data_copy, data, data_size);
    /*
     * Выделение памяти для элемента списка.
     * Инициализация полей элемента.
     */
    list_node *node = (list_node*)malloc(sizeof(list_node));
    node->data = data_copy;
    node->next = NULL;
    list->list_size++;
    /*
     * Если список пуст, тогда добавляемый элемент
     * является первым в списке.
     */
    if (list->head==NULL){
        list->head = node;
        list->current = list->head;
        return 1;
    }
 
    node->next = list->head; // переносим адрес текущего первого на вставляемый элемент
    list->head=node;// делаем вставляемый первым
 
    return 1;
}
Добавлено через 3 минуты
Извините, что надоедаю! еще один вопрос! Как организовать удаление i-того элемента в списке?
0
zss
Модератор
Эксперт С++
6531 / 6093 / 2007
Регистрация: 18.12.2011
Сообщений: 15,845
Завершенные тесты: 1
09.02.2014, 15:32 #15
Цитата Сообщение от yurets17 Посмотреть сообщение
Как организовать удаление i-того элемента в списке?
1.Двигаетесь по списку до (i-1)-го элемента.
2.Запоминаете его.
3.Переходите к следующему.
4.Берете его поле next и переносите в поле next запомненного (предыдущего).
5.Освобождаете память текущего элемента.
1
09.02.2014, 15:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.02.2014, 15:32
Привет! Вот еще темы с ответами:

Функция: вставка в начало очереди нового элемента - C++
Написать Функцию, которая вставляет в начало очереди новый элемент.

Добавить элемент в начало списка - C++
Добавить элемент в начало списка. срочно нужно,помогите пожалуйста

Передача указателя на начало списка - C++
#include <stdio.h> #include <vld.h> #include <iostream> #include <Windows.h> #define size 20 using namespace std; struct...

Значения не вставляются в начало списка - C++
Доброго времени суток ! Помогите пожалуйста у меня значения не вставляются в начало списка. #include <iostream> using namespace...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru