75664

Стек і черга. Хеш таблиця

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

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

Розробити підпрограми, які забезпечують запити на запис або читання даних з черги, стека або дека. Для організації вказаних структур використовувати масиви або списки. Перевірити працездатність розроблених підпрограм. Послідовність виконання операцій запису або читання вибираються випадково. Порівняти результати роботи, зробити висновки.

Украинкский

2015-01-24

209.96 KB

4 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Лабораторна робота №4 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013

Тема: Стек і черга. Хеш таблиця.

Мета: набуття навичок моделювання зв’язаних динамічних структур даних та роботи з ними

Завдання:

Розробити підпрограми, які забезпечують запити на запис або читання даних з черги, стека або дека. Для організації вказаних структур використовувати масиви або списки. Перевірити працездатність розроблених підпрограм. Послідовність виконання операцій запису або читання вибираються випадково. Порівняти результати роботи, зробити висновки.

Варіант № 9.

Розробити підпрограми роботи з пріоритетною чергою. Встановлення запитів в чергу виконується по пріоритету, зняття - з молодших адрес (початок черги). Черга організована на масиві з циклічним заповненням і списку. Пріоритет: мах значення числового параметра, при збігу параметрів - FIFO.

Хід роботи

У програмі у головній функції створюються черги: одна як відображення на масив, інша – на список. Користувачеві пропонується обрати для перегляду одну з цих черг. Крім того, користувач має змогу ввести дані і створити свою чергу. Дані з усіх черг програми виводяться за пріоритетом, який також вказано у вигляді числового поля-ключа для кожного поля даних окремо.

 

Складність алгоритму

Складність алгоритму дорівнює O( 2N +10 ) від Т, де Т - час виконання.


Блок-схема алгоритму


Лістинг програми

//--------------------MAIN.CPP-------

#include "all_the_headers.h"

int main()

{

   int command = 0;

   cout<<"\nTo watch array-queue press 1\nTo watch list-queue press 2\nTo make own queue press 3\nTo exit press 0:  ";

   cin>>command;

   if (command==1)

       {

           // --------------------------------------------

           // -------------------------  queue as arr-----

           // --------------------------------------------

           cout<<"\n~~~~~~~~~~~~~~ How to Make an Omelet ~~~~~~~~~~~~~~\n";

           QueueArr arr;

           int count=0;

           arr.AddElem(*(new Data("Heat a pan.")),42);

           ++count;

           arr.AddElem(*(new Data("Pour in the eggs.")),25);

           ++count;

           arr.AddElem(*(new Data("Crack the eggs and beat them.")),50);

           ++count;

           arr.AddElem(*(new Data("Flip the egg pancake over and cook for another few seconds.")),5);

           ++count;

           arr.AddElem(*(new Data("Take some eggs.")),67);

           ++count;

           arr.AddElem(*(new Data("Transfer the finished omelet to a plate.")),5);

           ++count;

           arr.AddElem(*(new Data("Cook for a minute.")),25);

           ++count;

           arr.AddElem(*(new Data("Add the butter and let it melt.")),30);

           ++count;

           for (int i=0; i<count; ++i)

               cout<<arr.TakeDestroy().name<<endl;

       }

   else if (command==2)

       {

           // --------------------------------------------

           // -------------------------  queue as list----

           // --------------------------------------------

           cout<<"\n~~~~~~~~~~~~~~ How to Make an Omelet ~~~~~~~~~~~~~~\n";

           QueueList list;

           int count=0;

           list.AddElem(new Data("Heat a pan."),42);

           ++count;

           list.AddElem(new Data("Pour in the eggs."),25);

           ++count;

           list.AddElem(new Data("Crack the eggs and beat them."),50);

           ++count;

           list.AddElem(new Data("Flip the egg pancake over and cook for another few seconds."),5);

           ++count;

           list.AddElem(new Data("Take some eggs."),67);

           ++count;

           list.AddElem(new Data("Transfer the finished omelet to a plate."),5);

           ++count;

           list.AddElem(new Data("Cook for a minute."),25);

           ++count;

           list.AddElem(new Data("Add the butter and let it melt."),30);

           ++count;

           for (int i=0; i<count; ++i)

               cout<<list.TakeDestroy()->name<<endl;

       }

       else if (command==3)

       {

           cout<<"\n\nInput number of the units: ";

           int n=0;

           cin>>n;

           QueueArr own;

           for(int i=0; i<n; ++i)

           {

               cout<<"\nInput priority: ";

               int p=0;

               cin>>p;

               own.AddElem(*(new Data("manual")),p);

           }

           cout<<"\n~~~~~~~~~~~~~~ Your own queue ~~~~~~~~~~~~~~\n";

           for (int i=0; i<n; ++i)

               cout<<own.TakeDestroy().name<<endl;

       }

       else return 0;

return 0;

}

//--------------------CLASS_STRUCT.H-------

#ifndef CLASS_STRUCT_H_INCLUDED

#define CLASS_STRUCT_H_INCLUDED

#include "all_the_headers.h"

class Data // data field class

{

public:

string name;

Data(string _name="") // ctot

{

 if (_name.compare("manual") == 0)

          {

             cout<<"Input data: ";

             std::getline(cin, _name);

             std::getline(cin, _name);

          }

 name=_name;

}

~Data() // dtor

{

}

};

// --------------------------------------------

// -------------------------  queue as arr-----

// --------------------------------------------

struct Unit  // unit of queue

{

int key;  // key field

Data elem;  // data field

};

class QueueArr

