Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Insertion Sort using a Linked List (http://www.go4expert.com/forums/insertion-sort-using-linked-list-t10831/)

monkey_slap 27May2008 02:44

Insertion Sort using a Linked List
 
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



All times are GMT +5.5. The time now is 07:30.