Двунаправленный список
Сегодня я увидел этот вопрос на stackexchange. Сначала просто сделал комментарий, но потом решил: а ведь стоит сделать реализацию дерева и двунаправленного списка, пригодится же когда-нибудь!
Для начала - то, что попроще: двунаправленный список.
#include #include #include typedef struct list_node{ int data; struct list_node *left_p, *right_p; } List; List *l_search(List *root, int v, List **Left, List **Right){ List *L = NULL, *R = NULL; int dir = -1; if(!root) goto not_Fnd; if(root->data == v) return root; if(root->data < v) dir = 1; do{ L = root->left_p; // left leaf R = root->right_p; // right leaf int D = root->data;// data in leaf if(D > v && dir == -1){ // search to left is true R = root; root = L; } else if(D < v && dir == 1){ // search to right is true L = root; root = R; } else if(D == v){ // we found exact value if(Left) *Left = L; if(Right) *Right = R; return root; } else break; }while(root); // if root == NULL, we catch an edge // exact value not found if(root){ // we aren't on an edge if(dir == -1) L = root; else R = root; } not_Fnd: if(Left) *Left = L; if(Right) *Right = R; return NULL; // value not found } List *l_insert(List *root, int v){ List *node, *L, *R; node = l_search(root, v, &L, &R); if(node) return node; // we found exact value V // there's no exact value: insert new if((node = (List*) malloc(sizeof(List))) == 0) return NULL; // allocation error node->data = v; // insert data // add neighbours: node->left_p = L; node->right_p = R; // fix neighbours: if(L) L->right_p = node; if(R) R->left_p = node; return node; } void l_remove(List **root, int v){ List *node, *left, *right; if(!root) return; if(!*root) return; node = l_search(*root, v, &left, &right); if(!node) return; // there's no such element if(node == *root) *root = node->right_p; if(!*root) *root = node->left_p; free(node); if(left) left->right_p = right; if(right) right->left_p = left; } int main(void) { List *tp, *root_p = NULL; int i, ins[] = {4,2,6,1,3,4,7}; for(i = 0; i < 7; i++) if(!(root_p = l_insert(root_p, ins[i]))) err(1, "Malloc error"); // can't insert for(i = 0; i < 9; i++){ tp = l_search(root_p, i, NULL, NULL); printf("%d ", i); if(!tp) printf("not "); printf("found\n"); } printf("now delete items 1, 4 and 8\n"); l_remove(&root_p, 1); l_remove(&root_p, 4); l_remove(&root_p, 8); for(i = 0; i < 9; i++){ tp = l_search(root_p, i, NULL, NULL); printf("%d ", i); if(!tp) printf("not "); printf("found\n"); } return 0; }
Код - полная реализация операций поиска и вставки элемента двунаправленного списка. Функция l_search ищет элемент с нужными данными. Если не находит - возвращает NULL, а еще она возвращает соседей элемента с нужными данными (даже если его не существует): это нужно для правильной работы функции l_insert. Функция l_remove удаляет элемент списка. Т.к. может быть ситуация, когда удалить нужно "корень", эта функция принимает ссылку на "корень" в аргументах.
Т.к. список двунаправленный, "корнем" его является любой элемент списка.
Деревья реализовал пока только поверхностно (сунул в ответ на stackoverflow), нужно еще воткнуть удаление узла + (возможно) построение пути до узла. А еще можно было бы над более сложными деревьями подумать.
P.S. Т.к. пока реализации тупо на уровне "сниппетов", в них нет самого важного - данных. Но это легко реализуется добавлением нужного типа данных в структуры.
Для начала - то, что попроще: двунаправленный список.
#include #include #include typedef struct list_node{ int data; struct list_node *left_p, *right_p; } List; List *l_search(List *root, int v, List **Left, List **Right){ List *L = NULL, *R = NULL; int dir = -1; if(!root) goto not_Fnd; if(root->data == v) return root; if(root->data < v) dir = 1; do{ L = root->left_p; // left leaf R = root->right_p; // right leaf int D = root->data;// data in leaf if(D > v && dir == -1){ // search to left is true R = root; root = L; } else if(D < v && dir == 1){ // search to right is true L = root; root = R; } else if(D == v){ // we found exact value if(Left) *Left = L; if(Right) *Right = R; return root; } else break; }while(root); // if root == NULL, we catch an edge // exact value not found if(root){ // we aren't on an edge if(dir == -1) L = root; else R = root; } not_Fnd: if(Left) *Left = L; if(Right) *Right = R; return NULL; // value not found } List *l_insert(List *root, int v){ List *node, *L, *R; node = l_search(root, v, &L, &R); if(node) return node; // we found exact value V // there's no exact value: insert new if((node = (List*) malloc(sizeof(List))) == 0) return NULL; // allocation error node->data = v; // insert data // add neighbours: node->left_p = L; node->right_p = R; // fix neighbours: if(L) L->right_p = node; if(R) R->left_p = node; return node; } void l_remove(List **root, int v){ List *node, *left, *right; if(!root) return; if(!*root) return; node = l_search(*root, v, &left, &right); if(!node) return; // there's no such element if(node == *root) *root = node->right_p; if(!*root) *root = node->left_p; free(node); if(left) left->right_p = right; if(right) right->left_p = left; } int main(void) { List *tp, *root_p = NULL; int i, ins[] = {4,2,6,1,3,4,7}; for(i = 0; i < 7; i++) if(!(root_p = l_insert(root_p, ins[i]))) err(1, "Malloc error"); // can't insert for(i = 0; i < 9; i++){ tp = l_search(root_p, i, NULL, NULL); printf("%d ", i); if(!tp) printf("not "); printf("found\n"); } printf("now delete items 1, 4 and 8\n"); l_remove(&root_p, 1); l_remove(&root_p, 4); l_remove(&root_p, 8); for(i = 0; i < 9; i++){ tp = l_search(root_p, i, NULL, NULL); printf("%d ", i); if(!tp) printf("not "); printf("found\n"); } return 0; }
Код - полная реализация операций поиска и вставки элемента двунаправленного списка. Функция l_search ищет элемент с нужными данными. Если не находит - возвращает NULL, а еще она возвращает соседей элемента с нужными данными (даже если его не существует): это нужно для правильной работы функции l_insert. Функция l_remove удаляет элемент списка. Т.к. может быть ситуация, когда удалить нужно "корень", эта функция принимает ссылку на "корень" в аргументах.
Т.к. список двунаправленный, "корнем" его является любой элемент списка.
Деревья реализовал пока только поверхностно (сунул в ответ на stackoverflow), нужно еще воткнуть удаление узла + (возможно) построение пути до узла. А еще можно было бы над более сложными деревьями подумать.
P.S. Т.к. пока реализации тупо на уровне "сниппетов", в них нет самого важного - данных. Но это легко реализуется добавлением нужного типа данных в структуры.