Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 12 )

Рассмотрим три важных правила:

1)  постоянные множители не имеют значения для определения порядка временной сложности, т. е. 0(k*f)=0(f);

2)  Правило произведений: порядок временной сложности произведения двух функций равен произведению их сложностей: 0(fg)=0(f)0(g);

3)  Правило сумм: порядок временной сложности суммы функций равен порядку максимального из слагаемых): O(n5+n2+n)=O(n5)

Правила анализа программ:

1.  Время выполнения операторов присваивания, чтения и записи обычно имеет порядок 0(1).

2.  Время выполнения последовательности операторов определяется с помощью правила сумм.

3.  Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок 0(1). Время для всей конструкции условия состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь).

4.  Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения  операторов тела цикла и времени  вычисления  условия прекращения  цикла  (обычно последнее имеет порядок 0(1)).  Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно

       

ПРАКТИЧЕСКИЕ И ЛАБОРАТОРНЫЕ ЗАНЯТИЯ

Лабораторная работа №1. Организация линейных связанных структур данных и операции с ними

Цель: закрепление умений и навыков в организации линейных связанных структур данных, научиться применять линейные списки при решении задач.

Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка  процедуры, которая манипулирует  ими. Организация информации  и методы  доступа  к  ней  обычно  определяются  характером  стоящей  перед программистом задачи. Поэтому каждый программист должен иметь в своем "багаже" соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации. В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как "char", "integer",  "real". На  следующем уровне  находятся массивы, представляющие  собой наборы  базовых  типов  данных.  Затем  идут  записи, представляющие собой группы типов данных,  доступ к  которым осуществляется по одному из данных, а на последнем уровне, когда уже не рассматриваются физические аспекты представления данных, внимание обращается на порядок,  в котором данные хранятся и в котором делается их поиск.  По  существу физические данные связаны с "машиной данных", которая управляет способом доступа  к информации в вашей программе. Имеется четыре такие "машины":

  •  очередь;

  •  стек;

  •  связанный список;

  •  двоичное дерево.

Каждый метод используется при решении определенного  класса задач. Каждый метод по  существу является  неким  "устройством",  которое обеспечивает для  заданной информации определенный  способ хранения  и  при запросе выполняет определенные операции  поиска данных.  В каждом  из этих методов используется две операции: добавить  элемент  и  найти  элемент  (под  элементом  понимается  некоторая информационная единица).

ОЧЕРЕДИ

Очередь  представляет  собой линейный  список данных, доступ  к  которому осуществляется по  принципу "первый вошел, первый вышел" (иногда сокращенно его называют методом доступа FIFO). Элемент, который был первым поставлен в очередь, будет первым получен при  поиске. Элемент, поставленный в очередь вторым  при поиске будет получен также вторым и т. д. Этот способ  является единственным  при постановке элементов  в очередь и при поиске элементов  в очереди. Применение очереди не позволяет делать прямой доступ к любому конкретному элементу. В повседневной жизни  очереди встречаются часто. Например, очередь в банке  или очередь в кафетериях  с быстрым обслуживанием являются очередью в указанном  выше смысле (исключая те  случае, когда человек пытается добиться обслуживания вне  очереди!). Для того, чтобы лучше  понять работу  очереди,  рассмотрим  две процедуры: постановка  в очередь и  выборка из очереди.  При выполнении процедуры постановки  в  очередь  элемент  помещается  в конец  очереди.  При  выполнении процедуры  выборки из очереди из нее удаляется первый элемент,  который является результатом выполнения данной процедуры.  Работа очереди проиллюстрирована на рис.1. Следует помнить, что при выборке из очереди из нее действительно удаляется один элемент. Если этот элемент нигде не будет сохранен, то в  последствии к нему нельзя будет осуществить доступ.

Операция  Содержимое  очереди

  1 Qstore(A)  А

  1 Qstore(В)  А В

1 Qstore(C)  A B C

2 Qretrieve  returns А  В С

1 Qstore(D)  B C D

2 Qretrieve  returns В  C D

