Добавил:

Valeriya Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Липецкий государственный технический университет

Предмет:

Структуры и алгоритмы обработки данных

Файл:

Лабораторная работа №1 Вариант №12

.doc

Скачиваний:

Добавлен:

20.06.2014

Размер:

126.98 Кб

Скачать

☆

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №1

по дисциплине

«Структуры и алгоритмы»

на тему:

«Деревья»

Студент

^{подпись, дата}

^{фамилия,
инициалы}

Группа

Принял

Журавлева М.Г.

^{ученая степень,
звание}

^{подпись, дата}

^{фамилия,
инициалы}

Липецк 2012

Задание

№ варианта

Ключ

Удаляемый узел

Распределение

Реализация

Степень дерева

Метод обхода

int

char[]

заменяется самым левым дочерним узлом

заменяется самым правым дочерним узлом

равномерное

нормальное

связный список дочерних узлов

список дочерних узлов, два массива

список дочерних узлов, массив структур, 3 поля

указатели

прямой

обратный

симметричный

Листинг программы

#include <stdio.h>

#include <conio.h>

#include <windows.h>

#include <locale.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

struct treeElem

{

char key[255];

int child, bro;

};

unsigned long int microtime()

{

SYSTEMTIME t;

GetSystemTime(&t);

return t.wMilliseconds + 1000 * (t.wSecond + 60 * (t.wMinute + 60 * (t.wHour)));

}

bool isExist(treeElem** root, bool woOutput = false)

{

if (*root == NULL)

{

if(!woOutput)

printf("Дерево чисто");

return 0;

}

return 1;

}

void randString(char* key, int size)

{

int i;

for (i = 0; i < size; i++)

{

key[i] = rand() % 25 + 65;

}

key[i+1] = '\0';

return;

}

int getNormalRand() //рандом для нормального распределения

{

int num = 0;

for (int i = 0; i < 12; ++i)

{

num += rand();

}

return num/12;

}

void cleanTree(treeElem** root, int* i, bool woOutput = false)

{

int start = microtime();

free(*root);

*root = NULL;

*i = -1;

if(!woOutput)

printf("Дерево успешно очищено за %iмс!", microtime() - start);

return;

}

void printTree(treeElem** root, unsigned int i)

{

if (!isExist(root))

return;

if ((*root)[i].child != -1) printTree(root, (*root)[i].child);

printf("[%i] элемент, ключ - %s\n\r", i+1, &(*root)[i].key);

if ((*root)[i].bro != -1) printTree(root, (*root)[i].bro);

return;

}

void getRoot(treeElem** root)

{

if (!isExist(root))

return;

printf("%s", (*root)[0].key);

}

void getKey(treeElem** root, int* i)

