Les listes chainées

Commenter

Contenu du snippet

aide sur les listes chainées pour debutant

Source / Exemple : 


//cours sur les listes chainées

#include "stdafx.h"
#include "iostream.h"

/////////////////////////////////////////////////

class maillon
{ 
private: int info;
		 maillon * suiv;

public:  maillon (const int); //constructeur
		 friend class liste;
};

maillon::maillon(const int i)
{
	info =i;
	suiv=NULL;
}

/////////////////////////////////////////////////

class liste
{ 
	private: maillon *debut;
	         maillon *fin;

	public:  liste();
			 ~liste();
			 int est_vide();
			 void faire_entrer(int);
			 int faire_sortir();
			 liste(liste &);
			 void affiche();			 
			 void inserer_trier(int);
			 bool est_present(int);
			 bool retire_trier(int);
};

liste::liste()
{
	debut=NULL;
	fin=NULL;
	cout<<"Le constructeur fonctionne"<<endl;
}

liste::~liste()
{
	int tmp;
	while(!est_vide())
			{
			  tmp=faire_sortir();
			}
	cout<<"Le deconstructeur fonctionne"<<endl;
}

int liste::est_vide()
{
	return debut==NULL;
}

void liste::faire_entrer(int inf) //fait entrer un maillon à la fin de la liste 
{	
	cout<<"creation d'un maillon: ";
	maillon *nm; // nm:nouveau maillon
	nm=new maillon(inf);
	if (debut==NULL) //liste vide
		{ cout<<"la liste est vide"<<endl;
		  debut =nm;
		  fin=nm;
		}
	else //la liste n'est pas vide
		{ cout<<"la liste n'est pas vide"<<endl;
		  fin->suiv=nm;
		  fin=nm;
		}
}

int liste::faire_sortir() // fait sortir le premier maillon de la liste
{
	maillon *p;
	int res;
	if (debut==NULL) //liste vide
		{ cout<<"probléme"<<endl;
		  return -1;
		}
	res=debut->info;
	p=debut;
	debut=debut->suiv;
	delete p;
	if (debut==NULL) fin=NULL;// liste vide apres suppression
	return res;
}

liste::liste(liste &l)//constructeur par recopie
{cout<<"constructeur par recopie"<<endl;
	debut=NULL;
	fin=NULL;
	maillon *p=l.debut;
	while(p)
		{ faire_entrer(p->info);
		  p=p->suiv;
		}
}

void liste::affiche()
{	cout<<"\n"<<"le contenu de la liste est: ";
	maillon *p=debut;
	while(p) //p!=NULL
			{ cout<<p->info<<"  ";
			  p=p->suiv;
			}
	cout<<endl;
}

void liste::inserer_trier(int inf) // insere un maillon trier dans le sens croissant
{
	maillon *np=new maillon (inf); //creation d'un nouveau maillon
	maillon *p; //pointeur de type maillon
	if (est_vide()) {debut=np;;fin=np;} //cas de la liste vide
	else if (inf<debut->info) { np->suiv=debut; debut=np;} //cas insertion en tete et cas 1 element
	else {  p=debut;
			while ((p->suiv)&&(p->suiv->info<inf)) {p=p->suiv;} 
			if (p->suiv) { np->suiv=p->suiv; p->suiv=np;} //cas insere un maillon
			else {p->suiv=np; fin=np;}//cas fin de liste
	     }
}

bool liste::est_present(int inf) // verifie si une valeur est present dans la liste
								 // la liste doit etre trier
{
	maillon *p=debut;
	while((p!=NULL)&&(p->info<inf)) p=p->suiv;
	if (p==NULL) return false;
	else if (p->info==inf) return true;
	else return false;
}

bool liste::retire_trier(int inf) // la liste doit etre trier 
{								  // possibilité de rajouter en tete un if(est-present())
								  // pour vérifier si la valeur a supprimer est dans la liste chainée
	cout<<"\n"<<"supression de "<<inf<<endl; 
	maillon *p,*tmp;
	p=debut;

	while((p->suiv!=NULL)&&(p->suiv->info<inf)) p=p->suiv;// se positionne sur le maillon précédent
														  // celui qui doit etre supprimer
	if((p->suiv!=NULL)&&(p->suiv->info==inf))  // cas dans la liste
											{ tmp=p->suiv;
											  p->suiv=p->suiv->suiv;
											  delete tmp;
											  return true;
											}
	else if(p->suiv==NULL)// cas fin de liste
						  {
							tmp=p->suiv;
							p->suiv=NULL;
							delete tmp;
							return true;
					      }
	else {
			if (est_vide()) return false;
			if (debut->info==inf) //cas debut de liste
								{ tmp=debut;
								  debut=debut->suiv;
								  delete tmp;
								  if(debut==NULL) fin=NULL; //cas la liste est vide apres supression d'un maillon
								  return true;
								}
		}

}

			
/////////////////////////////////////////////

//chaque partie du main peut etre testée séparément sauf si indiqué

void main ()
{
  
//test creation d'une liste
	liste l;
	l.faire_entrer(2);//creation de maillon
	l.faire_entrer(5);
	l.faire_entrer(8);
	l.faire_entrer(12);	
	//for(int i=0;i<5;i++) {l.faire_entrer(i);}//creation de 5 maillons
	l.affiche();

	//test constructeur par recopie
/*	liste a(l);//constructeur par recopie:permet de copier le liste l dans la liste a
	l.affiche();//affiche la liste l
	a.affiche();//affiche la liste a


  • /


	//test insertion d'un maillon
	l.inserer_trier(1);//insere 1 dans la liste cas insertion en tete
	l.affiche();
	l.inserer_trier(6);//cas insere un maillon
	l.affiche();
	l.inserer_trier(20);//cas fin de liste
	l.affiche();

	//test est_present
/*	bool a;
	int val=0;
	cout<<"entrer la valeur a chercher: ";
	cin>>val;
	a=l.est_present(val);
	if(a==true) cout<<val<<" est present dans la liste"<<endl;
	else cout<<val<<" n'est pas present dans la liste"<<endl;


  • /

 

	//test retire_trier (faire en meme temps le test d'insertion!!)
	bool ret;
	ret=l.retire_trier(1);
	if (ret==false) cout<<"la liste est vide"<<endl;
	l.affiche();
	ret=l.retire_trier(6);
	if (ret==false) cout<<"la liste est vide"<<endl;
	l.affiche();
	ret=l.retire_trier(20);
	if (ret==false) cout<<"la liste est vide"<<endl;
	l.affiche();

  
}

Conclusion :


fonctionne sous visual c++ 6 et unix

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.