sorting link list

I want to sort a link list, everything is right but it has run-time error and I don't know where is the problem!

here is the code:

Code:

struct student
{
	char name[20];
	int ID;
}*start, *cur, *temp;

Code:

	struct student *p, *k, *PB, *PF, *KB, *KF;
	int n = 1;

	temp = start;
	while(temp != cur)
	{
		n++;
		temp = temp->FL;
	}

	for(int i = 0; i < n; i++)
	{
		for(p = start; p->FL != cur->FL; p = p->FL)
		{
			for(k = p->FL; k != cur->FL; k = k->FL )
			{
				if (p->ave > k->ave && k != p->FL)
				{
					PB = p->BL;
					PF = p->FL;
					KB = k->BL;
					KF = k->FL;
					PB->FL = k;
					PF->BL = k;
					KB->FL = p;
					KF->BL = p;
					p->FL = KF;
					p->BL = KB;
					k->FL = PF;
					k->BL = PB;
				}
				else if (p->ave > k->ave && k == p->FL)
				{
					PB = p->BL;
					KF = k->FL;
					PB->FL = k;
					KF->BL = p;
					p->FL = KF;
					p->BL = k;
					k->FL = p;
					k->BL = PB;
				}
			}
		}
	}

Well, you've not actually allocated any memory for your pointers!
It would also be helpful to post the actual error message that you see.

QuantumPete

this is the error.

Unhandled exception at 0x01094ec2 in C++.exe: 0xC0000005: Access violation writing location 0x00000030.

I have attached the whole code

That error message tends to confirm QuantumPete's observation, so you should go and fix it as hinted.

thanks a lot
I think my way to sort a link list was wrong! so I decided to change it completely

Originally Posted by behzad_shabani

I think my way to sort a link list was wrong! so I decided to change it completely

I think it would be an understatement if I simply said I agreed with that idea.

May I suggest implementing a linked-list Insertion Sort? That's about the easiest when it comes to lists.

I thought very much, but I couldn't find any way without error
can somebody suggest me a way
thanks

Originally Posted by behzad_shabani

I thought very much, but I couldn't find any way without error
can somebody suggest me a way
thanks

Sorting a linked list is often much harder than inserting at the right place in the first place. That method is called "insertion sort". I've often solved the problem of sorting linked lists by removing one item at a time from one list and inserting the item in a new list in sorted order, for that very reason. There are so many special cases to care about when sorting a linked list.

Using variable names that mean something to other readers of the code would also help, as that makes it easier for us to understand what you are thinking.

--
Mats

I thought I'd try this, so I took a file like this:

Code:

mr man:12345
bob you:76
sara tall:10
Me Next:77262
   [...etc]

Read it into a linked list, and then sorted the list by name. This is not exactly an "insertion sort", but it could be made to work that way.

Alphabetic sorting is fairly simple if you compare list members two at a time (first 0 and 1, then 1 & 2, and so on), order them correctly and then set a flag if the order has changed. Repeat this technique until the flag doesn't go up.

Doing it with a linked-list is just as simple if the list size remains the same, since everything is allocated already, so you could simply add a new value and then sort for an "insertion sort".

Code:

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

struct _node {
	char *name;
	int ID;
	struct _node *next;
};

typedef struct _node node;
char *buffer;

int LLsize (node *head) {
	node *then;
	int i=1;
	if ((then=head->next)==NULL) return 0;
	while ((then=then->next)!=NULL)	i++;
	return i;
}

void LLadd (node *head, char *data, int num) {
	node *new, *ptr;
	new=malloc(sizeof(node));
	if (head->next==NULL) head->next=new;
	else {ptr=head->next;
		while (ptr->next!=NULL) ptr=ptr->next;
		ptr->next=new;}	
	new->name=malloc(strlen(data)+1);
	strcpy(new->name,data);
	new->ID=num;
	new->next=NULL;
}

int streamline (FILE *strIN) {
	int i=0, chr;
	buffer=malloc(1);
	while ((chr=fgetc(strIN))!=EOF) {
		if (buffer==NULL) return -1;
		if (chr=='\n') { buffer[i]='\0';
			return i+1;}
		buffer[i]=chr;
		buffer=realloc(buffer,++i+1);
	}
	buffer[i]='\0';
	return 0;
}

