Listes chainées...

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 972 fois - Téléchargée 38 fois

Contenu du snippet

//
// Exemple d'implémentation d'une liste simplement chaînée
//
// Ce prog. contient quelques fonctions élémentaires nécessaires à l'implémentation
// et au traitement d'une liste simplement chaînée contenant des entiers triés par ordre
// croissant.
//

Source / Exemple :


#include <iostream.h>
#include <stdlib.h>

struct NODE				
{					
	int data;
	NODE * next ;		
};

NODE* CreateList(NODE *);				
NODE* DeleteList(NODE *);				
NODE* InsertElement(NODE *, const int&, bool&);	
NODE* DeleteElement(NODE *, const int&, bool&);
NODE* ModifyElement(NODE *, const int&, const int&, bool&);
NODE* SearchElement(NODE *, const int&);
bool IsInList(NODE *, const int&);
int GetNumberOfElement(NODE *);
void PrintList(NODE *);

NODE* CreateList(NODE *head)
{
	return NULL;
}

NODE* DeleteList(NODE *head)
{
	NODE *cur;

	cur = head;

	while (cur != NULL)
	{
		cur = head->next;
		delete head;
		head = cur;
	}

	return NULL;
}

NODE* InsertElement(NODE *head, const int& value, bool& result)
{
	NODE *cur, *previous, *tmp;

	result = false;

	tmp = new NODE;
	if (tmp == NULL)
		return head;

	tmp->data = value;
	tmp->next = NULL;

	if (head == NULL)
	{
		tmp->next = head;
		head = tmp;
		result = true;
		return head;
	}

	if (value <= head->data)
	{
		tmp->next = head;
		head = tmp;
		result = true;
		return head;
	}

	cur = head;
	previous = NULL;
	while ((cur != NULL) && (cur->data < value))
	{
		previous = cur;
		cur = cur->next;
	}

	previous->next = tmp;
	tmp->next = cur;

	result = true;

	return head;
}
				

NODE* DeleteElement(NODE *head, const int& value, bool& result)
{
	NODE *cur, *previous;

	result = false;

	if (head == NULL)
		return head;
	
	if (value == head->data)
	{
		cur = head->next;
		delete head ;
		result = true;
		head = cur;
		return head;
	}

	cur = head;
	while ((cur != NULL) && (cur->data != value))
	{
		previous = cur;
		cur = cur->next;
	}
	
	if (cur == NULL)
		return head;

	previous->next = cur->next;

	delete cur;

	result = true;

	return head;
}

NODE* ModifyElement(NODE *head, const int& oldValue, const int& newValue, bool& result)
{
	NODE *cur;

	result = false;

	cur = head;

	while ((cur != NULL) && (cur->data != oldValue))
		cur = cur->next;

	if (cur == NULL)
		return head;

	cur->data = newValue;

	result = true;

	return head;
}

NODE* SearchElement(NODE *head, const int& value)
{
	NODE *cur;

	if (head == NULL)
		return head;

	cur = head;;
	while ((cur != NULL) && (cur->data != value))
		cur = cur->next;

	return cur;
}
				

bool IsInList(NODE *head, const int& value)
{
	NODE *cur;

	if (head == NULL)
		return false;

	cur = head;;
	while ((cur != NULL) && (cur->data != value))
		cur = cur->next;

	if (cur == NULL)
		return false;

	return true;
}

int GetEltNbr(NODE *head)
{
	NODE *cur;
	int nbr = 0;

	if (head == NULL)
		return 0;

	cur = head;
	while (cur != NULL) 
	{
		nbr++;
		cur = cur->next;
	}

	return nbr;
}

void PrintList(NODE *head)
{
	NODE *cur;

	if (head == NULL)
	{
		cout << "la liste est vide" << endl;
		return;
	}

	cur = head;
	while (cur != NULL) 
	{
		cout << cur->data << "\t";
		cur = cur->next;
	}
	
	cout << endl;

}

int main(int argc, char* argv[])
{
	int choice = 1;
	NODE *head;
	NODE *tmp;
	int val, val1;
	bool result;
	
	head = CreateList(head);

	cout << "Une liste d'entiers ordonnés par ordre croissant a été créée." << endl;
	
	while (choice != 0)
	{
		cout << endl
			 << "     ======================" << endl
		     << "     1: InsertElement() : Ajouter un élément à la liste" << endl
			 << "     2: DeleteElement() : Supprimer un élément de la liste" << endl
			 << "     3: SearchElement() : Rechercher une valeur dans la liste" << endl
			 << "     4: IsInList()      : Vérifier si une valeur est dans la liste" << endl
			 << "     5: ModifyElement() : Modifie une valeur dans la liste" << endl
			 << "     6: PrintList()     : Imprimer la liste" << endl
			 << "     7: GetEltNbr()     : Donner la taille de la liste" << endl
			 << "     ======================" << endl
			 << "     0: Quitter" << endl
			 << "     ======================" << endl
			 << endl
			 << "Votre choix : ";
		
		cin >> choice;
		cout << endl;

		switch(choice)
		{
		case 1 :
			cout << "Enter la valeur à ajouter : ";
			cin >> val;
			head = InsertElement(head, val, result);
			if (result == false)
			{
				cout << "Erreur lors de l'insertion de " << val << endl;
				head = DeleteList(head);
				exit(0);
			}
			else
				cout << "La valeur "<< val << " a été insérée dans la liste" << endl;
			break;
		
		case 2 :
			cout << "Enter la valeur à supprimer : ";
			cin >> val;
			head = DeleteElement(head, val, result);
			if (result == false)
				cout << "Erreur lors de la suppression de : " << val << endl;
			else
				cout << "La valeur "<< val << " a été supprimée de la liste" << endl;
			break;
		
		case 3 :
			cout << "Enter la valeur à rechercher : ";
			cin >> val;
			tmp = SearchElement(head, val);
			if (tmp == NULL)
				cout << val << "n'est pas dans la liste" << endl;
			else
				cout << "La valeur "<< val << "est dans la liste. Adresse : " << tmp << endl;
			break;

		case 4 :
			cout << "Enter la valeur à rechercher : ";
			cin >> val;
			if (IsInList(head, val))
				cout << val << " est dans la liste" << endl;
			else
				cout << val << " n'est pas dans la liste" << endl;
			break;

		case 5 :
			cout << "Enter l'ancienne valeur : ";
			cin >> val;
			cout <<endl << "Enter la nouvelle valeur : ";
			cin >> val1;
			head = ModifyElement(head, val, val1, result);
			if (result == false)
				cout << "Erreur lors de la modification de " << val << " en "<< val1 <<endl;
			else
				cout << "La valeur "<< val << " a été modifiée en " << val1 <<endl;

			break;

		case 6 :
			PrintList(head);
			break;

		case 7 :
			cout << "La liste contient " << GetEltNbr(head) << " éléments."<< endl;
			break;

		case 0 :
			break;
		}
	}

	head = DeleteList(head);
	cout << "La liste a été supprimée." << endl;

	return 0;
}

Conclusion :


Merci au revoir.....

A voir également

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.