Реферат по предмету "Программирование"


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

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

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

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=1) and (таблица[i].ключ>ключ) do
begin

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

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

                   i:=i-1

          
end;

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

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

    end

end

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

Выводы:

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

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

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

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат Концепт число в древнерусском языке на материале памятников ХХІ - ХІІІ веков
Реферат Сопоставительный анализ баллад В.А. Жуковского «Людмила» и «Светлана»
Реферат Готовился ли СССР к нападению на Германию?
Реферат Imagry In The Fall Of The House
Реферат ЭВМ "МЭСМ"
Реферат Корма фирмы "Тетра"
Реферат Анализ эффективности трудовой деятельности на промышленном предприятии и резервы ее повышения (на примере ОАО "Казанский жировой комбинат")
Реферат Проблеми реформування податку на додану вартість в Україні
Реферат Ants Essay Research Paper Ants are social
Реферат Молодежная субкультура 6
Реферат Значение двигательной активности в жизни студента
Реферат Прохождение практики по бухучету.
Реферат Бебель, Август
Реферат Государственное регулирование кризисных ситуаций
Реферат Проведення відбору експертів в галузі "Архітектура комп’ютерів"