Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Илич
0 / 0 / 1
Регистрация: 17.02.2016
Сообщений: 9
#1

Преобразовать односвязный список в двусвязный список - C++

18.01.2018, 09:46. Просмотров 158. Ответов 1
Метки нет (Все метки)

Доброго времени суток! Помогите, пожалуйста, преобразовать программу из односвязного списка в двусвязный. Спасибо.
http://www.cyberforum.ru/cpp-beginners/thread604615.html

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
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <fstream>
#include <locale>
 
using namespace std;
 
//имя файла откуда считываем данные
char fileName[] = "in.txt";
 
//структура телевизоры
struct tv
{
    //модель
    char modl[20];
    //марка
    char mark[20];
    //год выпуска
    int year;
};
 
//структура линейный динамический спискок
struct List
{
    //информации хранящяеся в звене списка
    tv info;
    //указатель на следующее звено списка
    List *next;
    List *prev;
};
//прототипы функций
//т.е. заголовки функций, а их реализации находится после реализации функции main
void add(List * &head, List * &tail, tv st);
void output(List *head);
int length(List *head);
int del(List * &head, List * &tail, int index);
int edit(List * &head, int index);
void sort(List * &head);
void newTV(tv &st);
void clear(List * &head, List * &tail);
void loadFromFile(char *fileName, List * &head, List * &tail);
void saveToFile(char *fileName, List *head);
int find(char *num, List *head, tv &st);
 
//главная функция
int main()
{
    setlocale(LC_ALL, "Russian");
    tv st;
    //объявляем указатели на голову и хвост списка
    List *head = NULL, *tail = NULL;
    int choise, index;
    char num[10];
    do
    {
        //очищаем экран
        system("cls");
        //выводим меню
        cout << "1 - Добавить телевизор в список\n";
        cout << "2 - Изменить элемент списка\n";
        cout << "3 - Удалить элемент из списка\n";
        cout << "4 - Поиск элемента в списке\n";
        cout << "5 - Вывод всех телевизоров\n";
        cout << "6 - Отсортировать по году выпуска\n";
        cout << "7 - Загрузить из файла\n";
        cout << "8 - Выгрузить в файл\n";
        cout << "0 - Выход\n";
        cout << "Выберете действие: ";
        cin >> choise;
        //в зависимости от того, что выбра выполняем определенные действия
        switch (choise)
        {
        case 1:
            //вызываем функцию для получения нового элемента "Телевизор"
            newTV(st);
            //добавляем  телевизор в  список 
            add(head, tail, st);
            cout << "Телевизор добавлена\n";
            break;
        case 2:
            cout << "Индекс элемента для изменения: ";
            cin >> index;
            //вызываем метод для изменения данных о телевизоре
            //и если функция вернула 0 значит всё прошло успешно
            //иначе данные  не были изменены
            if (edit(head, index) == 0) cout << "Элемент с индексом " << index << " изменён\n";
            else cout << "Элемента с индексом " << index << " нет\n";
            break;
        case 3:
            cout << "Индекс элемента для удаления: ";
            cin >> index;
            //вызываем метод для удаления телевизор
            //и если функция вернула 0 значит всё прошло успешно
            //иначе телевизор не была удалёна
            if (del(head, tail, index) == 0) cout << "Элемент с индексом " << index << " удалён\n";
            else cout << "Элемента с индексом " << index << " нет\n";
            break;
        case 4:
            cout << "Введите телевизор для поиска: ";
            fflush(stdin);
            cin.getline(num, 10);
            fflush(stdin);
            if (find(num, head, st) == 0) printf("Телевизор найдена\n|%10s|%20s|%5d|\n", st.modl, st.mark, st.year);
            else cout << "Телевизор такой модели отстуствует\n";
            break;
        case 5:
            //вызываем функцию для вывода информации о Телевизор  на экран
            output(head);
            break;
        case 6:
            //вызываем функция для сортировки данных о Телевизор по году выпуска
            sort(head);
            cout << "Список отсортирован\n";
            break;
        case 7:
            loadFromFile(fileName, head, tail);
            break;
        case 8:
            saveToFile(fileName, head);
            cout << "Данные выгружены в файл\n";
            break;
        }
        //если выбранное действие попадает в отрезок [1..8] то задерживаем результат на экране
        if (choise > 0 && choise <= 8) system("pause");
    } while (choise != 0);
    //вызываем функцию для очистки памяти занятой списком
    clear(head, tail);
    return 0;
}
 
