Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
13.08.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
21211.zip — 4.58 kb
  • posledovatelnye-tablicy_21211_1.rtf — 22.74 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

Последовательные таблицы
Последовательные
таблицы.
Будем рассматривать неотсортированные таблицы.
K - количество элементов в таблице
N - длина вектора представления элементов таблицы
Векторное представление:
type элемент = record key ... body ...;
таблица = array [1..N] of элемент
end
key=...
body=...
Время поиска K/2
Списковое представление:
type элемент = record 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 найти такое i: table[i].ключ=ключ и удалить этот элемент из table
i:=1; | процедура
table[последний+1].ключ:=ключ; |
while table[i].ключключ do i:=i+1условие инвариантности цикла| поиска
if i=1) and ( таблица [i]. ключ > ключ ) do begin
таблица[i+1].ключ:=таблица[i].ключ;



Ваше мнение



CAPTCHA