1. Accueil
  2. C / C++ / C++.NET
  3. Sources C / C++ / C++.NET
  4. Sources Astuces
  5. Implémentation d'une structure de donnée dynamique et générique de type "vector" en c

Implémentation d'une structure de donnée dynamique et générique de type "vector" en c

Soyez le premier à donner votre avis sur cette source.

Vue 5 881 fois - Téléchargée 228 fois

Télécharger le projet
Commenter

Description

Alors voila, je croi que tout est dans le titre.
J'ai fais ca un peu a la va-vite car j'en avais besoin tout de suite ;-)
J'ai mis une petite batterie de test avec pour que vous compreniez comment ca marche.
ATTENTION !!!! : Aucune gestion d'erreur n'est effectuée, a utiliser en faisant trés attention avec les MACROS.
Je vous aurais prévenu ...

Source / Exemple : 


#ifndef SVECTOR_H
#define SVECTOR_H

#ifdef _WIN32

#include <windows.h>

#define SMalloc(size)	VirtualAlloc(NULL,size,MEM_COMMIT | MEM_RESERVE | MEM_TOP_DOWN,PAGE_READWRITE)
#define SFree(ptr)	VirtualFree(ptr,0,MEM_RELEASE)
#define SMemCpy		CopyMemory

#else

#include <stdlib.h>
#include <string.h>

#define SMalloc		malloc
#define SFree		free
#define SMemCpy		memcpy

#endif

// Peut etre modifier selon les besoins :
#define REALLOC_SIZE 100

// Declare le SVector :
#define declareSVector(type,name) \
	struct SVector##name \
	{ \
		type *elements; \
		unsigned int nbElements; \
		unsigned int allocatedSize; \
	} *name