int comparewords (char *one, char *two) {
	int depth=0, dv, retv=0;
	while (1) { dv=depth;	
		if ((one[depth] == 0) && (two[depth] == 0)) return 0;
			else if (one[depth] == 0) return 1;
			else if (two[depth] == 0) return 2;		
		if (one[depth] == two[depth]) depth++;
		else if (one[dv] < two[dv]) {
			retv=1;
		} else if (one[dv] > two[dv]) {
			retv=2;
		}
		if (retv>0) return retv;
	}
	return -1;   //impossible
}

int comparenames (char *one, char *two) {
	int retv,i;
	char name1[256], name2[256], first1[128], last1[128], first2[128], last2[128];
	strcpy(name1,one); strcpy(name2,two);	// use copies and render lowercase
	for (i=0;i<strlen(name1);i++) if ((name1[i]<97) && name1[i]!=' ') name1[i]+=32;	
	for (i=0;i<strlen(name2);i++) if ((name2[i]<97) && name2[i]!=' ') name2[i]+=32;	
	sscanf(name1,"%[A-Za-z] %[A-Za-z]",first1,last1);
	sscanf(name2,"%[A-Za-z] %[A-Za-z]",first2,last2);
	if ((retv=comparewords(last1,last2))!=0) return retv;
	if ((retv=comparewords(first1,first2))!=0) return retv;
	return 0;  // names are identical
}

int main () {
	int num, retv, flag, i, tmp, count=0;
	char name[256], *ptr;
	FILE *fstRO=fopen("/root/test/names.txt","ro");
	node *head, *now;

	if (fstRO==NULL) {puts("fopen fail");
		return -1;}

	head=malloc(sizeof(node));
	head->name=NULL;	// head will be empty
	head->next=NULL;	

	while ((retv=streamline(fstRO))!=0) {
		if (retv<0) {puts("Memory allocation error!");
			return -2;}
		if (sscanf(buffer, "%[A-Za-z. ]:%d",name,&num)==2) LLadd(head,name,num);
		free(buffer); 
	}
	fclose(fstRO);	

	puts("____unsorted____");
	now=head->next;
	printf("%s (ID %d)\n",now->name,now->ID);
	while ((now=now->next)!=NULL) printf("%s (ID %d)\n",now->name,now->ID);
	
	printf("\nNumber of names=%d\n",num=LLsize(head));	
	while (1) { flag=0;
		now=head->next;
		for (i=0;i<(num-1);i++) {
			if ((retv=comparenames(now->name,now->next->name))==2) {
				ptr=now->name; 
				tmp=now->ID;
				now->name=now->next->name;
				now->ID=now->next->ID;
				now->next->name=ptr;
				now->next->ID=tmp;
				flag=1;
			}
			now=now->next;
		}
		count++;
		if (flag==0) break;
	}
	printf("Iterated list %d times\n\n",count);
	
	puts("____Sorted____");
	now=head->next;
	printf("%s (ID %d)\n",now->name,now->ID);
	while ((now=now->next)!=NULL) printf("%s (ID %d)\n",now->name,now->ID);
					
	while (head->next!=NULL) {
		now=head->next;
		free(head->name);
		free(head);		
		head=now;
	}
	free(head);
	puts("\nDone.");
	
	return 0;
}

The output looks like this:

____unsorted____
mr man (ID 12345)
bob you (ID 76)
sara tall (ID 10)
Me Next (ID 77262)
Bob not (ID 12412345)
Sam Would (ID 900)
Terry Green (ID 11)
Mk Next (ID 23345)
Somebody New (ID 8837)
Ralphy c (ID 655)
glenda hazel (ID 1666)
Flever Trung (ID 9022)

Number of names=12
Iterated list 10 times

____Sorted____
Ralphy c (ID 655)
Terry Green (ID 11)
glenda hazel (ID 1666)
mr man (ID 12345)
Somebody New (ID 8837)
Me Next (ID 77262)
Mk Next (ID 23345)
Bob not (ID 12412345)
sara tall (ID 10)
Flever Trung (ID 9022)
Sam Would (ID 900)
bob you (ID 76)

Done.


I imagine it's not the fasted method around, but it works.

