Stupid Pointers

[klopyrev]

Can someone who is proficient enough in Pointers check over this program for me? I just started learning C++ and want to check if the program is correct in terms of deleting all the allocated memory and other small details. Please read it over carefully and point it out if you find any potential bug or memory leak. This is the solution to problem S4 from the last CCC contest. If you don't know the problem, you can find it in the Contests forum, subject S1. In this program, I am trying to implement a Linked List. Since I just started programming, my implementation may not be perfect. If it isn't, I want to know what the problems with it are, so as to become more proficient with C++. Please read it over really carefully so as to find even the smallest, most obscure mistakes. Thank you for your time.

KL

PROGRAM:
#include <fstream>
#include <iostream>
using namespace std;
const int NUL = 0;
struct Element
{
int value;
Element * next;
};
int main()
{
char name[80];
cout << "Please enter the file name: ";
cin.getline(name, 80);
ifstream fin (name);
int N;
fin >> N;
Element ** front = new Element * [N];
Element ** back = new Element * [N];
for(int i = 0; i<N; i++)
{
front[i] = NUL;
back[i] = NUL;
}
int a, b;
while(fin >> a >> b && a!=0)
{
a--;
b--;
Element * next = new Element;
next -> value = a;
next -> next = NUL;
if(front[b] == NUL)
front[b] = next;
else
back[b] -> next = next;
back[b] = next;
}
long * dp = new long[N];
dp[0] = 1;
for (int i =1; i<N ;i++)
{
dp[i] = 0;
Element * next = front[i];
while(next!=NUL)
{
dp[i]+=dp[next -> value];
next = next -> next;
}
}
cout << dp[N-1] << '\n';
delete [] dp;
for(int i = 0; i<N; i++)
{
Element * next = front[i];
while(next!=NUL)
{
Element * temp = next;
next = next -> next;
delete temp;
}
}
delete [] front;
delete [] back;
return 0;
}

EDIT: Sorry about the lack of indentation and such. It looks fine to me when I write it in the editor, but when I look at the actual post, it seems to lack all the spacing and such. Strange.

[Null]

That's what code tags are for.

[ code ] and [/ code ] without the spaces will retain indenting.

[klopyrev]

Huh... I didn't know that. Here it is again then:

code:

#include <fstream> #include <iostream> using namespace std; const int NUL = 0; struct Element {         int value;         Element * next; }; int main() {         char name[80];         cout << "Please enter the file name: ";         cin.getline(name, 80);         ifstream fin (name);         int N;         fin >> N;         Element ** front = new Element * [N];         Element ** back = new Element * [N];         for(int i = 0; i<N; i++)         {                 front[i] = NUL;                 back[i] = NUL;         }         int a, b;         while(fin >> a >> b && a!=0)         {                 a--;                 b--;                 Element * next = new Element;                 next -> value = a;                 next -> next = NUL;                 if(front[b] == NUL)                         front[b] = next;                 else                         back[b] -> next = next;                 back[b] = next;         }         long * dp = new long[N];         dp[0] = 1;         for (int i =1; i<N ;i++)         {                 dp[i] = 0;                 Element * next = front[i];                 while(next!=NUL)                 {                         dp[i]+=dp[next -> value];                         next = next -> next;                 }         }         cout << dp[N-1] << '\n';         delete [] dp;         for(int i = 0; i<N; i++)         {                 Element * next = front[i];                 while(next!=NUL)                 {                         Element * temp = next;                         next = next -> next;                         delete temp;                 }         }         delete [] front;         delete [] back;         return 0; }

[Martin]

Some nit-picking. You shouldn't use char arrays (or C strings as they're sometimes called) in C++, use std::string in <string> instead. One of the big things that this will save you from are buffer overflows.

Also, use the keyword NULL; it'll do the same thing that you're doing with NUL.

As for the pointer stuff, I'm not sure what you're trying to do here "Element ** front = new Element * [N]; " It creates an array of N Element* pointers. It sort of kills the point of making a linked list, since you're just making an array of length N of Element*'s. When creating a linked list, the idea is that you have a pointer to the first element, call it "Element *head;", and then from that you can get to the n'th element by calling

code:

Element *current = head; for( int i=0;i<n;++i ) {     if( current != NULL )         current = current->next; }

Now, if you want to delete your list, you can simply do something like this:

code:

void deleteList( Element *e ) {     deleteList( e );     delete e; }

Trace that out, it should make sense.

Your delete statements at the end would free up the memory, but again, that's a bad implementation.

If you really want to do this, you should be using an STL vector, which frees itself when you're done with it.

Also, this is bad: "next = next -> next;" It works because of scope, but that's a really ambiguous statement. And while I'm at it, use some real variable names. dp doesn't tell me anything except that you're doing a dynamic programming solution. If it's cost, you should call it cost. And a comment here or there might be nice, but I understand it's a contest question.

[haskell]

Here are my suggestions:

1. Spaces are your friend. Its not all about writing the code fast, its about being able to find the errors as fast as possible, thus cutting down the time.

2. Look up the Standard Template Library(STL). It will save you bundles of time on these toy problems.

3. Char arrays = BAD in C++.

4. Making bulk arrays at the top is bad(char name[80]). Try to figure out the size from their input, then make the array according to that. That way you lessen your chances of an overflow.

5. Do a little C++ research. C is not C++... That code looks just like C, with a couple common STL templates put in for good measure. Try to maximize STL use.

[klopyrev]

Since nobody actually noticed any errors, I'm guessing there are none. I don't use vectors or strings, because I haven't reached that chapter in the book yet. I'm just trying to make sure I understand pointers completely before I go on. I understand char arrays are bad, but I don't know how to use anything else yet. I haven't learned STL yet either.

Quote:

As for the pointer stuff, I'm not sure what you're trying to do here "Element ** front = new Element * [N]; " It creates an array of N Element* pointers. It sort of kills the point of making a linked list, since you're just making an array of length N of Element*s.

I'm actually creating an array of linked lists. I need a linked list for each vertex in the graph. My front is the same thing as head. I added the back array to make the program work faster when reading a lot of input.

If anybody else spots any mistakes, please tell me. Once again, I'm putting the emphasis on my use of pointers, not my lack of use of the STL.

KL[/quote]

[Martin]

Oh, I get it now. Okay, you're fine then. Just fix the NULL and the next = next -> next thing (and the back[b] -> next = next;)

[abcdefghijklmnopqrstuvwxy]

Quote:

Please read it over really carefully so as to find even the smallest, most obscure mistakes. Thank you for your time.

Why would you say this, and then say "since no one found any errors."

All the things pointed out were errors. Just because you are properly allocating memory and freeing your pointers doesn't mean your code doesn't have any mistakes.

I think next time you want help you should state what you really want. For example, in this case, you should have said "I know my code is bad C++, but regarding pointers, have I made any mistakes?"