Need help with a Sorted Linked List

[smmcfarl]

I am trying to make a program to add, delete, and print a sorted linked list. I have tried many different things and now I am getting a Segmentation Fault so I was wondering what I am doing wrong?

Here is my code so far:

//ItemType.cxx
#include "ItemType.h"
ItemType::ItemType()
{
  id = -100;
  major = "zzzzzzz";
  exam1 = -100;
  exam2 = -100;
  exam3 = -100;
  gender = 'x';
}

ItemType::ItemType(int inId, string inMajor, int inExam1, int inExam2, int inExam3, char inGender)
{
  id = inId;
  major = inMajor;
  exam1 = inExam1;
  exam2 = inExam2;
  exam3 = inExam3;
  gender = inGender;
}
RelationType ItemType::ComparedTo(ItemType otherItem) const
{
  if (id < otherItem.id)
        return  LESS;
  else if (id  > otherItem.id)
             return  GREATER;
       else
             return  EQUAL;
}

void ItemType::GetItemFromFile(ifstream& inFile)
{
  inFile >> id >> exam1 >> exam2 >> exam3 >> major >> gender;
}

void ItemType::GetIdFromFile(ifstream& inFile)
{
  inFile >> id;
}

void ItemType::WriteItemToFile(ofstream& outFile) const
{
  outFile.setf(ios::left);
  outFile << setw(13) << id << setw(14) << exam1 << setw(11) << exam2
          << exam3 << major << setw(12) << gender << endl;
}

void ItemType::WriteInvalidItemToFile(ofstream& outFile) const
{
  outFile.setf(ios::left);
  outFile << setw(13) << id << setw(14) << exam1 << setw(11) << exam2
          << exam3 << major << setw(12) << gender
          << "  *** Invalid data" << endl; 
}

bool ItemType::ValidItem()
{
  return ((id >= MIN_ID) &&
         (id <= MAX_ID)&&
         (exam1 >= MIN_EXAM)&&
         (exam1 <= MAX_EXAM)&&
         (exam2 >= MIN_EXAM)&&
         (exam2 <= MAX_EXAM)&&
         (exam3 >= MIN_EXAM)&&
         (exam3 <= MAX_EXAM))&&
         ((gender == MALE) || (gender == FEMALE));
}

//ItemType.h
#include <fstream>
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

const int MAX_ITEMS = 10;
const int MAX_ID = 999;
const int MIN_ID = 111;
const int MAX_EXAM = 100;
const int MIN_EXAM = 0;
const char MALE = 'M';
const char FEMALE = 'F';

enum  RelationType {LESS, EQUAL, GREATER};


class ItemType
{
  public :
    ItemType();
    ItemType(int inId, string inMajor, int inExam1, int inExam2, int inExam3, char inGender);
    RelationType ComparedTo(ItemType otheritem) const;
    void GetItemFromFile(ifstream& inFile);
    void GetIdFromFile(ifstream& inFile);
    void WriteItemToFile(ofstream& outFile) const;
    void WriteInvalidItemToFile(ofstream& outFile) const;
    bool ValidItem();
  private :
    int id;
    int exam1;
    int exam2;
    int exam3;
    string major;
    char gender;
} ;


//SortedLinkedList.h
#include "ItemType.h"

struct NodeType
{
  ItemType info;
  NodeType* next;
};

// SortedType.h
class SortedType
{
 public:
  SortedType();
  ~SortedType();
  SortedType(const SortedType& otherList);
  bool IsFull() const;
  int  LengthIs() const;
  void MakeEmpty();
  void RetrieveItem(ItemType& item, bool& found);
  void InsertItem(ItemType item);
  void DeleteItem(ItemType item);
  void ResetList();
  void GetNextItem(ItemType& item);
  void Print(ofstream& outFile);

 private:
  NodeType* listData;
  int length;
  NodeType* currentPos;
};

//SortedType.cxx
#include "SortedLinkedList.h"

