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


 

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

63861. Проблемы защиты коренных народов 44 KB
  В Приангарье проживает 1950 человек которые относятся к категории коренных малочисленных народов КМН 1272 эвенка и 678 тофаларов по переписи населения 2010 года. Постановлением Правительства Иркутской области от 1 апреля 2013 года № 106пп утверждена долгосрочная целевая программа...
63862. Причины изменения языка в разных социальных группах 47.5 KB
  Эти слова прижились и использует в повседневной речи. Часто употребляемые молодыми людьми слова и выражения не понятны взрослым нашим родителям бабушкам дедушкам. От слова ботать учиться эти и многие другие слова и выражения привносят собой в язык особый смысловой оттенок.
63863. «Другие»: оценка гомосексуальности в разных культурах 24.08 KB
  Сегодня СМИ затрагивают абсолютно любые темы. Общество стало свободным, открытым. На просторах интернета можно найти ответы на любую тему. Эти изменения коснулись не только, каких либо масштабных процессов (внутренняя и внешняя политика), но и более личностных.
63864. Анализ государственной языковой политики республик в составе Российской Федерации через призму Интернет-сайтов их органов власти 39.33 KB
  Российская Федерация состоит из 83 субъектов 21 из которых являются республиками. Таблица 1 Государственные языки и титульные этносы в республиках России Республика Государственные языки Доля титульного этноса...
63865. Изменение социальных отношений и институтов 23.82 KB
  Меняется время меняются социальные институты и социальные отношения. Социальные институты от лат. Институты характеризуются своими возможностями влиять на поведение людей посредством установленных правил определяющих так её поведение.
63866. Мировоззрение молодежи в трансформационном аспекте 33.94 KB
  Мировоззрение система взглядов на объективный мир и место человека в нём на отношение человека к окружающей его действительности и самому себе а также обусловленные этими взглядами основные жизненные позиции людей их убеждения идеалы принципы познания и деятельности ценностные ориентации.
63867. Трансформация предпринимательской культуры в России в постсоветский период 22.52 KB
  На современном этапе в ходе проведения социально-экономических реформ активно обсуждается вопрос экономической культуры российского предпринимательства. В данной связи следует учитывать что именно степень эффективности проведения...
63868. Трансформация языка в контексте социокульутрных изменений 48.38 KB
  В обществе непрерывно происходят различные социальные процессы которые могут приводить к возникновению новых элементов и исчезновению ранее существовавших элементов и отношений между ними. Одним из таких элементов относится Язык который подвергся изменениям в результате социокультурного развития.