{

int choose = -1;

if (!isExist(root))

return;

while (choose - 1 < 0 || choose - 1 > *i)

{

system("cls");

printf("Введите номер узла: ");

scanf("%i", &choose);

if (choose - 1 < 0 || choose - 1 > *i)

{

printf("Введенный узел не существует, введите номер заново..");

getch();

}

printf("%s", (*root)[choose-1].key);

}

void setKey(treeElem** root, int* elemNum)

{

char key[255];

int i;

if (!isExist(root))

return;

printf("Введите номер узла, для которого нужно заменить ключ: ");

scanf("%i", &i);

i--;

if (i > *elemNum || i < 0)

{

printf("Элемент задан неверно");

return;

}

printf("Введите новый ключ для узла [%i] (без пробелов): ", i+1);

scanf("%s", key);

strcpy((*root)[i].key, key);

printf("Done");

return;

}

void search(treeElem** root, unsigned int i, char* query, bool* isFound)

{

if ((*root)[i].child != -1) search(root, (*root)[i].child, query, isFound);

if(!strcmp((*root)[i].key, query))

{

printf("%i ", i + 1);

*isFound = true;

}

if ((*root)[i].bro != -1) search(root, (*root)[i].bro, query, isFound);

}

void searchNode(treeElem** root)

{

if (!isExist(root))

return;

char query[255];

bool isFound = false;

printf("Введите искомый ключ: ");

scanf("%s", query);

search(root, 0, query, &isFound);

if(!isFound)

printf("Искомый ключ не найден");

return;

}

int getMostRightChild(treeElem** root, int elem) //сначала переход вправо по братьям, потом переход по детям (если возможно)

{

if (!isExist(root))

return -1;

while (true)

{

if((*root)[elem].bro != -1)

{

elem = (*root)[elem].bro;

continue;

}

if((*root)[elem].child != -1)

{

elem = (*root)[elem].child;

continue;

}

if(((*root)[elem].bro == -1) && ((*root)[elem].child == -1)) break;

}

return elem;

}

int getParent(treeElem** root, int* elemNum, int choose) // возвращает индекс родителя или -1 если элемент задан неверно или это корень

{

if (!isExist(root))

return -1;

for(int i = 0; i <= *elemNum; i++)

{

if((*root)[i].child == choose)

return i;

int k = (*root)[i].child;

while(k != -1)

{

if((*root)[k].bro == choose)

return i;

k = (*root)[k].bro;

}

return -1;

}

void addElemAPI(treeElem** root, int* elemNum, bool likeBro, int wide, int node, char* customString, int keysize = 5, bool outputOnSuccess = true) // keysize - размер строки, likebro - добавлять ли как брата, wide, size - макс. кол-во братьев(4 у меня) и элементов в целом(для проверки), node - куда добавлять

{

if (*root == NULL)

{

*root = (treeElem*) malloc(sizeof(treeElem));

if (customString[0] != '\0')

strcpy((*root)->key, customString);

else

randString((*root)->key, keysize);

(*root)->child = -1;

(*root)->bro = -1;

*elemNum = 0;

if(outputOnSuccess)

printf("Добавлен корень с номером [1] и ключом [%s]", (*root)->key);

return;

}

if (likeBro)

{

if (node == 0)

{

printf("К корню нельзя добавить брата");

return;

}

if(outputOnSuccess)

{

int broNum = 0;

int currElem = getParent(root, elemNum, node);

if (currElem == -1)

{

printf("Произошла неведомая хрень");

return;

}

currElem = (*root)[currElem].child;

while(currElem != -1)

{

++broNum;

currElem = (*root)[currElem].bro;

}

if (broNum >= wide)

{

printf("Достигнут максимум братьев");

return;

}

(*elemNum)++;

*root = (treeElem*) realloc(*root ,sizeof(treeElem) * ((*elemNum) + 1));

if (customString[0] != '\0')

strcpy((*root)[*elemNum].key, customString);

else

randString((*root)[*elemNum].key, keysize);

(*root)[*elemNum].child = -1;

(*root)[*elemNum].bro = (*root)[node].bro;

(*root)[node].bro = (*elemNum);

if (outputOnSuccess)

{

printf("Добавлен брат к элементу [%i] с номером [%i] и ключом [%s]", node+1, (*elemNum)+1, (*root)[(*elemNum)].key);

return;

}

else

{

(*elemNum)++;

*root = (treeElem*) realloc(*root ,sizeof(treeElem) * ((*elemNum) + 1));

if (customString[0] != '\0')

strcpy((*root)[*elemNum].key, customString);

else

randString((*root)[*elemNum].key, keysize);

(*root)[*elemNum].child = -1;

(*root)[*elemNum].bro = (*root)[node].child;

(*root)[node].child = (*elemNum);

if (outputOnSuccess)

{

printf("Добавлен брат к элементу [%i] с номером [%i] и ключом [%s]", node+1, (*elemNum)+1, (*root)[(*elemNum)].key);

return;

}

void addElem(treeElem** root, int* elemNum)

{

int wide = 4; // по варианту

int node = 0;

bool likeBro = false;

if (isExist(root, 1))

{

printf("Введите номер элемента: ");

scanf("%i", &node);

--node;

if (node > *elemNum || node < 0)

{

printf("Элемент введен неверно");

return;

}

printf("Добавить к элементу [%i]:\n\r1. Брата\n\r2. Дитя\n\r", node+1);

int temp;

scanf("%i", &temp);

--temp;

if(!temp) likeBro = true;

}

printf("Введите строку для нового элемента: ");

char customString[255];

scanf("%s", customString);

addElemAPI(root, elemNum, likeBro, wide, node, customString);

}

void treeGenerate(treeElem** root, int* elemNum)

{

printf("Введите среднее кол-во элементов в качестве братьев: ");

int broSize;

scanf("%i", &broSize);

if (broSize < 0 || broSize > 4 )

{

printf("Кол-во братьев должно быть в промежутке от 0 до 4");

return;

}

printf("Введите дисперсию: ");

int disp;

scanf("%i", &disp);

if (disp < 0 || disp > 4 )

{

printf("Дисперсия должна быть в промежутке от 0 до 4");

return;

}

printf("Введите общее количество элементов: ");

int size;

scanf("%i", &size);

if (size < 1)

{

printf("Размер не может быть меньше еденицы");

return;

}

--size;

printf("Введите размер ключа: ");

int keysize;

scanf("%i", &keysize);

if (keysize < 1)

{

printf("Размер не может быть меньше еденицы");

return;

}

int start = microtime();

cleanTree(root, elemNum, 1);

int from = broSize - disp;

if (from < 0)

from = 0;

int to = broSize + disp;

if (to > 4)

to = 4;

char tempString[1];

tempString[0] = '\0';

addElemAPI(root, elemNum, 0, 0, 0, tempString, keysize, false); // FAIL, надо передать \0 как строку с 1 символом а не как символ

--size;

// int currElem = *elemNum;

while (size>-1)

{

addElemAPI(root, elemNum, 0, broSize + disp, *elemNum, tempString, keysize, false);

--size;

int smth;

if((to - from) == 0)

smth = 0;

else

smth = (getNormalRand()%(to - from));

for (int i = 0; i < (from + smth); ++i)

{

addElemAPI(root, elemNum, 1, broSize + disp, *elemNum, tempString, keysize, false);

--size;

if(size < 0) break;

}

printf("Все элементы добавлены за %iмс!", microtime()-start);

}

/* int getLink(treeElem** root, int* elemNum, int choose)

{

if (!isExist(root))

return -1;

for(int i = 0; i <= *elemNum; i++)

{

if((*root)[i].child == choose || (*root)[i].bro == choose)

return i;

}

return -1;

} */

void getBro(treeElem** root, int* i) //нужен будет тест когда можно будет добавлять братьев

{

int choose = -1;

if (!isExist(root))

return;

while (choose - 1 < 0 || choose - 1 > *i)

{

system("cls");

printf("Введите номер узла: ");

scanf("%i", &choose);

if (choose - 1 < 0 || choose - 1 > *i)

{

printf("Введенный узел не существует, введите номер заново..");

getch();

}

if ((*root)[choose-1].bro == -1)

{

printf("У этого узла нет брата :(");

return;

}

printf("%i, %s", (*root)[choose-1].bro, (*root)[(*root)[choose-1].bro].key);

}

int searchIndex(treeElem** root, int* elemNum, char* key) // возвращает индекс узла при совпадении ключа и -1 если нет совпадений

{

for(int i = 0; i <= *elemNum; i++)

{

if(!strcmp((*root)[i].key, key)) return i;

}

printf("/n/rИскомый ключ не найден");

return -1;

}

void swipeData(treeElem** root, int *elemNum, int save, int del, bool linking) //save - что переносим, del - вместо чего переносим

{

// (*root)[save].bro = (*root)[del].bro;

// (*root)[save].child = (*root)[del].child;

strcpy((*root)[save].key, (*root)[del].key);

if (linking)

for (int i = 0; i <= *elemNum; i++)

{

if((*root)[i].bro == del) (*root)[i].bro = -1;

if((*root)[i].child == del) (*root)[i].child = -1;

}

return;

}

void makeDel(treeElem** root, int* elemNum, int index)

{

/* int link = parent;

if (link == -1) return;

if (index == (*root)[link].child) (*root)[link].child = -1; // хз нахрена мне этот кусок и под чем я это писал

else

{

link = (*root)[link].child;

while ((*root)[link].bro != index)

{

link = (*root)[link].bro;

}

(*root)[link].bro = -1;

} */

if (index == *elemNum) // тут и далее сжимаем массив, убирая мертвые колонки путем перемещения последнего элемента на место удаленного

{

(*elemNum)--;

*root = (treeElem*) realloc(*root, sizeof(treeElem) * ((*elemNum)+1));

printf("Done");

return;

}

swipeData(root, elemNum, *elemNum, index, 0);

(*elemNum)--;

*root = (treeElem*) realloc(*root, sizeof(treeElem) * ((*elemNum)+1));

printf("Done");

}

void delElem(treeElem** root, int* elemNum)

{

if (!isExist(root))

return;

char key[255];

system("cls");

printf("Введите ключ удаляемого узла: ");

scanf("%s", key);

int index = searchIndex(root, elemNum, key);

if(index == -1) return;

int swipeWith = getMostRightChild(root, index);

if (swipeWith == -1) return;

// int parent = getLink(root, elemNum, index);

if (swipeWith == index) // если элемент является листом

{

makeDel(root, elemNum, index);

return;

}

swipeData(root, elemNum, index, swipeWith, 1);

makeDel(root, elemNum, swipeWith);

}

void printParent(treeElem** root, int* elemNum)

{

int i;

if (!isExist(root))

return;

printf("Введите номер узла, для которого нужно найти родителя: ");

scanf("%i", &i);

i--;

if (i > *elemNum || i < 0)

{

printf("Элемент задан неверно");

return;

}

int result = getParent(root, elemNum, i);

if (result == -1)

{

printf("Элемент является корнем");

return;

}

printf("Родителем является [%i] элемент с ключом [%s]", result+1, (*root)[result].key);

return;

}

void getMostChild(treeElem** root, int* elemNum)

{

if (!isExist(root))

return;

int i;

printf("Введите номер элемента, у которого нужно найти самого крайнего ребенка: ");

scanf("%i", &i);

i--;

if (i > *elemNum || i < 0)

{

printf("Элемент задан неверно");

return;

}

if (!isExist(root))

return;

if((*root)[i].child == -1)

{

printf("Детей нет :(");

return;

}

while ((*root)[i].child != -1)

{

i = (*root)[i].child;

}

printf ("Узел имеет ребенка с индексом [%i] и ключом [%s]", i+1, (*root)[i].key);

return;

}

void callMenu(treeElem** root, int* elemNum)

{

unsigned int choose;

system("cls");

printf("Выберите номер желаемого действия: \n\r\n\r1. Добавить элемент в дерево\n\r2. Вывести дерево\n\r3. Очистить дерево\n\r4. Вывести корень\n\r5. Вывести ключ узла\n\r6. Поиск по ключу\n\r7. Вывести правого соседа узла\n\r8. Вывести крайнего ребенка узла\n\r9. Вывести родителя узла\n\r10. Ввести новый ключ для узла\n\r11. Удалить узел по ключу\n\r12. Сгенерировать дерево\n\r\n\r0.Выход\n\r\n\rВведите номер действия: ");

// choose = _getch() - 48; //магический преобразователь char в int

scanf("%i", &choose);

switch (choose)

{

case 0: return; //Добавить в конец меню потом (0. Выход)

case 1: addElem(root, elemNum); getch(); callMenu(root, elemNum); break;

case 2: system("cls"); printTree(root, 0); getch(); callMenu(root, elemNum); break;

case 3: cleanTree(root, elemNum); getch(); callMenu(root, elemNum); break;

case 4: getRoot(root); getch(); callMenu(root, elemNum); break;

case 5: getKey(root, elemNum); getch(); callMenu(root, elemNum); break;

case 6: searchNode(root); getch(); callMenu(root, elemNum); break;

case 7: getBro(root, elemNum); getch(); callMenu(root, elemNum); break;

case 8: getMostChild(root, elemNum); getch(); callMenu(root, elemNum); break;

case 9: printParent(root, elemNum); getch(); callMenu(root, elemNum); break;

case 10: setKey(root, elemNum); getch(); callMenu(root, elemNum); break;

case 11: delElem(root, elemNum); getch(); callMenu(root, elemNum); break;

case 12: treeGenerate(root, elemNum); getch(); callMenu(root, elemNum); break;

default: callMenu(root, elemNum); break;

}

return;

}

int main()

{

setlocale(LC_ALL, "Russian");

srand(microtime());

treeElem* root = NULL;

int elemNum = -1;

callMenu(&root, &elemNum);

return 0;

}

Контрольный пример

Вывод

При выполнении данной лабораторной работы я получил навыки программирования деревьев.

Список использованной литературы

Шилдт Г. Искусство программирования на C++. БХВ.2005
Шилдт Г. C++ Руководство для начинающих. Вильямс.2005
Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004

Соседние файлы в предмете Структуры и алгоритмы обработки данных

#
20.06.2014342.53 Кб29Задание к ИДЗ блоковые списки.doc
#
20.06.2014462.85 Кб36Задания к лабораторным.doc
#
20.06.201454.68 Кб33ИДЗ (блоковый список).docx
#
20.06.201467.07 Кб20ИДЗ Нелинейные типы данных (стек, дек, очередь, односвязный список).doc
#
20.06.2014536.58 Кб50Лабораторная работа №1 (стек).doc
#
20.06.2014126.98 Кб21Лабораторная работа №1 Вариант №12.doc
#
20.06.2014512.51 Кб19Лабораторная работа №1 Вариант №21.doc
#
20.06.2014110.59 Кб19Лабораторная работа №2 АВЛ-дерево.doc
#
20.06.2014337.92 Кб21Лабораторная работа №2 Вариант №21.doc
#
20.06.2014355.84 Кб27Лабораторная работа №3 Вариант №21.doc
#
20.06.2014278.53 Кб28Лабораторная работа №3 Неор.граф поиск в глубину.doc