519

Структуры и алгоритмы обработки данных на тему 2-3 деревья

Лабораторная работа

Информатика, кибернетика и программирование

Определить поля для записей, которые будут храниться в списке согласно своему варианту. Провести сравнение быстродействие реализованных алгоритмов для различного количества записей. Разработать алгоритмы вставки, поиска и удаления для 2-3 деревьев.

Русский

2013-01-06

240 KB

162 чел.

PAGE   \* MERGEFORMAT 13

МИНОБРНАУКИ РОССИИ

Федеральное государственное образовательное учреждение

высшего профессионального образования

«Ижевский государственный технический университет»

факультет «Информатика и вычислительная техника»

Лабораторная работа №3

по дисциплине «Структуры и алгоритмы обработки данных»

на тему «2-3 деревья»

Вариант №16

Выполнил

Студент гр. 4-78-12                                                                                Суслов Ю.Б.

Принял                                                                                                       

к.т.н., доцент                                                                                                 Лусников Р.Г.

Ижевск 2012

1. ПОСТАНОВКА ЗАДАЧИ

  1.  Определить поля для записей, которые будут храниться в списке согласно своему варианту из лабораторной работы N1. Выбрать ключевое поле (уникальное для всех записей).
  2.  Разработать алгоритмы вставки, поиска и удаления для 2-3 деревьев.
  3.  Реализовать алгоритмы на языке Си. Все функции и процедуры разбить на два типа: работающие со списком и взаимодействующие с пользователем. Структура списка должна содержать переменную – код ошибки, через которую процедуры, работающие с данными, будут сообщать об ошибках.
  4.  Составить и выполнить контрольный пример, проверяющий работу алгоритмов.
  5.  Провести сравнение быстродействие реализованных алгоритмов результатами из лабораторной работы №2 для различного количества записей (от 10 до 10000). Результат привести в табличной форме.
  6.  Составить отчет о проделанной работе.

Вариант 16:

Предметная область - Почта (Населенные пункты).


  1.  ОПИСАНИЕ СТРУКТУР ДАННЫХ

2.1.Описание структуры записи

Согласно вар.16, запись содержит поля:

  •  Id;
  •  Город отправки;
  •  Город прибытия;

Структура 2-3 дерева:

  •  kind;
  •  inf;
  •  lewoe;
  •  srednee;
  •  pravoe;
  •  lows;
  •  lowt;

1е поле – хранит в себе типа узла (внутренний или лист),2е – указатель на запись типа mail, 3е,4е,5е – указатели на левое среднее и правое поддеревья соответсвенно,6е и 7е хранят в себе ключи наименьшего из элементов хранящихся в соответствующем им правом поддереве.

3. ОПИСАНИЕ АЛГОРИТМОВ

  1.  Алгоритм вставки

Для ввода вначале реализуется алгоритм поиска для определения ячейки, сыном которой будет являться вставляемый элемент. Далее элемент вставляется в качестве сына найденной ячейки. Если у ячейки стало 3 сына, то сортируем их. Если же в результате вставки у ячейки стало 4 сына, что является нарушением свойства 2-3 дерева, то делим эту ячейку на две, и смотрим не нарушились ли свойства дерева для отца образовавшихся ячеек. В случае, когда свойство 1) не выполняется в корне дерева, то делим корень на две ячейки и их отцом ставим новый сформированный корень.

  1.  Алгоритм удаления

Для удаления реализуем алгоритм поиска удаляемого элемента в дереве. После этого удаляем наш элемент, и смотрим выполнения свойств 2-3 дерева для его отца. Если свойства выполняются, то алгоритм удаления завершен. Если нет, то смотрим на братьев этой ячейки. Если у левого или правого брата три сына, то забираем один, и определяем его как сына нашей ячейки. Если же у братьев также по два сына, то передаем единственного сына ячейки одному из братьев, а ячейку удаляем. В последнем случае необходимо опять же проверить выполнение свойств 2-3 дерева для отца нашей ячейки. Если у корня дерева в ходе этих перемещений остался только один сын, то удаляем корень и обозначаем новым корнем его единственного сына.

3.3. Алгоритм поиска

