Структуры и алгоритмы обработки данных

Операции над записями:
1. Прочтение содержимого поля записи.
2. Занесение информации в поле записи.
3. Все операции, которые разрешаются над полем записи, соответствующего типа.

2.3.4  Таблицы
Таблица – это конечный набор записей (рис. 2.11).

При задании таблицы указывается количество содержащихся в ней записей.

Пример:

Type ST = Record
Num: Integer;
Name: String[15];
Fak: String[5];
Group: String[10];
Angl: Integer;
Physic: Integer;

var
Table: Array [1..19] of St;

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

Операции с таблицами:
1. Поиск записи по заданному ключу.
2. Занесение новой записи в таблицу.

Ключ – это идентификатор записи. Для хранения этого идентификатора  отводится специальное поле.
Составной ключ – ключ, содержащий более двух полей.

2.4  Полустатические  структуры  данных

К полустатическим структурам данных относят стеки, деки и очереди.
Списки
Это набор связанных элементов данных, которые в общем случае могут быть разного типа.
Пример списка:
E1, E2, …….., En,…   n > 1 и не зафиксировано.
Количество элементов списка может меняться в процессе выполнения программы. Различают 2 вида списков:
1) Несвязные
2) Связные
В несвязных списках связь между элементами данных выражена неявно. В связных списках в элемент данных заносится указатель связи с последующим или предыдущим элементом списка.
Стеки, деки и очереди – это несвязные списки. Кроме того они относятся к последовательным спискам, в которых неявная связь отображается их последовательностью.

2.4.1  Стеки
Очередь вида LIFO (Last In First Out – Последним пришел, первым ушел ), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним, называется стеком. Это одна из наиболее употребляемых структур данных, которая оказывается весьма удобной при решении различных задач.
В силу указанной дисциплины обслуживания, в стеке доступна единственая его позиция, которая называется вершиной стека- это позиция, в которой находится последний по времени поступления  в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Графически стек можно представить следующим образом:

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

Операции, производимые над стеками:

1. Занесение элемента в стек.
Push(S,I), где S – идентификатор стека, I – заносимый элемент.
2. Выборка элемента из стека.
Pop(S)
3. Определение пустоты стека.
Empty(S)
4. Прочтение элемента без его выборки из стека.