Computer Tutorials: structure de données

Affichage des articles dont le libellé est structure de données. Afficher tous les articles

jeudi 11 septembre 2014

Réalisation d'un programme de gestion d'un dictionnaire

Posted on septembre 11, 2014 by ghizlan

Introduction :

L’élaboration d’un dictionnaire se basant sur l’alphabet français peut se faire de différentes manières à savoir les tableaux simples, les tables associatives (Hash-code), les listes chaînées et les arbres. La dernière solution qui se base sur les arbres présente la meilleure en terme d’optimisation de l’espace mémoire et de la rapidité de recherche et d’intervention et ceux dus à la notion de récursivité utilisée largement dans ce genre de manipulation.

Travail demandé :

Dans ce présent travail, on demande d’écrire un programme contenant un menu pour gérer un dictionnaire contenant des mots de la langue française qui seront présentés par ordre alphabétique fournissant pour chacun une définition. Pour se faire, nous disposons d’un menu comportant des fonctions pour créer un dictionnaire, pour y ajouter des mots , pour en supprimer, pour afficher tous les éléments, pour rechercher et enfin pour fermer et quitter le fichier.

Architecture utilisée :

On a opté pour l’utilisation des arbres, suivant l’architecture ci-dessus :

S_noeud *droite, *gauche: deux pointeurs pour la navigation dans l’arbre.

Char *info : pointe sur un espace dynamique pour recevoir le mot en question.

Char *def : pointe sur un espace dynamique pour recevoir la définition associée.

Les différentes étapes d’élaboration du menu sont expliquées ci-dessous:

1. Étapes de réalisation:

Pour élaborer ce mini projet, plusieurs étapes ont été suivies:

L’ajout d’un mot au dictionnaire.
La recherche d’un mot dans le dictionnaire.
La suppression d’un mot du dictionnaire.
La fermeture du dictionnaire.

Pour ce faire, un menu a été établi. Ce menu comporte toutes les fonctionnalités citées. Toutes ces fonctions sont décrites en détails dans les paragraphes qui suivent.

1.1. Élaboration du menu:

Le menu général de notre programme se présente comme suit:

1- Ajouter un mot au dictionnaire.

2- Rechercher un mot dans le dictionnaire.

3- Supprimer un mot du dictionnaire.

4- Fermer le dictionnaire.

Donc un ensemble de fonction a été élaboré afin d’exécuter le menu ci-dessus tout en utilisant les arbres sous c afin d’optimiser l’espace mémoire et en s’appuyant sur la notion de récursivité.

1.2. Les fonctions principales du programme:

A- Fonction exprimant l’ajout d’un mot au dictionnaire :

Pour ajouter un élément au dictionnaire, on a recours à une fonction qui ne retourne rien et qui prend comme paramètre un pointeur de pointeur de type t_noeud. Le prototype de la fonction qui permet l’ajout est arbre * create(char nb[],arbre * prim,char d[]). Dans la fonction create, On fait entrer le mot à insérer et on teste s’il existe déjà ou pas. Si l’élément existe, le mot ne sera pas accepté, sinon il sera ajouté avec succès.

B- Fonction vérifiant la recherche d’un mot dans le dictionnaire :

La fonction Exist qui nous permettra de chercher un mot dans le dictionnaire, elle retourne void et reçoit comme paramètre un pointeur nœud de type t_noeud. Le prototype de cette fonction est void Exist(arbre *src ,char elt[]).

C- Pour supprimer un élément du dictionnaire :

Dès que l’utilisateur désire supprimer un élément du dictionnaire, on fait appel à la fonction Supprimer dont le prototype est : void Supprimer(arbre**src, char *chaine). Cette fonction permet de vérifier si le mot entré existe dans le dictionnaire. Si c’est le cas elle permet de bien supprimer l’élément.

On trouve aussi la fonction Suppression dont le prototype est : void Suppression(arbre **src) qui permet de libérer le nœud à supprimer ainsi que sa définition.

2. Algorithmes:

typedef struct tree{

char mot[10];

char def[1000];

struct tree *droite;

struct tree *gauche;

}arbre;

ajouter (&R, mot[30])

i=0;

D=R;

ptr prec, temp;

Tantque (i<m.lenght())

D=D->bas;

prec=Null;

Tant que (D!=Null) et ((D->lettre)<mot[i])

prec=D;

D=D->suivant;

fin tantque

si ((D->lettre)=mot[i]) alors D=D->bas;

i=i+1;

sinon