That's a Bubble Sort, but done the same way as an array rather than taking advantage of the fact that it is a linked list.
That method has very limited usefulness because you have no random access, AND dont perform insertion/removal from the list (you have neither the benefits of an array nor the benefits of a list), so you're basically limited to swapping adjacent items. As such you limit your algorithm choice to just a few possibilities (Brick Sort & Bubble Sort being the most obvious), none of which are any better than O(n*n).
The larger your items are, the more efficient it will be to change the pointers to reorder the nodes vs swapping the entire objects of two nodes.

Originally Posted by iMalc

That's a Bubble Sort, but done the same way as an array rather than taking advantage of the fact that it is a linked list.

Since you are unable to actually explain what you mean by this, I strongly suspect you are wrong or are having some difficulty with grammar. Yes, it's a bubble sort. Show me how a bubble sort could possibly be different for a linked list, and I'll send you some pie

Originally Posted by iMalc

That method has very limited usefulness because you have no random access, AND dont perform insertion/removal from the list

I said more or less the same thing. The OP was not asking to INSERT anything, s/he wanted to SORT it. There is a big difference in the sense that you could sort a list (or linked list, he he) a number of ways, but if "LLadd" was intended to insert a new struct at the "proper" point, then you are stuck with only one possible sorting method. By seperating the add from the sort (rather than combining them in an "insertion sort") you keep this door open. You also keep the door open for recombining different sets of structs into different lists dynamically -- so you have in essence a data pool from which different lists could could be ordered. If all you want to do is keep a list which is always sorted on the basis of one term, you might as well use an array and just shove your data into a line.

You are contrasting a linked list with an array as if this difference had something to do with my implimentation. After all, YOU COULD perform insertion or removal on it, but, because it is not an array, you don't get random access. So, if this is a long winded way of saying: did you know you can also perform insertion and removal on a linked-list? I would have to say: that's a little hard to miss, so what is YOUR POINT???

That said, it would still be possible to perform different kinds of "insertion sorts" if you wanted to maintain one unordered list and make reordered copies of it. It would be fewer iterations thru the list. If you erase one as you go, you won't need twice as much memory BUT then you cannot do this:

Originally Posted by iMalc

The larger your items are, the more efficient it will be to change the pointers to reorder the nodes vs swapping the entire objects of two nodes.

I was thinking that on the bus yesturday -- "why didn't I just swap the next pointers around?"
That would make it more effiecient. However, you couldn't do that if you wanted to reorder it with an insertion sort...

Here's an insert sort for the above:

Code:

void LLinsert (node *head, char *data, int num) {
	node *new, *ptr, *prev;
	new=malloc(sizeof(node));
	new->name=malloc(strlen(data)+1);
	strcpy(new->name,data);
	new->ID=num;
	if (head->next==NULL) {		// first instance
		head->next=new;
		new->next=NULL;
		return;}
	ptr=head->next;
	if (comparenames(data,ptr->name)==1) {	// replace first
		head->next=new;
		new->next=ptr;
		return;}
	if (ptr->next==NULL) {		
		ptr->next=new;
		new->next=NULL;
		return;}
	while (1) {
		prev=ptr;
		ptr=ptr->next;
		if (comparenames(data,ptr->name)==1) {
			prev->next=new;
			new->next=ptr;
			break;}
		if (ptr->next==NULL) {		// last
			ptr->next=new;
			new->next=NULL;
			break;}
	}
}

To see it in action, insert sort this before "return 0" in main():

Code:

                 /* start again */
        head=malloc(sizeof(node));
	head->name=NULL;	// head will be empty
	head->next=NULL;

        if ((fstRO=fopen("/root/test/names.txt","ro"))==NULL) {puts("fopen fail");
		return -1;}
	
	while ((retv=streamline(fstRO))!=0) {
		if (retv<0) {puts("Memory allocation error!");
			return -2;}
		if (sscanf(buffer, "%[A-Za-z. ]:%d",name,&num)==2) LLinsert(head,name,num);
		free(buffer); 
	}

	fclose(fstRO);	
	
	puts("\n____Insert Sort____");
	now=head->next;
	printf("%s (ID %d)\n",now->name,now->ID);
	while ((now=now->next)!=NULL) printf("%s (ID %d)\n",now->name,now->ID);

