Arbre n-aire GNode

Version imprimable

Arbre n-aire GNode

Bonjour je fais une nouvelle fois appel à vous les zéros
J'ai dans l'idée de représenter les processus sous unix sous la forme d'un arbre n-aire mais je n'arrive pas à trouver l'algorithme de construction de cet arbre
Je dois lire les infos dans un fichier

Voici un exemple de ce fichier :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
UID        PID  PPID  C STIME TTY          TIME CMD
root         1     0  0 Feb07 ?        00:00:02 /sbin/init
root         2     0  0 Feb07 ?        00:00:00 [kthreadd]
root       381     1  0 Feb07 ?        00:00:00 upstart-udev-bridge --daemon
root       384     1  0 Feb07 ?        00:00:00 udevd --daemon
root       557   384  0 Feb07 ?        00:00:00 udevd --daemon
root       558   384  0 Feb07 ?        00:00:00 udevd --daemon
daemon     697     1  0 Feb07 ?        00:00:00 portmap
statd      746     1  0 Feb07 ?        00:00:00 rpc.statd -L
syslog     832     1  0 Feb07 ?        00:00:00 rsyslogd -c4
102        850     1  0 Feb07 ?        00:00:00 dbus-daemon --system --fork
root       855     1  0 Feb07 ?        00:00:00 gdm-binary
root       963   855  0 Feb07 ?        00:00:00 /usr/lib/gdm/gdm-simple-slave --display-id /org/gnome/DisplayManager/Display1
root      1006   963  0 Feb07 tty7     00:00:11 /usr/bin/X :0 -br -verbose -auth /var/run/gdm/auth-for-gdm-hAKrcA/database -nolisten tcp vt7
gdm       1195   963  0 Feb07 ?        00:00:00 /usr/bin/gnome-session --autostart=/usr/share/gdm/autostart/LoginWindow/
gdm       1237  1195  0 Feb07 ?        00:00:01 metacity
gdm       1238  1195  0 Feb07 ?        00:00:08 /usr/lib/gdm/gdm-simple-greeter
gdm       1239  1195  0 Feb07 ?        00:00:02 gnome-power-manager
root      1241   963  0 Feb07 ?        00:00:00 /usr/lib/gdm/gdm-session-worker
avahi      861     1  0 Feb07 ?        00:00:05 avahi-daemon: running [serveursoft.local]
avahi      863   861  0 Feb07 ?        00:00:00 avahi-daemon: chroot helper
root       865     1  0 Feb07 ?        00:00:00 /usr/sbin/console-kit-daemon --no-daemon

je n'arrive juste pas à trouver l'algorithme de construction
je dois aussi utiliser GNode de la glib
j'ai aussi creer une structure pour représenter les processus

Code:

1
2
3
4
5
6
7
8
 
typedef struct processus processus;
struct processus{
	int num;
	int numPere;
	char *proprietaire;
	char *nomCommande;
};

si vous pouviez me donner un pseudo code ce serait super , je n'aime pas qu'on me donne le code directement
Merci de vos réponses

26/03/2011, 20h20
pvincent

Bonjour,
Tout arbre n-aire étant réductible en un arbre binaire, j'aurai plutôt tendance à fabriquer un arbre binaire: il suffit de créer une structure dans laquelle on a deux liens: un vers le premier fils et un autre vers le frère plus jeune (si il existe).
Pour la remplir, il suffit de regarder quels sont tous les fils d'un père donné: on rajoute les fils les uns après les autres.
28/03/2011, 11h58
liberforce

Citation:

Envoyé par pvincent

Bonjour,
Tout arbre n-aire étant réductible en un arbre binaire, j'aurai plutôt tendance à fabriquer un arbre binaire: il suffit de créer une structure dans laquelle on a deux liens: un vers le premier fils et un autre vers le frère plus jeune (si il existe).
Pour la remplir, il suffit de regarder quels sont tous les fils d'un père donné: on rajoute les fils les uns après les autres.

Un processus peut avoir plusieurs processus enfants. Quel est donc l'intérêt de se rapporter à un arbre binaire quand le problème posé a pour représentation exacte un arbre n-aire ?
28/03/2011, 15h28
pvincent

J'aime bien les arbres binaires parceque la structure associée à un noeud est fixe et quand il est utile d'équilibrer l'arbre (ce qui n'est pas le cas ici je pense), c'est le bon choix. Aussi, avec ce type d'arbre il est facile de se passer d'une bibliothèque.

Evidemment on peut aussi s'en remettre à la GLib pour gérer des noeuds n-aires et alouer/libérer quand c'est utile et rajouter tous les fils d'un père donné pour définir ou modifier un noeud.