Для поиска необходимо последовательно просматривать ключи, хранящиеся в ячейках. Вначале ключ искомого элемента сравнивается с левым ключем ячейки и если наш ключ не больше его, то идем в левое поддерево. Иначе сравниваем наш ключ с ключем в правой ячейке и если наш ключ не больше его, то идем в среднее поддерево, иначе в правое поддерево. Таким образом доходим до нужного нам элемента.

  1.  ТЕКСТ ПРОГРАММЫ

#include <iostream>

#include "TPerfMeter.h"

using namespace std;

typedef struct

     {

     unsigned int id;

     char co[25];

     char cp[25];

     }mail;

enum nodetype {leaf,interior};

struct ttnode

   {

       nodetype kind;

       mail  *inf;

       ttnode * lewoe;

       ttnode * srednee;

       ttnode * pravoe;

       unsigned int lows;

       unsigned int lowt;

   };

ttnode * root;

mail x;

mail ttsearch(ttnode * node,unsigned int id)

{

   mail x;

   if (node!=NULL)

   {

       if (node->kind==interior)

       {

       if (id<node->lows) x=ttsearch(node->lewoe,id);

       else if (node->pravoe==NULL) x=ttsearch(node->srednee,id);

            else if (id<node->lowt) x=ttsearch(node->srednee,id);

                 else x=ttsearch(node->pravoe,id);

       }

       else if (id==node->inf.id) x=node->inf;

           else x.id=0;

   }

   else x.id=0;

   return x;

}

void insert1(ttnode * node,mail x,ttnode*& pnew,int & low)

{

   ttnode * pback;

   int lowback;

   int child;

   ttnode * w;

   pnew=NULL;

   if (node->kind==leaf)

    {

       if (node->inf.id!=x.id)

       {

           pnew=new ttnode;

           pnew->kind=leaf;

           if (node->inf.id<x.id)

           {

               pnew->inf=x;low=x.id;

           }

           else

           {

               pnew->inf=node->inf;

               node->inf=x;

               low=pnew->inf.id;

           }

       }

    }

    else

    {

        if (x.id<node->lows)

        {

            child=1;w=node->lewoe;

        }

        else if ((node->pravoe==NULL)||(x.id<node->lows))

               {

                   child=2;

                   w=node->srednee;

               }

             else

             {

                 child=3;

                 w=node->pravoe;

             }

             insert1(w,x,pback,lowback);

             if (pback!=NULL)

             {

                 if (node->pravoe=NULL)

                   if (child==2)

                       {

                           node->pravoe=pback;

                           node->lowt=lowback;

                       }

                   else

                   {

                       node->pravoe=node->srednee;

                       node->lowt=node->lows;

                       node->srednee=pback;

                       node->lows=lowback;

                   }

                  else

                  {

                      pnew=new ttnode;

                      pnew->kind=interior;

                      if (child==3)

                      {

                          pnew->lewoe=node->pravoe;

                          pnew->srednee=pback;

                          pnew->pravoe=NULL;

                          pnew->lows=lowback;

                          low=node->lowt;

                          node->pravoe=NULL;

                      }

                      else

                      {

                          pnew->srednee=node->pravoe;

                          pnew->lows=node->lowt;

                          pnew->pravoe=NULL;

                          node->pravoe=NULL;

                      }

                      if (child==2)

                      {

                          pnew->lewoe=pback;

                          low=lowback;

                      }

                      if (child==1)

                      {

                          pnew->lewoe=node->srednee;

                          low=node->lows;

                          node->srednee=pback;

                          node->lows=lowback;

                      }

                  }

             }

    }

}

void insert(mail *x, ttnode * &root)

{

   ttnode * pback;

   int lowback;

   ttnode * saves;

   if (root==NULL)

   {

       root=new ttnode;

       root->kind=leaf;

       root->inf=x;

   }

   else

   {

   insert1(root,x,pback,lowback);

   if (pback!=NULL)

   {

       saves=root;

       root=new ttnode;

       root->kind=interior;

       root->lewoe=saves;

       root->srednee=pback;

       root->lows=lowback;

       root->pravoe=NULL;

   }

   }

}

bool delete1(ttnode * &node,unsigned int x)

