Руководство пользователя 6




Скачать 199.11 Kb.
Название Руководство пользователя 6
Дата публикации 22.09.2014
Размер 199.11 Kb.
Тип Руководство пользователя
literature-edu.ru > Авто-ремонт > Руководство пользователя


Федеральное агентство по образованию Российской Федерации

Государственное образовательное учреждение

высшего профессионального образования

Нижегородский государственный университет им. Н.И. Лобачевского
Факультет Вычислительной математики и кибернетики

Отчёт по лабораторной работе
Реализация динамической структуры данных типа "стек"
на основе линейных односвязных списков
и ее практическое применение для задания локального оператора перехода двумерного клеточного автомата


Выполнил:

студент ф-та ВМК гр. 82-11
Толстолуцкая О.В.

Проверил:

ассистент каф. МО ЭВМ, ВМК
Кустикова В.Д.

Нижний Новгород

2013 г.

Содержание

Введение 4

Постановка задачи 5

Руководство пользователя 6

Руководство программиста 10

Описание структуры программы 10

Описание структур данных 10

Описание алгоритмов 13

Стек на основе линейных односвязных списков 13

Перевод в постфиксную форму 13

Вычисление выражения, записанного в постфиксной форме 14

Реализация двумерных клеточных автоматов 14

Заключение 16

Литература 17

Приложения 18

Приложение А. Файл исходного кода 18

Приложение Б. Заголовочный файл CellAutomata2D.h 19

Приложение В. Заголовочный файл CA.h 20

Приложение Г. Исходный код Stack.cpp 21

Приложение Д. Исходный код Корейка.cpp 21



Введение


Стек - структура данных, представляющая собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

Линейный однонаправленный список - это структура данных, состоящая из элементов одного типа, связанных между собой, задается указателем на первый элемент списка. Основные операции для работы со списком:

  1. операция, проверяющая список на пустоту;

  2. операция добавления объекта в список;

  3. операция определения первого (головного) элемента списка;

  4. операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

С помощью динамической структуры данных типа "стек" на основе линейных односвязных списков в этой лабораторной работе будет реализована работа с двумерными клеточными автоматами. Клеточный автомат это дискретная модель, включающую регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Для каждой ячейки определено множество ячеек, называемых окрестностью. Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое Правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке. В данной лабораторной работе поддерживается работа с окрестностью Неймана, окрестностью Мура, окрестностью Мвона и с пользовательской окрестностью.

Работа с пользовательской окрестностью реализована с помощью алгоритма перевода в постфиксную форму. Алгоритм перевода в постфиксную запись обрабатывает исходный массив лексем и строит новый массив из тех же лексем, расположенных в другом порядке.

Постановка задачи


Необходимо разработать и реализовать консольное приложение, позволяющее реализовать двумерный клеточный автомат при помощи динамической структуры данных типа "стек" на основе линейных односвязных списков.

  • Реализовать двумерные клеточные автоматы с поддержкой различных окрестностей.

Пользователь имеет возможность задавать:

  • размер клеточного автомата (по горизонтали и вертикали);

  • тип окрестности (Неймана, Мура, Мвона и пользовательская);

  • тип начальной конфигурации (тестовая, пользовательская, случайная);

Программа должна:

  • Считать каждую последующую итерацию с учетом предоставленных пользователем параметров.

  • Просчитывать пользовательскую окрестность с использование стека на списках.

  • Использовать статическую библиотеку классов для работы с двумерными клеточными автоматами и со стеком на списках.

Замечания:

  • При выборе пользовательской окрестности, должно вводиться арифметическое выражение, которое преобразуется в постфиксную форму и используется для расчета пользовательской окрестности.



Руководство пользователя


Запустите программу. На экран выведется окно диалога с пользователем (Рис. 1):



  1. Диалоговое окно.

Введите параметры запрашиваемые программой (Рис. 2). Ниже приведена таблица с пояснениями к вводимым параметрам (Таблица 1.).

2D or 1D(1/2)

Режим работы. Выберите 2.

size x

Задайте размер клеточного автомата по ширине.

