The new forums will be named Coin Return (based on the most recent vote)! You can check on the status and timeline of the transition to the new forums here.
The Guiding Principles and New Rules document is now in effect.
C++ (Pointers Asplode!)
clsCorwin
Registered User regular
Registered User regular
Yea, I'm still working on my linked-list implementation of a stack and queue, however my queues add is blowing up on me, as well as my stacks destroy (and I'm assuming queue::destroy() would blow if anything ever made it into it).
Heres my various functions from within my stack and queue cpp files.
I've drawn this stuff out, and the circles and arrows make sense, so I'm confused as to where I'm making an error here.
Heres my various functions from within my stack and queue cpp files.
void QUEUE::add(char ch)
{
if( QUEUE::empty() )
{
NODE *temp;
temp = new NODE;
temp->data = ch;
temp->next = rear;
front = temp;
delete temp;
count++;
}
else
{
NODE *temp;
temp = new NODE;
temp->data = ch; //assign data
rear->next = temp; //assign next link from rear
rear = temp; //set temp to rear
delete temp;
count++;
}
}
void QUEUE::destroy()
{
NODE *temp;
while( front != 0 && front != rear )
{
temp = front;
front = front->next;
delete temp;
}
}
void STACK::destroy()
{
NODE *temp;
while( top != 0 )
{
temp = top;
top = top->next;
delete temp;
}
}
I've drawn this stuff out, and the circles and arrows make sense, so I'm confused as to where I'm making an error here.
clsCorwin on
0
Posts
#pragma once struct NODE { char data; NODE *next; };Queue.h#pragma once #include "Node.h" class QUEUE { NODE *front; NODE *rear; int count; public: QUEUE(); ~QUEUE(); void create(); void destroy(); bool full(); bool empty(); void add(char ch); void remove(char &ch); char getFront(); char getRear(); int getCount(); };Queue.cpp#include "Queue.h" QUEUE::QUEUE() { QUEUE::create(); } QUEUE::~QUEUE() { QUEUE::destroy(); } void QUEUE::create() { front = rear = 0; count = 0; } void QUEUE::destroy() { NODE *temp; while( front != 0 && front != rear) { temp = front; front = front->next; delete temp; } } bool QUEUE::full() { bool result; NODE *temp; temp = new NODE; result = (temp == 0); delete temp; return result; } bool QUEUE::empty() { return count == 0; } void QUEUE::add(char ch) { if( QUEUE::empty() ) { NODE *temp; temp = new NODE; temp->data = ch; temp->next = rear; front = temp; delete temp; count++; } else { NODE *temp; temp = new NODE; temp->data = ch; //assign data rear->next = temp; //assign next link from rear rear = temp; //set temp to rear delete temp; count++; } } void QUEUE::remove(char &ch) { if( front == rear && !QUEUE::empty() ) { ch = front->data; front = rear = 0; count--; } else { NODE *temp; ch = front->data; //assign data to ch from front temp = front->next; //assign temp as front's link front = temp; //temp becomes front delete temp; //don't need temp anymore... count--; } } char QUEUE::getFront() { return front->data; } char QUEUE::getRear() { return rear->data; } int QUEUE::getCount() { return count; }Stack.h#pragma once #include "Node.h" class STACK { NODE *top; int count; public: STACK(); ~STACK(); void create(); void destroy(); bool full(); bool empty(); void push(char ch); void pop(char &ch); int getCount(); };Stack.cpp#include "Stack.h" STACK::STACK() { STACK::create(); } STACK::~STACK() { STACK::destroy(); } void STACK::create() { top = 0; count = 0; //sets total node count to 0 } void STACK::destroy() { NODE *temp; while( top != 0 ) { temp = top; top = top->next; delete temp; } } bool STACK::full() { bool result; NODE *temp; temp = new NODE; result = (temp == 0); delete temp; return result; } bool STACK::empty() { return count == 0; } void STACK::push(char ch) { NODE *temp; temp = new NODE; temp->data = ch; //put data into temp temp->next = top; //assign link to top top = temp; //set top to temp delete temp; //kill temp count++; //reduce node count } void STACK::pop(char &ch) { NODE *temp; temp = top; top = top->next; ch = temp->data; delete temp; count--; //increase node count } int STACK::getCount() { return count; }Palindrone.cpp#include "Queue.h" #include "Stack.h" #include <iostream> #include <fstream> #include <string> using namespace std; const int MAX = 80; typedef char STRING[MAX]; STACK s; //instantiating the objects QUEUE q; int length; void initialize(STRING str) { q.create(); //create the stack and queue s.create(); length = strlen(str); if( (q.full() == false) && (s.full() == false) ) //executes if both ADTs aren't full { for(int x = 0; x < length; x++) { q.add(str[x]); //puts data into the stack and queue s.push(str[x]); } } } bool isPalindrome() { bool result = true; while( (q.empty() == false) && (s.empty() == false) ) //executes while both ADTs { //are not empty char qchar, schar; q.remove(qchar); //stores queue in qchar s.pop(schar); //stores stack in schar if( qchar != schar ) //if the char removed from the queue != the char popped result = false; //it isn't a palindrome } return result; } void uninitialize() { q.destroy(); s.destroy(); } void print(STRING str) { ofstream fout("output.txt", ios::app); if( isPalindrome() ) fout << endl << "\"" << str << "\"" << " is a palindrome." << endl; else fout << endl << "\"" << str << "\"" << " is not a palindrome." << endl; } void printADT() //function to test if queue and stack are working properly { char ch; cout << "Queue Data:" << endl; //prints the contents of the queue for(int x = 0; x < q.getCount(); x++) { q.remove(ch); cout << x << ": " << ch << endl; } cout << "Stack Data:" << endl; //prints the contents of the stack for(int x = 0; x < s.getCount(); x++) { s.pop(ch); cout << x << ": " << ch << endl; } } int main() { STRING input; cout << "Enter a string to be checked." << endl; cin.getline(input, 80); initialize(input); print(input); uninitialize(); return 0; }See how many books I've read so far in 2010
For example, Node.h should be named Node.hpp, and look like this:
#ifndef NODE_H #define NODE_H struct NODE { char data; NODE *next; }; #endifI'm going to make these modifications, then compile, run, and see what happens.
front = temp; delete temp;front and temp are pointers to the same node. When you use delete you don't do anything to the pointer itself, you delete the data that it points to. So front is now a "dangling pointer".See how many books I've read so far in 2010
if( QUEUE::empty() ) { NODE *temp; temp = new NODE; temp->data = ch; temp->next = rear; front = temp; delete temp; count++; } else { NODE *temp; temp = new NODE; temp->data = ch; //assign data rear->next = temp; //assign next link from rear rear = temp; //set temp to rear delete temp; count++; }would work as:
if( QUEUE::empty() ) { NODE *temp; temp = new NODE; temp->data = ch; temp->next = rear; front = temp; rear = temp; count++; } else { NODE *temp; temp = new NODE; temp->data = ch; //assign data temp->next = rear; rear = temp; //set temp to rear count++; }Meet Barack Obama
Assertions, and how to use them
Assertions are one of the best debugging tools available. Their use is simple:
For example, in Queue::add, the first crash is a result of trying to read a NULL pointer.
void QUEUE::add(char ch) { if( QUEUE::empty() ) { NODE *temp; temp = new NODE; temp->data = ch; temp->next = rear; front = temp; delete temp; count++; } else { NODE *temp; temp = new NODE; temp->data = ch; rear->next = temp; // <--- CRASH! rear = temp; delete temp; count++; } }In this case, you can use an assertion to track down what's going on:
Once you've gotten there, it's time to find out why rear is NULL. In this case, the answer turns out to be easy - you never set rear in add() when the queue is empty.
By sprinkling assertions around your code to check that everything is as it should be, you help catch errors early. The earlier you catch an error, the closer it will be to its source.
new and delete
Based on how you're using these, I bet you come from a Java backround. For an example of what's wrong, I will again use Queue::add():
In C++, pointers are like "labels" that point to given locations in memory. These locations are given to your program by new and delete. "temp = new NODE" means "the label temp now points to some memory location". "front = temp" means "the label front now points to the same memory location". "delete temp" means "mark that memory location as invalid". Because temp and front both point to the same data area, you should not delete the data until you really don't need it any more. That would be somewhere in Queue::remove.
The debugger
Since you're using Visual Studio, you can run a debugger (no memory checker
See how many books I've read so far in 2010
void QUEUE::add(char ch) { if( QUEUE::empty() ) { NODE *temp; temp = new NODE; //create loc in mem for temp to point to rear = new NODE; //create loc in mem for rear to point to temp->data = ch; //assign data to temp temp->next = rear; //set link from temp to rear front = temp; //front points to temp points to count++; } else { NODE *temp; temp = new NODE; //create loc in mem for temp to point to temp->data = ch; //assign data rear->next = temp; //set link from rear to temp rear = temp; //rear points to mem temp points to count++; } } void QUEUE::remove(char &ch) { if( front == rear && !QUEUE::empty() ) { ch = front->data; front = rear = 0; delete front; count--; } else { NODE *temp; ch = front->data; //assign data to ch from front temp = front; //assign temp to mem front points to front = front->next; //front now points to front->next delete temp; //delete memory where temp points count--; } }See how many books I've read so far in 2010
See how many books I've read so far in 2010
See how many books I've read so far in 2010
It hits the while loop the first time and deletes the data at 0x00355b80, but since 0xcdcdcdcd isn't NULL, it runs again. Now, it has no valid next pointer, and it crashes.
Advice?
See how many books I've read so far in 2010
Stack.cpp
#include "Stack.h" STACK::STACK() { STACK::create(); } STACK::~STACK() { STACK::destroy(); } void STACK::create() { top = 0; count = 0; //sets total node count to 0 } void STACK::destroy() { NODE *temp; while( top != 0 ) { temp = top; top = top->next; delete temp; } } bool STACK::full() { bool result; NODE *temp; temp = new NODE; result = (temp == 0); delete temp; return result; } bool STACK::empty() { return count == 0; } void STACK::push(char ch) { if( STACK::empty() ) { NODE *temp; temp = new NODE; //create loc in mem for temp to point to top = new NODE; //create loc in mem for top to point to top->data = ch; //assign data top->next = temp; //set link from temp to top count++; } else { NODE *temp; temp = new NODE; //create loc in mem for temp to point to temp->data = ch; //assign data temp->next = top; //set link from temp to top top = temp; //top points to mem temp points to count++; } } void STACK::pop(char &ch) { NODE *temp; //create pointer temp = top; //set pointer to loc in mem top points to top = top->next; //top points to loc in mem top->next points to ch = temp->data; //assign value to ch delete temp; //delete memory that temp points to count--; //increase node count } int STACK::getCount() { return count; }See how many books I've read so far in 2010
It looks like there are some cases for which top isn't initialized (set to a value). Specifically, you're not setting temp->next to NULL in Stack::push, or top->next to NULL in Stack::pop.
There is no language requirement that says what your filename extensions should be. That having been said, "Header files are conventionally suffixed by .h." is a quote from Bjarne Stroustrop (the creator of C++) in his book -- which I had open on my desk when I read this post. I've never seen .hpp used by anyone but old Borland users.
As for the use of "#pragma once" it's a lot more elegant than the preprocessor guards. I know GCC gives a warning about it being deprecated, but I couldn't care less really, I use "#pragma once" all the time and will continue to do so until I hear a better argument against it than "us Linux weenies get a compiler warning and therefore you must do things our way."
There's no requirement, but if you don't, it's not obvious which headers are intended for C and which for C++. It's good to get into the habit of giving future readers of the code plenty of information
It's not good to rely upon your compiler's error handling behaviour. Just because you can turn off all your warnings or use a broken compiler, doesn't mean that the rest of us in Standards Land won't hate you for it. Or would you prefer I write code like this, just because my compiler happens to support it?
int some_function () { return ({int i; i = 0; i}); }Top is really at the bottom of the chain here. If I put top->next = 0, then I would lose the rest of my data. I already say top = top->next, to traverse the list while deleting the previous nodes after their data has been taken.
However, I did go and pretty much everytime I created a new node, I assigned its next pointer to 0. So now everything works super.
Appreciate all the help, and the additional info on new and delete.
Solved for the lock!
See how many books I've read so far in 2010
Yes, I follow your reasoning, and I don't have a problem with someone naming things .hpp. But, it's not "the (one) right way", a standard, or even a common practice. It's also unintuitive to me, because when you think about it, what is hpp, "header plus plus"? :P In the unlikely event that some confused C programmer tries to include a header file with C++ specific stuff in it, the compiler will error and they will see their mistake, and that's good enough for me.
That's good advice, but I think it's irrelevant here. The C++ standards have had nothing to say about "#pragma once", it's just the GCC community that decided to deprecate it, even though the support was already there and it's a better way of checking for redundant header inclusion. Why is it better? Because it's one line instead of three lines of code, because it's less of a hack, and also because you can have two header files named the same thing in different places in the source tree, and not worry about name conflicts when some guy decides to include both "../one/foo.h" and "../two/foo.h" in his code.
Your use of the term "broken" is a little perjorative. I mean, MSVC 2005 is extremely compliant to language standards. The only time I need to alter GNU code to get it to compile in Microsoft VC++ is when the GNU code relies on APIs present only in POSIX operating systems. Which is frequently, but, let's not blame the compiler for the non-standard-ness of the OS. :-)
Since pragmas are not included in the C++ standard in any way, it should not be used except in code written for interoperation with a specific compiler. They are not part of the C++ standard, and should not be taught in a class supposedly about C++. An improperly namespaced include guard is just as bad as an improperly namespaced function - your example headers should define ONE_FOO_H and TWO_FOO_H, not just FOO_H.
VS 2005 is hardly compliant to the standards - try using any of the standard C library functions like strcpy, sscanf and it will error out with the command to use its own (Windows-specific) functions. It also does not support exception specifications (in any meaningful way) or C's variadic macros.
As long as you properly space out your curly braces, thats all that really matters. You can figure everything else out as long as its readable.
See how many books I've read so far in 2010
Well there's learning to code, and there's learning all the cruft that is required to get your project to build. Understanding pointers, classes, templates, advanced data structures -- that's all learning to code; that's the focus of a good class. Understanding makefiles, compiler-specific preprocessor features, or what have you is not the focus, but I think it's unrealistic to expect some amount of development environment-specific knowledge won't be shared.
The C runtime library functions for string and buffer manipulation are prone to security (buffer overflow) problems, so VS2005 just warns (not errors) you to use secure versions of those routines. If you define CRT_SECURE_NO_DEPRECATE it will not do that. There will probably be a standardized secure CRT eventually, but Microsoft should be lauded for taking the initiative in the meantime. Having the ability to make my old code more secure is a good thing. In any case the support for the old CRT functions is all still there.
I had noticed the lack of variadic macro support in VS2003, but VS2005 supports them no problem. Exception specifications, that's an even more esoteric language feature. It's one of only two language features that VS2005 does not support (the other being export templates, which no compiler except Comeau supports, and many people want removed from the C++ 0x standard anyway). The omission of support for these two features was intentional and a conscious choice, from what I have heard in interviews with the VC++ product team at Microsoft.
So I stand by my earlier statement; VC++ 2005 is extremely compliant to the language standards.
ifndef-define-endif guards work on every compiler on every system. They are as much a part of the language as pointers or functions. Unless the class is specifically on working with a specific compiler, it shouldn't use proprietary and non-portable versions of standard language features.
Warnings are as bad as errors, since decent programmers set "error on warning" flags anyway. Compiler diagnostics should be reserved for real problems, not just when some company decides certain functions don't help their bottom line. Microsoft should not be praised for telling programmers to abandon the perfectly safe, standard libraries in favor of their own Windows-specific libraries. If I wanted to code to one OS, I would use Win32, or MFC, or WinForms, or whatever the current library of the week is.
Exception specifications are hardly esoteric - it's nearly impossible to use exceptions correctly without them. You are correct, though, about the variadic macros - I had mixed up 2003 and 2005.
.hpp isn't even remotely standard. .h, .H, .hpp, .h++, and hundred of other extensions (or none at all) are in use out there. They're all arbitrary, they all vary from the coding standards of one institution to another, and not using one specific version of the extensions isn't evidence of anything.
At any rate, .h is the most standard extension for C++ header files, and it's what Stroustrup uses himself in in the language documentation. I'm all for giving style advice to beginners when it's helpful, but don't muddy the issue by giving style advice as though it's immutable fact. At the end of the day, it's nothing more than personal preference with no effect on anything.
Edit: I see someone else caught you out at this as well Which is irrelevant given the superset nature of C++, except in some highly specific corner cases, none of which apply to a beginner doing a straight C++ project. It's lousy advice to confuse a beginner with crap like "if you're not using .hpp your prof doesn't understand the language". .h is as close to a de facto standard as exists for C++ header files.
I'm not trying to say that .hpp is the one and only way. If you use .c++, use .h++. If .C, then .H. But just as you wouldn't name your C++ source files .c, you shouldn't name your C++ headers .h.
There is no better time than when beginning to learn how to program correctly. If a user learns to name their files incorrectly, to use proprietary compiler features, or to quiet warnings it can take much longer for them to become a proficient programmer.