{

   ttnode * w;

   ttnode* y;

   bool onlyone;

   onlyone=false;

   if (node->lewoe->kind==leaf)

   {

       int ex;

       if (x<node->lows)

           if (x==node->lewoe->inf.id) ex=1;

           else ex=0;

       else if (node->pravoe==NULL)

               if (x==node->srednee->inf.id) ex=2;

               else ex=0;

           else if (x<node->lowt)

                   if (x==node->srednee->inf.id) ex=2;

                   else ex=0;

               else if (x==node->pravoe->inf.id) ex=3;

                   else ex=0;

       if (ex)

       {

           if (node->pravoe==NULL)

               if (ex=2) {delete node->srednee;node->srednee=NULL;node->lows=node->lewoe->inf.id; }

               else {delete node->lewoe;node->lewoe=node->srednee;node->srednee=NULL; }

           else

               if (ex=3) {delete node->pravoe;node->pravoe=NULL; }

               else if (ex=2) {delete node->srednee;node->srednee=node->pravoe;node->pravoe=NULL;node->lows=node->lowt; }

                    else {delete node->lewoe;node->lewoe=node->srednee;node->srednee=node->pravoe;node->pravoe=NULL;node->lows=node->lowt; }

           if (node->srednee=NULL) return true;

       }

       return false;

   }

   else

   {

       if (x<node->lows) w=node->lewoe;

       else if (node->pravoe==NULL) w=node->srednee;

            else if (x<node->lowt) w=node->srednee;

                 else w=node->pravoe;

       onlyone=delete1(w,x);

       if (onlyone)

       {

           if (w==node->lewoe)

               if (node->srednee->pravoe!=NULL)

               {

                   y=node->srednee;

                   w->srednee=y->lewoe;

                   y->lewoe=y->srednee;

                   y->srednee=y->pravoe;

                   w->lows=node->lows;

                   node->lows=y->lows;

                   y->lows=y->lowt;

                   y->pravoe=NULL;

               }

               else

               {

                   y=node->srednee;

                   y->pravoe=y->srednee;

                   y->srednee=y->lewoe;

                   y->lewoe=w->lewoe;

                   y->lowt=y->lows;

                   y->lows=node->lows;

                   node->lows=w->lows;

                   node->lewoe=y;

                   node->srednee=node->pravoe;

                   node->pravoe=NULL;

                   if (node->srednee==NULL) return true;

               }

           else if (w==node->srednee)

               if (node->lewoe->pravoe!=NULL)

               {

                   y=node->lewoe;

                   w->lewoe=y->pravoe;

                   node->lows=y->lowt;

                   y->pravoe=NULL;

               }

               else

               {

                   y=node->lewoe;

                   if (node->pravoe!=NULL)

                       if (node->pravoe->pravoe!=NULL)

                           {

                           w->srednee=node->pravoe->lewoe;

                           node->lows=w->lows;

                           w->lows=node->lowt;

                           node->lowt=node->pravoe->lows;

                           node->pravoe->lows=node->pravoe->lowt;

                           node->pravoe->pravoe=NULL;

                           }

                       else

                       {

                           y->pravoe=w->lewoe;

                           node->srednee=node->pravoe;

                           node->pravoe=NULL;

                           y->lowt=w->lows;

                           node->lows=node->lowt;

                           if (node->srednee==NULL) return true;

                       }

               }

           else if (w==node->pravoe)

               if (node->srednee->pravoe!=NULL)

               {

               y=node->srednee;

               w->lewoe=y->pravoe;

               y->pravoe=NULL;

               node->lowt=y->lowt;

               }

               else

               {

                   y=node->srednee;

                   y->pravoe=w->lewoe;

                   y->lowt=w->lows;

                   node->pravoe=NULL;

               }

               }

       return false;

       }

   }

void deleted(ttnode * &node,unsigned int x)

{

   if (node!=NULL)

   {

       if (node->kind==leaf)

           {if (node->inf.id==x) {delete node;node=NULL;}}

       else

       if (delete1(node,x)) {node->kind=leaf;node->inf=node->lewoe->inf;}

   }

}

void out(mail x)

{

   if (x.id!=0) printf("%d %s %s\n",x.id,x.co,x.cp);

   else printf("error!");

}

