[Besoin d'aide]Projet en langage C : pointeurs et allocation mémoire
Hors ligneReveur-ml Le 06/11/2005 à 19:20 Profil de Reveur-ml Configuration de Reveur-ml

Bonjour à toutes et à tous,

Si je viens vers vous ce soir, c'est pour demander humblement de l'aide.

En effet, voilà 1 semaine que je planche sur un projet en C...et malgré tous mes efforts je n'avance que très lentement.

La date limite approche, il me reste moins d'une semaine pour terminer mon travail, et je suis très loin du but.


Ce que j'attends de vous?

Pas que vous me pondiez un code que je pourrais copier / coller, mais uniquement des conseils, des explications, des pistes. Vous pouvez même ne pas taper une seule ligne de C dans vos réponses, et vous contenter de me guider un peu, cela me sera déjà énormément utile (vraiment).

Pourquoi je n'y arrive pas seul?

Petit résumé de ma situation: je suis actuellement à "cheval" entre la 2e et la 3e année de mon Ecole, il ne me manque que 2 crédits (sur 60) de 2A pour valider mon année, sans quoi je resterai bloqué l'année prochaine et ne pourrai pas passer en 4A.

Ces 2 crédits, je ne peux les obtenir qu'avec ce projet; mais cela fait 2 ans que je n'ai pas touché au C et même en reprenant assidument mes anciens cours, cela me prend énormément de temps pour me remettre à niveau.

Qui plus est, ce projet est censé être fait en binôme, mais étant le seul 3A de ce cours, je me retrouve seul, les autres ses connaissant et ayant déjà formé leurs binômes...ce qui n'arrange vraiment pas ma situation.


Je vais maintenant vous montrer le sujet et ce que j'ai déjà codé.

Le thème est le suivant: vous connaissez ces fameuses machines qui coupent les documents "ultra confidentiels" en fines bandelettes? Dans ce projet, on nous donne ces bandelettes (sous forme d'images) et le but est d'essayer de trouver laquelle va à côté de laquelle, pour reconstituer le document original.

Au début de ce projet, on nous donne des fichiers texte contenant les valeurs des pixels des bords gauche et droit de chaque bandelette; il "suffit" alors de voir quels sont les bords ayant le plus de similitudes pour reconstituer le document.

C'est facile sur le papier, mais concrètement...enfin je vous laisse lire la suite.

(Si vous êtes encore là à me lire, après mon discours d'intro, j'ai de la chance :p)

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

Contexte



On cherche à reconstituer un document détruit par un destructeur de documents. Il faut retrouver l'ordre des images des bandes de papier pour créer l'image du document original. Ce problème est complexe à double titre:

-Le nombre de configurations possible est factorielle le nombre de bandelettes. Ainsi le nombre d'arrangements possible pour 20 bandelettes est 20! = 2.43290200817664e+18 ce qui est déjà considérable.

-Il s'agit ici de documents "scannés" donc des images et non les vrais documents informatiques. Même si on est capable de recréer tous les documents possibles, reconnaître celui qui est identique au document original est en soi un problème complexe.

Nous essayerons de trouver des solutions approchées, pour le moment ce projet consiste à charger en mémoire des données représentant des bandelettes, c'est ces données que nous utiliserons dans nos algorithmes de reconstruction.

Les données sont les images des bandelettes, une image est composée d'une matrice de pixels (abréviation de picture element"), chaque pixel a une valeur entre 0 et 255 (0 pour le noir, 255 pour le blanc, et un dégradé de gris entre les deux).

Pour reconstituer le document nous allons simplement agencer les bandelettes, les unes à côté des autres en essayant de satisfaire au mieux une contrainte de continuité sur els bords, pour cela nous n'avons besoin que de la liste des valeurs des pixels sur les bords droit et gauche de chacune des images.

Ce travail a été fait pour vous (pour vous éviter d'avoir à gérer les notions d'image). Les données que vous manipulerez sont déjà extraites dans des fichiers. Il s'agit de suites de nombres qui sont les valeurs des pixels des bords des bandelettes.

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

Le programme

Voici le format des fichiers représentant nos données:

slice length 1710

252 252

252 252

252 246

237 252

252 250

244 234

...

(il y a 1710 lignes dans cet exemple)



La première ligne donne l'information du nombre de données, les lignes suivantes sont les valeurs des pixels des bords gauche et droit.

Nous allons écrire un programme qui lit le contenu de tels fichiers et qui les met en mémoire dans la structure de données suivante:


typedef struct

{

     int size;

     unsigned char *data;

} vector;



Ceci permet de définir un nouveau type de "vector" permettant de regrouper sous un même nom de variable:

-un pointeur sur les valeurs des pixels du bord des bandelettes

-et le nombre d'éléments pointés.


typedef struct

{

     char id[1024];

     vector *left;

     vector *right;

} shred;



Ceci définit un nouveau type "shred" qui permet de regrouper sous un même nom de variable ce dont nous avons besoin pour représenter une bandelette:

-un identifiant de bandelette (c'est tout simplement le nom de fichier dans lequel on a lu les valeurs).

-2 pointeurs sur des "vector" qui contiennent les données des bords gauche et droit de la bandelette.



Ecrivez les fonctions d'allocation et désallocation mémoire du type vector avec les prototypes suivants:

vector *vectorAllocate (int size);

void vectorDestroy(vector *v);

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

Etapes à suivre:



1-écrivez la fonction d'allocation et écrivez un appel de cette fonction dans le main.

2-mettez y juste quelques données que vous écrirez directement dans le code.

3- affichez ces données.

4-puis appelez la fonction de désallocation.


Avec la même méthodologie vous écrirez les fonctions d'allocation et désallocation du type shred avec les prototypes suivants:

shred* shredAllocate(int leftSize, int rightSize);

void shredDestroy *s);


Jusqu'ici, tout va bien, j'ai réussi (en une semaine) à tout coder.

Voici ce que j'ai pour l'instant codé, cela se compile bien, je ne pense pas qu'il y aie de fautes.

Chaque fonction étant bien détaillée dans l'énoncé, je ne pense pas avoir à mettre de commentaires dans le code.

Si celui-ci est obscur, n'hésitez pas à me demander et j'ajouterai tous les commentaires nécessaires.

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



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

typedef struct
{
     int size;
     unsigned char *data;
} vector;

typedef struct
{
     char id[1024];
     vector *left;
     vector *right;
} shred;

vector *vectorAllocate (int size)
{
     vector *ptr = (vector*) malloc(sizeof(vector));
     ptr->size=size;
     ptr->data = (unsigned char*) malloc(ptr->size * sizeof(unsigned char));
     return(ptr);
}
void vectorDestroy(vector *v)
{
     free(v->data);
     free(v);
}

shred* shredAllocate(int leftSize, int rightSize)
{
     shred *ptr = (shred*) malloc(sizeof(shred));
     ptr->left = vectorAllocate(leftSize);
     ptr->right = vectorAllocate(rightSize);
     return(ptr);
}
void shredDestroy(shred *s)
{
     free(s->left);
     free(s->right);
}
int main()
{
     vector *tmp;
     shred *tmp2;

     tmp=vectorAllocate(1710);
     tmp->data[2]=250;
     tmp->data[1709]=10;

     printf("\n %d , %d \n",tmp->data[2], tmp->data[1709]);
     tmp2 = shredAllocate(1710,1710);
     tmp2->left->data[0]=1;
     tmp2->left->data[1]=2;
     printf("\n %d , %d \n",tmp2->left->data[0], tmp2->left->data[1]);

     vectorDestroy(tmp);

     shredDestroy(tmp2);

     return 0;
 }


-----------------------------------------------------------------------
Maintenant on passe à la phase suivante...

Et sincèrement , ce n'est pas juste difficile pour moi, c'est tout bonnement incompréhensible.

Un exemple tout bête: dans ce qui va suivre, le prof parler du type "FILE", mais qu'est-ce que c'est?

Quelque chose d'inclus dans les librairies, quelque chhose que je dois définir moi même?

Un autre: il ne précise pas combien de fonctions je dois coder en tout; tout cela est-il une seule grosse foction? Chaque point abordé est il une fonction? Je n'en ai aucune idée.

Je bloque complètement...des explications, des conseils, je vous en prie, me seraient Extrêmement utiles.

Voici donc la suite du projet (à noter que ce n'est loin d'être la fin...mais je préfère déjà me concentrer sur cette partie, plutôt que de m'étaler sur tout en même temps).

-----------------------------------------------------------------------
Vous allez écrire la fonction de lecture de données dans le fichier avec le prototype suivant:

shred* loadShred(char *fileName);

Cette fonction a comme unique paramètre le nom du fichier à charger, et retourne un pointeur sur la structure de données qu'il aura alloué (en appelant les fonctions précédemment définies) et rempli.

Pour pouvoir lire dans un fichier il faut l'ouvrir, lire les données puis le fermer, cela se fait grâce aux fonctions fopen, fgets, fclose de la librairie stdio (standart input output). La fonction fopen prend en paramètre le nom de fichier à ouvrir et ce que l'on veut en faire: lire ("r"ead) ou écrire ("w"rite). Elle retourne une valeur de type FILE c'est le descripteur de fichier qui idetifie le fichier que l'on est en train de manipuler. L'appel à cette fonction devrait donc ressembler à ça:


FILE *file;

file = fopen(fileName, "r");

Vous testerez que la variable file est différente de NULL pour vous assurer d'une bonne ouverture du fichier. Vous pouvez alors lire le contenu du fichier ligne à ligne grâce ç la fonction fgets dot le prototype est le suivant:

char * fgets(char * s, int size, FILE * steam);


Les paramètres sont, dans l'ordre: la chaîne de caractères qui contiendra ce qui est lu dans le fichier (c'est à vous de donner un pointeur vers une zone de mémoire allouée), le nombre d'éléments alloués pour la chaine de caractères, et enfin le descripteur de fichier sur lequel on veut effectuer la lecture.


La fonction fgets retourne NULL quand elle arrive en fin de fichier ainsi le code suivant permet d'afficher le contenu d'un fichier.


while(fgets(buffer, 1024, file))

     printf("%s\n", buffer);

Où buffer est un tableau de char de 1024 éléments.

Pour en finir avec le fichier il faut le fermer cela se fait avec la fonction fclose que l'on applique sur le descripteur de fichier. Le nombre de fichiers ouverts en même temps est limité, il faut donc toujours bien penser à fermer les fichiers une fois qu'on a fini de s'en servir.

fclose(file);

Il vous faut maintenant manipuler ce buffer pour en extraire les informations voulues car les chiffres qu'il contient ne sont pas directement utilisables; en effet il ne s'agit pas de nombre mais d'une chaine de caractères représentant ce nombre. Une fonction de la "stdlib" nous permet de faire cette traduction:

int atoi(const char *nptr); // Ascii TO Integer

Elle prend en paramètre un pointeur sur le début de l'endroit où est écrit le nombre et retourne l'entier correspondant (le const signifie que cette fonction ne modifiera pas le contenu des valeurs pointées).

Pour finir, vous écrirez une fonction d'affichage:

void printShred(shred *s);

que vous appellerez dans le main pour finir de tester votre fonction loadShred en affichant les données chargées.

Conclusion:

A la fin de la séance, vous devriez avoir écrit un programme qui lit un fichier texte de description de bord de bandelette, alloue la mémoire nécessaire, met les données en mémoire, affiche les valeurs lues, puis désalloue la mémoire. Tout ceci sans erreur ni fuite mémoire.



Lors de la prochaine séance, nous fabriquerons une liste chaînée pour charger en mémoire plusieurs bandelettes, nous pourrons alors faire des comparaisons et commencer la reconstruction du document détruit.

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

Même si je saisis dans l'ensemble l'algorithme de cette partie du code, si quelqu'un pouvait se dévouer pour me le réexpliquer plus en détails, ne serait-ce que ça, m'aiderait Beaucoup.

Je vous remercie d'avance pour votre soutien (et j'en ai besoin).

Si certains points ne sont pas clairs, n'hésitez pas à me poser des questions, j'y répondrai au plus vite.

Sur ce, je vous remercie déjà d'avoir lu jusqu'ici mon message, mais aussi d'avance pour vos réponses.

Bonne soirée et bonne continuation.

Un élève en école d'inge, honteusement faible en C.
Hors ligneAralicia Le 26/06/2007 à 17:35 Profil de Aralicia Configuration de Aralicia

Bonjour.

Voici ma reponse aux deux questions faite dans tout ton message :

1) le type FILE

