Теоретическая часть

Содержание

Введение …………………………………………………………………… 3

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

Использование программы……………………………………….4

Раздел 1. Теоретическая часть……………………………………….……5

Раздел 2. Алгоритмическая част…………………………………………..7

2.1 Создание списка………………………………………………….7

2.2 Добавление элемента в список………………………………….7

2.3 Удаление …………………………………………………………8

2.4 Просмотр списка…………………………………………………9

2.5 Синтаксический анализатор…………………………………….10

Раздел 3 Техническое задание…………………………………………….11

Раздел 4 …………………………………………………………………….13

4.1 Описание программы ………………………………………….13

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

Вывод ………………………………………………………………………15

Список использованной литературы ………………………………….16

Приложение А ……………………………………………………………..17

Приложение Б ……………………………………………………………...29

Введение

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

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

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

При помощи среды визуального проектирования Delphi создать программу-оболочку для управления структурой данных "список". Реализовать операции создания списка, просмотра содержимого списка, удаление списка, добавления элемента в список, удаление заданного элемента из списка, поиска в списке по заданному полю. Также реализовать встроенный в программу синтаксический анализатор, при помощи которого производить вывод на экран искомого множества элементов списка (синтаксический анализатор должен работать как минимум по трем полям и использовать как минимум три булевых оператора).

Создать линейный двунаправленный неупорядоченный список.

Элемент списка – принтер;

1. тип;

2. качество;

3. фирма изготовитель;

4.название;

Осуществить поиск по:

1. названию;

2. фирме изготовителю;

3. качеству

Использование программы:

a) можно составить базу данных содержащую сведенья о принтерах;

b) можно исправить уже имеющуюся базу данных;

c) можно просмотреть все сведенья о принтерах, содержащихся в базе данных;

d) можно осуществить поиск принтеров по заданным параметрам.

Раздел 1

Теоретическая часть

Классический пример структуры данных последовательного доступа, в которой можно удалять и добавлять элементы в середине структуры, -- это линейный список. Различают однонаправленный и двунаправленный списки (иногда говорят односвязный и двусвязный).

Элементы списка как бы выстроены в цепочку друг за другом. У списка есть начало и конец. Имеется также указатель списка, который располагается между элементами. Если мысленно вообразить, что соседние элементы списка связаны между собой веревкой, то указатель -- это ленточка, которая вешается на веревку. В любой момент времени в списке доступны лишь два элемента -- элементы до указателя и за указателем. (рис. 1.1)

Рис. 1.1- Структура однонаправленного списка

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

Рис. 1.2 – Структура двунаправленного списка

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

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

-указатель списка, содержащий адрес первого и последнего элементов;

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

Раздел 2

Дата добавления: 2015-11-04