Обработка динамических структур

Министерство образования РФ Московский авиационный институт

(государственный технический университет)

филиал "Восход"

Кафедра МиПОИС

Отчет

по курсовой работе

"Обработка динамических структур"

по дисциплине: Программирование на языках высокого уровня

Студента гр. ДА 2-40 Воронцов О. В.

Байконур 2006г.

Аннотация

В данной курсовой работе представлена реализация программы, для обработки динамической структуры данных, содержащей сведения об авторах книг. Программа, разработанная в среде Turbo C++ 3.0, моделирует работу со структурой как с базой данных.

Содержание

Введение

1. Постановка задачи

2. Метод решения

2.1 Общая схема работы программы

2.2 Метод сортировки

3. Разработка алгоритмов решения задачи

3.1 Общая схема алгоритма

3.2 Стандартные процедуры и функции, используемые в программе

3.3 Описание работы пользовательских подпрограмм

3.3.1 Описание работы подпрограммы vvodSp

3.3.2 Описание работы подпрограммы loadIT

3.3.3 Описание работы подпрограммы sort

3.3.4 Описание работы подпрограммы vivodSp

3.3.5 Описание работы подпрограммы dobEl

3.3.6 Описание работы подпрограммы delel

3.3.7 Описание работы подпрограммы vidacha

3.3.8 Описание работы подпрограммы vozvrat

3.3.9 Описание работы подпрограммы saveIT

3.3.10 Описание работы основной программы

4. Руководство пользователя

5. Анализ результатов

Заключение

Список литературы

Приложения

Введение

В данном отчёте представлено решение задачи с помощью языка программирования С.

В первом разделе отчёта представлена постановка задачи. Второй раздел содержит метод решения программы. Третий раздел отчёта – алгоритм работы программы, включая алгоритм работы интерфейса программы и десяти основных подпрограмм. В четвёртом разделе рассматривается подробное руководство пользователя. Пятый раздел содержит анализ результатов. В листинге (приложение Д) представлен полный текст программы с комментариями.

1. Постановка задачи

Требуется сделать обработку картотеки библиотеки. Для этого следует:

а) Создать список (не менее 10 записей) со следующей структурой:

- фамилия и инициалы автора

- название книги

- год издания

- количество экземпляров данной книги в библиотеке

Использовать двусвязный список.

б) Реализовать следующие действия:

- Отсортировать список по фамилиям авторов книг методом простого обмена;

- Добавить в картотеку новую книгу, не нарушая алфавитный порядок;

- Удалить из картотеки книги заданного автора;

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

- По фамилии автора и названию книги возвратить книгу в библиотеку, отслеживая количество книг в обоих списках;

- Сохранить полученные списки в файл.

в) Действия со списком оформить в виде отдельных функций.

2. Методы решения задачи

2.1 Общая схема работы программы

Целесообразно для решения задачи использовать два списка. Первый список будет хранить информацию о книгах, хранящихся в библиотеке, а второй – о выданных на руки. Для этого будет произведено присваивание информационных полей первого списка второму, а затем поле записи количества книг во втором списке будет обнулено (так как в начале книг на руках нет). Уменьшение количества книг в одном списке будет сопровождаться увеличением во втором и наоборот. Например, после выдачи книги на руки счётчик количества экземпляров во втором списке увеличится на единицу, а в первом уменьшится на единицу. При выводе на печать второго списка следует оговорить, чтобы на экране появлялись только те книги, количество которых в этом списке больше нуля.

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

Так как требуется провести ряд действий со списком, то рационально организовать текстовое меню (его вид приведен в таблице 1.1). Меню будет представлено вертикально расположенными строками, каждая строка – отдельный пункт меню. Выбор пункта меню будет осуществляться путём введения с клавиатуры его порядкового номера. Для считывания введенного символа требуется зарезервировать переменную n, хранящую код нажатой клавиши. Выбор любого пункта меню будет активировать соответствующую функцию.

В процессе создания списка будут заполняться информационные поля каждого элемента. Информационные поля будут включать данные об авторе книги, её названии, годе издания и количестве экземпляров в библиотеке. Более подробно создание списка описано в пункте 3.3.1.

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

Пример выполнения меню Введите номер пункта для выполнения 1. Заполнить список 2. Загрузить списки из файлов 3. Отсортировать текущий список 4. Вывести текущий список 5. Вывести текущий список выданных на руки книг 6. Добавить новый элемент

7. Удалить из списка книги заданного автора

8. Выдать книгу на руки 9. Вернуть книгу в библиотеку 10. Сохранить списки в файл

11. Выход из программы

Ваш выбор:

2.2 Метод сортировки

Сортировка методом простого выбора – один из наиболее простых способов сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому списку. За каждый проход элементы последовательно будут сравниваться попарно и, в случае если последующий элемент меньше предыдущего (то есть порядок в паре неверный), будет выполняться обмен элементов. Проходы по списку будут повторяться до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает, что список отсортирован.

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

3. Разработка алгоритмов решения задачи

3.1 Схема работы программы

Считать номер n пункта меню:

1. Если n=1, вызвать функцию vvodSp. Формирование списка.

