HELP Implementing Double Linked Lists as an Array of Pointers in C++
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: HELP Implementing Double Linked Lists as an Array of Pointers in C++

  1. #1
    Join Date
    Dec 2012
    Posts
    3

    Question HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Hi Everyone,

    I am studying/writing/ code for a future Advanced Data Structure class in C++; however I am not suppose to use STL, Templates and etc (the way I just code "kinda" of resembles what I have to use).

    My application is suppose to read/analyze all integers contained in a text file of 5-digit integers (10000 99999).

    For simplicity I am using the following input (or please, check the attached):

    20007 20008 20009
    20010 20010
    20012 20012
    20013
    20014 20010
    20015
    20016

    10000 10009 10009 10003
    10004 10005
    10006 10002
    10008 10003
    10007
    10013

    20151 20151
    20152

    30734
    30735
    30736
    30736 30738
    30738
    30739
    30740
    30741
    30742
    30743 30744 30745 30746 30747

    30748

    So far, my code is not displaying/printing the lists separated by the first digit of these 5-digits integers. I am expecting it to display/print logically/similar to the following:

    Output:

    Results for input file numbers.txt:
    27 total integers read from file

    The 3 unique integers beginning with digit 1 were
    18399 17342 19948

    The 6 unique integers beginning with digit 3 were
    39485 34710 31298 38221 35893 32791

    The 4 unique integers beginning with digit 4 were
    43928 49238 45678 43210

    The 6 unique integers beginning with digit 6 were
    64545 62987 66221 61777 66666 65432

    The 2 unique integers beginning with digit 8 were
    88888 86861

    The 1 unique integer beginning with digit 9 was
    98765

    There were 22 unique 5-digit integers in the file.
    The highest unique count in one list was 6 integers.


    My code that will follow soon displays/prints only the LAST 5-digits "group" of integers (in this case the 5-digits starting with 3). I am not sure what's wrong with my code; perhaps I am not designing it correctly. May be my calls in it are on the wrong place or I have to write all integers and then traverse it and output it (if that's the case, I am not sure how).

    Please, any directions, any ideas will be greatly appreciated.

    My code follows:
    **********************************************
    Code:
    #include <iostream> 
    #include <fstream>
    #include <iomanip>
    
    using namespace std;  
    
    const int MAX_CELLS = 10;        
    const int UNIQUE_FIVE_DIGIT = 5; 
    
    struct node
    {
        node* prev;                                            
        node* next;                                        
        int   data;                                        
    };           
    /////////////////////////////////////////////////////////////////////
    int main(int argc, char* argv[]) 
    {
        ifstream inFile;                      
        node *lists[MAX_CELLS] = { NULL };      
        int count = -1;                       
        bool result = true;                     
    
        do 
        {
    
            if ( argc != 2 ) 
            {
                cout << "Command line arguments not valid!" << endl << endl;
                result = false;
            }   
    
            if ( !argv[1] ) 
            {
                cout << "The command line arguments does not specify any filename!" << endl; 
                result = false;
            }           
    
            inFile.open(argv[1]);
    
            if ( !inFile ) 
            {
                cout << "The input data file does not exist or cannot be opened!" << endl;
                result = false;
            }   
    
            if ( result )
            {
                cout << "Results for input file " << argv[1] << ":" << endl;
                ReadInFile(inFile, lists, count);   
    
                result = false;  
            }
    
        } while ( result );
    
        system("PAUSE");  
        return 0;
    }
    ///////////////////////////////////////////////////////////////////
    void ReadInFile(ifstream& inFile, node* arrayPtr[], int& count) 
    {
        int number = 0;
        int newNumber = 0;
        int countResult = 0;
        node* p = new node;
    
        while ( inFile )   
        {
    
            inFile >> number;
            newNumber = number / 10000; 
    
            if ( !isDuplicate(arrayPtr[newNumber], number) )
            {
                    arrayPtr[newNumber] = prepend( arrayPtr[newNumber], number );
                    p = arrayPtr[newNumber];
            }
    
            count++;
        }
    
        for (int count = 0; count < 10; count++)
        {    
            arrayPtr[count] = p;
            countResult = counting(p);
        }
    
        cout << setw(7) << count << " total integers read from file" << endl << endl;
    
        inFile.close();    
    
        cout << "The " << countResult << " unique integers beginning with digit " << newNumber <<" were " << endl;
    
        displayIt(p, countResult);
    }
    /////////////////////////////////////////////////////////////////////
    void displayIt(node* p, int count) 
    {
        cout << setw(14); 
        print_list(p);
        cout << endl;
    }
    /////////////////////////////////////////////////////////////////////
    bool isDuplicate(node* top, int number) 
    {
    
        while( top != NULL )
        {
    
            if( top->data==number )
                return true;
    
            top = top->next;
        } 
    
        return false;
    }
    /////////////////////////////////////////////////////////////////////
    node* prepend(node* beginning, int number) 
    {
        node* p = new node;
    
        p->data = number;
        p->prev = NULL;
        p->next = beginning;
    
        if( beginning != NULL )
        {
            beginning->prev = p;
        }
    
        return p;
    }
    /////////////////////////////////////////////////////////////////////
    void print_list( node* beginning ) 
    {    
    
        for( node *p=beginning; p != NULL; p=p->next )
        {
            std::cout << p->data;
    
            if( p->next != NULL )
            {
                std::cout << " ";
            }
    
        }      
    }
    /////////////////////////////////////////////////////////////////////
    int counting( node* beginning ) 
    {
        int count(0);
    
        for( node *p=beginning; p != NULL; p=p->next )
        {
            ++count;
        }
    
        return count;
    }
    **********************************************

    Big thanks in advance.

    Marco

  2. #2
    Join Date
    Apr 1999
    Posts
    27,423

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by lanza View Post
    I am not sure what's wrong with my code; perhaps I am not designing it correctly. May be my calls in it are on the wrong place or I have to write all integers and then traverse it and output it (if that's the case, I am not sure how).
    Honestly, there should be no "maybes" when you write the code. Everything you code must be done with certainty that what you have written will execute properly. Everything you design must be done with complete confidence that the design works -- first on paper, and then translated to programming code.

    Of course, if the code doesn't execute properly (which is more often than not), then you debug the code using the debugger or whatever other technique (print statements, etc.) to find out where the code deviates from your initial plans. Then you fix the code according to what you've discovered by debugging, or you redo your design based on what you've discovered by debugging. That is how programming works, whether it is student or professional.
    Please, any directions, any ideas will be greatly appreciated.
    Given what was stated, have you debugged your own code?

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; December 27th, 2012 at 10:53 AM.

  3. #3
    Join Date
    Dec 2012
    Posts
    3

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Hi Paul,

    Big thanks for the reply.

    I used the debugger and so far follows most of my design (but not sure how to display all data yet):

    1) I read the data file and while it is reading it
    2) check for duplicates
    3) if it's not a duplicate then I will add into the lists based on the first digit
    4) then I counted and display it, HOWEVER
    it is displaying the last 5-digit integers (starting with digit 3) as follows:

    Results for input file 1numbers.txt:
    43 total integers read from file

    The 14 unique integers beginning with digit 3 were
    30748 30747 30746 30745 30744 30743 30742 30741 30740 30739 30738 30736
    30735 30734
    Press any key to continue . . .

    However, I am expecting it to display all data from the file (in my case I have digits starting with 1, 2, and 3 as you can see in my first/previous post).

    It's doing most of it but I was expecting it to display the other unique integers with digit 2 and ... with digit 1 as well since it is in the input file.

    I am not sure yet why.

    Big thanks.

    Marco

  4. #4
    Join Date
    Apr 1999
    Posts
    27,423

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by lanza View Post
    It's doing most of it but I was expecting it to display the other unique integers with digit 2 and ... with digit 1 as well since it is in the input file.

    I am not sure yet why.
    So you should go straight to the function that prints:
    Code:
    void print_list( node* beginning ) 
    {    
    
        for( node *p=beginning; p != NULL; p=p->next )
        {
            std::cout << p->data;
    
            if( p->next != NULL )
            {
                std::cout << " ";
            }
    
        }      
    }
    If you claim that you don't see all your output, the only conclusion is that "p" no longer points to the beginning of your list of nodes.

    This is what I mean by debugging -- somewhere along the way, you've either lost track, replaced, or did something that causes the list to either lose its contents, or you've moved the head of the list around and now it points somewhere else. How else would a seemingly simple print loop not print out the correct results, unless "beginning" has been trashed somewhere?

    So use the debugger, keep track to make sure what is happening to "beginning" to see where it goes wrong.

    Regards,

    Paul McKenzie

  5. #5
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,057

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Topic number 1 in schools really should be how to use the debugger and why you can't write any code without it. You've made the classic beginner mistake of trying to write the whole program at once and now you have to figure out which part is broken. Any of us would write one small part at a time, step through it in the debugger to make sure it's doing what we want it to, then moving on to the next part. What you need to do now is step through all your code. Make sure the nodes are being created and inserted correctly, make sure you dupe test is working correctly, then make sure you're outputting correctly. Your mistake could be anywhere. You need to debug individual functions as you go so that when something goes wrong, it's pretty easy to identify.

  6. #6
    Join Date
    Dec 2012
    Posts
    3

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Big Thanks for all of you.

    Problem solved; now I just need to figure out how this program will produce the last line of the sample output such as "The highest unique count in one list was 6 integers". In other words, what list has the highest values in it.

    Thanks.

    Marco

  7. #7
    Join Date
    May 2009
    Posts
    2,413

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by GCDEF View Post
    Topic number 1 in schools really should be how to use the debugger and why you can't write any code without it.
    I disagree. Real programmers don't use debuggers. They write correct code. And they use the Stepwise Refinement method to accomplish that.

    Debuggers are fine when you inherit a pile of crap code and need to quickly hide the bad smell. But when you write new code it should work from start to finish and you should be confident it does.

    In this case the OP should start all over and develop the code incrementally in small working steps one by one. Start with something working and make sure everything you add in works too. How hard is that really?
    Last edited by nuzzle; December 29th, 2012 at 07:52 AM.

  8. #8
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,057

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by nuzzle View Post
    I disagree. Real programmers don't use debuggers. They write correct code. And they use the Stepwise Refinement method to accomplish that.

    Debuggers are fine when you inherit a pile of crap code and need to quickly hide the bad smell. But when you write new code it should work from start to finish and you should be confident it does.

    In this case the OP should start all over and develop the code incrementally in small working steps one by one. Start with something working and make sure everything you add in works too. How hard is that really?
    I really hope you're joking.

  9. #9
    Join Date
    May 2009
    Posts
    2,413

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by GCDEF View Post
    I really hope you're joking.
    No I don't.

    It's much better to avoid errors than to look for them later.
    Last edited by nuzzle; December 29th, 2012 at 10:08 AM.

  10. #10
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,057

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by nuzzle View Post
    No I don't.

    It's much better to avoid errors than to look for them later.
    I don't know of any programmers that write perfect code on the first try every time, and I don't know of any programmers that can look at code and be absolutely positive what it's doing every time. What I'm saying, is write a small section of code, run it in the debugger to be sure it works then move on to the next piece. Proper use of the debugger is the way to avoid errors.

  11. #11
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,791

    Re: HELP Implementing Double Linked Lists as an Array of Pointers in C++

    Quote Originally Posted by nuzzle View Post
    I disagree. Real programmers don't use debuggers. They write correct code. And they use the Stepwise Refinement method to accomplish that.

    Debuggers are fine when you inherit a pile of crap code and need to quickly hide the bad smell. But when you write new code it should work from start to finish and you should be confident it does.

    In this case the OP should start all over and develop the code incrementally in small working steps one by one. Start with something working and make sure everything you add in works too. How hard is that really?
    The best and most reliable method of achieving this "stepwise refinement" is stepping through your code in a debugger and verifying that it does indeed work as you intended.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center