Method (1015691), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Правила подготовки исходных данных могут быть пояснены с помощью примера подготовки данных, но не могут сводится только к этому примеру.

4.7. Выходные данные

Указываются «характер и организация выходных данных, формат, описание и способ кодирования выходных данных». Описание должно позволять разобраться в результатах работы программы без изучения ее алгоритма.

Примечание: допускается, в случае необходимости, объединять некоторые разделы или вводить дополнительные разделы.

23

5. ПРИМЕР ОПИСАНИЯ ПРОГРАММЫ

Рассмотрим следующую постановку задачи. Двунаправленный кольцевой список размещается в двух массивах. Массив VALUES содержит значения элементов списка. Каждое значение задается последовательностью из 3 целых чисел. Массив INFO содержит справочные части элементов списка, т. е. индексы соответствующих значений в массиве VALUES и ссылки на справочные части предыдущих и следующих элементов списка в массиве INFO.

Написать программу на языке С, реализующую следующие действия со списком заданной организации:

1) печать списка;

2) добавление нового элемента в конец списка;

3) удаление из списка заданного элемента;

4) перестановка N-го и (N+l)-ro элементов;

5) поиск индекса заданного элемента списка в массиве VALUES;

6) сборка мусора.

Ведение списка свободных элементов и использование ранее занятых, но уже освобождённых участков памяти для размещения новых элементов не допускается. Новый элемент может быть добавлен только в конец списка при наличии свободной памяти. Если таковой не окажется, необходимо осуществить «сборку мусора».

Текст описания программы следует ниже.

5.1. Общие сведения

Программа имеет имя LIST, написана на языке С для операционной системы MS DOS версии 6.2 и выше. Для функционирования программы необходим один из компиляторов языка C/C++ (например, Borland C++ версии 4.5).

5.2. Функциональное назначение

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

Обрабатываемый список в каждый момент времени может содержать не более LEN элементов, каждый из которых представлен последовательностью из NUM целых чисел. Значения символических констант LEN и NUM могут модифицироваться в тексте программы с обязательной последующей её перекомпиляцией.

24

Для этого необходимо скорректировать директивы препроцессора ^define LEN значение ^define NUM значение в заголовочном файле list.h. По умолчанию LEN = NUM = 3.

В качестве компонентов элементов списка могут использоваться не более чем шестизначные целые числа (включая знак минус для отрицательных чисел).

5.3. Описание логической структуры 5.3.1. Структура программы

Программа состоит из главной функции Main, поддерживающей диалоговый интерфейс пользователя при работе со списком, набора функций, реализующих основные операции над списком: Add, Del, Change, Findindex, Print, Defrag и функций вспомогательного характера Getact и Valcpy.

Для размещения двунаправленного кольцевого списка в программе определены массивы values и info. Массив values содержит значения элементов списка, а массив info справочные части списка.

Описания массивов имеет вид

value values[LEN];

informat info [LEN];

LEN - символическая константа, задающая максимальное количество элементов списка.

Два новых типа данных value и informat созданы для удобства представления списка заданной организации. Тип данных value используется для представления значения элемента списка в виде последовательности из NUM целых чисел.

Определение типа value имеет следующий вид typedef int value [NUM];

NUM - символическая константа, задающая количество целых чисел в последовательности, представляющей значение элемента списка.

Тип данных informat используется для представления справочной части каждого элемента списка, которая содержит два числа:

1) индекс в массиве info справочной части предыдущего элемента списка;

2) индекс в массиве info справочной части следующего элемента списка. Следует иметь в виду, что, поскольку список кольцевой, предыдущим

для первого элемента списка является последний, а следующим для

последнего - первый.

25

Определение типа informat имеет следующий вид •

typedef struct {intpprev, pnext;} informat;

Для описания состояния списка используются следующие переменные:

int pfirst, plast, amount;

pfirst - индекс первого элемента списка в массивах values, info;

plast - индекс последнего элемента списка в массивах values, info;

amount - количество элементов списка.

Массивы values и info, а также переменные pfirst, plast и amount опреде­ляются как глобальные и не передаются функциям программы в качестве параметров.

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

Заголовочный файл list.h содержит описание новых типов value и infor­mat; описание глобальных переменных values, info, pfirst и amount; прототи­пы всех функций программы; директивы препроцессора #define, определяю­щие символические константы LEN и NUM, а также директивы ^include для подключения необходимых стандартных функций языка С. Этот файл вклю­чается в файлы - потребители для обеспечения доступа к внешним объектам.

5.3.2. Алгоритм

Программа, функционируя в интерактивном режиме, позволяет пользо­вателю выбрать одно из возможных действий, используя меню вида

1 - ОЧИСТИТЬ 2 - ДОБАВИТЬ 3 - УДАЛИТЬ 4 - ПЕРЕСТАВИТЬ 5 - НАЙТИ 6 - ВЫВЕСТИ НА ЭКРАН

7 - ЗАВЕРШИТЬ

8 ответ на приглашение к вводу нужно задать номер выбранного дейст­вия. После распознавания действия следует запрос на необходимые данные и вызывается функция, реализующая это действие. Блок - схема программы приведена на рис 5.1.