2. Если n=2, вызвать функцию loadIT. Считывание списков из файлов.

3. Если n=3 , вызвать функцию sort. Сортировка первого списка по фамилиям автора.

4. Если n=4, вызвать функцию vivodSp. Вывод первого (текущего) списка на печать.

5. Если n=5, вызвать функцию vivodSp. Вывод второго списка (выданных на руки книг) на печать.

6. Если n=6, вызвать функцию dobEl. Добавление нового элемента в конец списка и последующая сортировка по имени автора.

7. Если n=7, вызвать функцию delel. Удаление всех записей с введённой фамилией автора.

8. Если n=8, вызвать функцию vidacha. Добавление книги во второй список, удаление из первого.

9. Если n=9, вызвать функцию vozvrat. Удаление книги из второго списка, добавление в первый.

10. Если n=10, вызвать функцию saveIT. Запись данных первого и второго списков в файлы.

11. Если n=11, выполнить выход из программы.

Блок схемы основной программы и функций vvodSp, dobEl, delel представлены в приложениях соответственно А, Б, В, Г.

3.2 Стандартные процедуры и функции, используемые в программе

В процессе разработки программы были использованы стандартные модули языка программирования С: stdio.h, alloc.h, conio.h, string.h,.

Модуль stdio.h позволяет работать с потоками (строки, файлы…). Данный модуль включает такие необходимые функции как scanf(), printf(), gets(), puts(), и набор функций для работы с файлами.

Модуль alloc.h предназначен для работы с динамической памятью, в нем содержатся функции calloc(), malloc(), free() и константа NULL.

Модуль string.h предназначен для работы со строками, точнее строковым типом данных. В нем находятся функции для копирования, сравнения, склеивания, и поиска подстроки. В программе используются две стандартные функции этого модуля: strwr и strcmp. Первая преобразует строчные символы строки в прописные. Данная функция необходима для предотвращения ошибок ввода из-за восприимчивости программы к регистру. Функция strcmp(Строка1, Строка2) сравнивает строки Строка1 и Строка2, возвращает 0, если строки равны; число меньше нуля, если первая строка меньше второй; число больше нуля, если первая строка больше второй. Модуль conio.h предназначен для работы с экраном в текстовом режиме. В нем хранятся функции для очистки экрана, изменения цвета текста и фона, атрибутов текста, процедуры для буферизированного и небуферизированного ввода с клавиатуры.

3.3 Описание работы пользовательских подпрограмм

3.3.1 Описание работы подпрограммы vvodSp

Подпрограмма предназначена для формирования первого списка. Функция возвращает указатель на начало первого списка. Входной параметр – указатель на указатель на начало второго списка.

1. Обнулить указатели на начала и хвосты обоих списков.

2. Пока не будет введено "no" выполнять:

2.1 Динамически выделить память под указатель на текущий элемент.

2.2 Обнулить указатель на следующий за текущим элемент.

2.3 Присвоить указателю на предшествующий текущему элемент адрес предыдущего элемента.

2.4 Если указатель на начало списка обнулён, то присвоить вершине списка адрес текущего элемента, то есть текущий элемент становится вершиной.

2.5 Иначе, присвоить указателю на следующий за предыдущим элемент списка адрес текущего элемента.

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

Аналогичные действия проводятся со вторым списком. Далее:

2.7 Считать информационные поля элемента первого списка.

2.8 Приравнять информационные поля элементов первого списка к информационным полям второго.

2.9 Обнулить поле количества книг.

2.10 Считать значение s.

3. Вернуть указатель на начало первого списка.

Таблица 3.3.1-Локальные идентификаторы функции vvodSp

Идентификатор	Тип	Назначение
s	char	предназначена для ответа на вопрос: продолжать ли список
cur, cur2	el*	указатель на текущие элементы
tail, tail2	el*	указатель на хвосты списка
top	el*	указатель на начало первого списка
top2	el*	указатель на начало второго списка

3.3.2 Описание работы подпрограммы loadIT

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

Входные параметры функции – указатель на указатель на начало первого и второго списков.

1. Обнулить ссылки на хвосты и вершины обоих списков.

2. Открыть файлы "Base.txt" и "Out.txt" для чтения.

3. В цикле "пока не конец файла" динамически выделять память под указатель на текущий элемент.

3.1 Обнулить указатель на элемент, следующий за текущим.

3.2 Приравнять указатель на конец списка к указателю на предшествующий.

3.3 Если указатель на начало списка пустой, то присвоить ему адрес текущего элемента, текущий элемент становится началом списка.

3.4 Иначе присвоить адрес текущего элемента указателю на следующий за предыдущим.

3.5 Указатель на текущий элемент приравнять к последнему.

3.6 Произвести считывание списков из файлов.

4. Закрыть все файлы.

Таблица 3.3.2-Локальные идентификаторы функции loadIT

Идентификатор	Тип	Назначение
cur, cur2	el*	указатели на текущие элементы
pr	el*	указатель на предыдущий элемент списка
tail, tail2	el*	указатель на хвост первого и второго списков

3.3.3 Описание работы подпрограммы sort

