Allocation dyna de variable pointeur ou Recompilation auto

Version imprimable

11/12/2015, 17h48
marchrysostome

Allocation dyna de variable pointeur ou Recompilation auto

bonjour,:)

Voila mon problème,
J'aimerais numéroter tout les arbre d'un graphe à taille indéterminé.

Pour les numéroter , j'utilise une suite génératrice de nombre premier, qui croit assez rapidement.
Mon problème est que je n'arrive pas à trouver une technique pour les retrouver rapidement , de tel sorte que ,
J'ai un fonction trouverArbre(double numero) et elle me renvoie le pointeur sur l'arbre associé.

Il faudrait, qu'a chaque création d'arbre, je crée un pointeur qui lui est propre, associé au numéro.
Je ne peux pas utiliser de tableau car, ça userais énormément de place, étant donné que les case ne sont pas successive.
De plus la recherche serait trop longue, j'ai pensé au vector en C++ mais ça gâcherait de même un place conséquente, encore plus que en C si je trier par ordre croissant.:roll:

La seule technique que j'ai trouver, c'est avec l'écriture de fichier, j'assigne une lettre (entre a et j) à chaque chiffre de 0 à 9, et je réécrit dans un fichier exemple: tree aesjgh suivie d'un return aesjgh, mais après il faut que je fasse un système de macro qui recompile automatiquement .
Ca à l'air bien compliqué.:aie:

Donc si vous connaissais une technique plus simple je suis preneur, sinon si vous savez comment faire de la recompilation auto d'un fichier .c à partir d'un executable en C ça m'aiderais beaucoup aussi.

Merci d'avance!:)
11/12/2015, 18h17
Matt_Houston

Je crois que tu confonds les termes arbre et nœud. Un arbre est un type de graphe et un graphe contient des nœuds, pas des arbres (encore que les nœuds peuvent êtres des arbres mais là on part sur autre chose :P).

Il te faut une structure de donnée ordonnée pour pouvoir effectuer une recherche dichotomique d'entier : liste triée, tableau trié, arbre. Là comme cela, je partirais vers un arbre binaire. Il existe de nombreuses manière d'implémenter un arbre et de l'équilibrer en fonction de la fréquence et du type des opérations que tu auras à faire dessus. Sache qu'un arbre n-aire peut être implémenté sous forme de tableau. 8-)

C'est plus de l'algorithmique que du C pour l'instant.
11/12/2015, 18h38
marchrysostome

Je parle bien d'arbre car les noeuds dans ma structure , peuvent être réutiliser dans d'autre arbre, en fait, mais oui l'arbre contient plusieurs noeuds, et du coup la foret de mes arbres est bien un graph, mais je numérote les graphe car il représente les connexion du noeud à la racine
C'est pour un projet perso d'IA, j'essaye de créer une structure similaire au cerveau.
Oui du coup ta solution est la meilleur, j'y est pensé entre temps, à faire un noeud contenant des pointeur équivalent à chaque chiffre les chiffre de 0 à 9, pointant eux même vers un autre noeud similaire, ainsi de suite...
11/12/2015, 19h25
Abacar94

Citation:

Envoyé par marchrysostome

j'essaye de créer une structure similaire au cerveau.
.

alors là faut voire avec le langage LISPE il est plus adapter pour l'intelligence artificiel :mouarf:
en fin bref, je croit que tu doit faire sa comme un dictionnaire de typeII
11/12/2015, 19h28
Obsidian

EDIT : messagé rédigé avant les commentaires ci-dessus.

Bonjour et bienvenue,

Citation:

Envoyé par marchrysostome

Voila mon problème,
J'aimerais numéroter tout les arbre d'un graphe à taille indéterminé.

Les arbres ou les nœuds ?
Ton graphe peut-il contenir des cycles ?

Citation:

Pour les numéroter , j'utilise une suite génératrice de nombre premier, qui croit assez rapidement.

