0

有 3 个堆栈 - A、B、C

堆栈 A 和 B 已排序（堆栈顶部的数字最大）。Stack C is Empty 只允许 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);
}
4

1 回答 1

0

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

要将所有元素以相反的顺序推送到 C 上，您需要 C 底部的最高元素（必须首先推送此值）。如果 a > b 则：弹出 a，按 c。

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

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

让我们假设 a 为空且 b 不是，因此 a.top 等于 -1 并且 b.top 在 0 到 MAX_MEMBERS - 1 的范围内。由于其中一个堆栈不为空，因此条件为真。通过调用 top(&a) 执行以下代码：

返回一个[-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?
}
于 2013-05-18T16:20:40.840 回答