- •Внутреннее представление данных
- •1) Представление чисел
- •2) Представление текстовых данных.
- •3) Представление мультимедийной информации
- •2. Основные этапы обработки программ пользователя.
- •Средства записи алгоритмов. Виды алгоритмов
- •4. Основные этапы решения задачи на компьютере.
- •Структура программы на языке Паскаль
- •6. Идентификаторы, числа, строки, выражения .
- •Операторы ввода/вывода данных
- •8. Числовые типы данных .
- •Полезные функции
- •Логические операции над битами
- •Символьный тип данных
- •10. Логический тип данных (Boolean) .
- •11.Перечисляемый и ограниченный типы.
- •Функция succ(X)
- •Функция pred(X)
- •Функция ord(X)
- •12. Раздел описания типов и констант . Типизированные константы.
- •Оператор присваивания, составной и условные операторы
- •Составной оператор
- •Оператор if-else
- •14. Операторы цикла.
- •Циклы включают в себя
- •Цикл for
- •Итерационные циклы Цикл while
- •Цикл repeat
- •16. Оператор выбора.
- •Массивы и переменные с индексами
- •18. Сортировка массивов.
- •Метод "пузырька"
- •Сортировка вставками
- •Строковые типы данных.
- •20. Приведение типов в Паскале.
- •Правила работы с типами данных
- •Пример задачи, где используется явное преобразование типов
- •21. Тип множество (Set).
- •23. Файловые типы данных
- •Классификация файлов в tp
- •24. Типизированные файлы. Создание и просмотр файлов.
- •25. Корректировка и дозапись компонент в типизированных файлах.
- •26. Текстовые файлы.
- •27. Корректировка и дозапись информации в текстовый файл.
- •28.Описание и вызов процедур в Паскале.
- •Параметры-значения, параметры-переменные
- •29. Описание и вызов функций в Паскале.
- •30.Область действия переменных при использовании подпрограмм.
- •31.Способы передачи параметров в подпрограммы.
- •32.Рекурсивное описание процедур и функций.
- •Существует два вида рекурсий:
- •33. Динамические типы данных. Простейшие действия с указателями.
- •34.Создание и обработка динамических списков
- •35. Создание и обработка стеков.
- •36.Создание и обработка очередей.
- •37. Создание и использование таблиц.
- •40.Буферизированный и небуферизированный ввод данных.
37. Создание и использование таблиц.
Таблицы описываются так же, как и списки, только в записи может присутствовать несколько полей.
Виды таблиц:
1.Таблицы – списки
Type p_tabl=^elem;
elem=record
next:p_tabl;
k:integer;
inf: …; {может быть любого типа, в том числе и указателем}
end;
Var p: p_tabl;
nil
kn
infn
K1
K2
Inf2
Inf1
2.Таблицы-массивы
K3
K1
K2
Kn
…
Type inform=record
Inf1
Inf2
Inf3
infn
…
End;
Point=^inform;
Str_tabl=record
K:byte;
P:point;
End;
Mas=array [1..n] of str_tabl;
Var tabl:mas;
38. Нелинейные динамические структуры. Деревья.
1. Двунаправленные списки
Двусвязным (двунаправленным) списком называется структура, состоящая из записей, в которых в первом поле хранится указатель на предыдущую запись (элемент списка), во втором – переменная, а в третьем указатель на следующую запись (элемент списка).
Работать с двусвязными списками намного проще чем с односвязными, так как мы можем двигаться по списку и слева направо (из начала в конец), и справа налево (из конца в начало). Но при этом мы должны будем запомнить и хранить уже два указателя: r – на начало списка и q – на конец списка.
Type point=^list;
List=record
X:byte;
Next, prev:point;
End;
2.Структура текста, разбитого на слова.
3.Двоичное дерево
можно представить так:
4.Направленный граф
можно представить так:
2. Текст – это связанная структура. Ее элементы представляют собой записи с тремя полями: первое поле содержит текстовую информацию (например, слово), второе поле либо указывает на первый элемент следующей строки, либо имеет значение Nil, третье – на следующий элемент данной строки.
3. Компонента двоичного дерева имеет также три поля: первое поле содержит основную информацию (число, символ, слово и т.д.), а второе и третье поля содержат ссылки на предыдущую и последующую компоненты дерева. Для некоторых компонентов дерева одно из этих полей либо оба имеют значение Nil.
4. Посредством ссылок можно выразить все связи в структуре, моделирующей направленный граф: вершинам графа соответствуют сами динамические переменные, а ребрам – ссылки.
Узломназывают переменную, содержащую два различных, отличных отNil, значения указателя. Так, узловые элементы текста содержат ссылки на очередной элемент данной строки и на первый элемент следующей строки.
Нелинейные структуры удобны для задач поиска. Список упорядоченных элементов в виде двоичного дерева:
Узел 4 называется корнем дерева. Вход в дерево происходит только через корень. Для каждого узла различаются левое и правое поддеревья. Упорядоченность элементов следующая: элементы левого поддерева меньше узла и меньше элементов правого поддерева.
Время поиска в двоичном дереве сокращается по сравнению с линейной структурой с ~N до log2N, где N – число узлов в дереве. Компоненту двоичного дерева можно представить переменной типа
birec = record
I: integer;
pred, succ: intp
end;
Каждая такая переменная содержит три поля: поле целого значения – поле I, поле указателя на предыдущий (в смысле упорядоченности) элемент – поле pred и поле указателя на последующий элемент – поле succ.
Алгоритм построения дерева:
Всегда при добавлении вершины к дереву алгоритм начинает работу с корня. Если ее значение больше, чем значение корня, то идем по правым веточкам, если меньше – по левым, пока не найдется ей место
Алгоритм добавления вершины подобен алгоритму построения дерева.
Type tree=^elem;
Elem=record
K:byte;
Left, right: tree;
End;
Var p: tree;
New (p);
Удаление вершины:
- Нашли удаляемую вершину
- Идем шаг налево, и потом до конца направо, или один шаг вправо и до конца налево.
Обход дерева. Вывод информации на экран.