Commit | Line | Data |
---|---|---|
3f0f8bfd JB |
1 | /********************************************************************/ |
2 | /* Implantation d'une liste triee d'entiers */ | |
3 | /********************************************************************/ | |
4 | #include <stdio.h> | |
5 | #include <stdlib.h> | |
ef5acd44 | 6 | #include <stdbool.h> |
3f0f8bfd JB |
7 | |
8 | typedef int element; | |
9 | ||
10 | typedef struct cellule { | |
11 | element valeur; | |
12 | struct cellule *suivant; | |
13 | } Cellule, *Liste; | |
14 | ||
15 | Liste ajouter_iter(element e, Liste L) | |
16 | { | |
17 | Cellule *pc, *p1 = L, *p2 = NULL; | |
18 | ||
19 | pc = (Cellule *) malloc(sizeof(Cellule)); | |
20 | pc->valeur = e; | |
21 | pc->suivant = NULL; | |
22 | ||
23 | if (!L) /* liste vide */ | |
24 | return pc; | |
25 | ||
26 | while (p1 && (e >= p1->valeur)) { | |
27 | p2 = p1; | |
28 | p1 = p1->suivant; | |
29 | } | |
30 | ||
31 | if (!p2) { /* insertion en tete */ | |
32 | pc->suivant = L; | |
33 | L = pc; | |
34 | } else { /* insertion entre p2 et p1 */ | |
35 | p2->suivant = pc; | |
36 | pc->suivant = p1; | |
37 | } | |
38 | ||
39 | return L; | |
40 | } | |
41 | ||
42 | int longueur_iter(Liste L) | |
43 | { | |
44 | int longueur = 0; | |
45 | ||
105fac43 | 46 | while (L != NULL) { |
3f0f8bfd JB |
47 | L = L->suivant; |
48 | longueur++; | |
49 | } | |
50 | return longueur; | |
51 | } | |
52 | ||
53 | int longueur_rec(Liste L) | |
54 | { | |
105fac43 JB |
55 | if (L != NULL) { |
56 | return 1 + longueur_rec(L->suivant); | |
57 | } else { | |
58 | return 0; | |
59 | } | |
3f0f8bfd JB |
60 | } |
61 | ||
62 | void visualiser_iter(Liste L) | |
63 | { | |
ca2c69d5 JB |
64 | int compteur = 0; |
65 | ||
66 | printf("--Debut--\n"); | |
67 | while (L != NULL) { | |
68 | printf("L[%d]->value=%d\n", compteur, L->valeur); | |
69 | L = L->suivant; | |
70 | compteur++; | |
71 | } | |
72 | printf("--Fin--\n"); | |
73 | } | |
74 | ||
75 | void _visualiser_rec(Liste L, int compteur) | |
76 | { | |
77 | if (L != NULL) { | |
ef5acd44 JB |
78 | if (compteur == 0) |
79 | printf("--Debut--\n"); | |
ca2c69d5 JB |
80 | printf("L[%d]->value=%d\n", compteur, L->valeur); |
81 | compteur++; | |
82 | _visualiser_rec(L->suivant, compteur); | |
83 | if (compteur == (longueur_rec(L) - 1)) | |
84 | printf("--Fin--\n"); | |
85 | } | |
86 | ||
3f0f8bfd JB |
87 | } |
88 | ||
89 | void visualiser_rec(Liste L) | |
90 | { | |
ca2c69d5 JB |
91 | int compteur = 0; |
92 | ||
ca2c69d5 | 93 | _visualiser_rec(L, compteur); |
3f0f8bfd JB |
94 | } |
95 | ||
ef5acd44 | 96 | bool rechercher_iter(element e, Liste L) |
3f0f8bfd | 97 | { |
ef5acd44 JB |
98 | bool rt_val = false; |
99 | ||
85bdc677 JB |
100 | while (L != NULL) { |
101 | if (L->valeur == e) { | |
cdc1c7e2 | 102 | rt_val = true; |
85bdc677 JB |
103 | break; |
104 | } | |
105 | L = L->suivant; | |
ef5acd44 | 106 | } |
ef5acd44 | 107 | return rt_val; |
3f0f8bfd JB |
108 | } |
109 | ||
110 | Liste rechercher_rec(element e, Liste L) | |
111 | { | |
f23fb1de JB |
112 | if (L->valeur != e && L->suivant != NULL) |
113 | { | |
114 | return L = rechercher_rec(e, L->suivant); | |
115 | } | |
3f0f8bfd JB |
116 | } |
117 | ||
118 | Liste ajouter_rec(element e, Liste L) | |
119 | { | |
120 | /* ... */ | |
121 | } | |
122 | ||
123 | Liste supprimer_iter(element e, Liste L) | |
124 | { | |
125 | /* ... */ | |
126 | } | |
127 | ||
128 | Liste supprimer_rec(element e, Liste L) | |
129 | { | |
130 | /* ... */ | |
131 | } | |
132 | ||
133 | Liste inverser_iter(Liste L) | |
134 | { | |
135 | /* ... */ | |
136 | } | |
137 | ||
138 | Liste inverser_rec(Liste L) | |
139 | { | |
140 | /* ... */ | |
141 | } | |
142 | ||
143 | /****************************************************************************/ | |
144 | int main() | |
145 | { | |
146 | int x; | |
147 | Liste L = NULL; | |
105fac43 JB |
148 | L = ajouter_iter(2, L); |
149 | L = ajouter_iter(1, L); | |
150 | L = ajouter_iter(3, L); | |
85bdc677 JB |
151 | L = ajouter_iter(4, L); |
152 | printf("Saisir un entier a chercher dans la liste L\n"); | |
3f0f8bfd | 153 | scanf("%d", &x); |
ca2c69d5 | 154 | printf("L a pour longueur %d\n", longueur_rec(L)); |
3f0f8bfd | 155 | visualiser_iter(L); |
ca2c69d5 | 156 | visualiser_rec(L); |
85bdc677 JB |
157 | if (rechercher_iter(x, L)) |
158 | printf("L'element %d est present dans L\n", x); | |
159 | else | |
160 | printf("L'element %d n'est pas present dans L\n", x); | |
f23fb1de JB |
161 | if (rechercher_rec(x, L) != NULL) |
162 | printf("L'element %d est present dans L\n", x); | |
163 | else | |
164 | printf("L'element %d n'est pas present dans L\n", x); | |
3f0f8bfd JB |
165 | /* ... */ |
166 | } | |
167 | ||
168 | /****************************************************************************/ |