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 5digit 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 5digit 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: 122