Динамическая структура данных - Курсовая работа

Часто в процессе работы с данными невозможно определить, сколько памяти потребуется для их хранения, память следует распределять во время выполнения программы по мере необходимости отдельными блоками. Такой способ организации данных называется динамической структурой данных, поскольку она размещается в динамической памяти и ее размер изменяется во время выполнения программы.Абстракция подразумевает разделение и независимое рассмотрение интерфейса и реализации. В линейном списке каждый элемент связан со следующим и, возможно, с предыдущим. В первом случае список называется односвязным, во втором - двусвязным. В качестве ключа в процессе работы со списком могут выступать разные части поля данных. Над списками можно выполнять следующие операции: · начальное формирование списка (создание первого элемента);По определению авторитета в области объектно-ориентированных методов разработки программ ГРАДИБУЧА «объектно-ориентированное программирование (ООП) - это методология программирования, которая основана на представлении программы в виде совокупности объектов, каждый из которых является реализацией определенного класса (типа особого вида), а классы образуют иерархию на принципах наследуемости» [1]. Гради Буч выделяет две разновидности декомпозиции: алгоритмическую (так он называет декомпозицию, поддерживаемую структурными методами) и объектно-ориентированную, отличие которых состоит, по его мнению, в следующем: «Разделение по алгоритмам концентрирует внимание на порядке происходящих событий, а разделение по объектам придает особое значение факторам, либо вызывающим действия, либо являющимся объектами приложения этих действий» [2]. Класс - описание (абстракция), которое показывает, как построить существующую во времени и пространстве переменную этого класса, называемую объектом. Поведение выражает динамику изменения состояний объекта и его реакцию на поступающие сообщения, т.е. как объект изменяет свои состояния и взаимодействует с другими объектами [5]. Идентификация (распознавание) объекта - это свойство, которое позволяет отличить объект от других объектов того же или других классов.Программа представлена двумя классами и основным cpp-файлом, содержащим пользовательский интерфейс для удобства работы со списками. Класс c List представляет собой линейный односвязный список, состоящий из объектов класса c Element. Поле data типа int содержит числовое значение элемента списка, поле next типа c Element* - ссылку на следующий элемент списка. Дело в том что, при выполнении любой из вышеуказанных операций, происходит перебор элементов списка, чтобы дойти до нужного, так как список не имеет произвольного доступа к элементам, поэтому перебор рациональней начинать с "головы" списка. Для печати важно знать начало списка, чтобы последовательно распечатать значения всех элементов списка, поэтому в переменную темрустанавливается ссылка на "голову" списка, после чего проверяется факт существования списка и выводится соответствующие сообщение, если он не подтверждается, если же список не пуст, то он выводится на экран: void CLIST::Print()Часто в процессе работы возникают ситуации, связанные с некорректным вводом данных, что может вызвать выход из строя программы. Разумеется, в каждой программе должны быть реализованы алгоритмы защиты от неопытного пользователя, предостерегающие программу от сбоя. Первоначальный ввод списка реализуется представленным ниже кодом: cout<<"Enter the list elements (enter "stop" to complete the input):"<<endl; Таким образом, при вводе будут игнорироваться любые строки не являющиеся числами, кроме строки с командой остановки ввода (см. рисунок 10).В данной работе были получены понятия об абстрактные типах данных, о принципах их представления в современных языках программирования, в С в частности. В большинстве современных императивных языков основной концепцией, используемой для описания абстракций в программном коде, является объектно-ориентированный подход. Модули - это компоненты программы, которые имеют два важных свойства: Модули скрывают в себе детали реализации.

Содержание

Введение

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

1.1 Абстрактные типы данных. Линейные списки

1.2 Понятие объектно-ориентированного программирования

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

3. Тестирование

Заключение

Приложение

программирование абстрактный линейный алгоритм

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

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

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

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

В данной работе были получены понятия об абстрактные типах данных, о принципах их представления в современных языках программирования, в С в частности. В большинстве современных императивных языков основной концепцией, используемой для описания абстракций в программном коде, является объектно-ориентированный подход. Объектно-ориентированное программирование (ООП) также, как и подход к программированию на основе АТД, является, в некоторой степени, развитием идей о модульном программировании. Модули - это компоненты программы, которые имеют два важных свойства: Модули скрывают в себе детали реализации.

Модули могут быть повторно использованы в различных частях программы.

Дэвид Парнас в своей работе 1972 года, представлял модули как абстрактные машины, хранящие внутри себя состояния и позволяющие изменять это состояние посредством определенного набора операций. Эта концепция является базовой, как для концепции абстрактных типов данных, так и для объектно-ориентированного программирования. Проведя параллели между работой Парнаса и современных понятиях ООП, нетрудно заметить взаимосвязь понятий класс и модуль.

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