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;

}

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

Висновки

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


 

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

17769. Інтернет – як засіб інформаційної підтримки роботи вчителя 94 KB
  Інтернет – як засіб інформаційної підтримки роботи вчителя Організація мережі Інтернет. Перегляд інформаційних ресурсів в Інтернеті Доступ користувачів до мережі Інтернет. Робота з пошуковими серверами електронними бібліотеками. Пошук потрібних нових гр...
17770. Основні вимоги до створення навчальної презентації 51.5 KB
  Основні вимоги до створення навчальної презентації План Визначення поняття €œ Презентація €. Типи презентацій. Алгоритм створення презентацій. Вимоги до структури та змісту презентації. Вимоги до оформлення змісту презентації за Д. Льюїсом. ...
17771. Інформаційні технології в освіті 94.5 KB
  Інформаційні технології в освіті. План 1.Походження терміну Інформація. Поняття інформації. Види інформації. Форми подання. Інформаційні процеси. 2. Визначення основних термінів курсу: технологія інформаційна технологія ІТ інфор...
17772. Основні напрямки використання ІКТ в навчальній діяльності на уроках іноземних мов 64.5 KB
  Лекція 4. Основні напрямки використання ІКТ в навчальній діяльності на уроках іноземних мов. Педагогічні програмні засоби їх класифікація. Підготовка вчителя до уроку з використанням ППЗ Основні форми використання ППЗ на різних етапах уроку. Організ
17773. Використання можливостей MS Excel у роботи вчителя. Розробка електронного навчального модуля 281.5 KB
  Лабораторна робота № 3 Тема. Використання можливостей MS Excel у роботи вчителя. Розробка електронного навчального модуля. II частина – Перевірка. Мета . Оволодіння навичками використання MS Excel у роботі : створення тестів для перевірки знань та при підготовці до ба...
17774. Розробка електронного навчального модуля 27.65 KB
  Лабораторна робота № 1 Тема. Розробка електронного навчального модуля. I частина – Інформація. Підготовка навчальних презентацій для викладання іноземних мов засобами програми Power Point. Мета . Оволодіння навичками створення електронного навчального мо...
17776. Розробка електронного навчального модуля 84.5 KB
  Лабораторна робота № 2 Тема. Розробка електронного навчального модуля. II частина – Практика. Підготовка навчальних матеріалів для закріплення знань учнів з іноземних мов засобами програмно – апаратного комплексу Smart Board. Мета . Оволодіння навичками створе...
17777. ЗАГАЛЬНА ФІЗІОЛОГІЯ ЗБУДЛИВИХ ТКАНИН 1.95 MB
  Загальна фізіологія збудливих тканин. 1. Фізіологія як наука. Поняття про функцію. Методи фізіологічних досліджень. Нормальна фізіологія – наука про об’єктивні закономірності протікання функцій організму в їх взаємозв’язку і у взаємодії організму із зовнішнім середо