Le type file est utilisee par les fonctions fopen, fgets, fread, fscanf, fprintf, fclose... pour gerer la lecture/ecriture de fichiers. il correspond + ou - a un descrip\
teur vers le fichier. Pour Unix/Linux/Alpha/Solaris (et probablement Windows), il est inclus dans stdio.h

2) le nombre de fonctions

Il est variable selon la facon de coder que tu veux utiliser. Dans le case present, je te conseille de proceder de la maniere suivante :
I : Lecture totale du fichier
On utilise fopen pour ouvrir le fichier, puis, par des appels repetes a fgets on lit l'integrite du fichier en reallouant a chaque appel la taille de la chaine finalle. \
On ferme le fichier avec fclose, puis on retourne le pointeur vers la chaine de caractere finale (format char*).
II : Decoupage du fichier.
A partir de la chaine precedement recue, on le decoupe en un tableau de lignes (format char** - vive le char "\n"). la chaine de caractere precedente ne sera plus utilis\
ee, on peut donc liberer sa memoire.
III : Analyse du fichier.
On alloue un Shred de la bonne taille (grace a la premiere ligne du tableau - rappel : l'index d'un tableau commence a 0!),
puis on le remplit case par case (== ligne par ligne - penser a ignorer la deuxieme). Une fois le Shred remplis, on peut liberer la memoire du tableau.
IV : Affichage des resultats.
A partir du Shred, on affiche les resultat. la facon de le faire est a ta discretion.
V : Vidage de la memoire.
On desalloue le Shred.