SortedType::SortedType()  // Class constructor
//*********************************************************
{
  length = 0;
  listData = NULL;
}
SortedType::~SortedType()
//*********************************************************
{
  MakeEmpty();
}
SortedType::SortedType(const SortedType& otherList)
  //*********************************************************
{
    NodeType* fromPtr;  // Pointer into list being copied from
    NodeType* toPtr;    // Pointer into new list being built
    if(otherList.listData == NULL)
    {
        listData = NULL;
        return;
    }
    // Copy first node
    fromPtr = otherList.listData;
    listData = new NodeType;
    listData->info = fromPtr->info;

    // Copy remaining nodes

    toPtr = listData;
    fromPtr = fromPtr->next;
    while (fromPtr != NULL)    {
        toPtr->next = new NodeType;
        toPtr = toPtr->next;
        toPtr->info = fromPtr->info;
        fromPtr = fromPtr->next;
    }
    toPtr->next = NULL;
}
bool SortedType::IsFull() const
//*********************************************************
{
  NodeType* ptr;
  ptr = new NodeType;
  if (ptr == NULL)
    return true;
  else
  {
    delete ptr;
    return false;
  }}

int SortedType::LengthIs() const
  //*********************************************************
{
  return length;
}
void SortedType::MakeEmpty()
  //*********************************************************
{
  NodeType* tempPtr;
  while (listData != NULL) // traverse list, deallocating each node in turn
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
  length = 0;
}
void SortedType::DeleteItem(ItemType item)
  //*********************************************************
{
  NodeType* location = listData;
  NodeType* tempLocation;

  // Locate node to be deleted.
  if (item.ComparedTo(listData->info)== EQUAL)
  {
    tempLocation = location;
    listData = listData->next;          // Delete first node.
  }
  else
  {
    while (!((item.ComparedTo((location->next)->info))== EQUAL))
      location = location->next;

    tempLocation = location->next;
    location->next = (location->next)->next;
  }
  delete tempLocation;
  length--;
}
void SortedType::ResetList()
  //*********************************************************
{
  currentPos = NULL;
}
void SortedType::RetrieveItem(ItemType& item, bool& found)
  //*********************************************************
{
  bool moreToSearch;
  NodeType* location;

  location = listData;
  found = false;
  moreToSearch = (location != NULL);

  while (moreToSearch && !found)
  {
    switch(item.ComparedTo(location->info))
    {      case GREATER:
        location = location->next;
        moreToSearch = (location != NULL);
        break;
      case EQUAL:
        found = true;
        item = location->info;
        break;

      case LESS:
        moreToSearch = false;
        break;
    }
  }
}
void SortedType::InsertItem(ItemType item)
//***************************************************
{
  NodeType* newNode;  // pointer to node being inserted
  NodeType* predLoc;  // trailing pointer
  NodeType* location; // traveling pointer
  bool moreToSearch;

  location = listData;
  predLoc = NULL;
  moreToSearch = (location != NULL);
  // Find insertion point.
  while (moreToSearch)
  {
    if(item.ComparedTo(location->info) == GREATER)
      {
      predLoc = location;
      location = location->next;
      moreToSearch = (location != NULL);
} 
else
moreToSearch = false;
}
// Prepare node for insertion newNode = new NodeType;
newNode->info = item;
// Insert node into list.
if (predLoc == NULL) // Insert as first
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}
void SortedType::GetNextItem(ItemType& item)
//*********************************************************
{
if (currentPos == NULL) //Wrap at end of list currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
}

void SortedType::Print(ofstream& outFile)
//*********************************************************
{
currentPos = listData;
while(currentPos != NULL)
{
currentPos ->info.WriteItemToFile(outFile);
currentPos = currentPos->next;
}
}

//main
#include "SortedLinkedList.h"

