Емельянов Эдуард Владимирович (eddy_em) wrote,
Емельянов Эдуард Владимирович
eddy_em

Двунаправленный список

Сегодня я увидел этот вопрос на stackexchange. Сначала просто сделал комментарий, но потом решил: а ведь стоит сделать реализацию дерева и двунаправленного списка, пригодится же когда-нибудь!
Для начала — то, что попроще: двунаправленный список.
#include <stdio.h>
#include <stdlib.h>
#include <err.h>

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. Т.к. пока реализации тупо на уровне "сниппетов", в них нет самого важного — данных. Но это легко реализуется добавлением нужного типа данных в структуры.
Tags: c, snippets
Subscribe

promo eddy_em september 3, 12:13 8
Buy for 10 tokens
Уже больше полугода занимаюсь разработкой, вот, наконец-то в мастерских взялись за меня и начали выдавать первые детали. Сегодня сделал тестовую сборку (как обычно, местами пришлось "доработать напильником"): Пока прибор без названия (да и как-то не лезет в голову ничего, у меня нет…
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic
  • 0 comments