Понедельник, Июль 5th, 2010

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

Операции над записями:
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. Прочтение элемента без его выборки из стека.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники