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


 

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

68502. Мораль, нравственность и этика в системе регулярного поведения 102.99 KB
  Ритуалы и этикет как регуляторы поведения Ритуал магическое действие имеющее космический смысл Основная функция упорядочить взаимоотношения между социумом и Виды ритуалов: календарный погребальный Свадебный рождение ребенка инициации ритуал гостеприимства и обмена дарами ритуальные жертвоприношения...
68503. Этика - внутренняя организационная система 123.88 KB
  Никакие кодексы не будут действовать если они не соответствуют с внутренним ощущением правильного справедливого Будут этики доиндустриального общества пророки учет интересов других людей подчинение младших старшим Индустриальное общество...
68505. Ядерная физика 426.5 KB
  Активность является характеристикой радиоактивного вещества как источника радиоактивного излучения. Поглощенная доза количество энергии ядерного излучения поглощенное единицей массы вещества. Поглощенная доза не учитывает качественный состав падающего излучения.
68506. Понятие финансового права и его сущность 62 KB
  Финансовая деятельность государства - это осуществление им функций по планомерному образованию, распределению и использованию денежных фондов (фин ресурсов) в целях реализации задач социально-экономического развития и обеспечения обороноспособности и безопасности страны.
68507. Правовые системы современности 195 KB
  Романо-германская правовая семья. Становления и развития романо-германского права. Основные черты и особенности романо-германского права. Существенные различия правовых систем Германии и Франции. Англосаксонская правовая семья. Традиционная правовая семья. Религиозная правовая семья
68508. Фізичний рівень передачі інформації: цифрові канали передачі даних 372.5 KB
  Крім того до апаратною складовою комп’ютерної мережі відносяться кабельні системи ліній зв’язку та комунікаційне обладнання що дозволяє об’єднувати окремі сегменти мережі і організовувати інформаційні потоки. Структурована кабельна система Кабельна система є базою для будьякої мережі.
68509. ФІЛОСОФІЯ, ЇЇ ПРЕДМЕТ ТА ФУНКЦІЇ 176.5 KB
  Завдання для самостійної роботи: Доведіть чому кожна людина є філософом хоча й не завжди усвідомлює це Проаналізуйте хто ближче до істини у поясненні суттєвості світу матеріалісти чи ідеалісти Чим відрізняється релігія наука і філософія Проаналізуйте визначення філософії.
68510. ЭТИКА И ЭСТЕТИКА В КОНТЕКСТЕ КУЛЬТУРЫ 111.5 KB
  Каждой целостной исторической формации присущ свой тип культуры. В его развитии решающую роль отводят материальным факторам, связанным с доминирующим типом социально-экономических отношений. Культура — это, прежде всего характерный для членов данного общества образ мыслей и образ действий.