Explication du fonctionnement des piles dans C

Question

Je veux juste une explication simple du processus de liaison lorsque je pousse des données sur une pile. Je sais comment utiliser le code de mon livre, mais je ne suis pas sûr de comprendre le fonctionnement du processus lorsque vous déplacez le lien de la pile de l'un à l'autre.

Pour piles comme:

typedef struct node 
{ 
    void dataptr; 
    struct node* link; 
}STRUCT_NODE; 

typedef struct 
{ 
    int count; 
    STACK_NODE* top; 
}STACK; 

Comment changer le lien pour pointer vers les nouvelles données poussé sur la pile. Aussi je ne sais pas

Answer 1

Stacks peut être mis en œuvre de diverses manières, mais étant donné la façon dont vous formulez votre question je suppose que votre pile est juste une liste chaînée, quelque chose comme

head 
↓ 
A → B → C → D → 0 

« lorsque vous vous déplacez le lien de la tête de la pile d'un à l'autre », l'image change juste à:

head 
    ↓ 
A → B → C → D → 0 

Bien sûr, A est pas accessible plus dans ce graphique, vous feriez mieux d'avoir un autre pointeur vers elle quelque part (que ce soit seulement pour en disposer), mais c'est l'essentiel de la façon dont la pile est éclatée (par m aking head = head->next si chaque nœud de la pile est un struct node avec un champ next qui est un struct node*, et bien sûr head est également un struct node*). C'est pour sortir quelque chose de la pile (et vous devriez libérer la mémoire utilisée par A dans ce cas). Dans les étapes détaillées, ce serait:

1/Sauvegarde de l'ancienne tête.

 head 
     ↓ 
old → A → B → C → D → 0 

2/Réglage de la tête.

  head 
      ↓ 
old → A → B → C → D → 0 

3/retour de la vieille tête (pointé par old).

Si au contraire, vous parlez de pousser quelque chose sur la pile, c'est une opération qui consiste à:

1/Création d'un nouvel élément.

head 
    ↓ 
Z A → B → C → D → 0 

2/pointant vers la tête en cours

head 
    ↓ 
Z → A → B → C → D → 0 

3/Réglage de la tête pour pointer sur lui.

head 
↓ 
Z → A → B → C → D → 0 

Answer 2

Supposons que vous ayez du STACK appelé my_stack, et un STACK_NODE appelé my_node.Pour ajouter my_node à my_stack, faites ceci:

my_node.link = my_stack.top; 
my_stack.top = &my_node; 
my_stack.count = my_stack.count + 1; 

Answer 3

Compte tenu de vos structures de données représentant un noeud sur la pile et la pile elle-même:

typedef struct node { 
    void  *dataptr; 
    struct node *link; 
} NODE; 

typedef struct { 
    int count; 
    NODE *top; 
} STACK; 

vous initialiser une pile comme suit:

STACK myStack; 
myStack.count = 0; 
myStack.top = NULL; 

Cela vous donne essentiellement une pile vide. Je vais utiliser top pour décider si la pile est vide - vous pouvez utiliser count ou top (comme 0 ou NULL respectivement) pour faire ce travail, mais c'est une bonne idée d'en choisir une et de s'en tenir au cas où vous écrivez un code bogué à l'avenir où le compte mis en cache et le nombre réel de sortir de l'étape :-)

Pour pousser un nœud sur la pile, il est une simple opération de:

• attribuer le nouveau nœud et définir la charge utile (1).
• pointez le lien du nouveau noeud vers la tête actuelle.
• pointez la tête vers ce nouveau noeud (3).
• incrémenter le compte (4).

Le code suivant montre comment vous pouvez le faire:

/* 1 */ NODE *newNode = malloc (sizeof (NODE)); // should check for failure. 
     newNode->dataptr = NULL; 
/* 2 */ newNode->link = myStack.top; 
/* 3 */ myStack.top = newNode; 
/* 4 */ myStack.count++; 

