Création d'une pile de chaînes dans C

Question

Je veux avoir une pile qui accepte des chaînes. Je veux être capable de pousser et d'enlever les cordes, ainsi que d'effacer toute la pile. Je pense que C++ a quelques méthodes pour cela. Qu'en est-il de C?

Answer 1

Voir Wikipedia's article about stacks.

Answer 2

Essayez GNU Obstacks.

de Wikipédia:

Dans le langage de programmation C, obstack est une extension GNU-gestion de la mémoire à la bibliothèque standard C. Un "obstack" est une "pile" d '"objets" (éléments de données) qui est gérée dynamiquement.

Exemple de code

de Wikipedia:

char *x; 
void *(*funcp)(); 

x = (char *) obstack_alloc(obptr, size); /* Use the macro. */ 
x = (char *) (obstack_alloc) (obptr, size); /* Call the function. */ 
funcp = obstack_alloc; /* Take the address of the function. */ 

OMI ce qui fait Obstacks spécial: Il n'a pas besoin malloc() ni free(), mais la mémoire peut encore être attribuée «dynamique». C'est comme alloca() sur les stéroïdes. Il est également disponible sur de nombreuses plateformes, puisqu'il fait partie de la bibliothèque GNU C. Surtout sur les systèmes embarqués, il peut être plus logique d'utiliser Obstacks au lieu de malloc().

Answer 3

Exemple rapide et sale non testé. Utilise une structure de liste à lien unique; les éléments sont poussés sur et sortis de la tête de la liste.

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

/** 
* Type for individual stack entry 
*/ 
struct stack_entry { 
    char *data; 
    struct stack_entry *next; 
} 

/** 
* Type for stack instance 
*/ 
struct stack_t 
{ 
    struct stack_entry *head; 
    size_t stackSize; // not strictly necessary, but 
        // useful for logging 
} 

/** 
* Create a new stack instance 
*/ 
struct stack_t *newStack(void) 
{ 
    struct stack_t *stack = malloc(sizeof *stack); 
    if (stack) 
    { 
    stack->head = NULL; 
    stack->stackSize = 0; 
    } 
    return stack; 
} 

/** 
* Make a copy of the string to be stored (assumes 
* strdup() or similar functionality is not 
* available 
*/ 
char *copyString(char *str) 
{ 
    char *tmp = malloc(strlen(str) + 1); 
    if (tmp) 
    strcpy(tmp, str); 
    return tmp; 
} 

/** 
* Push a value onto the stack 
*/ 
void push(struct stack_t *theStack, char *value) 
{ 
    struct stack_entry *entry = malloc(sizeof *entry); 
    if (entry) 
    { 
    entry->data = copyString(value); 
    entry->next = theStack->head; 
    theStack->head = entry; 
    theStack->stackSize++; 
    } 
    else 
    { 
    // handle error here 
    } 
} 

/** 
* Get the value at the top of the stack 
*/ 
char *top(struct stack_t *theStack) 
{ 
    if (theStack && theStack->head) 
    return theStack->head->data; 
    else 
    return NULL; 
} 

/** 
* Pop the top element from the stack; this deletes both 
* the stack entry and the string it points to 
*/ 
void pop(struct stack_t *theStack) 
{ 
    if (theStack->head != NULL) 
    { 
    struct stack_entry *tmp = theStack->head; 
    theStack->head = theStack->head->next; 
    free(tmp->data); 
    free(tmp); 
    theStack->stackSize--; 
    } 
} 

/** 
* Clear all elements from the stack 
*/ 
void clear (struct stack_t *theStack) 
{ 
    while (theStack->head != NULL) 
    pop(theStack); 
} 

/** 
* Destroy a stack instance 
*/ 
void destroyStack(struct stack_t **theStack) 
{ 
    clear(*theStack); 
    free(*theStack); 
    *theStack = NULL; 
} 

Modifier

Il serait utile d'avoir un exemple de comment l'utiliser:

int main(void) 
{ 
    struct stack_t *theStack = newStack(); 
    char *data; 

    push(theStack, "foo"); 
    push(theStack, "bar"); 
    ... 
    data = top(theStack); 
    pop(theStack); 
    ... 
    clear(theStack); 
    destroyStack(&theStack); 
    ... 
} 

Vous pouvez déclarer des piles comme des variables automatiques, plutôt que d'utiliser newStack() et destroyStack(), vous devez juste vous assurer qu'ils sont initialisés correctement, comme dans

int main(void) 
{ 
    struct stack_t myStack = {NULL, 0}; 
    push (&myStack, "this is a test"); 
    push (&myStack, "this is another test"); 
    ... 
    clear(&myStack); 
} 

J'ai juste l'habitude de créer des pseudo constructeurs/destructeurs pour tout.