macOS insertion sort linked list in C

[prostuff1]

I am having a hella a time with this and I can not figure out why.

Here is what I am trying to do:
I have a C struct that has a pointer to the next node and then all the data types it holds. I am trying to do an insertion sort based on the snew->total.

I have this:

void insert_student (struct student * head, struct student * snew) 
{
	struct student * child;
	struct student * parent;
	child = (struct student *) malloc(sizeof(struct student));
	parent = (struct student *) malloc(sizeof(struct student));
	
	if(head->next != NULL)
	{
		for(parent=head,child=head->next; child!=NULL && child->total<snew->total; parent=child,child=child->next);
		parent->next = snew;
		snew->next = temp;
	}
	else
	{
		head->next = snew;
	}	
}

struct student *head is the first element in the linked list and struct student *snew is what I am trying to insert into the linked list.

The student struct looks like this:

struct student {struct student * next; char name[20]; int midterm; int final; int total; char grade; };

I am also trying to print the linked list after it has been created and I think I have that right but might as well put it up while I am doing this:

void report_grades(struct student * head) 
{
	struct student *temp;
	temp = (struct student *) malloc(sizeof(struct student));
	
	printf("Name\tMidterm\tFinal\tTotal\tGrade\n");
	for(temp=head; temp!=NULL; temp=temp->next)
	{
		printf("%s \t%i \t%i \t%i \t%c", temp->name, temp->midterm, temp->final, temp->total, temp->grade);
	}
}

Any guidance is appreciated!!

 

[jpyc7]

Doesn't look like your first function should compile, because of a non-declared variable called "temp". In fact, it looks like the code inside the "if clause" should say "snew->next = child;"

Also you can delete the "malloc" lines, since I think the nodes are already allocated and you're just passing in the pointers.

It is a little bit strange that you always have a "head" node. If you allowed your head pointer to be NULL, then you could have a truly empty list. As it is, I think the case of an empty list is exactly one node. That is more customary with some types of tree structures where there can be a "root" node.

Again, you don't need the "malloc" in your print function.

 

[garethlewis2]

Your insert function needs the pointer to head to be defined as

struct student **head.

You have a pointer to a struct, you need a pointer to a pointer to a struct. You need to reassign the head variable on the heap, not the stack.

 

[prostuff1]

Doesn't look like your first function should compile, because of a non-declared variable called "temp". In fact, it looks like the code inside the "if clause" should say "snew->next = child;"

Also you can delete the "malloc" lines, since I think the nodes are already allocated and you're just passing in the pointers.

It is a little bit strange that you always have a "head" node. If you allowed your head pointer to be NULL, then you could have a truly empty list. As it is, I think the case of an empty list is exactly one node. That is more customary with some types of tree structures where there can be a "root" node.

Again, you don't need the "malloc" in your print function.

Go catch on the temp thing. I had gone through and renamed some of the variables and that was one I missed. But that did not fix my problem. It still errors out.

Your insert function needs the pointer to head to be defined as

struct student **head.

You have a pointer to a struct, you need a pointer to a pointer to a struct. You need to reassign the head variable on the heap, not the stack.

If I do that the program will not even compile.

Also, I probably should have included this with the first post but here it is now:

#include <stdio.h>
#include "student.h"

int main () 
{
	/*Assume all student records contain three parts:name, midterm score, final score;
	 each part is less than 20 characters.*/
	char srecord[3][20];
	
	/* An anonymous student who scored the maximum of everything */
	struct student anon = {NULL, "anon", 100, 100, 100, 'A'};
	struct student * head = & anon;
	
	printf("Please input a new student record:\n");
	
	while (ERROR != get_record(srecord)) 
	{
		
		struct student * temp = NULL ;
		temp = process_record(srecord);
		
		/* Insert a new student into the link list */
		if (head->next == NULL) 
		{ 
			head->next = temp; /* The first student */
		} 
		else 
		{
			insert_student(head, temp); 
		}
		printf("Please input a new student record:\n");
	}
	
	report_grades(head);
	
	return 0;
}

This is the main driver for the program. I enter the student name, there midterm score, and then there final score. I then computer the total score and letter grade. From there I take that and insert it into the linked list.

Thanks for the help so far!

 

[gnasher729]

Go catch on the temp thing. I had gone through and renamed some of the variables and that was one I missed. But that did not fix my problem. It still errors out.

