Реализация линейного списка в типизированном файле

Рисунок 5.8 – Процедура добавления нового элемента в упорядоченный список в файле

7. Поиск элемента в отсортированном списке

 

Процедура поиска элемента в отсортированном  списке, реализованном в файле  имеет следующие параметры:

1. Файловая переменная (по ссылке);
2. Адрес первого элемента списка (по значению);
3. Ключ поиска (по значению);
4. Указатель (номер записи) на найденный и предыжущий к найденному (по ссылке, так как это результат выполнения процедуры);
5. Признак того, найден реально элемент или нет (по ссылке и имеет тип Boolean);

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

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

Результат поиска – найден элемент  или не найден находится в специальной  переменной типа Boolean.

Данная процедура имеет такой  же алгоритм, как и процедура поиска для «кучи», описанный в лабораторной работе №2.

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

8. Удаление элемента из отсортированного  списка

 

Процедура удаления получает следующие параметры:

1. Файловая переменная (по ссылке);
2. Адрес первого элемента (по ссылке, так как при удалении первого элемента адрес начала списка уже будет изменен);
3. Ключ удаляемого элемента.

При удаленнии элемента может использоваться процедура поиска, описанная в п.5.3.7.

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

Алгоритм процедуры удаления:

1. Поиск элемента по ключу в списке;
2. Извлечение элемента из списка (здесь выполняется проверка – удаляется первый элемент или нет, и в зависимости от этого выполняются действия по извлечению элемента из списка);
3. Знесение свободной записи, оставшейся после удаления элемента в список дыр с помощью вызова процедуры, описанной в пункте 5.3.5.

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

9. Удаление списка

 

Если в файле находится один список, то можно удалить файл и  заново выполнить инииализацию списка.

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

Процедуру удаления реализуйте самстоятельно.

4. Создание проекта, который обеспечивает создание и обработку списка, расположенного в типизированном файле

1. Задача, решаемая проектом

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

2. Интерфейс проекта

 

Главная форма проекта представлена на рисунке 5.9. Для вывода подсписоков мультисписка используются компоненты ListBox.

Рисунок 5.9 – Изображение главной формы проекта

3. Описание типов для проекта

 

Проект имеет такую же структуру, как и во 2-й лабораторной работе.

Содержимое модуля типов представлено на рисунке 5.10.

Рисунок 5.10 – Содержимое модуля типов

 

4. Реализации операции добавления нового элемента в упорядоченный список в файле

 

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

 Рисунок 5.11 – Процедура, обрабатывающая событие нажатия на кнопку «Добавить» на форме ввода данных

5.5 Задания для выполнения проекта

Создайте проект, который выполняет  обработку списка элементов, а именно производит добавление элемента в список, расположенный в типизированном файле, как это показано в п.5.3.

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

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

 

Таблица 5.2 – Задания для выполнения проекта

Вариант	Содержимое элемента Списка	Реализовать операцию со списком:
0	Целое число	Реализовать операцию создания копии списка 2.Удалить из списка все четные элементы
1	- номер аудитории - кафедра -количество компьютеров	1. Реализовать операцию сохранения и восстановления списка из типизированного файла 2. Создать второй список, в котором  будут только записи об аудториях  кафедры ИКС
2	- фамилия спортсмена - разряд - вид спорта	1. Реализовать операцию удаления  элемента с дубликатами из  отсортированного списка 2. Удалить спортсменов, которые  занимаются плаваньем
3	- название книги - цена - тираж	1. Реализовать операцию слияния  двух отсортированных списков 2. Удалить  книги, перед которыми  в списке находится книга с  тирадом больше 50000 экземпляров.
4	- название блюда - количество калорий - страна	1.Реализовать операцию инвертирования  списка 2. Удалить записи о тех блюдах, перед которыми находится блюдо страны Испания
5	- название магазина - количество рботников	1. Реализовать операцию удаления  элемента и его дубликатов  из неупорядоченного списка 2. Создать второй список, в котором будет хранится информация о магазинах, где количество работников меньше 30
6	Целое число	1.Реализовать операцию создания копии списка 2. Перед каждым элементом, равным 0, вставить в список новый элемент со значением 2.
7	Строка	1.Реализовать операцию удаления  элемента с дубликатами из  отсортированного списка 2. После каждой строки, которая имеет длину больше 3-х символов, вставить элемент со строкой «***»
8	- номер школы - директор - количество учителей	1.Реализовать операцию инвертирования  списка 2. Удалить информацию из списка о тех школах, где количество учителей меньше 40
9	Целое число	1.Реализовать операцию слияния  двух отсортированных списков 2.После каждого четного элемента  вставить новый, который равен  сумме двух предыдущих элементов  списка.

5.6 Тестирование проекта

Выполните тестирование проекта следующим образом:

1. В таблице разместите значения элементов, добавленных в список.
2. Выполните задание 1, согласно варианта, вручную и изобразите его результат в отчете;
3. Выполните задание 1 при помощи проекта и изображение интерфейса с результатом выполнения поместите в отчет.
4. Аналогично выполните тестирование второго задания.

7. Содержание отчета

1. Наименование работы.

2. Цель работы.

3. Изображение интерфейса проекта, реализованного согласно задания.

4. Текст программы.

5. Результаты тестирования проекта.

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

8. Контрольные вопросы и задания

1. Знать алгоритм и уметь написать любую из описанных в данной работе процедур обработки списка;
2. Рассказать об основных особенностях реализации списка в типизированном файле;
3. В чем состоит инициализация списка в типизированном файле.
4. Какие дополнительные процедуры необходимо реализовать при создании и обработке списка в файле по сравнению с обработкой списка в «куче»;
5. Что содержит поле Next каждого элемента списка в файле.
6. Что такое «дыра»?
7. Как организованы «дыры» в файле;
8. Как узнать адрес первого элемента списка, если он реализован в типизированном файле?
9. Где может размещаться новый элемент в файле?
10. Опишите алгоритм процедуры поиска свободного места в типизированном файле для нового элемента списка.