temp=(ptr) malloc(size of(noeud));

temp->lettre=mot[i];

si (prec=!=Null) alors

prec->suivant=temp;

temp->suivant=D;

sinon

si (D=Null)

D->bas=temp;

temp->haut=D;

temp->suivant=Null;

sinon

temp->suivant=D;

D->haut=Null;

finsi

fintantque

si i>=mot.lenght() alors D->bas=definition;

---------------------------------------------------------------------------------------------------------------------

rechercher(&R, mot[30])

D=R;

tantque (D->bas!=Null) et (i=<mot.lenght())

tantque (D!=Null) et (mot[i]>D->lettre)

D=D->suivant;

fintantque

si mot[i]=D->lettre alors

D=D->bas;

i=i+1;

sinon return -1;

fintantque

si ( i=mot.lenght()) et (D->definition!=Null) alors

return D->definition;

sinon return -1

finsi

---------------------------------------------------------------------------------------------------------------------

supprimer(&R, mot[30])

D=recherche(&R, mot[30])

si (D!=Null)

alors

si D->bas!=Null

alors D->definition=Null;

sinon tantque ((D->haut->definition)!=Null) et ((D->haut->suivant)!=Null)

free(D);

3. Ecrans de saisie:

Menu principal:

Ajout d’un mot:

Recherche d’un mot:

Suppression d’un mot:

Quitter le programme :

Conclusion :

L’élaboration de ce programme permet d’étudier profondément les arbres comme structure et outil puissant dans la gestion de grandes tables de données. L’introduction de la gestion dynamique de la mémoire nous a permis de gérer d’une façon optimale l’occupation de la mémoire et mettre en évidence la force des pointeurs.

Pour télécharger le code source du programme

Réalisation d'un éditeur de texte en utilisant les listes chaînées

Posted on juillet 27, 2014 by ghizlan

I- Le cadre général :

a. But du Mini-projet:

Ce projet consiste à concevoir un éditeur de texte contenant les fonctionnalités de base communes à tous les éditeur en utilisant les listes chaînées.

b. Présentation du sujet :

Un éditeur de texte est un logiciel destiné à la création et l'édition de fichiers textes. Chaque système d'exploitation fournit un éditeur, tant son usage est courant, voire incontournable pour certaines tâches (souvent informatiques (administration de système et développement logiciel)).

Les éditeurs de texte se divisent en deux catégories:

· Les éditeurs plein écran (ou full-screen),

· Les éditeurs en mode caractère.

Un éditeur plein écran n'interagit avec l'unité centrale que lorsqu'elle est pressée une touche comme Entrée ou l'une des touches de fonction (Fn) ou d'action (PAn) du terminal. Le reste du temps, ce sont les capacités d'insertion native fournies par l'unité de contrôle du terminal qui permettent l'ajout, la suppression ou l'insertion de caractères dans toutes les lignes affichées sur l'écran.

c. Quelques opérations de base :

Les fonctionnalités les plus élémentaires d'un éditeur sont:

- Ouvrir un fichier (en proposant parfois une liste de fichiers récemment ouverts, ou déjà existants, voire en permettant de restreindre cette liste par un filtre)

- Ajouter du texte dans une ligne, ou des lignes dans un fichier

- Ôter des caractères dans une ligne, ou des lignes d'un fichier

