Hi Everyone,

I have been trying to post a code by I am not able to do it; I might the wrong but I am following all the rules; I don't know what else to do; please help.

I will try to copy as follows (it might works) :)

#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 and have a nice holidays.

Marco

Edited 3 Years Ago by ~s.o.s~: moved to proper forum

I am using the following input data for simplicity (via file throught command line argument):

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

The output should be logically similar to the following:

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.

Hi Everyone,

Big thanks in advance and sorry to post here in pieces; since I am new here, I was having problem posting it (sorry for the inconvenience).

Perhaps my problem is not in the code but the way I designed it.

I have some knowledge of C/C++ and am taking College Online classes. I have to/planning to take sometime next year an Advanced Data Structure class and since I think that it's not an easy subject, then I am starting to working/learning on it right now. The project I am working on it has the following requirements:

I am suppose to use struct (no STL, no classes) and implement a double linked list as an array of pointers.
My code has to read one integer at a time from the input file (integers will be separated by whitespace and the text file has 5-digit integers (10000 – 99999) ).

MY PROBLEMS (Assumption):

1) It will outputs only the last 5-digit integers (with digit 3).

In other words, it outputs data for the last/unique 5-digit integers from the file (in this case digit 3) and it's not outputing the other unique 5-digit integers data from the file such as those with starting digit 1 and 2 as it should be, based on the output (posted earlier in this post here) from the req/specs.

2) My ReadInFile function calls and check for duplicates (it's working) then, I am not sure what I do next if I read the whole data from the file and closed it, and then I will go to the list again, count it based on the first digit and display it HOWEVER I am confusing how I am going to do it. I have been trying for hours but with no success. As I mentioned before, perhaps my problem is more a matter of design then code but please let me know where are my mistakes.

Once again big thanks.

Marco

Hi,

I'm not sure where to start so I'll start from the beginning and type as I go through your code.

When checking your command-line parameters you have a series of if statements, but entry of one does not lock out the rest; this is undesire in your case as it will continue to attempt opening a file and perform other activities. You also don't need the argv[1] check that way. I am also not sure why the entire construct is in a do-while loop. Could you explain this? I've removed it for now as I didn't see the need for it. This means I've modified main to the following:

int main(int argc, char* argv[])
{
    ifstream inFile;
    node    *lists[MAX_CELLS] = { NULL };
    int      count            = -1;
    bool     result           = true;

    // Check the amount of command-line arguments.
    if (argc != 2)
    {
       cerr << "Command line arguments not valid!\n";
    }

    // A correct amount of command-line parameters were supplied.
    else
    {
        // Attempt to open the file with the file name supplied as a command-line parameter.
        inFile.open(argv[1]);

        // Opening failed.
        if (!inFile)
        {
            cerr << "The input data file does not exist or cannot be opened!\n";
        }
        // Opening was a success!
        else
        {
            cout << "Results for input file \"" << argv[1] << "\":\n";
            ReadInFile(inFile, lists, count);
        }
    }

    return 0;
}

The next point of interest seems to be the "ReadInFile" function. In the first part you're reading integers from the file, and for every integer you obtain the first digit which serves as the index for the array of linked lists you supplied to the function. You loop condition is the stream itself which will fail after it read something. So you should change it to read or otherwise change the loop itself. The "10000" you us in there is a "magic number"; I'd let that be based on a define. You defined a constant called "UNIQUE_FIVE_DIGIT" but you didn't use it yet. You could replace it with something like "pow(10, UNIQUE_FIVE_DIGIT - 1)" or something, casted to an integer. I've kept it the same for now. You also don't initialize "count" (the reference parameter) in your function. It's initialized to -1 outside, which is likely to cause errors in counting. Initialize it to 0 in the function.

You check if the number is already in the list for the list for numbers starting with that digit with the function isDuplicate, and that function seems fine. (I've only added some const keywords to the function signature)

If it doesn't exist, you add it to the list for that digit, which is fine, but i think from there things go wrong. If it is already in the list you basically skip it. But you want your program to only count unique numbers, so something will have to happen there. You could remove the number from it's digit-list as soon as you find a duplicate, but then you have the "problem" of having to remember which numbers are blacklisted. Another approach you could take is to just read every integer and put it in the correct list first, and remove duplicates from the lists after reading. I went for the first approach because I think this is what you were trying to do with 'p'. If we find a duplicate we remove it from its digit list, and add it to the list 'p' which is basically a blacklist. I've renamed 'p' to 'blacklist' to make its purpose more clear.

This means your read loop transforms as follows:

// As long as something can be read from the file..
    while (inFile >> number)
    {
        // Obtain the first digit of the read number.
        newNumber = number / 10000;

        // Only process the number if it's not in the blacklist.
        if (!isDuplicate(blacklist, number))
        {
            // This one is a duplicate of a number we thought was unique.
            if (isDuplicate(arrayPtr[newNumber], number))
            {
                // Remove the number from "arrayPtr" as it is no longer unique.
                arrayPtr[newNumber] = removeNode(arrayPtr[newNumber], number);

                // Add this number to the blacklist.
                blacklist = prepend(blacklist, number);
            }
            // It is a new number.
            else
            {
                // Add this number to the digit-list.
                arrayPtr[newNumber] = prepend(arrayPtr[newNumber], number);
            }
        }

        // Increase the total amount of numbers read.
        count++;
    }

Note that I had to add a "removeNode" function which removed an item from a list. I've tried to keep it like prepend in the sense that it returns a pointer to the new list:

// Removes the first node in "list" that has the value "value", if it exists.
// Returns a pointer to the head of the new list. (prepend-style)
node* removeNode(node* list, const int value)
{
    if (list != NULL)
    {
        // We've found the node.
        if (list->data == value)
        {
            node* rest = list->next;

             // Set the pointers of the nodes before and after the found node, if present.
            if (list->prev != NULL)
            {
                list->prev->next = list->next;
            }

            if (list->next != NULL)
            {
                list->next->prev = list->prev;
            }

            // Delete the current node.
            delete list;
            list = rest;
        }

        // Look for the node in the rest.
        else
        {
            list->next = removeNode(list->next, value);
        }
    }

    return list;
}

What you're doing next, is counting the unique values. You can do this while reading the integers, but I'll keep it the way it is now, and just "fix" it. The counter you use for the loop is called "counter" and the function also has a parameter called "counter". I recommend to avoid conflicts like these even if it goes right in this case. Also you're using '10' which is again a magic number. use the MAX_CELLS constant you defined.

You want to display the amount of elements in every list as well as their contents and you want to do that sequentially. Adding counters for the things you want to display isn't that difficult once you have the rest.

Applying all these changes results in the following 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;   // The previous entry in the list. NULL if it does not exist.
    node* next;   // The next entry in the list. NULL if it does not exist.
    int   data;   // Data contained in the this node.
};


node* prepend(node* const beginning, const int number)
{
    node* p = new node;

    p->data = number;
    p->prev = NULL;
    p->next = beginning;

    if( beginning != NULL )
    {
        beginning->prev = p;
    }

    return p;
}


bool isDuplicate(const node* top, const int number)
{
    while(top != NULL)
    {
        if(top->data == number)
        {
            return true;
        }

        top = top->next;
    }

    return false;
}


int counting(const node* const beginning)
{
    int count = 0;

    for(const node *p = beginning; p != NULL; p = p->next)
    {
        ++count;
    }

    return count;
}


void print_list(const node* const beginning)
{
    for(const node *p = beginning; p != NULL; p = p->next)
    {
        cout << p->data;

        if( p->next != NULL )
        {
            cout << " ";
        }
        else
        {
            cout << endl;
        }
    }
}

void displayIt (const node* const p)
{
    cout << setw(14);
    print_list(p);
    cout << endl;
}


// Removes the first node in "list" that has the value "value", if it exists.
// Returns a pointer to the head of the new list. (prepend-style)
node* removeNode(node* list, const int value)
{
    if (list != NULL)
    {
        // We've found the node.
        if (list->data == value)
        {
            node* rest = list->next;

             // Set the pointers of the nodes before and after the found node, if present.
            if (list->prev != NULL)
            {
                list->prev->next = list->next;
            }

            if (list->next != NULL)
            {
                list->next->prev = list->prev;
            }

            // Delete the current node.
            delete list;
            list = rest;
        }

        // Look for the node in the rest.
        else
        {
            list->next = removeNode(list->next, value);
        }
    }

    return list;
}


void ReadInFile(ifstream& inFile, node* arrayPtr[], int& count)
{
    int number      = 0;
    int newNumber   = 0;
    node* blacklist = NULL;
    count           = 0;

    // As long as something can be read from the file..
    while (inFile >> number)
    {
        // Obtain the first digit of the read number.
        newNumber = number / 10000;

        // Only process the number if it's not in the blacklist.
        if (!isDuplicate(blacklist, number))
        {
            // This one is a duplicate of a number we thought was unique.
            if (isDuplicate(arrayPtr[newNumber], number))
            {
                // Remove the number from "arrayPtr" as it is no longer unique.
                arrayPtr[newNumber] = removeNode(arrayPtr[newNumber], number);

                // Add this number to the blacklist.
                blacklist = prepend(blacklist, number);
            }
            // It is a new number.
            else
            {
                // Add this number to the digit-list.
                arrayPtr[newNumber] = prepend(arrayPtr[newNumber], number);
            }
        }

        // Increase the total amount of numbers read.
        count++;
    }

    cout << setw(5) << ' ' << count << " total integers read from file" << endl << endl;

    // Some statistic counters. Should split stuff like this to its own function at some point.
    int uniqueCount   = 0;
    int uniqueCurrent = 0;
    int highestUnique = 0;

    for (int i = 0; i < MAX_CELLS; i++)
    {
        // Count the amount of elements in the list.
        uniqueCurrent = counting(arrayPtr[i]);

        // See if this is a new hi-score.
        if (uniqueCurrent > highestUnique)
        {
            highestUnique = uniqueCurrent;
        }

        // Add up these unique numbers.
        uniqueCount += uniqueCurrent;

        // Finally show the amount of unique numbers starting with this digit..
        cout << setw(5) << ' ' << "The " << uniqueCurrent << " unique integers beginning with digit " << i << " were:\n";

        // .. and display the digits themselves.
        displayIt(arrayPtr[i]);
    }

    // Show the final statistics.
    cout << setw(5) << ' ' << "There were " << uniqueCount << " unique 5-digit integers in the file.\n"
         << setw(5) << ' ' << "The highest unique count in one list was " << highestUnique << " integers.\n";

    // Close the input file.
    inFile.close();
}


int main(int argc, char* argv[])
{
    ifstream inFile;
    node    *lists[MAX_CELLS] = { NULL };
    int      count            = -1;

    // Check the amount of command-line arguments.
    if (argc != 2)
    {
       cerr << "Command line arguments not valid!\n";
    }

    // A correct amount of command-line parameters were supplied.
    else
    {
        // Attempt to open the file with the file name supplied as a command-line parameter.
        inFile.open(argv[1]);

        // Opening failed.
        if (!inFile)
        {
            cerr << "The input data file does not exist or cannot be opened!\n";
        }
        // Opening was a success!
        else
        {
            cout << "Results for input file \"" << argv[1] << "\":\n";
            ReadInFile(inFile, lists, count);
        }
    }

    return 0;
}

This can be improved upon further, but it should answer your initial question.

Let me know when you don't understand any of it and I'll elaborate.

Good luck!

Edited 3 Years Ago by Gonbe

Hi Gonbe,

I don't know what happened but I just wrote you a lot and did a reply but all of the sudden it disappeared.

I will do it again -:)

Big thanks for your help. You are right about the loop inside main; I don't know why I did that -:)

It's kinda of late too me right now, about 3 am but I will reread your answers/comments again tomorrow and apply the changes where necessary/need to be.

I was able to work on it today and my main problem was that inside my loop I have arrayPtr[count] = p being overwritten instead of using p = arrayPtr[count]; and also I moved my call to displayIt inside the loop and etc.

Big thanks again for your help and concern.

Marco

This question has already been answered. Start a new discussion instead.