mail in()

{

   mail x;

   printf("input id:\n");

   scanf("%d",&x.id);

   printf("input cityOtppravki:\n");

   scanf("%s",&x.co);

   printf("input cityPribitia:\n");

   scanf("%s",&x.cp);

   return x;

}

void testing()

{

   ttnode* x;

   mail q;

   int i,ans,j;

   printf("write number of elements: \n");

   scanf("%d",&

   ans);

   clock_t tStart;

   tStart = clock();

   for (i=0;i<ans;i++)

   {

       q.id=rand();

       q.co[0]='s';

       q.cp[0]='s';

       insert(q,x);

   }

   printf("for %5d addtime: %.3f secn\n", ans,(float)(clock() - tStart) / CLOCKS_PER_SEC);

   tStart = clock();

   for (i=0;i<ans;i++)

   {

      j=rand();

      q=ttsearch(x,j);

   }

   printf("for %5d searchtime: %.3f secn\n", ans,(float)(clock() - tStart) / CLOCKS_PER_SEC);

   tStart = clock();

   for (i=0;i<ans;i++)

   {

       j=rand();

       deleted(x,j);

   }

   printf("for %5d removetime: %.3f secn\n", ans,(float)(clock() - tStart) / CLOCKS_PER_SEC);

   system("pause");

}

void menu(ttnode* &root)

{

   int ans=5;

   int id;

   while (ans)

   {

   system("cls");

   printf("1.Dobavit element\n");

   printf("2.Udalit element\n");

   printf("3.poisk elementa\n");

   printf("4.testing\n");

   printf("0.close\n");

   scanf("%d",&ans);

   switch (ans)

   {

   case 1:x=in();out(x);insert(x,root);printf("insert succesfull!\n");system("pause");break;

   case 2:printf("input id:\n");scanf("%d",&id);deleted(root,id);printf("delete succesfull!\n");system("pause");break;

   case 3:printf("input id:\n");scanf("%d",&id);x=ttsearch(root,id);out(x);system("pause");break;

   case 4:testing();

   case 0:break;

   default: printf("wrong!\n");

   }

   }

}

int main()

{

  root=NULL;

  menu(root);

   return 0;

}

Текст файла “TPerfMeter.h”:

#pragma once

#include <Windows.h>

class TPerfMeter

{

HANDLE dthread;

LARGE_INTEGER swfreq, swstart, swend;

DWORD oldmask;

public:

TPerfMeter();

void Start();

double Stop();

};

inline TPerfMeter::TPerfMeter()

{

dthread=GetCurrentThread();

}

inline void TPerfMeter::Start()

{

oldmask=SetThreadAffinityMask(dthread,1);

QueryPerformanceFrequency(&swfreq);

QueryPerformanceCounter(&swstart);

SetThreadAffinityMask(dthread,oldmask);

}

inline double TPerfMeter::Stop()

{

oldmask=SetThreadAffinityMask(dthread,1);

QueryPerformanceCounter(&swend);

SetThreadAffinityMask(dthread,oldmask);

return static_cast<double>(swend.QuadPart-swstart.QuadPart) *1000.f / static_cast<double>(swfreq.QuadPart);

}


  1.  КОНТРОЛЬНЫЙ ПРИМЕР

  1.  ОЦЕНКА БЫСТРОДЕЙСТВИЯ

10000 записей.

Операция

Время AVL дерева(с)

Время бинарного дерева (с)

Время массива указателей (с)

Время динамического списка (с)

Время хеш-таблицы (с)

Время 2-3 дерева (с)

Вставка элемента

0.034

0.107

0.116

0.288

0.052

0.021

Поиск элемента

0.016

0.022

0.014

0.115

0.027

0.011

Удаление элемента

0.032

0.051

0.038

0.145

0.029

0.018


 

А также другие работы, которые могут Вас заинтересовать

37175. Реформы Петра Первого 89.44 KB
  Реформы Петра Первого. ВОЕННЫЕ РЕФОРМЫ ПЕТРА I Военные реформы занимают особое место среди Петровских преобразований. Историки насчитывают всего лишь несколько месяцев мирного времени за более чем 35летнее правление Петра. Понятно что именно армия и флот были главным предметом заботы Петра.
