Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Динамічні структури даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2014
Тип роботи:
Розрахункова робота
Предмет:
Обчислювальний практикум
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
/
Кафедра ЕОМ
Розрахунковова робота
на тему
"Динамічні структури даних"
з дисципліни
"Обчислювальний практикум"
Зміст
Зміст……………………………………………………………………………………...2
Завдання 1. АТД «СТЕК»……………………………………………………………....3
Умова задачі…………………………………………………………………3
Аналіз завдання………………………………………………………….…..3
Проектування алгоритму………………………………………………...….3
Програмна реалізація………………………………………………………..5
Результат виконання програми……………………………………………..8
Завдання 2. АТД «ЧЕРГА»……………………………………………………………..9
Умова задачі…………………………………………………………………9
Аналіз завдання………………………………………………………….…..9
Проектування алгоритму………………………………………………......10
Програмна реалізація………………………………………………………10
Результат виконання програми……………………………………………11
Завдання 3. АТД «СПИСОК»…………………………………………………………13
3.1 Умова задачі………………………………………………………………..13
3.2 Аналіз завдання………………………………………………………….…13
3.3 Проектування алгоритму………………………………………………......14
3.4 Програмна реалізація………………………………………………………14
3.5 Результат виконання програми……………………………………………16
Завдання 4. АТД «ДЕРЕВО»…………………………………………………………..17
Умова задачі………………………………………………………………..17
Аналіз завдання………………………………………………………….…17
Проектування алгоритму………………………………………………......18
Програмна реалізація………………………………………………………18
Результат виконання програми……………………………………………24
Висновок. …………………………………………………………………………….....24
Завдання 1
1.1 Умова задачі
Застосування АТД "СТЕК" до розв’язання прикладних задач
Обчислити вираз, представлений в постфіксній формі запису.
Аналіз завдання
Зворо́тній по́льський за́пис (зворотний бездужковий запис, постфіксна нотація, польський інверсний запис (ПОЛІЗ), англ. RPN — Reverse Polish Notation) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація.
Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов).
Основні операції для роботи зі стеком:
push ("заштовхнути елемент"): елемент додається в стек та розміщується в його верхівці. Розмір стеку збільшується на одиницю. При перевищенні розміру стека граничної величини, відбувається переповнення стека (англ. stack overflow)
pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow)
Додаткові операції (присутні не у всіх реалізаціях стеку):
isEmpty: перевірка наявності елементів в стеку; результат: істина (true), коли стек порожній.
isFull: перевірка заповненості стека. Результат: істина, коли додавання нового елементу неможливе.
clear: звільнити стек (видалити усі елементи).
top: отримати верхній елемент (без виштовхування).
size: отримати розмір (кількість елементів) стека.
swap: поміняти два верхніх елементи місцями.
Проектування алгоритму
На рис.1. зображено алгоритм обчислення виразу, представленого в постфіксній формі запису. Для всіх символів робимо наступне:
Якщо Аі число, то вкласти його у стек;
Якщо Аі оператор, то:
Витягуємо із стеку два числа;
Виконуємо дію із числами і результат вкладаємо в стек;
Якщо Аі є функцією то:
Витягуємо із стеку одне число;
Визначаємо значення функції із відповідним аргументом та поміщаємо результат у стек;
В кінці роботи в стеку знаходитиметься результат виразу.
/
Рис 1. Алгоритм обчислення в постфіксній формі
Програмна реалізація
#include <iostream>
#include <locale>
#include <string>
#include <cmath>
using namespace std;
struct Node
{
char data;
Node *next;
};
class Stack
{
private:
Node *Head;
public:
Stack()
{
Head = NULL;
}
void push(char val)
{
Node *Ptr = new Node;
Ptr -> data = val;
if(Head == NULL)
{
Head = Ptr;
Ptr -> next = NULL;
}
else
{
Node *temp = Head;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = Ptr;
Ptr -> next = NULL;
}
}
void pop()
{
Node *temp = Head, *temp1;
if(Head != NULL)
{
if(Head -> next == NULL)
{
delete Head;
Head = NULL;
}
else
{
while(temp -> next != NULL)
{
temp1 = temp;
temp = temp -> next;
}
delete temp;
temp = temp1 -> next = NULL;
}
}
}
bool isEmpty()
{
return Head == NULL;
}
char top()
{
Node *Ptr = Head;
if(Head != NULL)
{
if(Ptr -> next == NULL)
return Ptr -> data;
else
{
while(Ptr ->next != NULL)
Ptr = Ptr -> next;
return Ptr -> data;
}
}
else
return NULL;
}
void Print()
{
Node *Ptr = Head;
if(Head == NULL)
cout << "Стек прожнiй!\n";
else
{
while(Ptr != NULL)
{
if(Ptr ->data == 'n'){
cout << '0';
Ptr = Ptr ->next;
}
else if(Ptr -> data == '#'){
cout << "-";
Ptr = Ptr ->next;
}
else{
cout << Ptr -> data;
Ptr = Ptr -> next;
}
}
}
}
};
int translationToNumber(char *number)
{
int size = strlen(number) - 1;
int chislo = 0;
for(int i = 1, j = size; j >= 0; i *= 10, j--)
chislo += (number[j] - '0') * i;
return chislo;
}
int main()
{
setlocale(LC_ALL, "Ukrainian");
Stack stack;
Node *Ptr = NULL, *Ptr1 = NULL;
const int size = 256;
int size_f, j = 0, size_p = 0, size_i,
resultat, chislo_l, chislo_r;
char postfix[size] = "",
value[size] = "", prom_str[size] = "",
l_push[size] = "", R_push[size] = "";
cout << "Введiть вираз: ";
cin.getline(postfix, sizeof(postfix), '\n');
size_f = strlen(postfix);
for(int i = 0; i < size_f; i++)
{
if(postfix[i] <= '9' && postfix[i] >= '0' || postfix[i] == ' ')
stack.push(postfix[i]);
else if(postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/' || postfix[i] == '^')
{
if(postfix[i] == '-')
if(postfix[i+1] <= '9' && postfix[i+1] >= '0' ){
stack.push('#');
continue;
}
if(stack.top() == ' ' )
stack.pop();
j = 0;
while(stack.top() != ' ' && stack.top() != NULL && stack.top() != '#' && stack.top() != 'n')
{
l_push[j++] = stack.top();
stack.pop();
}
strrev(l_push);
chislo_l = translationToNumber(l_push);
if(stack.top() == 'n'){
chislo_l = 0;
stack.pop();
}
else if(stack.top() == '#'){
chislo_l *= -1;
stack.pop();
}
stack.pop();
memset(l_push, 0, 256);
if(stack.top() == ' ' )
stack.pop();
j = 0;
while(stack.top() != ' ' && stack.top() != NULL && stack.top() != '#' && stack.top() != 'n')
{
R_push[j++] = stack.top();
stack.pop();
}
strrev(R_push);
chislo_r = translationToNumber(R_push);
if(stack.top() == 'n'){
chislo_l = 0;
stack.pop();
}
else if(stack.top() == '#'){
chislo_r *= -1;
stack.pop();
}
memset(R_push, 0, 256);
switch(postfix[i]){
case '+':
resultat = chislo_r + chislo_l;
break;
case '-':
resultat = chislo_r - chislo_l;
break;
case '*':
resultat = chislo_r * chislo_l;
break;
case '/':
if(chislo_l == 0){
cout << "На нуль дiлити не можна!";
goto End;
}
resultat = chislo_r / chislo_l;
break;
case '^':
resultat = pow(chislo_r , chislo_l);
break;
}
j = 0;
if( resultat == 0)
stack.push('n');
else{
if(resultat < 0){
resultat *= -1;
while(resultat >= 1)
{
value[j++] = ((resultat % 10) + '0');
resultat = resultat / 10;
}
strrev(value);
stack.push('#');
for(int s = 0; s < j; s++)
stack.push(value[s]);
}
else
{
while(resultat >= 1)
{
value[j++] = ((resultat % 10) + '0');
resultat = resultat / 10;
}
strrev(value);
for(int s = 0; s < j; s++)
stack.push(value[s]);
}
}
}
}
cout << "Результат виконання: ";
stack.Print();
End:
cout << "\n\n";
system("pause");
return 0;
}
Результат виконання програми
На рис.2. зображено результат виконання програми. Вводимо вхідний рядок,
програма видає результат обчислення.
/
Рис 2. Результат виконання програми.№1
Завдання 2
2.1 Умова задачі
Застосування АТД " ЧЕРГА " до розв’язання прикладних задач
У магазині стоїть черга з m покупців. Час обслуговування покупця з черги – це випадкове ціле число в діапазоні від 1 до t1. Час додавання нового покупця до черги - це випадкове ціле число в діапазоні від 1 до t2.
Промоделювати стан черги:
а) вивести повідомлення про час виникнення подій ( обслуговування та додавання покупця ) за період часу T (T >> t1, T >> t2);
б) показати залишок черги;
в) розв’язати задачу, передбачивши, що через випадковий час від 1 до t3 до початку черги додається „пільговий” покупець, який обслуговується першим, а через випадковий час від 1 до t4 не витримує та йде з черги останній покупець.
2.2 Аналіз завдання
Черга — динамічна структура даних, що працює за принципом «перший прийшов — перший пішов» (англ. FIFO — first in, first out). У черги є голова (англ. head) та хвіст (англ. tail). Елемент, що додається до черги, опиняється в її хвості. Елемент, що видаляється з черги, знаходиться в її голові.
Така черга повністю аналогічна звичній «базарній» черзі, в якій хто перший встав в неї, той першим буде обслуженим.
Основні операції з чергою:
англ. enqueue — "поставити в чергу". Операція додавання елемента в "хвіст" черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення (англ. queue overflow).
англ. dequeue — "отримання з черги". Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація "незаповнення" (англ. queue underflow).
2.3 Проектування алгоритму
На рис. 3 зображена блок-схема алгоритму головної функції, яка відображає стан черги в даний момент часу.
/
Рис 3. Алгоритм виконання програми №2
2.4 Програмна реалізація
#include <iostream>
#define N 1000
using namespace std;
#include "Queue.h"
#include <string.h>
#include <time.h>
int _tmain(int argc, _TCHAR* argv[])
{
setlocale (0, "");
srand(time(0));
int now_time = 0;
int T;
int number = 1;
int temp;
Queue q1;
int
m, t1, t2, t3, t4;
cout << "Введiть вхiднi данi - m, t1, t2, t3, t4" << endl;
cin >> m >> t1 >> t2 >> t3 >> t4;
cout << "Введiть час Т - час, впродовж якого проводитиметься дослiдження" << endl;
cin >> T;
int now_t1 = rand()%(t1) + 1;
int now_t2 = rand()%(t2) + 1;
int now_t3 = rand()%(t3) + 1;
int now_t4 = rand()%(t4) + 1;
for(int i = 0; i < m; i++)
{
q1. push(number);
cout << "Час " << now_time << " - додався покупець " << number << endl;
number++;
}
while(now_time < T)
{
if(now_time > now_t1)
{
temp = q1.front();
q1.pop();
now_t1 += rand()%(t1) + 1;
cout << "Час " << now_time << " - обслужили покупця " << temp << endl;
q1.show();
}
if(now_time > now_t2)
{
q1.push(number);
now_t2 += rand()%(t2) + 1;
cout << "Час " << now_time << " - додався покупець " << number << endl;
number++;
q1.show();
}
if(now_time > now_t3)
{
q1.push_front(number);
now_t3 += rand()%(t3) + 1;
cout << "Час " << now_time << " - додався покупець(пiльговий) " << number << endl;
number++;
q1.show();
}
if(now_time > now_t4)
{
temp = q1.last1();
q1.pop_last();
now_t4 += rand()%(t4) + 1;
cout << "Час " << now_time << " - невитримав i пiшов покупець " << temp << endl;
q1.show();
}
now_time++;
}
system("pause");
return 0;
}
2.5 Результат виконання програми
На рис.4. зображено результат виконання програми. Вводимо вхідні дані і програма ілюструє стан чергу протягом досліджуваного часу.
/
Рис 4.Результат виконання програми №2
Завдання 3
3.1 Умова завдання
Застосування АТД " СПИСОК " до розв’язання прикладних задач
Поліном від трьох змінних ( X , Y , Z ) представити у вигляді циклічного списку, в якому кожний вузол має п’ять полів: одне – для коефіцієнта члена поліному , друге – для показника степеня змінної X , третє – для показника степеня змінної Y, четверте – для показника степеня змінної Z, п’яте – для вказівника на наступний вузол списку. Елементи списку мають бути впорядковані спочатку по зменшенню степеня Х, пізніше по зменшенню степеня Y, а після цього по зменшенню степеня Z. Структура збереження поліномів повинна забезпечувати ефективне виконання такої операції над ними:
Обчислення полінома по заданим значенням X , Y , Z .
3.2 Аналіз завдання
Лінійний список – це скінчена послідовність однотипних елементів (вузлів), можливо, з повтореннями. Список розташовується в пам'яті довільним чином. Кожний вузол однонаправленого лінійного зв'язаного списку містить вказівник на наступний вузол списку, що дозволяє переміщуватись вперед по списку. Кожний вузол двонаправленого лінійного зв'язаного списку містить вказівники на попередній і наступний вузли списку, що дозволяє переміщуватись по списку вперед та назад.
За визначенням, список — це послідовність з n≥0 елементів X[1],X[2], … X[n], для якої виконується наступна умова: якщо n>0 та X[1] — перший елемент у списку, а X[n] — останній, то k-й елемент розташований між X[k-1] та X[k+1] елементами для усіх 1<k<n.
З такими структурами даних виконуються наступні операції:
отримання k-го елемента списку для читання чи запису в нього нового значення;
додавання нового елемента в будь-яку позицію в списку;
видалення елемента списку;
об'єднання в одному списку двох або більше лінійних списків;
розбиття списку на два або більше фрагментів;
створення копії списку;
визначення кількості елементів в списку;
сортування елементів списку;
пошук елемента, що задовольняє певним критеріям.
3.3 Проектування алгоритму
На рис. 5 зображена блок схема алгоритму головної функції, яка додає елементи многочлена і обчислює його.
/
Рис 5. Алгоритм виконання програми №3
3.4 Програмна реалізація
#include <iostream>
#include <cstdlib>
using namespace std;
struct Node
{
float cof;
int nX;
int nY;
int nZ;
Node *Next;
};
class List
{
Node *Head,*Tail;
int size;
public:
List():Head(NULL),Tail(NULL),size(0){};
~List();
void Add(float cof, int nX, int nY, int nZ);
void Show(int temp);
int Count();
double Calc(int tmp, float X1, float Y1, float Z1);
};
List::~List()
{
while (size!=0)
{
Node *temp=Head->Next;
delete Head;
Head=temp;
size--;
}
}
int List::Count()
{
return size;
}
void List::Add(float coef, int eX, int eY, int eZ)
{
size++;
Node *temp=new Node;
temp->Next=Head;
temp->cof=coef;
temp->nX=eX;
temp->nY=eY;
temp->nZ=eZ;
if (Head!=NULL)
{
Tail->Next=temp;
Tail=temp;
}
else Head=Tail=temp;
}
void List::Show(int temp)
{
Node *tempHead=Head;
temp=size;
while (temp!=0)
{
cout<<tempHead->cof<<"*"<<"X"<<"^"<<tempHead->nX<<" *"<<"Y"<<"^"<<tempHead->nY<<" *"<<"Z"<<"^"<<tempHead->nZ;
if(temp > 1)
cout <<" + ";
tempHead=tempHead->Next;
temp--;
}
}
double List::Calc(int tmp, float X1, float Y1, float Z1)
{
float res=0;
Node *tempHead1 = Head;
tmp = size;
while(tmp !=0 )
{
res += tempHead1->cof*pow(X1,tempHead1->nX)*pow(Y1,tempHead1->nY)*pow(Z1, tempHead1->nZ);
tempHead1=tempHead1->Next;
tmp--;
}
return res;
}
void main()
{
float X, Y, Z;
List lst;
lst.Show(lst.Count());
lst.Add(1,0,2,1);
lst.Add(3,2, 4,1);
lst.Add(2, 1, 0, 4);
lst.Show(lst.Count());
cout<<"\nEnter the X, Y, Z: ";
cin >> X >> Y >> Z;
cout << endl << "Res = "<< lst.Calc(lst.Count(), X, Y, Z)<<endl;
cout<<endl;
system("PAUSE");
}
3.5 Результат виконання програми
На рис. 6 зображений результат виконання програми. Вводимо вхідні дані і програма виводить результат обчислення полінома.
/
Рис 6.Результат виконання програми№3
Завдання 4
4.1 Умова задачі
Написати програму реалізації гри Го-Моку. Це нескладна позиційна гра, яка відома зі стародавніх часів і, напевно, вперше виникла у Японії. Ця гра схожа на хрестики-нолики, але набагато цікавіша. За класичними правилами грають на дошці розміром 19x19 клітин (в програмі реалізуйте альтернативні варіанти: скорочений 9x9 та розширений 29x29 клітин). Гравці ставлять свої фішки на вільні клітини дошки по черзі. Виграє той, кому першому пощастить побудувати власну лінійку з п’яти фішок – горизонтальну, вертикальну або діагональну.
4.2 Аналіз завдання
Дерево - одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:
існує один відокремлений вузол — корінь (root) дерева;
інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин в свою чергу є деревом. Дерева T1…Tm мають назву піддерев (subtrees) даного кореня.
Для того, щоб реалізувати дане завдання, я створив клас, який відтворює структуру даних типу «Дерево» і написав головну функцію, яка сканує гральну дошку на наявність переможця. На рис.7. схематично зображено зв’язки елементів гральної дошки. Кожен елемент має в собі значення і вісім вказівників на сусідні елементи. Крайні елементи вказують на NULL.
/
Рис 7. Зв’язки елементів.
4.3 Проектування алгоритму
На рис.8. зображена блок-схема алгоритму головної функції Scaner(). Функція після кожного ходу перевіряє гральну дошку на наявність виграшу. Вона проходить кожен елемент і перевіряє, чи існує в будь-якому напрямі послідовність з п’яти однакових фішок. Якщо немає вільних клітинок і виграшу, то функція виводить нічию./
Рис 8.Алгоритм роботи головної функції.
4.4 Програмна реалізація
Клас Gomoku містить вказівник на перший елемент (1А), дві змінні, які вказують переможця, змінну розміру дошки і методи:
void Board() - будує гральну дошку.
void PrintBoard() – друкує гральну дошку.
char Scanner() – сканує дошку на наявність переможця чи нічиї.
bool ShowStep(int v, char h, int who) – перевіряє, чи зайнята дана клітинка.
Кожен елемент реалізований у вигляді структури, що містить ім’я, горизонтальне вертикальне положення елемента, та вісім вказівників на сусідні елементи.
Код програми:
#include"Gomoku.h"
using namespace std;
int main()
{
setlocale(LC_ALL, "Ukrainian");
Ret:
Gomoku g;
system("cls");
cout << "Вiтаю в грi Гомоку! Введiть розмiр гральної дошки: ";
cin >> g.size;
while(g.size < 5||g.size > 62){
cout << "Розмiр не коректний. Будь ласка введiть iнше число: ";
cin >> g.size;
}
g.Board();
int who = 1;
system("cls");
while(who != 100){
g.PrintBoard();
if(who % 2 == 1){
who = 1;
cout << endl << "Гравець A\n";
}
else{
who = 2;
cout << endl << "Гравець B\n";
}
cout << "Введiть число та лiтеру клiтинки: ";
int vert; char hor;
cin >> vert >> hor;
while(vert >= g.size || vert < 0 || hor < 'A' || hor >= 65+g.size){
cout << "Ви ввели невiрнi значення! Будь ласка введiть iншi значення: ";
cin >> vert >> hor;
}
while(g.ShowStep(vert, hor, who) == false){
cout << "Ця клiтинка вже зайнята! Введiть iншi значення: ";
cin >> vert >> hor;
}
who++;
system("cls");
if(g.Scanner() == 'A'){
cout << "\t ВIТАЮ! Гравець А, Ви виграли!\n\n";
break;
}
else if(g.Scanner() == 'B'){
cout << "\t Вiтаю, гравець B, Ви виграли!\n\n";
break;
}
else if(g.Scanner() == 'D'){
cout << "\t Нiчия!\n\n";
break;
}
}
g.PrintBoard();
cout << "\nБажаєте зiгрази знову? (Так - Y, Нi - N) ";
char ret;
cin >> ret;
switch (ret)
{
case 'Y':
goto Ret;
case 'N':
return 0;
}
}
#include <iostream>
#define SELECT_PLAYER_A 1;
#define SELECT_PLAYER_B 2;
#define SELECT_PLAYER_NOT 0;
struct Node
{
char data;
int vert;
int hor;
Node *up_left;
Node *up;
Node *up_right;
Node *center_left;
Node *center_right;
Node *down_left;
Node *down;
Node *down_right;
};
class Gomoku{
private:
Node *Head;
int WinA;
int WinB;
public:
Gomoku(){
Head = new Node;
Head->vert = 0;
Head->hor = 0;
Head->center_left = NULL;
Head->up_left = NULL;
Head->down_left = NULL;
Head->up = NULL;
Head->up_right = NULL;
WinA = 0;
WinB = 0;
};
~Gomoku(){delete Head;};
void Board();
void PrintBoard();
char Scanner();
void Step(int h, int v);
bool ShowStep(int v, char h, int who);
int size;
};
#include "Gomoku.h"
#include <iostream>
using namespace std;
void Gomoku::Board()
{
Head->data = '_';
Node *Ptr = Head;
Node *Ptr1, *Ptr2;
for(int i = 0; i < size; i++){
if(i == size-1)
Ptr->down = NULL;
else{
Ptr->down = new Node;
Ptr = Ptr->down;
Ptr->data = '_';
Ptr->vert = i+1;
Ptr->hor = 0;
}
}
Ptr = Head;
Node *tmp = Ptr;
Ptr->up = NULL;
Ptr = Ptr->down;
while(tmp->down != NULL){
Ptr->up = tmp;
Ptr = Ptr->down;
tmp = tmp->down;
}
Ptr = Head;
Head->up = Ptr->up;
Node *PtrI = Head;
for(int j = 0; j < size; j++){
PtrI = Ptr;
for(int i = 0; i < size; i++){
if(j == 0){
Ptr->up = NULL;
Ptr->up_left = NULL;
Ptr->up_right = NULL;
}
if(i == 0){
Ptr->center_left = NULL;
Ptr->up_left = NULL;
Ptr->down_left = NULL;
}
if(j == size-1){
Ptr->down = NULL;
Ptr->down_left = NULL;
Ptr->down_right = NULL;
}
if(i == size-1){
Ptr->center_right = NULL;
Ptr->up_right = NULL;
Ptr->down_right = NULL;
}
else {
Ptr->center_right = new Node;
Ptr = Ptr->center_right;
Ptr->data = '_';
Ptr->vert = j;
Ptr->hor = i+1;
}
}
Ptr = PtrI;
tmp = Ptr;;
Ptr->center_left = NULL;
Ptr = Ptr->center_right;
while(tmp->center_right != NULL){
Ptr->center_left = tmp;
Ptr = Ptr->center_right;
tmp = tmp->center_right;
}
Ptr = PtrI;
if(j != 0){
Ptr1 = Ptr->up;
Ptr2 = Ptr;
for(int i = 0; i < size-1; i++){
Ptr1 = Ptr1->center_right;
Ptr2 = Ptr2->center_right;
Ptr1->down = Ptr2;
Ptr2->up = Ptr1;
Ptr1->center_left->down_right = Ptr2;
Ptr2->up_left = Ptr1->center_left;
Ptr1->down_left = Ptr2->center_left;
Ptr2->center_left->up_right = Ptr1;
}
}
Ptr = PtrI;
Ptr = Ptr->down;
}
}
void Gomoku::PrintBoard()
{
Node *Ptr = Head;
Node *HeadI = Head;
cout << " ";
for(char i = 'A'; i < size+65; i++)
cout << i << " ";
cout << endl;
for(int i = 0; i < size; i++){
if(i < 10)
cout << "0" << i << " ";
else
cout << i<< " ";
for(int j = 0; j < size; j++){
cout << Ptr->data << " ";
Ptr = Ptr->center_right;
}
cout << endl;
HeadI = HeadI->down;
Ptr = HeadI;
}
}
bool Gomoku::ShowStep(int v, char h, int w)
{
Node *PtrP = Head;
while(PtrP->vert != v)
PtrP = PtrP->down;
while(PtrP->hor+65 != h)
PtrP = PtrP->center_right;
if(PtrP->data == 1 || PtrP->data == 2)
return false;
else {
if(w == 1){
PtrP->data = SELECT_PLAYER_A;}
else
PtrP->data = SELECT_PLAYER_B;
return true;
}
}
char Gomoku::Scanner()
{
Node *Ptr = Head;
Node *HeadI = Head;
Node *tmp = Head;
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(Ptr->data == 1){
tmp = Ptr;
while(Ptr != NULL && Ptr->data == 1){
WinA++;
Ptr = Ptr->center_right;
}
if(WinA == 5)
return 'A';
WinA = 0;
Ptr = tmp;
}
if(Ptr->data == 1){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 1){
WinA++;
Ptr = Ptr->down_right;
}
if(WinA == 5)
return 'A';
WinA = 0;
Ptr = tmp;
}
if(Ptr->data == 1){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 1){
WinA++;
Ptr = Ptr->down;
}
if(WinA == 5)
return 'A';
WinA = 0;
Ptr = tmp;
}
if(Ptr->data == 1){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 1){
WinA++;
Ptr = Ptr->down_left;
}
if(WinA == 5)
return 'A';
WinA = 0;
Ptr = tmp;
}
//////////////////////////////////////
if(Ptr->data == 2){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 2){
WinB++;
Ptr = Ptr->center_right;
}
if(WinB == 5)
return 'B';
WinB = 0;
Ptr = tmp;
}
if(Ptr->data == 2){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 2){
WinB++;
Ptr = Ptr->down_right;
}
if(WinB == 5)
return 'B';
WinB = 0;
Ptr = tmp;
}
if(Ptr->data == 2){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 2){
WinB++;
Ptr = Ptr->down;
}
if(WinB == 5)
return 'B';
WinB = 0;
Ptr = tmp;
}
if(Ptr->data == 2){
tmp = Ptr;
while( Ptr != NULL && Ptr->data == 2){
WinB++;
Ptr = Ptr->down_left;
}
if(WinB == 5)
return 'B';
WinB = 0;
Ptr = tmp;
}
Ptr = Ptr->center_right;
}
HeadI = HeadI->down;
Ptr = HeadI;
}
int draw = 0;
Ptr = Head;
HeadI = Head;
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
if(Ptr->data == '_')
draw++;
Ptr = Ptr->center_right;
}
HeadI = HeadI->down;
Ptr = HeadI;
}
if(draw == 0)
return 'D';
return 0;
}
06.04.2015 11:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора