Таблицы (tables) Таблица - это совокупность записей, каждая из которых состоит из двух полей - ключа и тела: причем ключи обязательно должны быть различными: - презентация

1 Таблицы (tables) Таблица - это совокупность записей, каждая из которых состоит из двух полей - ключа и тела: причем ключи обязательно должны быть различными: ключ i ключ j, если i j. ключ 1 тело 1 ключ 2 тело 2 ключ N тело N … N 0 По отношению к таблице применяются следующие операции: 1. Поиск по ключу: дан ключ - найти запись с этим ключом. 2. Вставка новой записи в таблицу. 3. Удаление записи, имеющей данный ключ.

2 Основная проблема при работе с таблицей – это так организовать таблицу, чтобы поиск по ключу был как можно более быстрым. Соглашения 1) Операция удаления записей из таблиц применяется на практике достаточно редко, поэтому мы не будем рассматривать ее в дальнейшем. 2) Мы будем пользоваться следующим описанием записей таблиц: type запись = record ключ: Тип Ключа; тело: Тип Тела end; Тип запись - это тип элементов таблицы, которые мы представляем паскалевскими записями из двух полей. Ключи могут быть любого типа, лишь бы их можно было сравнивать на равно-неравно и на больше-меньше; как правило, это числа или строки. Тела же записей могут быть любого типа (массивами, строками и т.п.) - все зависит от конкретной задачи. 3) Текущее количество записей в таблице будем обозначать как N: N - число записей в таблице 4) Каждый способ организации таблиц мы будем оценивать по числу сравнений ключей, т.е. по тому количеству записей таблицы, ключи из которых нужно сравнить с заданным ключом, чтобы найти запись с этим ключом или найти место, куда надо вставить новую запись: оценка операций – по числу сравнений ключей

3 Оптимальный алгоритм поиска а) да нет б) да нет в) N/2 N/2 Упорядоченные таблицы 12 nn+1 L M ключ 1 ключ 2... ключ n... TАБ тело 1 тело 2 тело n Nn

4 const L=...; {размер массива М} type index = 1..L; таблица = record M: array[index] of запись; N: index end; Алгоритм бинарного поиска (поиск по ключу) function Бинарный Поиск(var TAB: таблица; key: Тип Ключа; var i: integer): boolean; var l, r, c: integer; begin with TAB do begin l:=1; r:=N; {левый и правый концы} while lM[c].ключ then l:=c+1 else r:=c end; Бинарный Поиск:=key=M[l].ключ; i:=l; end {of with} end;

5 Вставка новой записи M ==> procedure вставка(var TAB: таблица; var rec: запись); var i, j: integer; begin if Бинарный Поиск(TAB,rec.ключ,i) then TAB.M[i]:=rec else with TAB do begin if rec.ключ>M[i].ключ then i:=i+1; {i – место для rec} for j:=N downto i do M[j+1]:=M[j]; {освободить i-е место} M[i]:=rec; N:=N+1 end end;

6 Методы сортировки ключей таблицы Сортировка простым обменом (метод пузырька). procedure bubblesort (var TAB : таблица); vari,j : index; x : запись; begin for i:=2 to TAB.N do begin for j:= TAB.N downto i do { Шаг сортировки } if TAB.M[j-1].ключ > TAB.M[j].ключ then begin x:=TAB.M[j-1]; TAB.M[j-1]:=TAB.M[j]; TAB.M[j]:=x end end; Шагом сортировки по методу пузырька назовем полный проход по массиву ключей Число сравнений в алгоритме простого обмена C = (n 2 - n)/2, а количество пересылок M min = 0,M ср = (n2 - n)*3/4,M max = (n2 - n)*3/2

7 Сортировка простым выбором procedure sort (var TAB : таблица); vari,j,k : index; x : запись; begin for i:=1 to TAB.N - 1do begin k:=i; x:=TAB.M[i]; for j:=i+1 to TAB.N do{Очередной шаг сортировки} if TAB.M[j].ключ < x.ключ then begin k:=j; x:=TAB.M[j] end; TAB.M[k]:=TAB.M[i]; TAB.M[i]:=x; end end; Шагом сортировки по методу простого выбора назовем полный проход по отрезку массива ключей при поиске минимального ключа и обмен найденного минимального ключа с первым ключом этого отрезка ключей. Среднее число сравнений равно С=(n 2 - n)/2, а число пересылок: М min =3*(n-1)M max =trunc(n 2 /4) + 3*(n-1)