C++

Forum

 
[Help!]Linked Lists

aquariusmirky (19)
I'm working on a practice problem with linked list,
the program is supposed to read in a list of student scores and add it to a list, until input score is -1, which indicates user is done with the input.
program is supposed to print the list and number of nodes in it, and then sort all the scores into 4 lists for grades A, B, C, F, and then print each of the four lists.

for example,
for input: 23 77 89 99 67 12 65 55 44 50 99 100 50 88 76 40 -1
output would be:
SCORES: 23 77 89 99 67 12 65 55 44 50 99 100 50 88 76 40 contains 16 nodes
A_LIST: 99 99 100 contains 3 nodes
B_LIST: 89 88 contains 2 nodes
C_LIST: 77 76 conatins 2 nodes
F_LIST: 23 67 12 65 55 44 50 50 40 contains 9 nodes

right now my code keeps crashing, I am new to linked list and the topic gets me pretty confused, can someone help me figure what's the problem? Thanks!!

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
 

#include <iostream>
using namespace std;

struct Node
{
 int data;
 Node * link;
};

void get_input(Node*&head_ptr)
{
//reads in a list of exam scores (int 0-100) from the keyboard 
//and creates a linked list of integers by adding each new number to the tail end of the list. 
 int n;
// n = head_ptr->data;
 Node*temp;
 temp = head_ptr;
 cin>>n;
 while (n != -1)
 { 
   temp->link = new Node; 
   temp = temp->link;  
   temp->data = n; 
   temp->link = NULL;
   cin>>n;  
 }
 
}

void display_and_count(Node*&head_ptr)
{
//prints the original list and prints out how many nodes were on the list.
  int count=1;
  Node*next;
  next = head_ptr;
  while (next->link != NULL)
  {
   cout << next->data;
   next = next->link;
   count++;
  }
  cout<<"contains "<<count<<" nodes.";
}

void split_them_up(Node*&head_ptr, Node*a, Node*b, Node*c, Node*f)
{
//a, b, c, f, originally empty; separate x into 4 lists
// SCORES should be empty afterwards
//preserve order, each new addition made to the tail of list
  
  Node*temp;
  temp = head_ptr;
  while (temp->link != NULL)
  {     
   if (temp->data >= 90) 
   {
     a->link = temp;
     a = a->link; 
   }
   else if (temp->data >= 80) 
   {
     b->link = temp; 
     b = b->link;
   }
   else if (temp->data >= 70) 
   {
     c->link = temp; 
     c = c->link;
   }
   else
   {
     f->link = temp; 
     f = f->link;
   }
   temp = temp->link;
  }



}

int main ()
{
    Node *SCORES = NULL;
    Node *A_LIST = NULL;
    Node *B_LIST = NULL;
    Node *C_LIST = NULL;
    Node *F_LIST = NULL;

    get_input(SCORES);
    cout<<"SCORES: "; 
    display_and_count(SCORES);
    split_them_up(SCORES, A_LIST, B_LIST, C_LIST, F_LIST);
    cout<<"A_LIST: ";
    display_and_count(A_LIST);
    cout<<"B_LIST: ";
    display_and_count(B_LIST);
    cout<<"C_LIST: ";
    display_and_count(C_LIST);
    cout<<"F_LIST: ";
    display_and_count(F_LIST);   
     
}
Last edited on
aquariusmirky (19)
someone please help! thanks!
fafner (377)
It's not so easy to say without knowing what messages you get at the crash. I would change void get_input(Node*&head_ptr) to void get_input(Node*head_ptr). Also, maybe 
1
2
3
4
5
6
7
8
 
while (n != -1)
 { 
   temp->link = new Node; 
   temp = temp->link;  
   temp->data = n; 
   temp->link = NULL;
   cin>>n;  
 }

should be
1
2
3
4
5
6
7
8
 
while (n != -1)
 { 
   temp->link = new Node; 
   temp->data = n; 
   temp->link = NULL;
   temp = temp->link;  
   cin>>n;  
 }
.
closed account (D80DSL3A)
I suppose it crashes right at line 91: get_input(SCORES);
This is because you are passing a NULL pointer to the get_input(), assigning temp = head_ptr; (which is NULL) then on line 22 you do this: temp->link = new Node; . Dereferencing a NULL pointer = crash!
Keep passing head_ptr as a reference (because you need the passed pointer to change value).
You need to allocate a node to head_ptr at the start of the function.

