Une liste chainée avec clés

Commenter

Contenu du snippet

une liste chainée qui range des objets "ordonnables" (une classe abstraite, qu'il faut implémenter dans la classe "fille" à ranger dans la liste.

Je ne sais pas si ce genre de prog peut intéresser quelqu'un. Si ce n'est pas le cas, merci de me l'indiquer, je n'en mettrai plus.

Source / Exemple : 


#ifndef _LISTEORDONNEE_H_
#define _LISTEORDONNEE_H_

class	Ordonnable
{
public:
	virtual	~Ordonnable(){}

	virtual int	compareTo(Ordonnable *obj)=0;
	//Précond : obj doit être de même type que this
	//Résultat:	retourne : -1,0 ou 1 selon que obj est resp <,= ou > à this

	virtual char *getIdentifiant()=0;
	//Précond : aucune
	//Résultat: retourne une chaine de caractères identifiant le type
	//			d'objet. La chaine est dans le tas, et doit être détruite par
	//			l'utilisateur. Cette fonction sert à la gestion des listes,
	//			afin de garantir qu'une liste ne contient qu'un type d'objet
	//			ordonnable (cette garantie n'est valable que dans la mesure
	//			où l'utilisateur donne des identifiants différents à chaque
	//			type d'objet ordonnable).
};

class	CLOrdonnable
{
	friend class ListeOrdonnee;
//private:
public:
	Ordonnable		*val;
	CLOrdonnable	*suiv;
protected:
public:
	CLOrdonnable(Ordonnable *val, CLOrdonnable *suiv=NULL);
	virtual ~CLOrdonnable();
};

class	ListeOrdonnee
{
//private:
public:
	//Tête de la liste chaînée
	CLOrdonnable	*tete;
	//Identifiant des éléments reçus par la liste
	char			*identifiant;

	int	chercheCOrdonnable(	Ordonnable		*valCherchee,
							CLOrdonnable	*&celTrouvee,
							CLOrdonnable	*&celPrecedente);
	//Précond : val ne doit pas être nul.
	//Résultat: retourne 1 si valCherchee a été trouvée dans la liste, ou 3 si elle n'a
	//			pas été trouvée.
	//			si une erreur s'est produite, retourne son code.
	//			Si la valeur a été trouvée, celTrouvee et celPrecedente pointent
	//			respectivement la cellule contenant la valeur cherchée, et celle
	//			la précédant.
	//			Si la valeur n'a pas été trouvée, celTrouvee et celPrecedente pointent
	//			resp sur la cellule contenant la valeur sup, et celle la précédant

protected:
public:
	ListeOrdonnee(char *identifiant=NULL);
	~ListeOrdonnee();

	CLOrdonnable *getTete();
	//Précond : aucune
	//Résultat: retourne un pointeur sur la tete de la liste

	int ajouteElement (Ordonnable *val);
	//Précond : Si l'identifiant de type est déjà renseigné, l'objet passé
	//			en paramètre doit posséder le même identifiant de type.
	//			Si l'identifiant de type n'est pas renseigné, la liste prend
	//			pour seul identifiant acceptable le type de l'objet passé en argument.
	//			L'identifiant de l'instance de l'objet ne doit pas être déjà présent
	//			dans la liste.
	//			Si l'opération réussit, la méthode retourne 0. Si elle échoue,
	//			un code d'erreur est retourné.
	//Action  : Stocke l'objet passé en paramètre dans la liste ordonnée.

	int	supprimeElement(Ordonnable *val);
	//Précond : Si l'identifiant de type est déjà renseigné, l'objet passé
	//			en paramètre doit posséder le même identifiant de type.
	//			L'identifiant de l'instance de l'objet ne doit pas être déjà présent
	//			dans la liste.
	//			Si l'opération réussit, la méthode retourne 0. Si elle échoue,
	//			un code d'erreur est retourné.
	//Action  :	supprime l'objet possédant le même identifiant d'instance que celui
	//			passé en paramètre, si il existe.

	int	getNombreElements();
	//Précond : aucune
	//Résultat: retourne le nombre d'éléments présents dans la liste chaînée

	void vide();
	//Précond : aucune
	//Action  : vide la liste. Tous les éléments sont supprimés de la liste,
	//			et sont détruits.
};

#endif

/*
Codes des erreurs retournées
0	pas d'erreur
1	identifiant d'instance déjà présent
2	identifiant de type incorrect
3	identifiant d'instance non trouvé
4	pointeur nul interdit


  • /


CLOrdonnable::CLOrdonnable(Ordonnable *val, CLOrdonnable *suiv)
{
	this->val = val;
	this->suiv = suiv;
}

CLOrdonnable::~CLOrdonnable()
{
	delete(this->val);
}

ListeOrdonnee::ListeOrdonnee(char *identifiant)
{
	int l;
	this->tete = NULL;

	if (identifiant==NULL)
	{
		this->identifiant=NULL;
	}
	else
	{
		l=strlen(identifiant);
		this->identifiant = new char[l+1];
		strcpy(this->identifiant,identifiant);
	}
}

ListeOrdonnee::~ListeOrdonnee()
{
	this->vide();
	delete(this->identifiant);
}

CLOrdonnable *ListeOrdonnee::getTete()
{
	return	this->tete;
}

int ListeOrdonnee::chercheCOrdonnable(	Ordonnable *valCherchee,
										/*R*/CLOrdonnable *&celTrouvee,
										/*R*/CLOrdonnable *&celPrecedente)
{
	int		resultComp;
	char	*ident;

	if (valCherchee==NULL)
	{
		//erreur valeur nulle interdite
		return	4;
	}

	//test sur l'identifiant de type
	if (this->identifiant==NULL)
	{
		//Si l'identifiant de la liste n'a pas été initialisé,
		//on l'initialise avec l'identifiant de type de l'instance passée
		this->identifiant=valCherchee->getIdentifiant();
	}
	else
	{
		//Comparaison de l'identifiant de type de la liste, avec celui
		//du type de l'instance recherchée.
		ident = valCherchee->getIdentifiant();
		if (strcmp(ident,this->identifiant)!=0)
		{
			delete(ident);
			//erreur type incorrect pour cette liste
			return	2;
		}
		delete (ident);
	}
	
	//Recherche de l'indentifiant d'instance :
	//parcours partiel de la liste chainée, jusqu'à rencontrer une instance
	//dont la comparaison indique qu'elle est supérieure ou égale à celle recherchée
	resultComp=-1;
	celPrecedente = NULL;
	celTrouvee = this->tete;
	while (	celTrouvee!=NULL &&/*alors*/
			(resultComp=valCherchee->compareTo(celTrouvee->val))<0)
	{
		celPrecedente = celTrouvee;
		celTrouvee = celTrouvee->suiv;
	}
	if (resultComp!=0)
	{
		//identifiant d'instance non trouvé
		return	3;
	}
	//identifiant d'instance trouvé
	return	1;
}

