Работа по гражданскому праву таблицы

Последовательные таблицы.

Будем рассматривать неотсортированные таблицы.

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 {найти такое i: table[i].ключ=ключ и удалить этот элемент из table}

i:=1; | процедура

table[последний+1].ключ:=ключ; |

while table[i].ключ<>ключ do i:=i+1{условие инвариантности цикла}| поиска

if i<=последний then begin

while i<>последний do begin

table[i]:=table[i+1];

i:=i+1

end;

последний:=последний-1;

end else write(‘Такого элемента нет’)

end.

Сложность: К/2 - поиск

К/2 - сдвиг

К/2+К/2=К, то есть сложность линейна

body=...

key=...

type ссылка=звено;

звено=record ключ:key;

тело:body;

связь:ссылка

end;

var таблица:ссылка;

procedure ВСТАВИТЬ(var таблица,последний:ссылка; ключ: key; тело:body)

var элемент:звено;

begin

new(элемент);

элемент.ключ:=ключ;

элемент.тело:=тело;

элемент.связь:=nil;

последний.связь:=элемент;

последний:=элемент;

if таблица=nil then таблица:=элемент else последний.связь:=элемент;

последний:=элемент

end

Сложность не зависит от длины таблицы

procedure изменить (var таблица, последний:ссылка; ключ:key; тело:body)

{найти таблица.ключ = ключ и заменить таблица.тело на тело}

var следующий:ссылка;

begin {поиск элемента с заданным ключом}

if таблица<> nil then begin

new(следующий);

следующий.ключ:=ключ:

следующий.связь:= nil;

последний.связь:=следующий;

следующий:=таблица;

end;

{поиск}

while следующий.ключ<> ключ do следующий:=следующий.связь;

if последний.связь<>следующий then следующий.тело:=тело

else write(‘элемент не найден’);

{нужно уничтожить сгенерированный элемент}

dispose(последний.связь)

end

Сложность К/2

procedure удалить(var таблица, последний: ссылка; ключ: key);

var текущий: ссылка;

{если элемент последний или первый, то рассмотрим отдельно, иначе сдвинем ссылку и освободим память}

if {таблица пуста} then write (‘Таблица пуста’) else

if {в таблице один элемент} then

if {единственный элемент есть искомый} then {сделать таблицу пустой}

else write(‘нет искомого элемента в таблице’)

else write (‘нет искомого элемента в таблице’)

else {поиск в таблице}

new(текущий);

текущий.ключ=ключ;

текущий.связь:=nil;

последний.связь:=текущий;

текущий:=таблица;

while текущий.ключ<> ключ do begin

предок:=текущий;

текущий:=текущий.связь

end

if {первый элемент - искомый} then begin

текущий:=таблица;

таблица:= текущий.связь;

dispose(текущий)

end

if {последний- искомый (текущий=последний)} then begin

последний:=предок;

последний.связь:=nil;

dispose(текущий);

dispose(текущий.связь)

end

else begin

предок.связь:=текущий.связь;

dispose(текущий);

dispose(последний.связь)

end

end

Сложность = сложности поиска по линейному списку К/2

Таблицу нужно формировать так, чтобы наиболее часто встречаемые ключи находились в начале списка. Зная частоту встреча7емости ключей и отсортировав таблицу можно улучшить эффективность.

Сортированные последовательные таблицы.

Типы ключа и тела далее просты.

procedure вставить(var таблица: table; var последний: integer; ключ: key; тело:body)

var i:integer;

begin

if последний = N then write(‘таблица заполнена’) else begin

i:=последний;

{считаем, что все ключи упорядоченны по возрастанию, то есть

I(Kj)=I(Kt)+1

(Kj, Kt)R и не s: (Kj, Ks)R (Ks, Kt)R}

while (i>=1) and (таблица[i].ключ>ключ) do begin

таблица[i+1].ключ:=таблица[i].ключ;

таблица[i+1].тело:=таблица[i].тело;

i:=i-1

end;

таблица[i].тело:=тело;

таблица[i].ключ:=ключ

end

end

Сложность операции вставки для отсортированных таблиц возросла.

Выводы:

1) основная сложность операций в таблице - поиск. Для данной - линейна.

2)векторное представление хорошо, когда операции удаления и вставки относительно редки, а, если же нет, то предпочтение нужно отдавать списковому представлению.

3) Для последовательных таблиц понижение сложности можно достичь за счет использования информации о встречаемости ключей. Операцию поиска можно сократить за счёт сокращения длины путей поиска.

Список литературы





Похожие курсовые работы

1. Работа по гражданскому праву особенная часть

2. Таблицы и схемы по гражданскому праву

3. Контрольная работа по гражданскому праву часть

4. Бесплатно курсовая работа по гражданскому праву

5. Работа по гражданскому праву по общей части

6. Безвозмездное пользование имуществом курсовая работа по гражданскому праву

7. Бесплатно курсовая работа по гражданскому праву гражданская правосубъектность физических лиц

8. Бесплатно курсовая работа по гражданскому праву участие прокурора в уголовном процессе

9. 2008 2009курсовая работа по гражданскому праву на тему вексель и вексельные правоотношения

10. Бесплатно курсовая работа по гражданскому праву участие в гражданском процессе органов местного самоуправления

11. Контрольная по гражданскому праву особенная часть

12. Работа по уголовному праву особенная часть

13. Схемы и таблицы к курсовой работе по уголовному праву

14. Решение задач по гражданскому праву особенная часть

15. Где ответы к задачам по гражданскому праву

Курсовые работы, рефераты и доклады