Les listes chainées

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 728 fois - Téléchargée 40 fois

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

Ajouter un commentaire Commentaires
cs_lacousine Messages postés 58 Date d'inscription mardi 6 janvier 2004 Statut Membre Dernière intervention 13 juillet 2007
16 sept. 2005 à 03:38
je trouve que la source est très bien. J'avais justement un problème de constructeur par copie à règler. Et grace à ta source c'est réussi.

le truc que je ne comprend pas parcontre c'est ceci : public: maillon (const int); //constructeur
friend class liste;

pourquoi tu utilises friend ? moi je ne vois pas l'intéret et je ne comprend pas pourquoi tu as mis cette notation.
stysty Messages postés 7 Date d'inscription vendredi 4 avril 2003 Statut Membre Dernière intervention 24 octobre 2005
30 avril 2003 à 19:12
Est ce que tu pourrais me donner des voie pour l im plementer en csharp car je n'y arrive pas
Merci
cs_Xentor Messages postés 64 Date d'inscription jeudi 9 août 2001 Statut Membre Dernière intervention 24 juillet 2003
9 janv. 2002 à 16:21
lol, déconstructeur = destructeur !

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.