#include <stdio.h> #include <stdlib.h> void check(char *message, int success) { printf("%s %s\n", success ? "pass" : "FAIL", message); } /* * array fixed stack. create an array of length one greater than the maximum * stack depth, and call aInit on it to set it up. */ void aInit(int *stack) { stack[0] = 0; } void aPush(int *stack, int value) { stack[++stack[0]] = value; } int aPeek(int *stack) { if(stack[0] == 0) { return 0; } return stack[stack[0]]; } int aPop(int *stack) { if(stack[0] == 0) { return 0; } return stack[stack[0]--]; } int aSize(int *stack) { return stack[0]; } void aPrint(int *stack) { int i; /* print the stack from top to bottom */ for(i = stack[0]; i > 0; i--) { printf("%d ", stack[i]); } printf("\n"); } void test_a() { int stack[10]; aInit(stack); check("a size", aSize(stack) == 0); aPush(stack, 1); aPush(stack, 2); check("a size", aSize(stack) == 2); check("a peek", aPeek(stack) == 2); check("a peek", aPeek(stack) == 2); check("a pop", aPop(stack) == 2); check("a size", aSize(stack) == 1); aPush(stack, 3); check("a size", aSize(stack) == 2); check("a peek", aPeek(stack) == 3); } /* * struct fixed stack */ struct sStack { int size; int data[10]; }; void sInit(struct sStack *stack) { stack->size = 0; } int sSize(struct sStack *stack) { return stack->size; } void sPush(struct sStack *stack, int value) { stack->data[stack->size] = value; stack->size += 1; } int sPeek(struct sStack *stack) { if(stack->size == 0) { return 0; } return stack->data[stack->size - 1]; } int sPop(struct sStack *stack) { if(stack->size == 0) { return 0; } stack->size -= 1; return stack->data[stack->size]; } void sPrint(struct sStack *stack) { int i; /* print the stack from top to bottom */ for(i = stack->size; i > 0; i--) { printf("%d ", stack->data[i - 1]); } printf("\n"); } void test_s() { struct sStack stack; sInit(&stack); check("s size", sSize(&stack) == 0); sPush(&stack, 1); sPush(&stack, 2); check("s size", sSize(&stack) == 2); check("s peek", sPeek(&stack) == 2); check("s peek", sPeek(&stack) == 2); check("s pop", sPop(&stack) == 2); check("s size", sSize(&stack) == 1); sPush(&stack, 3); check("s size", sSize(&stack) == 2); check("s peek", sPeek(&stack) == 3); } /* * linked dynamic stack */ struct lNode { struct lNode *next; int data; }; struct lStack { struct lNode *head; }; void lInit(struct lStack *stack) { stack->head = NULL; } int lSize(struct lStack *stack) { int size = 0; struct lNode *i; i = stack->head; while(i != NULL) { size += 1; i = i->next; } return size; } void lPush(struct lStack *stack, int value) { struct lNode *head; head = (struct lNode*)calloc(1, sizeof(struct lNode)); head->data = value; head->next = stack->head; stack->head = head; } int lPeek(struct lStack *stack) { if(stack->head == NULL) { return 0; } return stack->head->data; } int lPop(struct lStack *stack) { struct lNode *head; int out; head = stack->head; if(head == NULL) { return 0; } stack->head = head->next; out = head->data; free(head); return out; } void lPrint(struct lStack *stack) { struct lNode *i; for(i = stack->head; i != NULL; i = i->next) { printf("%d ", i->data); } printf("\n"); } void lDestroy(struct lStack *stack) { struct lNode *head; struct lNode *next; head = stack->head; while(head != NULL) { next = head->next; free(head); head = next; } stack->head = NULL; } void test_l() { struct lStack stack; lInit(&stack); check("l size", lSize(&stack) == 0); lPush(&stack, 1); lPush(&stack, 2); check("l size", lSize(&stack) == 2); check("l peek", lPeek(&stack) == 2); check("l peek", lPeek(&stack) == 2); check("l pop", lPop(&stack) == 2); check("l size", lSize(&stack) == 1); lPush(&stack, 3); check("l size", lSize(&stack) == 2); check("l peek", lPeek(&stack) == 3); lDestroy(&stack); } int main() { test_a(); test_s(); test_l(); return 0; }
I hope the code is clean and clear, but there is a good chance that is is not.
No comments:
Post a Comment