Mensajes

La raiz es el primer nodo que se inserta..

Su padre es null.

Tus funciones de inOrden o preorden son recursivas y no necesitan saber quien es el padre, aun asi gastan mas memoria. En funciones iterativas es mecesario saber quien es el podre y gastan menos memoria.

En ocasiones es necesario separar subarboles o eliminar arboles completos, y tambien facilita mucho tener una referencia al padre.

Basicamente es una facilidad tener esa referencia en fumciones iterarivas.

Como reto deberias de hacer tu funcion inOrden y preOrden de forma iterativa, Esto es sin llamar a las funciones dichas desde si mismas.

Saludos!

Hola

Código (c) [Seleccionar] Expandir

if( borrar->siguiente == NULL){ //Supongo que aqui estas evaluanfo por el ultimo Nodo
//a esta altura el nodo a borrar es el ultimo
struct nodo *aux = L->primero;
while( aux->siguiente != borrar ){
aux = aux->siguiente;
        }
//a esta altura el nodo aux es el penultimo
L->ultimo = aux; //El que antes era penultimo ahora sera el ultimo
L->elementos--;
aux->siguiente = NULL; //El apuntador siguiente del ultimo Nodo debe de apuntar a NULL
free( borrar );
}

[Busca como implementar una busqueda binaria y el algoritmo de disjktra es lo mas rapido que vas a encontrar y terminarias usando menos memoria.]

Hola.

pensaba en una búsqueda binario aunque según yo que no es posible.

Los arboles binarios por su diseño implementan una busqueda binaria


Si lo quieres manejar manualmente en un array tendrias que ordenarlos para posteriormente hacer una búsqueda binaria.

Calcule la memoria que usaria mi codigo y seria cerca de 2 MB en el peor de los casos (100000) inputs.

hay veces que me complico programando en C ya que me gusta saber que hace exactamente el codigo. Lo que tu haces con un simple cin>>  yo lo hago como con 10 lineas de codigo y au que son muchas lineas siento que se ejecuta igual de rapido que un cin o incluso mas rapido aun...

Busca como implementar una busqueda binaria y el algoritmo de disjktra es lo mas rapido que vas a encontrar y terminarias usando menos memoria.

Voy a adaptar mi codigo a C++ para que veas como funciona.

Mientras te dejo unos videos que hice de arboles binarios

[youtube=640,360]https://www.youtube.com/watch?v=BBsgYwXGdI8[/youtube]

[youtube=640,360]https://www.youtube.com/watch?v=hlWvK1EU-oA[/youtube]

Saludos

Varios detalles:
El programa no sabe "apriori" cuanto espacio va a necesitar cada cadena.

Un apuntador debe de apuntar a una sección valida de memoria. Actualmente tus apuntadores no apuntan a ningun lado.

De lo anterior es la mitad solo la mitad es cierto. Tus apuntadores no esten inicializados y tienen "basura" de la pila... con lo cual se me hace increible que llegaras al tercer apuntador.

En fin son muchad cosas mas, Otra es el titulo de este tema...

Mientras te dejo mas consejos en video

[youtube=640,360]https://www.youtube.com/watch?v=mG8_nY3Yzg4[/youtube]

Saludos

Titulos sugeridos:

Código [Seleccionar] Expandir

¿Mejor algoritmo? Problema con aproximaciones de Grafos

Código [Seleccionar] Expandir

Optimizar algoritmo para busqueda de elementos

Saludos

Pues a mi me parece algo incorrecta la forma de interpretar la lectura ya que ahi hablan de solo u  amigo en comun.

un dato curioso es que si existen tres invidividuos A, C, B pertenecientes al espacio, y A es amigo de C y C amigo de B, se genera un lazo mistico mediante el cual A y B son amigos,

Y la implementacion esta hablando del amigo del amigo del amigo.

EN FIN...

La implementacion podria ser cualquier arbol binario para optimizar las busquedas aunque el hecho de tener un arbol por individuo usa mucha memoria.

