Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 13:51     Вставка в начало списка #1
Народ, поскажите как реализовать вставку в начало списка? текст вставки в конец сделал, а в начало не пойму как! Вот вставка в конец:
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;
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 13:58     Вставка в начало списка #2
Ваша структура List, как лично я понял, хранит только один указатель - на head листа. Обычно List реализуют так, что всегда есть доступ по указателю и к началу и к концу списка.
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;
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 14:05     Вставка в начало списка #4
Тогда для добавления в начало создайте новый экземпляр list_node, инициализируйте current указателем на него, а в новосозданном экземпляре list_node пропишите ссылку на бывший current.
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 14:08  [ТС]     Вставка в начало списка #5
Цитата Сообщение от parsila Посмотреть сообщение
Тогда для добавления в начало создайте новый экземпляр list_node, инициализируйте current указателем на него, а в новосозданном экземпляре list_node пропишите ссылку на бывший current.
извините за тупость - всмысле поменять в самой структуре?
zss
Модератор
Эксперт С++
 Аватар для zss
5948 / 5553 / 1785
Регистрация: 18.12.2011
Сообщений: 14,192
Завершенные тесты: 1
09.02.2014, 14:10     Вставка в начало списка #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
А чтобы вставить в начало, не надо проходить весь список.
C++
1
2
node->next = list->head; // переносим адрес текущего первого на вставляемый элемент
list->head=node;// делаем вставляемый первым
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
09.02.2014, 14:12     Вставка в начало списка #7
yurets17, Да. Смотрите - у Вас есть экземпляр структуры list - он хранит характерные только для него параметры - head, current и проч. Когда Вы добавляете, удаляете элементы в этот экземпляр - Вы работаете именно с ними. Поэтому изменения проводятся именно в экземпляре, а не как Вы сказали "в структуре".
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;// делаем вставляемый первым
Подскажите, что неправильно в коде, который я сбросил? А то с тем что вы скинули все равно не работает
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;
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;
}
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;
}
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;
}
все равно не работает! вставляет всё по очереди, а не в начало
zss
Модератор
Эксперт С++
 Аватар для zss
5948 / 5553 / 1785
Регистрация: 18.12.2011
Сообщений: 14,192
Завершенные тесты: 1
09.02.2014, 15:20     Вставка в начало списка #13
У Вас уже есть node
C
1
list_node *node = (list_node*)malloc(sizeof(list_node));
Новый создавать не надо
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-того элемента в списке?
zss
Модератор
Эксперт С++
 Аватар для zss
5948 / 5553 / 1785
Регистрация: 18.12.2011
Сообщений: 14,192
Завершенные тесты: 1
09.02.2014, 15:32     Вставка в начало списка #15
Цитата Сообщение от yurets17 Посмотреть сообщение
Как организовать удаление i-того элемента в списке?
1.Двигаетесь по списку до (i-1)-го элемента.
2.Запоминаете его.
3.Переходите к следующему.
4.Берете его поле next и переносите в поле next запомненного (предыдущего).
5.Освобождаете память текущего элемента.
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 17:14  [ТС]     Вставка в начало списка #16
Цитата Сообщение от zss Посмотреть сообщение
1.Двигаетесь по списку до (i-1)-го элемента.
2.Запоминаете его.
3.Переходите к следующему.
4.Берете его поле next и переносите в поле next запомненного (предыдущего).
5.Освобождаете память текущего элемента.
а так не пойдет?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
int list_del(list_head *list, int i){
 
    list_node *ptr=list->head;
    list_node *temp;
    int num=0;
 
    while (num++!=i)
    ptr=ptr->next;
    temp=ptr->next; //Указатель temp указывает на удаляемый элемент
    ptr->next=temp->next;
    delete temp;
    return 0;
}
zss
Модератор
Эксперт С++
 Аватар для zss
5948 / 5553 / 1785
Регистрация: 18.12.2011
Сообщений: 14,192
Завершенные тесты: 1
09.02.2014, 17:21     Вставка в начало списка #17
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int list_del(list_head *list, int i){
 
    list_node *ptr=list->head;
    list_node *temp;
    int num=0;
 
    while (num++!=i-1)
         ptr=ptr->next;
    temp=ptr; // Запомнили предыдущий
    ptr=ptr->next; // перешли к удаляемому
    temp->next=ptr->next; // перенесли указатель из удаляемого на предыдущий
    delete ptr; // удалили текущий
    return 0;
}
И еще не забудьте рассмотреть пустой список и учесть возможность того, что у списка не окажется i элементов.
yurets17
1 / 1 / 0
Регистрация: 07.10.2013
Сообщений: 170
09.02.2014, 17:47  [ТС]     Вставка в начало списка #18
Цитата Сообщение от zss Посмотреть сообщение
И еще не забудьте рассмотреть пустой список и учесть возможность того, что у списка не окажется i элементов.
А если я введу і равное 0, то будет ошибка если num++!=i-1

Добавлено через 15 минут
Цитата Сообщение от zss Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int list_del(list_head *list, int i){
 
    list_node *ptr=list->head;
    list_node *temp;
    int num=0;
 
    while (num++!=i-1)
         ptr=ptr->next;
    temp=ptr; // Запомнили предыдущий
    ptr=ptr->next; // перешли к удаляемому
    temp->next=ptr->next; // перенесли указатель из удаляемого на предыдущий
    delete ptr; // удалили текущий
    return 0;
}
И еще не забудьте рассмотреть пустой список и учесть возможность того, что у списка не окажется i элементов.
А если мне примеру нужно удалить нулевой элемент?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.02.2014, 22:24     Вставка в начало списка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
parsila
5 / 5 / 3
Регистрация: 08.04.2013
Сообщений: 30
12.02.2014, 22:24     Вставка в начало списка #19
Если Вам нужно удалить нулевой элемент, просто присвойте list->current значение list->current->next.
Yandex
Объявления
12.02.2014, 22:24     Вставка в начало списка
Ответ Создать тему
Опции темы

Текущее время: 19:54. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru