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


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

Висновки

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


 

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

21198. Продукционные модели представления знаний 62 KB
  Например продукционную модель действий человека при посадке в автобус можно представить в следующем виде: Если не имеет деньги то пешком Если имеет деньги и не пришел автобус то ждать Если пришел автобус и не тот маршрут то ждать Если пришел автобус и тот маршрут то садиться в автобус 11. Если имеет колеса и имеет винт и имеет крылья и возит грузы то самолет . Если имеет колеса и имеет винт и не имеет крылья и возит грузы то вертолет. Если не...
21199. Характеристики программного обеспечения систем искусственного интеллекта 59.5 KB
  Структура и свойства программного обеспечения Основными составными частями программного обеспечения ПрО систем искусственного интеллекта СИИ являются: программноаппаратные средства СИИ Лекция №5; программные средства представления знаний в СИИ Лекции №№611; языки программирования и среды функционирования СИИ Лекция №13; инструментальные программные средства создания СИИ Лекция №14 и др. Основными особенностями ПрО которые существенно отличают их от ПрО традиционных систем управления и обработки данных являются свойства...
21200. Язык „Prolog” и его приложения 175.5 KB
  Язык Prolog€ и его приложения 13. Общие сведения Язык Prolog€ Programming in Logical разработан А. В языке Prolog€ реализованы идеи логического прграммирования – нового перспективного направления в развитии современных средств программирования которое возникло в рамках работ по созданию систем искусственного интеллекта. При использовании языка Prolog€ основное внимание уделяется описанию структуры решаемой задачи а не разработке традиционного алгоритма ее решения.
21201. Инструментальные средства создания интеллектуальных систем 64 KB
  В состав типовой технологической инструментальной системы входят: база данных системы; подсистема автоматизации проектирования и программирования; подсистема отладки документирования и сопровождения; подсистема управления процессом создания СИИ и другие подсистемы. Главным направлением в технологии разработки и реализации инструментальных систем в настоящее время является так называемая CASEтехнология Computer Aided Software Engineering поддерживающая все стадии жизненного цикла системы. Программные средства CASEтехнологии делятся на...
21202. Общая характеристика проблемы создания систем искусственного интеллекта 90 KB
  Для решения трудно формализуемых и неформализуемых задач в разных областях человеческой деятельности и создаются системы искусственного интеллекта СИИ . В настоящее время у создателей СИИ нет единого мнения по определению понятия интеллекта. Таким образом определить понятие СИИ так чтобы оно удовлетворяло всех довольно трудно. Разнообразие существующих определений пока не позволило создать единое стратегическое направление исследований в области СИИ.
21203. Интеллект человека. Основные характеристики 54.5 KB
  Интеллект человека. Особенности строения и функционирования мозга человека В определение дисциплины Системы искусственного интеллекта входит понятие интеллект под которым подразумевают естественный интеллект человека выработанный человечеством в течение миллионов лет эволюции. Человек считается интеллектуальным от природы в связи со способностью человеческого мозга ставить и решать интеллектуальные задачи связанные с жизнедеятельностью и выживанием человека в сложных зачастую – экстремальных условиях окружающего мира. До сих пор...
21204. Искусственный интеллект 44 KB
  В связи с этим в настоящее время ИИ трактуется как комплекс программноаппаратных средств моделирования процессов мышления человека и структуры человеческого мозга используемых в СИИ для решения трудно формализуемых задач человеческой деятельности не поддающихся формальному математическому описанию. Анализируя возможность моделирования интеллектуальных способностей человека Лекция №2 в современных СИИ можно сделать следующие выводы: искусственный ум возможен; искусственный интеллект возможен; как приближенная модель мышления человека...
21205. Характеристики и классификация систем искусственного интеллекта 69.5 KB
  Сравнительные характеристики традиционных и интеллектуальных систем Характеристики Традиционные системы Интеллектуальные системы Тип информации Данные Знания Тип обработки информации Числовая Символьная Модель представления информации Математическая Эвристическая Способ обработки информации Алгоритм Вывод на знаниях Получаемое решение задачи Оптимальное Правдоподобное Модификации системы Редкие Частые 4. к автоматическому пополнению и получению новых знаний на основе накопленного системой опыта анализа и решения задач пользователей;...
21206. Экспертные системы. Структура программноаппаратных средств экспертной системы 162.5 KB
  Знания эксперта используются для создания базы знаний ЭС. Основу ЭС составляет база знаний БЗ моделирующая память человека и представляющая собой хранилище знаний о свойствах и закономерностях данной ППО полученных в результате использования профессионального опыта...