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

Размещено на

Размещено на

1. Постановка задачи

Составить программу - магазин с одним продавцом. Компьютер вместо кассового аппарата. База наличия товаров.

1. Наименование товара

2. Единица измерения

3. Цена единицы

4. Количество

5. Дата завоза

· Регистрация поступления товаров

· Оформление покупки: выписка чека, корректировка базы.

· Проблема уценки и описания

· Инвентаризация остатков товара с вычислением суммарной стоимости

Программа должна обеспечивать:

· Диалог с помощью меню

· Контроль ошибок при вводе данных

2. Теоретическая часть

2.1 Динамические структуры данных. Классификация

линейный односвязный список программа

Для того чтобы в процессе выполнения программы произвольно добавлять и удалять данные, необходимо организовать данные не в массив, а во что-то другое. Если к элементу данных добавить ещё и указатель, в котором будет храниться адрес какого-то другого элемента, то это и будет кардинальным решением проблемы. Такая организация представления и хранения данных называется динамической структурой данных.

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

Кроме того, динамические структуры позволяют нам организовать данные так, чтобы их представление в программе было максимально приближено к тому, как эти данные выглядят в реальности. Так, для моделирования обслуживания очереди к врачу лучше всего подойдет динамическая структура данных под названием «очередь», а не массив, а для представления сети автомобильных дорог нужна «сеть».

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

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

Элемент любой динамической структуры данных представляет собой структуру (struct), содержащую, по крайней мере, два поля - для хранения данных и для указателя. В общем случае полей данных и указателей может быть несколько. Поля данных могут быть любого типа: стандартного (основного), составного или типа указатель.

2.2 Двухсвязные линейные списки

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

Графическое представление двухсвязного списка

2.3 Кольцевой список

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

2.4 Стеки

Стек - частный случай однонаправленного линейного списка, для которого определены только две операции: добавление и удаление данных. Доступ к элементам в стеке представлен по принципу «последним пришёл - первым вышел». Можно привести хороший пример стека, это стопка тарелок, что бы взять вторую сверху тарелку нужно сначала поднять первую.

2.5 Очереди

Очередь - это линейная динамическая структура данных, для которой выполняется правило: добавление данных возможно только в конец структуры, а удаление только с начала. Доступ к элементам в очереди представлен по принципу «первым пришёл - первым вышел». Примером в реальной жизни может служить очередь к врачу.

2.6 Двусторонняя очередь

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

2.7 Очередь с приоритетом

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

2.8 Деревья

Деревья - это нелинейная динамическая структура данных, представленная в виде иерархии элементов, называемых узлами.

На самом верхнем уровне иерархии всегда имеется только один узел, называемый корнем узла. Каждый узел, кроме корневого, связан только с одним узлом более высокого уровня, называемым узлом-предком. Элементы дерева связываются с помощью ветвей (ребер) с одним или несколькими узлами более низкого уровня - дочерними узлами или потомками. Элементы, расположенные в конце ветвей и не имеющие дочерних узлов, называют листьями. От корня до любого узла существует только один путь. Максимальная длина пути от корня до листьев называется высотой дерева. Любой узел дерева с его потомками также образует дерево, называемое поддеревом. Число поддеревьев для данного узла образует степень узла. Максимальное значение среди степеней всех узлов определяет степень дерева.

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

Как правило, в дереве всегда задают какой-либо принцип упорядоченности, например, по возрастанию какого-то параметра (ключа). Таки образом, для каждого узла ключи наследников располагаются слева направо по возрастанию. То есть, в бинарном дереве для каждого узла значение ключа левого наследника будет меньше значения ключа узла, а значение ключа в узле меньше значения ключа в правом наследнике.

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

2.9 Линейные односвязные списки

Линейный список - это динамическая структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Эта структура данных предназначена для быстрой вставки элементов в определенное место.

Каждый элемент списка содержит поле данных (Data) (оно может иметь простую или сложную структуру) и поле ссылки на следующий элемент (next). Поле ссылки последнего элемента должно содержать пустой указатель (NULL).

Самый простой способ связать между собой множество элементов - сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным).

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

1) Сформировать структуры (расположить их в начале программы, что позволит изменять структуру с данными, не затрагивая при этом основную структуру List):

struct Data // структура, содержащая поля данных, необходимых для работы

struct List // структура, содержащая поле типа Data и поле с адресом последующего элемента next

Графически линейный список можно представить следующим образом:



2) В программе определить указатель на начало будущего списка:

List *u=NULL; // список пуст, указатель задан равным константе NULL

3) Выполнить заполнение списка:

Создание первого элемента:

u = new List; // выделение памяти под элемент

u->d.a=3; // заполнение поля с данными

u->next=NULL; // указатель на следующий элемент пуст

Создание пос...