Maybe something like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
int n;
cin >> n;
if( n == -1 ) return; // nothing to do. Return from function now.

// otherwise fill head node
if( head_ptr == NULL )
{
    head_ptr = new Node;
    head_ptr->data = n;
    head_ptr->link = NULL;
}

// now move on to the others
Node* temp = head_ptr;
cin >> n;
while (n != -1)// your version seems correct
 { 
   temp->link = new Node; 
   temp = temp->link;  
   temp->data = n; 
   temp->link = NULL;
   cin>>n;  
 }


Your split_them_up() looks faulty too (for similar reasons) but see if the above corrections will at least get the program to execute through line 93 (ie. comment out lines 94-102). Then work from there.

EDIT: Your display_and_count() won't display the last node. Can you see why?
Last edited on
aquariusmirky (19)
thanks! that's very helpful!
I modified the display_and_count() so it displays every score now. the program works fine for the "score" list (prints all scores, node count is correct), but it doesn't output right for the 4 new lists created from the original list (A_LIST, B_LIST, C_LIST, F_LIST), it only displays the last score in the list and node count is always 1, can you take a look at the spliting code and see where went wrong? Thanks!
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
 
void split_them_up(Node*&head_ptr, Node*&a, Node*&b, Node*&c, Node*&f)
{
//a, b, c, f, originally empty; separate x into 4 lists
// SCORES should be empty afterwards
//preserve order, each new addition made to the tail of list
  a = new Node;
  b = new Node;
  c = new Node;
  f = new Node;
  Node*temp;
  temp = head_ptr;
  while (temp->link != NULL)
  {     
   if (temp->data >= 90) 
   {  
     if(a == NULL)
     {
       a = new Node;
       a->data = temp->data;
       a->link = NULL;
     }
     else
     {
       a->link = new Node; 
       a = a->link;  
       a->data = temp->data; 
       a->link = NULL;
     }
   }
   else if (temp->data >= 80) 
   {
     if(b == NULL)
     {
       b = new Node;
       b->data = temp->data;
       b->link = NULL;
     }
     else
     {
       b->link = new Node; 
       b = b->link;  
       b->data = temp->data; 
       b->link = NULL;
     }
   }
   else if (temp->data >= 70) 
   {
     if(c == NULL)
     {
       c = new Node;
       c->data = temp->data;
       c->link = NULL;
     }
     else
     {  
       c->link = new Node; 
       c = c->link;  
       c->data = temp->data; 
       c->link = NULL;
     }
   }
   else
   {
     if(f == NULL)
     {
       f = new Node;
       f->data = temp->data;
       f->link = NULL;
     }
     else
     {
       f->link = new Node; 
       f = f->link;  
       f->data = temp->data; 
       f->link = NULL;
     }
   }
   temp = temp->link;
  }
aquariusmirky (19)
full code for reference:
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
 
#include <iostream>
using namespace std;

struct Node
{
 int data;
 Node * link;
};

void get_input(Node*&head_ptr)
{
//reads in a list of exam scores (int 0-100) from the keyboard 
//and creates a linked list of integers by adding each new number to the tail end of the list. 
 int n;
// n = head_ptr->data;
 
 cin>>n;
 if (n==-1) return; // do nothing
 //otherwise fill in the head node
 if (head_ptr == NULL)
 {
   head_ptr = new Node;
   head_ptr->data = n;
   head_ptr->link = NULL;             
 }
 Node*temp;
 temp = head_ptr;
 cin>>n;
 while (n != -1)
 { 
   temp->link = new Node; 
   temp = temp->link;  
   temp->data = n; 
   temp->link = NULL;
   cin>>n;  
 }
 
}

void display_and_count(Node*&ptr)
{
//prints the original list and prints out how many nodes were on the list.
  int count=1;
  Node*next;
  next = ptr;
  while (next->link != NULL)
  {
   cout << next->data <<" ";
   next = next->link;
   count++;
  }
  cout<<next->data<<"  ";
  cout<<"contains "<<count<<" nodes.";
}

void split_them_up(Node*&head_ptr, Node*&a, Node*&b, Node*&c, Node*&f)
{
//a, b, c, f, originally empty; separate x into 4 lists
// SCORES should be empty afterwards
//preserve order, each new addition made to the tail of list
  a = new Node;
  b = new Node;
  c = new Node;
  f = new Node;
  Node*temp;
  temp = head_ptr;
  while (temp->link != NULL)
  {     
   if (temp->data >= 90) 
   {  
     if(a == NULL)
     {
       a = new Node;
       a->data = temp->data;
       a->link = NULL;
     }
     else
     {
       a->link = new Node; 
       a = a->link;  
       a->data = temp->data; 
       a->link = NULL;
     }
   }
   else if (temp->data >= 80) 
   {
     if(b == NULL)
     {
       b = new Node;
       b->data = temp->data;
       b->link = NULL;
     }
     else
     {
       b->link = new Node; 
       b = b->link;  
       b->data = temp->data; 
       b->link = NULL;
     }
   }
   else if (temp->data >= 70) 
   {
     if(c == NULL)
     {
       c = new Node;
       c->data = temp->data;
       c->link = NULL;
     }
     else
     {  
       c->link = new Node; 
       c = c->link;  
       c->data = temp->data; 
       c->link = NULL;
     }
   }
   else
   {
     if(f == NULL)
     {
       f = new Node;
       f->data = temp->data;
       f->link = NULL;
     }
     else
     {
       f->link = new Node; 
       f = f->link;  
       f->data = temp->data; 
       f->link = NULL;
     }
   }
   temp = temp->link;
  }



}

int main ()
{
    Node *SCORES = NULL;
    Node *A_LIST = NULL;
    Node *B_LIST = NULL;
    Node *C_LIST = NULL;
    Node *F_LIST = NULL;
  /*  int head;
    cin >> head;
    SCORES->data = head;*/
    get_input(SCORES);
    cout<<"SCORES: "; 
    display_and_count(SCORES);
    cout<<endl;
    split_them_up(SCORES, A_LIST, B_LIST, C_LIST, F_LIST);
    cout<<"A_LIST: ";
    display_and_count(A_LIST);
    cout<<endl;
    cout<<"B_LIST: ";
    display_and_count(B_LIST);
    cout<<endl;
    cout<<"C_LIST: ";
    display_and_count(C_LIST);
    cout<<endl;
    cout<<"F_LIST: ";
    display_and_count(F_LIST);  
    cout<<endl; 
    
    system("pause");
     
}
closed account (D80DSL3A)
Here's the problem (from line 80 of your last post):
a = a->link;

a needs to remain pointing to the 1st node in the list. Same problem with b,c and f.

You can omit lines 61-64 since you are covering the 1st node creation with:
1
2
3
4
5
6
 
if(a == NULL)
{
       a = new Node;
       a->data = temp->data;
       a->link = NULL;
}
in each case.

For the subsequent Nodes in each list (in the else following the code above) use a temp* (Node* aTemp = a;) to iterate to the end of the list from Node a, then insert the new Node there.

Note: I think the last Node in the scores list will be missed because of line 67:
while (temp->link != NULL) ignores the last Node for which the data is valid but link=NULL. This is the same problem I saw with your display_and_count() earlier.
aquariusmirky (19)
fixed! thank you!!
aquariusmirky (19)
actually, more problems here, the code works for output that contains at least 4 scores, but crashes for input of less than 4 scores, can someone take a look and see why? thanks!

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 
#include <iostream>
using namespace std;

struct Node
{
 int data;
 Node * link;
};

void get_input(Node*&head_ptr)
{
//reads in a list of exam scores (int 0-100) from the keyboard 
//and creates a linked list of integers by adding each new number to the tail end of the list. 
 int n;
 cin>>n;
 if (n==-1) return; // do nothing
 //otherwise fill in the head node
 if (head_ptr == NULL)
 {
   head_ptr = new Node;
   head_ptr->data = n;
   head_ptr->link = NULL;             
 }
 Node*temp;
 temp = head_ptr;
 cin>>n;
 while (n != -1)
 { 
   temp->link = new Node; 
   temp = temp->link;  
   temp->data = n; 
   temp->link = NULL;
   cin>>n;  
 }
 
}

void display_and_count(Node*&ptr)
{
//prints the original list and prints out how many nodes were on the list.
  
  if (ptr == NULL) 
  {
  cout<<"contains 0 nodes.";      
  return;  
  }
  else
  {
  int count=1;
  Node*next;
  next = ptr;
  while (next->link != NULL)
  {
   cout << next->data <<" ";
   next = next->link;
   count++;
  }
  cout<<next->data<<"  ";
  cout<<"contains "<<count<<" nodes.";
  }
}

void split_them_up(Node*&head_ptr, Node*&a, Node*&b, Node*&c, Node*&f)
{
  
  Node*temp;
  temp = head_ptr;
  Node*atemp = NULL;
  Node*btemp = NULL;
  Node*ctemp = NULL;
  Node*ftemp = NULL;
  
  
  while (temp->link != NULL)
  {     
   if (temp->data >= 90) 
   {  
     if(a == NULL)
     {
       a = new Node;
       a->data = temp->data;
       a->link = NULL;
       atemp = a;
     }
     else
     {
       atemp->link = new Node; 
       atemp = atemp->link;  
       atemp->data = temp->data; 
       atemp->link = NULL;
     }
   }
   else if (temp->data >= 80) 
   {
     if(b == NULL)
     {
       b = new Node;
       b->data = temp->data;
       b->link = NULL;
       btemp=b;
     }
     else
     {
       btemp->link = new Node; 
       btemp = btemp->link;  
       btemp->data = temp->data; 
       btemp->link = NULL;
     }
   }
   else if (temp->data >= 70) 
   {
     if(c == NULL)
     {
       c = new Node;
       c->data = temp->data;
       c->link = NULL;
       ctemp = c;
     }
     else
     {  
       ctemp->link = new Node; 
       ctemp = ctemp->link;  
       ctemp->data = temp->data; 
       ctemp->link = NULL;
     }
   }
   else
   {
     if(f == NULL)
     {
       f = new Node;
       f->data = temp->data;
       f->link = NULL;
       ftemp = f;
     }
     else
     {
       ftemp->link = new Node; 
       ftemp = ftemp->link;  
       ftemp->data = temp->data; 
       ftemp->link = NULL;
     }
   }
   
   temp = temp->link;
  }  

  if (temp->data >= 90) 
   {  
       atemp->link = new Node; 
       atemp = atemp->link;  
       atemp->data = temp->data; 
       atemp->link = NULL;
   }
   else if (temp->data >= 80) 
   {
       btemp->link = new Node; 
       btemp = btemp->link;  
       btemp->data = temp->data; 
       btemp->link = NULL;
   }
   else if (temp->data >= 70) 
   {
       ctemp->link = new Node; 
       ctemp = ctemp->link;  
       ctemp->data = temp->data; 
       ctemp->link = NULL;
     
   }
   else
   {
       ftemp->link = new Node; 
       ftemp = ftemp->link;  
       ftemp->data = temp->data; 
       ftemp->link = NULL;
   }
}

int main ()
{
    Node *SCORES = NULL;
    Node *A_LIST = NULL;
    Node *B_LIST = NULL;
    Node *C_LIST = NULL;
    Node *F_LIST = NULL;
    
    get_input(SCORES);
    cout<<"SCORES: "; 
    display_and_count(SCORES);
    cout<<endl;
    split_them_up(SCORES, A_LIST, B_LIST, C_LIST, F_LIST);
    cout<<"A_LIST: ";
    display_and_count(A_LIST);
    cout<<endl;
    cout<<"B_LIST: ";
    display_and_count(B_LIST);
    cout<<endl;
    cout<<"C_LIST: ";
    display_and_count(C_LIST);
    cout<<endl;
    cout<<"F_LIST: ";
    display_and_count(F_LIST);  
    cout<<endl; 
    
    system("pause");
     
}
closed account (D80DSL3A)
Why are lines 148-176 there? Is this code to catch the last node that's missed by the while loop above? If so, simply replace line 74: while (temp->link != NULL) with
while (temp != NULL) and omit lines 148-176. This is the fix I was hinting at in my earlier posts.

The crash is probably occurring when the last Node in the SCORES list becomes the 1st Node in a sub-list. The above fix should correct this.

Likewise, you could omit line 58 by changing line 52 to: while (next != NULL).
aquariusmirky (19)
one more question,
the last part of the problem asks to write a sort function sorting scores in each of the lists in ascending order. i tried a lot of approaches and everything crashed now i'm really confused as to how to approach this, can anyone give me a hint?
i used to sort numbers with bubble sort somehow that does not seem like a good idea here...?

intended output: A_LIST: 92 93 95 98 99 99 100
sort scores in ascending order
Topic archived. No new replies allowed.