Навигация
Односвязный список на основе указателей
16711
знаков
0
таблиц
1
изображение
Содержание
Введение
1. Определение АТД
2. Общие положения
3. Описание операций
3.1 Операция добавления элемента
3.2 Операция добавления элемента после указанного
3.3 Операция удаления указанного элемента
3.4 Операция распечатки записей списка
4. Реализация АТД-список
4.1 Главная функция
4.2 Интерфейс
4.3 Реализация методов
Заключение
Список литературы
Приложение A: граф-схемы алгоритмов
Введение
Независимо от типа решаемых задач, любая программа оперирует какими-то данными, а сама программа предстваляет собой методы управления и обработки этих данных. Скорость выполнения программой поставленной задачи зависит не только от алгоритмов, использованных в ней для обработки и управления данными, но также и от самой организации данных. Таким образом, мы приходим к понятию о структурах данных.
Прямое взаимодействие между программой через пользователя и структурами данных оставляет открытыми множество данных, модификация которых нелегитимным способом (минуя интерфейс) может привести к нежелательным последствиям. Чтоб миновать данную проблему необходимо "возвести стены" между данными и программой, оставив лишь "окошко" в виде интерфейса. Для этого необходимо определить абстрактные типы данных, с помощью которых эти стены воздвигаются.
В данной работе разрабатывается абстрактный тип данных (АТД) – список, который впоследствии реализуется в виде связного списка, реализованного при помощи косвенной адресации, основанной на указателях. Более подробно вопросы разработки АТД рассматриваются в [3].
1. Определение АТД
Абстракция данных описывает, что можно делать с набором данных, игнорируя вопрос "каким образом это делается?". Абстракция данных – это способ разрабатывать отдельные компоненты программы, независимо от остальной ее части (остальных компонентов). Таким образом, абстракция данных – естественное расширение функциональной абстракции, позволяющей разрабатывать функции в относительной изоляции друг от друга. Набор данных в сочетании с совокупностью операций над ними называется абстрактным типом данных. Описание операций, входящих в АТД, должно быть достаточно строгим, чтоб точно указать их воздействие на данные. Но в нем не должен указываться способ хранения данных или детали выполнения операций. Конкретный способ хранения данных (структура данных) выбирается только при реализации АТД. Структура данных – конструкция, определенная в языке программирования для хранения набора данных. Согласно варианту задания, определены следующие данные:
1. Наименование микросхемы
2. Стоимость
3. Количество
Над ними определены следующие операции:
1.Добавление элемента в неупорядоченный список
2.Удаление элемента с заданным полем из неупорядоченного списка
3.Добавление элемента после указанного
4.Удаление всех элементов с заданным полем
5.Распечатка списка
Данный набор определяет множество допустимых операций над опеределенными в задании данными, т.е. нам задан абстрактный тип данных.
Далее будут рассмотрены каждая из операций в отдельности, определены их спецификации и предложены конкретные реализации.
2. Общие положения
Абстрактный список можно реализовать в виде массива – на первый взгляд, очевидный шаг. Массив имеет фиксированный размер (в большинстве языков программирования), в то время как длина абстрактного списка неограничена. Таким образом, структура данных становится статической, что является недостатком.
Другой существенный недостаток является продолжением достоинства массивов – последовательное расположение данных в смежных ячейках, иными словами, столь часто производимые, следовательно, требующие максимальной скорости выполнения, операции как вставка и удаления элемента приводят к необходимости сдвигать элементы массива, затрачивая дополнительное время.
Принцип реализации списка, не использующего сдиг элементов, основан на косвенной адресации. О других способах реализации абстарктных списков подробно рассказывается в [3].
Каждый узел связанного списка состоит из двух частей: непосредственно данных и указателя на следующий элемент – такой же узел или константу NULL.
Поскольку, согласно принципу инкапсуляции, доступ к данным должен осуществляться только посредством методов, определенных для этой цели, для данных определен спецификатор доступа private.
Механизм выделения памяти под элементы списка, основанного на указателях, предполагает динамическое выделение памяти при помощи операторов new и delete. Таким образом, при создании нового элемента имеет смысл выделять память только лишь под новые данные, а не под уже определенные методы – операции списка. Следовательно, необходимо вынести методы из структуры данных. В данной работе, была применена методика расширения интерфейса созданием структуры методов – дружественного класса, методы которого имеют доступ к закрытым членам класса узла.
Подробней о принципах объектно-ориентированного программирования можно узнать из [1, 3].
Указатели на голову и хвост списка объявлены в классе List поскольку по сути необходимы для реализации методов АТД, в то время как для самой структуры данных они не имеют ни малейшего смысла.
Методы, которые не должны никоим образом модифицировать данные, объявлены с использованием ключевого слова const.
Похожие работы
водить все действия, что и с обычными переменными. Для работы с динамическим распределением памяти очень удобно использовать связанные структуры данных, например односвязные списки. Простейшим примером списка является массив, в котором последовательно расположены все его элементы. Но у такого представления есть существенный недостаток – требуется заранее точно указать количество элементов ...
... подход к разработке эффективного алгоритма для решения любой задачи – изучить ее сущность. Довольно часто задачу можно сформулировать на языке теории множеств, относящейся к фундаментальным разделам математики. В этом случае алгоритм ее решения можно изложить в терминах основных операций над множествами. К таким задачам относятся и задачи информационного поиска, в которых решаются проблемы, ...
... данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами. Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве. Наконец, сортировка ...
... мощность (заменять процессоры), расширять емкость оперативной памяти, добавлять внешние устройства. Машины имеют большие наборы команд, развитое системное программное обеспечение, включающее трансляторы языков программирования Ассемблер, ФОРТРАН, ПЛ/1, КОБОЛ, АЛГОЛ, ПАСКАЛЬ, операционные системы с различными функциональными возможностями. Основная особенность управляющих вычислительных машин ...
0 комментариев