Les listes chainées

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 702 fois - Téléchargée 38 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_Xentor
Messages postés
64
Date d'inscription
jeudi 9 août 2001
Statut
Membre
Dernière intervention
24 juillet 2003
-
lol, déconstructeur = destructeur !
stysty
Messages postés
7
Date d'inscription
vendredi 4 avril 2003
Statut
Membre
Dernière intervention
24 octobre 2005
-
Est ce que tu pourrais me donner des voie pour l im plementer en csharp car je n'y arrive pas
Merci
cs_lacousine
Messages postés
58
Date d'inscription
mardi 6 janvier 2004
Statut
Membre
Dernière intervention
13 juillet 2007
-
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.

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.