int main()
{
  ifstream inFile;
  ofstream outFile;
  inFile.open("in.data");
  outFile.open("out.data");
  if(inFile.fail() || outFile.fail())
  {
    outFile << "Input or Output file FAILED!" << endl;
  }
  SortedType sort;
  ItemType item;
  char command;
  bool found;
  string major; 
 char gender;

  sort.MakeEmpty();
  outFile << "<~~~~~~~~~~~~~~~~~ GPA Report ~~~~~~~~~~~~~~~~~~~~~~>" << endl << endl;

  inFile >> command;
  while(inFile)
  {
    switch (command)
    {
      case 'A':
      item.GetItemFromFile(inFile);
      if(item.ValidItem())
        {
          if(!sort.IsFull())
            sort.InsertItem(item);
          else
            outFile << "~ List is Full! No Add!" << endl;
        }
      else
         item.WriteInvalidItemToFile(outFile);
           break;
         case 'D':
         item.GetIdFromFile(inFile);
         sort.RetrieveItem(item, found);
         if(!sort.LengthIs() == 0)
           {
             if(found);
               {
                 sort.DeleteItem(item);
               }
           }
         Else
            outFile << "List is empty! No Delete!" << endl;
            break;
         case 'P':
         if(sort.LengthIs()>0)
           {
             outFile.setf(ios::fixed);
             outFile.setf(ios::showpoint);
             outFile.precision(2);
             outFile.setf(ios::left);
             outFile << "STUDENT ID   Exam1   Exam2   Exam3   MAJOR       SEX" << endl;
             outFile << "----------   -----   -----   -----   -----       ---" << endl;
             sort.Print(outFile);
          }
         else
            outFile << "~ List is empty! No Print!" << endl;
            break;
    }
    inFile >> command;
  }
    outFile << "~~~ END ~~~" << endl;
    return 0;
}

Thanks for the help in advance.

[smmcfarl]

This is an input sample for the program:
A 999 79 83 86 I F
A 123 87 78 99 C M
D 999
D 123
D 333
P
A 868 88 100 94 C M
A 756 71 81 91 I F
A 222 82 79 99 C M
A 460 99 77 101 I M
A 1000 77 98 56 C F
D 222
P

[smmcfarl]

Can anyone help with a little advice on what I need to change?

[nezachem]

Run your program in a debugger. It will show you exactly where the segfault occurs, along with the function call sequence which lead to it. Usually it is more than enough to pinpoint the problem.

[smmcfarl]

What kind of debugger should I us?

[nezachem]

Depends on your development environment. Every IDE I know has one. If you calling gcc from the command line, then use gdb.

[smmcfarl]

I still can't get it to work any other suggestions?

[smmcfarl]

I still can't get anything to work and it still is giving me a Segmentation Fault...could someone please help by looking at my code and explaining what I am doing wrong???

[raptr_dflo]

That's a lot of code to ask us to pore over by hand, rather than doing what was already asked. If you don't know how to use the debugger for your development environment, then start by inserting lines like cout << "Here #1" << endl; into your main(), and see how far it gets before you get the Segmentation Fault. Once you've narrowed it down to a particular function call, you can start outputting more detailed information, and/or inserting output lines within the function.

That said, I started following the flow in main(), looks like sort.MakeEmpty() is fine, but after that, you call this absurd sort.IsFull() function which wastefully allocates and frees a node, just to see if it can. The point of a linked-list is that there is no concept of "full". It can grow until the system runs out of memory, which is what you're in fact testing. Instead, it is more practical simply to allocate the node within the Insert function, and if you fail, return a value that indicates failure. Thus bool InsertItem(args) rather than void InsertItem(args) .

I then looked for where you allocate the -actual- node you're going to add to the list in InsertItem() and discovered you've commented out the allocation at line 151 of SortedType.cxx. There's your first problem.

Hopefully, this has not only solved your immediate issue, but given you some insight into how to debug your own programs! :)

[smmcfarl]

Alright thank you that worked out and it is finally working.

[raptr_dflo]

Excellent! Please mark the thread as "solved". :)