int ListeOrdonnee::ajouteElement (Ordonnable *val)
{
	CLOrdonnable	*precedent=NULL;
	CLOrdonnable	*trouve=NULL;
	CLOrdonnable	*nouvelle=NULL;
	int	result;

	result = chercheCOrdonnable(val,trouve,precedent);
	if (result != 3)
	{
		//erreur
		return	result;
	}
	//création de la nouvelle cellule
	nouvelle = new CLOrdonnable(val,trouve);
	if (precedent==NULL)
	{
		//on est en tête de la liste
		this->tete = nouvelle;
	}
	else
	{
		precedent->suiv = nouvelle;
	}
	return	0;
}

int	ListeOrdonnee::supprimeElement(Ordonnable *val)
{
	CLOrdonnable	*precedent=NULL;
	CLOrdonnable	*trouve=NULL;
	int	result;

	result = chercheCOrdonnable(val,trouve,precedent);
	if (result != 1)
	{
		//erreur
		return	result;
	}
	if (precedent==NULL)
	{
		//on est en tête de la liste
		this->tete = trouve->suiv;
	}
	else
	{
		precedent->suiv = trouve->suiv;
	}
	delete(trouve);
	return	0;
}

int	ListeOrdonnee::getNombreElements()
{
	int nombre = 0;
	CLOrdonnable *parcours = this->tete;

	//Parcours total de la liste
	while (parcours!=NULL)
	{
		parcours = parcours->suiv;
		nombre++;
	}
	return 0;
}

void ListeOrdonnee::vide()
{
	CLOrdonnable	*temp;

	//parcours total de la liste
	while (this->tete!=NULL)
	{
		temp=this->tete;
		this->tete=temp->suiv;
		delete(temp);
	}
}

Conclusion :


Dans le même registre, je suis en train d'essayer de faire un arbre binaire de recherche, et je voudrais, autant que possible, équilibrer les branches à chaque ajout (pour optimiser le nombre maximal de noeuds à traverser lors d'une recherche) mais j'ai un peu de mal.

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.