Chaque partie peut constituer une fonction, les fonctions de la parties I, II et III constituant loadShred.


Voici le main, la fonction loadShred et la fonction unloadShred, mais pas leurs sous-fonctions (faut que tu bosse, quand meme ;))                                        
J'ai suppose que l'adresse du fichier bandellette etait passee en paramettre, mais je n'ai pas verifie que celui ci existait (risque de SIGSEGV)

******************************

int main(int argc, char **argv)
{
  shred *s;                                                                                                                                                              

  s = loadShred(argv[1]); /*Etapes I, II et III*/                                                                                                                        
  printShred(s); /* Etape IV */                                                                                                                                          
  UnloadShred(s); /* Etape V */                                                                                                                                          
}

shred *loadShred(char *path)
{
  char *str;                                                                                                                                                              
  char **tab;                                                                                                                                                            
  shred *s;                                                                                                                                                              

  str = getFile(path); /* Etape I */                                                                                                                                      
  tab = strToTab(str); /* Etape II */                                                                                                                                    
  s = tabToShred(tab); /* Etape III */                                                                                                                                    
  return (s);                                                                                                                                                            
}

void UnloadShred(shred *s)
{
  vectorDestroy(s->left);                                                                                                                                                
  vectorDestroy(s->right);                                                                                                                                                
  shredDestroy(s);                                                                                                                                                        
}

******************************

Et voila ! Juste par curiosité, dans quelle école es-tu ?

Bonne journée.
Vous avez résolu votre problème avec VIC ? Faites-le savoir sur les réseaux sociaux !
Vulgarisation-informatique.com
Cours en informatique & tutoriels