75670

Динамічні структури, що розгалужуються (дерева)

Практическая работа

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

На початку програми зявляється розбита на елементи формула-зразок у вигляді дерева. Вершина цього дерева містись саму формулу. У листах дерева містяться змінні. Користувач може ввести свою формулу натиснувши клавішу Insert. Після того можна змінити значення змінних, які за замовчуванням дорівнюють

Украинкский

2015-01-24

455.83 KB

2 чел.

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

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

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

Кафедра ПЗ

Практична робота №6 варіант №9

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

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

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

Вінниця, 2013


Тема: Динамічні структури, що розгалужуються (дерева).

 

Мета:  Засвоїти поняття дерева як структури даних. Закріпити навички застосування динамічних структур даних при розв’язуванні задач. Сформувати уміння реалізовувати дерева з використанням списків.

Завдання:

Варіант № 9.

  1.  Клас арифметичних виразів, що містить однобуквені змінні, операції +, -, *, / і круглі дужки, назвемо класом найпростіших виразів. Реалізувати:
  2.  процедуру побудови дерева найпростішого арифметичного виразу, заданого у виді рядка.
  3.  процедуру обчислення значення найпростішого арифметичного виразу, заданого деревом при значеннях змінних, що вводяться з клавіатури.
  4.  процедуру перетворення дерева в рядок.

Опис алгоритму виконання

На початку програми з'являється розбита на елементи формула-зразок у вигляді дерева. Вершина цього дерева містись саму формулу. У листах дерева містяться змінні. Користувач може ввести свою формулу натиснувши клавішу Insert. Після того можна змінити значення змінних, які за замовчуванням дорівнюють 2. Для цього треба натиснути на лист правою клавішею миші. Щоб отримати готовий результат слід натиснути клавішу Space.

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

Складність алгоритму дорівнює О(N2) від t,

де tчас виконаня,

Nкількість символів у стрічці формули.


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

 



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

#include <vector>

using namespace std;

#pragma once

class Node

{

public:

string data;

double value;

int x;

int y;

vector <Node*> children;

Node *parent;

Node(void);

Node(string _data, int _x, int _y);

Node(const Node &arg);

~Node(void);

void Show(HDC hdc, int x, int y);

int ChangeX(int _x);

int ChangeY(int _y);

void InputData(string _data);

void Push(string a, int _x, int _y);

static void ShowTree(Node *tr,  HDC hdc);

void Split(string input);

void FindThisNode(int mdx, int mdy);

int PressedArea(int mdx, int mdy);

int UpMouseArea(int mux, int muy);

bool PressedNode(int mdx, int mdy);

double Calc(bool last=false);

static void MakeStr(char s, double d);

void ChangeXY();

};

extern Node *ThisNode;


#include "StdAfx.h"

//#include "Node.h"

using namespace std;

Node *ThisNode=0;

string Output="";

Node::Node(void)

{

parent=0;

x=300;

y=50;

value=2.0;

}

Node::Node(string _data, int _x, int _y):data(_data), x(_x), y(_y)

{

parent=0;

value=2.0;

}

Node::Node(const Node &arg)

{

data=arg.data;

x=arg.x;

y=arg.y;

parent=0;

value=0.0;

}

Node::~Node(void)

{

}

void Node::Show(HDC hdc, int x, int y)

{

HPEN hNodePen, hRightPen, holdpen;

HBRUSH hNodeBrush, holdbrush;

 

hNodePen = CreatePen(PS_SOLID, 4, RGB(255, 128, 0));

hRightPen = CreatePen(PS_SOLID, 4, RGB(7, 100, 255));

holdpen = (HPEN)SelectObject(hdc, hNodePen);

 

hNodeBrush = CreateSolidBrush(RGB(255, 128, 0));

holdbrush = (HBRUSH)SelectObject(hdc, hNodeBrush);

 

if (parent!=0)

{

  holdpen = (HPEN)SelectObject(hdc, hRightPen);

  POINT pnt;

  ::MoveToEx(hdc, x, y-10, &pnt);

  ::LineTo(hdc, parent->x, parent->y+10);

 

}

 

holdpen = (HPEN)SelectObject(hdc, hNodePen);

Ellipse(hdc, x-30, y-30, x+30, y+30);

if (this->children.size()==0)

{

 char buffer[20];

 sprintf (buffer, "%f", value);

 ::TextOutA(hdc, x-5, y+8, (LPCSTR) buffer, strlen(buffer) );

}

::TextOutA(hdc, x-5, y-7, (LPCSTR) data.c_str(), data.size() );

  

::DeleteObject(hNodePen);

::DeleteObject(hRightPen);

::DeleteObject(hNodeBrush);

}

int Node::ChangeX(int _x)

{

x=_x;

return x;

}

int Node::ChangeY(int _y)

{

y=_y;

return y;

}

void Node::InputData(string _data)

{

data=_data;

}