// Creation de SVector :
#define createSVector1(type,name) \
	do \
	{ \
		name = SMalloc(sizeof(struct SVector##name)); \
		name->nbElements = 0; \
		name->allocatedSize = REALLOC_SIZE; \
		name->elements = SMalloc(REALLOC_SIZE * sizeof(type)); \
	} while (0)

// Creation de SVector en precisant la taille alouee en argument :
#define createSVector2(type,name,size) \
	do \
	{ \
		name = SMalloc(sizeof(struct SVector##name)); \
		name->nbElements = 0; \
		name->allocatedSize = size; \
		name->elements = SMalloc((size) * sizeof(type)); \
	} while (0)

// Destruction de SVector :
#define destroySVector(name) \
	do \
	{ \
		SFree(name->elements); \
		SFree(name); \
	} while (0)

// Acces a un element :
#define elementAt(name,pos)	(name->elements[pos])

// Nombre d'elements de SVector :
#define sizeOf(name)		(name->nbElements)

// Ajouter un element :
#ifdef _WIN32

#define addElement(type,name,element) \
	do \
	{ \
		if (name->allocatedSize == name->nbElements) \
		{ \
			type *tmp; \
			name->allocatedSize += REALLOC_SIZE; \
			tmp = SMalloc(name->allocatedSize * sizeof(type)); \
			SMemCpy(tmp,name->elements,name->nbElements * sizeof(type)); \
			SFree(name->elements); \
			name->elements = tmp; \
			name->elements[name->nbElements++] = element; \
		} \
		else \
			name->elements[name->nbElements++] = element; \
	} while (0)

#else

#define addElement(type,name,element) \
	do \
	{ \
		if (name->allocatedSize == name->nbElements) \
		{ \
			name->allocatedSize += REALLOC_SIZE; \
			name->elements = realloc(name->elements,name->allocatedSize * sizeof(type)); \
			name->elements[name->nbElements++] = element; \
		} \
		else \
			name->elements[name->nbElements++] = element; \
	} while (0)

#endif

// Supprime un element a la position pos, il est retourne dans ret (qui doit etre de type "type *")
// ret peut etre NULL
// ne fait rien si pos trop grand :
#define removeAt(name,pos,ret) \
	do \
	{ \
		int i; \
		if (pos >= name->nbElements) \
			break; \
		if ((ret) != 0) \


    			
  • (ret) = name->elements[pos]; \

		for (i = pos;i < name->nbElements - 1;i++) \
			name->elements[i] = name->elements[i + 1]; \
		name->nbElements--; \
	} while (0)

// Supprimer un element, il est retourner dans ret (qui doit etre de type "type *")
// ret peut etre NULL
// La fonction funcCompare doit etre du type "int (*func)(type element1,type element2)"
// et doit retourner 0 si element1 == element2 et != 0 sinon
// ne fait rien si element pas trouve :
#define removeElement(name,funcCompare,element,ret) \
	do \
	{ \
		int i,j; \
		for (i = 0;i < name->nbElements;i++) \
			if (!funcCompare(element,name->elements[i])) \
				break; \
		if (i == name->nbElements) \
			break; \
		if ((ret) != 0) \


    			
  • (ret) = name->elements[i]; \

		for (j = i;j < name->nbElements - 1;j++) \
			name->elements[j] = name->elements[j + 1]; \
		name->nbElements--; \
	} while (0)

// Trouve un element dans SVector et met sa position dans ret qui doit etre de type "int *"
// La fonction funcCompare est la meme que pour "removeElement"
// ret sera -1 si element pas trouve :
#define findElement(name,funcCompare,element,ret) \
	do \
	{ \
		int i; \
		for (i = 0;i < name->nbElements;i++) \
			if (!funcCompare(element,name->elements[i])) \
				break; \
		if (i == name->nbElements) \
		{ \


    			
  • (ret) = -1; \

			break; \
		} \


    		
  • (ret) = i; \

	} while (0)

// Trie le SVector avec l'algo de tri a bulle
// La fonction funcCompare doit etre du type "int (*func)(type element1,type element2)"
// et doit retourner val < 0 si element1 < element2, val > 0 si element1 > element2
// val = 0 si element1 == element2 :
#define sort(type,name,funcCompare) \
	do \
	{ \
		int size,i,fini; \
		type tmp; \
		size = name->nbElements; \
		do \
		{ \
			fini = 1; \
			for (i = 0;i < size - 1;i++) \
				if (funcCompare(name->elements[i],name->elements[i + 1]) > 0) \
				{ \
					tmp = name->elements[i]; \
					name->elements[i] = name->elements[i + 1]; \
					name->elements[i + 1] = tmp; \
					fini = 0; \
				} \
			size--; \
		} while (!fini); \
	} while (0)

#endif

Conclusion :


Bon beh si vous avez des suggestions, n'hésitez pas ...
Merci de me prévenir si vous constatez un bug
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Signaler
Messages postés
178
Date d'inscription
mardi 16 août 2005
Statut
Membre
Dernière intervention
25 août 2010
 1
pour le tri, pourquoi pas faire un qsort tout simple...qui sera autrement plus performant..

qsort(name->elements, name->nbElements, sizeof(type), funcCompare);

Sinon, l'utilisation de telles macros génère beaucoup trop de code, et détourne l'utilité des macro. Les macro sont là pour aider à coder, pas pour essayer de faire ce que le langage ne sait pas ou ne peut faire. Il vaut mieux faire un préprocesseur sans ce cas...

De plus, il est possible d'avoir une approche générique sans passer par des macros...
Signaler
Messages postés
106
Date d'inscription
mardi 11 novembre 2003
Statut
Membre
Dernière intervention
11 février 2008
Salut

Pour le realloc dans la version non windows j'y ai pensé et je viens de réaliser que se serait facile a faire donc je le modifirais.
Pour le do{...] while (0) je sais pas pourquoi je l'ai pas mis mais je le rajouterais si sa peut te fare plaisir ;-)
Je prevoirais le cas de removeAt(monvector,2,NULL) c'est une bonne idée.
Le createSVector(type,name,size) j'y ai meme pas pensé je le rajouterais aussi.
Quant au tri fusion, pour l'instant je vois pas trop comment faire, mais je vais y réfléchir ...

bref il y a du travail lol :-)

Merci beaucoup pour ton commentaire constructif, ca fait plaisir.

a bientot
Signaler
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
 5
salut!

tu devrais utiliser realloc plutôt que malloc pour ajouter un élément dans addElement pour la version non windows ?

pourquoi tu mets bien le do { ... } while (0) sauf dans createSVector et destroySVector ?

souvent on propose de retourner une valeur dans un pointeur, ou non si le paramètre est NULL par exemple:
removeAt(monvector,2,NULL)
ça pourrait être intéressant de prévoir ça

pourquoi tu utilises le tri à bulle et pas le quicksort, ou le tri fusion ?

pourquoi pas #define createSVector(type,name,size) ???

a+
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.