Подпрограмма предназначена для сортировки списков по фамилии автора. Обращение к функции происходит и при добавлении нового элемента в список. Входной параметр функции – указатель на начало первого списка.

1. В цикле "пока не конец списка перейти к последующему элементу".

1.2 Если указатель на следующий элемент поля имени автора меньше текущего, то записать в дополнительную переменную dop адрес информационного поля текущего элемента.

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

1.4 Присвоить указателю на следующий элемент поля имени автора адрес вспомогательной переменной.

Таблица 3.3.3-Локальные идентификаторы функции sort

Идентификатор	Тип	Назначение
k	int	результат обмена (есть/нет)
cur	el*	указатель на текущий элемент
dop	book	вспомогательная переменная

3.3.4 Описание работы подпрограммы vivodSp

Подпрограмма обеспечивает вывод на печать текущего списка. При обращении к ней может вывести содержимое первого или второго списка. Входной параметр – указатель на текущий элемент списка.

В цикле "пока не конец списка", если информационное поле количества книг больше нуля, то распечатать текущий элемент и перейти к следующему.

3.3.5 Описание работы подпрограммы dobEl

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

1. В циклах "пока указатель на последующий элемент первого и второго списков не пустой"

1.2 Выделить динамически память под добавляемые элементы.

1.3 Считать информационные поля добавляемого элемента.

1.4 Приравнять информационные поля элементов первого списка к информационным полям второго.

1.5 Обнулить поле количества книг.

1.6 Для обоих списков обнулить указатель на следующий за добавляемым элемент.

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

1.8 Присвоить указателю на предыдущий элемент значение последнего элемента.

1.9 Присвоить адрес добавленного элемента последнему.

Таблица 3.3.4-Локальные идентификаторы функции dobEl

Идентификатор	Тип	Назначение
x, x2	el	новый элемент

3.3.6 Описание работы подпрограммы delel

Подпрограмма предназначена для удаления всех записей с введённой фамилией автора. Входные параметры – указатель на указатель на начало первого и второго списков.

1. В цикле "пока не конец файла":

1.1 Если информационное поле автора у элемента совпадает с введённым именем, то рассматриваются три случая.

1.1.1 Если удаляемый элемент стоит в начале списка, то присвоить указателю на начало списка указатель на следующий за ним элемент списка.

1.1.2 Обнулить ссылку на предыдущий элемент следующего элемента, то есть указатель новой вершины на предыдущий элемент.

1.1.3 Проделать аналогичные действия над вторым списком.

1.2.1 Если следующий элемент за текущим равен нулю, то удаляемый элемент находится в конце списка.

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

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

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

Таблица 3.3.5-Локальные идентификаторы функции delel

Идентификатор	Тип	Назначение
cur, cur2	el*	указатели на текущий элемент списка
n	int	результат поиска
isk	char	строка с фамилией автора

3.3.7 Описание работы подпрограммы vidacha

Подпрограмма предназначена для выдачи книги на руки, то есть для уменьшения количества книг в первом списке и увеличения во втором.

Входные параметры функции – указатели на текущие элементы первого и второго списков.

1. Считать фамилию автора и название книги.

2. В цикле "пока не конец списка"

2.1 Если фамилия автора и название книги совпадает с введёнными и количество книг больше 0, то:

2.1.1 Уменьшить на единицу значение количества в информационном поле первого списка

2.1.2 Увеличить на единицу значение количества в поле второго списка

3. Перейти к следующему элементу

Таблица 3.3.6-Локальные идентификаторы функции vidacha

Идентификатор	Тип	Назначение
iskA	char	строка с некоторым автором
iskN	char	строка с некоторой книгой
isk	char	записывает результат поиска
n	int	записывает результат поиска

3.3.8 Описание работы подпрограммы vozvrat

Подпрограмма обратная функции vidacha. Возвращает указанную книгу автора в библиотеку, то есть уменьшает количество книг во втором списке и увеличения в первом. Входные параметры функции – указатели на текущие элементы первого и второго списков.

1. Считать фамилию автора и название книги.

2. В цикле "пока не конец списка"

2.1 Если фамилия автора и название книги совпадает с введёнными и количество книг больше 0, то:

2.1.1 Уменьшить на единицу значение количества в поле второго списка.

2.1.2 Увеличить на единицу значение количества в поле первого списка.

3. Перейти к следующему элементу.

Таблица 3.3.7-Локальные идентификаторы функции vozvrat

Идентификатор	Тип	Назначение
iskA	char	строка с некоторым автором
iskN	char	строка с некоторой книгой
isk	char	записывает результат поиска
n	int	записывает результат поиска

3.3.9 Описание работы подпрограммы saveIT

Подпрограмма предназначена для записи данных первого и второго списков в файлы. Входные параметры – указатели на текущий элемент первого и второго списков.

1. Открыть файлы для чтения.

2. В цикле "пока не конец списка" произвести запись данных текущего элемента в файл для обоих списков.

3. Перейти к следующему элементу списка.

Таблица 3.3.8-Локальные идентификаторы функции saveIT

Идентификатор	Тип	Назначение
zap, zap2	book	вспомогательная переменная
f1, f2	FILE	переменная связанная с файлами