519

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

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

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

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

Русский

2013-01-06

240 KB

156 чел.

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


 

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

7445. Административно-правовое регулирование реализации прав, свобод и обязанностей граждан 206 KB
  Административно-правовое регулирование реализации прав, свобод и обязанностей граждан ПЛАН Введение Понятие и механизм административно-правового регулирования. Административно-правовое обеспечение прав и свобод граждан. Администрат...
7446. Система управленческого учета на предприятии ЗАО Мензелинский хлебозавод 201 KB
  Система управленческого учета на предприятии ЗАО Мензелинский хлебозавод ВВЕДЕНИЕ Переход к рыночным отношениям совершенно по-иному определяет место предприятия экономике. Эффективность его работы во многом зависит от управленческой деятельности, об...
7447. Расчет параметров и изучение структуры гидропривода агрегатного станка 359 KB
  ЗАДАНИЕ на курсовую работу по дисциплине: Гидравлика Тема проекта: Расчет параметров и изучение структуры гидропривода агрегатного станка Технические условия: диаметры трубопроводов гидролиний dтр=12 мм нагрузка на агрегатную головку в период рабоч...
7448. Исследование имиджа фирмы The Coca-Cola Company 89.9 KB
  Введение В современных рыночных условиях функционирует множество организаций, часть из которых является лидерами рынка, другие же распадаются, не выдержав конкуренции. Именно конкуренция заставляет организации бороться за право существования на рынк...
7449. Марковские модели систем 114.79 KB
  Марковские модели систем Введение Основные понятия теории Марковских цепей ввел А.А. Марков в 1907г. С тех пор эту теорию развивали многие ведущие математики. В последнее время обнаружилась важная роль цепей Маркова в биологических и социологических...
7450. Финансовые проблемы формирования и использования оборотных средств предприятия 241 KB
  Финансовые проблемы формирования и использования оборотных средств предприятия ВВЕДЕНИЕ Оборотные средства являются одной из составных частей имущества предприятия. Состояние и эффективность их использования - одно из главных условий успешной деятел...
7451. Разработка базы данных Абитуриент средствами Microsoft Access 1.11 MB
  Разработка базы данных Абитуриент средствами Microsoft Access I. Введение Для принятия обоснованных и эффективных решений в производственной деятельности, в управлении экономикой и в политике современный специалист должен уметь с помощью компьютеров...
7452. Планирование воспитательной работы классного руководителя (по Е.Н. Степанову) 141.5 KB
  Планирование воспитательной работы классного руководителя (по Е.Н. Степанову) Трудно представить жизнедеятельность образовательного учреждения без его перспективного и календарного плана, без плана подготовки и проведения школьного мероприятие...
7453. Изучение и анализ гражданско-правого регулирования лизинговых отношений в предпринимательской деятельности 48.08 KB
  Введение Лизинг (финансовая аренда) - это разновидность арендных отношений, в результате которых лизингодатель обязуется приобрести в собственность указанное лизингополучателем имущество у определенного им продавца и предоставить второму это имущест...