[lanza]

Hi Everyone,

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) ).

For each integer the program reads, it should:

1) Keep track of the total number of integers read.

2) Determine which double linked list the integer belongs in, using the first digit of the
integer.

3) There will be a cell in an array of pointers for each possible digit, 1 – 9. The program
will determine which index to use by determining the first digit of each 5-digit integer.

4) Only unique integers should be inserted into each list (no duplicates). So the next step
will be to check if the integer is already in the double linked list that corresponds to that
starting digit.

5) If the integer is not yet in the list, the program should add the integer to the top
(beginning) of the appropriate double linked list (i.e. only add integers that are not
already on the list).

6) About displaying it..., I worry about it later.

Can you please help me with the following questions:

1) Am I initializing my double linked lists (array of pointers) correctly inside the function void initializeLists(node*[])? In other words, am I "really initialize each pointer in the array to NULL, to represent 10 empty lists?

2) Inside the function void ReadInFile(ifstream&, node*[], int&) I am trying to do steps #2-#3. My code performs a simple div to determine which list the number goes in.
Based on the result of this number, I believe that I am suppost to check if it's duplicate and then add it into the list (list 1, list 2, and so on).

a) I am passing to the function isDuplicate(arrayPtr[0], number) but "something" tells me that I should not pass the array this way and I am not sure how I would do that?

My bool isDuplicate(node* top, int number) function does not work properly (it does not "avoid" duplicates" as it's suppose to do) and I don't know why?

3) Does my void addNumbers(node* &top, int number) make sense?

*********************************************************************************************
MY CODE FOLLOWS (my compiler is MS Visual Studio 2005):

 
#include <iostream>
 #include <fstream>
 #include <iomanip>

using namespace std;

const int MAX_CELLS = 10; // maximum number of cells
 const int UNIQUE_FIVE_DIGIT = 5; // five digits

struct node
 {
 node* prev; // pointer to previous (backward) node in list
 node* next; // pointer to next (forward) node in list
 int data; // node data
 };

// function prototypes
 void initializeLists(node*[]); // to initialize lists
 void ReadInFile(ifstream&, node*[], int&); // read integers from input file into the double linked lists and keep track of its counting
 bool isDuplicate(node*, int); // to check for duplicates into the lists
 void addNumbers(node* &list, int); // to add number into the list
 void displayResults(node*); // display double linked lists information on the screen
 //********************************************************************* 
 int main(int argc, char* argv[])
 {
 ifstream inFile; // to handle the file
 node *lists[MAX_CELLS] = { NULL }; // array of pointers to hold list data
 int count = 0; // for counting
 bool result = true; // to control the loop

 do
 {
 if ( argc != 2 ) // check for command line arguments
 {
 cout << "Command line arguments not valid!" << endl << endl;
 result = false;
 } 

 if ( !argv[1] ) // check if the user type a filename
 {
 cout << "The command line arguments does not specify any filename!" << endl;
 result = false;
 } 

 inFile.open(argv[1]);

 if ( !inFile ) // check if the file exist and can be opened
 {
 cout << "The input data file does not exist or cannot be opened!" << endl;
 result = false;
 } 

 if ( result )
 {
 initializeLists(lists);
 ReadInFile(inFile, lists, count);
 
 cout << "Results for input file " << argv[1] << ":" << endl << endl;
 displayResults(lists[1]);
 result = false;
 }

 } while ( result );

 system("PAUSE");
 return 0;
 }
 //********************************************************************* 
 void initializeLists(node* arrayPtr[])
 {
 node* current = new node;

 if( current == NULL )
 {
 cout << "Error - out of heap space!" << endl << endl;
 return;
 }
 else
 current = NULL; 

 for ( int count = 0; count < MAX_CELLS; count++ )
 {
 arrayPtr[count] = current;
 }
 }
 //*************************************************************************
  void ReadInFile(ifstream& inFile, node* arrayPtr[], int& count)
 {
 int number = 0;
 int newNumber = 0;
 bool check = false;
 node *listTop = NULL;
 arrayPtr[0] = new node; arrayPtr[0]->data = 0; arrayPtr[0]->prev = NULL; arrayPtr[0]->next = NULL;
 arrayPtr[1] = new node; arrayPtr[1]->data = 0; arrayPtr[1]->prev = NULL; arrayPtr[1]->next = NULL;
 arrayPtr[2] = new node; arrayPtr[2]->data = 0; arrayPtr[2]->prev = NULL; arrayPtr[2]->next = NULL; 

 while ( inFile )
 {
 inFile >> number;
 count++;
 newNumber = number / 10000; 

 // if the number is 1 goes to 1
 // if the number is 2 goes to 2

 if ( newNumber == 1 )
 {
 if ( !isDuplicate(arrayPtr[0], number) )
 {
 addNumbers(listTop, number);
 cout<< listTop->data << endl;
 }
 } 

 if ( newNumber == 2 )
 {
 if ( !isDuplicate(arrayPtr[1], number) )
 {
 addNumbers(listTop, number);
 cout<< listTop->data << endl;
 }
 } 

 if ( newNumber == 3 )
 {
 if ( !isDuplicate(arrayPtr[2], number) )
 {
 addNumbers(listTop, number);
 cout<< listTop->data << endl;
 }
 }

 if ( !inFile.eof() )
 count++;
 } 

 inFile.close();
 }
 //*********************************************************************
 bool isDuplicate(node* top, int number)
 {
  if ( currNode == NULL )
 return false;
 else
 {
 while ( currNode->next != NULL )
 {
 if ( number == currNode->data )
 return true;
 }
 currNode = currNode->next;
 }
 return false; */ 

 int i = 0;
 for ( i = 0; i < MAX_CELLS; i++ ) // next, prev ???
 {
  node* head = top;

 while ( head != NULL )
 {
 if ( head->data == number )
 return 1; // it was one
 head = head->next;
 }
 }
 return 0; // it was 0
 }
 //*********************************************************************
  void addNumbers(node* &top, int number)
 {
 node *currNode = new node;
 currNode->data = number;

 currNode->next = NULL;
 currNode->prev = currNode;
 top = currNode;
 }