5.3.3. Функция Add

Предназначена для добавления элемента в конец списка. Выполняет следующие действия :

- если количество элементов списка amount равно LEN (максимальному

26

Рис. 5.1

количеству элементов списка), то на экран монитора выводит сообщение:

« ДОБАВЛЕНИЕ НЕВОЗМОЖНО - НЕТ СВОБОДНОЙ ПАМЯТИ »,

и состояние списка не изменяется ;

- если достигнут конец массива (т.е. plast равно LEN " 1), но количество элементов списка amount меньше максимального значения LEN, то вызывает функцию Defrag, осуществляющую «сборку мусора»;

- значение добавляемого элемента записывает на свободное место в массив values, а его справочную часть - на свободное место в массив info. После этого корректирует справочные части предыдущего и первого элементов списка, а значение переменных plast и amount увеличивает на единицу.

Прототип (описание) функции имеет вид

int Add (value val);

Таблица 5.1

Формальные аргументы функции Add

Функция использует глобальные переменные values, info, pfirst, plast, amount и функцию Defrag.

Функция возвращает значение (-1), если добавление элемента в конец списка невозможно, и 0 - при удачном завершении своей работы.

Функция содержит 20 строк текста, находящегося в файле. Add.c и занимает около 1 Кбайта памяти.

5.3.4. Функция Defrag

Предназначена для «сборки мусора», т.е. перемещения элементов списка к началу массивов values и info с тем, чтобы собрать неиспользуемую в результате удаления элементов память в конце этих массивов. Такая стратегия использования памяти позволяет быстро удалять и размещать новые элементы до тех пор, пока не исчерпается свободная память в конце массивов values и info, причем место, занимаемое удаленными из списка

28

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

1) если первый элемент списка находится не в начале массивов values и info, то переставляем его значение в первый элемент массива values (т.е. в values[0]), корректируя соответствующим образом справочные части первого, второго и последнего элементов списка ;

2) переходим к следующему элементу списка ;

3) если текущий (i - и) элемент не расположен в памяти сразу вслед за предыдущим ((i - 1) - м)), то переставляем его значение на место, следующее непосредственно за предыдущим, корректируя соответствующим образом справочные части (i - 1) - го, i - го и (i + 1) - го элементов списка ;

4) если текущий элемент не последний, то переходим к п. 2, иначе -выход.

Прототип функции имеет вид :

void Defrag (void);

Функция использует глобальные переменные values, info, pfirst, plast, amount и функцию Valcpy для копирования значения элемента списка.

Функция содержит 30 строк текста, находящегося в файле Defrag.c и занимает около 1,5 Кбайт памяти.

5.3.5. Функция Del

Предназначена для удаления из списка элемента с номером nel. Выполняет следующие действия :

- если номер элемента списка меньше единицы или больше количества элементов списка на экран монитора выводит сообщение :

« УДАЛЕНИЕ NNNNN ЭЛЕМЕНТА НЕВОЗМОЖНО »,

где NNNNN - номер элемента списка;

- определяет индекс элемента списка с номером nel в массивах values и info (для этого вызывается вспомогательная функция Findindex);

- корректирует соответствующие справочные части у предыдущего и последующего элементов ;

- в случае удаления первого, последнего или единственного элемента списка корректирует соответствующие указатели на первый, последний элемент, или на тот и другой одновременно ;

- значение переменной amount уменьшает на единицу.

29

Прототип функции имеет вид

int Del (int nel);

Таблица 5.2

Формальные аргументы функции Del

Функция использует глобальные переменные values, info, pfirst, plast, amount и функцию Findindex.

Функция возвращает значение (-1), если удаление элемента из списка невозможно, и 0 - при удачном завершении своей работы.

Функция содержит 15 строк текста, находящегося в файле Del.c и занимает около 1 Кбайта памяти.

5.3.6. Функция Change

Предназначена для перестановки соседних (N-го и (N+l)-ro) элементов списка.

Выполняет следующие действия:

- если номер элемента списка меньше 1 или больше количества элементов списка, то на экран выдает сообщение:

"ПЕРЕСТАНОВКА NNNNN ЭЛЕМЕНТА НЕВОЗМОЖНА",

где NNNNN номер элемента списка;

- определяет индекс р элемента списка с номером nel в массивах values и info (для этого вызывается вспомогательная функция Findindex, возвращающая указатель на искомый элемент);

- меняет местами элементы массива values с индексами р и р+1 (для этого вызывается вспомогательная функция Valcpy копирования значения элемента списка); корректировка справочной информации в массиве info не требуется.

Прототип функции имеет вид

int Change (int nel);

30

Таблица 5.3

Формальные аргументы функции Change

Функция использует глобальные переменные values и info и функцию Valcpy.

Функция возвращает значение (-1), если перестановка элементов невозможна, и 0 - при удачном завершении своей работы.

Функция содержит 12 строк текста, содержащегося в файле Change.c и занимает около 1 Кбайта памяти.

5.3.7. Функция Print

Предназначена для вывода на экран монитора списка элементов в форме, приведенной в подразд. 5.7.

Прототип функции имеет вид

Характеристики

Список файлов книги