使用structs对两个堆栈进行排序

Question

有3个堆栈-A、B、C

堆栈A和B被排序（堆栈顶部的数字最大）。堆栈C为空，仅允许5次操作：

推，弹出，顶，is_empty，创建

我们需要编写一个函数来接收堆栈A和B，将堆栈A和B中的所有数字移动到堆栈C，堆栈C必须排序（最大数字在顶部）。

我有算法：

比较A的顶部和B的顶部

Pop the least element and push to stack C

Repeat step 2 until any of the stack ( A or B) becomes empty

Move remaining elements from non-empty stack to C. Now you have all the elements in C  but in ascending order. (That is least element at top).

Move all the elements from C to A. (Contents in A are in descending order)

Move all the elements from A to B. (Contents in B are in ascending order)

Move all the elements from B to C.

我开始写代码，但有错误，我不知道为什么！

代码：

#include <stdio.h> 
#include <stdlib.h>
#include <conio.h>
#define MAX_MEMBERS 10
typedef struct
{
    int num;
}ITEM;

typedef struct
{
    ITEM a[MAX_MEMBERS];
    int top;
}STACK;

void create_stack(STACK *s)
{
    s->top=-1;
}

int is_empty(STACK *s)
{
    return s->top==-1;
}

int is_full(STACK *s)
{
    return s->top==MAX_MEMBERS-1;
}

ITEM pop(STACK *s)
{
    return s->a[s->top--];
}

void (STACK *s,ITEM *item)
{
    s->a[++s->top]=*item;
}

ITEM top(STACK *s)
{
    return s->a[s->top];
}

void sort (STACK *a,STACK *b,STACK *c)
{
    while(!is_empty(&a)||!is_empty(&b))
        if(top(&a)>top(&b))
            push(&c,pop(&b));

    if(!is_empty(&a))
    {
        while(!is_empty(&a))
            push(&c,pop(&a));
    }

    else
    {
        while(!is_empty(&b))
            push(&c,pop(&b));
    }

    while(!is_empty(&c))
        push(&a,pop(&c));

    while(!is_empty(&a))
        push(&b,pop(&a));

    while(!is_empty(&b))
        push(&c,pop(&b));

}

void main(void)
{
    STACK a,b,c;
    create_stack(&a);
    create_stack(&b);
    create_stack(&c);
    sort(&a,&b,&c);
}

Answer 1

您应该弹出最高的元素并将其推到C。

要将所有元素按相反的顺序推送到C上，您需要C底部的最高元素（必须首先推送此值）。如果一个

无论如何，你的代码似乎不是很安全。请看以下内容：

while(!is_empty(&a)||!is_empty(&b))
    if(top(&a)>top(&b))

假设a是空的，b不是空的，因此a.top等于-1，b.top在0到MAX_成员-1的范围内。由于其中一个堆栈不是空的，因此该条件为真。通过呼叫top(

返回一个[-1]//错误：索引超出范围

This is how your code is resolved.
is_empty(&a) returns true
!is_empty(&a) returns false
(false || true) returns true

while(false || true)
    if( top(&a) > top(&b) )

无论如何，我怀疑你的代码是否能编译。

void (STACK *s,ITEM *item)
{
    s->a[++s->top]=*item;
}

这应该是：

void push(STACK *s,ITEM *item)
{
    s->a[++s->top]=*item;
}

同时考虑：

void main(void)
{
    STACK a,b,c;
    create_stack(&a); //stack a is created, contains no elements
    create_stack(&b); //stack b is created, contains no elements
    create_stack(&c); //stack c is created, contains no elements
    sort(&a,&b,&c); //sort which elements of the stack?
}