37176. Доходы бюджета 42 KB
  Доходы бюджета необходимо рассматривать прежде всего как фактор влияющий на совокупное потребление путем оказания влияния на уровень доходности социальных групп и виды деятельности. Доходы бюджета способны воздействовать на хозяйственную активность на объемы выпускаемой продукции и техническое оснащение производства на равновесие цен на отраслевое и территориальное размещение инвестиций. Доходы бюджета выражают экономические отношения возникающие в процессе формирования основного общегосударственного фонда денежных средств между...
37177. Расходы бюджета 29 KB
  По своему материальновещественному воплощению бюджетные расходы представляют собой денежные средства направляемые на финансовое обеспечение задач и функций государства и местного самоуправления. Посредством такой формы функционирования бюджета как бюджетные расходы образуются доходы нетрудоспособных граждан и оказывается поддержка другим социальнонезащищенным слоям населения. Бюджетные расходы способны оказывать активное влияние на формирование экономического роста приоритетное финансирование научных исследований развитие прогрессивных...
37178. Межбюджетные отношения 36.5 KB
  Низкая доля собственных доходов в бюджетах субъектов Федерации и местных бюджетах заметно снижает заинтересованность на местах в наращивании налогового потенциала в своевременном и полном поступлении налогов в бюджетную систему. Межбюджетные трансферты из федерального бюджета бюджетам бюджетной системы Российской Федерации предоставляются в форме: дотаций на выравнивание бюджетной обеспеченности субъектов Российской Федерации; субсидий бюджетам субъектов Российской Федерации; субвенций бюджетам субъектов Российской...
37179. Бюджетный процесс 30 KB
  В соответствии с Бюджетным кодексом правительство России вносит на рассмотрение Государственной Думы проект федерального бюджета на очередной финансовый год не позднее 26 августа. В первом чтении принимаются основные параметры бюджетапроходит в течение 30 дней со дня его внесения в Государственную думу. Рассматривается: прогнозируемый объём доходов в очередной год и плановый период с выделением объёма нефтегазовых доходов; приложения с нормативами распределения доходов между уровнями бюджетной системы; общий объём расходов; ...
37180. Возникновение бюджета 30 KB
  По экономической сущности государственный бюджет это денежные отношения возникающие у государства с юридическими и физическими лицами по поводу распределения национального дохода в связи с образованием и использованием бюджетного фонда предназначенного для финансирования экономики социальнокультурных мероприятий нужд обороны и государственного управления. Благодаря ей можно прогнозировать социальноэкономические последствия бюджетной политики. Бюджет играет важную экономическую социальную и политическую роль в воспроизводственном...
37181. Бюджетное устройство 90.5 KB
  Бюджетная система унитарного государства состоит из двух звеньев государственного и местных бюджетов. Бюджетная система федеративных госуда рств тр ехзвенная и состоит из федеративного федерального бюджета бюджетов членов субъектов федерации и местных бюджетов. Бюджетный кодекс РФ далее БК РФ даёт следующее определение бюджетной системы: Основанная на экономических отношениях и государственном устройстве РФ регулируемая нормами права совокупность федерального бюджета бюджетов субъектов РФ местных бюджетов и бюджетов государственных...
37182. Право регулирования денежного обращение страны 92.5 KB
  Главными задачами правового регулирования денежного обращения в России являются: обеспечение четкого разделения правовых полномочий и ответственности в сфере денежного обращения между Президентом РФ законодательной и исполнительной властями; поддержание необходимого темпа роста денежной массы в обращении и правильного соотношения между наличным и безналичным денежным обращением с целью стабильного и эффективного функционирования экономики страны; обеспечение законодательной и исполнительной власти правовыми нормами и инструментами...
37183. Денежно – кредитная политика 86 KB
  Согласно комментариям к федеральному закону О Центральном банке Российской Федерации Банка России денежно кредитная политика определяется как основная часть единой государственной экономической политики проявляющаяся в воздействии на количество денег в обращении с целью достижения стабильности цен обеспечения максимально возможной занятости населения а также роста реального объёма производства. В отличие от первого определения второе подчёркивает возможность влияния денежно кредитной политики не только на сферу обращения но и...