void Node::Push(string a, int _x, int _y)  // push new element to the tree

{

int dx=100;

Node *cur = new Node(a, _x, _y);

cur->parent=this;

cur->x=x-200+dx*children.size();

cur->y=y+80;

children.push_back(cur);

}

void Node::ChangeXY()

{

if(this!=0&&this->parent!=0)

{

 int dx=100;

 if(this->parent->parent==0)

 {

  dx=1000/(this->parent->children.size()+1);

 }

 else dx=this->parent->parent->children[0]->x*2;

 for(int i=0;i<this->parent->children.size(); ++i)

  this->parent->children[i]->x=dx/this->parent->children.size()/2+i*dx;

}

}

void Node::ShowTree(Node *tr,  HDC hdc)  // prints tree

{

   if (tr==NULL)  // return if the tree is empty

       return;

     // if tree exists and not empty

   for (int i=0; i<tr->children.size(); ++i)

 Node::ShowTree(tr->children[i],  hdc);

tr->Show(hdc, tr->x, tr->y);

}

void Node::Split (string input)

{

   data=input;

string s="";

int prior=5;

int skob=0;

if(input.size()<=2) return;

 

for(int i=0; i<input.size()-1; ++i)

 {

 switch(input[i])

 {

  case '+':

  case '-':

   if(skob==0&&prior>1)prior=1;

   break;

  case '*':

  case '/':

   if(skob==0&&prior>2)prior=2;

   break;

  case '(':

   ++skob;

   break;

  case ')':

   --skob;

   break;

 }

 }

skob=0;

for (int i=0; i<input.size(); ++i)

 {

 switch(input[i])

 {

  case '+':

  case '-':

   s+=input[i];

   if(prior==1&&skob==0)

   {

    Push(s, x, y);

    s="";

   }

   break;

  case '*':

  case '/':

   s+=input[i];

   if(prior==2&&skob==0)

   {

    Push(s, x, y);

    s="";

   }

   break;

  case '(':

   if(skob!=0)

   s+=input[i];

   ++skob;

   break;

  case ')':

   if(skob!=1)

   s+=input[i];

   --skob;

   break;

  

  default:

   s+=input[i];

   break;

 }

}

 if(s!="")

Push(s, x, y);

for (int i=0; i<this->children.size(); ++i)

 this->children[i]->Split(children[i]->data);

}

double Node::Calc(bool last)

{

if (this->children.size()==0)

{

  if (this->data.size()==1)

  {

   if(last)

   {

   MakeStr(')', this->value);

   }

   else

   MakeStr(' ', this->value);

  }

  else

  {

   if(last)

   {

   MakeStr(')', this->value);

   Output+=this->data[this->data.size()-1];

   }

   else MakeStr(this->data[this->data.size()-1], this->value);

  }

  return value;

}

Output+="(";

double res=children[0]->Calc();

 

for (int i=0; i<this->children.size()-1; ++i)

{

 bool last=i==children.size()-2;

 switch(children[i]->data[children[i]->data.size()-1])

 {

  case '+':

   res+=children[i+1]->Calc(last);

   break;

  case '-':

   res-=children[i+1]->Calc(last);

   break;

  case '*':

   res*=children[i+1]->Calc(last);

   break;

  case '/':

   res/=children[i+1]->Calc(last);

   break;

  default: break;

 }

}

 

 

 

 if (this->data.size()>2)

 if (this->data[this->data.size()-2]==')')

 {

  Output+=this->data[this->data.size()-1];

  Output+="(";

 }

 

return res;

}

int Node::PressedArea(int mdx, int mdy)

{

if (mdx>(x-30)&&mdx<x&&mdy<(y+30)&&mdy>(y-30)) return 1;   // left child

else if (mdx<(x+30)&&mdx>x&&mdy<(y+30)&&mdy>(y-30)) return 2; // right child

else return -1;

}

int Node::UpMouseArea(int mux, int muy)

{

if (mux<(x-10)&&muy>(y+10)) return 1;   // left child

else if (mux>(x+10)&&muy>(y+10)) return 2; // right child

else return -1;

}

bool Node::PressedNode(int mdx, int mdy)

{

if (mdx>(x-30)&&mdx<(x+30)&&mdy<(y+30)&&mdy>(y-30)) return true;   

else return false;

}

void Node::FindThisNode(int mdx, int mdy)  // traverses the tree

{

   if  (ThisNode!=0) return;

   

 if(this->PressedNode(mdx, mdy))

 ThisNode=this;

else for (int i=0; i<this->children.size(); ++i)

 this->children[i]->FindThisNode(mdx, mdy);

 

}

void Node::MakeStr(char s, double d)

{

// double convert to buf

char buff [100];

sprintf (buff, "%f", d);

string buf(buff);

 buf+=s;

Output+=buf;

}

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

Висновки

Засвоїли поняття дерева як структури даних. Закріпили навички застосування динамічних структур даних при розв’язуванні задач. Сформували уміння реалізовувати дерева з використанням списків.


 

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

