Проектирование игры в шахматы
Министерство
образования и наук Российской Федерации
НОВОСИБИРСКИЙ
ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА
ПРИКЛАДНОЙ МАТЕМАТИКИ
Курсовая
работа
по
практикуму на ЭВМ: Структуры данных и алгоритмы
Факультет
прикладной
математики и информатики
Группа ПМИ-22
Студентка Малыгина
Д.Н.
Преподаватель
Тракимус Ю.В.
Новосибирск
1. Условие
задачи
Задано описание шахматной позиции в обычной
шахматной нотации. Например, «белые: Кр g1,
Л f1, пп f2,
g2, h3;
чёрные: Кр b8, К e5,
С e6, Ф a2,
пп a7, b7».
По описанию позиции напечатать изображение этой позиции, содержащее поле,
разбитое на клетки подходящего размера, внутри которых записано название фигуры
и её цвет (для занятых в позиции клеток). Определить все возможные ходы фигур.
Переместить фигуру на возможное для неё место. шахматная позиция фигура ход
2. Анализ
задачи
2.1
Исходные данные задачи
C = (B, W)
- (описание шахматной позиции)
сложная величина состоящая из 2-х эл. B и W
= (N, Fj, Ki) ∪ {∅ }
- (фигуры чёрного цвета) сложная
величина состоящая из 2-х эл. F, K или пустого множества
Fj - шахматная фигура j = 1, 16
= (Xi, Yj) Ki - координата шахматной
фигуры i = 1, 64∈ {‘a’, …, ‘h’} i = 1, 8 координата по x
Yj ∈ {‘1’, …, ‘8’} j = 1, 8 координата по y
W = (N, Fj, Ki) ∪ {∅ }
W - (фигуры белого цвета) сложная величина состоящая из 2-х эл. F,
K или пустого множества
Fj - шахматная фигура j = 1, 16
= (Xi, Yj) Ki - координата шахматной
фигуры i = 1, 64∈ {‘a’, …, ‘h’} i = 1, 8 координата по x
Yj ∈ {‘1’, …, ‘8’} j = 1, 8 координата по y
2.2
Результат
D = (T,
n) ∪ {∅ }
D - сложная величина состоящая из 2-х эл. или пустого множества
T = {ti | ti =(Ns, Xj,
Yi) i = 1,32}
Т - вид в котором шахматная фигура,
включая её координаты, представлена в таблице
Ns - номер шахматной фигуры, под которым она обозначена в в таблице s = 1,32
Xj - номер под которым координата по X , шахматной фигуры, обозначена в в
таблицеj = 1, 8
Yi - номер под которым координата по Y, шахматной фигуры, в таблицеi = 1, 8
n - величина обозначающая фактическое количество элементов Т, n = 1,32
2.3
Решение
Основное решение поставленной задачи составит в
нахождении соответствующих значений входной величины т.е. все возможные
варианты ходов фигуры
Формальная постановка задачи
– определение фигуры (сама фигура,
цвет )
– в зависимости от определённой
фигуры, выбор одного из нескольких алгоритмов решения
– изменение итоговых данных
3. Структуры
исходных данных и результатов задачи
3.1 Входные
данные
Внешнее представление:
С - описание шахматной
позиции, представлена в виде 2-х элементов отделённых друг от друга ' ;
'
1 элемент: В - фигуры чёрного цвета,
состоит из 2-х элементов отделённых друг от друга запятыми и пробелами
эл. F - шахматная фигура
(последовательность заглавных, строчных букв не более чем из 2-х символов)
эл. K - координата шахматной фигуры
(последовательность из 2-х символов:
первый - строчная латинская буква,
второй - цифра)
элемент: W - фигуры белого цвета, состоит из
2-х элементов отделённых друг от друга запятыми и пробелами
1 эл. F - шахматная фигура (последовательность
заглавных, строчных букв не более чем из 2-х символов)
эл. K - координата шахматной фигуры
(последовательность из 2-х символов:
первый - строчная латинская буква,
второй - цифра)
Внутреннее представление:
С
представлено, по частям в виде символьного массива
3.2 Выходные
данные
Внешнее представление:
Изображение, на котором представлена шахматная
доска с шахматными фигурами белого и чёрного цветов
Внутреннее
представление:
Статическая таблица, состоящая из
двух частей:
1-я часть список из трёх эл. (номер
фигуры, координата по Х, координата по Y )
2-я часть n - фактическое количество эл. в
таблице
– структура
таблицы
elem
{chessmanNo;x;y;
}work
{table [32];n;
}
4.
Укрупнённый алгоритм решения задачи
{= 0;(выбор фигуры)
{(белые)= 1;(королль)
//возможные ходы(a, b, flg);(ферзь)
//возможные ходы(a, b, flg);(слон)
//возможные ходы
bishop(a, b, flg);(ладья)
//возможные ходы(a, b, flg);(конь)
//возможные ходы(a, b, flg);(пешка)
//возможные ходы(a, b, flg);
}
//перенос выбраной фигуры
{
if(место занято)
срубить фигуру;
переместить фигуру;
}
}
5. Структура
программы
Текст программы разбит на четыре модуля.
Модуль 1 содержит функции решения основных
подзадач и определения входных и выходных данных.
Модуль 2 содержит функции графического вывода данных.
Модуль 3 содержит объявление структур и
подпрограмм.
Модуль 4 содержит вспомогательные функции,
реализующие основной алгоритм решения задачи.
5.1
Модуль 1
Главная функция main:
назначение:
определения входных и выходных данных задачи.
прототип: void
main()
5.2
Модуль 2
процедура input_fl
назначение:
ввод из файла обозначения фигур
привычных пользователю
инициализация структур: color_1, color_2
прототип: void
input_fl(color_1 *B, color_2 *W)
процедура initchess
- назначение:
инициализация шахматных фигур
(фигуры видные пользователю)
прототип: void initchess()
процедура figchess
назначение: задаем место фигуры на
изображении видном пользователю
i- фигура, y, x - координаты
прототип: void figchess(int i, int y,int x)
процедура myalg
назначение: подпрограмма связывающая
алгоритм решения задачи и вывод результата
прототип: void myalg()
процедура InitializeComponent
назначение: инициализация компонент
относящихся к выводу результата
- прототип: void
InitializeComponent(void)
процедура
clik
- назначение: подпрограмма
связывающая нахождение возможных ходов
- прототип: void
clik(int a, int b, stack **course)
5.3
Модуль 3
содержит объявление структур:
color_1, color_2 (структуры содержащие обозначение фигур удобных пользователю и
их соответствующее обозначения в программе),(таблица содержащая результат), stack
(стек для хранения возможных ходов)
содержит объявление процедур:
myscanf, king, queen, bishop, rook, kNight, pawn,
in_stack
содержит объявление функций: occupied_space,
out_stack
5.4
Модуль 4
функция searchBlack
- назначение: поиск номера,
соответствующего шахматной фигуре, под которые данная фигура известна программе
- прототип:
searchBlack(char *s, color_1 B)
B - объявление структуры содержащей
информацию о фигурах чёрного цвета (входной параметр)- символьный массив
содержащий обозначение фигуры
данная функция возвращает номер под
которые данная фигура известна программе
функция searchWhite
назначение: поиск номера,
соответствующего шахматной фигуре, под которые данная фигура известна программе
- прототип: int
searchWhite(char *s, color_2 W)
W - объявление структуры содержащей
информацию о фигурах белого цвета (входной параметр)- символьный массив
содержащий обозначение фигуры
данная функция возвращает номер под
которыми данная фигура известна программе
процедура myscanf
назначение: считывание
пользовательского обозначения фигур
- прототип: void
myscanf(color_1 B, color_2 W, work *el)
возвращает указатель на таблицу с
основным результатом программы
процедура king
назначение: определение возможных
ходов короля
-прототип: void
king(stack **B, int a, int c, int f, work ell)
процедура queen
назначение: определение возможных
ходов ферзя
-прототип: void
queen(stack **B, int a, int c, int f,work ell)
процедура bishop
назначение: определение возможных
ходов слона
-прототип: void
bishop(stack **B, int a, int c, int f, work ell)
процедура rook
назначение: определение возможных
ходов ладьи
-прототип: void
rook(stack **B, int a, int c, int f, work ell)
процедура kNight
назначение: определение возможных
ходов коня
-прототип: void
kNight(stack **B, int a, int c, int f, work ell)
процедура pawn
назначение: определение возможных
ходов пешки
-прототип: void
pawn(stack **B, int a, int c, int f,work ell)
процедура in_stack
назначение: операция положить в стек
-прототип: void
in_stack(stack **Q, int x_1, int y_1)
функция out_stack
назначение: операция положить в стек
-прототип: int
out_stack(stack**Q, int *x_1, int *y_1)
5.5 Структура программы по управлению
6.
Текст
программы
/*chessman.h*/
#include
"StdAfx.h"
#include<string.h>
#include <stdio.h>
#include<locale.h>
#include
"chessman.h"*fl, *fll, *fll2, *input;
//Координаты по xx [] =
"abcdefgh";
//Координаты по yy [] =
"87654321";
void openfile(work ell)
{((fll =
fopen("fll.txt", "w")) == NULL)("error");{(int i
= 0; i<= ell.n; i++){(fll,"%d
",ell.table[i].chessmanNo);(fll,"%d
",ell.table[i].x);(fll,"%d ",ell.table[i].y);
}(fll);
}
}closefile(work *ell)
{((fll =
fopen("fll.txt", "r")) == NULL)("error");{(int i
= 0; fscanf(fll,"%d ",&(ell->table[i].chessmanNo)) != EOF;
i++){(fll,"%d ",&(ell->table[i].x));(fll,"%d
",&(ell->table[i].y));>n = i;
}(fll);
}
}openfile_stakc(stack
**B)
{((fll2 =
fopen("fll2.txt", "w")) == NULL)("error");{f,
v;(out_stack(&(*B), &f, &v)){(fll,"%d
",f);(fll,"%d\n",v);
}(fll2);
}
}closefil_stakc(stack
**B)
{((fll2 =
fopen("fll2.txt", "r")) == NULL)("error");{p,
r;(fscanf(fll2,"%d ",&p) != EOF){(fll,"%d
",&r);_stack(&(*B), p, r);
}(fll2);
}
}
//поиск по чёрным фигурам
int searchBlack(char *s,
color_1 B)
{(int k = 0; k<16;
k++){(!strcmp(B.Bcolor[k].chessman,s))B.Bcolor[k].No;
}-1;
}
//поиск по белым фигурамsearchWhite(char
*s, color_2 W)
{(int k = 0; k<16;
k++){(!strcmp(W.Wcolor[k].chessman,s))W.Wcolor[k].No;
}-1;
}
//считывание обозначение пользователяmyscanf(color_1
B, color_2 W, work *el)
{((input =
fopen("input.txt", "r")) == NULL)("error");{wrk,
i;>n = 0;sym[5],chessm[3],chessman[3], slovo[8], same = '0', sign[] =
";";
// Считываем информацию о фигурах из
файла
while(fscanf(input,"%s",&slovo)
!= EOF)
{
//чёрные фигуры(strcmp(B.chessBlack,
slovo) == 0)
{
//считываем до
;(input,"%s",&sym);
while(sym[0] != sign[0])
{
// координата(sym[1]
>= '0' && sym[1] <= '9')
{
//если одинаковые фигуры(same != '0')
{(chessm,chessman);(chessm,&same);=
searchBlack(chessm, B);>table[el->n].chessmanNo = wrk;
//выясняем координату по x= 0;
while(sym[0] !=
x[i])++;>table[el->n].x = i;
//выясняем координату по y= 0;
while(sym[1] !=
y[i])++;>table[el->n].y = i;
//переходим к следующему элементу
таблицы>n++;++;
}
{
//выясняем координату по x
i = 0;(sym[0] !=
x[i])++;>table[el->n].x = i;
//выясняем координату по y= 0;
while(sym[1] !=
y[i])++;>table[el->n].y = i;
//переходим к следующему элементу
таблицы>n++;
same++;
}
}
//фигура
{= searchBlack(sym,
B);>table[el->n].chessmanNo = wrk;= '0';(chessman,sym);
}(input,"%s",&sym);
}
}
//белые фигуры
{
//считываем до
;(input,"%s",&sym);(sym[0] != sign[0])
{
// координата(sym[1]
>= '0' && sym[1] <= '9')
{
//если одинаковые фигуры(same != '0')
{(chessm,chessman);(chessm,&same);=
searchWhite(chessm, W);>table[el->n].chessmanNo = wrk;
//выясняем координату по x= 0;
while(sym[0] !=
x[i])++;>table[el->n].x = i;
//выясняем координату по y= 0;
while(sym[1] !=
y[i])++;>table[el->n].y = i;
//переходим к следующему элементу
таблицы>n++;++;
}
{
//выясняем координату по x
i = 0;(sym[0] !=
x[i])++;>table[el->n].x = i;
//выясняем координату по y= 0;
while(sym[1] !=
y[i])++;>table[el->n].y = i;
//переходим к следующему элементу
таблицы>n++;
same++;
}
}
//фигура
{= searchWhite(sym,
W);>table[el->n].chessmanNo = wrk;= '0';(chessman,sym);
}(input,"%s",&sym);
}
}
}
}(input);
}
//что в данной клеткеoccupied_space(int K1, int K2, work ell)
{(int i = 0; i <=
ell.n; i++){(ell.table[i].x == K1 && ell.table[i].y == K2)ell.table[i].chessmanNo;
}-1;
}
//пешка рядомpawn_of_king(int x,
int y, int flg, work elem)
{int s = x, c = y;M =
-3, N = -3;
//белые(flg == 1){((s-1
>= 0 && s-1 <= 7)&&(c-1 >= 0 && c-1 <= 7))=
occupied_space(s-1, c-1, elem);((s+1 >= 0 && s+1 <=
7)&&(c-1 >= 0 && c-1 <= 7))= occupied_space(s+1, c-1,
elem);
//важный ход пешки((7 < M
&& M < 16) || (7 < N && N < 16))0;
//не одна из пешек не претендует на
это место
return 1;
}
//чёрные{((s-1 >= 0
&& s-1 <= 7)&&(c+1 >= 0 && c+1 <= 7))=
occupied_space(s-1, c+1, elem);((s+1 >= 0 && s+1 <=
7)&&(c+1 >= 0 && c+1 <= 7))= occupied_space(s+1, c+1,
elem);
//важный ход пешки((23 < M
&& M < 32) && (23 < N && N < 32))0;
//не одна из пешек не претендует на
это место
return 1;
}
}
//конь рядомkNight_of_king(int
x, int y, int flg, work elem)
{int s = x, c = y;M =
-3, N = M, V = M, K = M, G = M, Q = M, P = M, D = M;
//если фигура входит в границы((s+2
>= 0 && s+2 <= 7)&&(c+1 >= 0 && c+1 <= 7))
M = occupied_space(s+2,
c+1, elem);
//если фигура входит в границы((s+2
>= 0 && s+2 <= 7)&&(c-1 >= 0 && c-1 <= 7))
N = occupied_space(s+2,
c-1, elem);
//если фигура входит в границы((s-2
>= 0 && s-2 <= 7)&&(c+1 >= 0 && c+1 <= 7))
V = occupied_space(s-2,
c+1, elem);
//если фигура входит в границы((s-2
>= 0 && s-2 <= 7)&&(c-1 >= 0 && c-1 <= 7))
K = occupied_space(s-2,
c-1, elem);
//если фигура входит в границы((s-1
>= 0 && s-1 <= 7)&&(c-2 >= 0 && c-2 <= 7))
G = occupied_space(s-1,
c-2, elem);
//если фигура входит в границы((s+1
>= 0 && s+1 <= 7)&&(c-2 >= 0 && c-2 <= 7))
Q = occupied_space(s+1,
c-2, elem);
//если фигура входит в границы((s-1
>= 0 && s-1 <= 7)&&(c+2 >= 0 && c+2 <= 7))
P = occupied_space(s-1,
c+2, elem);
//если фигура входит в границы((s+1
>= 0 && s+1 <= 7)&&(c+2 >= 0 && c+2 <= 7))
D = occupied_space(s+1,
c+2, elem);
//определение цвета фигур(flg ==
1){(M == 1||M == 6||N == 1||N == 6||V == 1||V == 6||K == 1||K == 6)
return 0;(G == 1||G ==
6||Q == 1||Q == 6||P == 1||P == 6||D == 1||D == 6)0;1;
}{(M == 17||M == 22||N
== 17||N == 22||V == 17||V == 22||K == 17||K == 22)0;(G == 17||G == 22||Q ==
17||Q == 22||P == 17||P == 22||D == 17||D == 22)0;1;
}
}
//слон рядомbishop_of_king(int
x, int y, int flg, work elem)
{M = -1, g1, g2, g3,
g4;int s = x, c = y;
//цвет(flg == 1){= 2;=
4;= 5;= 20;
}{= 18;= 19;= 21;= 3;
}
//пока фигура входит в границы или
является сама королём
do{++;++;((x <= 7
&& x >= 0)&&(y <= 7 && y >= 0)){=
occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;
}
}while((M == -1|| M ==
g4) && (x <= 7 && x >= 0)&&(y <= 7 &&
y >= 0));
x = s, y =c;
//пока фигура входит в границы или
является сама королём
do{++;-;((x <= 7
&& x >= 0)&&(y <= 7 && y >= 0)){=
occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;
}
}while((M == -1|| M ==
g4) && (x <= 7 && x >= 0)&&(y <= 7 &&
y >= 0));
x = s, y =c;
//пока фигура входит в границы или
является сама королём
do{-;-;((x <= 7
&& x >= 0)&&(y <= 7 && y >= 0)){=
occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;
}
}while((M == -1|| M ==
g4) && (x <= 7 && x >= 0)&&(y <= 7 &&
y >= 0));
x = s, y =c;
//пока фигура входит в границы или
является сама королём
do{-;++;((x <= 7
&& x >= 0)&&(y <= 7 && y >= 0)){=
occupied_space(x, y, elem);(M == g1||M == g2||M == g3)0;
}
}while((M == -1|| M ==
g4) && (x <= 7 && x >= 0)&&(y <= 7 &&
y >= 0));1;
}
//лодья рядомrook_of_king(int x,
int y, int flg, work elem)
{M = -1, g1, g2, g3,
g4;int s = x, c = y;(flg == 1){= 0;= 4;= 7;= 20;
}{
g1 = 16;= 19;= 23;= 3;
}
//пока фигура входит в границы или
является сама королём
do{++;(x <= 7
&& x >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M ==
g3)0;
}
x = s, y = c;
//пока фигура входит в границы или
является сама королём
do{-;(x <= 7
&& x >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M ==
g3)0;
}
}while((M == -1|| M ==
g4) && (x <= 7 && x >= 0));
x = s, y = c;
//пока фигура входит в границы или
является сама королём
do{-;(y <= 7
&& y >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M ==
g3)0;
}
}while((M == -1|| M ==
g4) && (y <= 7 && y >= 0));
y = c;
//пока фигура входит в границы или
является сама королём
do{++;(y <= 7
&& y >= 0){= occupied_space(x, y, elem);(M == g1||M == g2||M ==
g3)0;
}
}while((M == -1|| M ==
g4) && (y <= 7 && y >= 0));1;
}
//король рядомking_of_king(int x,
int y, int flg, work elem)
{g, M;int a = x, b =
y;(flg == 1)= 3;= 20;
//если фигура входит в границы((a+1
>= 0 && a+1 <= 7)&&(b+1 >= 0 && b+1 <= 7)){
M = occupied_space(a+1,
b+1, elem);
if(M == g)0;
}
//если фигура входит в границы
if((a-1 >= 0
&& a-1 <= 7)&&(b-1 >= 0 && b-1 <= 7)){=
occupied_space(a-1, b-1, elem);
if(M == g)0;
}
//если фигура входит в границы
if((a+1 >= 0
&& a+1 <= 7)&&(b-1 >= 0 && b-1 <= 7)){=
occupied_space(a+1, b-1, elem);
if(M == g)0;
}
//если фигура входит в границы
if((a-1 >= 0
&& a-1 <= 7)&&(b+1 >= 0 && b+1 <= 7)){=
occupied_space(a-1, b+1, elem);
if(M == g)0;
}
//если фигура входит в границы
if(a-1 >= 0
&& a-1 <= 7){= occupied_space(a-1, b, elem);
if(M == g)0;
}
//если фигура входит в границы
if(a+1 >= 0
&& a+1 <= 7){= occupied_space(a+1, b, elem);
if(M == g)0;
}
//если фигура входит в границы
if(b+1 >= 0
&& b+1 <= 7){= occupied_space(a, b+1, elem);
if(M == g)0;
}
//если фигура входит в границы
if(b-1 >= 0
&& b-1 <= 7){= occupied_space(a, b-1, elem);(M == g)0;
}1;
}
//связывающая подпрограмма для короляcommunication_king(int
k, int c, int f, work el){(king_of_king(k, c, f, el)){(pawn_of_king(k, c, f,
el)){(rook_of_king(k, c, f, el)){(bishop_of_king(k, c, f,
el)){(kNight_of_king(k, c, f, el))1;
}
}
}
}0;
}
//корольking(stack **B, int
a, int c, int f, work ell)
{int a1 = a, b1 = c;W_1
= 16, B_1 = 0, g1, g2, M;
//цвет(f == 1){= B_1;=
B_1 + 15;
}{
g1 = W_1;= W_1 + 15;
}
//просмотр всех вариантов хода
королём
//если фигура входит в границы((a1+1
>= 0 && a1+1 <= 7)&&(b1+1 >= 0 && b1+1 <=
7)){
//не одна из фигур не претендует на
клетку
if(communication_king(a1+1,
b1+1, f, ell)){= occupied_space(a1+1, b1+1, ell);((M >= g1 && M
<= g2)|| M == -1)_stack(&(*B), a1+1, b1+1);
}
}
//если фигура входит в границы((a1-1
>= 0 && a1-1 <= 7)&&(b1-1 >= 0 && b1-1 <=
7)){
//не одна из фигур не претендует на
клетку
if(communication_king(a1-1,
b1-1, f, ell)){= occupied_space(a1-1, b1-1, ell);((M >= g1 && M
<= g2)|| M == -1)_stack(&(*B), a1-1, b1-1);
}
}
//если фигура входит в границы((a1+1
>= 0 && a1+1 <= 7)&&(b1-1 >= 0 && b1-1 <=
7)){
//не одна из фигур не претендует на
клетку
if(communication_king(a1+1,
b1-1, f, ell)){= occupied_space(a1+1, b1-1, ell);((M >= g1 && M
<= g2)|| M == -1)_stack(&(*B), a1+1, b1-1);
}
}
//если фигура входит в границы((a1-1
>= 0 && a1-1 <= 7)&&(b1+1 >= 0 && b1+1 <=
7)){
//не одна из фигур не претендует на
клетку
if(communication_king(a1-1,
b1+1, f, ell)){= occupied_space(a1-1, b1+1, ell);((M >= g1 && M
<= g2)|| M == -1)_stack(&(*B), a1-1, b1+1);
}
}
//если фигура входит в границы(a1-1
>= 0 && a1-1 <= 7){
//не одна из фигур не претендует на
клетку
if(communication_king(a1-1,
b1, f, ell)){= occupied_space(a1-1, b1, ell);((M >= g1 && M <=
g2)|| M == -1)_stack(&(*B), a1-1, b1);
}
}
//если фигура входит в границы(a1+1
>= 0 && a1+1 <= 7){
//не одна из фигур не претендует на
клетку
if(communication_king(a1+1,
b1, f, ell)){= occupied_space(a1+1, b1, ell);((M >= g1 && M <=
g2)|| M == -1)_stack(&(*B), a1+1, b1);
}
}
//если фигура входит в границы(b1+1
>= 0 && b1+1 <= 7){
//не одна из фигур не претендует на
клетку
if(communication_king(a1,
b1+1, f, ell)){= occupied_space(a1, b1+1, ell);((M >= g1 && M <=
g2)|| M == -1)_stack(&(*B), a1, b1+1);
}
}
//если фигура входит в границы(b1-1
>= 0 && b1-1 <= 7){
//не одна из фигур не претендует на
клетку
if(communication_king(a1,
b1-1, f, ell)){= occupied_space(a1, b1-1, ell);((M >= g1 && M <=
g2)|| M == -1)_stack(&(*B), a1, b1-1);
}
}
}
//ферзьqueen(stack **B,
int a, int c, int f,work ell)
{(&(*B), a, c, f,
ell);(&(*B), a, c, f, ell);
}
//слонbishop(stack **B,
int a, int c, int f, work ell)
{int a1 = a, b1 = c;W_1
= 16, B_1 = 0, g1, g2, g3, M;
//цвет(f == 1){= B_1;=
B_1 + 15;= 3;
}{
g1 = W_1;= W_1 + 15;= 20;
}
//просмотр всех вариантов хода слоном
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{++;++;=
occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0
&& c <= 7)) && ((M >= g1 && M <= g2)|| M ==
-1) && M != g3)_stack(&(*B), a, c);
}while((M ==
-1)&&((a >= 0 && a <= 7)&&(c >= 0 && c
<= 7)) && M != g3);
a = a1, c = b1;
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{-;-;=
occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0
&& c <= 7)) && ((M >= g1 && M <= g2)|| M ==
-1) && M != g3)_stack(&(*B), a, c);
}while((M ==
-1)&&((a >= 0 && a <= 7)&&(c >= 0 && c
<= 7)) && M != g3);
a = a1, c = b1;
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{-;++;=
occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0
&& c <= 7)) && ((M >= g1 && M <= g2)|| M ==
-1) && M != g3)_stack(&(*B), a, c);
}while((M ==
-1)&&((a >= 0 && a <= 7)&&(c >= 0 && c
<= 7)) && M != g3);
a = a1, c = b1;
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{++;-;=
occupied_space(a,c,ell);(((a >= 0 && a <= 7)&&(c >= 0
&& c <= 7)) && ((M >= g1 && M <= g2)|| M ==
-1) && M != g3)_stack(&(*B), a, c);
}while((M ==
-1)&&((a >= 0 && a <= 7)&&(c >= 0 && c
<= 7)) && M != g3);
}
//лодьяrook(stack **B, int
a, int c, int f, work ell)
{int a1 = a, b1 = c, z1
= -1, z2 = 8;W_1 = 16, B_1 = 0, g1, g2, g3, M;
//цвет(f == 1){= B_1;=
B_1 + 15;= 3;
}{
g1 = W_1;= W_1 + 15;= 20;
}
//просмотр всех вариантов хода
ладьёй
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{++;=
occupied_space(a,c,ell);((a > z1 && a < z2) && ((M >=
g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a,
c);
}while((M == -1)
&& ((a > z1) && (a < z2)) && M != g3);
a = a1, c = b1;
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{-;=
occupied_space(a,c,ell);((a > z1 && a < z2) && ((M >=
g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a,
c);
}while((M == -1)
&& ((a > z1) && (a < z2)) && M != g3);
a = a1, c = b1;
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{-;=
occupied_space(a,c,ell);((c > z1 && c < z2) && ((M >=
g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B), a,
c);
}while((M == -1)
&& ((c > z1) && (c < z2)) && M != g3);
a = a1, c = b1;
//до тех пор пока не встретится
король противника или очередная клетка будет занята
do{++;=
occupied_space(a,c,ell);(((c > z1) && (c < z2)) && ((M
>= g1 && M <= g2)|| M == -1) && M != g3)_stack(&(*B),
a, c);
}while((M == -1)
&& ((c > z1) && (c < z2)) && M != g3);
}
//коньkNight(stack **B,
int a, int c, int f, work ell)
{int a1 = a, b1 = c;W_1
= 16, B_1 = 0, g1, g2, g3, M;
//цвет(f == 1){= B_1;=
B_1 + 15;= 3;
}{
g1 = W_1;= W_1 + 15;= 20;
}
//просмотр всех вариантов хода конём
M =
occupied_space(a1+2,b1-1,ell);
//если координата в границах доски
фигура в клетке цвета противника и не король
if(((a1+2 >= 0
&& a1+2 <= 7)&&(b1-1 >= 0 && b1-1 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1+2, b1-1);= occupied_space(a1+2,b1+1,ell);
//если координата в границах доски
фигура в клетке цвета противника и не король
if(((a1+2 >= 0
&& a1+2 <= 7)&&(b1+1 >= 0 && b1+1 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1+2, b1+1);= occupied_space(a1-2,b1+1,ell);
//если координата в границах доски
фигура в клетке цвета противника и не король
if(((a1-2 >= 0
&& a1-2 <= 7)&&(b1+1 >= 0 && b1+1 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1-2, b1+1);= occupied_space(a1-2,b1-1,ell);
//если координата в границах доски
фигура в клетке цвета противника и не король
if(((a1-2 >= 0
&& a1-2 <= 7)&&(b1-1 >= 0 && b1-1 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1-2, b1-1);= occupied_space(a1-1,b1-2,ell);
//если координата в границах доски
фигура в клетке цвета противника и не король
if(((a1-1 >= 0
&& a1-1 <= 7)&&(b1-2 >= 0 && b1-2 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1-1, b1-2);= occupied_space(a1+1,b1-2,ell);
//если координата в границах доски фигура
в клетке цвета противника и не король
if(((a1+1 >= 0
&& a1+1 <= 7)&&(b1-2 >= 0 && b1-2 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1+1, b1-2);= occupied_space(a1-1,b1+2,ell);
//если координата в границах доски
фигура в клетке цвета противника и не король
if(((a1-1 >= 0
&& a1-1 <= 7)&&(b1+2 >= 0 && b1+2 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1-1, b1+2);= occupied_space(a1+1,b1+2,ell);
//если координата в границах доски
фикура в клетке цвета противника и не король
if(((a1+1 >= 0
&& a1+1 <= 7)&&(b1+2 >= 0 && b1+2 <= 7))
&& ((M >= g1 && M <= g2)|| M == -1) && M !=
g3)_stack(&(*B), a1+1, b1+2);
}
//пешкаpawn(stack **B, int
a, int c, int f,work ell)
{int a1 = a, b1 = c;W_1
= 16, B_1 = 0, g1, g2, g3, M;
//цвет(f == 1){= B_1;=
B_1 + 15;= 3;(c == 6){
//одна вперёд=
occupied_space(a1,b1-1,ell);((b1-1 >= 0 && b1-1 <= 7) &&
(M == -1)){_stack(&(*B), a1, b1-1);
//две вперёд=
occupied_space(a1,b1-2,ell);((b1-2 >= 0 && b1-2 <= 7) &&
(M == -1))_stack(&(*B), a1, b1-2);
}
//одна влево=
occupied_space(a1-1,b1-1,ell);((a1-1 >= 0 && a1-1 <= 7)
&& (b1-1 >= 0 && b1-1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1-1, b1-1);
//одна вправо=
occupied_space(a1+1,b1-1,ell);((a1+1 >= 0 && a1+1 <= 7)
&& (b1-1 >= 0 && b1-1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1+1, b1-1);
}{
//одна вперёд=
occupied_space(a1,b1-1,ell);((b1-1 >= 0 && b1-1 <= 7) &&
(M == -1))_stack(&(*B), a1, b1-1);
//одна влево=
occupied_space(a1-1,b1-1,ell);((a1-1 >= 0 && a1-1 <= 7)
&& (b1-1 >= 0 && b1-1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1-1, b1-1);
//одна вправо=
occupied_space(a1+1,b1-1,ell);((a1+1 >= 0 && a1+1 <= 7)
&& (b1-1 >= 0 && b1-1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1+1, b1-1);
}
}{= W_1;= W_1 + 15;=
20;(c == 1){
//одна вперёд=
occupied_space(a1,b1+1,ell);((b1+1 >= 0 && b1+1 <= 7) &&
(M == -1)){_stack(&(*B), a1, b1+1);
//две вперёд=
occupied_space(a1,b1+2,ell);((b1+2 >= 0 && b1+2 <= 7) &&
(M == -1))_stack(&(*B), a1, b1+2);
}
//одна влево=
occupied_space(a1-1,b1+1,ell);((a1-1 >= 0 && a1-1 <= 7)
&& (b1+1 >= 0 && b1+1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1-1, b1+1);
//одна вправо=
occupied_space(a1+1,b1+1,ell);((a1+1 >= 0 && a1+1 <= 7)
&& (b1+1 >= 0 && b1+1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1+1, b1+1);
}{
//одна вперёд=
occupied_space(a1,b1+1,ell);((b1+1 >= 0 && b1+1 <= 7) &&
(M == -1))_stack(&(*B), a1, b1+1);
//одна влево=
occupied_space(a1-1,b1+1,ell);((a1-1 >= 0 && a1-1 <= 7)
&& (b1+1 >= 0 && b1+1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1-1, b1+1);
//одна вправо=
occupied_space(a1+1,b1+1,ell);((a1+1 >= 0 && a1+1 <= 7)
&& (b1+1 >= 0 && b1+1 <= 7) && (M >= g1
&& M <= g2) && M != g3)_stack(&(*B), a1+1, b1+1);
}
}
}
//копирование стекаcopying(stack *Q1,
stack **Q2)
{(Q1 != NULL) {(*Q2 ==
NULL){
*Q2 = new stack;
(*Q2)->X = Q1->X;
(*Q2)->Y = Q1->Y;
(*Q2)->next = NULL;
}{*R = new stack;>X =
Q1->X;>Y = Q1->Y;>next = (*Q2);
(*Q2) = R;
}= Q1->next;
}
}
//в стекin_stack(stack **Q, int x_1, int y_1)
{(*Q == NULL){
*Q = new stack;
(*Q)->X = x_1;
(*Q)->Y = y_1;
(*Q)->next = NULL;
}{*R = new stack;>X =
x_1;>Y = y_1;>next = *Q;
*Q = R;
}
}
//из стекаout_stack(stack**Q,
int *x_1, int *y_1)
{(*Q == NULL)0;
*x_1 = (*Q)->X;
*y_1 = (*Q)->Y;*N =
*Q;
*Q = (*Q)->next;N;1;
}
//поиск в стекеsearch_stack(stack*Q, int n, int m)
{(Q != NULL){(Q->X ==
n && Q->Y == m)1;= Q->next;
}0;
}
/*Form1.h*/
#pragma once
#include<string.h>
#include <stdio.h>
#include
"chessman.h"FILE *fl, *fll, *fll2, *input;C, old_X, old_Y;// фигура для пп clikchess
{namespace System;namespace System::ComponentModel;namespace
System::Collections;namespace System::Windows::Forms;namespace
System::Data;namespace System::Drawing;
/// <summary>
/// Сводка для Form1
///
</summary>fig[63];ref class Form1 : public System::Windows::Forms::Form
{:
//необходимая информация о фигурхinput_fl(color_1 *B, color_2 *W)
{k = 0, q = 0;ch[4];((fl
= fopen("fl.txt", "r")) ==
NULL)("error");{(fl,"%s",&B->chessBlack);(fl,"%s",&W->chessWhite);((k
< 16) && fscanf(fl,"%s",&ch))
{(B->Bcolor[k].chessman,
ch);>Bcolor[k].No = k;++;
}(fscanf(fl,"%s",&ch)
!= EOF)
{(W->Wcolor[q].chessman,
ch);>Wcolor[q].No = k;
q++;++;
}
}(fl);
}
//инициализация фигур
void initchess()
{(int i = 0; i < 32;
i++)[i]= -5;();
}initznak()
{(int i = 32; i < 63;
i++)[i]= -5;
}
//место фигуры i- фигура, y,x -
место(они с -1)
void figchess(int i, int
y,int x)
{[i] = y*8+x;
}
//считаные нажатием координаты
void clik(int a, int b,
stack **course)
{
//инициализация символов хода();ell;
stack *backup = NULL;flg
= 0;
//вспомогательные элементы(&ell);_stakc(&backup);
//выбор фигуры(backup == NULL)
{= occupied_space(a, b,
ell);
if(C>15) //белые= 1;
//королль(C == 3 || C == 20)
king(&(*course), a,
b, flg,ell);
//ферзь(C == 4 || C == 19)(&(*course),
a, b, flg,ell);
//слон((C == 2 || C == 5)
|| (C == 18 || C == 21))(&(*course), a, b, flg,ell);
//лодья((C == 0 || C == 7)
|| (C == 16 || C == 23))(&(*course), a, b, flg,ell);
//конь((C == 1 || C == 6)
|| (C == 17 || C == 22))(&(*course), a, b, flg,ell);
//пешка((C >= 24
&& C <= 31) || (C >= 8 && C <= 15))(&(*course), a,
b, flg,ell);
//вспомогательные элементы(*course,
&backup);
openfile_stakc(&backup);_X
= a, old_Y = b;
}
//выбор места переноса фигуры
{U, d = 0, h = 0;
//необходимо чтобы выбранное место
соответствовало правильному ходу
if(search_stack(backup,
a, b)){= occupied_space(old_X, old_Y, ell);(ell.table[d].chessmanNo != U){++;
}= occupied_space(a, b,
ell);
//место пусто переместить(U == -1){
ell.table[d].x =
a;.table[d].y = b;
}
//место
занято срубить{(ell.table[h].chessmanNo !=
U)++;.table[h].x = -5;.table[h].y = -5;.table[d].x = a;.table[d].y = b;
}
//смена
изображения();(int j = 0; j <
ell.n; j++)(ell.table[j].chessmanNo,ell.table[j].y,ell.table[j].x);
}
//вспомогательные
элементы(out_stack(&backup,
&old_X, &old_Y))_X = 0, old_Y = 0;_stakc(&backup);(ell);
}
}
//основной
алгоритмmyalg()
{_1 Bl;_2
Wh;elem;_fl(&Bl,&Wh);(Bl, Wh, &elem);(elem);(int j = 0; j <
elem.n; j++)
//выполнение
вывода пользовательской расстановки
фигур(elem.table[j].chessmanNo,
elem.table[j].y, elem.table[j].x);
}(void)
{();();();
}:
~Form1()
{(components)
{components;
}
}:
System::Windows::Forms::PictureBox^ pictureBox1;::::ComponentModel::Container
^components;
#pragma region Windows
Form Designer generated codeInitializeComponent(void)
{>pictureBox1 =
(gcnew System::Windows::Forms::PictureBox());
(cli::safe_cast<System::ComponentModel::ISupportInitialize^
>(this->pictureBox1))->BeginInit();>SuspendLayout();
//
// pictureBox1
//>pictureBox1->BackColor
= System::Drawing::Color::White;>pictureBox1->Location =
System::Drawing::Point(12, 12);>pictureBox1->Name =
L"pictureBox1";>pictureBox1->Size = System::Drawing::Size(400,
400);>pictureBox1->TabIndex = 0;>pictureBox1->TabStop =
false;>pictureBox1->Paint += gcnew System::Windows::Forms::PaintEventHandler(this,
&Form1::pictureBox1_Paint);>pictureBox1->MouseClick += gcnew
System::Windows::Forms::MouseEventHandler(this,&Form1::pictureBox1_MouseClick);
// Form1
//>AutoScaleDimensions
= System::Drawing::SizeF(6, 13);>AutoScaleMode =
System::Windows::Forms::AutoScaleMode::Font;>ClientSize =
System::Drawing::Size(424,
420);>Controls->Add(this->pictureBox1);>FormBorderStyle =
System::Windows::Forms::FormBorderStyle::FixedSingle;>MaximizeBox =
false;>Name = L"Form1";>Text = L"Form1";
(cli::safe_cast<System::ComponentModel::ISupportInitialize^
>(this->pictureBox1))->EndInit();>ResumeLayout(false);
}
#pragma endregion:
System::Void pictureBox1_Paint(System::Object^ sender,
System::Windows::Forms::PaintEventArgs^ e) {^ g = e->Graphics;n = 0;(int i =
0; i < 8; i++)
{(int j = 0; j < 8;
j++)
{(n % 2 ==
1)>FillRectangle(Brushes::Brown, j * 50, i * 50, 50,
50);>FillRectangle(Brushes::Wheat, j * 50, i * 50, 50, 50);++;
}++;
}::Drawing::Font^
drawFont = gcnew System::Drawing::Font( "Arial",29
);>DrawString(L"♜", drawFont, Brushes::Black,
fig[0] % 8 * 50, fig[0] / 8 * 50);>DrawString(L"♞", drawFont, Brushes::Black, fig[1] % 8 * 50, fig[1] / 8 *
50);>DrawString(L"♝",
drawFont, Brushes::Black, fig[2] % 8 * 50, fig[2] / 8 *
50);>DrawString(L"♚",
drawFont, Brushes::Black, fig[3] % 8 * 50, fig[3] / 8 *
50);>DrawString(L"♛",
drawFont, Brushes::Black, fig[4] % 8 * 50, fig[4] / 8 *
50);>DrawString(L"♝",
drawFont, Brushes::Black, fig[5] % 8 * 50, fig[5] / 8 *
50);>DrawString(L"♞",
drawFont, Brushes::Black, fig[6] % 8 * 50, fig[6] / 8 *
50);>DrawString(L"♜",
drawFont, Brushes::Black, fig[7] % 8 * 50, fig[7] / 8 * 50);(int i = 0; i <
8; i++)>DrawString(L"♟",
drawFont, Brushes::Black, fig[8 + i] % 8 * 50, fig[8 + i] / 8 *
50);>DrawString(L"♖",
drawFont, Brushes::Black, fig[16] % 8 * 50, fig[16] / 8 *
50);>DrawString(L"♘",
drawFont, Brushes::Black, fig[17] % 8 * 50, fig[17] / 8 *
50);>DrawString(L"♗",
drawFont, Brushes::Black, fig[18] % 8 * 50, fig[18] / 8 *
50);>DrawString(L"♕",
drawFont, Brushes::Black, fig[19] % 8 * 50, fig[19] / 8 *
50);>DrawString(L"♔",
drawFont, Brushes::Black, fig[20] % 8 * 50, fig[20] / 8 *
50);>DrawString(L"♗",
drawFont, Brushes::Black, fig[21] % 8 * 50, fig[21] / 8 *
50);>DrawString(L"♘",
drawFont, Brushes::Black, fig[22] % 8 * 50, fig[22] / 8 *
50);>DrawString(L"♖",
drawFont, Brushes::Black, fig[23] % 8 * 50, fig[23] / 8 * 50);(int i = 24; i
< 32; i++)>DrawString(L"♙", drawFont, Brushes::Black, fig[i] % 8 * 50, fig[ i] / 8 *
50);(int i = 32; i < 63; i++)>DrawString(L"✕", drawFont, Brushes::Blue, fig[i] % 8 * 50, fig[i] / 8 *
50);
}: System::Void
pictureBox1_MouseClick(System::Object^ sender,
System::Windows::Forms::MouseEventArgs^ e) {*poss_course = NULL;x1 = e->X /
50, y1 = e->Y / 50;(x1, y1, &poss_course);(poss_course != NULL){(int s =
0, k = 0, z = 32; out_stack(&poss_course, &s, &k); z++)(z, k, s);
}->Refresh();
}
};
}
/*main.cpp*/
// chess.cpp: главный
файл проекта.
#include
"stdafx.h"
#include
"Form1.h"
#include
"chessman.h"namespace chess;
[STAThreadAttribute]main(array<System::String
^> ^args)
{
// Включение визуальных эффектов Windows XP до создания каких-либо
элементов управления
Application::EnableVisualStyles();::SetCompatibleTextRenderingDefault(false);
// Создание главного окна и его запуск
Application::Run(gcnew
Form1());0;
}
/*chessman.cpp*/
#ifndef CHESSMAN_H
#define CHESSMAN_H
//Таблица с чёрными фигурамиBlack {
char chessman [4];No;
};color_1 {Bcolor
[16];chessBlack [8];
};
//Таблица
с белыми фигурамиWhite {chessman [4];No;
};color_2 {Wcolor
[16];chessWhite [7];
};
};work {table [33];n;
};stack {*next;X;Y;
};myscanf(color_1 B,
color_2 W, work *el);
//королльking(stack **B, int a, int c, int f,work ell);
//ферзьqueen(stack **B, int a, int c, int f,work ell);
//слонbishop(stack **B, int a, int c, int f,work ell);
//лодьяrook(stack **B, int a, int c, int f,work ell);
//коньkNight(stack **B, int a, int c, int f,work ell);
//пешкаpawn(stack **B, int a, int c, int f,work ell);
//копирование
стекаcopying(stack *Q1, stack **Q2);
//в
стекin_stack(stack **Q, int x, int y);
//из
стекаout_stack(stack**Q, int *x, int *y);
//что
в данной клеткеoccupied_space(int K1, int K2, work
ell);openfile(work ell);closefile(work *ell);openfile_stakc(stack
**B);closefil_stakc(stack **B);search_stack(stack*Q, int n, int m);
#endif
7.
Набор тестов
Входные данные
|
Назначение теста
|
1)
|
Отсутствие обозначения фигур
|
2) чёрные: Л a8, h8, К b8, g8, С c8, f8, Кр d8, Ф e8, пп a7, b7,
c7, d7, e7, f7, g7, h7 ; белые: Л a1, h1, К b1, g1, С c1, f1, Кр d1, Ф e1, пп
a2, b2, c2, d2, e2, f2, g2, h2 ;
|
Все возможные фигуры
|
3) п d2
|
Возможный ход пешки бело цвета
|
4) К g1
|
Возможный ход коня бело цвета
|
5) Ф e3
|
Возможный ход ферзя бело цвета
|
6) С e2
|
Возможный ход слона бело цвета
|
7) Л g8
|
Возможный ход ладья чёрного цвета
|
8) Ф g5
|
Возможный ход ферзя бело цвета
|
9) Кр d4
|
Возможный короля бело цвета
|
10) Кр d5
|
Возможный короля бело цвета
|
11) п g2
|
Возможный короля пешки бело цвета
|
12) Кр e4
|
Возможный короля бело цвета
|
13) Кр c6
|
Возможный короля чёрного цвета
|
14) Л g8
|
Возможный ход ладья чёрного цвета
|
15) Кр e7
|
Возможный короля бело цвета
|
16) Л h1
|
Возможный ход ладья белого цвета
|
17) Л e6
|
Возможный ход ладья белого цвета
|
18) Кр d3
|
Возможный короля чёрного цвета
|
19) Кр c4
|
Возможный короля чёрного цвета
|
8. Результаты
работы программы
Входные
данные
|
Выходные
данные
|
|
1)
|
|
|
2)
|
|
|
3)
|
|
|
4)
|
|
|
5)
|
|
|
6)
|
|
|
7)
|
|
|
8)
|
|
|
9)
|
|
|
10)
|
|
|
11)
|
|
|
12)
|
|
|
13)
|
|
|
14)
|
|
|
15)
|
|
|
16)
|
|
17)
|
|
18)
|
|
19)
|
|
Литература
1. Хиценко В.П., Шапошникова Т.А.
Структуры данных и алгоритмы: методические указания. Новосибирск: НГТУ, 2008.