Динамические структуры данных; списки: основные виды и способы реализации. Технологии программирования
Способы конструирования программ
Динамические структуры данных – сложные, организованные определенным образом данные, которые могут менять размер и/или свою структуру во время работы программы. Т
Типичными динамическими структурами являются массивы, стеки, очереди, списки, деревья. Универсальными способами организации таких структур является использование указателей.
Указатели – переменные, содержащие не сами данные, а адреса памяти.
Стек – линейная динамическая структура, у которой в каждый момент времени доступным является последний ее элемент. Стеки упорядочены, неоднородны (элементы стэка могут относиться к разным типам).
Previous – указатель на тип элемента stack
Массивы – последовательность упорядоченных, индексированных значений одного типа.
Количество элементов динамических массивов можно изменять во время работы.
| Stack Item | Queue Item | List Item |
| Data | Data | Data |
| Previous | Next | Pointes |
Описание динам. массива: TypeName = Array of BaseType
Очередь – линейная динамическая структура. Отличается от стэка тем, что при добавлении элемент помещается в конец очереди.
Список – линейная динамическая структура связанных элементов.
Для списка определены следующие операции:
Вставка элемента в список;
Удаление элемента из списка;
Перемещение элемента по списку;
Извлечение данных элемента списка;
Поиск элемента и сортировка (дополнительно).
|
|
|
Pointes – указатели для перемещения по списку.
Если каждый элемент имеет указатель на один соседний элемент, то список однонаправленный. Перемещение производится в одну сторону. Если на 2 элемента, то двунаправленный.
Списки представляют собой структуру последовательного доступа, так как в каждый момент времени доступен только текущий элемент. Для доступа к остальным необходимо последовательное перемещение по списку с помощью указателей на соседний элемент.
Для реализации двунаправленного списка элемент должен содержать данные data и указатели previous и next на предыдущий и последующий элемент соответственно. Перемещение по списку осуществляется простыми перемещениями указателя Current на предыдущий и последующий элемент.
В языках программирования (Pascal, C, др.) существует и другой способ выделения памяти под данные, который называется динамическим. В этом случае память под величины отводится во время выполнения программы. Такие величины будем называть динамическими. Раздел оперативной памяти, распределяемый статически, называется статической памятью; динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью).
|
|
|
Использование динамических величин предоставляет программисту ряд дополнительных возможностей. Во-первых, подключение динамической памяти позволяет увеличить объем обрабатываемых данных. Во-вторых, если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации. В-третьих, использование динамической памяти позволяет создавать структуры данных переменного размера.
Работа с динамическими величинами связана с использованием еще одного типа данных — ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.
Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.
Адрес величины — это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.
Далее будем более подробно обсуждать указатели и действия с ними в языке Pascal.
В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти — много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации.
|
|
|
Следует отчетливо понимать, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему — величина. Как это часто бывает, действует "закон сохранения неприятностей": выигрыш в памяти компенсируется проигрышем во времени.
Технология программирования - это совокупность методов и средств разработки (написания) программ и порядок применения этих методов и средств. Основные походы:
Операциональный подход. В эпоху ЭВМ 1 - го и 2-го поколений основным требованием к алгоритму была его узко понимаемая эффективность:
1) минимальные требования в отношении оперативной памяти компьютера - программа должна была использовать наименьшее возможное число ячеек оперативной памяти компьютера;
2) минимальное время исполнения (минимальное число операций). При этом программы составлялись из команд, непосредственно или почти непосредственно исполнявшихся компьютером (точнее говоря, процессором):
|
|
|
* операции присваивания;
* простейших арифметических операций;
* операций сравнения чисел;
* операторов безусловного и условных переходов (изменяющих порядок вычисления команд в программе);
* операторов вызова подпрограмм (вспомогательных алгоритмов).
Такой подход в программировании (создании алгоритмов), ориентированный на непосредственно выполняемые компьютером операции, можно назвать операциональным. Программа созданная в таком подходе малоэффективная. Много времени. Линейная.
Структурное программирование – это методология программирования, основанная на иерархическом решении задач. Основная цель – это дисциплинированность программирования. Принципы:
Принцип абстракции – рассмотрение решаемой задачи в целом, без учета деталей ее реализации.
Принцип нисходящего проектирования – исходная задача разбивается на несколько подзадач, которые разбиваются на еще более мелкие подзадачи до тех пор, пока алгоритм решения подзадач не станет легко реализуемым.
Принцип модульности – каждая из подзадач реализуется в отдельном модуле.
Модуль – независимая часть программы, которая может быть разработана, отлажена и откомпилирована отдельно от основной программы. Каждый модуль может ссылаться на другие модули. Количество используемых модулей называется размахом (шириной) модуля, который не должен превышать 7. Использование модулей имеет следующие преимущества:
1) возможность создания программы несколькими программистами;
2) простота проектирования и последующих модификаций программы;
3) упрощение отладки программы - поиска и устранения в ней ошибок;
4) возможность использования готовых библиотек наиболее употребительных модулей.
Стандарты СП:
разбивать программы на модули (задачииподзадачи),
использовать стандартные алгоритмические конструкции,
использовать значимые имени,
использовать префиксы для родственных имен.
не допускать вложенности условных конструкций (ифов) – не более трех,
не использовать выражения с неочевидной семантикой (смыслом).
Объектно-ориентированное программирование (ООП) - методология, которая основана на представлении программ в виде набора объектов отражающая части модели и определение способов взаимодействия между ними (парадигма программирования, в которой основными концепциями являются понятия объектов и классов). Цель методологии разработки программ: дисциплинированность программирования и эффективность разработки программ. Принципы ООП:
Принцип модульности – программа состоит из модулей, в каждом модуле реализованы объекты родственных классов, модули могут быть разработаны отдельно.
Инкапсуляция (encapsulation) заключается в объединении данных и методов обработки данных в одной структуре (объекте) и обеспечения скрытия данных и контролирования данных (доступ к своим данным контролирует сам объект).
Наследование (inheritance) – способность порождать новые классы объектов от уже существующих. Класс, от которого порождается новый, называется базовым классом или родительским или предок (ancestor).Порождаемый класс называется наследником или потомком (descendant).Потомок наследует все свойства и методы предка, а также может вводить свои новые свойства и методы или изменять родительские. В свою очередь от наследника могут порождаться новые классы. Причем от 1го класса могут быть порождены несколько наследников или от нескольких классов 1н наследник (множественное наследование).
Полиморфизм(polymorphism) – способность объектов разных, но родственных классов, выполнять одинаковые действия по-своему. Для решения задачи в рамках ООП должна быть разработана иерархия классов необходимых для реализации модели решаемой задачи.
Основные признаки (свойства) ООП:
- абстрагирование – это процесс выделения абстракции предметной области задачи. Это совокупность существующих характеристик некоторого объекта. Эти характеристики отличают его от других объектов.
- ограничение доступа – это сокрытие отдельных элементов абстракции.
- модульность – это принцип разработки программной системы предполагающей реализацию его отдельных частей модулей.
- иерархия – это ранжирование, упорядочение систем абстракции.
- типизация – ограничения, которые накладываются на свойства объекта и препятствующие взаимоотношению абстракции разных типов. Тип может связываться с объектом статически (раннее связывание на стадии компиляции) либо динамически (позднее связывание).
- параллелизм – это свойство нескольких объектов одновременно находящихся в активном состоянии и выполняют некоторые действия. В основном реализуют только в многопроцессорных машинах.
- устойчивость – это свойство абстракции существует во времени не зависимо от процесса, его породившего. Различают: * временные объекты (промежуточное); * локальные объекты (существуют только в том блоке, в котором описаны); * глобальные объекты (существует во время работы основной программы); * сохраненные в файлах;
Язык считается ООП, если в нем реализованы хотя бы 1-4 признака: С++, Паскаль с версии 5.5 и выше, Delphi и др.
Объект – сложная структура, включающая данные и действия над ними. Данные определяют свойства объекта (его внутреннее состояние). Действие определяет функциональность объекта, в том числе способы взаимодействия с другими объектами. Класс – это сложный структурированный тип данных, вкл. описания набора данных и методов их обработки, а также взаимодействия с другими классами. Переменная типа класс, это объект.
Таким образом в структурном программировании на 1е место поставлена логика выполнения решаемой задачи т.е логика алгоритма определяет структуру программы. В ООП на 1е место поставлена структура данных необходимых для решения задач т.е структура программы определена данными. На практике эти подходы сочетаются.
Дата добавления: 2020-01-07; просмотров: 500; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!