It would be really helpful if you post exactly the code that has problems, and exactly what the problem is. "It still errors out" or "it doesn't compile" is not a description of the problem.

Now start with how your insertion function should be used: "head" should be either a pointer to the first student in the list, or NULL if there are no list elements, so it should be initialized as "head = NULL". There should be no struct named "anon" that is only there to make your code work (using this is the kind of thing that I call "asking for trouble". Your code may work today, but you will forever be cursing the day you wrote it that way when you have to make modifications later). The caller should _not_ have code that checks the linked list and either calls insert_student or not; insert_student should handle all the cases. And since every time you insert a student with lowest score the "head" variable must change, you pass &head to insert_student. So the calls would be:

struct student *head = NULL; 
while (...) {
    ...
    insert_student (&head, temp);
}

Now when you write insert_student, you need to figure out the proper types for your parameters, and your code for the function will be very simple:

while (<put in the right condition>)
    head = &((*head)->next);

snew->next = <right value here>
*head = <right value here>

 

[garethlewis2]

You still need to define the function insert to have a parameter of the form,

struct student **head.

The value struct student *head is on the stack for the insert_student code. You need to alter the value of head in the main program, that is what the ** is for.

your insert function will become something like

insert_student(struct student **head, <<data>>)
{
<< do work >>

*head = struct allocated in heap.
}

If you don't bother doing this, your program is not going to work, if after this, you still can't get it working, get a tutorial on linked lists.

 

[prostuff1]

OK, when I use these combination of files it errors at:

for(parent=head,child=head->next; child!=NULL && child->total<snew->total; parent=child,child=child->next);

The main file:

#include <stdio.h>
#include "student.h"

int main () 
{
	/*Assume all student records contain three parts:name, midterm score, final score;
	 each part is less than 20 characters.*/
	char srecord[3][20];
	
	/* An anonymous student who scored the maximum of everything */
	struct student anon = {NULL, "anon", 100, 100, 100, 'A'};
	struct student * head = & anon;
	
	printf("Please input a new student record:\n");
	
	while (ERROR != get_record(srecord)) 
	{
		
		struct student * temp = NULL ;
		temp = process_record(srecord);
		
		/* Insert a new student into the link list */
		if (head->next == NULL) 
		{ 
			head->next = temp; /* The first student */
		} 
		else 
		{
			insert_student(head, temp); 
		}
		printf("Please input a new student record:\n");
	}
	
	report_grades(head);
	
	return 0;
}

The student.c file:

#include "student.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
/*if you use library function int atoi(char *), you should also include stdlib.h */



/* Get a new student srecord from input, 
 return SUCCESS with a long string saved in (char *) srecord.
 return ERROR if the input is invalid.
 */
int get_record(char srecord[3][20]) 
{
	char c;
	int i=-1;
	int j=0;
	int state=0;
	int done=0;
	while((c=getchar())!='\n')
	{
		if(isalnum(c)&&state==0)
		{
			if(i!=-1) srecord[i][j]='\0';
			state=1;
			i++;
			if(i>2)
				return ERROR;
			j=0;
		}
		if(!isalnum(c)&&state==1)
		{
			state=0;
		}
		if(state==1)
		{
			srecord[i][j++]=c;
		}
		done=1;
	}
	srecord[i][j]='\0';
	if (done == 0)
	{
		return ERROR;
	}
	return SUCCESS;
}

/* Generate a new student based on the string srecord 
 with its field: next, being NULL.
 
 Note: 
 You need to use malloc() to get memory for a new student 
 so that you can return it with a pointer to the main program.
 Otherwise, a local variable defined will be lost as the function 
 returns so the main program never sees a new student available.
 */
struct student * process_record(char srecord[3][20]) 
{
	int midterm=0, final=0, temp_len_midterm=0, temp_len_final=0, total=0;
	char grade;
	struct student * snew ;
	
	/* Get the memory for this student */
	snew = (struct student *) malloc(sizeof(struct student));
	
	/* Find student name and scores in the array, srecord, and stash them to snew */
	strcpy(snew->name, srecord[0]);
	