Cela va pousser soit sur une pile vide ou un peuplé. Le cas de bordure d'une pile vide affiche newNode.link défini sur NULL, puis myStack.top sur newNode, ce qui correspond au comportement correct.

pour faire apparaître un noeud de la pile:

• enregistrer la tête de courant (1).
• Si la tête actuelle n'est pas NULL, avancez la tête vers son lien (et décrémentez le nombre).
• retourne la tête actuelle enregistrée (3).

qui traduit en code, est la suivante:

/* 1 */ NODE *popNode = myStack.top; 
/* 2 */ if (myStack.top != NULL) { 
      myStack.top = myStack.top->link; 
      myStack.count--; 
     } 
/* 3 */ return popNode; 

Cela renvoie soit l'adresse du noeud sauté, ou NULL si la pile est vide.

L'ensemble des opérations peut être encapsulé comme suit. Espérons que les commentaires le rendront explicite en conjonction avec les commentaires ci-dessus, mais n'hésitez pas à soulever des préoccupations et je vais les aborder avec une modification.

---

// Error codes (probably should be enums). 

#define STACK_ERR_OKAY  0 
#define STACK_ERR_NOTEMPTY 1 
#define STACK_ERR_NOPAYLOAD 2 
#define STACK_ERR_NOMEMORY 3 

// Structures. 

typedef struct sNode { 
    void   *data; // Payload pointer. 
    struct sNode *next; // Link to next node. 
} tNode; 

typedef struct { 
    int   count; // Count for fast sizing. 
    NODE   *top; // First node. 
} tStack; 

// Make a new stack returning its pointer or NULL on failure. 

tStack *stackNew (void) { 
    tStack stack = malloc (sizeof (tStack)); 
    if (stack != NULL) { 
     stack->count = 0; 
     stack->top = NULL; 
    } 
    return stack; 
} 

// Delete a current stack, must be empty first. 

int stackDel (tStack *stack) { 
    if (stack->top != NULL) 
     return STACK_ERR_NOT_EMPTY; 
    free (stack); 
    return STACK_ERR_OK; 
} 

// Push a pointer payload (no NULLs allowed) onto the stack. 

int stackPush (tStack *stack, void *payload) { 
    if (payload == NULL) 
     return STACK_ERR_NOPAYLOAD; 
    tNode *node = malloc (sizeof (tNode)); 
    if (node == NULL) 
     return STACK_ERR_NOMEMORY; 
    node->data = payload; 
    node->next = stack->top; 
    stack->top = node; 
    stack->count++; 
    return STACK_ERR_OK; 
} 

// Pop a pointer payload from the stack. Returns NULL if stack was empty. 

int stackPop (tStack *stack) { 
    tNode *node = stack->top; 
    if (node == NULL) { 
     return NULL; 
    stack->top = node->next; 
    stack->count--; 
    return node->data; 
} 

// Get stack size. 

int stackSize (tStack *stack) { 
    return stack->count; 
} 

La raison pour laquelle j'ai insisté pour qu'une pile doit être vide avant la suppression est parce que le code ne sait pas avec certitude ce que la charge utile est.Il pourrait être un simple pointeur à un bloc de mémoire (peu profonde) dans ce cas, vous pouvez simplement utiliser:

void stackDel (tStack *stack) { 
    tNode *node = stackPop (stack); 
    while (node != NULL) { 
     free (node); 
     node = stackPop (stack); 
    } 
    free (stack); 
} 

mais, si elle est un pointeur vers mémoire contenant d'autres pointeurs vers la mémoire, il est plus difficile de libérer automatiquement le mémoire il références (il serait probablement mieux fait comme un rappel à l'appelant de l'API car ce serait la seule bête qui savait avec certitude comment libérer correctement la mémoire). Beaucoup plus simple d'en faire un pré-requis sur l'appelant à l'avant.