2 Qretrieve  returns С  D

Рис.1. Работа очереди: 1 - постановка в очередь; 2 - выборка из очереди элемента А В, С.

Очереди  в  программировании используются  во многих  случаях,  например,  при моделировании (обсуждается  ниже в соответствующей главе),  при планировании работ (метод ПЕРТ или графики Гатта), при буферизации ввода-вывода. В качестве  примера рассмотрим  простую программу  планирования  предписаний, которая позволяет обращаться к нескольким предписаниям. При  каждом обращении предписание удаляется из списка и на экран выводится следующее предписание. Для простоты  в программе  используется массив символьных строк  для управления событиями.  Описание  предписания  ограничивается  80  символами  и  число предписаний не должно превышать 100. Прежде всего в этой программе планирования должны быть предусмотрены процедура постановки в очередь и процедура выборки из очереди.  Эти  процедуры  приводятся  ниже  и  даются  необходимые  описания глобальных  переменных и типов данных.

Const

  MAX_EVENT  = 100;

type

  EvtType  =  string[80];

  var

  event: array[1..MAX_EVENT]  of EvtType;

  spos,  rpos:  integer;

  {добавить  в очередь}

  procedure  Qstore(q:EvtType);

  begin

  if spos=MAX_EVEMT  then

  writeln ( ' List ful1)

else

  begin

  event[spos]:=q;

  spos:=spos+l;

  end;

end;  {конец  процедуры  постановки в очередь}

{ выборка  объекта из очереди }

function  Qretrieve:EvtType;

begin

  if  rpos=spos then

  begin

  writeln (‘No appointments scheduled.');

  Qretrieve := ' ' ;

  end else

  begin

  rpos:=rpos+1;

  Qretrieve := event[rpos-l] ;

  end;

end;  { конец процедуры выборки  из очереди  }

       В работе этих функций используются  три глобальные переменные: "spos", которая содержит индекс следующего свободного элемента; “rpos",  которая содержит индекс следующего выбираемого  элемента и "event", которая представляет собой массив символьных строк с описанием предписаний. Переменные "spos" и "rpos" должны быть установлены в нулевое значение до первого обращения к процедурам постановки в 2 очередь и выборки из очереди. В этой программе процедура постановки в очередь помещает новые события в конец списка и делает проверку заполнения списка. Функция выборки из очереди выбирает события из очереди  при  необходимости их обработки.  Когда  планируется  новое событие, переменная "spos" увеличивается на единицу, а когда событие завершается, то увеличивается  на  единицу  переменная  "rpos". Фактически  переменная  "rpos" преследует переменную "spos" в проходах по очереди. Если значение  указателя  свободного  места  совпадает  со значением указателя  выбираемого элемента, то это означает, что в очереди  нет  событий.

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

СТЕКИ

Организация стека в  определенном  смысле  противоположна организации очереди, поскольку здесь  используется доступ  по принципу "последней вошел, первый вышел" (такой метод доступа  иногда  называют  методом LIFO).  Представим  себе  стопку тарелок. Нижняя тарелка из этой стопки  будет использована последней, а верхняя тарелка (которая была установлена в стопку последней) будет использована первой. Стеки широко  используются  в системном  программном обеспечении,  включая компиляторы и интерпретаторы. Исторически сложилось так, что две основные операции для стека - поместить в стек и выбрать из стека -  получили название соответственно "затолкнуть" и "вытолкнуть". Поэтому для реализации стека необходимо создать две функции: "posh" (затолкнуть), которая помещает элемент в вершину стека, и "pop" (вытолкнуть), которая выбирает из вершины  стека значение. Необходимо также предусмотреть определенную область в памяти, где фактически будет храниться стек. Для этого можно использовать  массив или  можно  выделить  область  памяти,  используя  средство  динамического распределения  памяти, предусмотренное в  языке Паскаль.  Как и  при работе с очередью  при выборке значения из стека  элемент  будет  потерян, если  его  не сохранить где-нибудь в памяти.  Ниже приводится общая форма процедур установки в стек и выборки из стека.