c - 是否应该为此函数使用 Malloc 分配内存?这会导致分段错误吗?
问题描述
我写了这个伪代码,因为我想尝试构建一个我在更大程序中使用的基本计算器。如下:
对于每个令牌t
:
如果t
是运算符或左括号,则将其压入操作数堆栈。
Else ift
是右括号:重复弹出操作数堆栈,直到碰到左括号。对于找到的每个运算符:
- 弹出值堆栈两次以获取操作数。
- 对这些操作数执行操作。
- 将操作结果压入值堆栈。
Elset
表示一个数字。
转换t
为整数,并将其压入值堆栈。当你没有令牌时,重复弹出操作数堆栈直到它为空,像以前一样执行每个操作。此时值栈上应该有一个数字,这就是答案。
然而,当我编写代码时,它给了我一个分段错误。我知道这与内存有关,但我不确定如何修复它或者是否需要为此功能分配内存。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
不确定这是否写得正确或是否会引发错误?
int operandApplication(int a, int b, char op){
if (op == '+'){
return a + b;
}
else {
return a * b;
}
}
int popValStack(int valstack[], int *top){
int valdata = valstack[*top];
*top = *top - 1;
return valdata;
}
void pushValStack(int valstack[], int *top, int value){
*top = *top + 1;
valstack[*top] = value;
}
char *popOpStack (char *charstack[], int *top){
char *chardata = charstack[*top];
*top = *top -1;
return chardata;
}
void pushOpStack (char *charstack[], int *top, char *value){
*top = *top + 1;
charstack[*top] = value;
}
我是否需要使用 malloc 在以下主函数中分配内存?
int main(int argc, char *argv[]){
int i;
int valueStack[50];
int valcounter = 0;
int opcounter = 0;
int l;
int m;
char *opStack[50];
char *op;
for(i = 1; i < argc; i++){
我在这里使用了字符串比较,因为它看起来更容易,但不确定它是否有用。
char *t = argv[i];
int s1 = strcmp(t, "[");
int s2 = strcmp(t, "+");
int s3 = strcmp(t, "x");
int s4 = strcmp(t, "]");
if(s1 == 0 | s2 ==0 | s3 == 0){
pushOpStack(opStack, &opcounter, argv[i]);
}
else if(s4 == 0){
char *S = popOpStack(opStack, &opcounter);
while (*S!= '[') {
int a = popValStack(valueStack, &valcounter);
int b = popValStack(valueStack, &valcounter);
pushValStack (valueStack, &valcounter, operandApplication(a, b, *S));
}
}
else {
int x = atoi(t);
pushValStack(valueStack, &valcounter, x);
}
}
while (opcounter > 0){
op = popOpStack(opStack, &opcounter);
l = popValStack(valueStack, &valcounter);
m = popValStack(valueStack, &valcounter);
pushValStack (valueStack, &valcounter,
operandApplication(l, m, *op));
}
printf ("%d\n", valueStack[valcounter]);
}
解决方案
malloc
在这个程序中不需要写。int i
堆栈内存,像or之类的普通变量声明int valueStack[50]
,一直存在到其声明的函数退出。因此,您声明的所有变量都main
将一直存在,直到程序完成。
另一方面,如果您尝试像这样返回堆栈内存:
int *newStack() {
int stack[50];
return stack;
}
int *valueStack = newStack();
那将是一个问题,一旦返回,stack
指向的内存就会被释放。将指向可能被覆盖的已释放内存。newStack
vauleStack
经验法则是,如果你返回一个指针,它必须是malloc
'd。
我无法重现您的问题,但我可以看到它可能出错的地方。有几个地方你可以从你的堆栈中走出来。
因为valueStack
和opStack
是固定大小,当达到 49 导致(等待它)堆栈溢出时,pushValStack
两者popOpStack
都会离开堆栈的末尾。top
int valueStack[50];
int valcounter = 0;
for( int i = 0; i < 50; i++ ) {
pushValStack(valueStack, &valcounter, i);
}
(它是 49 而不是 50,因为top
在将值放入堆栈之前会增加。这会导致一个错误的错误,其中为了存储位置 0top
中的任何内容必须从 -1 开始。)
类似地,popValStack
并且popOpStack
可以从数组的后面走出来导致堆栈下溢。负索引在 C 中起作用;他们在指针之前读取内存,这是不好的。有趣的是,这并没有对我造成错误。YMMV。
发现这类错误的一种方法是输入一些assert
s 来检查你没有越界。断言是您假设为真的表达式。如果不是,则程序停止。
#include <stdio.h>
#include <assert.h>
// Here I put the stack size into a constant so it can be referenced by the asserts.
#define STACK_SIZE 50
int popValStack(int valstack[], int *top){
assert( *top >= 0 );
int valdata = valstack[*top];
*top = *top - 1;
return valdata;
}
void pushValStack(int valstack[], int *top, int value){
*top = *top + 1;
assert( *top < STACK_SIZE );
valstack[*top] = value;
}
int main(int argc, char *argv[]){
int valueStack[STACK_SIZE];
int valcounter = 0;
for( int i = 0; i < STACK_SIZE; i++ ) {
pushValStack(valueStack, &valcounter, 1);
}
}
然后,您将得到一个明显的错误,而不是一个神秘的段错误。
Assertion failed: (*top < STACK_SIZE), function pushValStack, file test.c, line 26.
断言可以方便地验证代码中的任何假设和边界。
更进一步,我们可以通过使用结构将与堆栈相关的所有变量收集到一个位置来改进堆栈的代码和完整性。
typedef struct {
int *stack;
size_t size;
size_t top;
} IntStack;
(我在size_t
这里使用而不是int
因为它保证足够大以容纳最大可能对象的大小,因此它适用于数组索引。)
然后 IntStack 可以作为一个单元传递。它知道它的大小和顶部的位置。
void IntStackPush( IntStack *stack, int value ) {
assert( stack->top < stack->size );
stack->stack[stack->top] = value;
stack->top += 1;
}
int IntStackPop( IntStack *stack ) {
assert( stack->top > 0 );
stack->top -= 1;
return stack->stack[stack->top];
}
#define STACK_SIZE 50
int main(){
int values[STACK_SIZE];
IntStack valueStack = { .stack = values, .size = STACK_SIZE, .top = 0 };
for( int i = 0; i < STACK_SIZE; i++ ) {
IntStackPush(&valueStack, i);
}
for( int i = 0; i < STACK_SIZE; i++ ) {
printf("%d\n", IntStackPop(&valueStack));
}
}
请注意,我们必须手动初始化可能容易出错的结构。相反,我们可以编写一个函数来为我们做这件事。因为我们现在从函数返回一个指针,所以我们需要malloc
.
IntStack *IntStackNew( size_t size ) {
// Allocate space for the struct.
IntStack *stack = malloc(sizeof(IntStack));
stack->top = 0;
stack->size = size;
// And allocate space for the stack.
stack->stack = malloc( size * sizeof(int) );
return stack;
}
由于我们在堆上分配内存,我们需要释放它。
void IntStackFree( IntStack *stack ) {
free(stack->stack);
free(stack);
}
现在堆栈可以在不了解其内容的情况下使用。
#define STACK_SIZE 50
int main(){
IntStack *valueStack = IntStackNew(STACK_SIZE);
for( int i = 0; i < STACK_SIZE; i++ ) {
IntStackPush(valueStack, i);
}
for( int i = 0; i < STACK_SIZE; i++ ) {
printf("%d\n", IntStackPop(valueStack));
}
IntStackFree(valueStack);
}
推荐阅读
- android - Cardboard-xr-plugin 导致 VR 环境在移动相机时卡顿
- ubuntu - 如何使用 Kotlin 的反射?
- angular - Angular 7:EventEmitter 对点击事件不起作用
- python - 排序外部多索引
- javascript - 减速器功能改变状态,但屏幕不重新渲染
- javascript - 我的功能没有识别正确的人
- python - 为什么我不能从我的 Django Paginator 中得到正确的结果
- javascript - 在 For 循环中创建 JavaScript 数组
- html - Gliderjs 单杠类
- python - 未找到 Seaborn 模块“histplot”