C++ Link List Program Input file is LinkNbrs.dat. Text File located: http://past

Question

C++ Link List Program

Input file is LinkNbrs.dat. Text File located: http://pastebin.ca/3391307

I have a list of numbers that I need to know two things, what numbers I have and how many of each number do I have in the list. So you are to read in each number and add the number to an ordered link list. Now, if you are adding a number to the list and you find that number, then you will just count it. If you do not find the number in the link list, then you will add a new node to the link list with the new number and set the count to one.

The structure/class will have three fields, the number, a counter. The counter is used to keep count of how many of this number exist and of course a link field.

Print out the values and their counts say 5 per line.

   example     5 – 22   8 – 15   13 – 5 22 – 3 25 – 18   where the 5 is the number and 22 is its count (ie there were 22 number 5’s in the list). Label output please.

Print out the sum and average of the set of input values.

Print out the number of nodes in the link list.

Explanation / Answer

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <fstream>

class LListRec { // this is a double linked list, I added the prev field so I could figure out how to do it
   public:
       int value;
       int count;
       LListRec *next;
       LListRec *prev;
       LListRec() { // I added a default constructor so I didn't have to initialize in the newNode() function
           next = NULL;
           prev = NULL;
           value = 0;
           count = 1;
       }
};

typedef LListRec *Node; // Nodes are pointer variables to LListRec objects
Node LIST_HEAD; // global for tracking list head

Node newNode() {
   return new LListRec(); // You have to use the struct name here and not the sugar
}

void insert(int v) { // inserts each value in order, does not increment counter
   Node   c = NULL,
           p = NULL,
           temp = NULL;

   if (LIST_HEAD == NULL) { // first item in list             
       LIST_HEAD = newNode();
       LIST_HEAD->value = v;
   }
   else {
       c = LIST_HEAD;
       while (c != NULL && v > c->value) {
           p = c;
           c = c->next;
       }
       // loop has fallen out, temp = address of new LListRec, p = the address to insert temp after, c = address to insert temp before
       if (c == LIST_HEAD) { // new item needed at the beggining of list, also LIST_HEAD needs to be reassigned
           temp = newNode();
           temp->value = v;
           LIST_HEAD = temp;
           temp->next = c;
           c->prev = temp;
       }
       else if (c == NULL) { // new item needed at end of list
           temp = newNode();
           temp->value = v;
           p->next = temp;
           temp->prev = p;
       }
       else { // new item needed in between two items, link up between p and c
           temp = newNode();
           temp->value = v;
           p->next = temp;
           temp->next = c;
           temp->prev = p;
           c->prev = temp;
       }
   }
}

void insertOrCount(int v) { // inserts only new values, if value is already present, does not create node, simply increments counter
   Node   c = NULL,
           p = NULL,
           temp = NULL,
           comp = LIST_HEAD; // used to check for duplicates
   bool insertThis = true;

   if (LIST_HEAD == NULL) { // first item in list             
       LIST_HEAD = newNode();
       LIST_HEAD->value = v;
   }
   else {
       c = LIST_HEAD;

       while (comp) { // check for any duplicates
           if (comp->value == v) {
               insertThis = false;
               comp->count++;
           }
           comp = comp->next;
       }

       while (c != NULL && v > c->value) {
           p = c;
           c = c->next;
       }

       // loop has fallen out, temp = address of new LListRec, p = the address to insert temp after, c = address to insert temp before
       if (c == LIST_HEAD && insertThis) { // new item needed at the beggining of list, also LIST_HEAD needs to be reassigned
           temp = newNode();
           temp->value = v;
           LIST_HEAD = temp;
           temp->next = c;
           c->prev = temp;
       }
       else if (c == NULL && insertThis) { // new item needed at end of list
           temp = newNode();
           temp->value = v;
           p->next = temp;
           temp->prev = p;
       }
       else { // new item needed in between two items, link up between p and c
           if (insertThis) {
               temp = newNode();
               temp->value = v;
               p->next = temp;
               temp->next = c;
               temp->prev = p;
               c->prev = temp;
           }
       }
   }
}

void printList() {
   Node c;
   c = LIST_HEAD;
   int i = 1;
   while (c) {
       std::cout << c->value << " - " << c->count;
       if (i % 5 == 0) { std::cout << std::endl; }
       else { std::cout << ", "; }
       c = c->next;
       i++;
   }
   std::cout << std::endl;
}

int rng(int min, int max) // returns rand integer between min and max
{
   int rangeVal = (max - min) + 1;
   return (rand() % rangeVal) + min;
}

int main() {
   std::ifstream inFile;
   inFile.open("LinkNbrs.dat");
   if (!inFile) { std::cout << "Error opening file..."; }
   int x; // integer to read in

   /*
   //For testing...
   srand(30);

   for (int i = 1; i <= 10000; i++) {
       int random = rng(0, 50);
       std::cout << random << " ";
       insertOrCount(random);  
   }
   */
  
   while (inFile >> x) {
       insertOrCount(x);
   }

   std::cout << "Linked List Functions ";
   printList();

   inFile.close();
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.