C Typed Stack: реализация связанного списка - PullRequest
Новая
       11

C Typed Stack: реализация связанного списка

0 голосов
/ 28 сентября 2011

У меня готовится экзамен по информатике, и большая часть будет посвящена программированию в ANSI C. Я новичок в C, и в качестве обзора я попытался реализовать стек, используя связанный список.Мой код компилируется, но он не работает должным образом.

Я считаю, что с моей функцией push () произошла ошибка.Я предполагаю, что моя ссылка на стек не обновляется должным образом.

Я написал следующий код с нуля для изучения / практики.Буду очень признателен за любой совет, как исправить мой код или улучшить мой стиль программирования.

Спасибо, ребята!

stack.h 

#ifndef __STACK__
#define __STACK__

#include <stdlib.h>
#include "bool.h"

#define EMPTY -1

typedef struct Node {
    int index;
    enum { INT = 0, CHAR, STRING } type;
    union {
        int i;
        char c;
        char* s;
    } value;
    struct Node* prev;
} Node;

typedef Node* Stack;

Stack init();
void push(Stack stack, int type, void* value);
void pop(Stack stack, Node* node);
void empty(Stack stack);
Bool isempty(Stack stack);

#endif

stack.c 

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

Stack init() {
    Stack stack = (Node*) malloc(sizeof(Node));
    stack->index = EMPTY;
    stack->type = INT;
    stack->value.i = 0;
    stack->prev = 0;
    return stack;
}

void push(Stack stack, int type, void* value) {
    int length;
    Node* node = (Node*) malloc(sizeof(Node));
    node->index = stack->index + 1;
    node->type = type;
    switch(node->type) {
        case INT:
            node->value.i = *((int*) value);
        break;
        case CHAR:
            node->value.c =  *((char*) value);
        break;
        case STRING:
            length = strlen((char*) value) + 1;
            node->value.s = (char*) malloc(length * sizeof(char));
            strcpy(node->value.s, value);
        break;
    }       
    node->prev = stack;
    stack = node;
}

void pop(Stack stack, Node* node) {
    int length;
    Node* temp = stack;
    if (!isempty(stack)) {
        node->index = stack->index;
        node->type = stack->type;
        switch(stack->type) {
            case INT:
                node->value.i = stack->value.i;
            break;
            case CHAR:
                node->value.c = stack->value.c;
            break;
            case STRING:
                length = strlen(stack->value.s) + 1;
                node->value.s = (char*) malloc(length * sizeof(char));
                strcpy(node->value.s, stack->value.s);
                free(stack->value.s);
            break;
        }
        node->prev = 0;
        stack = stack->prev;
        free(temp); 
    } else {
        /*TODO: handle empty case */    
        puts("Stack empty!");
    }
}

void empty(Stack stack) {
    while (!isempty(stack)) {
        Node* temp = malloc(sizeof(Node));
        pop(stack, temp);
        free(temp);
    }
}

Bool isempty(Stack stack) {
    return stack->index == EMPTY ? TRUE : FALSE;
}

bool.h 

#ifndef __BOOL__
#define __BOOL__

typedef int Bool;

#define FALSE 0
#define TRUE 1

#endif

main.c 

#include <stdlib.h>
#include <stdio.h>
#include "stack.h"

int main() {
    Stack stack = init();
    Node* node = malloc(sizeof(Node));
    int i = 5;
    push(stack, 0, &i);
    pop(stack, node);
    printf("Node value: %d\n", node->value.i);
    free(node);
    empty(stack);
    puts("done.");
    return 0;
}

1 Ответ

1 голос
/ 28 сентября 2011

На самом деле вы не модифицируете стек.Вы должны использовать & stack для методов push, pop и empty.Они будут иметь следующую подпись: 

void push(Stack * stack, int type, void* value);
void pop(Stack * stack, Node* node);
void empty(Stack *stack);

и, конечно, использовать содержимое указателя внутри этих методов, например: 

void push(Stack * stack, int type, void* value) {
    int length;
    Node* node = (Node*) malloc(sizeof(Node));
    node->index = (*stack)->index + 1;
    node->type = type;
    switch(node->type) {
        case INT:
            node->value.i = *((int*) value);
        break;
        case CHAR:
            node->value.c =  *((char*) value);
        break;
        case STRING:
            length = strlen((char*) value) + 1;
            node->value.s = (char*) malloc(length * sizeof(char));
            strcpy(node->value.s, value);
        break;
    }
    node->prev = *stack;
    *stack = node;
}

void pop(Stack * stack, Node* node) {
    int length;
    Node* temp = *stack;
    if (!isempty(*stack)) {
        node->index = (*stack)->index;
        node->type = (*stack)->type;
        switch((*stack)->type) {
            case INT:
                node->value.i = (*stack)->value.i;
            break;
            case CHAR:
                node->value.c = (*stack)->value.c;
            break;
            case STRING:
                length = strlen((*stack)->value.s) + 1;
                node->value.s = (char*) malloc(length * sizeof(char));
                strcpy(node->value.s, (*stack)->value.s);
                free((*stack)->value.s);
            break;
        }
        node->prev = 0;
        *stack = (*stack)->prev;
        free(temp);
    } else {
        /*TODO: handle empty case */
        puts("Stack empty!");
    }
}

void empty(Stack *stack) {
    while (!isempty(*stack)) {
        Node* temp = malloc(sizeof(Node));
        pop(stack, temp);
        free(temp);
    }
}
...