Работа со структурами
1 Понятие табличной структуры данных
Таблицей называется структура данных, элементы которой представляют собой записи, состоящие из нескольких полей. При этом одно из полей называется полем ключа, а остальные - полями данных. Каждая запись таблицы имеет уникальный код в поле ключа. По этому коду осуществляется поиск данных в таблице. Задача поиска в таблице имеет следующую формулировку.
Табличная структура Т состоит из множества записей Тi , i=1¸n, каждая из которых имеет поле ключа К i и множество полей данных Dj , j=1¸m. Определить значения полей данных такой записи таблицы, поле ключа которой содержит значение x , называемое аргументом поиска.
Пример табличной структуры
| Планета | Радиус (в радиусах Земли) | Масса (в массах Земли) |
| Меркурий | 0,382 | 0,055 |
| Венера | 0,950 | 0,816 |
| Земля | 1,000 | 1,000 |
| Марс | 0,531 | 0,107 |
| Юпитер | 11,2 | |
| Сатурн | 9,5 | 95,1 |
| Уран | 3,9 | 14,6 |
| Нептун | 4,0 | 17,2 |
| Плутон | 0,45 | 0,002 |
Ключом в приведенной таблице является поле, озаглавленное «Планета», а поля «Радиус» и «Масса» являются полями данных. Результатом решения задачи поиска в такой таблице для аргумента поиска, например, x=Юпитер будут значения данных 11,2 и 318.
Таблица называется упорядоченной, если ее записи каким-либо образом упорядочены по значению поля ключа. Например, если при i<j значения ключей Кi < Кj. Очевидно, что для упорядоченной таблицы могут использоваться алгоритмы поиска записи, минимизирующие время поиска. Время поиска, измеряемое в количестве просмотренных в процессе поиска записей, является основной характеристикой способа упорядоченности таблицы и, соответственно, алгоритма решения задачи поиска. Таблица вышерассмотренного примера является неупорядоченной. (Ее можно было бы упорядочить, расположив названия планет в алфавитном порядке). Единственный способ организации поиска в такой таблице - линейный поиск: последовательный просмотр всех записей, начиная с первой, до тех пор, пока не будет обнаружен заданный аргумент поиска, либо пока по окончании просмотра всей таблицы не будет сделан вывод об отсутствии в ней записи с искомым ключом.
Для организации таблицы средствами языка С удобно воспользоваться типом struct со следующим синтаксисом:
struct <имя типа> {
<список полей>
}
<список полей>::=<поля>|<список полей>;<поля>
<поля>::=<тип> <имена>
<имена>::=<имя>|<имена>,<имя>
Описав одну запись таблицы в виде типа struct, собрать множество записей в единую таблицу можно, например, с помощью одномерного массива. Так, вышеприведенная таблица в C-программе может быть описана в виде массива table:
struct line {
char *planet;
float radius,mass;
};
line table[9];
2. Задание на лабораторную работу
Полагая, что некоторая табличная структура представляет собой последовательность записей, содержащих по два поля каждая: поле ключа типа char* и поле данных типа int, - написать функции включения новой записи в таблицу и выборки данных из таблицы по заданному ключу, соблюдая при этом условие уникальности каждого значения поля ключа.