Pers.narod.ru. Алгоритмы. Упражнения на бинарные деревья и списки

Вершина дерева содержит динамический массив целых значений и два указателя на потомков. Значения в дереве не упорядочены. Размерность динамического массива в корневой вершине - N, на каждом следующем уровне - в 2 раза больше. Функция включает новое значение в свободное место в массиве ближайшей к корню вершины.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N 2
 
typedef struct tree {
	char *value;
	unsigned int size;
	struct tree **child;
} TREE;
 
TREE *CreateNode(char *value, unsigned int size)
{
	TREE *new_node = (TREE *) malloc(sizeof(TREE));
	new_node->value = (char *) malloc(strlen(value) + 1);
	strcpy(new_node->value, value);
	new_node->size = size;
	new_node->child = (TREE **) malloc(sizeof(TREE) * new_node->size);
	for(unsigned int i = 0; i < new_node->size; i++)
		*(new_node->child + i) = NULL;
	return (new_node);
}
 
TREE *found_node;
 
void ScanTree(TREE *node)
{
	if(node == NULL)
		return;
	for(unsigned int i = 0; i < node->size; i++)
		if(node->child[i] == NULL) {
			if(found_node == NULL) {
				found_node = node;
				break;
			}
			else {
				if(node->size < found_node->size) {
					found_node = node;
					break;
				}
			}
		}
	for(i = 0; i < node->size; i++)
		ScanTree(node->child[i]);
	return;
}
 
TREE *InsertNode(TREE *root, char *value)
{
	TREE *new_node = NULL;
	if(root == NULL) {
		root = CreateNode(value, N);
		return (root);
	}
	found_node = NULL;
	ScanTree(root);
	new_node = CreateNode(value, found_node->size * 2);
	for(unsigned int i = 0; i < found_node->size; i++)
		if(found_node->child[i] == NULL) {
			found_node->child[i] = new_node;
			break;
		}
	return (new_node);
}
 
void main(void)
{
	TREE * root = NULL;
	root = InsertNode(root, "root");
	InsertNode(root, "child_1");
	InsertNode(root, "child_2");
	InsertNode(root, "child_3");
	InsertNode(root, "child_4");
	InsertNode(root, "child_5");
	InsertNode(root, "child_6");
        //Добавьте здесь вывод того, что получается
}

Вершина дерева содержит массив целых и два указателя на правое и левое поддерево. Значения в дереве не упорядочены. Естественная нумерация значений производится путем обхода дерева по принципу " левое поддерево - вершина - правое поддерево" . Разработать функции включения и получения значения элемента по заданному логическому номеру.

#include <stdio.h>
#include <stdlib.h>
#include <values.h>
 
#define N 2
 
typedef struct tree {
	int *value;
	unsigned int size;
	struct tree **child;
} TREE;
 
TREE *CreateNode(unsigned int size)
{
	TREE *new_node = (TREE *) malloc(sizeof(TREE));
	new_node->value = (int *) malloc(sizeof(int) * size);
	new_node->size = size;
	new_node->child = (TREE **) malloc(sizeof(TREE) * 2);
	for(unsigned int i = 0; i < new_node->size; i++)
		*(new_node->value + i) = MAXINT;
	for(i = 0; i < 2; i++)
		*(new_node->child + i) = NULL;
	return (new_node);
}
 
TREE *found_node;
unsigned int found_index;
 
void ScanTreeIndex(TREE *node)
{
	int found;
	if(node == NULL)
		return;
	for(unsigned int i = 0; i < 2; i++)
		if(node->child[i] == NULL) {
			if(found_node == NULL) {
				found = 0;
				for(unsigned int j = 0; j < node->size; j++)
					if(node->value[j] == MAXINT) {
						found = 1;
						break;
					}
				if(found) {
					found_node = node;
					found_index = j;
					break;
				}
			}
			else {
				if(node->size < found_node->size) {
					found = 0;
					for(unsigned int j = 0; j < node->size; j++)
						if(node->value[j] == MAXINT) {
							found = 1;
							break;
						}
					if(found) {
						found_node = node;
						found_index = j;
						break;
					}
				}
			}
		}
	for(i = 0; i < node->size; i++)
		ScanTreeIndex(node->child[i]);
	return;
}
 
