Содержание

Введение

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. Общие положения

Абстрактный список можно реализовать в виде массива – на первый взгляд, очевидный шаг. ............