1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Insertion Sort using a Linked List

Discussion in 'C++' started by monkey_slap, May 26, 2008.

  1. monkey_slap

    monkey_slap New Member

    Joined:
    May 26, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    I ran into a roadblock developing my code for an assignment to sort a linked list as it is entered (insertion sort). We've had sketchy classes lately so the idea of linked lists is really rough for me at the moment because it's a little hard to understand. This assignment was completed before without the sort, but now with the sort I am encountering a lot of problems. So far my program builds without error, but after the head is declared and values are entered, the next value causes a the program to crash. I assume it is because of the SortList and/or Swap functions I've inserted. Without these functions the program works just fine.

    Code:
    #include<iostream>
    using namespace std;
    // -------------------------------------------------------------
    class Node {
    public: Node* next;   // points to next node
            int identification; //data in node
            int length; //data in node
            int width; //data in node
            int height; //data in node
    };
    // -------------------------------------------------------------
    void DisplayResults (Node* current) {
        if ( ! (current == NULL) ) { //loop output
            cout << current -> identification
                 << "\t"
                 << current -> length
                 << "\t"
                 << current -> width
                 << "\t"
                 << current -> height
                 << endl;
            current = current -> next; //next node
            DisplayResults (current); } //loop output
    return; }// DisplayResults
    // -------------------------------------------------------------
    void Swap(Node* current, Node* nextNode) {
        Node* swap; //temp storage for value
        Node* swapNext; //temp storage for link
        swapNext = current->next;
        current->next = nextNode->next;
        nextNode->next = swapNext;
        swap = current;
        current = nextNode;
        nextNode = swap;
    return; }// Swap
    // -------------------------------------------------------------
    void SortList(int identification, int length, int width, int height, Node* current, Node* &head) {
       Node* nextNode = current->next;//for comparison of node after current
       current = head;
       while(current != NULL) { //loops through the list
           if(current->identification < nextNode->identification)//checks if current is less than next for ID
               Swap(current, nextNode);//executes swap function to switch nodes
           current = current->next; //next node
       }//loops through the list
    return; }// SortList
    // -------------------------------------------------------------
    void BuildFirstNode (int &identification, int &length, int &width, int &height,
                         int &sumCars, Node* &head,  Node* &current,
                         Node* &pointer) {
       cout << "Please enter Box Car ID number (-1 to exit): ";
       cin >> identification;
       if( identification != -1){  // test if sentinel
           cout << "Please enter car " //input for length
                << identification
                << "'s length: ";
          cin >> length;
          cout << "Please enter car " //input for width
                << identification
                << "'s width: ";
          cin >> width;
          cout << "Please enter car " //input for height
                << identification
                << "'s height: ";
          cin >> height;
          pointer = new Node; //creates new node for data
          pointer -> identification = identification; //the following assigns data value
          pointer -> height = height;
          pointer -> width = width;
          pointer -> length = length;
          pointer -> next = NULL; //sets next node to NULL
          head = pointer;
          // set current to point to first node in list
          current = head;       // Sets first value to head
          sumCars = sumCars + 1;}//test if sentinel
       return; }// BuildFirstNode
    // -------------------------------------------------------------
    void Build (int identification, int length, int width, int height, int &sumCars,
                Node* current, Node* pointer, Node* &head) {
       cout << "Please enter Box Car ID number (-1 to exit): ";
       cin >> identification;
       if( identification != -1){  // test if sentinel
           cout << "Please enter car " //input for length
                << identification
                << "'s length: ";
          cin >> length;
          cout << "Please enter car " //input for width
                << identification
                << "'s width: ";
          cin >> width;
          cout << "Please enter car " //input for height
                << identification
                << "'s height: ";
          cin >> height;
          pointer = new Node; //creates new node for data
          pointer -> identification = identification; //the following assigns data value
          pointer -> height = height;
          pointer -> width = width;
          pointer -> length = length;
          pointer -> next = NULL; //sets next node to NULL
          sumCars = sumCars + 1;  //sum adds up per loop
          SortList(identification,length,width,height,current,head);
          Build (identification, length, width, height, sumCars, current, pointer,head);
          // recursive call to build another Node
       }  // test if sentinel
       return; }//Build
    // -------------------------------------------------------------
    void DisplayInformation( ) {
       cout << "Assignment Number: 8"
            << endl
        << "Name: Ryan Nystrom"
        << endl
        << "Student ID: M03054661"
        << endl
        << endl;
    return; }// DisplayInformation
    // -------------------------------------------------------------
    void DisplayChartTitle( ) {
        cout << "CAR ID\t"
             << "LENGTH\t"
             << "WIDTH\t"
             << "HEIGHT"
             << endl
             << "------\t"
             << "------\t"
             << "-----\t"
             << "------"
             << endl;
    return; }// DisplayChartTitle
    // -------------------------------------------------------------
    void SumValues(Node* current, int &sumLength, int &sumWidth, int &sumHeight) {
       if ( ! (current == NULL) ) { //loop output
          sumLength = sumLength + current -> length;
          sumWidth = sumWidth + current -> width;
          sumHeight = sumHeight + current -> height;
          current = current -> next; //next node
          SumValues(current,sumLength,sumWidth,sumHeight);
       }//loop output
    return; }//SumValues
    // -------------------------------------------------------------
    void AverageValues(int sumLength,int sumWidth, int sumHeight, int averageLength,
                       int averageWidth, int averageHeight, int &sumCars) {
       averageLength = sumLength/sumCars;
       averageWidth = sumWidth/sumCars;
       averageHeight = sumHeight/sumCars;
    return; }// AverageValues
    // -------------------------------------------------------------
    int main ( ) {
        Node* pointer;
        Node* current;
        Node* head;
        int sumCars,length,width,height,identification;
        int sumLength = 0;
        int sumWidth = 0;
        int sumHeight = 0;
        int averageLength = 0;
        int averageWidth = 0;
        int averageHeight = 0;
        BuildFirstNode(identification,length,width,height,sumCars,head,current,pointer);
        Build(identification,length,width,height,sumCars,current,pointer,head);
        DisplayChartTitle( );
        DisplayResults(current);
        SumValues(current,sumLength,sumWidth,sumHeight);
        AverageValues& #40;sumLength,sumWidth,sumHeight,averageLength,averageWidth,averageHeight,sumCar
    s);
        cout << endl
             << "The average length is: "
             << averageLength
             << endl
             << "The average width is: "
             << averageWidth
             << endl
             << "The average height is: "
             << averageHeight
             << endl;
    return 0; }// main
     

Share This Page