void ScanTree(TREE *node)
{
	if(node == NULL)
		return;
	for(unsigned int i = 0; i < 2; i++)
		if(node->child[i] == NULL) {
			if(found_node == NULL) {
				found_node = node;
				break;
			}
			else {
				if(node->size < found_node->size) {
					found_node = node;
					break;
				}
			}
		}
	for(i = 0; i < node->size; i++)
		ScanTree(node->child[i]);
	return;
}
 
TREE *InsertNode(TREE *root, int value)
{
	TREE *new_node = NULL;
	if(root == NULL) {
		new_node = CreateNode(N);
		new_node->value[0] = value;
		return (new_node);
	}
	found_node = NULL;
	found_index = MAXINT;
	ScanTreeIndex(root);
	if((found_node != NULL) && (found_index != MAXINT))
		found_node->value[found_index] = value;
	else {
		found_node = NULL;
		found_index = MAXINT;
		ScanTree(root);
		new_node = CreateNode(found_node->size * 2);
		new_node->value[0] = value;
		for(unsigned int i = 0; i < 2; i++)
			if(found_node->child[i] == NULL) {
				found_node->child[i] = new_node;
				break;
			}
	}
	return (new_node);
}
 
void main(void)
{
	TREE * root = NULL;
	root = InsertNode(root, 1);
	InsertNode(root, 2);
	InsertNode(root, 3);
	InsertNode(root, 4);
	InsertNode(root, 5);
	InsertNode(root, 6);
	InsertNode(root, 7);
        //Добавьте здесь вывод того, что получается
}

Список - каждый элемент является заголовком односвязного списка. Элемент списка второго уровня содержит указатель на строку. Включение и удаление по логическому номеру. Включение элемента последним в список производить с учетом выравнивания длины текущего и следующего списков. В этой программке даже печать есть :)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define N 3
 
typedef struct slavelist {
	char *value;
	struct slavelist *next;
} SLAVELIST, *PSLAVELIST;
 
typedef struct mainlist {
	PSLAVELIST slave;
	struct mainlist *next;
} MAINLIST, *PMAINLIST;
 
PSLAVELIST CreateSlave(char *value)
{
	PSLAVELIST new_elem = (PSLAVELIST) malloc(sizeof(SLAVELIST));
	new_elem->value = (char *) malloc(strlen(value) + 1);
	strcpy(new_elem->value, value);
	new_elem->next = NULL;
	return (new_elem);
}
 
PMAINLIST CreateMain(void)
{
	PMAINLIST new_elem = (PMAINLIST) malloc(sizeof(MAINLIST));
	new_elem->next = NULL;
	return (new_elem);
}
 
unsigned int GetSize(PMAINLIST elem)
{
	unsigned int size = 0;
	PSLAVELIST slave_elem = elem->slave;
	while(slave_elem) {
		size++;
		slave_elem = slave_elem->next;
	}
	return (size);
}
 
unsigned int GetElementByNumberForAdd(PMAINLIST root, unsigned int number, PMAINLIST *pelem, PSLAVELIST *pslave_elem)
{
	unsigned int counter = 0;
	PMAINLIST elem;
	PSLAVELIST slave_elem;
	*pelem = NULL;
	*pslave_elem = NULL;
	elem = root;
	while(elem) {
		slave_elem = elem->slave;
		while(slave_elem) {
			if(counter ++ == number - 1) {
				*pelem = elem;
				*pslave_elem = slave_elem;
			}
			slave_elem = slave_elem->next;
		}
		elem = elem->next;
	}
	return (counter);
}
 
unsigned int GetElementByNumberForDelete(PMAINLIST root, unsigned int number, PMAINLIST *pelem, PSLAVELIST *pslave_elem)
{
	unsigned int counter = 0;
	PMAINLIST elem;
	PSLAVELIST slave_elem;
	*pelem = NULL;
	*pslave_elem = NULL;
	elem = root;
	while(elem) {
		slave_elem = elem->slave;
		while(slave_elem) {
			if(counter ++ == number) {
				*pelem = elem;
				*pslave_elem = slave_elem;
			}
			slave_elem = slave_elem->next;
		}
		elem = elem->next;
	}
	return (counter);
}
 
PSLAVELIST ScanListForAdd(PMAINLIST elem)
{
	PSLAVELIST slave_elem = elem->slave;
	PSLAVELIST temp_slave_elem;
	while(slave_elem->next->next)
		slave_elem = slave_elem->next;
	temp_slave_elem = slave_elem->next;
	slave_elem->next = NULL;
	return (temp_slave_elem);
}
 
