使用栈在C语言中对整型数组进行排序

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;
}

- Anas Mostafa

---

在你的内部循环中，当你说if (x>peek(s))时，你不知道s上是否有任何项，因为你刚刚从s中弹出了一个项。将其更改为if (!isempty(s) && x > peek(s))。（你可以在你的pop和peek函数中包含<assert.h>和assert(s->top > 0)来捕获这种编程错误。另外，你的变量x应该是type类型的。） - M Oehm

Answer 1

这段代码存在多个问题：

• 在 if (x > peek(s)) 中，应该测试栈 s 是否为空，以避免访问 s->array[-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;
}

- chqrlie