size y

Задайте размер клеточного автомата по высоте.

type of start conf

(0-test, 1-random, 2-user)

Задайте тип стартовой конфигурации:

  • Тестовая (вид тестовой конфигурации приведен ниже).

  • Случайная (значение каждой клетки задается случайным образом).

  • Пользовательская (клетка закрашивается/раскрашивается по щелчку мыши на ней).

type of neighbourhood


Выберите тип окрестности (вид окрестностей приведен ниже):

  • Нейман

  • Мур

  • Мвон

  • Пользовательская

  1. Пояснения к вводу.



  1. Пример ввода параметров.

На экран выведется первая итерация клеточного автомата (Рис. 3).



  1. Первая итерация клеточного автомата, с параметрами указанными в Рис. 2.

При нажатии клавиши «Пробел» выводится следующая итерация, а при нажатии клавиши «Enter» вывод на экран следующих итераций происходит автоматически, останавливается по нажатию «Пробел». Ниже приведено окно работы программы после 10 итераций (Рис. 4).



  1. Окно работы программы через 10 итераций.

Выход из программы производится по нажатию клавиши «Escape».

В программе использованы следующие окрестности:

  • Окрестность Неймана (Рис. 5):



  1. Окрестность Неймана.

  • Окрестность Мура (Рис. 6):



  1. Окрестность Мура.

  • Окрестность Мвона (Рис. 7):



  1. Окрестность Мвона.

  • Пользовательская окрестность задается арифметическим выражением, буквами в выражении обозначены следующие клетки (Рис. 8):



  1. Буквы для задания окрестности.

Примечание: Задавать окрестность нужно заглавными буквами без пробелов.

Пример вводимого выражения: A+(B-C)*D.

Руководство программиста

Описание структуры программы


Данная программа имеет следующую структуру:

  • Проект (содержащий только файл исходного кода) с подключенными библиотеками для работы с OpenCV и клеточными автоматами.

  • Статическая библиотека, в которой реализованы классы для работы с клеточным автоматом и со стеком. Содержит заголовочный файл с прототипами функций и файл с реализацией этих функций.

Описание структур данных


Статическая библиотека содержит следующие классы:

  • State – класс состояния одной клетки.

Поля:

  • текущее состояние клетки.

Методы класса:

  • void changeState(int) - изменить состояние клетки на указанное;

  • int getState()узнать состояние клетки в текущий момент.

  • CellAutomata –клеточный автомат.

Поля:

  • предыдущее состояние клеточного автомата;

  • следующее состояние клеточного автомата;

  • размер клеточного автомата.

Методы класса:

  • virtual void calNextConf () - виртуальный метод вычисления следующей конфигурации;

  • virtual void testConf () - виртуальный метод установления тестовой конфигурации;

  • virtual void userConf() - виртуальный метод установления пользовательской конфигурации;

  • virtual void ramdomeConf() - виртуальный метод установления рандомной конфигурации;

  • state *GetPrevConf()- узнать предыдущую конфигурацию;

  • (void put(int i,int n)) - узнать состояние клетки клеточного автомата;

  • int get(int i) - изменить состояние клетки клеточного автомата.

  • CellAutomata2D – класс двумерного клеточного автомата.

Поля:

  • высота клеточного автомата.

Методы класса:

  • void calNextState(int) - виртуальный метод вычисления следующего значения клетки;

  • void calNextConf (int) - метод вычисления следующей конфигурации;

  • void testConf () - метод установления тестовой конфигурации;

  • void userConf() - метод установления пользовательской конфигурации;

  • void ramdomeConf() - метод установления рандомной конфигурации.

CellAutomata2DNeiman – класс двумерного клеточного автомата с окрестностью Неймана.

Методы класса:

  • void calNextState(int) - метод вычисления следующего значения клетки.

CellAutomata2DMvon – класс двумерного клеточного автомата с окрестностью Неймана.

Методы класса:

  • void calNextState(int) - метод вычисления следующего значения клетки.

CellAutomata2DMur – класс двумерного клеточного автомата с окрестностью Неймана.

