我正在尝试使用动态内存和指针算术来构建堆栈来遍历堆栈。我遇到了似乎无法解决的错误。错误根据我运行程序的方式而有所不同。 1) 如果我只使用参数运行，我会在第 112 行的 fClose 之前得到一个 segFault，并且没有 pFile 不为 NULL。 2)如果我运行时将少于 20 个项目送入堆栈，则一切正常，只有当我第二次重新分配堆栈时，我才开始出现错误 3)如果我使用超过 20 个元素和 valgrind 运行它，它会一直运行，但会出现一些读/写错误，主要是在 PushStack 中。
我一直以为我已经很接近了，但此时我更加迷失了。我确信这可能不是堆栈的最佳实现，但我仍然无法弄清楚为什么它有时不起作用。
源代码:
/**********************************************************************
CS2123 assignment2_stacks.c by Kyle Widmann
Purpose:
This program takes a file supplied by user and reads each line, which is expected to be an int. A stack is implemented using dynamic memory. If the int is -99999 the stack is popped. Otherwise the number is pushed onto the stack. The stack increased by chunks of 10, but never decreases.
Command Parameters:
assignment2 -i datafile.txt
Input:
numbers supplied by datafile.txt from Command Line
-The file is assumed to be nothing but integers.
-All integers >-99999 will be pushed onto stack
-Reading -99999 will cause the stack to pop
Results:
Whenever the stack is popped the program prints elements remaning after the pop, and what integer was popped. The program also prints whenver the stack size grows, as well as what the old and new stack sizes are.
Returns:
0 - normal
Notes:
**********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Typedef for our stack
typedef struct stack{
int iInfo;
int iCount;
int iStackSize;
}STACK;
//Define our definitions for True, False and Pop
#define TRUE 0
#define FALSE -1
#define POP -99999
//Declaration of functions
STACK *makeStack();
STACK *increaseStack(STACK *pStack);
int stackPush(int x, STACK **ppStack);
int stackPop(STACK **ppStack);
int stackEmpty(STACK *pStack);
int stackFull(STACK *pStack);
void getFile(int argc, char *argv[], char **ppszInputFile);
void readFile();
/**************************** MAIN FUNCTION ************************/
int main(int argc, char *argv[])
{
printf("Assignment 2 written by Kyle Widmann\n\n");
//Pointer to input file from CLI, and stack to be used across program
char *pszInputFile = NULL;
STACK *pStack = makeStack();
//Get the filename from the CLI
getFile(argc, argv, &pszInputFile);
//Open and read the file, pushing/popping as necessary
readFile(pszInputFile, &pStack);
//reset pStack to beginning of stack and free
//GETTING ERRORS HERE????
// printf("about to initialize iCount\n");
int iCount = (int)pStack->iCount;
// printf(" in Main. iCount: %d\n", iCount);
pStack = pStack-(iCount-1);
// printf("in Main. pStack: %p\n", pStack);
free(pStack);
return 0;
}
void readFile(char *pszInputFile, STACK **ppStack){
char szInputBuffer[100]; //Input buffer to read from file
int iInput; //variable to store the int read from file
int iPop=0; //variable to store the popped int
FILE *pFile; //pointer to input file
//Open the file
pFile = fopen(pszInputFile, "r");
if(pFile == NULL)
printf("Error opening file;");
printf("pFile addres: %p\n", pFile);
while(fgets(szInputBuffer, 100, pFile) != NULL){
if(sscanf(szInputBuffer, "%d[^\n]", &iInput) == 1){
// printf("input: %d... \t", iInput);
if(iInput == POP){
// printf("about to Pop\n");
iPop = stackPop(ppStack);
if(iPop == FALSE){
printf("There was an error popping the stack\n");
}
else{
printf("Number of elements after popping: %d \t\t Integer popped: %d\n", (*ppStack)->iCount, iPop);
}
}
else{
printf("About to push %d \tStackSize: %d\tStackCount: %d\n", iInput, (*ppStack)->iStackSize, (*ppStack)->iCount);
stackPush(iInput, ppStack);
}
}
}
// GETTING ERRORS HERE???
// printf("pFile addres: %p\n", pFile);
if(pFile != NULL){
fclose(pFile);
pFile = NULL;
}
}
STACK *makeStack(){
STACK *stack = (STACK *)malloc(sizeof(STACK)*10);
stack->iInfo = 0;
stack->iCount = 0;
stack->iStackSize = 10;
if(stack == NULL){
printf("Error allocating stack\n");
}
return stack;
}
STACK *increaseStack(STACK *pStack){
// printf("inside increase stack. iCount: %d\tiStackSize: %d\n", pStack->iCount, pStack->iStackSize);
//Set old stack size and old count of elements to redirect new stack after realloc
int iOldCapacity = pStack->iStackSize;
int iOldCount = (int)pStack->iCount;
//set pStack back to the beggining of the HEAP
pStack = pStack-(pStack->iCount-1);
// printf("iCount after resetting to beginnign: %d\n", (pStack+iOldCount-1)->iCount);
//Realloc pStack and add 10 spaces
pStack = (STACK *)realloc(pStack, (sizeof(STACK)*(pStack->iStackSize + 10)));
// printf("Printing Stack...\n");
// int i;
// for(i = 0; i<iOldCount; i++){
// printf("Address: %p\tiCount: %d\t, iStackSize: %d\n", pStack+i, (pStack+i)->iCount, (pStack+i)->iStackSize);
// }
//point pStack back to the last element pushed onto stack
pStack = pStack + (iOldCount-1);
//Update the size of stack
pStack->iStackSize = pStack->iStackSize +10;
// printf("Post realloc. iCount: %d\tiStackSize: %d\n", pStack->iCount, pStack->iStackSize);
//Print out that the stack has grown.
printf("Stack capacity has grown from %d to %d\n", iOldCapacity, pStack->iStackSize);
return pStack;
}
int stackPush(int x, STACK **ppStack){
if(stackFull(*ppStack) == TRUE){
//increase stack size
*ppStack = increaseStack(*ppStack);
}
//set first element
if(stackEmpty(*ppStack) == TRUE){
(*ppStack)->iInfo = x;
(*ppStack)->iCount = (*ppStack)->iCount + 1;
}
else
{
//Set the next element in stack
(*ppStack+1)->iInfo = x;
(*ppStack+1)->iCount = (*ppStack)->iCount +1;
(*ppStack+1)->iStackSize = (*ppStack)->iStackSize;
//ensure always pointing to top
*ppStack = (*ppStack + 1);
}
return TRUE;
}
int stackPop(STACK **ppStack){
int iPop;
// if the stack is not empty
if(stackEmpty(*ppStack) == FALSE){
iPop = (*ppStack)->iInfo;
(*ppStack-1)->iStackSize = (*ppStack)->iStackSize;
//set the stack pointing to the previous element since current element was popped
*ppStack = (*ppStack -1);
return iPop;
}
return FALSE;
}
int stackEmpty(STACK *pStack){
if(pStack->iCount > 0){
return FALSE;
}
return TRUE;
}
int stackFull(STACK *pStack){
if(pStack->iCount + 1 == pStack->iStackSize){
return TRUE;
}
return FALSE;
}
/********************************* getFile ******************************
void getFile(int argc, char *argv[], char **ppszInputFile)
Purpose:
Reads the CLI to assign file name containing student info to pszInputFile
Parameters:
I int argc the count of command line arguments
I char argv[] Array of the command line arguments
I/O char **ppszInputFile Double pointer to character string for the file name
Notes:
**************************************************************************/
void getFile(int argc, char *argv[], char **ppszInputFile)
{
int i;
for (i = 1; i < argc; i++)
{
// check for a switch
if (argv[i][0] != '-')
printf("Error: Switch expected");
// determine which switch it is
switch (argv[i][1])
{
case 'i': // Book File Name
if (++i >= argc)
printf("Error: Missing Switch\n");
// check for too long of a file anme
else
*ppszInputFile = argv[i];
break;
default:
printf("Error: Switch expected");
}
}
}
Valgrind 输出:
valgrind --leak-check=full --show-leak-kinds=all ./stacks -i data_a2.txt
==7116== Memcheck, a memory error detector
==7116== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==7116== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==7116== Command: ./stacks -i data_a2.txt
==7116==
Assignment 2 written by Kyle Widmann
Size of STACK: 12 Size of stack: 12 Size of STACK*10: 120
pFile addres: 0x5203540
About to push 29 StackSize: 10 StackCount: 0
About to push 5 StackSize: 10 StackCount: 1
About to push 7295 StackSize: 10 StackCount: 2
About to push 103 StackSize: 10 StackCount: 3
About to push 394 StackSize: 10 StackCount: 4
Number of elements after popping: 4 Integer popped: 394
Number of elements after popping: 3 Integer popped: 103
About to push 48 StackSize: 10 StackCount: 3
About to push 12 StackSize: 10 StackCount: 4
About to push 839 StackSize: 10 StackCount: 5
About to push 55 StackSize: 10 StackCount: 6
Number of elements after popping: 6 Integer popped: 55
About to push 28 StackSize: 10 StackCount: 6
About to push 91 StackSize: 10 StackCount: 7
About to push 523 StackSize: 10 StackCount: 8
Number of elements after popping: 8 Integer popped: 523
About to push 289 StackSize: 10 StackCount: 8
About to push 32 StackSize: 10 StackCount: 9
inside increase stack. iCount: 9 iStackSize: 10
iCount after resetting to beginnign: 9
Printing Stack...
Address: 0x52047f0 iCount: 1 , iStackSize: 10
Address: 0x52047fc iCount: 2 , iStackSize: 10
Address: 0x5204808 iCount: 3 , iStackSize: 10
Address: 0x5204814 iCount: 4 , iStackSize: 10
Address: 0x5204820 iCount: 5 , iStackSize: 10
Address: 0x520482c iCount: 6 , iStackSize: 10
Address: 0x5204838 iCount: 7 , iStackSize: 10
Address: 0x5204844 iCount: 8 , iStackSize: 10
Address: 0x5204850 iCount: 9 , iStackSize: 10
Post realloc. iCount: 9 iStackSize: 20
Stack capacity has grown from 10 to 20
About to push 414 StackSize: 20 StackCount: 10
Number of elements after popping: 10 Integer popped: 414
About to push 829 StackSize: 20 StackCount: 10
About to push 21 StackSize: 20 StackCount: 11
About to push 9 StackSize: 20 StackCount: 12
About to push 45 StackSize: 20 StackCount: 13
About to push 299 StackSize: 20 StackCount: 14
About to push 101 StackSize: 20 StackCount: 15
Number of elements after popping: 15 Integer popped: 101
About to push 3 StackSize: 20 StackCount: 15
About to push 88 StackSize: 20 StackCount: 16
About to push 718 StackSize: 20 StackCount: 17
About to push 501 StackSize: 20 StackCount: 18
Number of elements after popping: 18 Integer popped: 501
About to push 39 StackSize: 20 StackCount: 18
About to push 89 StackSize: 20 StackCount: 19
inside increase stack. iCount: 19 iStackSize: 20
iCount after resetting to beginnign: 19
Printing Stack...
Address: 0x5204920 iCount: 1 , iStackSize: 10
Address: 0x520492c iCount: 2 , iStackSize: 10
Address: 0x5204938 iCount: 3 , iStackSize: 10
Address: 0x5204944 iCount: 4 , iStackSize: 10
Address: 0x5204950 iCount: 5 , iStackSize: 10
Address: 0x520495c iCount: 6 , iStackSize: 10
Address: 0x5204968 iCount: 7 , iStackSize: 10
Address: 0x5204974 iCount: 8 , iStackSize: 10
Address: 0x5204980 iCount: 9 , iStackSize: 20
Address: 0x520498c iCount: 10 , iStackSize: 20
Address: 0x5204998 iCount: 11 , iStackSize: 20
Address: 0x52049a4 iCount: 12 , iStackSize: 20
Address: 0x52049b0 iCount: 13 , iStackSize: 20
Address: 0x52049bc iCount: 14 , iStackSize: 20
Address: 0x52049c8 iCount: 15 , iStackSize: 20
Address: 0x52049d4 iCount: 16 , iStackSize: 20
Address: 0x52049e0 iCount: 17 , iStackSize: 20
Address: 0x52049ec iCount: 18 , iStackSize: 20
Address: 0x52049f8 iCount: 19 , iStackSize: 20
Post realloc. iCount: 19 iStackSize: 30
Stack capacity has grown from 20 to 30
About to push 47 StackSize: 30 StackCount: 20
==7116== Invalid write of size 4
==7116== at 0x400D30: stackPush (assignment2_stacks.c:162)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116== Address 0x5204a10 is 0 bytes after a block of size 240 alloc'd
==7116== at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7116== by 0x400BAE: increaseStack (assignment2_stacks.c:133)
==7116== by 0x400CDF: stackPush (assignment2_stacks.c:153)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116==
==7116== Invalid write of size 4
==7116== at 0x400D4A: stackPush (assignment2_stacks.c:163)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116== Address 0x5204a14 is 4 bytes after a block of size 240 alloc'd
==7116== at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7116== by 0x400BAE: increaseStack (assignment2_stacks.c:133)
==7116== by 0x400CDF: stackPush (assignment2_stacks.c:153)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116==
==7116== Invalid write of size 4
==7116== at 0x400D62: stackPush (assignment2_stacks.c:164)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116== Address 0x5204a18 is 8 bytes after a block of size 240 alloc'd
==7116== at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7116== by 0x400BAE: increaseStack (assignment2_stacks.c:133)
==7116== by 0x400CDF: stackPush (assignment2_stacks.c:153)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116==
pFile addres: 0x5203540
about to initialize iCount
==7116== Invalid read of size 4
==7116== at 0x40086F: main (assignment2_stacks.c:64)
==7116== Address 0x5204a14 is 4 bytes after a block of size 240 alloc'd
==7116== at 0x4C2FD5F: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==7116== by 0x400BAE: increaseStack (assignment2_stacks.c:133)
==7116== by 0x400CDF: stackPush (assignment2_stacks.c:153)
==7116== by 0x400A1B: readFile (assignment2_stacks.c:101)
==7116== by 0x400860: main (assignment2_stacks.c:60)
==7116==
in Main. iCount: 21
in Main. pStack: 0x5204920
==7116==
==7116== HEAP SUMMARY:
==7116== in use at exit: 0 bytes in 0 blocks
==7116== total heap usage: 6 allocs, 6 frees, 6,272 bytes allocated
==7116==
==7116== All heap blocks were freed -- no leaks are possible
==7116==
==7116== For counts of detected and suppressed errors, rerun with: -v
==7116== ERROR SUMMARY: 4 errors from 4 contexts (suppressed: 0 from 0)
最佳答案
问题出在您的 increaseStack() 函数中，这与我在评论中观察到的您保留了大量冗余数据有关。请特别注意，问题在第二次堆栈扩展后立即发生 - 这并非巧合。
以下是 increaseStack() 函数行为的高级描述:
记录堆栈容量和元素数量，如提供的元素指针所示。
使用记录的元素计数调整元素指针以指向最底部的堆栈元素。
重新分配，根据当前元素指针(现在指向最底部元素)指示的容量选择新容量。
调整堆栈指针，使其指向与函数入口处指向的元素相对应的重新分配空间的元素。
更新堆栈指针指向的元素中记录的堆栈容量。
仔细研究步骤 3 和 5，并考虑为什么您的方法适用于第一次堆栈扩展，但不适用于第二次。
我怀疑我知道您对解决方案的第一倾向是什么，但请抵制它。相反，请考虑如何更好地设计它。特别是，为每个元素设置单独的 iCount 和 iStackSize 会给您带来什么好处？ (提示:无。)
我建议像这样更改您的结构堆栈:
typedef struct stack{
int *iInfo;
int iCount;
int iStackSize;
}STACK;
然后，仅维护一个结构堆栈，并对其iInfo 成员执行动态分配/重新分配。使用基于 iCount 的简单索引语法在 iInfo 指向的空间中存储值并从中检索值。
关于c - 动态分配的堆栈和指针运算出现奇怪的内存错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37866100/