Табличные структуры данных

1. Понятие таблицы. Виды таблиц.
Ключ уникален для каждого элемента.
Ключ (key) – поле или набор полей, однозначно (уникально) идентифицирующих запись.
Примеры: табельный номер, ИНН, СНИЛС, заводской номер, серийный номер.

Представление таблицы. Классификация таблиц
struct Man
{
int Id;
string Surname;
string Name;
};
struct Man table[15];
…
cin >> table[0].Surname;
…
Классификация таблиц
по месту хранения
внутренние;
внешние (файлы);
по отношениям связи между элементами
линейные;
нелинейные;
по упорядоченности записей
упорядоченные;
неупорядоченные.

2. Условия поиска в таблицах.

В линейной таблице элементы располагаются друг за другом.
В оперативной памяти отображаются в массивы или линейные связанные списки.
3. Линейные таблицы.
5
11
23
7
1
9
21
14
97
45

Поиск в упорядоченных таблицах
Двоичный (бинарный, логарифмический) поиск
5
11
23
27
31
39
41
44
67
75
1
2
3
4
5
6
7
8
9
10
10
23
5
1
4
2
3
1
31
11
23
int binarySearch(int *table, int n, int key)
{
int left, right, index;
left = 0;
right = n-1;
while(left<=right)
{
index = (left + right)/2;
if(key > table[index])
left = index + 1;
else if(key < table[index])
right = index – 1;
else return index;
}
return -1;
}

Поиск в неупорядоченных таблицах
Последовательный поиск
int search(int *table, int n, int key)
{
int i = 0;
while(i
i++;
return (i==n)?-1:i;
}
5
11
23
7
1
9
21
14
97
45
45
14
14
34

Поиск в неупорядоченных таблицах
Использование заграждающего элемента
int search(int *table, int n, int key)
{ int i = 0;
int r = table[n-1];
table[n-1] = key;
while(table[i]!=key)
i++;
table[n-1] = r;
return (i==n-1 && r!=key)?-1:i;
}

Работа с линейными таблицами
Основные операции с данными
Создание (create)
Чтение (read)
Модификация (update)
Удаление (delete)
struct Man {
int Id;
string Surname;
string Name;
string Patronymic;
};
…
Man* table;
…

Работа с линейными таблицами
void serialize(fstream & stream, Man & man)
{
stream.write((char *)&man.Id, sizeof(man.Id));
size_t dataSize = man.Surname.size();
stream.write((char *)&dataSize, sizeof(dataSize));
stream.write(&man.Surname[0], dataSize);
dataSize = man.Name.size();
stream.write((char *)&dataSize, sizeof(dataSize));
stream.write(&man.Name[0], dataSize);
dataSize = man.Patronymic.size();
stream.write((char *)&dataSize, sizeof(dataSize));
stream.write(&man.Patronymic[0], dataSize);
}

Работа с линейными таблицами
void deserialize(std::fstream & stream, Man & man)
{
stream.read((char *)&man.Id, sizeof(man.Id));
size_t dataSize = 0;
stream.read((char *)&dataSize, sizeof(dataSize));
man.Surname.resize(dataSize);
stream.read(&man.Surname[0], dataSize);
dataSize = 0;
stream.read((char *)&dataSize, sizeof(dataSize));
man.Name.resize(dataSize);
stream.read(&man.Name[0], dataSize);
dataSize = 0;
stream.read((char *)&dataSize, sizeof(dataSize));
man.Patronymic.resize(dataSize);
stream.read(&man.Patronymic[0], dataSize);
}

Работа с линейными таблицами
int add(Man & man) {
int code = 0;
int size = 0;
fstream file("table.dat", ios::in | ios::out | ios::ate
| ios::binary);
if (file.is_open()) {
file.seekg(0, ios::beg);
file.read((char*)&size, sizeof(size));
size++;
if (file.eof() || file.fail())
file.clear();
file.seekg(0, ios::beg);
file.write((char*)&size, sizeof(size));
file.seekg(0, ios::end);
serialize(file, man);
if (file.fail())
code = -1;
file.close();
}
else
code = -1;
return code;
}

Работа с линейными таблицами
Man* loadTable(int & size) {
Man* table = 0;
fstream file("table.dat", ios::in | ios::out | ios::ate
| ios::binary);
if (file.is_open()) {
file.seekg(0, ios::beg);
file.read((char*)&size, sizeof(size));
if (size > 0)
table = new Man[size];
for(int i=0; i
deserialize(file, table[i]);
file.close();
}
return table;
}

Работа с линейными таблицами
bool writeTable(Man* table, int size) {
bool result = true;
fstream file("table.dat", ios::out | ios::binary);
if (file.is_open() && size > 0) {
file.write((char*)&size, sizeof(size));
for (int i = 0; i < size; i++)
serialize(file, table[i]);
file.close();
if (file.bad())
result = false;
}
return result;
}

Работа с линейными таблицами
bool deleteFromTable(Man* table, int size, int index) {
bool result = true;
fstream file("table.dat", ios::out | ios::binary);
if (file.is_open() && size > 0) {
file.write((char*)&size, sizeof(size));
for (int i = 0; i < size; i++)
if (i != index)
serialize(file, table[i]);
file.close();
if (file.bad())
result = false;
}
return result;
}

4. Логически связанные таблицы.
Студент
Дисциплина
Успеваемость