typedef int element;
typedef struct cellule {
- element valeur;
- struct cellule *suivant;
+ element valeur;
+ struct cellule *suivant;
} Cellule, *Liste;
-
-
Liste ajouter_iter(element e, Liste L)
{
- Cellule *pc, *p1=L, *p2=NULL;
-
- pc = (Cellule *)malloc(sizeof(Cellule));
- pc->valeur=e;pc->suivant=NULL;
-
- if (!L) /* liste vide */ return pc;
- while (p1 && (e >= p1->valeur))
- {
- p2 = p1;
- p1 = p1->suivant;
- }
-
- if (!p2) /* insertion en tete */ {pc->suivant = L; L=pc; }
- else {/* insertion entre p2 et p1 */
- p2->suivant = pc;
- pc->suivant = p1;
- }
-
- return L;
+ Cellule *pc, *p1 = L, *p2 = NULL;
+
+ pc = (Cellule *) malloc(sizeof(Cellule));
+ pc->valeur = e;
+ pc->suivant = NULL;
+
+ if (!L) /* liste vide */
+ return pc;
+ while (p1 && (e >= p1->valeur)) {
+ p2 = p1;
+ p1 = p1->suivant;
+ }
+
+ if (!p2) { /* insertion en tete */
+ pc->suivant = L;
+ L = pc;
+ } else { /* insertion entre p2 et p1 */
+ p2->suivant = pc;
+ pc->suivant = p1;
+ }
+
+ return L;
}
-
int longueur_iter(Liste L)
{
- int res = 0;
- while(L)
- {
- res = res + 1;
- L=L->suivant;
- }
- return res;
+ int res = 0;
+ while (L) {
+ res = res + 1;
+ L = L->suivant;
+ }
+ return res;
}
-
int longueur_rec(Liste L)
{
- if(!L) return 0;
- return 1+longueur_rec(L->suivant);
+ if (!L)
+ return 0;
+ return 1 + longueur_rec(L->suivant);
}
-
void visualiser_iter(Liste L)
{
- while (L)
- {
- printf("%d ",L->valeur);
- L = L->suivant;
- }
- printf("\n");
+ while (L) {
+ printf("%d ", L->valeur);
+ L = L->suivant;
+ }
+ printf("\n");
}
-
void visualiser_aux(Liste L)
{
- if(L)
- {
- printf("%d ",L->valeur);
- visualiser_aux(L->suivant);
- }
+ if (L) {
+ printf("%d ", L->valeur);
+ visualiser_aux(L->suivant);
+ }
}
-
void visualiser_rec(Liste L)
{
- visualiser_aux(L);
- printf("\n");
+ visualiser_aux(L);
+ printf("\n");
}
-
int rechercher_iter(element e, Liste L)
{
- while(L)
- {
- if(e == L->valeur) return 1;
- L = L->suivant;
- }
- return 0;
+ while (L) {
+ if (e == L->valeur)
+ return 1;
+ L = L->suivant;
+ }
+ return 0;
}
-
int rechercher_rec(element e, Liste L)
{
- if(L == NULL) return 0;
- if(e==L->valeur) return 1;
- return rechercher_rec(e,L->suivant);
+ if (L == NULL)
+ return 0;
+ if (e == L->valeur)
+ return 1;
+ return rechercher_rec(e, L->suivant);
}
-
Liste rechercher_rec2(element e, Liste L)
{
- if(!L || e==L->valeur) return L;
- else return rechercher_rec2(e,L->suivant);
+ if (!L || e == L->valeur)
+ return L;
+ else
+ return rechercher_rec2(e, L->suivant);
}
-
Liste ajouter_rec(element e, Liste L)
-{
- if(!L)
- {
- L=(Cellule *)malloc(sizeof(Cellule)); /* liste vide */
- L->valeur=e;L->suivant=NULL;
- }
- else if(e < L->valeur) /* ajouter DEVANT la tete */
- {
- Cellule *p=(Cellule *)malloc(sizeof(Cellule));
- p->valeur=e; p->suivant=L;
- L=p; /* nouvelle tete de liste */
- }
- else L->suivant=ajouter_rec(e,L->suivant); /* ajouter DERRIERE la tete */
- return L;
+{
+ if (!L) {
+ L = (Cellule *) malloc(sizeof(Cellule)); /* liste vide */
+ L->valeur = e;
+ L->suivant = NULL;
+ } else if (e < L->valeur) { /* ajouter DEVANT la tete */
+ Cellule *p = (Cellule *) malloc(sizeof(Cellule));
+ p->valeur = e;
+ p->suivant = L;
+ L = p; /* nouvelle tete de liste */
+ } else
+ L->suivant = ajouter_rec(e, L->suivant); /* ajouter DERRIERE la tete */
+ return L;
}
-
Liste supprimer_iter(element e, Liste L)
{
- Liste prec = NULL;
- while(L)
- {
- if(e == L->valeur) {
- prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */
- free(L); /* liberation memoire pour L */
- return prec;
- }
- prec = L;
- L = L->suivant;
- }
- return L;
+ Liste prec = NULL;
+ while (L) {
+ if (e == L->valeur) {
+ prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */
+ free(L); /* liberation memoire pour L */
+ return prec;
+ }
+ prec = L;
+ L = L->suivant;
+ }
+ return L;
}
-
Liste supprimer_rec(element e, Liste L)
{
- if(!L) ; /* element absent - on ne fait rien */
- else if(L->valeur==e)
- {
- Cellule *p=L;
- L=L->suivant;
- free(p);
- }
- else L->suivant=supprimer_rec(e,L->suivant);
- return L;
+ if (!L) ; /* element absent - on ne fait rien */
+ else if (L->valeur == e) {
+ Cellule *p = L;
+ L = L->suivant;
+ free(p);
+ } else
+ L->suivant = supprimer_rec(e, L->suivant);
+ return L;
}
-
Liste inverser_iter(Liste L)
{
- Liste cell=NULL; /* une cellule temporaire */
- Liste inv=NULL; /* la liste inversee */
-
- while(L!=NULL)
- {
- cell=L; /* on prend la premiere cellule de la liste */
- L=L->suivant; /* le debut de la liste devient l'element suivant */
- cell->suivant=inv; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer*/
- inv=cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */
- }
- return inv;
+ Liste cell = NULL; /* une cellule temporaire */
+ Liste inv = NULL; /* la liste inversee */
+
+ while (L != NULL) {
+ cell = L; /* on prend la premiere cellule de la liste */
+ L = L->suivant; /* le debut de la liste devient l'element suivant */
+ cell->suivant = inv; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer */
+ inv = cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */
+ }
+ return inv;
}
-
-
Liste inserer_fin(element e, Liste L)
{
- Cellule *pc, *p1=L, *p2=NULL;
- pc = (Cellule *)malloc(sizeof(Cellule));
- pc->valeur=e;pc->suivant=NULL;
- if (!L) return pc;
- while (p1)
- {
- p2 = p1;
- p1 = p1->suivant;
- }
- p2->suivant = pc;
- pc->suivant = p1;
- return L;
+ Cellule *pc, *p1 = L, *p2 = NULL;
+ pc = (Cellule *) malloc(sizeof(Cellule));
+ pc->valeur = e;
+ pc->suivant = NULL;
+ if (!L)
+ return pc;
+ while (p1) {
+ p2 = p1;
+ p1 = p1->suivant;
+ }
+ p2->suivant = pc;
+ pc->suivant = p1;
+ return L;
}
-
Liste inverser_rec(Liste L)
{
- if(L != NULL) {
- return inserer_fin(L->valeur, inverser_rec(L->suivant));
- }
- else return L;
+ if (L != NULL) {
+ return inserer_fin(L->valeur, inverser_rec(L->suivant));
+ } else
+ return L;
}
-
-/****************************************************************************/
+/****************************************************************************/
int main()
{
- Liste L=NULL;
- printf("liste vide\n");
- visualiser_iter(L);
- visualiser_rec(L);
-
- printf("longueur=%d\n",longueur_iter(L));
- printf("longueur=%d\n",longueur_rec(L));
-
- printf("ajout de 3\n");
- L=ajouter_iter(3,L);
- printf("ajout de 6\n");
- L=ajouter_iter(6,L);
- printf("ajout de 1\n");
- L=ajouter_iter(1,L);
- printf("ajout de 10\n");
- L=ajouter_iter(10,L);
- printf("ajout de 6\n");
- L=ajouter_iter(6,L);
- visualiser_iter(L);
- visualiser_rec(L);
-
- printf("longueur=%d\n",longueur_iter(L));
- printf("longueur=%d\n",longueur_rec(L));
-
- printf("recherche de %d = %d\n",3,rechercher_iter(3,L));
- printf("recherche de %d = %d\n",3,rechercher_rec(3,L));
- printf("recherche de %d = %d\n",4,rechercher_iter(4,L));
- printf("recherche de %d = %d\n",4,rechercher_rec(4,L));
-
- printf("ajout (rec) de 4\n");
- L=ajouter_rec(4,L);
- visualiser_iter(L);
- printf("ajout (rec) de 8\n");
- L=ajouter_rec(8,L);
- visualiser_iter(L);
-
- printf("suppression (iter) de 4\n");
- supprimer_iter(4,L);
- visualiser_iter(L);
- printf("suppression (rec) de 6\n");
- supprimer_rec(6,L);
- visualiser_iter(L);
-
- printf("liste inversee (iter)\n");
- Liste inv = inverser_iter(L);
- visualiser_iter(inv);
-
- printf("Liste inversee (rec)\n");
- Liste inv2 = inverser_rec(inv);
- visualiser_iter(inv2);
-
- /* il faut aussi tester chaque fonction (visualiser, supprimer, rechercher, inverser, ...) sur tous les cas : liste vide, liste avec un seul element, operation sur le premier element, operation sur le dernier element, ... */
+ Liste L = NULL;
+ printf("liste vide\n");
+ visualiser_iter(L);
+ visualiser_rec(L);
+
+ printf("longueur=%d\n", longueur_iter(L));
+ printf("longueur=%d\n", longueur_rec(L));
+
+ printf("ajout de 3\n");
+ L = ajouter_iter(3, L);
+ printf("ajout de 6\n");
+ L = ajouter_iter(6, L);
+ printf("ajout de 1\n");
+ L = ajouter_iter(1, L);
+ printf("ajout de 10\n");
+ L = ajouter_iter(10, L);
+ printf("ajout de 6\n");
+ L = ajouter_iter(6, L);
+ visualiser_iter(L);
+ visualiser_rec(L);
+
+ printf("longueur=%d\n", longueur_iter(L));
+ printf("longueur=%d\n", longueur_rec(L));
+
+ printf("recherche de %d = %d\n", 3, rechercher_iter(3, L));
+ printf("recherche de %d = %d\n", 3, rechercher_rec(3, L));
+ printf("recherche de %d = %d\n", 4, rechercher_iter(4, L));
+ printf("recherche de %d = %d\n", 4, rechercher_rec(4, L));
+
+ printf("ajout (rec) de 4\n");
+ L = ajouter_rec(4, L);
+ visualiser_iter(L);
+ printf("ajout (rec) de 8\n");
+ L = ajouter_rec(8, L);
+ visualiser_iter(L);
+
+ printf("suppression (iter) de 4\n");
+ supprimer_iter(4, L);
+ visualiser_iter(L);
+ printf("suppression (rec) de 6\n");
+ supprimer_rec(6, L);
+ visualiser_iter(L);
+
+ printf("liste inversee (iter)\n");
+ Liste inv = inverser_iter(L);
+ visualiser_iter(inv);
+
+ printf("Liste inversee (rec)\n");
+ Liste inv2 = inverser_rec(inv);
+ visualiser_iter(inv2);
+
+ /* il faut aussi tester chaque fonction (visualiser, supprimer, rechercher, inverser, ...) sur tous les cas : liste vide, liste avec un seul element, operation sur le premier element, operation sur le dernier element, ... */
}
-
-/****************************************************************************/
+/****************************************************************************/
/* trace d'execution :
liste vide
-
longueur=0
longueur=0
ajout de 3
Liste inversee (rec)
1 3 6 8 10
*/
-
repositories / Algorithmic_C.git / blobdiff