	//get the Midterm Value
	temp_len_midterm = strlen(srecord[1]);
	if(temp_len_midterm == 1)
	{
		for(int x=1; x<20; x++)
		{
			srecord[1][x] = '\0';
		}
		
		midterm = atoi(srecord[1]);
		
		snew->midterm = midterm;
		
	}
	else if(temp_len_midterm == 2)
	{
		for(int x=2; x<20; x++)
		{
			srecord[1][x] = '\0';
		}
		
		midterm = atoi(srecord[1]);
		
		snew->midterm = midterm;
	}
	else
	{
		snew->midterm = 100;
	}
	
	//get the Final Value
	temp_len_final = strlen(srecord[2]);
	if(temp_len_final == 1)
	{
		for(int x=1; x<20; x++)
		{
			srecord[2][x] = '\0';
		}
		
		final = atoi(srecord[2]);
		
		snew->final = final;
	}
	else if(temp_len_final == 2)
	{
		for(int x=2; x<20; x++)
		{
			srecord[2][x] = '\0';
		}
		
		final = atoi(srecord[2]);
		
		snew->final = final;
	}
	else
	{
		snew->final = 100;
	}
	
	//calculate final
	total = (snew->midterm*.4) + (snew->final*.6);
	snew->total = total;
	
	//find letter grade
	if(total >= 90)
	{
		grade = 'A';
		snew->grade = grade;
	}
	else if(total > 80 && total <= 89)
	{
		grade = 'B';
		snew->grade = grade;
	}
	else if(total > 70 && total <=79)
	{
		grade = 'C';
		snew->grade = grade;
	}
	else
	{
		grade = 'D';
		snew->grade = grade;
	}	
	
	printf("%s\n",snew->name);
	printf("%i\n",snew->midterm);
	printf("%i\n",snew->final);
	printf("%i\n",snew->total);
	printf("%c\n",snew->grade);
	
	return snew;
}

/* Insert a new student into a link list represented by head,since you are required to report the grades 
 accoriding to the order A B C D, you should implement your link list as a sorted link list*/
void insert_student (struct student * head, struct student * snew) 
{
	struct student * child;
	struct student * parent;
	
	if(head->next != NULL)
	{
		for(parent=head,child=head->next; child!=NULL && child->total<snew->total; parent=child,child=child->next);
		parent->next = snew;
		snew->next = child;
	}
	else
	{
		head->next = snew;
	}
	
	
}

/* Report all the students linked to head or its followups */
void report_grades(struct student * head) 
{
	struct student *temp;
	
	printf("Name\tMidterm\tFinal\tTotal\tGrade\n");
	for(temp=head; temp!=NULL; temp=temp->next)
	{
		printf("%s \t%i \t%i \t%i \t%c", temp->name, temp->midterm, temp->final, temp->total, temp->grade);
	}
}

The main file was given to me by my instructor/teacher and I kinda assumed it was correct; she did not say anything about needing to change it. But if there is something I can do in that file that would make this easier please let me know.

This is my first C class (obviously) and this whole pointers thing is just confusing me to no end.

The main problem is that when I try to enter more then one set of srecord it borks on the for loop like I posted above.

 

[gnasher729]

OK, when I use these combination of files it errors at:

What exactly do you mean by "it errors at"? Can you write it so that someone who is not a clairvoyant will know what the problem is?

The main file was given to me by my instructor/teacher and I kinda assumed it was correct; she did not say anything about needing to change it.

It most definitely needs to change. First, the design where the caller has to handle an empty list differently is atrocious. Second, the fact that the caller has to know how to handle an empty list is atrocious. Third, there is the fact that the caller handles the empty list incorrectly - when the first record is inserted by hand, there is no code that sets its "next" field to NULL. Since it is undefined what the contents of memory allocated with "malloc" is, it may very well be that on your teacher's system that student record was filled with zeroes and "next" was equal to NULL, but on your system it isn't. So that main file contains a serious bug.

That is exactly why I called this "a design that is asking for trouble". It may very well be that you can fix your problems by replacing

head->next = temp;

with

head->next = temp;
temp->next = NULL;

But the problem is not that this code has a bug, the problem is that the design asked for code that needs to get it right in many, many places and one place was wrong. You should aim for a design that requires simple code and simple use of the code.

By the way, if you don't change your teacher's design, you will always have to fight the fact that head points to that static struct named anon, so you have to add code that ignores that struct everywhere. report_grades will first print out the struct named anon. Did I mention this design is asking for trouble?