英文:
Minium value of a stack in C
问题
我正在尝试实现一个用数组在C中实现的栈的最小值计算函数，只能使用push()和pop()函数。以下是我的代码（findMin()是最后一个函数）。
这个函数不起作用，如果我将5 3 5 5 5放入栈中，它会打印"最小值1"。我认为这是因为我找不到正确的基本条件。
void init(int S[]) {
S[0] = 0;
}
int push(int S[], int x) {
if (!fullStack(S)) {
S[0] = S[0] + 1;
S[S[0]] = x;
} else {
printf("栈已满\n");
}
}
int pop(int S[]) {
if (!emptyStack(S)) {
int x = S[S[0]];
S[0]--;
return x;
} else {
printf("栈为空\n");
return -1;
}
}
int emptyStack(int S[]) {
return S[0] == 0;
}
int fullStack(int S[]) {
return S[0] == SIZE;
}
int findMin(int S) {
if (emptyStack(S)) return -1;
else {
int x = pop(S);
int min = findMin(S);
if (min == -1 || x < min) {
push(S, x);
return x;
} else {
push(S, x);
return min;
}
}
}
这是修复后的代码，修复了查找最小值的问题。在递归中，我们需要保留栈的状态，因此在递归之前出栈，然后在递归之后入栈。此外，如果栈为空，我们应该返回一个特定的值（例如-1）来表示没有找到最小值。
英文:
i'm trying to implement a funcion who calculate the minium value of a stack in C implemented with an array, using only push() and pop() function.
here is my code: (findMin() is the last function).
The function doesn't work, if i put 5 3 5 5 5 in the stack, it prints "minium value 1". I think it's because i can't find a correct base condition
void init(int S[]){
S[0] = 0;
}
int push(int S[], int x) {
if(!fullStack(S)){
S[0] = S[0] + 1;
S[S[0]] = x;
}
else printf("stack full\n");
}
int pop(int S[]) {
if(!emptyStack(S)){
int x = S[S[0]];
S[0]--;
return x;
}
else {
printf("stack empty\n");
return -1;
}
}
int emptyStack(int S[]) {
return S[0] == 0;
}
int fullStack(int S[]) {
return S[0] == SIZE;
}
int findMin(int S[]){
if(emptyStack(S)) return ;
else{
int x = pop(S);
if(x < findMin(S)) return x;
else return findMin(S);
push(S, x);
}
}
答案1
得分: 1
有趣的逻辑...
根据我理解的，以下是你需要做的事情：
#define LARGE_NUMBER 1000; // 你可以查看 INT_MAX
int findMin(int S[]){
if(emptyStack(S)) return LARGE_NUMBER;
else{
int x = pop(S);
int y = findMin(S); // 将结果存储在单独的变量中以返回
if(x < y) return x;
else return y;
push(S, x); // 这是无法到达的代码，因此堆栈变为空
}
}
经过这些更改，当输入为 "5 3 5 5 5" 时，findMin() 返回 "3"。
英文:
Interesting logic...
By what i could understand, here is what you need to do,
#define LARGE_NUMBER 1000; //You could look into INT_MAX
int findMin(int S[]){
if(emptyStack(S)) return LARGE_NUMBER;
else{
int x = pop(S);
int y = findMin(S); // Store result in separate variable to return
if(x < y) return x;
else return y;
push(S, x); // This is unreachable code, so stack becomes empty
}
}
After these changes, findMin() returns "3" in your case when input is "5 3 5 5 5".
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论