23116. Енергія електромагнітного поля. Густина потоку енергії ЕМП 98.5 KB
  Густина потоку енергії ЕМП. Енергія ЕМП може перетворюватись в інші види енергії наприклад у кінетичну енергію зарядів. Обчислимо роботу яку виконує ЕМП зміщуючи заряди. Якщо за час dt заряд зміщується на відстань то робота ЕМП буде .
23117. Принцип найменшої дії. Функція Лагранжа 43.5 KB
  Функція Лагранжа Найбільш загальне формулювання закону руху механічних систем дає так званий принцип найменшої дії або принцип Гамільтона. Функція L називається функцією Лагранжа даної системи а інтеграл дією. Функція Лагранжа залежить лише від q и а не від більш високих похідних що пояснюється тим що механічний стан повністю визначається завданням координат та швидкостей. Для спрощення запису формул припустимо спочатку що система має лише одну степінь вільності так що буде визначена лише одна функція qt.
23118. Гамільтонова форма рівнянь 90.5 KB
  Гамільтонова форма рівнянь. Підставляючи отримане в початкове рня маємо: Для переходу до змінних і додаємо і віднімаємо: Звідси Оскільки права частина виражена через диференціали то її можна розглядати як повний диференціал певної функції що залежить від яку позначимо і назвемо функцією Гамільтона: де Залишилося довести що Маємо Враховуючи це запишемо: звідки Ця система рівнянь називається канонічними рівняннями Гамільтона. рівн. рівн.
23119. Закони руху системи матеріальних точок та твердого тіла. Тензор інерції 77 KB
  Закони руху системи матеріальних точок та твердого тіла. Запишемо другий закон Ньютона для матеріальної точки з даної системи: 1 де сумарна зовнішня сила що діє на іту м. Записавши 1 для кожної точки системи та просумувавши всі отриманні рівняння маємо: 2. З урахуванням третього закону Ньютона тобто співвідношення перепишемо 2 як: 3 Нехай Rрадіус вектор даної системи: задає точкуцентр мас системи.
23120. Закони збереження та фундаментальні властивості простору-часу 263 KB
  Рух механічної системи описується 2S величинами де Sкількість ступенів вільності. системи вибір початку відліку часу одна з сталих в диф. рівняннях що описують динаміку може бути обрана сталою 1 При розвязанні системи 1 2S1 сталих де Отримані величини інтеграли руху визнач. системи явно не залеж.
23121. Рух тіл в інерціальній та неінерціальній системах відліку. Сили інерції. Коріолісівське прискорення 202 KB
  Коріолісівське прискорення. інваріантне 0 де прискорення в ІСВ швидкість в ІСВ маса тіла рівнодійна сил взаємодії які діють на тіло. Характеризуватимемо рух початку координат НеІСВ відносно ІСВ радіусвектором а обертання НеІСВ відносно ІСВ кутовою частотою х В НеІСВ вимагають аналогічного до 0 запису закону руху тіла відносно радіусвектора : Оскільки прискорення в НеІСВ внаслідок х нерівне та величина не змінюється при переході до НеІСВ необхідно щоб сумарна сила складалась не тільки з теж...
23122. Закони руху системи матеріальних точок та твердого тіла. Тензор інерції 159.5 KB
  Закони руху системи матеріальних точок та твердого тіла.Введемо вектор повної кількості руху систем частинок: Знайдемо його зміну з часом: Для першої суми: ТобтоТаким чином якщо сума всіх зовнішніх сил рівна нулю то має місце закон збереження імпульсу. Ведемо повний момент кількості руху:Знайдемо швидкість його зміни в часі: Другий доданок повний момент зовнішніх сил .Розглянемо перший доданок врахувавши : За умов виконання має місце закон збереження моменту кількості руху.
23123. Хвилі у пружньому середовищі. Хвильове рівняння. Звукові хвилі 59.5 KB
  Хвилі у пружньому середовищі. Звукові хвилі. Розрізняють хвилі повздовжні і поперечні в залежності від того чи рухаються частинки біля своїх положень рівноваги вздовж чи поперек напрямку розповсюдження хвилі. Розглянемо хвилі типу Позн.
23124. Рух ідеальної рідини. Рівняння Бернуллі 55.5 KB
  Нагадаємо що поле швидкостей характеризує не швидкiсть окремих частинок середовища а швидкiсть у данiй точцi в даний момент часу будьякої частинки рiдини або газу що знаходиться в цiй точцi в цей момент часу. Надалi будемо розглядати такi рiдини або гази для яких тензор пружних напругє iзотропним: pij = −pδij 14.10 для вязкої рiдини газу набуде вигляду: Це є рiвняння НавєСтокса де η коефiцiєнт зсувної вязкостi коефiцiєнт обємної вязкостi. Для повного опису руху рiдини необхiдно додати ще рiвняння неперервностi та...