-2
我一直在寻找相当多的东西，我一直无法找到解决方案。对于我的数据结构课程，我被要求使用链表创建一个堆栈。在大多数情况下，它运作良好，我的教授甚至给了我24/25的任务，但它一直困扰着我，它仍然崩溃。我怀疑问题在于复制构造函数或弹出操作。这里是头文件：使用链接列表的C++堆栈双删除问题
/*******************************************************************************
*** DESCRIPTION : This file implements a stack ADT using a linked list. ***
*** Besides the standard constructor, copy, and destructor ***
*** functions, the available functions include: ***
*** * push - pushes data onto the stack ***
*** * pop - pops data from the stack ***
*** * peek - view the top element on the stack ***
*** * view - output every element on the stack ***
*******************************************************************************/
#ifndef _KIELASJC2_H
#define _KIELASJC2_H
// User specified element type
typedef char ElementType;
class StackType{
// Exportable definitions
public:
// Constructor
StackType();
// Copy constructor
StackType(StackType& copyStack);
// Destructor
~StackType();
// Push data onto the stack
void push(const ElementType pushElem);
// Pop data from the stack
void pop(ElementType& popElem);
// Peek the top element on the stack without changing the stack
void peek(ElementType& peekElem);
// Look at every element in the stack without changing the stack
void view();
private:
// Non-exportable definitions
struct NodeType;
typedef NodeType* PointerType;
struct NodeType{
ElementType element;
PointerType next;
};
PointerType theTop;
bool isEmpty(PointerType tempNode);
bool isFull(PointerType tempNode);
};
#endif
，这里是实现文件：
/*******************************************************************************
*** DESCRIPTION : This file implements a stack ADT using a linked list. ***
*** Besides the standard constructor, copy, and destructor ***
*** functions, the available functions include: ***
*** * push - pushes data onto the stack ***
*** * pop - pops data from the stack ***
*** * peek - view the top element on the stack ***
*** * view - output every element on the stack ***
*** It also includes two private functions: ***
*** * isEmpty - checks to see if the stack is empty ***
*** * isFull - checks to make sure temp wasn't NULL ***
*******************************************************************************/
#include <iostream> // For using cout
#include <iomanip> // For manipulating output
#include "kielasjc2.h" // Header to this implementation file
// Debug
#define DEBUG 0
// Namespace
using namespace std;
/*******************************************************************************
*** FUNCTION Constructor ***
********************************************************************************
*** DESCRIPTION : Initializes the class by setting theTop and tempNode to ***
*** NULL. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : NONE ***
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
StackType::StackType() {
// Initialize both top and temp to NULL
theTop = NULL;
}
/*******************************************************************************
*** FUNCTION Copy Constructor ***
********************************************************************************
*** DESCRIPTION : Creates a copy of the stack linked list by popping all ***
*** elements in the first stack into a temporary stack. All ***
*** elements from the temporary stack are then pushed back ***
*** into the copied stack and original stack. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : StackType& copyStack - copy of the original stack ***
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
StackType::StackType(StackType& copyStack) {
// Point the top to NULL
theTop = NULL;
// Create a temporary stack
StackType tempStack;
// Create a temporary element
ElementType tempElem;
// Create a temporary pointer to the top
//PointerType tempNode = theTop;
// Create a temporary pointer to the the top of the copy stack
//PointerType tempTempNode = tempStack.theTop;
//PointerType copyTempNode = copyStack.theTop;
// Loop through the entire stack and pop each element into the temp stack
while (!copyStack.isEmpty(copyStack.theTop)) {
// Pop the current stack
copyStack.pop(tempElem);
// Push the popped element into the temp stack
tempStack.push(tempElem);
}
// Refill the current and copy stacks with the temp stack
while (!tempStack.isEmpty(tempStack.theTop)){
// Pop the temp stack
tempStack.pop(tempElem);
// Push the popped element onto the current newly copied stack
push(tempElem);
// Push the same popped element back onto the copy stack
copyStack.push(tempElem);
}
}
/*******************************************************************************
*** FUNCTION Destructor ***
********************************************************************************
*** DESCRIPTION : Destroys the current stack by popping every element. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : NONE ***
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
StackType::~StackType() {
// Create a temporary element just so we can call pop
ElementType tempElem;
#if DEBUG
cout << "[+] DEBUG: FUNCTION - Destructor" << endl;
cout << "[+] theTop: " << theTop << endl;
#endif
// While the stack is not empty, pop
while (!isEmpty(theTop)) {
// Pop the top node
pop(tempElem);
}
}
/*******************************************************************************
*** FUNCTION push ***
********************************************************************************
*** DESCRIPTION : Pushes the input element onto the current stack. ***
*** INPUT ARGS : const ElementType pushElem - element to be pushed onto ***
*** the current stack. ***
*** OUTPUT ARGS : NONE ***
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
void StackType::push(const ElementType pushElem) {
// Create a pointer to a new node
PointerType tempNode = new (nothrow) NodeType;
// Verify that the node isn't full
if (isFull(tempNode)) {
// Tell the user if new memory couldn't be allocated
cout << "[!] ERROR: (push) New dynamic node could not be created.";
cout << endl;
return;
}
#if DEBUG
ElementType tempElem;
cout << "[+] DEBUG: FUNCTION - push" << endl;
peek(tempElem);
cout << "[+] top before the push: " << tempElem << endl;
cout << "[+] Top ptr before: " << theTop << endl;
#endif
// Set the temporary node element to the element being pushed
tempNode->element = pushElem;
// Set the next pointer to the top
tempNode->next = theTop;
// If these two lines were flipped, the code works, but it creates a memory
// leak, so that doesnt work either
theTop = tempNode;
tempNode = NULL;
#if DEBUG
peek(tempElem);
cout << "[+] Top ptr after: " << theTop << endl;
cout << "[+] top after the push: " << tempElem << endl;
#endif
}
/*******************************************************************************
*** FUNCTION pop ***
********************************************************************************
*** DESCRIPTION : Pops the top element off of the current stack. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : ElementType& popElem - Stores the element that was ***
*** popped from the stack.
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
void StackType::pop(ElementType& popElem) {
// Create a temporary pointer
PointerType tempNode = theTop;
// Point temp to the same node the top is pointing to
//tempNode = theTop;
// Make sure the stack isn't empty
if (isEmpty(tempNode)) {
// Tell the user if the stack is empty
cout << "[!] ERROR: (pop) No node available to pop, stack is empty.";
cout << endl;
return;
}
#if DEBUG
cout << "[+] DEBUG: FUNCTION - pop" << endl;
cout << "[+] Top ptr before: " << theTop << endl;
#endif
// Point the top to the next node
theTop = theTop->next;
// Derefrence the next node of the current node being popped
tempNode->next = NULL;
// Pop the element into popElem
popElem = tempNode->element;
// Delete the node
delete tempNode;
// Point temp back to NULL
tempNode = NULL;
#if DEBUG
cout << "[+] Top ptr after: " << theTop << endl;
cout << "[+] Element being popped: " << popElem << endl;
#endif
}
/*******************************************************************************
*** FUNCTION peek ***
********************************************************************************
*** DESCRIPTION : Looks at the top element of the current stack by popping ***
*** it. The element is then pushed back onto the top of the ***
*** current stack. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : ElementType& peekElem - stores the element being peeked. ***
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
void StackType::peek(ElementType& peekElem) {
// Create a temporary pointer
//PointerType tempNode;
// Point temp to the top
//tempNode = theTop;
// Make sure the stack isn't empty
if (isEmpty(theTop)) {
// Tell the user if the stack is empty
cout << "[!] ERROR: (peek) Stack is empty, no element to peek at.";
cout << endl;
// Return a null value if the stack is empty
peekElem = '\0';
return;
}
// Pop the top element into peekElem
pop(peekElem);
// Push the popped element back onto the top of the stack
push(peekElem);
#if DEBUG
cout << "[+] DEBUG: FUNCTION - peek" << endl;
cout << "[+] Peeked value: " << peekElem << endl;
#endif
}
/*******************************************************************************
*** FUNCTION view ***
********************************************************************************
*** DESCRIPTION : Shows the user every element on the current stack by ***
*** popping every element and pushing them into a temporary ***
*** stack. Once the user has seen the contents of the stack, ***
*** the elements on the temporary stack are popped and ***
*** pushed back onto the current stack. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : NONE ***
*** IN/OUT ARGS : NONE ***
*** RETURN : NONE ***
*******************************************************************************/
void StackType::view() {
// Create a temporary stack
StackType tempStack;
// Create a temporary element
ElementType tempElem;
// Point a temporary node to the top
//PointerType tempNode = theTop;
// Point a temporary node to the top of the copy stack
//PointerType copyTempNode;
// View output for the user
cout << "The Top -> ";
// Loop through the entire stack and pop each element into the temp stack
while (!isEmpty(theTop)) {
// Pop the current stack
pop(tempElem);
// Push the popped element into the temp stack
tempStack.push(tempElem);
// Output the elements as the stack is popped
cout << tempElem << " -> ";
}
cout << "The Bottom" << endl;
// Refill the current stack with the temp stack
while (!tempStack.isEmpty(tempStack.theTop)){
// Pop the temp stack
tempStack.pop(tempElem);
// Push the popped element onto the current stack
push(tempElem);
}
}
/*******************************************************************************
*** FUNCTION isEmpty ***
********************************************************************************
*** DESCRIPTION : Checks to see whether or not the stack is empty. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : NONE ***
*** IN/OUT ARGS : NONE ***
*** RETURN : bool true/false - true if the stack is empty, false ***
*** if the stack is not empty. ***
*******************************************************************************/
bool StackType::isEmpty(PointerType tempNode) {
// If the top isn't pointing to NULL, our stack isn't empty yet
if (tempNode != NULL) {
return false;
} else {
return true;
}
}
/*******************************************************************************
*** FUNCTION isFull ***
********************************************************************************
*** DESCRIPTION : Checks to see if the current stack is full after ***
*** attempting to allocate new memory for the next node. ***
*** This will only provide a relevent value if it is used ***
*** immediately after trying to allocate memory for a new ***
*** node being pointed to by the tempNode. ***
*** INPUT ARGS : NONE ***
*** OUTPUT ARGS : NONE ***
*** IN/OUT ARGS : NONE ***
*** RETURN : bool true/false - true if the tempNode is NULL, false ***
*** if a pointer value was assigned to tempNode. ***
*******************************************************************************/
bool StackType::isFull(PointerType tempNode) {
// If temp isn't NULL, we have successfully allocated memory.
// This function should only be used immediately after allocating new
// memory to the tempNode.
if (tempNode != NULL) {
return false;
} else {
return true;
}
}
这是我的测试代码：
#include <iostream>
#include "kielasjc2.h"
using namespace std;
int main(int argc, char* argv[]) {
StackType stack;
StackType stack2;
stack.push('a');
stack2 = stack;
cout << "Stack: ";
stack.view();
cout << endl;
cout << "Stack2: ";
stack2.view();
cout << endl;
}
最后，这是输出（包括错误）我收到：
Stack: The Top -> a -> The Bottom
Stack2: The Top -> a -> The Bottom
*** glibc detected *** ./a.out: double free or corruption (fasttop): 0x0000000001d78010 ***
======= Backtrace: =========
/lib64/libc.so.6(+0x75f3e)[0x7f9b25fb0f3e]
/lib64/libc.so.6(+0x78d8d)[0x7f9b25fb3d8d]
./a.out[0x400c67]
./a.out[0x400b35]
./a.out[0x400f50]
/lib64/libc.so.6(__libc_start_main+0xfd)[0x7f9b25f59d1d]
./a.out[0x400919]
======= Memory map: ========
00400000-00402000 r-xp 00000000 00:15 9699818 /users/csc300/kielasjc/CSC300/A2_Stack_ADT/a.out
00601000-00602000 rw-p 00001000 00:15 9699818 /users/csc300/kielasjc/CSC300/A2_Stack_ADT/a.out
01d78000-01d99000 rw-p 00000000 00:00 0 [heap]
7f9b20000000-7f9b20021000 rw-p 00000000 00:00 0
7f9b20021000-7f9b24000000 ---p 00000000 00:00 0
7f9b25f3b000-7f9b260c5000 r-xp 00000000 fd:00 917513 /lib64/libc-2.12.so
7f9b260c5000-7f9b262c5000 ---p 0018a000 fd:00 917513 /lib64/libc-2.12.so
7f9b262c5000-7f9b262c9000 r--p 0018a000 fd:00 917513 /lib64/libc-2.12.so
7f9b262c9000-7f9b262cb000 rw-p 0018e000 fd:00 917513 /lib64/libc-2.12.so
7f9b262cb000-7f9b262cf000 rw-p 00000000 00:00 0
7f9b262cf000-7f9b262e5000 r-xp 00000000 fd:00 917506 /lib64/libgcc_s-4.4.7-20120601.so.1
7f9b262e5000-7f9b264e4000 ---p 00016000 fd:00 917506 /lib64/libgcc_s-4.4.7-20120601.so.1
7f9b264e4000-7f9b264e5000 rw-p 00015000 fd:00 917506 /lib64/libgcc_s-4.4.7-20120601.so.1
7f9b264e5000-7f9b26568000 r-xp 00000000 fd:00 917544 /lib64/libm-2.12.so
7f9b26568000-7f9b26767000 ---p 00083000 fd:00 917544 /lib64/libm-2.12.so
7f9b26767000-7f9b26768000 r--p 00082000 fd:00 917544 /lib64/libm-2.12.so
7f9b26768000-7f9b26769000 rw-p 00083000 fd:00 917544 /lib64/libm-2.12.so
7f9b26769000-7f9b26851000 r-xp 00000000 fd:00 1049574 /usr/lib64/libstdc++.so.6.0.13
7f9b26851000-7f9b26a51000 ---p 000e8000 fd:00 1049574 /usr/lib64/libstdc++.so.6.0.13
7f9b26a51000-7f9b26a58000 r--p 000e8000 fd:00 1049574 /usr/lib64/libstdc++.so.6.0.13
7f9b26a58000-7f9b26a5a000 rw-p 000ef000 fd:00 1049574 /usr/lib64/libstdc++.so.6.0.13
7f9b26a5a000-7f9b26a6f000 rw-p 00000000 00:00 0
7f9b26a6f000-7f9b26a8f000 r-xp 00000000 fd:00 917528 /lib64/ld-2.12.so
7f9b26c7d000-7f9b26c82000 rw-p 00000000 00:00 0
7f9b26c8b000-7f9b26c8e000 rw-p 00000000 00:00 0
7f9b26c8e000-7f9b26c8f000 r--p 0001f000 fd:00 917528 /lib64/ld-2.12.so
7f9b26c8f000-7f9b26c90000 rw-p 00020000 fd:00 917528 /lib64/ld-2.12.so
7f9b26c90000-7f9b26c91000 rw-p 00000000 00:00 0
7ffe362e8000-7ffe362fd000 rw-p 00000000 00:00 0 [stack]
7ffe36359000-7ffe3635a000 r-xp 00000000 00:00 0 [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
Aborted
当你使用调试器来逐步执行代码，每次一行，并在调试器中做出什么看法？ –
我意识到问题发生在析构函数被调用时。我结束了多次删除同一个节点，从而导致双重空闲错误。 – magicbycalvin