//функция для добавления элемента st в список 
void add(List * &head, List * &tail, tv st)
{
    if (head == NULL) //если список ещё не создан,то
    {
        head = new List;//выделяем место под голову списка
        head->next = NULL;//зануляем указатель на следующий элемент
        head->info = st;//заносим данные в голову списка
        tail = head; // хвост списка устанавливаем в head
    }
    else //иначе
    {
        List *x = new List;//выделяем место под новый элемент
        x->info = st;//заносим туда данные
        x->next = NULL;//указатель на следующий элемент ставим в NULL т.е. его не существует пока что
        tail->next = x;//и связываем новый элемент с хвостом списка
        tail = x;//и хвост списка ставим равным x
    }
}
 
//функция для получения количества элементов в списке head
int length(List *head)
{
    //обнуляем количество элементов списка
    int n = 0;
    //пока не конец списка делаем
    while (head != NULL)
    {
        //увеличиваем количество элементов на 1
        n++;
        //переходим к следующему звену списка
        head = head->next;
    }
    //возвращаем количество элементов списка
    return n;
}
 
//функция для вывода списка на экран
void output(List *head)
{
    //если head = NULL значит список пуст
    if (head == NULL)
    {
        cout << "Список пуст\n";
        return;
    }
    //выводим шапку для вывода информации об оружии
    const char l[] = "---------------------------------------\n";
    cout << l;
    cout << "|   Модель  |        Марка       | Год |\n";
    cout << l;
    //пока не конец списка
    while (head != NULL)
    {
        //выводим на экран данные о очередном телевизоре
        printf("|%10s|%20s|%5d|\n", head->info.modl, head->info.mark, head->info.year);
        //переходим к следующему телевизору
        head = head->next;
    }
    cout << l;
}
 
//функция для удаления элемента списка с индексом index
int del(List * &head, List * &tail, int index)
{
    //получаем количество элементов списка
    int n = length(head);
    //если index больше количества элементов списка или меньше или равно нуля или список пуст то
    if (index > n || index <= 0 || n == 0)
    {
        //возвращаем результат работы функции =1 т.е. есть ошибки
        return 1;
    }
    List *t = head, *tt = head;
    //если необходимо удалить первый элемент списка то
    if (index == 1)
    {
        //запоминаем первый элемент списка в переменной t
        t = head;
        //переходим к следующему элементу
        head = head->next;
        //удаляем первый элемент
        delete t;
        //если голова списка стала пустой то
        //и хвост списка ставим пустым
        if (head == NULL) tail = NULL;
    }
    //иначе
    else
    {
        //запоминаем текущий элемент списка
        tt = head;
        //запоминаем последующий элемент списка
        t = head->next;
        //индексацию начинаем с 1 т.к. первый элемент уже просмотрен
        int i = 1;
        //пока не конец списка
        while (t != NULL)
        {
            //увеличиваем индекс на 1
            i++;
            //если i == index, т.е. индекс текущего элемента равен индексу удаляемого то
            if (i == index)
            {
                //переставляем указатели
                tt->next = t->next;
                //прерываем цикл
                break;
            }
            //переходим к следующим элементам
            tt = tt->next;
            t = t->next;
        }
        //если удаляемый элемент является последним то меняем указатель на хвост списка
        if (index == n) tail = tt;
        //освобождаем память занятую под элемент с индексом index
        delete t;
    }
    //оповещаем о корректном удалении
    return 0;
}
 
//функция для изменения информации об оружии с индексом index
int edit(List * &head, int index)
{
    //получаем количество элементов списка
    int n = length(head);
    //если index больше количества элементов списка или меньше или равно нуля или список пуст то
    if (index > n || index <= 0 || n == 0)
    {
        //возвращаем результат работы функции =1 т.е. есть ошибки
        return 1;
    }
    int i = 0;
    List *t = head;
    //пока не конец списка
    while (t != NULL)
    {
        i++;
        //если индекс текущего элемента равен индексу искомого то
        if (i == index)
        {
            tv st;
            //вызываем функцию для получения информации о новой телевизоре
            newTV(st);
            //и в звено с индексом index заносим данные о новой телевизоре
            t->info = st;
            //прерываем цикл
            break;
        }
        //переходим к слудующему элементу
        t = t->next;
    }
    return 0;
}
 
//функция для ввода информации о новой телевизоре с клавиатуры
void newTV(tv &st)
 
