Понятие «список» имеет такое же большое значение в вычислениях, как понятие «множество» в математике. Любой вычислительный процесс может быть представлен и описан с помощью операций над списками.
Пустым списком называется последовательность, не содержащая элементов (обозначается Ø или ()).
Последовательность элементов, представляющую список, можно рассматривать как упорядоченную слева направо, так и упорядоченную справа налево. Элемент A в некотором списке отличается от одноэлементного списка (A), содержащего такой же элемент.
Операция «+» позволяет добавить элемент A к списку t справа A + t (ДобавитьСправа(t,A)) или слева t + A (ДобавитьСлева(t,A)).
Операция Элементов(t) возвращает число элементов в списке t.
Первый элемент A некоторого непустого списка t записывается как
A = Голова(t), t <> Ø,
если последовательность рассматривается как упорядоченная слева направо, и как
A = ГоловаСправа( t ), t <> Ø,
если последовательность рассматривается как упорядоченная справа налево.
Непустой список t с удаленным первым элементом записывается как Хвост(t), если последовательность рассматривается как упорядоченная слева направо, и как ХвостСправа(t), если последовательность рассматривается как упорядоченная справа налево.
Операция Опустошить(t) опустошает список t.
Операция t||f (Соединить(t,f)) присоединяет содержимое списка f к списку t справа.
1. Реализовать абстрактный тип данных Список целых чисел, в соответствии с приведенной ниже спецификацией.
2. Оттестировать каждую операцию, определенную на типе данных одним из методов тестирования.
3. Оттестировать тип данных в целом.
4. Разработать приложение под Windows для демонстрации выполненного абстрактного типа данных.
Для описания ADT на логическом уровне используется формат, который включает заголовок с именем ADT, описание объекта типа данных и список операций. Для каждой операции определяются входные (Вход) значения, предоставляемые клиентом, (Предусловия), требования к исходным данным, в случае истинности которых операция может быть выполнена, и процесс обработки данных (Процесс), который выполняется операцией. После выполнения операции определяются выходные значения (Выход), которые возвращаются клиенту, и постусловия (Постусловия), указывающие на любые изменения данных.
ADT List
Данные
Списки - это изменяемые неограниченные последовательности целых чисел. Они изменяются операциями: «Опустошить», «ДобавитьСлева», «ДобавитьСправа», «Голова», «ГоловаСправа», «Хвост», «ХвостСправа», «Соединить».
Таблица 1. Описание операций для ADT List.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.