I really appreciate your help.
Marco

Attached File(s)

•  numbers.txt (615.23K)
  Number of downloads: 39

[NathanMullenax]

It looks like initializeLists is totally unnecessary, as all of the list pointers are already initialized to NULL by the first line of your main() function, which is what you want. Otherwise, you wouldn't be able to tell the difference between a list of length 1 and list of length 0.

Also, I believe your addNumbers is adding to the end of the list instead of the beginning. Something like this would work to add to the beginning of the list.

Spoiler

// called like arrayPtr[n] = prepend( arrayPtr[n], v );
node * 
prepend( node * beginning, int v )
{
    node * p = new node;
    p->data = v;
    p->prev = NULL;
    p->next = beginning;
    if( beginning != NULL )
    {
        beginning->prev = p;
    }
    return p;
}

The signature for isDuplicate is fine, but it should only need one while loop to do its work of search for a number forward through the list (since the function is always passed the beginning of the list).

Something like this would work:

Spoiler

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

One final note: in the ReadInFile function, once you find the digit 'n', the appropriate list is simply list[n-1], and there should only be 9 of them (0..8) for the corresponding digits (1..9).

This means you don't need an if block for each digit. Hope this helps. Good luck!

[lanza]

Hi NathanMullenax,

Big Thanks for the fast reply. I am working on it.

Once again, big thanks for the help.

Marco

[lanza]

Hi,

Once again big thanks for the help.

I am quoting about the lists as follows:

One final note: in the ReadInFile function, once you find the digit 'n', the appropriate list is simply list[n-1], and there should only be 9 of them (0..8) for the corresponding digits (1..9).

If I want to count the number of digits/integers added into each list (in my case I have lists starting with digit 1; with digit 2 ... 9).

1) How do I count it and display it, by using "list[n-1]"?

In other words I would like to display it like the following:

The 3 unique integers beginning with digit 1 were 12345 17335 19222
The 2 unique integers beginning with digit 3 were 39485 34710
... ando so on

3) Do I have to read the file again to do it or can I do it from my array of pointers?

I assume that I will have to count the integers using "a forward-pointing links" as it traverse the list and display it but I am not sure how it's done, any idea please?

And then do it "backwardly-pointing links" as it will be pointed to the last node, any ideas please?

4) How do I count the "unique-digit integer" in each list, by summing as it traverse, any idea please?

My new code follows:

int main(int argc, char* argv[])
{
	ifstream inFile;                      // to handle the file
	node *lists[MAX_CELLS] = { NULL };    // array of pointers to hold list data	
	int count = -1;                       // for counting
	bool result = true;                   // to control the loop

	do 
	{
		if ( argc != 2 ) // check for command line arguments
		{
			cout << "Command line arguments not valid!" << endl << endl;
			result = false;
		}	

		if ( !argv[1] ) // check if the user type a filename
		{
			cout << "The command line arguments does not specify any filename!" << endl; 
			result = false;
		}	     	

		inFile.open(argv[1]);
		
		if ( !inFile ) // check if the file exist and can be opened
		{
			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 totalCount = 0;
	    
    while ( inFile )   
	{
		inFile >> number;
		newNumber = number / 10000;	

		if ( !isDuplicate(arrayPtr[newNumber], number) )
		{
			totalCount++; // good count with no duplicates
			arrayPtr[newNumber] = prepend( arrayPtr[newNumber], number );	
		}	
		count++;
	}	
	
	inFile.close(); 

	display(arrayPtr, count);
}

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;
    }
	
//	cout<< p->data << endl;
    
	return p;
}

void display(node* lists[], int totalCounter)
{
	int uniqueDigOne = 0, digOne = 1;

	cout << setw(7) << totalCounter << " total integers read from file" << endl << endl;	
	cout << "The " << uniqueDigOne << " unique integers beginning with digit 1 were " << endl << setw(4) << digOne << endl;
}

