arrays - 在c中使用堆栈对int数组进行排序

Question

我正在尝试对一堆元素进行排序，但函数溢出了，我不知道为什么会这样。

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

#define type int   //type of element in the stack
#define  max 100

typedef struct {
    int top;
    type array[max];
} stack;

stack *initialize () {
    stack *s = malloc (sizeof (stack));
    s->top = 0;
    return s;
}

void push (stack *s, type x) {
    s->array[s->top++] = x;
}

type pop (stack *s) {
    return s->array[--s->top];
}

type isfull (stack *s) {
    return s->top >= max;
}

type isempty (stack *s) {
    return !s->top;
}

type peek (stack *s) {
    return s->array[s->top - 1];
}

void sortstack (stack *s) { //sorting the stack
    stack *temp = initialize();
    int x, flag;
    do {
        flag = 0;
        while (!isempty (s)) {
            x = pop (s);
            if (x > peek (s)) {
                push (temp, pop (s));
                push (s, x);
                flag = 1;
            } else push (temp, x);
        }
        while (!isempty (temp)) push (s, pop (temp));
    } while (flag);
}

int main() {
    stack *s = initialize();
    push (s, 2);
    push (s, 4);
    push (s, 4);
    push (s, 7);
    push (s, 9);
    push (s, 18);
    sortstack (s);
    while (!isempty (s)) printf ("%d  ", pop (s));
    
    return 0;
}

Answer 1

代码中存在多个问题:

• 在 if (x > peek (s)) 中，您应该测试堆栈 s 是否为空，以避免访问 s 的未定义行为->数组[-1]。

• x 应该定义为 type 类型。

• 在离开函数 sortstack 之前，您应该释放临时堆栈 temp。

• 你应该使用 typedef int type; 而不是 #define type int

• 用大写字母定义诸如 max 之类的宏是惯用的，建议使用更具描述性的名称。

• 添加 assert 语句有助于捕获意外错误情况。

修改后的版本:

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

typedef int type;   //type of element in the stack
#define STACKSIZE 100

typedef struct {
    int top;
    type array[STACKSIZE];
} stack;

stack *initialize(void) {
    stack *s = malloc(sizeof(stack));
    assert(s != NULL);
    s->top = 0;
    return s;
}

void discard(stack *s) {
    free(s);
}

void push(stack *s, type x) {
    assert(s->top < STACKSIZE);
    s->array[s->top++] = x;
}

type pop(stack *s) {
    assert(s->top > 0);
    return s->array[--s->top];
}

type isfull(stack *s) {
    return s->top >= max;
}

type isempty(stack *s) {
    return !s->top;
}

type peek(stack *s) {
    assert(s->top > 0);
    return s->array[s->top - 1];
}

void sortstack(stack *s) { //sorting the stack
    stack *temp = initialize();
    int flag;
    do {
        flag = 0;
        while (!isempty(s)) {
            type x = pop(s);
            if (!isempty(s) && x > peek(s)) {
                push(temp, pop(s));
                push(s, x);
                flag = 1;
            } else {
                push(temp, x);
            }
        }
        while (!isempty(temp)) {
            push(s, pop(temp));
        }
    } while (flag);
    discard(temp);
}

int main() {
    stack *s = initialize();
    push(s, 2);
    push(s, 4);
    push(s, 4);
    push(s, 7);
    push(s, 9);
    push(s, 18);
    sortstack(s);
    while (!isempty(s)) {
        printf("%d  ", pop(s));
    }
    printf("\n");
    discard(s);
    
    return 0;
}