- Rechercher/remplacer une chaîne texte (la recherche n'est pas toujours disponible).

- Sauvegarder le fichier, ou au contraire sortir en renonçant aux modifications (en cas de grosse erreur comme un effacement involontaire de texte).

d. Analyse générale :

Editer un texte semble très intuitif à toute personne sachant utiliser un ordinateur et un éditeur. Du point de vue d’un programmeur, il faut penser à toutes les fonctionnalités que doit proposer un tel programme. De l’ouverture d’un fichier à sa sauvegarde, en passant par les différentes opérations possibles sur le texte et l’annulation de celles-ci. Toutes ces fonctionnalités s’appliquent à des données.

Les fonctionnalités de l'éditeur à réaliser :

Parmi celles-ci certaines sont « indispensables » au bon fonctionnement de l'éditeur et au respect du cahier des charges. En voici une synthèse :

· Ouvrir ou créer un fichier ;

· Sauvegarde du fichier sous ;

· Sauvegarde du fichier si le fichier existe déjà ;

· Insertion du texte à la position courante ;

· Suppression du texte à la position courante ;

· Ajouter du texte après la ligne courante ;

· Donner la position du curseur ;

· Faire la recherche ;

· Et d’autres fonctionnalités….

Un éditeur de texte porte bien son nom : son rôle est en effet d’éditer du texte… La donnée fondamentale est donc un texte. Texte qui peut provenir d’un fichier chargé en mémoire, ou qui peut également être créé de « toute pièce » dans l’éditeur.

Afin que cet éditeur puisse servir de manière effective,il faut disposer de données persistantes qui permettent de stocker de manière définitive ce texte (dans un fichier). Lors de son chargement en mémoire, le texte est placé ligne par ligne dans une liste chaînée et devient une donnée résidente jusqu’à un nouvel enregistrement.

En dehors du texte, des données relatives aux opérations que l’on veut effectuer sont indispensables : les coordonnées x et y de la position courante par exemple. Nombre de lignes et nombre de caractères dans la ligne courante sont également des données q'on aura besoin d’extraire du texte.

Un dernier type de données est utilisé, il s’agit de la liste des commandes acceptées et reconnues par l’interpréteur de commande. Ces données sont réunies dans une liste les faisant correspondre aux fonctions voulues. On traite ces données en les comparants à une saisie de l’utilisateur.

II- Architecture de l'application :

Lors du lancement du programme, on obtient la fenêtre suivante qui demande soit d’ouvrir un fichier existant soit la création d’un nouveau fichier. Cette opération aboutira à la création d’une liste doublement chaînée contenant le texte en cours d’édition, chaque ligne étant rattachée à celle la précédant et à celle la suivant.

Une fois cette opération effectuée, Une fenêtre de saisie s’ouvre, permettant de d’éditer le texte avec toutes les fonctionnalités habituelles de déplacement du curseur ou des lignes, de la saisie du texte ou encore sa suppression.

Lorsqu’on clique sur ECHAP, un prompt « EDITEUR> » s’affiche nous permettant de saisir la fonctionnalité qu’on veut effectuer. La plus simple étant « help » ; l’aide nous permet de consulter les différentes commandes relatives à chaque fonctionnalité disponible sur notre éditeur.

Ainsi, l’utilisateur peut saisir les commandes qu’il désire suivies éventuellement de leurs paramètres. Ces commandes appelleront les fonctions voulues afin qu’elles s’exécutent et laissent à nouveau la place à l’interpréteur de commande, déjà prêt pour la commande suivante.

Les fonctions réalisant des opérations sur le texte reçoivent toutes un pointeur sur la liste doublement chaînée. Elles peuvent être appelées les unes à la suite des autres.

En fin d’édition, il pourra être utile de sauvegarder les modifications du texte dans un fichier.

GESTION DE LA MEMOIRE EN FILE

Posted on juin 23, 2014 by ghizlan

1. Le cadre général :

Une file est une structure de données dynamique dans laquelle on insère des nouveaux éléments à la fin (queue) et où on enlève des éléments au début (tête de file).

On parle d’un mode d’accès : FIFO (First In First Out).

L'objectif de ce TP est d'écrire un programme qui permet la gestion d’une file de valeurs entières et de longueur 8.

2. Les différentes fonctions :

**a. la fonction CREFILE() :**

Cette fonction permet de créer une file vide dans un tableau nommé file[ ] et de dimension DMAX déclaré au niveau de la fonction principale. CREFILE() quant à elle, initialise AR et AE deux variables, respectivement, pour la réception et l’émission des nombres au sein de la file.

Puisque les variables locales perdent leurs valeurs une fois la fonction termine son exécution; on a vu utile de mettre les variables AR et AE dans 2 tableaux de dimension 1, afin qu’on puisse conserver leurs valeurs.

**b. la fonction FILEVIDE() :**

Cette fonction retourne une valeur logique vraie ou fausse selon que la file est vide ou non. Tout en se référant à un compteur (cpt) qui compte le nombre d’éléments constituants la file en fonction de l’ajout et la suppression.

**c. la fonction FILEPLEINE() :**

Cette fonction fournit une valeur logique vraie ou fausse selon que la file est pleine ou non (en vérifiant la valeur de cpt).

**d. la fonction AJOUTER() :**

La fonction AJOUTER() permet, après vérification de la file si elle est pleine, d’ajouter une valeur entière dans la file. Cet ajout est toujours accompagné par une incrémentation de la valeur de AR.

**e. la fonction SUPPRIMER() :**

Cette fonction permet, en se référant à la valeur de cpt et en vérifiant ainsi si la file est vide, de supprimer l’élément en tête de la file et d’afficher sa valeur.