75664

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

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

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

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

Украинкский

2015-01-24

209.96 KB

5 чел.

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

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

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

Кафедра ПЗ

Лабораторна робота №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


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

Висновки

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


 

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

49647. Республика как форма государственного правления 271.87 KB
  РЕСПУБЛИКАНСКАЯ ФОРМА ПРАВЛЕНИ СМЕШАННЫЕ РЕСПУБЛИКАНСКИЕ ФОРМЫ ПРАВЛЕНИЯ ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 35 ВВЕДЕНИЕ Прежде чем приступить к рассмотрению темы Республиканская форма правления нужно дать определение формы правления. Под формой правления мы понимаем систему формирования и взаимоотношений главы государства высших органов законодательной и исполнительной власти.
49648. Организация автоматизированной информационной системы налогообложения на предприятии ОАО «КЗПК» 169.5 KB
  Автоматизированная информационная технология АИТ в налоговой системе это совокупность методов информационных процессов и программнотехнических средств объединенных в технологическую цепочку обеспечивающую сбор обработку хранение распространение и отображение информации с целью снижения трудоемкости процессов использования информационного ресурса а также повышения их надежности и оперативности. В информационном аспекте система должна предоставлять достаточную и полную информацию для реализации ее основных функций иметь рациональные...
49650. Разработка программного продукта АИС «Название отдела (рабочего места)» 573.5 KB
  Проектирование информационно-логической модели БД Этапы создания информационной системы базы данных Типовой жизненный цикл информационной системы любого класса представляет собой последовательность этапов: анализа предметной области проектирования системы разработки и реализации системы тестирования и отладки сопровождения системы. Этап анализа предметной области включает: Формулировку требований к функциональности будущей системы; Определение объемов и структуры...
49653. ИСПОЛЬЗОВАНИЕ ОПТИЧЕСКОЙ ИНТЕРФЕРЕНЦИИ ДЛЯ ИЗМЕРЕНИЯ ФИЗИЧЕСКИХ ВЕЛИЧИН 639.2 KB
  Интерференция света при отражении от тонких пластинок При падении световой волны на тонкую прозрачную пластинку или пленку происходит отражение от обеих поверхностей пластинки. Пластинка отбрасывает вверх два когерентных параллельных пучка света из которых один образуется за счет отражения от верхней поверхности пластинки второй вследствие отражения от нижней поверхности. кратного отражения от поверхностей пластинки. Следовательно оптическая разность хода лучей 1 и 2 равна где s1 длина отрезка ОА s2 суммарная длина отрезков ОС и...