1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

Insertion Sort using a Linked List

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

  1. monkey_slap

    monkey_slap New Member

    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