Алгоритмы и структуры данных ЛР2. Двусвязные списки
 Скачать 0.5 Mb.
|
|
Министерство цифрового развития, связи и массовых коммуникаций Российской Федерации Сибирский государственный университет телекоммуникаций и информатики Межрегиональный учебный центр переподготовки специалистов Лабораторная работа №2 по дисциплине: Алгоритмы и структуры данных Лабораторная работа №2 Тема: Двусвязные списки Цель работы: изучить понятие и способы описания двусвязных списков и освоить их программную реализацию средствами языка С++. Задание: На основе материалов конспекта лекций (раздел 3) и рекомендуемой литературы изучить теоретический материал по программированию двусвязного и кольцевого списка. Составить программу на языке С++, в которой реализовать двусвязный список целых чисел. Предусмотреть операции добавления, изменения и удаления элемента в указанной позиции. Сформировать список произвольных целых чисел (не менее 10 элементов) и вывести его на экран. В соответствии с индивидуальным вариантом (табл. 1) обработать данные списка. При этом не использовать дополнительные списки или массивы. Обработанные данные вывести на экран. Модифицировать программу для работы с кольцевым двусвязным списком и протестировать ее работу. Сравнить реализации обоих списков и сделать выводы. Таблица 1 - Индивидуальные задания к лабораторной работе №2
Блок-схемы алгоритмов.   Рисунок 1. Блок-схема основной программы  Рисунок 2. Блок-схема инициализации списка с 1 узлом и данными параметра а  Рисунок 3. Блок-схема добавления элемента в конец списка  Рисунок 4. Блок-схема добавления элемента в начало списка  Рисунок 5. Блок-схема вывода списка на экран  Рисунок 6. Блок-схема вывода списка на экан в обратном порядке  Рисунок 7. Блок-схема добавления элемента в указанную позицию  Рисунок 8. Блок-схема удаления элемента из указанной позиции  Рисунок 9. Блок-схема изменения элемента в указанной позиции  Рисунок 10. Блок-схема сортировки списка Текст программы. #include #include #include #include #include using namespace std; // Статическая структура, описывающая узел списка typedef struct list { int info; struct list* next; struct list* prev; }; typedef list* LLink; // тип данных: указатель на элемент LLink Head = NULL; // Функция инициализации списка с 1 узлом и данными параметра а list* init(int a) { list* lst = new list; lst->info = a; lst->next = NULL; lst->prev = NULL; Head = lst; return Head; } // Функция добавления элемента в конец списка void add_tail(list* lst, int item) { if (lst == NULL) lst = init(item); else { list* tmp = lst; while (tmp->next != NULL) tmp = tmp->next; list* p = new list; tmp->next = p; p->info = item; p->next = NULL; p->prev = tmp; } } // Функция добавления элемента в начало списка void add_head(list* lst, int item) { list* p = new list; p->next = lst; lst->prev = p; lst = p; p->info = item; p->prev = NULL; Head = lst; } // Функция вывода списка на консоль void printlist(list* lst) { list* p = lst; wcout << L"LIST:" << endl; while (p!= NULL) { wcout << (*p).info << L" "; p = (*p).next; } wcout << endl; } // Функция вывода списка в обратном порядке на консоль void printlist_rev(list* lst) { list* p = lst; wcout << L"LIST:" << endl; while (p->next!= NULL) p = (*p).next; while (p->prev!= NULL) { wcout << (*p).info << L" "; p = (*p).prev; } wcout << (*p).info << L" "; wcout << endl; } // Функция добавления элемента в указанную позицию void add_pos(list* lst, int pos, int item) { list* p = lst; if (pos <= 0) { wcout << L"В указанную позицию вставить элемент не возможно" << endl; return; } else if (pos == 1) { add_head(lst, item); return; } else { for (int i=1; i < pos-1; i++) { if (p->next == NULL) { add_tail(lst, item); return; } else { p = p->next; } } list* s = new list; s->info = item; p->next->prev = s; s->next = p->next; p->next = s; s->prev = p; p = p->next; } } // Функция удаления элемента из указанной позиции void del_pos(list* lst, int pos) { list* p = lst; if (pos <= 0) { wcout << L"Указанной позиции не существует" << endl; return; } else if (pos == 1) { Head = p->next; return; } else { for (int i = 1; i < pos; i++) { if (p->next == NULL) { wcout << L"Указанной позиции не существует" << endl; return; } else { p = p->next; } } p->prev->next = p->next; } } // Функция изменения элемента в указанной позиции void edit_pos(list* lst, int pos, int item) { list* p = lst; if (pos <= 0) { wcout << L"В указанной позиции нет элемента" << endl; return; } else if (pos == 1) { p->info = item; return; } else { for (int i = 1; i < pos; i++) { if (p->next == NULL) { wcout << L"В указанной позиции нет элемента" << endl; return; } else { p = p->next; } } p->info = item; } } // Функция сортировки списка void sort(list* lst) { LLink curr; int tmp; curr = lst->next; while (curr) { tmp = curr->info; LLink prv = curr->prev; while (prv != NULL && tmp < prv->info) { prv->next->info = prv->info; prv = prv->prev; } if (prv == NULL) lst->info = tmp; else prv->next->info = tmp; curr = curr->next; } } int main() { wcout.imbue(locale("rus_rus.866")); int Num; //число ряда list* lst = new list; for (int i = 1; i <= 10; i++) //ввод чисел ряда в список { wcout << L"Введите " << i << L"-е число: "; wcin >> Num; add_tail(Head, Num); //добавление в список новых чисел } wcout << L"Вывод списка: " << endl; printlist(Head); //вывод списка в консоль wcout << L"Вывод списка в обратном порядке: "; printlist_rev(Head); //вывод списка в обратном порядке в консоль wcout << L"Введите число для добавления в начало списка: "; wcin >> Num; add_head(Head, Num); //добавление в начало списка нового числа wcout << L"Вывод списка: " << endl; printlist(Head); //вывод списка в консоль int pos; wcout << L"Введите позицию списка для добавления: "; wcin >> pos; wcout << L"Введите число: "; wcin >> Num; add_pos(Head, pos, Num); //добавление в выбранную позицию списка нового числа wcout << L"Вывод списка: " << endl; printlist(Head); //вывод списка в консоль wcout << L"Введите позицию списка для удаления: "; wcin >> pos; del_pos(Head, pos); //удаление числа из позиции в списке wcout << L"Вывод списка: " << endl; printlist(Head); //вывод списка в консоль wcout << L"Введите позицию списка для изменения: "; wcin >> pos; wcout << L"Введите число: "; wcin >> Num; edit_pos(Head, pos, Num); //изменение числа в выбранной позиции списка wcout << L"Вывод списка: " << endl; printlist(Head); //вывод списка в консоль sort(Head); //сортировка списка wcout << L"Вывод списка после сортировки: " << endl; printlist(Head); //вывод списка в консоль char ch = _getch(); //ожидание нажатия любой клавиши } Результат выполнения программы.  Анализ полученных результатов. Список формируется в соответствии с ожидаемыми результатами. Новые элементы добавляются корректно с учетом заданный позиций. Удаление и изменение элементов списка работает корректно. Список выводиться на экран в правильном порядке. Подпрограмма сортировки списка работает корректно. Выводы по работе. В ходе работы научились создавать двухсвязный список, добавлять в него новые элементы, удалять элементы, последовательно получать данные из списка в соответствии с очередностью списка от начала до конца, изменять данные элементов списка. |