En minuto mas pongo mi implementacion ( La cual solo aborda el primer ejemplo que yo dije donde solo valido a los amigos del primer amigo)

Código (c) [Seleccionar] Expandir

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>

#define MAXLINE 40

struct nodo_arbol {
struct nodo_arbol *padre,*derecho,*izquierdo;
int valor;
};

struct nodo {
int id;
int *relations;
int total;
struct nodo_arbol *arbol;
};

struct nodo **todos = NULL; //Futuro arreglo de todos los nodos existente

void add_relation(int A,int B);
bool existe_salto(int A,int B);

struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor);
struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar);
struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor);


int main() {
FILE *in = NULL;
char *line = NULL;
char *delim = " \n";
char *token;
char caso;
int N,M,i,A,B;
in = fopen("amistad.in","r");
line = calloc(MAXLINE,1);
fgets(line,MAXLINE,in);
token = strtok(line,delim);
N = strtol(token,NULL,10);
todos = calloc(sizeof(struct nodo*),N); //Reservamos espacio para al menos N apuntadores a los nodos
token = strtok(NULL,delim);
M = strtol(token,NULL,10);
i = 0;
while(i < M) {
memset(line,0,MAXLINE);
fgets(line,MAXLINE,in);
token = strtok(line,delim);
caso = token[0];
token = strtok(NULL,delim);
A = strtol(token,NULL,10);
A--;
token = strtok(NULL,delim);
B = strtol(token,NULL,10);
B--;
switch(caso){
case 'P':
//printf("P %i %i\n",A+1,B+1);
if(todos[A] && todos[B]) { // Ambos nodos son Validos, entonces hay que buscar si existe al menos un camino de a A a B
if(existe_salto(A,B)) {
printf("1\n");
}
else {
printf("0\n");
}
}
else { // Uno de los nodos es NULL entonces no existe camino de A a B
//printf("Un nodo es invalido\n");
printf("0\n");
}
break;
case 'S':
//printf("S %i %i\n",A+1,B+1);
add_relation(A,B);
break;
}
i++;
}
fclose(in);
return 0;
}

void add_relation(int A,int B) {
if(todos[A] != NULL) {
//Nodo ya inicializado;
todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
todos[A]->relations[todos[A]->total] = B;
todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
todos[A]->total++; //incrementamos el numero total de relaciones que tiene este nodo
}
else {
//Nodo no inicializado
todos[A] = calloc(sizeof(struct nodo),1);
todos[A]->id  = A; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
todos[A]->relations = realloc(todos[A]->relations,sizeof(int)*(todos[A]->total+1));
todos[A]->relations[todos[A]->total] = B;
todos[A]->arbol = agregar_valor_arbol(todos[A]->arbol,B);
todos[A]->total++; //incrementamos el numero total de relaciones que tiene este nodo
}
if(todos[B] != NULL) {
//Nodo ya inicializado;
todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
todos[B]->relations[todos[B]->total] = A;
todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
todos[B]->total++; //incrementamos el numero total de relaciones que tiene este nodo
}
else {
//Nodo no inicializado
todos[B] = calloc(sizeof(struct nodo),1);
todos[B]->id  = B; //Esto es mera formalidad, ya que actualmente el indice del arreglo ya es el mismo "id"
todos[B]->relations = realloc(todos[B]->relations,sizeof(int)*(todos[B]->total+1));
todos[B]->relations[todos[B]->total] = A;
todos[B]->arbol = agregar_valor_arbol(todos[B]->arbol,A);
todos[B]->total++; //incrementamos el numero total de relaciones que tiene este nodo

}
}

