Sorted Linked List

Shane McFarland (7)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
//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;
};
Shane McFarland (7)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
//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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
} 
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;
}
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
//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;
}
Shane McFarland (7)
The input sample is:
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
Shane McFarland (7)
What do I need to do so this will work? Anything will help.
Last edited on
bg5004 (1)
Did u solve your problem? if so what was wrong? I think the problem is coming somewhere within your case 'D' I took out the D statements in your input and that was the only way i could get it to compile.
Shane McFarland (7)
No, I still havent gotten it to work out.
Topic archived. No new replies allowed.