{
    //очистка буфера ввода
    fflush(stdin);
 
    cout << "Модель: ";
 
    //вводим Модель
 
    cin.getline(st.modl, 30);
 
    fflush(stdin);
 
    cout << "Марка: ";
 
    cin.getline(st.mark, 20);
 
    fflush(stdin);
 
    cout << "Год выпуска: ";
 
    cin >> st.year;
 
    fflush(stdin);
 
}
 
//функция для сортировка списка
void sort(List * &head)
{
    List *t = head, *tt;
    tv temp;
    //пузырьковая сортировка
    while (t != NULL)
    {
        tt = t->next;
        while (tt != NULL)
        {
            if (tt->info.year < t->info.year)
            {
                temp = tt->info;
                tt->info = t->info;
                t->info = temp;
            }
            tt = tt->next;
        }
        t = t->next;
    }
}
 
//функция для очитски памяти занятой списком
void clear(List * &head, List * &tail)
{
    List *t;
    while (head != NULL) //пока не конец списка,делаем
    {
        t = head->next; //переходим к следующему элементу
        delete head;//очищаем память занятой под head
        head = t;//заносим в head значение t
    }
    tail = NULL;
}
 
//функция для сохранения информации о телевизорах в файл с иненем fileName
void saveToFile(char fileName[], List *head)
{
    //открываем файл с именем fileName для записи
    ofstream out(fileName);
    //пока не конец списка выполянем
    while (head != NULL)
    {
        //записываем в файл информацию о очередной телевизоре
        out << head->info.modl << "\n";
        out << head->info.mark << "\n";
        out << head->info.year;
        //переходим к следующей телевизоре
        head = head->next;
        //если есть ещё телевизоры то заносим в файл перевод строки
        //эта проверка нужна для того чтобы в файл не записывать лишнюю пустую строку
        if (head != NULL) out << "\n";
    }
    out.close();
}
 
void loadFromFile(char *fileName, List * &head, List * &tail)
{
    //открываем файл с именем fileName на чтение 
    ifstream in(fileName);
    tv st;
    char y[10];
    //если файл открыт
    if (in.is_open())
    {
        //очищаем список
        clear(head, tail);
        //пока не конец файла выполняем
        while (!in.eof())
        {
            //считываем из файла модель
            in.getline(st.modl, 10);
            //считываем название
            in.getline(st.mark, 20);
            //считываем год
            in.getline(y, 10);
            st.year = atoi(y);
            //вызываем функцию для добавления элемента st в список 
            add(head, tail, st);
        }
        cout << "Данные из файла получены\n";
    }
    else cout << "Файл отсутствует\n";
    //закрываем файл
    in.close();
}
 
//функция поиска телевизора по модель
int find(char *cal, List *head, tv &st)
{
    //пока не конец списка выполянем
    while (head != NULL)
    {
        if (strcmp(head->info.modl, cal) == 0)
        {
            st = head->info;
            return 0;
        }
        head = head->next;
    }
    return 1;
}
0
Вложения
Тип файла: zip coursework.zip (4.1 Кб, 0 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2018, 09:46
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Преобразовать односвязный список в двусвязный список (C++):

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

Заменить массив структур на односвязный список, и на двусвязный список
Взять текст задания и заменить массив структур на односвязный список, и на...

Создать двусвязный список групп факультета, где каждая группа представляет собой односвязный список студентов
Задание: создайте двусвязный список групп факультета. Каждая группа...

Двусвязный в односвязный список
Добрый день.Помогите,пожалуйста,переделать программу,обрабатывающую двухсвязный...

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

1
DobroAlex
Модератор
367 / 312 / 159
Регистрация: 30.04.2016
Сообщений: 1,630
Завершенные тесты: 3
18.01.2018, 09:56 #2
Илич,
C++
1
2
List *next;
    List *prev;
Это уже двусвязный. И поменяйте char[] на string, не в 70-х живём
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.01.2018, 09:56
Привет! Вот еще темы с решениями:

Возможно ли как-то переделать односвязный список в двусвязный?
Собственно вопрос в названии. Возможно ли переделать односвязный список в...

Создать динамический односвязный или двусвязный список
Помогите, как создать динамический односвязный или двусвязный список(Описать...

Односвязный (двусвязный) список - поиск людей по минимальному и максимальному возрасту
Здравствуйте форумчане. Имеется задание: Для структуры из Вашего варианта...

Реализовать иерархию классов, включающую в себя односвязный и двусвязный список
Нужно реализовать иерархию классов, включающую в себя односвязный и двусвязный...


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

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

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