Хранение данных с использованием линейных списков

СОДЕРЖАНИЕ

 

Введение…………………………………………………………………..		4
1	Реализация линейных списков…………………………………….	6
2	Разработка и выбор алгоритмов…………………………………...	9
3	Описание работы программы на псевдокоде……………………..	13
4	Составление программного кода………………………………….	14
5	Тестирование и отладка программы………………………………	23
6	Результат работы программы……………………………………...	27
Заключение………………………………………………………………..		29
Список используемых источников……………………………………...		30
Приложение. Листинг программы………………………………………		31

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

На сегодняшний  день информация и информационные ресурсы  играют огромную роль в жизни человека. Существует множество выражений, которые  отражают этот факт, например «Знаешь  всё – владеешь миром», «Проинформирован – значит вооружен» и т.п. Поэтому вопрос эффективного хранения и обработки информации является одним из самых актуальных.

Одним из решений этого вопроса является линейные списки. Список – это набор  записей, выстроенных в определенной последовательности.[1] В повседневной жизни списки окружают нас повсюду, являясь довольно эффективным способом хранения нужной нам информации. Примерами могут служить список продуктов, который составляют  при походе в магазин, список студентов в журнале, список дел на день, различные словари и т.д. Область применения линейных списков достаточно широка:

• в операционных системах (очередь задач, готовых к выполнению, очередь документов к принтеру; стек состояний прерванных процессов (задач);
• в системах имитационного моделирования (очередь заявок на обслуживание какой-либо системой массового обслуживания );
• в научном и исследовательском ПО и т. д.

Линейные  списки находят широкое применение в приложениях, где непредсказуемы требования на размер памяти, необходимой  для хранения данных; большое число  сложных операций над данными, особенно включений и исключений. На базе линейных списков могут строиться стеки, очереди и деки. Представление очереди с помощью линейного списка позволяет достаточно просто обеспечить любые желаемые дисциплины обслуживания очереди. Особенно это удобно, когда число элементов в очереди трудно предсказуемо.

Основными достоинствами линейных списков являются:

• лёгкость добавления и удаления элементов;
• размер ограничен только объёмом памяти компьютера и разрядностью указателей;
• динамическое добавление и удаление элементов.

Целью моей курсовой работы является разработка программы на языке C++, осуществляющей эффективное хранение и обработку данных на основе линейных списков. Для достижения цели поставлены следующие задачи:

• уяснить поставленную задачу;
• выбрать реализацию линейного списка;
• выбрать алгоритмы для реализации функций линейного списка;
• написать, протестировать и отладить программу.

 

 

 

 

 

 

 

 

 

 

 

 

 

1  Реализация линейных списков

Для успешного  выполнения поставленных задач необходимо основательно разобраться, что собой  представляют линейные списки и как  они реализуются в языке программирования C++.

Проблема  эффективного управления данными является важнейшей для любой реализации списка. Список представляет совокупность связанных между собой узлов. Любой узел представляет собой структуру (в смысле struct), содержащую, по крайней мере, два поля: для хранения данных и для указателя. Полей данных и указателей может быть несколько. Поля данных могут быть любого типа: основного, составного или типа указатель. Описание простейшего элемента (компоненты, узла) выглядит следующим образом:

struct Node

{

Data d; // тип данных Data должен быть определен ранее

Node *next; // указатель на следующий элемент списка

Node *prev; // указатель на следующий элемент (если используется     двусвязный список)

};

Список, каждый элемент которого содержит  указатель только на следующий за ним элемент, называется однонаправленным или односвязным. Если добавить в каждый элемент вторую ссылку — на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список. [2] На рисунке 1 приведена структура односвязного списка. На нем поле INF - информационное поле (данные), NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.

 

Рисунок 1 – Структура односвязного списка

 

Однако, обработка односвязного списка не всегда удобна, так как отсутствует возможность  продвижения в противоположную  сторону. Такую возможность обеспечивает двусвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. Структура линейного двухсвязного списка приведена на рисунке 2, где поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil, как и показано на рисунке 2:

 

 

 

 

 

Рисунок 2 – Структура двусвязного списка

 

Для удобства обработки списка добавляют еще  один особый элемент - указатель конца  списка. Наличие двух указателей в  каждом элементе усложняет список и  приводит к дополнительным затратам памяти, но в то же время обеспечивает более эффективное выполнение некоторых  операций над списком. [3]

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

 

 

 

 

 

 

Рисунок 3 – Структура кольцевого списка

 

При работе со списками используются следующие основные операции:

• начальное формирование списка (создание первого элемента);
• добавление элемента в конец списка;
• чтение элемента с заданным ключом;
• вставка элемента в заданное место списка (до или после элемента с заданным ключом);
• удаление элемента с заданным ключом;
• упорядочивание списка по ключу.  

 

 

 

  2  Разработка и выбор алгоритмов

   В своей работе за основу я решил взять линейный двусвязный список, так как считаю, что он обеспечивает наиболее эффективную работу с данными. Основное внимание при разработке программы следует уделить разбиению на функции и спецификации их интерфейсов. Т.е. логично оформить в виде функций различные операции со списком (формирование, поиск, добавление, удаление элемента и т.д.), поскольку они представляют собой законченные действия. Интерфейс пользователя организуем в виде текстового меню, которое будет выводиться на экран после каждого действия.

Будем исходить из того, что все функции должны быть независимы, чтобы изменения  в одной функции не могли влиять на поведение другой. Для этого всё, что функциям необходимо получать извне, будем передавать им через параметры.

Элементы  списка представим в виде структуры  с именем Node, содержащей информационное поле (собственно хранимый символ) и два указателя: на предыдущий элемент и на следующий.

struct Node

{

char d;

Node *next;

Node *prev;

};

Теперь  определим интерфейс программы. Перечислим основные функции работы с элементами списка, которые нам  понадобятся:

• добавление элемента;
• вставка элемента;
• удаление выбранного элемента;
• поиск заданного элемента;
• сортировка списка;
• выполнение задания курсовой работы;
• вывод списка на экран.

 

Каждый пункт этого  меню, оформим в виде отдельной  функции. Давайте путем логических рассуждений попытаемся определить их интерфейсы и алгоритмы работы.

Добавление элемента.

Чтобы добавить новый элемент  в список, нужно знать, что и куда добавлять. Иными словами в функцию в качестве параметров нужно передать указатели на начало списка и конец списка, а внутри нее организовать ввод элемента. При этом указатели на начало и конец списка должны быть изменены внутри функции, следовательно, следует передать их по ссылкам. Алгоритм работы функции добавления следующий: ввести элемент, затем обнулить указатель на следующий элемент (т.к. добавление происходит в конец списка), а в указатель на предыдущий элемент записать адрес предыдущего элемента или обнулить его (если список пуст).

Вставка элемента.

Чтобы вставить новый элемент  в список, нужно знать после  какого элемента будет произведена  вставка. Следовательно, алгоритм работы функции вставки такой: ввести вставляемый  элемент, ввести элемент, после которого будет произведена вставка и  если такой элемент найден, произвести вставку и скорректировать указатели  головы и хвоста списка.

Удаление элемента.

Чтобы удалить  элемент, нужно знать, откуда и какой элемент удалить. Предварительно нужно найти этот элемент, т.е. путем прохода по списку получить указатель на него. Следовательно, внутри функции удаления будет вызываться функция поиска, которую тоже следует оформить отдельно. Алгоритм работы функции удаления следующий: вводится элемент, который требуется удалить, затем в зависимости от того, находится элемент в начале списка, в середине или в конце, этот элемент удаляется и соответствующим образом корректируются указатели на предыдущий и следующий элементы, а также указатели головы и хвоста списка. В качестве параметров функция будет получать ссылки на начало и конец списка.

Поиск элемента.

Тривиальным алгоритмом для решения поставленной задачи является последовательный, или  линейный, поиск. Я решил использовать его в своей программе, т.к. его  реализация достаточно проста. Он заключается  в том, что мы поочередно сравниваем какой-либо элемент со всеми элементами последовательности. Обнаружив совпадение, мы возвращаем индекс найденного элемента (в нашем случае указатель на него).[4] В качестве параметров в функцию поиска будут передаваться указатель на начало списка и искомый элемент.

Сортировка  списка.

Среди различных  алгоритмов сортировки, таких как  сортировка вставкой, выбором, слиянием и прочих, наиболее оригинальным мне кажется алгоритм пузырьковой сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву элементов. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

Рисунок 4 – Пример пузырьковой сортировки

 

Вывод на экран.

Алгоритм  работы этой функции достаточно прост: если список не пуст, мы проходим по всем элементам, начиная с первого, и  выводим их на экран. Для передвижения по списку будем использовать указатели  на следующие элементы, которые содержатся во всех элементах списка. В качестве своего единственного параметра  функция будет получать указатель  головы списка.

Функция, выполняющая задание курсовой работы.

Данная  функция будет являться основной в моей программе, поэтому разработке ее интерфейса следует уделить особое внимание. Действия, которые будет  выполнять эта функция, состоят  в следующем: вводятся три последовательности различных символов и затем на экран выводятся общие символы  этих последовательностей. Для ввода  будем использовать функцию добавления элемента, которая в ходе цикла  будет добавлять в список некоторое  количество элементов, которое определяет пользователь. Затем с помощью  функции поиска производится поочередный  поиск символов первой последовательности (можно взять любую) в двух других. И если символ присутствует и во второй и в третьей последовательности, он выводится на экран. Функция не будет принимать никаких параметров.

Текстовое меню.

Интерфейс пользователя представим в виде простейшего  текстового меню, которое будет выводиться на экран после каждого действия. Алгоритм работы данной функции также  довольно прост: на экран будут выводиться пункты меню в виде текстовых записей, которые будут оставаться на экране до тех пор, пока пользователь не нажмет нужную клавишу. После нажатия клавиши  будет выполнено соответствующее  действие, а затем на экране вновь  появится текст меню.