Once again, big thanks.

Marco

[NathanMullenax]

You definitely don't need to read the file again, since you already have the lists of numbers loaded.
The code for printing a list and counting a list should be nearly identical: you just take a pointer to the beginning of the list, and repeatedly follow its next pointer until you hit a NULL.

Alternatively, since you are already counting while you are loading, you could create an array of integers to store the unique count for each digit and update it during the loading process.

Note: the signature for prepend is a little weird: the parameter 'node *& beginning' is something you might use for modifying the contents of a pointer (i.e., the address that it points to). Since you're not doing that it should just be 'node * beginning'. In the two functions below, I've used a 'pointer to a const node' because I'm expressly not doing anything to the value being pointed other than reading it. It's generally good to be explicit about this sort of thing; it will help you find errors at compile time instead of later at run time.

Spoiler

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

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

Hope this helps. Thanks.

[NathanMullenax]

Correction (now that I've thought about it for a minute):

A pointer to a reference is simply a pointer, so the '&' in something like:

void
doSomething( node * &p )
{
}

Is saying p is a pointer to the address of a parameter, which is redundant because a pointer is already the address of the parameter. On the other hand, if you had written:

void
doSomething( node & *p )
{
    p = new node;
}

You would have a reference to a pointer, which means you could change what the pointer pointed to and it would have effect outside of the function. This is called double indirection.

Scratch all of that. I'm an idiot: the second one ain't even legal. The first one is what you would use for modifying the pointer. I had my associativity wrong. The first one is a 'reference to a pointer'.

This post has been edited by NathanMullenax: 30 September 2012 - 10:08 AM

[lanza]

NathanMullenax, on 30 September 2012 - 09:36 AM, said:

You definitely don't need to read the file again, since you already have the lists of numbers loaded.
The code for printing a list and counting a list should be nearly identical: you just take a pointer to the beginning of the list, and repeatedly follow its next pointer until you hit a NULL.

Alternatively, since you are already counting while you are loading, you could create an array of integers to store the unique count for each digit and update it during the loading process.

Note: the signature for prepend is a little weird: the parameter 'node *& beginning' is something you might use for modifying the contents of a pointer (i.e., the address that it points to). Since you're not doing that it should just be 'node * beginning'. In the two functions below, I've used a 'pointer to a const node' because I'm expressly not doing anything to the value being pointed other than reading it. It's generally good to be explicit about this sort of thing; it will help you find errors at compile time instead of later at run time.

Spoiler

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

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

Hope this helps. Thanks.

######################################################

Hi NathanMullenax and Everyone,

Once again big thanks for your help.

I am trying to display the integers numbers in the double linked list but it's "kinda repeat the numbers". Perhaps I am calling it from the wrong place and am passing the wrong argument.

I am calling it from prepend as follows:

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;
    }

	print_list(p);	
	//cout<< p->data << endl;
    
	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 << endl;
	        }
	    }
	   std::cout << endl;
}

######################################################
If I use the commented cout inside the prepend function, it prints/display all integers from the file; however by using the print_list function it displays the following:
Results for input file numbers.txt:
20007
20008
20007
20009
20008
20007
20010
20009
20008
20007
20012
20010
20009
20008
20007
...
######################################################
INPUT FILE:
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
...
######################################################

My plan is to print/display it as separated pieces of data on the screen from each double linked list and the total numbers of each. In other words, counting for each double linked list (with digits 1, digits2 - 9) and then displaying each list with its numbers and the total of it.

Big thanks.

Marco

[NathanMullenax]

It looks like everything is working--you're just calling print_list from the wrong place. It's being called every time a new integer is added to a list instead of just once when the list is completely built.

If you put a 'cout<<"print_list\n";' at the top of the print_list function, you would instead see this:

Quote

print_list
20007
print_list
20008
20007
print_list
20009
20008
20007
print_list
20010
20009
20008
20007
print_list
20012
20010
20009
20008
20007
...

The count and print functions should be called (once per digit) in their own loop after all of the reading and list building is done. Thanks.

[lanza]

NathanMullenax, on 02 October 2012 - 07:44 AM, said:

It looks like everything is working--you're just calling print_list from the wrong place. It's being called every time a new integer is added to a list instead of just once when the list is completely built.

If you put a 'cout<<"print_list\n";' at the top of the print_list function, you would instead see this:

Quote

print_list
20007
print_list
20008
20007
print_list
20009
20008
20007
print_list
20010
20009
20008
20007
print_list
20012
20010
20009
20008
20007
...

The count and print functions should be called (once per digit) in their own loop after all of the reading and list building is done. Thanks.

Hi NathanMullenax,

Your explanation really helped me a lot since I am trying to not only code but understand what's going on as well. Your explanation is clear and concise.

Big thanks.

Marco
P.S.: I am doing it while I can, as right now, besides taking an online advanced math class (not easy and very time consuming), I am also have to work as well otherwise I can survive the world we live in - once again, big thanks.