close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Санкт-Петербургский государственный политехнический
университет
Кафедра “Прикладная математика”
Отчет по курсовой работе по дисциплине
“Языки и методы программирования”
Студент группы № 23601/1
Елисеев Артем Андреевич
Выполнил (подпись)____________(дата)____________
Руководитель Беляев Сергей Юрьевич
Работа принята (подпись) ____________
1
Оглавление
Постановка задачи...................................................................................................................................... 3
Описание алгоритма .................................................................................................................................. 3
Текст программы ........................................................................................................................................ 5
Описание тестирования ...........................................................................................................................11
2
Постановка задачи
В данной работе требуется на примере конкретной задачи реализовать
октодерево с поддержкой операций добавления и поиска элементов. Для
начала формализуем исходную задачу.
Итак, пользователь нашей программы может делать следующие запросы
к ней:
1) Напечатать октодерево в текущий момент;
2) Добавить точку с координатами (, , );  ≤ , ,  ≤  в октодерево;
3) Сделать запрос на поиск точки с координатами (, , );  ≤ , ,  ≤
 в октодереве;
4) Завершить программу.
Количество запросов со стороны пользователя может быть неограниченно.
Описание алгоритма
Для описания алгоритма требуется пояснить, по каким правилам
строится и как определяется октодерево.
Октодерево – специальный вид дерева, в котором каждый узел имеет
либо 8 сыновей, либо 0, если узел является листовым.
Такое определение имеет геометрическую интерпретацию, о которой
сейчас пойдет речь.
Каждый внутренний узел дерева содержит в себе точку, которая лежит
в области пространства, занимаемой данным узлом. Внутри нее,
соответственно, пространство разбивается на 8 частей, которые изображены
на рисунке выше. Узлы, соответствующие этим частям, и будут детьми
3
рассматриваемого родительского узла. Заранее договоримся о нумерации
этих узлов. Первые 4 на рисунке выше образуют нижнюю половину куба,
другие 4 (5 – 8) – верхнюю. Нумерация среди 1 – 4 и 5 – 8 производится
аналогично, проведем ее лишь для 1 – 4. Левый ближний узел – 1, правый
ближний узел – 2, левый дальний узел – 3, правый дальний узел – 4, если
следовать рисунку выше.
В корневом узле в качестве точки запишем первую, пришедшую от
пользователя точку.
Теперь приведем алгоритмы добавления и поиска элемента в
октодереве, а также его печати.
Добавление элемента
Осуществим добавление элемента рекурсивной процедурой.
1. Проверка наличия точки в рассматриваемом узле, изначально это
корень. Если точки в этом узле нет, то записываем в него пришедшую от
пользователя точку и завершаем процедуру. Иначе переходим к
следующему шагу.
2. Если в этом узле уже есть точка, то проверяем, листовой ли узел. Если
нет, то переходим к следующему шагу. Иначе, добавляем узлу детей,
делая его родительским, и переходим к следующему шагу.
3. Проверяем, в каком из восьми кубов, на которые разбит куб данного
узла, лежит пришедшая от пользователя точка. Если она лежит в
нескольких сразу, берем среди всех них куб с наименьшим номером.
Запускаем нашу процедуру от выбранного куба.
4. Если точка не оказалась ни в одном из восьми кубов, завершаем
процедуру.
Поиск элемента
Для поиска элемента воспользуемся стандартным алгоритмом обхода
дерева в ширину.
1. Создадим очередь из вершин дерева, в начало которой поместим его
корень.
2. Пока очередь не пуста, выкидываем из начала очереди вершину. Если
очередь стала пустой, алгоритм завершается.
4
3. Если в этой вершине точки нет, пропускаем ее и переходим к шагу 2.
Иначе, сравниваем точку в этой вершине с пришедшей от пользователя,
в случае равенства, поиск успешно совершен, и процедура завершается.
4. Если равенства точек нет, то добавляем в очередь всех детей данной
вершины при их наличии и возвращаемся к шагу 2.
Печать дерева
Печать дерева реализуется рекурсивной процедурой.
1. Передаем в процедуру корень дерева.
2. Если в рассматриваемом узле есть точка, печатаем ее с количеством
пробелов перед ней, соответствующим уровню вершины (уровни
вершин устанавливаются в процедуре добавления в октодерево, при
добавлении листовому узлу детей их уровень устанавливается на
единицу больше уровня их родителя, уровень корня равен нулю).
3. Иначе печатаем сообщение о том, что точки в данном узле нет с
аналогичным числом пробелов.
4. При наличии детей у узла запускаем процедуру печати от них с шага 2.
Текст программы
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 8
typedef struct point
{
int x;
int y;
int z;
} point;
typedef struct tree
{
point * dot;
int level;
struct tree ** child;
} tree;
typedef struct List {
tree * node;
struct List * next;
} List;
typedef struct Queue {
List * first;
List * last;
5
} Queue;
Queue * InitQueue()
{
Queue * q;
q = malloc(sizeof(Queue));
q->first = malloc(sizeof(List));
q->last = q->first;
return q;
}
void AddToQueue (Queue * q, tree * add)
{
List * t;
t = malloc(sizeof(List));
t->node = add;
t->next = NULL;
q->last->next = t;
q->last = t;
}
void InitBorder (point * left, point * right)
{
left->x = 0;
left->y = 0;
left->z = 0;
right->x = MAX_SIZE;
right->y = MAX_SIZE;
right->z = MAX_SIZE;
}
tree * InitTree(point * start)
{
tree * root;
root = malloc(sizeof(tree));
root->dot = start;
root->child = NULL;
root->level = 0;
return root;
}
int InCube(point * left, point * right, point * first)
{
if ((first->x >= left->x) && (first->y >= left->y) && (first->z >= left>z))
if ((first->x <= right->x) && (first->y <= right->y) && (first->z <=
right->z))
return 1;
return 0;
}
void ChangeBorders(point * left, point * right, point * first, point *
second, int number)
{
switch (number + 1)
{
case 1:
{
left->x = first->x;
left->y = first->y;
left->z = first->z;
6
right->x = (first->x + second->x) / 2;
right->y = (first->y + second->y) / 2;
right->z = (first->z + second->z) / 2;
break;
}
case 2:
{
left->x = (first->x + second->x) / 2;
left->y = first->y;
left->z = first->z;
right->x = second->x;
right->y = (first->y + second->y) / 2;
right->z = (first->z + second->z) / 2;
break;
}
case 3:
{
left->x = first->x;
left->y = (first->y + second->y) / 2;
left->z = first->z;
right->x = (first->x + second->x) / 2;
right->y = second->y;
right->z = (first->z + second->z) / 2;
break;
}
case 4:
{
left->x = (first->x + second->x) / 2;
left->y = (first->y + second->y) / 2;
left->z = first->z;
right->x = second->x;
right->y = second->y;
right->z = (first->z + second->z) / 2;
break;
}
case 5:
{
left->x = first->x;
left->y = first->y;
left->z = (first->z + second->z) / 2;
right->x = (first->x + second->x) / 2;
right->y = (first->y + second->y) / 2;
right->z = second->z;
break;
}
case 6:
{
left->x = (first->x + second->x) / 2;
left->y = first->y;
left->z = (first->z + second->z) / 2;
right->x = second->x;
right->y = (first->y + second->y) / 2;
right->z = second->z;
break;
}
case 7:
{
left->x = first->x;
left->y = (first->y + second->y) / 2;
left->z = (first->z + second->z) / 2;
right->x = (first->x + second->x) / 2;
right->y = second->y;
right->z = second->z;
7
break;
}
case 8:
{
left->x = (first->x + second->x) / 2;
left->y = (first->y + second->y) / 2;
left->z = (first->z + second->z) / 2;
right->x = second->x;
right->y = second->y;
right->z = second->z;
break;
}
}
}
void InsertOct(tree * root, point * search, point * left, point * right)
{
int i, flag = 0;
point * local_left, * local_right;
local_left = malloc(sizeof(point));
local_right = malloc(sizeof(point));
if (root->dot == NULL)
{
root->dot = malloc(sizeof(point));
*(root->dot) = *search;
root->child = NULL;
free(local_left);
free(local_right);
return;
}
if (root->child == NULL)
{
root->child = malloc(sizeof(tree*));
for (i = 0; i < 8; i++)
{
root->child[i] = malloc(sizeof(tree));
root->child[i]->dot = NULL;
root->child[i]->child = NULL;
root->child[i]->level = root->level + 1;
}
}
for (i = 0; i < 8; i++)
{
local_left->x = left->x;
local_left->y = left->y;
local_left->z = left->z;
local_right->x = right->x;
local_right->y = right->y;
local_right->z = right->z;
ChangeBorders(local_left, local_right, left, right, i);
if (InCube(local_left, local_right, search))
{
if (!flag)
{
flag = 1;
InsertOct(root->child[i], search, local_left, local_right);
}
}
}
free(local_left);
free(local_right);
8
return;
}
int Equal(point * first, point * second)
{
if (first->x == second->x)
if (first->y == second->y)
if (first->z == second->z)
return 1;
return 0;
}
void SearchOct(tree * root, point * search, int * error)
{
tree * now;
Queue * q;
int i = 0;
q = InitQueue();
AddToQueue(q, root);
while (q->first->next != NULL)
{
now = q->first->next->node;
q->first = q->first->next;
if (now->dot == NULL)
continue;
if (Equal(now->dot, search))
{
*error = 0;
return;
}
i = 0;
if (now->child != NULL)
{
while (i < 8)
AddToQueue(q, now->child[i++]);
}
}
}
void PrintTree(tree * root)
{
if (root != NULL)
{
int i;
if (root->dot)
{
for (i = 0; i < root->level; i++)
printf(" ");
printf("%i %i %i\n", root->dot->x, root->dot->y, root->dot->z);
}
else
{
for (i = 0; i < root->level; i++)
printf(" ");
printf("NULL\n");
}
if (root->child)
for (i = 0; i < 8; i++)
PrintTree(root->child[i]);
}
}
9
int main(void)
{
tree * root;
point init, left, right;
char s[2];
char * get;
InitBorder(&left, &right);
printf("Tree initialization:\n");
printf("Type in a point to start from:\n");
scanf("%i %i %i", &(init.x), &(init.y), &(init.z));
root = InitTree(&init);
for (;;)
{
printf("\n");
printf("Type a number from 1 to 4:\n");
printf("1 - Print tree.\n");
printf("2 - Add a point.\n");
printf("3 - Search a point.\n");
printf("4 - Exit.\n");
scanf("%s", s);
get = malloc(strlen(s) + 1);
strcpy(get, s);
switch (get[0])
{
case '1':
{
printf("You've chosen to print the tree.\n\n");
printf("The tree.\n");
PrintTree(root);
break;
}
case '2':
{
point search;
printf("You've chosen to insert a point.\n");
printf("Type in a point to insert:\n");
scanf("%i %i %i", &(search.x), &(search.y), &(search.z));
InsertOct(root, &search, &left, &right);
printf("The tree.\n\n");
PrintTree(root);
break;
}
case '3':
{
point find;
int error = 1;
printf("You've chosen to search a point.\n");
printf("Type in a point to search:\n");
scanf("%i %i %i", &(find.x), &(find.y), &(find.z));
SearchOct(root, &find, &error);
if (error)
printf("The search has failed!\n");
else
printf("The search has done successfully!\n");
break;
}
case '4':
{
free(get);
10
printf("You've chosen to exit the program.\n");
return 0;
}
default:
break;
}
free(get);
}
return 0;
}
Описание тестирования
Для тестирования данной программы производился ее неоднократный
запуск с вводом конкретных данных, при котором проверялось:
1)
2)
3)
4)
Стабильность работы программы при одинаковых входных данных;
Отсутствие “падений” и “зависаний”;
Корректное выполнение всех заявленных процедур;
Корректное завершение программы;
Приведем пример тестирования на скриншотах, данных ниже
11
12
13
При проведении тестирования такого рода никаких проблем обнаружено
не было, что позволяет судить о корректности работы программы в целом.
14
1/--страниц
Пожаловаться на содержимое документа