Obviously this is better if you are building the list from scratch, and not sorting an existing one. If the list is small so you can afford memory to build TWO lists, it will be obviously be faster than the straight sort of one list.

I added a count of the number of times comparenames() gets called, and this is the output:

____unsorted____
mr man (ID 12345)
bob you (ID 76)
sara tall (ID 10)
Me Next (ID 77262)
Bob not (ID 12412345)
Sam Would (ID 900)
Terry Green (ID 11)
Mk Next (ID 23345)
Somebody New (ID 8837)
Ralphy c (ID 655)
glenda hazel (ID 1666)
Flever Trung (ID 9022)
Imalc Khan (ID -1)

Number of names=13

____Sorted____
Ralphy c (ID 655)
Terry Green (ID 11)
glenda hazel (ID 1666)
Imalc Khan (ID -1)
mr man (ID 12345)
Somebody New (ID 8837)
Me Next (ID 77262)
Mk Next (ID 23345)
Bob not (ID 12412345)
sara tall (ID 10)
Flever Trung (ID 9022)
Sam Would (ID 900)
bob you (ID 76)

comparenames() called 130 times

____Insert Sort____
Ralphy c (ID 655)
Terry Green (ID 11)
glenda hazel (ID 1666)
Imalc Khan (ID -1)
mr man (ID 12345)
Somebody New (ID 8837)
Me Next (ID 77262)
Mk Next (ID 23345)
Bob not (ID 12412345)
sara tall (ID 10)
Flever Trung (ID 9022)
Sam Would (ID 900)
bob you (ID 76)

comparenames() called 39 times

Originally Posted by MK27

Since you are unable to actually explain what you mean by this, I strongly suspect you are wrong or are having some difficulty with grammar. Yes, it's a bubble sort. Show me how a bubble sort could possibly be different for a linked list, and I'll send you some pie

I can think of two things he (might) mean, one trivial and one more interesting. The trivial one is that you are using a for-loop to travel the list, rather than walking the list until you fall off the end. The more interesting is that the point of a list is to insert/delete quickly, so instead of swapping, you should delete and re-insert a node (works out to changing some pointers). You seemed to grasp this later in your reply; I don't know why you didn't grasp it here.

There's a difference between not being able to explain something, and not being given time to .
I wrote Bubble Sort for linked lists about a year ago. Here is a copy and paste of the best implementation I came up with (except I don't feel like translating it to C right now):

Code:

//Gives a fake node pointer where only the 'next' member is valid
#define fakePrev(T, H, N) (T*)(((size_t)&H) + ((size_t)H) - ((size_t)&H->N))
//Swaps 'b' and 'c' (we need 'a' to do this)
#define ListSwap(a,b,c) do{ \
		(b)->next = (c)->next; \
		(a)->next = (c); \
		(c)->next = (b); \
	}while(false)

template <class TItem>
void BestBubbleSort(TItem *&head) {
	const TItem *stophere = NULL;
	while (head != stophere) {
		TItem *curr = head, *prev = fakePrev(TItem, head, next);
		TItem *after = curr->next, *theBubble = NULL;
		while (after != stophere) {
			//compare adjacent items
			if (*after < *curr) {
				//swap the order of the items
				ListSwap(prev, curr, after);
				theBubble = curr;
			}
			//move all pointers along to the next items
			prev = curr;
			curr = after;
			after = after->next;
		}
		if (theBubble == NULL) return;
		//go through one fewer items next time
		stophere = theBubble;
	}
}

My point is that if you perform sorting on a linked-list without modifying the pointer values in the nodes then you are limited to algorithms with rather bad running times O(n*n), AND have the possibility that items being swapped are large taking even more time.
In terms of what it needed to do, your implementations have been just fine.
I'm not saying the technique is never useful, I'm just pointing out the limitations of its usefulness.

Of course if you're writing an algorithm such as Bubble Sort that doesn't require random access or even reverse iteration, then it doesn't matter too much how you implement it. Merge Sort is much more efficient and not too much harder to implement for lists.

I will have to investigate this "Merge Sort".

I suppose that since modern computers have so much memory in relation to their processing power, my contention that that the bubble sort saves space may be almost mute.