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


 

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

44818. Методика обучения фонетике и орфоэпии 12.83 KB
  Цели изучения фонетики раскрыть перед учащимися роль звуковой стороны языка показать связь последней с лексикой и грамматикой. Познавательные цели: дать школьникам представление о звуковой системе русского языка предупредить бытовое смешение звука и буквы развивать речевой слух научить работать с орфоэпическим словарём познакомить с нормами литературного произношения. Практические цели: формирование учебноязыковых фонетических явлений: распознать звуки русского языка классифицировать их анализируя звуковой состав слова...
44821. Основной капитал предприятий 20.86 KB
  К основному капиталу относится та часть авансированного капитала которая затрачена на постройку зданий сооружений на покупку машин оборудования инструмента. После реализации товара основной капитал по частям возвращается в денежной форме предпринимателю. Основной капитал подвергается физическому и моральному износу.
44822. Мова - суспільне явище. Функції мови 22.5 KB
  Можна дати чималу кількість визначень до поняття мова Мова засіб спілкування мислетворення інтелектуального та естетичного освоєння світу. Мислетворча засіб творення і вираження думки. Номінативна засіб називання усіх ознак предметів дій тощо. Пізнавальна засіб пізнання і накопичення досвіду.
44824. Предпринимательство. Субъекты и формы предпринимательской деятельности 38.28 KB
  По назначению готовой продукции: производящая средства производства производящая средства потребления. По особенностям функционирования выделяют: 1активные ОС заняты в процессе воспроизводства продукции здание в цехе станки машины приборы и т.Фондоотдача Отражает объем продукции приходящийся на один рубль основных фондов. Показывает какая величина основных фондов приходится на рубль выпущенной продукции.
44825. Эффективность государственного регулирования в переходной экономике 24 KB
  Эффективность государственного регулирования в переходной экономике Система государственного регулирования в переходной экономике характеризуется двумя определяющими тенденциями. В переходной экономике роль государственного регулирования в целом выше чем в развитом рыночном хозяйстве. Далее в переходной экономике рынок не сразу становится главным регулятором хозяйственной деятельности поэтому государству приходится активно вмешиваться в экономические процессы. В переходной экономике по сравнению с административнокомандной...
44826. Die Berliner Mauer 26 KB
  Gebut wurde die Berliner Muer nfng der 60er Jhre um den Flüchtlingsstrom vom Osten in den Westen zu stoppen. Die DDR steht kurz vor dem us ist wirtschftlich und politisch bnkrott. Die Sttsgrenze wird geöffnet die Vereinigung der beiden deutschen Stten ist nch über 40 Jhren Trennung in Sicht.