Listes Chainées
Anas FAJOUI & SaifElislam BETTAOUI G. Info groupe Prof : [Link]
A
liste simplement chainee :
struct noeud
int elt;
struct noeud *suiv;
};
typedef struct noeud noeud;
//Question 1:
int comptage_L(noeud *L)
noeud *P = L;
int i = 0;
while (P)
i++;
P = P->suiv;
return i;
//Question 2:
int comptage_occ(noeud *L, int E)
{
noeud *P = L;
int i = 0;
while (P)
if (P->elt == E)
i++;
P = P->suiv;
return i;
//Question 3:
int verification(noeud *L)
noeud *P = L;
while (P->suiv->suiv)
if (P->elt > P->suiv->elt)
return 0;
else
P = P->suiv;
return 1;
}
//Question 4:
noeud * insertion_tete(noeud *L, int E)
noeud *nouv;
if (nouv = (noeud*) malloc(sizeof(noeud*)))
nouv->elt = E;
if (!L)
L = nouv;
nouv->suiv = NULL;
else
nouv->suiv = L;
L = nouv;
return L;
//Question 5:
noeud * insertion_queue(noeud *L, int E)
noeud *nouv;
if (nouv = (noeud*) malloc(sizeof(noeud*)))
{
nouv->elt = E;
nouv->suiv = NULL;
noeud *P = L;
while (P->suiv)
P = P->suiv;
P->suiv = nouv;
return L;
//Question 6:
noeud * insertion_pos(noeud *L, int n)
noeud *nouv;
noeud *P = L;
for (int i = 1; i < n; i++)
P = P->suiv;
nouv->suiv = P->suiv;
P->suiv = nouv;
return L;
//Question 7:
noeud * suppression_pos(noeud *L, int n, int *E)
{
noeud *P = L;
for (int i = 1; i < n; i++)
P = P->suiv;
E = P->suiv->elt;
P->suiv = P->suiv->suiv;
return L;
Listes à double chainage :
//Question 10:
doublec * inserer_deb(doublec * L, int E)
doublec * nouv;
if (nouv = (doublec*) malloc(sizeof(doublec)))
nouv -> elt = E;
nouv -> pred = NULL;
nouv -> suiv = L;
if (!L)
L = nouv;
else
L -> pred = nouv;
L = nouv;
return L;
}
//Question 10:
doublec * inserer_fin(doublec * L, int E)
doublec * nouv;
if (nouv = (doublec*) malloc(sizeof(doublec)))
nouv -> elt = E;
nouv -> suiv = NULL;
if (!L)
nouv -> pred = NULL;
L = nouv;
else
doublec * P = L;
while (P -> suiv)
P = P -> suiv;
P -> suiv = nouv;
nouv -> pred = P;
return L;
//Question 11:
doublec * supprimer_deb(doublec * L, int * E)
{
doublec * P = L;
*E = L -> elt;
if (L -> suiv)
L -> suiv -> pred = NULL;
L = L -> suiv;
free(P);
return L;
//Question 11:
doublec * supprimer_fin(doublec * L, int * E)
doublec * P = L;
while (P -> suiv)
P = P -> suiv;
*E = P -> elt;
if (P -> pred)
P -> pred -> suiv = NULL;
else
L = NULL;
free(P);
return L;
Classe d’etudiants (Question 8/9) :
struct noeud{
int val;
struct noeud* suiv;
struct noeud* prec;
};
struct tete{
struct noeud* first;
struct noeud* last;
};
struct noeud* nouv_noeud(int x){
struct noeud* P = (struct noeud*)malloc(sizeof(struct noeud));
P->val = x;
P->suiv = NULL;
P->prec = NULL;
};
struct tete* initialize(){
struct tete* liste = (struct tete*)malloc(sizeof(struct tete));
liste->first = NULL;
liste->last = NULL;
return liste;
};
int count_list(struct tete* liste){
int count = 0;
struct noeud* liste1 = liste->first;
while(liste1 != NULL){
count++;
liste1 = liste1->suiv;
return count;
};
struct noeud* adress_by_index(struct tete* liste, int k){
int i = 1;
struct noeud* liste1 = liste->first;
while(liste1 != NULL && i<k){
i++;
liste1 = liste1->suiv;
if(liste1 != NULL) return liste1;
else return NULL;
};
void insert_queue(struct tete* liste, int x){
if(liste->first == NULL){
struct noeud* P = nouv_noeud(x);
liste->first = P;
liste->last = P;
else{
struct noeud* P = nouv_noeud(x);
P->prec = liste->last;
liste->last->suiv = P;
liste->last = P;
};
void afficher_liste(struct tete* liste){
struct noeud* element = liste->first;
printf("\nListe:\n");
while(element != NULL){
printf("%d; ", element->val);
element = element->suiv;
};
void supp(struct tete* liste, int k){
int len = count_list(liste);
if(k == 1){
struct noeud* P = liste->first;
liste->first = liste->first->suiv;
liste->first->prec = NULL;
free(P);
if(k == len){
struct noeud* P = liste->last;
liste->last = liste->last->prec;
liste->last->suiv = NULL;
free(P);
if(k>1 && k<len){
struct noeud* precedant = adress_by_index(liste, k-1);
struct noeud* P = precedant->suiv;
struct noeud* suivant = P->suiv;
precedant->suiv = suivant;
suivant->prec = precedant;
free(P);
};
