Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.53/15: Рейтинг темы: голосов - 15, средняя оценка - 4.53
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
1

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

23.12.2016, 16:30. Просмотров 2983. Ответов 16
Метки нет (Все метки)


Помогите сделать вставку элемента в пустой односвязный список. У меня работает вставка только при непустом.Заранее благодарен!Функция Insert
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <string>
#include <Windows.h>
 
using namespace std;
 
struct List    //струткура
{
    int Data;
    int key;
    List* next;
 
};
 
int control(string Nom)   //контроль входных данных
{
 
    int i = 0, len = Nom.length(), n;
 
    char p = Nom.c_str()[i];
    setlocale(LC_ALL, "Russian");
    while (1)
    {
        if ((p < '0') || (p > '9'))
        {
            cout << "Ошибка. Введите целое положительное число: ";
            cin >> Nom;
            i = 0;
            p = Nom.c_str()[i];
            len = Nom.length();
            n = atoi(Nom.c_str());
        }
        i++;
        p = Nom.c_str()[i];
        n = atoi(Nom.c_str());
 
        if (i == len) break;
    }
    return n;
}
 
void Init(int n, List**begin) //заполнение списка
{
    int s;
    string a;
    string Nom;
    if (n > 0)
    {
        (*begin) = new List();  //выделение памяти
        cout << "Введите значение: ";
        cin >> a;
        s = control(a); //контроль входных данных
        (*begin)->Data = s;
        (*begin)->next = NULL;
        Init(n - 1, &((*begin)->next));
    }
}
 
void Print(List*begin) //печать списка
{
    if (begin != NULL)
    {
        cout << begin->Data << "\t";
        Print(begin->next);
    }
    else cout << "\n";
}
 
 
void Insert(List *begin, unsigned n, int val) //вставка элемента в список
{
    unsigned i = 1;
    string a;
    int s;
    List *tmp = NULL;
    List*first = NULL;
    //Находим нужный элемент. Если вышли за пределы списка, то выходим из цикла,
    //ошибка выбрасываться не будет, произойдёт вставка в конец
    if (n == 1)
    {
        List* newSecondElem = new List(*begin);
        begin->Data = val;
        begin->next = newSecondElem;
        return;
    }
    else {
        while (i < (n - 1) && begin->next)
        {
            begin = begin->next;
            i++;
        }
        tmp = (List*)malloc(sizeof(List));
        tmp->Data = val;
        //Если это не последний элемент, то next перекидываем на следующий узел
        if (begin->next)
        {
            tmp->next = begin->next;
            //иначе на NULL
        }
        else tmp->next = NULL;
        begin->next = tmp;
    }
}
 
 
void Search(List*begin, int val) //поиск элемента в списке
{
    bool f = false;
    int i = 1;
    while (begin)
    {
        if (begin->Data == val) //поиск по значению
        {
            f = true;
            cout << "Элемент найден,его позиция: " << i << endl;
            break;
        }
        else begin = begin->next;
        i++;
    }
    if (f == false) cout << "Элемент не найден" << endl;
}
 
void Delete(List *&head, int data) //удаление элемента списка
{
    List *temp = head;
    List *el = NULL;
    if (head && head->Data == data)
    {
        el = head;
        head = head->next;
        delete el;
        return;
    }
    while (temp->next)
    {
        if (temp->next->Data == data)
        {
            el = temp->next;
            temp->next = el->next;
            delete el;
            return;
        }
        temp = temp->next;
 
    }
}
void Free(List**begin) //удаление всего списка
{
    List*p = *begin;
    List*first;
 
    if (*begin == NULL) cout << "Попытка очистить пустой ЛОС\n";
    while (p)
    {
        first = p;
        p = p->next;
        delete first;
    }
    *begin = NULL;
}
 