Методы класса:

  • void calNextState(int) - метод вычисления следующего значения клетки.

CellAutomata2DUser - класс двумерного клеточного автомата с окрестностью задаваемой пользователем.

Поля:

  • Polka выражение, переведенное в польскую запись.

  • Arr массив, содержащий значения клеток, выбранных пользователем в окрестность.

Методы класса:

  • void calNextState(int) - метод вычисления следующего значения клетки.

Stack очередь.

Поля:

  • pBegin – начало стека;

  • с - размер стека.

Методы класса:

  • int size() - узнать текущий размер стека;

  • int put(char _data)- положить в стек элемент;

  • char get() - изъять элемент из стека;

  • int ISFULL() - проверка полноты стека.

  • int IsEmpty() - проверка пустоты стека.

Node – линейный односвязный список.

Поля:

  • char data – данные, хранящиеся в списке;

  • Node* pNext – указатель на следующий элемент списка;

Методы класса:

  • void SetNext(Node* _pNext) – установть указатель на следующий элемент списка;

  • Node* GetNext()const – получить указатель на следующий элемент списка;

  • char GetData()const – изъять данные;

Схема наследования классов (Рис. 9):



  1. Схема наследования классов.

Описание алгоритмов

Стек на основе линейных односвязных списков


Стек пуст в самом начале. Создадим первый элемент «5»и положим его в список, этим элементом будет одно звено линейного односвязного списка. При этом элемент (поскольку он единственный) будет указывать на конец списка (NULL), а указателем на начало списка станет указатель на первый элемент (Рис. 10).



  1. Список из одного элемента.

Добавим в список еще один элемент «7». Тогда указателем на начало списка станет указатель на элемент «7», а указателем на следующий после «7» элемент станет указатель на элемент «5»(Рис. 11).



  1. Список из двух элементов.

Если требуется изъять элемент «7», то указателем на начало нашего списка снова становится указатель на «5» (Рис. 10).

Заметим, что согласно идеологии стека мы можем изымать и класть элементы только на его вершину. То есть, например, имея текущим стек из двух элементов (Рис. 11), мы не можем изъять элемент «5» сразу, для этого необходимо сначала извлечь «7». Соответственно все операции для работы с нашим списком реализованы согласно принципу: последним пришёл - первым вышел (LIFO).

Перевод в постфиксную форму


Рассмотрим алгоритм перевода в постфиксную форму.

  1. Создаем два стека: стек «1» и стек «2».

  2. Просматриваем наше выражение слева направо.

    1. Если пришел операнд кладем его в стек «1».

    2. Если операция или левая скобка, то в стек «2».

    3. Если пришла правая скобка, то изымаем все из стека «1» и перекладываем в стек «2».

    4. Если у пришедшей операции приоритет меньше чем у операции на вершине стека «2», то перекладываем все операции имеющие более низкий или равный приоритет.

  3. Пройдя все, перекладываем из стека «2» в стек «1».

Ниже приведена таблица приоритетов операций (Таблица 2.).

Приоритет операции:

Операция:

0

=

1

