Последовательные таблиці
N — довжина вектора уявлення елементів таблицы Векторное представление: Для підготовки даної праці були використані матеріали із сайту internet. Основна складність операцій на таблиці — пошук. Для даної — линейна. Сложность операції вставки для відсортованих таблиць возросла. If i=последний+1 then write (‘нет запису із ‘, ключ) else table. тело:=тело. While not (table. key=ключ) do {це основна… Читати ще >
Последовательные таблиці (реферат, курсова, диплом, контрольна)
Последовательные таблицы.
Будем розглядати неотсортированные таблицы.
K — кількість елементів в таблице.
N — довжина вектора уявлення елементів таблицы Векторное представление:
type елемент = record key … body …;
таблиця = array [1.N] of элемент.
end.
key=…
body=…
Время пошуку K/2.
Списковое представление:
type елемент = record key… body …;
связь=элемент;
procedure вставити (var table: таблица; var ключ: key; тело: body).
begin.
if последний>=N then write (‘нет місця') else begin.
последний:=последний+1;
table[последний]. key:=ключ;
table[последний]. body:=тело;
end;
with table[последний] do.
key:=ключ;
body:=тело;
end.
end.
Предполагаем, що довжина ключа й тіла сама й та же.
procedure изменить (var table: таблица; var последний: integer).
var i, j: integer;
begin.
table[последний+1]. key:=ключ;
i:=1;
while not (table[i]. key=ключ) do {це основна умова хоча разів выполняется}.
i:=i+1;
if i=последний+1 then write (‘нет запису із ‘, ключ) else table[i]. тело:=тело.
end.
Операции вставити й змінити мають складність K/2, де До — кількість елементів в таблице.
Procedure Исключить (var table: таблица; var последний: integer).
var i: integer.
begin {знайти таке і: table[i]. ключ=ключ усунути цей елемент з table}.
i:=1; | процедура.
table[последний+1]. ключ:=ключ; |.
while table[i]. ключключ do i:=i+1{условие інваріантості циклу}| поиска.
if i=1) and (таблица[i]. ключ>ключ) do begin.
таблица[i+1]. ключ:=таблица[i].ключ;
таблица[i+1]. тело:=таблица[i].тело;
i:=i-1.
end;
таблица[i]. тело:=тело;
таблица[i]. ключ:=ключ.
end.
end.
Сложность операції вставки для відсортованих таблиць возросла.
Выводы:
1) основна складність операцій на таблиці - пошук. Для даної - линейна.
2)векторное уявлення добре, коли операції видалення і вставки щодо рідкісні, і якщо немає, то перевагу потрібно віддавати списковому представлению.
3) Для послідовних таблиць зниження складності можна досягнути з допомогою використання інформації про народження ключів. Операцію пошуку можна скоротити рахунок скорочення довжини шляхів поиска.
Список литературы
Для підготовки даної праці були використані матеріали із сайту internet.