void Check(List** begin) //проверка пустоты списка
{
    if (*begin == NULL)
    {
        cout << "Список пустой!" << endl;
    }
    else cout << "Список не пустой!" << endl;
}
 
 
int menu(List*begin) //меню
{
    int v;
    string vv;
        cout << "Меню" << endl;
        cout << "1. Создать ЛОС" << endl;
        cout << "2. Вывести на экран текущий список" << endl;
        cout << "3. Вставка элемента в список" << endl;
        cout << "4. Удаление элемента из списка" << endl;
        cout << "5. Поиск элемента в списке" << endl;
        cout << "6. Удаление всего списка" << endl;
        cout << "7. Проверка пустоты списка" << endl;
        cout << "8. Завершение программы" << endl;
        cout << "Введите цифру: ";
        cin >> vv;
        v = control(vv);
    return v;
}
 
int main() //основная функция
{
    int n, val, a, vall, b, v;
    string Nom, udal, pos, num, sear;
    char key = 'Y';
    setlocale(LC_ALL, "Russian");
 
    List* begin = NULL;
    cout << " ВАС ПРИВЕТСТВУЕТ ПРОГРАММА ЛИНЕЙНОГО ОДНОСВЯЗНОГО СПИСКА" << endl;
    v = menu(begin);
    while ((key == 'Y') || (key == 'y'))
    {
        
        switch (v) //реализация меню
        {
        case 1:
        {
            cout << "Введите размер n (n>1): ";
            cin >> Nom;
            n = control(Nom);
            while (n < 2) // проверка списка на ввод больше одного элемента
            {
                cout << "Ошибка!Введите целое положительное число (n>1): ";
                cin >> Nom;
                n = control(Nom);
            }
            Init(n, &begin);
            cout << "Исходный список: ";
            Print(begin);
            v = menu(begin);
        }break;
        case 2://печать списка
        {
            cout << "Исходный список: ";
            Print(begin);
            v = menu(begin);
        }break;
        case 3://вставка элемента в список
        {
            cout << "Введите позицию (pos>0), на которую хотите вставить новый элемент: ";
            cin >> pos;
            a = control(pos);
            while (a < 1)//начальная позиция начинается с 1
            {
                cout << "Ошибка! Введите позицию (pos>0): ";
                cin >> pos;
                a = control(pos);
            }
            cout << "Введите вставляемое число: ";
            cin >> num;
            val = control(num);
            Insert(begin, a, val);
            cout << "Исходный список: ";
            Print(begin);
            v = menu(begin);
        }break;
        case 4://удаление элемента списка
        {
            cout << "Введите удаляемый элемент: ";
            cin >> udal;
            b = control(udal);
            Delete(begin, b);
            cout << "Исходный список: ";
            Print(begin);
            v = menu(begin);
        }break;
        case 5://поиск элемента
        {
            cout << "Введите искомое число: ";
            cin >> sear;
            vall = control(sear);
            Search(begin, vall);
            v = menu(begin);
        }break;
        case 6://удаление всего списка
        {
            Free(&begin);
            cout << "Исходный список: ";
            Print(begin);
            v = menu(begin);
        }break;
        case 7://проверка пустоты списка
        {
            Check(&begin);
            v = menu(begin);
        }break;
        case 8://завершение работы
        {
            cout << "Программа завершена!";
            key = 'n';
            Sleep(2000);
        }break;
        default://контроль при некорректном вводе
        {
            cout << "Ошибка!" << endl;
            v = menu(begin);
        }
        }
    }
    return 0;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.12.2016, 16:30
Ответы с готовыми решениями:

Вставка элемента в линейный односвязный список после заданного
Я составила программу, но возникла проблема с реализацией вставки элемента после указанного...

Вставка нового элемента в линейный односвязный список перед элементом с максимальным значением ключа
Привет, всем. Помогите, разобраться с добавлением нового элемента в линейный односвязный список...

Вставка в односвязный список
Как реализуется, можно с пояснениями?

Односвязный список. Вставка списка
Доброго времени суток. Кто может подсказать в чём причина того что я не могу присвоить значение...

16
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 17:29 2
Цитата Сообщение от Skier97 Посмотреть сообщение
Помогите сделать вставку элемента в пустой односвязный список. У меня работает вставка только при непустом.
А вы не делайте его пустым. Первым элементом списка должен быть элемент-заглушка присутствующий всегда "шоб было". Поле next последнего элемента списка должно указывать на начальный элемент-заглушку (кольцевой список), чтоб не морочить себе голову этими NULL. И жить сразу становится проще, жить становится веселее.
Алсо, раз уж это тема про C++, то изучите new и конструкторы. А не создавайте объекты через malloc.
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 17:31  [ТС] 3
у меня линейный односвязный, а не кольцевой. И как тогда быть? Использую malloc потому что не срабатывало по другому, не мог додуматься. Если можете, то есть какой то другой вариант вставки?
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 17:37 4
Цитата Сообщение от Skier97 Посмотреть сообщение
у меня линейный односвязный, а не кольцевой.
А что мешает кольцевому списку быть односвязным?
Цитата Сообщение от Skier97 Посмотреть сообщение
И как тогда быть?
По плюсовому - List переименовать в ListNode. Потом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
class List
{
public:
    void insert(int n,int value);
private:
    ListNode*begin;
};
void List::insert(int n,int value)
{
    if(!begin)
        //воткнуть сюда код создающий первый элемент и пихающий его в begin
}
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 17:42  [ТС] 5
так он же должен быть линейный, или типо кольцевой не имеет значение для этого?
А без классов нельзя? Просто просили лучше без них
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 17:51 6
Цитата Сообщение от Skier97 Посмотреть сообщение
так он же должен быть линейный, или типо кольцевой не имеет значение для этого?
А, тогда пардон.
Цитата Сообщение от Skier97 Посмотреть сообщение
А без классов нельзя? Просто просили лучше без них
Можно - void Insert(List *&begin, unsigned n, int val). Дальше как в примере выше - if(!begin)...
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 18:02  [ТС] 7
Я сделал так,ввожу значение позиции равной 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
void Insert(List *&begin, unsigned n, int val) //вставка элемента в список
{
    unsigned i = 1;
    string a;
    List *tmp = NULL;
    if (!begin)
    {
        List* newSecondElem = new List(*begin);
        begin->Data = val;
        begin->next = newSecondElem;
        return;
    }
 
}
case 3://вставка элемента в список
        {
            cout << "Введите позицию (pos>0), на которую хотите вставить новый элемент: ";
            cin >> pos;
            a = control(pos);
            while (a < 1)//начальная позиция начинается с 1
            {
                cout << "Ошибка! Введите позицию (pos>0): ";
                cin >> pos;
                a = control(pos);
            }
            cout << "Введите вставляемое число: ";
            cin >> num;
            val = control(num);
            Insert(begin, a, val);
            cout << "Исходный список: ";
            Print(begin);
            v = menu(begin);
        }break;
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 18:04 8
Цитата Сообщение от Skier97 Посмотреть сообщение
Я сделал так,ввожу значение позиции равной 1 и значение, и затем вылетает
А зачем вы пытаетесь создавать копию не существующего элемента? new List(*begin).
Алсо, "впихнуть в begin" это begin=new List. newSecondElem не нужны.
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 18:09  [ТС] 9
а указатель next на что передавать будет?
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 18:12 10
Цитата Сообщение от Skier97 Посмотреть сообщение
а указатель next на что передавать будет?
А указатель next будет указывать на NULL. Вы же вставляете в список первый, а следовательно и последний элемент. И это не кольцевой список или список с элементами-заглушками созданными специально чтоб на них указывали.
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 18:15  [ТС] 11
Я сделал так и он у меня только первый элемент заполняет
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Insert(List *&begin, unsigned n, int val) //вставка элемента в список
{
    unsigned i = 1;
    string a;
    List *tmp = NULL;
    while (i < (n) && begin->next)
    {
        begin = begin->next;
        i++;
    }
 
    if (!begin)
    {
        begin = new List();
        begin->Data = val;
        begin->next = NULL;
        return;
    }
 
}
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 18:25 12
Цитата Сообщение от Skier97 Посмотреть сообщение
Я сделал так и он у меня только первый элемент заполняет
Ну а в ветку else киньте код работавший при не пустом списке. А вообще:
C++
1
2
3
4
5
6
7
8
9
10
11
void Insert(List **begin, unsigned n, int val)
{
    while(--n && (*begin)->next)
        begin=&(*begin)->next;
    List*next=*begin;
    *begin=new List;
    (*begin)->next=next;
    (*begin)->data=val;
}
...
Insert(&begin,1,1234);
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 18:29  [ТС] 13
он просто удаляет предыдущие значения в списке и записывает новое, когда я хочу вставить не на первую позицию

Добавлено через 15 секунд
сейчас попробую

Добавлено через 4 минуты
он почему то когда вставляем у меня в списке один элемент и я хочу вставить на вторую позицию новый, он его ставит на первую позицию, зато потом все работает нормально
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 18:30 14
Лучший ответ Сообщение было отмечено Skier97 как решение

Решение

Цитата Сообщение от Renji Посмотреть сообщение
while(--n && (*begin)->next)
Упс, попутал - while(--n && *begin).
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
struct List
{
    List*next;
    int data;
};
 
void Insert(List **begin, unsigned n, int val)
{
    while(--n && *begin)
        begin=&(*begin)->next;
    List*next=*begin;
    *begin=new List;
    (*begin)->next=next;
    (*begin)->data=val;
}
 
int main()
{
    List*begin=nullptr;
    Insert(&begin,1,1);
    Insert(&begin,2,2);
    Insert(&begin,2,3);
    for(List*pos=begin;pos;pos=pos->next)
        std::cout<<pos->data<<std::endl;
    return 0;
}
Итого
1
3
2
1
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 18:36  [ТС] 15
спасибо , все работает!
А что значит while(--n && *begin)?

Добавлено через 1 минуту
и зачем пишем это?(*begin)->next = next;
0
2706 / 1875 / 554
Регистрация: 05.06.2014
Сообщений: 5,447
23.12.2016, 18:52 16
Цитата Сообщение от Skier97 Посмотреть сообщение
А что значит while(--n && *begin)?
--n - уменьшает n на единицу и возвращает получившееся число. Далее идет неявное n!=0 (в логических выражениях число считается истиной если не ноль и ложью если ноль).
begin - указатель на тот указатель, в который надо положить адрес нового элемента списка. Для первого элемента это указатель на начало списка. Для второго элемента - next первого элемента. Для третьего - next второго элемента и так далее. Цикл while перебирает эти указатели. Ну а *begin проверяет что этот самый "указатель, в который надо положить адрес" не равен NULL. Если равен, значит мы добрались до next последнего элемента и уперлись в конец списка.
Цитата Сообщение от Skier97 Посмотреть сообщение
и зачем пишем это?(*begin)->next = next;
Затем, что next здесь - указатель на элемент идущий следом за вставленным. Вы на бумажке себе схему происходящего нарисуйте, так понятней будет.
0
1 / 1 / 0
Регистрация: 11.11.2016
Сообщений: 104
23.12.2016, 18:56  [ТС] 17
понял спасибо
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.12.2016, 18:56

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

вставка элемента в линейный односвязный список
Здравствуйте! У меня вот такое задание: требуется программа, позволяющая вставлять новый элемент...

Односвязный список: просмотр, поиск, вставка и удаление элементов
Нужно создать односвязный список типа общего вида, элементы которого описываются следующим образом:...

Добавление элемента в односвязный список
Здравствуйте, делаю односвязный список, возник такой вопрос в следующем методе: void Add(int a)...

Односвязный список: удаление элемента
написал такой код . но оно не удаляет первый элемент . как исправить ? bool DeleteByIndex(Us*...


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

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

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