- •Вопрос 1) Основные структуры данных.
- •Вопрос 2) Массивы и их свойства.
- •Вопрос 3) Записи
- •Вопрос 4) Множества
- •Операции над множествами
- •Операции отношения.
- •Вопрос 5) Динамические структуры данных;
- •Вопрос 6) Линейные списки.
- •Вопрос 7) Циклические списки
- •Вопрос 8) Стек и его организация
- •Вопрос 9) Очереди и их организация
- •Вопрос 10) Задачи поиска в структурах данных.
- •Вопрос 11) Алгоритм линейного поиска.
- •Вопрос 12) Алгоритм бинарного поиска.
- •Вопрос 13) Алгоритм Кнута, Мориса- Пратта
- •Вопрос 14) Хэширование данных
- •Вопрос 15) сортировка данных
- •15. Сортировка данных
- •1) Сортировка включением
- •2) Сортировка Шелла
- •3) Обменная сортировка
- •4) Сортировка перемешиванием (Шейкерная сортировка)
- •5) Сортировка со слиянием
- •1) Прямое слияние
- •2) Естественное слияние
- •Вопрос 16) Пузырьковая сортировка.
- •17 Вопрос
- •Вопрос 18) Представление графов и деревьев
- •Вопрос 19) Представление бинарных деревьев.
- •Вопрос 20) Представление графов Способы представления графа в информатике Матрица смежности
- •Матрица инцидентности
- •Список рёбер
- •Вопрос 21) Алгоритмы на графах
- •Алгоритм Дейкстры нахождения кратчайшего пути
Вопрос 4) Множества
Наряду с массивами и записями существует еще один структурированный тип √ множество. Этот тип используется не так часто, хотя его применение в некоторых случаях является вполне оправданным.
Тип множество соответствует математическому понятию множества в смысле операций, которые допускаются над структурами такого типа. Множество допускает операции объединения множеств (+), пересечения множеств (*), разности множеств (-) и проверки элемента на принадлежность к множеству (in). Множества также как и массивы объединяют однотипные элементы. Поэтому в описании множества обязательно должен быть указан тип его элементов.
Var
RGB, YIQ, CMY : Set of string;
Здесь мы привели описание двух множеств, элементами которых являются строки. В отличие от массивов и записей здесь отсутствует возможность индексирования отдельных элементов.
CMY:= [▒M ▓,▓C ▓,▓Y ▓];
RGB:= [▒R▓,▓G▓,▓B▓];
YIQ:=[ ▒Y ▓,▓Q ▓,▓I ▓];
Writeln (▒Пересечение цветовых систем RGB и CMY ▓, RGB*CMY);
Writeln (▒Пересечение цветовых систем YIQ и CMY ▓,YIQ*CMY);
Операции выполняются по отношению ко всей совокупности элементов множества. Можно лишь добавить, исключить или выбрать элементы, выполняя допустимые операции.
Множества - это наборы однотипных логически связанных друг с другом объектов Описание типа множества
<имя_типа>=set of <базовый тип>
Операции над множествами
* пересечение множеств;
+ объединение множеств;
- разность множеств;
Операции отношения.
= проверка эквивалентности;
<> проверка неэквивалентности;
<= проверка вхождения;
in проверка принадлежности;
A=B, когда множества А и В совпадают
A<>B, множества А и В не совпадают
A<=B, все элементы А принадлежат В
A>=B, все элементы В принадлежат А
Вопрос 5) Динамические структуры данных;
Что такое динамические структуры? Да просто данные, размер которых может меняться во время работы программы. В Delphi есть массивы, которые так и называются динамическими, есть строки. TStream тоже можно так назвать, его размер легко изменить в любой момент. Все замечательно, и очень удобно для программиста. Вот только в современных компьютерах работа с памятью - одна из самых медленных операций, да еще и скорость работы память практически не зависит от частоты процессора. А изменение размера структуры, как правило, приводит к перераспределению памяти. Вот и получается, что изменение размера массива, например, весьма долгая операция.
В этой статье мне хочется рассказать о структуре, которая позволяет значительно ускорить операции со структурами изменяемых размеров.
Программисту очень часто приходится работать со строками, и иногда - с длинными строками. И часто мне приходится видеть примерно следующий код:
var
s: string;
ch: char;
i, N: integer;
begin
S:= '';
for i := 1 to N do
s := s + ch;
...
Вроде бы все хорошо. Но string в Delphi подразумевает использование динамической строки (ansistring, можно, правда, объявить переменную как ShortString или выключить опцию компилятора, но тогда длина строки ограничена 255 символами).