{

private:

Unit *arr;  // arr of units

int numOfUnit;  // number of units

public:

QueueArr() // ctor

{

 numOfUnit=0;

 arr=0;

}

~QueueArr() // dtor

{

}

   void AddElem(Data &elem, int key)  // add unit to the queue

{

 Unit *temp = new Unit[numOfUnit+1];

 for(int i=0; i<numOfUnit; ++i)

 {

  temp[i]=arr[i];

 }

 temp[numOfUnit].elem=elem;

 temp[numOfUnit].key=key;

 ++numOfUnit;

 delete [] arr;

 arr=temp;

}

Data TakeDestroy()

{

 Unit *tmp = new Unit[numOfUnit-1];

 int j = 0; // counter for the new  arr

 int max = 0;

 Data temp;

 for(int i=0; i<numOfUnit; ++i)

 {

  if(arr[i].key>arr[max].key)

  {

   max = i;

  }

 }

 for(int i=0; i<numOfUnit; ++i)

 {

  if(i!=max)

  {

   tmp[j] = arr[i];

   ++j;

  }

 }

 temp = arr[max].elem;

 delete [] arr;

 arr = tmp;

 --numOfUnit;

 return temp;

}

};

// --------------------------------------------

// -------------------------  queue as list--

// --------------------------------------------

struct ListStr  // sructure for list (element of list)

{

int key;  // key field

Data *elem;   // pointer to the data field

ListStr *next; // pointer to thenext elem

};

class QueueList  // queue list class

{

public:

ListStr *begin;  // pointer to the beginning

QueueList()  // ctor

{

 begin=0;

}

~QueueList() // dtor

{

}

void AddElem(Data *elem, int key)  // add new elem to list

{

 ListStr *cur = begin;

 if(begin==0)

       {

  begin=new ListStr();

  begin->elem=elem;

  begin->key=key;

  begin->next=0;

  return;

 }

 while(cur->next!=0)

 {

  cur=cur->next;

 }

 cur->next=new ListStr();

 cur->next->elem=elem;

 cur->next->key=key;

 cur->next->next=0;

}

Data* TakeDestroy() // get and delete current element from list

{

 ListStr *cur = begin;

 ListStr *max = begin;

 while(cur!=0)

 {

  if(cur->key>max->key)

               max=cur;

  cur=cur->next;

 }

 if(max==begin)

 {

  begin=begin->next;

  return max->elem;

 }

 cur=begin;

 while(cur->next!=max)

 {

  cur=cur->next;

 }

 cur->next=max->next;

 return max->elem;

}

};

#endif // CLASS_STRUCT_H_INCLUDED


Результат виконання

Висновки

Набуто навички моделювання зв’язаних динамічних структур даних та роботи з ними. В результаті виконання лабораторної роботи було розроблено підпрограму роботи з пріоритетною чергою, організованою як а масиві, так і на списку.


 

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

66777. АЛГОРИТМЫ И ПРОГРАММНЫЕ СРЕДСТВА ИДЕНТИФИКАЦИИ НЕЧЕТКИХ МОДЕЛЕЙ НА ОСНОВЕ ГИБРИДНЫХ МЕТОДОВ 4.41 MB
  Такой алгоритм исключает недостаток методов основанных на производных неспособность проходить локальные минимумы и недостаток генетического алгоритма не всегда точное попадание в глобальный оптимум. Трехэтапная идентификация параметров сначала многократным запуском алгоритма имитации отжига генерируется...
66778. Роль управленческого фактора в процессе взаимодействия коммерческих банков и их клиентов 439.5 KB
  Взаимодействие коммерческих банков и их клиентов промышленных предприятий осуществляется в различных организационных формах от создания финансово-промышленных групп на основе слияния промышленного и банковского капитала и до предельно формализованных контактов ограничивающихся привычными финансовыми...
66779. ТЕХНОЛОГИИ ДИСТАНЦИОННОГО ОБУЧЕНИЯ 149 KB
  Преимущества дистанционного обучения: Возможность заниматься в удобное для себя время в удобном месте и темпе. Но в этом таится и сложность дистанционные курсы в основе которых лежат новые технологии обучения не вписываются в структуру и программы традиционного обучения.
66781. Правовые проблемы недропользования с участием иностранного инвестора 712.5 KB
  Важной чертой принимаемого законодательства о недропользовании становится распространение на него некоторых методов и институтов гражданского права чего не допускало предшествующее законодательство. Значительно расширяется применение гражданско-правовых методов регулирования отношений...
66782. Общество с ограниченной ответственностью: правовое положение и роль органов внутренних дел в обеспечении его деятельности 740 KB
  В разные годы развития экономики нашей страны государство регламентирует возможность создания и деятельность различных организационно-правовых форм ведения предпринимательской деятельности. Осуществление хозяйствования в тех или иных формах определяется, прежде всего, уровнем развития производственных отношений...
66783. ИНДИВИДУАЛЬНЫЙ ИМИДЖ КАК СТОРОНА ДУХОВНОЙ ЖИЗНИ ОБЩЕСТВА 2.24 MB
  Острый интерес к проблемам имиджелогии в политике, торговле, рекламном деле, в организации масс медиа и индустрии развлечений,в искусстве, в практическом управлении - вот далеко не полный перечень очевидных факторов роста актуальности проблем имиджелогии.
66785. Философия художественного творчества И.А. Ильина 1.21 MB
  Диссертация посвящена историко-философскому анализу теории художественного творчества И.А. Ильина. Актуальность предлагаемого исследования состоит в том, что, несмотря на появление в последние годы множества работ по философии Ильина, эстетическая концепция мыслителя...