+++ /dev/null
-/********************************************************************/
-/* Implantation d'une liste triee d'entiers */
-/********************************************************************/
-#include <stdio.h>
-#include <stdlib.h>
-
-typedef int element;
-
-typedef struct cellule {
- 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;
-}
-
-
-int longueur_iter(Liste L)
-{
- 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);
-}
-
-
-void visualiser_iter(Liste L)
-{
- 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);
- }
-}
-
-
-void visualiser_rec(Liste L)
-{
- 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;
-}
-
-
-int rechercher_rec(element e, Liste L)
-{
- 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);
-}
-
-
-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;
-}
-
-
-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 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;
-}
-
-
-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 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;
-}
-
-
-Liste inverser_rec(Liste L)
-{
- if(L != NULL) {
- return inserer_fin(L->valeur, inverser_rec(L->suivant));
- }
- else return L;
-}
-
-
-/****************************************************************************/
-
-int main()
-{int x;
- 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
-ajout de 6
-ajout de 1
-ajout de 10
-ajout de 6
-1 3 6 6 10
-1 3 6 6 10
-longueur=5
-longueur=5
-recherche de 3 = 1
-recherche de 3 = 1
-recherche de 4 = 0
-recherche de 4 = 0
-ajout (rec) de 4
-1 3 4 6 6 10
-ajout (rec) de 8
-1 3 4 6 6 8 10
-suppression (iter) de 4
-1 3 6 6 8 10
-suppression (rec) de 6
-1 3 6 8 10
-liste inversee (iter)
-10 8 6 3 1
-Liste inversee (rec)
-1 3 6 8 10
-*/
-
repositories / Algorithmic_C.git / blobdiff