PMAINLIST AddNewElement(PMAINLIST root, char *value, unsigned int number)
{
	PMAINLIST elem, temp_elem;
	PSLAVELIST slave_elem, found_slave_elem, new_slave_elem, temp_slave_elem;
	if((root == NULL) && (number != 0))
		return (NULL);
	if(root == NULL) {
		elem = CreateMain();
		new_slave_elem = CreateSlave(value);
		elem->slave = new_slave_elem;
		return (elem);
	}
	found_slave_elem = NULL;
	if(GetElementByNumberForAdd(root, number, &elem, &found_slave_elem) < number)
		return (NULL);
	new_slave_elem = CreateSlave(value);
	elem = root;
	if(found_slave_elem != NULL) {
		temp_slave_elem = found_slave_elem->next;
		found_slave_elem->next = new_slave_elem;
		new_slave_elem->next = temp_slave_elem;
	}
	else {
		temp_slave_elem = root->slave;
		root->slave = new_slave_elem;
		new_slave_elem->next = temp_slave_elem;
	}
	elem = root;
	temp_elem = NULL;
	while(elem) {
		if(GetSize(elem) > N) {
			temp_elem = elem;
			break;
		}
		elem = elem->next;
	}
	if(temp_elem != NULL) {
		temp_slave_elem = NULL;
		while(temp_elem) {
			if(GetSize(temp_elem) > N) {
				temp_slave_elem = ScanListForAdd(temp_elem);
				if(temp_slave_elem) {
					if(temp_elem->next) {
						temp_elem = temp_elem->next;
						found_slave_elem = temp_elem->slave;
						temp_elem->slave = temp_slave_elem;
						temp_slave_elem->next = found_slave_elem;
						continue;
					}
					else {
						elem = CreateMain();
						elem->slave = temp_slave_elem;
						temp_elem->next = elem;
						break;
					}
				}
			}
			temp_elem = temp_elem->next;
		}
	}
	return (elem);
}
 
int DeleteElement(PMAINLIST *proot, unsigned int number)
{
	PMAINLIST elem, temp_elem;
	PSLAVELIST slave_elem, temp_slave_elem;
	if(*proot == NULL)
		return (0);
	if(GetElementByNumberForDelete(*proot, number, &elem, &slave_elem) < number)
		return (0);
	if((*proot == elem) && ((*proot)->slave == slave_elem) && 
           (slave_elem->next == NULL) && ((*proot)->next == NULL)) {
		delete slave_elem->value;
		delete slave_elem;
		delete *proot;
		*proot = NULL;
		return (1);
	}
	if(elem->slave == slave_elem) {
		elem->slave = slave_elem->next;
		delete slave_elem->value;
		delete slave_elem;
		if(elem->slave == NULL) {
			temp_elem = *proot;
			if(*proot == elem)
				*proot = elem->next;
			else {
				while(temp_elem->next != elem)
					temp_elem = temp_elem->next;
				temp_elem->next = elem->next;
			}
			delete elem;
		}
	}
	else {
		temp_slave_elem = elem->slave;
		while(temp_slave_elem->next != slave_elem)
			temp_slave_elem = temp_slave_elem->next;
		temp_slave_elem->next = slave_elem->next;
		delete slave_elem->value;
		delete slave_elem;
	}
	return (1);
}
 
void PrintAllLists(PMAINLIST root)
{
	PMAINLIST elem;
	PSLAVELIST slave_elem;
	unsigned int count = 0;
	unsigned int count_slave = 0;
	elem = root;
	while(elem) {
		count++;
		printf("main element: %u\n", count);
		slave_elem = elem->slave;
		while(slave_elem) {
			printf("\tslave element: %s %d\n", slave_elem->value, count_slave ++);
			slave_elem = slave_elem->next;
		}
		elem = elem->next;
	}
	return;
}
 
void main(void)
{
	PMAINLIST root = AddNewElement(NULL, "first", 0);
	AddNewElement(root, "second", 1);
	AddNewElement(root, "third", 2);
	AddNewElement(root, "fourth", 3);
	AddNewElement(root, "fifth", 4);
	AddNewElement(root, "sixth", 5);
	AddNewElement(root, "seventh", 5);
	PrintAllLists(root);
	DeleteElement(&root, 6);
	DeleteElement(&root, 0);
	PrintAllLists(root);
	return;
}

Рейтинг@Mail.ru

вверх гостевая; E-mail
Hosted by uCoz