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;

}

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

Висновки

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


 

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

32777. Термодинамика необратимых процессов. Явления переноса в термодинамически неравновесных системах. Опытные законы диффузии, теплопроводности и внутреннего трения 48.5 KB
  Термодинамика необратимых процессов. ТЕРМОДИНАМИКА НЕОБРАТИМЫХ ПРОЦЕССОВ неравновесная термодинамика изучает общие закономерности поведения систем не находящихся в состоянии термодинамического равновесия. процессов изменение энтропии системы dS равно: где deS = Q T внешнее изменение энтропии связанное с обратимым теплообменом с окружающей средой Qбесконечно малое колво теплоты Tабс. тра diS внутреннее изменение энтропии обусловленное самопроизвольным протеканием в системе необратимых процессов.
32778. ИЗУЧЕНИЕ ЗАКОНОВ ВРАЩАТЕЛЬНОГО ДВИЖЕНИЯ С ПОМОЩЬЮ МАЯТНИКА ОБЕРБЕКА 3.8 MB
  Определить момент инерции системы тел. Исследовать зависимость углового ускорения от величины момента приложенных сил с учётом сил трения. 2 Угловая скорость и угловое ускорение для всех точек тела одинаковы в данный момент времени однако для различных точек тела линейные скорости движения по окружности разные так как зависят от расстояния R точки до оси вращения. Сила равнодействующая внешних и внутренних сил приложенных к iму элементарному объему телу создаёт относительно произвольно взятой точки на оси вращения момент силы ...
32779. Определение коэффициентов трения качения и скольжения методом наклонного маятника 201 KB
  Северодвинске ФАКУЛЬТЕТ: IV КАФЕДРА: ФИЗИКИ Лабораторная работа Определение коэффициентов трения качения и скольжения методом наклонного маятника Северодвинск 2007 Лабораторная работа ФМ 16 Наклонный маятник Ι. Цель работы Цель работы: определение коэффициентов трения качения и трения скольжения. Основные теоретические положения При относительном перемещении двух соприкасающихся тел или при попытке вызвать такое перемещение возникают силы трения. Различают три вида трения возникающего при контакте твердых тел: трение скольжения покоя и...
32780. Изучение законов сохранения импульса 538.5 KB
  Определить коэффициенты восстановления скорости и энергии для случая частично упругого удара. Существует два предельных вида удара: абсолютно упругий и абсолютно неупругий. Абсолютно упругим называется такой удар при котором механическая энергия тел не переходит в другие немеханические виды энергии а размеры и форма тел полностью восстанавливаются после удара. Абсолютно неупругим ударом называется такой удар при котором размеры и форма тел не восстанавливаются после удара.
32781. Определение коэффициентов восстановления скорости и энергии шаров 150.23 KB
  Схема лабораторной установки схема проведения эксперимента Установка включает в свой состав: 1 основание; 2 вертикальную стойку; 3 верхний кронштейн; 4 корпус; 5 электромагнит; 6 нити для подвески металлических шаров; 7 провода для обеспечения электрического контакта шаров с клеммами 10. Основание снабжено тремя регулируемыми опорами 8 и зажимом 9 для фиксации вертикальной стойки 2 выполненной из металлической трубы ; на верхнем кронштейне 3 предназначенном для подвески шаров расположены узлы регулировки обеспечивающие...
32782. ОПРЕДЕЛЕНИЕ ПЛОТНОСТИ ЖИДКОСТИ ПРИ ПОМОЩИ КАТЕТОМЕТРА 1.2 MB
  ЦЕЛЬ И МЕТОД РАБОТЫ научиться работать с катетометром В 630; определить плотность жидкости с помощью катетометра используя метод сообщающихся сосудов. ТЕОРЕТИЧЕСКОЕ ВВЕДЕНИЕ Плотность жидкости можно определить с помощью сообщающихся сосудов. 1 поверх жидкости известной плотности  наливают в оба колена исследуемую жидкость неизвестной плотности .
32783. ОПРЕДЕЛЕНИЕ УНИВЕРСАЛЬНОЙ ГАЗОВОЙ ПОСТОЯННОЙ 532 KB
  ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ На базе экспериментальных законов БойляМариотта ГейЛюссака Шарля Клапейрон установил что для разреженных газов выполняется соотношение 1 где P давление газа Па V объем газа м3 T абсолютная температура К C газовая постоянная зависящая от массы газа.=1013105 Па и T=273 К один моль любого газа занимает один и тот же объем равный =224 литра=224102 м3 поэтому для одного моля газа из соотношения 1 получаем: или 2 где величина R=831 одинакова для всех...
32784. ОПРЕДЕЛЕНИЕ ОТНОШЕНИЯ ТЕПЛОЁМКОСТЕЙ ДЛЯ ВОЗДУХА 256.5 KB
  Избыток давления воздуха в Рис. Пусть при состоянии 1 в баллоне объемом V масса воздуха равна m. Масса воздуха m занимала перед открытием крана К2 объем V1 где V1 V.
32785. Определение ускорения свободного падения при помощи машины Атвуда 569.5 KB
  Северодвинске Факультет: № 4 Кафедра: № 12 Лабораторная работа Определение ускорения свободного падения при помощи машины Атвуда г. Северодвинск 2007 Лабораторная работа ФМ 11 Определение ускорения свободного падения при помощи машины Атвуда 1. Цель и метод: С помощью машины Атвуда исследовать законы кинематики и научиться экспериментально определять ускорение свободного падения. Законы свободного падения тел открыл итальянский физик Галилео Галилей 1564 ― 1642.