通過使用結構

Question

排序兩個堆疊有3個棧 - A，B，C

堆棧A和B被排序（在堆棧的頂部的數目是最大的）。堆棧C是空的，只有5操作被允許：

推， 流行， 頂部， is_empty， 創建

我們需要寫接收棧A和B的功能，在移動所有的號碼堆棧A和B堆棧C和堆棧C必須被排序（最大的數字在最上面）。

我的算法：

Compare top of A with top of 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的底部（這個值必須先被推動）。如果a> b然後：彈出a，按c。

無論如何，你的代碼似乎並不很安全。看一看下面：

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

讓我們假設一個是空的，b是不是讓a.top等於-1，b.top是在範圍0到MAX_MEMBERS - 1.由於的一個堆棧不是空的條件是真的。 通過調用top（& a）執行以下代碼：

return 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? 
}