| 1 | /********************************************************************/ |
| 2 | /* Implantation d'une liste triee d'entiers */ |
| 3 | /********************************************************************/ |
| 4 | #include <stdio.h> |
| 5 | #include <stdlib.h> |
| 6 | |
| 7 | typedef int element; |
| 8 | |
| 9 | typedef struct cellule { |
| 10 | element valeur; |
| 11 | struct cellule *suivant; |
| 12 | } Cellule, *Liste; |
| 13 | |
| 14 | |
| 15 | |
| 16 | Liste ajouter_iter(element e, Liste L) |
| 17 | { |
| 18 | Cellule *pc, *p1=L, *p2=NULL; |
| 19 | |
| 20 | pc = (Cellule *)malloc(sizeof(Cellule)); |
| 21 | pc->valeur=e;pc->suivant=NULL; |
| 22 | |
| 23 | if (!L) /* liste vide */ return pc; |
| 24 | while (p1 && (e >= p1->valeur)) |
| 25 | { |
| 26 | p2 = p1; |
| 27 | p1 = p1->suivant; |
| 28 | } |
| 29 | |
| 30 | if (!p2) /* insertion en tete */ {pc->suivant = L; L=pc; } |
| 31 | else {/* insertion entre p2 et p1 */ |
| 32 | p2->suivant = pc; |
| 33 | pc->suivant = p1; |
| 34 | } |
| 35 | |
| 36 | return L; |
| 37 | } |
| 38 | |
| 39 | |
| 40 | int longueur_iter(Liste L) |
| 41 | { |
| 42 | int res = 0; |
| 43 | while(L) |
| 44 | { |
| 45 | res = res + 1; |
| 46 | L=L->suivant; |
| 47 | } |
| 48 | return res; |
| 49 | } |
| 50 | |
| 51 | |
| 52 | int longueur_rec(Liste L) |
| 53 | { |
| 54 | if(!L) return 0; |
| 55 | return 1+longueur_rec(L->suivant); |
| 56 | } |
| 57 | |
| 58 | |
| 59 | void visualiser_iter(Liste L) |
| 60 | { |
| 61 | while (L) |
| 62 | { |
| 63 | printf("%d ",L->valeur); |
| 64 | L = L->suivant; |
| 65 | } |
| 66 | printf("\n"); |
| 67 | } |
| 68 | |
| 69 | |
| 70 | void visualiser_aux(Liste L) |
| 71 | { |
| 72 | if(L) |
| 73 | { |
| 74 | printf("%d ",L->valeur); |
| 75 | visualiser_aux(L->suivant); |
| 76 | } |
| 77 | } |
| 78 | |
| 79 | |
| 80 | void visualiser_rec(Liste L) |
| 81 | { |
| 82 | visualiser_aux(L); |
| 83 | printf("\n"); |
| 84 | } |
| 85 | |
| 86 | |
| 87 | int rechercher_iter(element e, Liste L) |
| 88 | { |
| 89 | while(L) |
| 90 | { |
| 91 | if(e == L->valeur) return 1; |
| 92 | L = L->suivant; |
| 93 | } |
| 94 | return 0; |
| 95 | } |
| 96 | |
| 97 | |
| 98 | int rechercher_rec(element e, Liste L) |
| 99 | { |
| 100 | if(L == NULL) return 0; |
| 101 | if(e==L->valeur) return 1; |
| 102 | return rechercher_rec(e,L->suivant); |
| 103 | } |
| 104 | |
| 105 | |
| 106 | Liste rechercher_rec2(element e, Liste L) |
| 107 | { |
| 108 | if(!L || e==L->valeur) return L; |
| 109 | else return rechercher_rec2(e,L->suivant); |
| 110 | } |
| 111 | |
| 112 | |
| 113 | Liste ajouter_rec(element e, Liste L) |
| 114 | { |
| 115 | if(!L) |
| 116 | { |
| 117 | L=(Cellule *)malloc(sizeof(Cellule)); /* liste vide */ |
| 118 | L->valeur=e;L->suivant=NULL; |
| 119 | } |
| 120 | else if(e < L->valeur) /* ajouter DEVANT la tete */ |
| 121 | { |
| 122 | Cellule *p=(Cellule *)malloc(sizeof(Cellule)); |
| 123 | p->valeur=e; p->suivant=L; |
| 124 | L=p; /* nouvelle tete de liste */ |
| 125 | } |
| 126 | else L->suivant=ajouter_rec(e,L->suivant); /* ajouter DERRIERE la tete */ |
| 127 | return L; |
| 128 | } |
| 129 | |
| 130 | |
| 131 | Liste supprimer_iter(element e, Liste L) |
| 132 | { |
| 133 | Liste prec = NULL; |
| 134 | while(L) |
| 135 | { |
| 136 | if(e == L->valeur) { |
| 137 | prec->suivant = L->suivant; /* le suivant de prec devient le suivant de L */ |
| 138 | free(L); /* liberation memoire pour L */ |
| 139 | return prec; |
| 140 | } |
| 141 | prec = L; |
| 142 | L = L->suivant; |
| 143 | } |
| 144 | return L; |
| 145 | } |
| 146 | |
| 147 | |
| 148 | Liste supprimer_rec(element e, Liste L) |
| 149 | { |
| 150 | if(!L) ; /* element absent - on ne fait rien */ |
| 151 | else if(L->valeur==e) |
| 152 | { |
| 153 | Cellule *p=L; |
| 154 | L=L->suivant; |
| 155 | free(p); |
| 156 | } |
| 157 | else L->suivant=supprimer_rec(e,L->suivant); |
| 158 | return L; |
| 159 | } |
| 160 | |
| 161 | |
| 162 | Liste inverser_iter(Liste L) |
| 163 | { |
| 164 | Liste cell=NULL; /* une cellule temporaire */ |
| 165 | Liste inv=NULL; /* la liste inversee */ |
| 166 | |
| 167 | while(L!=NULL) |
| 168 | { |
| 169 | cell=L; /* on prend la premiere cellule de la liste */ |
| 170 | L=L->suivant; /* le debut de la liste devient l'element suivant */ |
| 171 | cell->suivant=inv; /* on libere l'element de la liste et on le place en debut de la liste a renvoyer*/ |
| 172 | inv=cell; /* l'element qu'on vient de mettre en debut de liste devient le debut de la liste de a renvoyer */ |
| 173 | } |
| 174 | return inv; |
| 175 | } |
| 176 | |
| 177 | |
| 178 | |
| 179 | Liste inserer_fin(element e, Liste L) |
| 180 | { |
| 181 | Cellule *pc, *p1=L, *p2=NULL; |
| 182 | pc = (Cellule *)malloc(sizeof(Cellule)); |
| 183 | pc->valeur=e;pc->suivant=NULL; |
| 184 | if (!L) return pc; |
| 185 | while (p1) |
| 186 | { |
| 187 | p2 = p1; |
| 188 | p1 = p1->suivant; |
| 189 | } |
| 190 | p2->suivant = pc; |
| 191 | pc->suivant = p1; |
| 192 | return L; |
| 193 | } |
| 194 | |
| 195 | |
| 196 | Liste inverser_rec(Liste L) |
| 197 | { |
| 198 | if(L != NULL) { |
| 199 | return inserer_fin(L->valeur, inverser_rec(L->suivant)); |
| 200 | } |
| 201 | else return L; |
| 202 | } |
| 203 | |
| 204 | |
| 205 | /****************************************************************************/ |
| 206 | |
| 207 | int main() |
| 208 | { |
| 209 | Liste L=NULL; |
| 210 | printf("liste vide\n"); |
| 211 | visualiser_iter(L); |
| 212 | visualiser_rec(L); |
| 213 | |
| 214 | printf("longueur=%d\n",longueur_iter(L)); |
| 215 | printf("longueur=%d\n",longueur_rec(L)); |
| 216 | |
| 217 | printf("ajout de 3\n"); |
| 218 | L=ajouter_iter(3,L); |
| 219 | printf("ajout de 6\n"); |
| 220 | L=ajouter_iter(6,L); |
| 221 | printf("ajout de 1\n"); |
| 222 | L=ajouter_iter(1,L); |
| 223 | printf("ajout de 10\n"); |
| 224 | L=ajouter_iter(10,L); |
| 225 | printf("ajout de 6\n"); |
| 226 | L=ajouter_iter(6,L); |
| 227 | visualiser_iter(L); |
| 228 | visualiser_rec(L); |
| 229 | |
| 230 | printf("longueur=%d\n",longueur_iter(L)); |
| 231 | printf("longueur=%d\n",longueur_rec(L)); |
| 232 | |
| 233 | printf("recherche de %d = %d\n",3,rechercher_iter(3,L)); |
| 234 | printf("recherche de %d = %d\n",3,rechercher_rec(3,L)); |
| 235 | printf("recherche de %d = %d\n",4,rechercher_iter(4,L)); |
| 236 | printf("recherche de %d = %d\n",4,rechercher_rec(4,L)); |
| 237 | |
| 238 | printf("ajout (rec) de 4\n"); |
| 239 | L=ajouter_rec(4,L); |
| 240 | visualiser_iter(L); |
| 241 | printf("ajout (rec) de 8\n"); |
| 242 | L=ajouter_rec(8,L); |
| 243 | visualiser_iter(L); |
| 244 | |
| 245 | printf("suppression (iter) de 4\n"); |
| 246 | supprimer_iter(4,L); |
| 247 | visualiser_iter(L); |
| 248 | printf("suppression (rec) de 6\n"); |
| 249 | supprimer_rec(6,L); |
| 250 | visualiser_iter(L); |
| 251 | |
| 252 | printf("liste inversee (iter)\n"); |
| 253 | Liste inv = inverser_iter(L); |
| 254 | visualiser_iter(inv); |
| 255 | |
| 256 | printf("Liste inversee (rec)\n"); |
| 257 | Liste inv2 = inverser_rec(inv); |
| 258 | visualiser_iter(inv2); |
| 259 | |
| 260 | /* 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, ... */ |
| 261 | } |
| 262 | |
| 263 | |
| 264 | /****************************************************************************/ |
| 265 | |
| 266 | /* trace d'execution : |
| 267 | liste vide |
| 268 | |
| 269 | |
| 270 | longueur=0 |
| 271 | longueur=0 |
| 272 | ajout de 3 |
| 273 | ajout de 6 |
| 274 | ajout de 1 |
| 275 | ajout de 10 |
| 276 | ajout de 6 |
| 277 | 1 3 6 6 10 |
| 278 | 1 3 6 6 10 |
| 279 | longueur=5 |
| 280 | longueur=5 |
| 281 | recherche de 3 = 1 |
| 282 | recherche de 3 = 1 |
| 283 | recherche de 4 = 0 |
| 284 | recherche de 4 = 0 |
| 285 | ajout (rec) de 4 |
| 286 | 1 3 4 6 6 10 |
| 287 | ajout (rec) de 8 |
| 288 | 1 3 4 6 6 8 10 |
| 289 | suppression (iter) de 4 |
| 290 | 1 3 6 6 8 10 |
| 291 | suppression (rec) de 6 |
| 292 | 1 3 6 8 10 |
| 293 | liste inversee (iter) |
| 294 | 10 8 6 3 1 |
| 295 | Liste inversee (rec) |
| 296 | 1 3 6 8 10 |
| 297 | */ |
| 298 | |