Как сделать древовидную структуру в C
Вопрос
Я очень новичок в C. Однако мне нужна программа, которая решает проблему для меня. Как я могу сделать следующее?
Мне нужна древовидная структура. Это не традиционное дерево, так как у каждого листа может быть много разных листьев. Поэтому каждый лист должен содержать связанный список, который содержит дочерние элементы листа. В каждой ссылке есть массив char [] [] и несколько переменных типа int, которые сообщают, насколько хорош лист. А затем мне нужно выполнить поиск в лучшем случае, чтобы найти лучший массив char [] [] и вывести его. Если я найду подходящий массив, я могу остановить обход дерева.
Решение
Мне бы хотелось, чтобы связанный список сортировался во время вставки, чтобы вы всегда могли вернуть первый элемент списка в узле дерева.
Что-то вроде
struct listnode {
char** data;
int quality;
struct listnode* next;
};
struct treenode {
struct treenode* left;
struct treenode* right;
int key;
struct listnode* list;
};
struct treenode* tree_insert(struct treenode* root, int key, int quality, char** data)
{
if(root == NULL) {
root = treenode_alloc();
root->key = key;
root->list = list_insert(root->list, quality, data);
return root;
}
if(key < root->key) {
root->left = tree_insert(root->left, key, quality, data);
} else if(key > root->key) {
root->right = tree_insert(root->right, key, quality, data);
} else {
//key == root->key
root->list = list_insert(root->list, quality, data);
}
return root;
}
struct listnode* list_insert(struct listnode* head, int quality, char** data) {
struct listnode* prev = NULL;
struct listnode* ins = NULL;
struct listnode* ptr = NULL;
if(head == NULL) {
head = listnode_alloc();
head->quality = quality;
head->data = data;
return head;
}
ptr = head;
while(quality < ptr->quality) {
if(ptr->next == NULL) { //we reached end of list
ptr->next = list_insert(NULL, quality, data);
return head;
}
prev = ptr;
ptr = ptr->next;
}
//insertion into middle of list (before ptr, because ptr->quality >= quality)
ins = listnode_alloc();
ins->quality = quality;
ins->data = data;
ins->next = ptr;
if(prev) {
prev->next = ins;
}
return head;
}
Другие советы
arrayindex - это информация о местоположении, поэтому больше информации, чем фактические элементы - это индекс, arrayelement - это данные, хорошие ключевые слова fordfulkersson , trie datamodel для химии, b-tree для классики логика, breadthfirstsearch, concordance базы данных, куча или а именно стек (LIFO)
изучите структуры данных & amp; Алгоритмы ... Википедия - хорошее место для поиска.