Pourquoi des nombres premiers ? (c'est une vraie question)

Citation:

Mon problème est que je n'arrive pas à trouver une technique pour les retrouver rapidement , de tel sorte que ,
J'ai un fonction trouverArbre(double numero) et elle me renvoie le pointeur sur l'arbre associé.

Il faudrait, qu'a chaque création d'arbre, je crée un pointeur qui lui est propre, associé au numéro.
Je ne peux pas utiliser de tableau car, ça userais énormément de place, étant donné que les case ne sont pas successive.

C'est tout le problème de la complexité algorithmique : si ta structure est optimisée en taille mais est implémentée avec une liste chaînée (avec plusieurs fils par nœud), il te faudra la parcourir pour la retrouver. Si c'est un tableau, l'espace consommé sera prohibitif mais tu accèdera à tes nœuds en temps constant. Ce qui est intéressant, c'est que cette complexité se calcule. Tu peux également trouver un compromis entre les deux, par exemple en conservant en cache les pointeurs vers les nœuds les plus utilisés et de là, retrouver tous les autres en un temps minimum. C'est d'ailleurs cette idée qui est à l'origine des hash tables qu'on utilise à un peu toutes les sauces désormais.

Citation:

De plus la recherche serait trop longue, j'ai pensé au vector en C++ mais ça gâcherait de même un place conséquente, encore plus que en C si je trier par ordre croissant.:roll:

C'est-à-dire que vector<>, ce n'est pas un objet magique ni même en soi une structure de données fondamentale : c'est une classe pré-écrite pour toi, qui rend les services qu'elle annonce en choisissant éventuellement la meilleure stratégie (je ne me souviens plus si vector<> elle même peut le faire où s'il faut utiliser quelque chose de plus sophistiqué). Donc, c'est quelque chose qui a été longuement pensé au niveau algorithmique en général mais qui n'est pas spécialement

En plus, c'est une classe très mal nommée car ce qu'elle manipule est tout sauf un vecteur : elle n'honore pas toutes les règles qui y seraient applicables, mais ajoute par contre des facilités certes bien pratiques mais qui ne correspondent à rien en théorie des vecteurs proprement dite, par exemple la possibilité d'insérer un nombre au milieu de la séquence. Du coup, en insérant par exemple un « 6 » en deuxième position, un vecteur type 3x+5y+4z pourrait devenir un 3w+6x+5y+4z, c'est-à-dire que les dimensions « muteraient » : l'ajout d'information impliquerait que les coefficients suivants se mettrait subitement à décrire autre chose.

Citation:

La seule technique que j'ai trouver, c'est avec l'écriture de fichier, j'assigne une lettre (entre a et j) à chaque chiffre de 0 à 9, et je réécrit dans un fichier exemple: tree aesjgh suivie d'un return aesjgh, mais après il faut que je fasse un système de macro qui recompile automatiquement .
Ca à l'air bien compliqué.:aie:

Rien de tout cela mais l'idée est là. Indice : tu dois pouvoir choisir la base de calcul correspond au nombre maximum de degrés de chaque nœud (si ce que tu veux faire est bien ce à quoi je pense).

Citation:

Donc si vous connaissais une technique plus simple je suis preneur, sinon si vous savez comment faire de la recompilation auto d'un fichier .c à partir d'un executable en C ça m'aiderais beaucoup aussi.

Merci d'avance!:)

Techniquement, il suffit d'appeler le compilateur puis de faire un exec() pour basculer vers le fichier généré, mais c'est à proscrire ! :aie:
11/12/2015, 20h16
Matt_Houston

Du coup je ne sais pas pour les autres mais là je suis incapable de conceptualiser ta structure de données, dont tu sembles pourtant avoir une idée très précise.

Si tu as toujours des questions concernant une potentielle implémentation en C, il faut que tu détailles tout cela avec pourquoi pas quelques schémas, nous ne sommes pas dans ta tête. ;)
11/12/2015, 20h55
marchrysostome

J'avais fais du scheme c'est vrai que c'est très plaisant mais la le projet est bien trop compliqué pour que je puisse user du fonctionnel, j'ai besoin d'avoir une grande marge de manoeuvre au niveau de l'adressage.

Sinon, pourquoi j'utilise des nombre premier ^^, tout simplement pour facilité les recherches, grace à la division par les nombres premiers !

voila ma structure :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 typedef struct Lignee{ double num; }lignee; typedef struct Data{ }data; typedef struct noeud * nod; //definition des noeuds typedef struct noeud { gene coordonnees; neurone data; nod pere; lignee * list; }Nod; typedef struct arbre * tree; typedef struct arbre{ lignee timeLine; nod Rooth; nod * fils; }Tree; typedef struct r_arbre * researchTree typedef struct r_arbre { researchTree Rtree[10]; lignee tree; }Rarbre;
Biensure elle n'est pas encore terminé

Donc en gros chaque noeud ont un gène qui lui est assigné, et un arbre possède comme numero le produit du gène de tout les noeud qu'il compose

11/12/2015, 23h51
Abacar94

Citation:

Envoyé par marchrysostome

J'avais fais du scheme c'est vrai que c'est très plaisant mais la le projet est bien trop compliqué pour que je puisse user du fonctionnel, j'ai besoin d'avoir une grande marge de manoeuvre au niveau de l'adressage.

Sinon, pourquoi j'utilise des nombre premier ^^, tout simplement pour facilité les recherches, grace à la division par les nombres premiers !

je sais pas si tu connais le dictionnaire de typeII, car selon mois c'est l'optimalité vu que pour chaque nœud on fait une liste des suivant immédiat et une autres des précédent immédiat sur un graphe

j'ai changé quelque truc dans ma structure pour faire le programme,
ça fait longtemps que je n'ai pas fais de C, alors si vous avez un conseil au niveau de allocation je suis preneur.
Voilà les changement au niveau de la structure et la fonction, pour ranger ces fameux arbres. :?

Code:

1
2
3
4
5
6
7
8
typedef struct r_arbre * researchTree
typedef struct r_arbre
{
	researchTree Rtree[10];
	tree linktree;
	lignee timeline;
 
}Rarbre;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* paramètre : arbre * lignée  * bool 
		but  : On désire faire pointer un arbre grace à sa ligné associé
				dans un arbre de recherche
	procédé	 : l'arbre de recherche contient pour noeud, chaque noeud crée
				pointe sur un tableau de 10 autres noeud.
				en lisant de gauche à droite chaque chiffre, successivement,
				du numéro de lignée, on prend le chemin du noeud correspondant
				au chiffre, jusqu'a atteindre le dernier noeud, associé au dernier 
				chiffre, on saisie alors la lignee dans la var correspondante
				et on fait pointé le "treelink" de ce noeud vers l'arbre.
	info sup  : - le bool sert à prendre en compte les 0, même si il se trouve à gauche
				- je verifie 2 fois si les pointeur sont nul, une première, au cas je l'ai
					déjà créer pour une lignée précédente, une seconde pour l'erreur */
void CreateResearchTree(tree arbre, lignee path, Bool zero){
	int i,a,b;
	int count=0;
	tree abre1= arbre;
 
	if(Retree== NULL){
		 Retree = (researchTree*)malloc(sizeof(researchTree));
	}
	if(Retree==NULL){
		printf("ERREUR fct::CreateResearchTree----> Retree\n");
		exit;
	}
 
	//on initialise l'arbre linktree
	if(Retree->linktree==NULL){
		CreateTree(Retree->linktree);
	}
	if(Retree->linktree==NULL){
		printf("ERREUR fct::CreateResearchTree----> linktree\n");
	}
 
	//on initialise le tableau de Rtree
	if(Retree->Rtree==NULL){
	Retree->Rtree= (researchTree*)malloc(sizeof(researchTree) *10);
	}
	if(Retree->Rtree==NULL){
		printf("ERREUR fct::CreateResearchTree----> Rtree[%d]\n",i);
			exit;
	}	
 
	while(num>=100){  //on veut isoler les deux premier chiffre de "timeline"
		num/=10;
		count++;
	}
	count++;
	if(zero = Vrai){ // on check si le dernier premier chiffre  était un zero 
		a=0;
	}
	else{
		a=num/10; // on garde le premier chiffre de "timeline" pour ne lancé la fonction que sur le noeud correspondant
	}
 
 
	if(count ==1){  // si il ne reste qu'un dernier chiffre
		Retree->timeline= path;
		Retree->linktree= arbre;
		return;
	}
	else{
		Retree->timeline=0;
	}
	if (num%10==0 ){
		b=CreateResearchTree(arbre, timeline, Vrai); //si le second  chiffre est zero, il ne sera pas pris en compte c'est un cas particulier
	}
	else{
		b=CreateResearchTree(arbre, timeline%(10^count), Faux); //on reffet la meme fonction avec "timeline" privee de son premier chiffre
	}
	Retree->(Rtree+a)->b;
	return;
}