(

2

+, -

3

*, /

  1. Таблица приоритетов операций.

Рассмотрим простой пример. На вход дано выражение: 3 + 4.

  1. Добавим 3 в стек «1».

  2. Помещаем + в стек «2».

  3. Добавим 4 в стек «1».

Мы прочитали всё выражение, теперь перекладываем все из стека «1» в стек «2». В нашем примере только +.

Получаем постфиксную форму выражения: 3 4 +.

Вычисление выражения, записанного в постфиксной форме


Алгоритм вычисления выражения в постфиксной форме.

  1. До тех пор пока приходят числа, кладем их в стек.

  2. Если пришла операция, то изымаем два числа с вершины стека и применяем к ним эту операцию.

  3. Продолжаем алгоритм до тех пор, пока не дойдем до конца строки.

Например, имеется строка с постфиксной записью: 34+.

  1. Кладем в стек элемент «3»;

  2. Кладем в стек элемент «4»;

  3. Пришел «+», применяем операцию сложение к двум числам с вершины стека.

Реализация двумерных клеточных автоматов


Окрестности, реализованные в данной лабораторной работе, описаны в пункте руководство пользователя (Руководство пользователя). В каждой клетке окрестности хранится 1 либо 0. Осуществляется проход по всем клеткам автомата, для каждой просчитывается новое значение. Например, есть поле шириной и высотой 3 клетки (Рис. 12).

1

0

1

0

1

0

1

0

1

  1. Пример начального состояния всех ячеек клеточного автомата.

Возьмем, например, окрестность Мура для подсчета следующего состояния. Тогда для клетки, выделенной желтым, окрестность будет состоять из клеток выделенных зеленым.

1

0

1

0

1

0

1

0

1

  1. Пример окрестности Мура.

Подсчитаем значение центральной клетки, как сумму всех клеток (0+0+0+0) окрестности по модулю 2, получим ноль, заменим значение центральной клетки. Далее последовательно пройдем по каждой клетке автомата и вычислим новое значение по заданному правилу перехода. Получим следующую конфигурацию клеточного автомата (Рис. 14).

0

1

0

1

0

1

0

1

0

  1. Клеточный автомат после первой итерации.

Если клетка является крайней, например, у нее нет соседней справа, то берется крайняя слева в этой же строке (Рис. 15).

1

0

1

0

1

0

1

0

1

  1. Пример зацикливания окрестности.

Заключение


Разработано и реализовано консольное приложение, позволяющее работать с клеточными автоматами, используя стек на списках. В данной программе освоена работа с библиотекой компьютерного зрения OpenCV, работа с классами, линейными односвязными списками, алгоритмом перевода в постфиксную форму и структурой данных «стек».

Литература





  1. Павловская Т.А. С/С++. Программирование на языке высокого уровня. - СПб.: Питер. - 2003. - 460с.

  2. Герберт Шилдт. Полный справочник по C++ = C++: The Complete Reference. — 4-е изд. — М.: Вильямс, 2011. — С. 800.

    .

Приложения

Приложение А. Файл исходного кода


#define ESC_KEY 27

#define DELAY 30

#define ENTER 13
const int width = 500, heigth = 500;

const char *winName = "Cell Automata";

const int thickness = 1;

int wStep, hStep, dimx, dimy;

Mat img;

void onMouseClick(int eventId, int x, int y,

int flags, void *userdata);

CellAutomata *CA;

int Mode;
int main()

{

int numIter = 0;

int tConf,b=0;

int neighbourhood;

char Str[80];

printf ("2D or 1D(1/2): ");

scanf ("%d", &Mode);

printf("size x ");

scanf("%d", &dimx);

printf("size y ");

scanf("%d", &dimy);

printf ("type of start conf (0-test, 1-random, 2-user) ");

scanf ("%d", &tConf);
wStep = (width - (dimx - 1) * thickness) / dimx;

hStep = (heigth - (dimy - 1) * thickness) / dimy;
if (Mode==1){

printf("type of neighbourhood (0-Neiman, 1-Mur, 2-Mvon, 3-User) ");

scanf("%d", &neighbourhood);

switch (neighbourhood) {

case 0: CA= new CellAutomata2DNeiman (dimx,dimy); break;

case 1: CA= new CellAutomata2DMur (dimx,dimy); break;

case 2: CA= new CellAutomata2DMvon (dimx,dimy); break;

case 3: printf("give rule");

scanf("%s", &Str);CA= new CellAutomata2DUser (dimx,dimy,Str); break;

default:

printf("type of neighbourhood is not correct");

getchar();

return 0;

}
switch (tConf){

case 1: (*CA).ramdomeConf();break;

case 2: (*CA).userConf();break;

case 0: (*CA).testConf();break;

default:

printf("type of conf is not correct");

getchar();

return 0;

}
char key = -1;

namedWindow(winName);

cvSetMouseCallback(winName, onMouseClick);

while (key != ESC_KEY)

{

// отображение сетки

img.release();

img.create(width, heigth, CV_32FC3);

int begin = 0;

for (int i = 1; i < dimx; i++)

{

begin = i * (wStep + thickness);

line(img, cvPoint(begin, 0), cvPoint(begin, heigth), CV_RGB(255, 111, 0),

thickness);

}

begin = 0;

for (int i = 1; i < dimy; i++)

{

begin = i * (hStep + thickness);

line(img, cvPoint(0, begin), cvPoint(width, begin), CV_RGB(255, 111, 0),

thickness);

}
for(int i=0; i

for (int j=0; j

if (((*CA).get(i*dimx+j))==1){

int rx=j*(hStep+thickness)+thickness;

int ry=i*(wStep+thickness)+thickness;

rectangle(img, cvRect(rx, ry, wStep, hStep), CV_RGB(255, 111, 0), CV_FILLED);

}

}

imshow(winName, img);
if (key!=-1){if (key==ENTER) b=1;

else b=0;}

if (b==0) key = waitKey();

else {key = waitKey(DELAY);}

numIter++;

(*CA).calNextConf();

}

}

Приложение Б. Заголовочный файл CellAutomata2D.h



#pragma once

#include

#include "CA.h"

#include "корейка.h"
class CellAutomata2D: public CellAutomata// двумерный клеточный автомат

{

protected:

int dimy;

virtual void calNextState (int x,int y)=0;

public:



void testConf ();

void ramdomeConf();

void userConf();

void calNextConf ();

};
class CellAutomata2DNeiman: public CellAutomata2D

{public: CellAutomata2DNeiman (int,int);

~CellAutomata2DNeiman();

void calNextState(int,int);

};
class CellAutomata2DMvon: public CellAutomata2D

{ public: CellAutomata2DMvon (int ,int );

~CellAutomata2DMvon();

void calNextState(int ,int );};
class CellAutomata2DMur: public CellAutomata2D

{ public: CellAutomata2DMur (int ,int );

void calNextState(int,int);

~CellAutomata2DMur();

};
class CellAutomata2DUser: public CellAutomata2D

{char* Polka, arr[13];

int size;

public: CellAutomata2DUser (int ,int, char*);

void calNextState(int,int);

~CellAutomata2DUser();

};

Приложение В. Заголовочный файл CA.h



#pragma once
#include
class state {

int n;

public:

state (int=0);

void changeState(int);

int getState();

};

class CellAutomata { // клеточный автомат

protected:

state *prevConf;

state *nextConf;

int dimx;

public:

virtual ~CellAutomata (){};

virtual void calNextConf ()=0;

virtual void testConf ()=0;

virtual void ramdomeConf()=0;

virtual void userConf()=0;

state *GetPrevConf(){

return(prevConf);

}

int get(int i) ;

void put(int i,int n);

};

Приложение Г. Исходный код Stack.cpp


#include "Stack.h"
Node::Node(char _data){

pNext=0;

data=_data;

}

void Node::SetNext(Node* _pNext){ pNext = _pNext; }

Node* Node::GetNext()const{ return pNext; }

char Node::GetData()const{ return data; }

Stack::Stack(char data){

pBegin = new Node(data) ;

c=0;

}

Stack::Stack(){ c=0; pBegin = NULL; }

int Stack::put(char _data){

try{

Node* tmp=pBegin;

pBegin = new Node(_data) ;

pBegin->SetNext(tmp);

c++;

return 0;

}

catch(...){ return 1; }

}

char Stack::get(){

try{

Node* tmp = pBegin->GetNext();

char tmpData = pBegin->GetData();

delete pBegin;

pBegin = tmp;

c--;

return tmpData;

}

catch(...){ return 1; }

}

int Stack::IsFull(){

if (pBegin==NULL) return 0;

Node* tmp = new Node(pBegin->GetData()) ;

if (tmp==NULL) return 1;

delete tmp;

return 0;

}

int Stack::IsEmpty(){

return pBegin==NULL;

}

Приложение Д. Исходный код Корейка.cpp


#include "корейка.h"
int prioritet(char a){

if ((a=='*')||(a=='/'))

return 3;

if ((a=='+')||(a=='-'))

return 2;

if (a=='(')

return 1;

if (a=='=')

return 0;

return 4;

};
void cO(char* Str, char* out){

Stack S1,S2;

for (int i=0;Str[i]!=0;i++){

if (Str[i]=='(') S2.put(Str[i]);

else if (Str[i]==')'){

char tmp=S2.get();

while ((tmp!='(')&&(S2.IsEmpty()!=1)){

S1.put(tmp);

tmp = S2.get();

}

}

else if (prioritet(Str[i])!=4){

if (S2.IsEmpty()) S2.put(Str[i]);

else{

char tmp=S2.get();

if (prioritet(Str[i])>prioritet(tmp)){

S2.put(tmp);

S2.put(Str[i]);

}

else{

while((prioritet(tmp)>=prioritet(Str[i]))&&(S2.IsEmpty()!=1)){

S1.put(tmp);

tmp = S2.get();

}

if (prioritet(tmp)>=prioritet(Str[i])) S1.put(tmp);

else S2.put(tmp);

S2.put(Str[i]);

}

}

}

else S1.put(Str[i]);

}

char t;

while(S2.IsEmpty()!=1)

{t=S2.get();

S1.put(t);

}

while(!S1.IsEmpty()){

out[S1.size()]=S1.get();

};

}
char Calculate(char a, char b, char c){

if (c=='+') return ((a+b)%2);

if (c=='-') return (abs(a-b)%2);

if (c=='*') return ((a*b)%2);

if (c=='/') {

if ((a==0)&&(b==0)) return (0) ;

if ((a==1)&&(b==1)) return (1);

if ((a==0)&&(b==1)) return (0);

if ((a==1)&&(b==0)) return (0);

};

}
char CalculateKoreyka (char *a, int size){

Stack S;
for (int i=0; i

if (prioritet(a[i])==4) S.put(a[i]);

else S.put(Calculate(S.get(), S.get(), a[i]));
return (S.get());

}


Добавить документ в свой блог или на сайт

Похожие:

Руководство пользователя 6 icon Руководство пользователя 6 0 (05. 05. 2014)
Инструкция по заполнению уп для Начальной ступени образования по новому стандарту 234
Руководство пользователя 6 icon Руководство пользователя администратор организации содержание
Вашему вниманию предлагается целый комплекс программных услуг для образовательных учреждений в рамках Всеукраинского школьного портала...
Руководство пользователя 6 icon Диссертация на соискание академической степени
Данная магистерская диссертация содержит введение, 5 глав и заключение, изложенных на 99 страницах машинописного текста. В работу...
Руководство пользователя 6 icon Руководство пользователя Государственная публичная научно-техническая библиотека России
Интернет серверов и Интернет комплексов. Система полностью отвечает международным требованиям, предъявляемым к подобного рода системам,...
Руководство пользователя 6 icon Руководство пользователя учитель школы краткое описание возможностей...
Вашему вниманию предлагается целый комплекс программных услуг для школы в рамках Всеукраинского школьного портала «класна оцінка»...
Руководство пользователя 6 icon Руководство пользователя 42 Сайт конкурса 42 Программная реализация...
Задачи, предлагаемые для проведения конкурса кио-2005 (конструируй, исследуй, оптимизируй) 26
Руководство пользователя 6 icon Руководство по аддиктологии ббк88. 4 Р84
Руководство предназначено для врачей-наркологов, психиатров, медицинских (кли­нических) психологов, оказывающих медико-психологическую,...
Руководство пользователя 6 icon Литература: Травматология: национальное руководство
Травматология: национальное руководство/ под ред. Г. П. Котельникова, С. П. Миронова. М.: Геотар-Медиа,2008. 808с
Руководство пользователя 6 icon Руководство по самозащите Боевая машина 1 ocr djvu Ego «Боевая машина:...
Главный акцент сделан при этом на выработке умения входить в надлежащее психическое состояние и на использовании в качестве оружия...
Руководство пользователя 6 icon Руководство по деповскому ремонту рд 32 цв 587 -2009
Настоящее руководство устанавливает единые требования к проведению деповского ремонта грузовых вагонов колеи 1520мм ремонтными структурными...
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции