Thread: sorting link list

  1. #1
    Registered User
    Join Date
    May 2008
    Location
    IR, Iran
    Posts
    103

    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;
    				}
    			}
    		}
    	}

  2. #2
    Technical Lead QuantumPete's Avatar
    Join Date
    Aug 2007
    Location
    London, UK
    Posts
    894
    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
    "No-one else has reported this problem, you're either crazy or a liar" - Dogbert Technical Support
    "Have you tried turning it off and on again?" - The IT Crowd

  3. #3
    Registered User
    Join Date
    May 2008
    Location
    IR, Iran
    Posts
    103
    this is the error.
    Unhandled exception at 0x01094ec2 in C++.exe: 0xC0000005: Access violation writing location 0x00000030.
    I have attached the whole code

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    That error message tends to confirm QuantumPete's observation, so you should go and fix it as hinted.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2008
    Location
    IR, Iran
    Posts
    103
    thanks a lot
    I think my way to sort a link list was wrong! so I decided to change it completely

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by behzad_shabani View Post
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    May 2008
    Location
    IR, Iran
    Posts
    103
    I thought very much, but I couldn't find any way without error
    can somebody suggest me a way
    thanks

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by behzad_shabani View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 11-29-2008 at 02:28 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iMalc View Post
    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

    Quote Originally Posted by iMalc View Post
    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:

    Quote Originally Posted by iMalc View Post
    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...
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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

    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MK27 View Post
    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.

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    Last edited by iMalc; 11-30-2008 at 12:36 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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.

    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. reading data from a file - link list
    By peter_hii in forum C++ Programming
    Replies: 7
    Last Post: 10-25-2006, 09:11 AM
  2. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  3. compiler build error
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-30-2003, 10:16 AM
  4. 1st Class LIST ADT
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 11-09-2001, 07:29 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

Tags for this Thread