bool existe_salto(int A,int B) {
bool r = false;
struct nodo *nodo_a = NULL,*nodo_b =NULL,*inicio =NULL,*pivote = NULL;
struct nodo_arbol *busqueda = NULL;
register int i,j,buscar;
nodo_a = todos[A];
nodo_b = todos[B];
if(nodo_a->total < nodo_b->total) {
//printf("Menor A %i\n",A+1);
inicio = nodo_a;
buscar = B;
}
else {
//printf("Menor B %i\n",B+1);
inicio = nodo_b;
buscar = A;
}
i = 0;
//printf("Nodos: ");
while(i < inicio->total && !r) {
//printf("%i\t ",inicio->relations[i]+1);
busqueda = buscar_nodo_arbol(inicio->arbol,buscar);
if(busqueda) {
r = true;
}
i++;
}
//printf("\n");
if(!r) {
i = 0;
while(i < inicio->total && !r) {
pivote = todos[inicio->relations[i]];
j = 0;
//printf("Nodos de %i:  ",inicio->relations[i]+1);
while(j < pivote->total && !r) {
busqueda = buscar_nodo_arbol(pivote->arbol,buscar);
//printf("%i\t ",pivote->relations[j]+1);
if(busqueda) {
r = true;
}
j++;
}
//printf("\n");
i++;
}
}
return r;
}


struct nodo_arbol *crear_nodo_arbol(struct nodo_arbol *padre,int valor) {
struct nodo_arbol *n = calloc(sizeof(struct nodo_arbol),1);
if(n == NULL) {
printf("Error de Memoria\n");
exit(0);
}
n->padre = padre;
n->valor = valor;
return n;
}

struct nodo_arbol *agregar_valor_arbol(struct nodo_arbol *arbol,int valor) {
struct nodo_arbol *temp,*pivote;
int derecho = 0;
if(arbol) {
temp =arbol;
while(temp != NULL) {
pivote = temp;
if(valor > temp->valor) {
temp = temp->derecho;
derecho = 1;
}
else {
temp = temp->izquierdo;
derecho = 0;
}
}
temp = crear_nodo_arbol(pivote,valor);
if(derecho) {
pivote->derecho = temp;
}
else {
pivote->izquierdo = temp;
}
return arbol;
}
else {
temp = crear_nodo_arbol(NULL,valor);
return temp;
}
}

struct nodo_arbol *buscar_nodo_arbol(struct nodo_arbol *arbol,int valorAbuscar) {
struct nodo_arbol *temp = NULL,*pivote = NULL;
int entrar = 1;
temp =arbol;
while(entrar == 1  && temp != NULL) {
pivote = temp;
if(valorAbuscar == temp->valor){
entrar = 0;
}
else {
if(valorAbuscar > temp->valor) {
temp = temp->derecho;
}
else {
temp = temp->izquierdo;
}
}
}
return temp;
}

Solo habria que extenderla para que revise todos los nodos.

Saludoa

Es posible usar una variable como formato de cadena claro, perto tiene que ser una variable cadena, y la cadena debe de ser valida.

Si te interesa ver ese tipo de errores con el printf, estan los bugs llamados format string los cuales se producen al usar incorrectamente printf, o cadenas malformadas

Busca por:

Código [Seleccionar] Expandir

format string bugs

Saludos!

Es anonimato es posible mientras nunca relaciones tu Nombre o IP con determinada cartera lo cual es muy difícil.

¿Hay cajeros donde puedes canjear bitcoints por dinero efectivo? Eso no lo sabia


Saludos!

En lenguaje C, la funcion printf necesita un formato de cadena, no es como cout de C++ que reconoce el tipo de variable y la imprime como tal.

Código (c) [Seleccionar] Expandir

   printf("%i",edad);

Saludos!

Es uno de varios tipos de almacenamiento.

Para enternder esto hay que comprender donde se almacen las variables, por lo general lenguajes como C++ u otros de mayor nivel no entran en tando detalle de donde se almancena las variables.

Las variables locales de las funciones y determinadas variables se almacenan en la Pila y cuando se usa memoria dinamica por lo general se almacena en el Heap.

Por lo que leo en : http://www.gotw.ca/gotw/009.htm

El free store es algo similar al heap (De hecho es lo mismo) solo por llamarlo de otra forma para diferenciarlo del heap asignado mediante "malloc". Este el (free store ) es un area de almacenamiento para las instancias de las clases usadas en la POO y es asignado mediante "new"

Saludos