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

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

Статическая строка (тип String) в языке Pascal представляет собой одномерный массив, в нулевом элементе которого находится дескриптор с количеством символов в строке, а в последующих элементах — коды символов строки.

Главный недостаток статической строки — неизменность физической длины, что приводит к неэффективному расходу памяти.

Статическая таблица с физической точки зрения представляет собой вектор, элементами которого являются записи. Ранее было отмечено, что полями записи могут быть интегрированные структуры данных — векторы, массивы, другие записи. Аналогично и элементами векторов и массивов могут быть также интегрированные структуры. Одна из таких сложных структур — таблица. Частой, характерной логической особенностью таблиц является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу — по значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ — это свойство, идентифицирующее данную запись во множестве однотипных записей. Как правило, к ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться в запись, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Например, при интеграции в таблицу записей о студентах выборка может производиться как по личному номеру студента, так и по фамилии.

Итак, основной операцией при работе с таблицами является операция доступа к записи по ключу — конкретному значению поля записи. Она реализуется процедурой поиска. Поскольку поиск может быть значительно более эффективным в таблицах, упорядоченных по значениям ключей, довольно часто над таблицами необходимо выполнять операции сортировки.

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

Для достижения высокой по скорости эффективности используют различающиеся алгоритмы сортировки и поиска для работы с оперативными и файловыми структурами. Обзор различных алгоритмов сортировки и поиска приведен в [17].

Списком называют упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называют линейным. Логические списки (и их частные виды: стеки, очереди, деки) можно реализовать статическим вектором или вектором в виде динамической переменной, но в этих случаях на размер списка накладываются ограничения. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Для снятия ограничений линейные связные списки целесообразно реализовывать динамическими структурами данных. Такие списки будем называть динамическими.

Стек — это линейный список с одной точкой доступа к его элементам, называемой вершиной стека. Добавить или убрать элементы можно только через его вершину. Принцип работы стека: LIFO (Last In-First Out — последним пришел — первым исключается).

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

• включение нового элемента (англ. push — заталкивать);

• исключение элемента из стекла (англ. pop — выскакивать).

Вспомогательные операции:

• определение текущего числа элементов в стеке;

• просмотр элементов стека (например, для печати);

• очистка стека;

• неразрушающее чтение элемента из вершины стека (может быть реализовано как комбинация основных операций: pop и push).

Очередь — это линейная структура данных, в один конец которой добавляются элементы, а с другого конца изымаются. Принцип работы очереди: FIFO (First In — First Out — первым пришел — первым вышел).

Дек (от англ. deq — double ended queue) — особый вид очереди в виде последовательного списка, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека — дек с ограниченным входом и дек с ограниченным выходом.

Разветвленный список, или дерево, — это список, элементами которого могут быть тоже списки.

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

Биранрное дерево — дерево, в каждом узле которого происходит разветвление только на два поддерева (ветви): левое и правое.

Лесом называют конечное множество непересекающихся деревьев.

Граф — сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта, обладает следующими свойствами:

• на каждый элемент (узел, вершину) может быть произвольное количество ссылок;

• каждый элемент может иметь связь с любым количеством других элементов;

• каждая связка (ребро, дуга) может иметь направление и вес.

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

Граф, все связи которого ориентированные, называют ориентированным графом, или орграфом; со всеми неориентированными связями — неориентированным графом; со связями обоих типов — смешанным графом.

Конкретные организации структур данных и алгоритмы реализации операций с ними рассмотрены в [21, 23, 25].

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

Однако длительное сохранение информации возможно лишь во внешней памяти, поэтому проектирование оперативных структур данных программы должно вестись в неотрывной связи (параллельно) с проектированием структуры файлов программы. Данные многих оперативных структур должны сохраняться в файлах и восстанавливаться по информации, записанной ранее в файл.

Пусть требуется спроектировать программу электронной таблицы. Такой проект выполнила фирма "Borland Inc", когда ей понадобилась демонстрационная программа. Обоснование потребности и цели разработки этого проекта были рассмотрены в гл. 2.

Что видит пользователь при работе с электронной таблицей? — Огромный двухмерный массив клеток.