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.

Quote:

---

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 :D

Quote:

---

Originally Posted by behzad_shabani

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

---

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 :D
can somebody suggest me a way :D
thanks

Quote:

---

Originally Posted by behzad_shabani

I thought very much, but I couldn't find any way without error :D
can somebody suggest me a way :D
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.

Quote:

---

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

Quote:

---

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:

Quote:

---

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

Quote:

---

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.

:)

Quote:

---

Originally Posted by MK27

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.

---

When you investigate merge sort, you will find that space consumption is a disadvantage, but not where linked lists are concerned. Consequently, any argument about saving space just falls flat.

Quote:

---

Originally Posted by laserlight

When you investigate merge sort, you will find that space consumption is a disadvantage, but not where linked lists are concerned. Consequently, any argument about saving space just falls flat.

---

So...rather than rewrite the linked-list out into fresh halfs, I could just use a counter to work with a half at a time?

Quote:

---

Originally Posted by MK27

So...rather than rewrite the linked-list out into fresh halfs, I could just use a counter to work with a half at a time?

---

I am not sure what you mean by a counter. Fundamentally, I suspect that you are thinking of a linked list as an indexed array, but as iMalc mentioned, if you want to use a linked list, you might as well take advantage of its nature as a linked list. A quick search for "linked list merge sort" brings up Mergesort For Linked Lists, apparently by the same guy responsible for PuTTY.

Whew! I got the merge sort, and I'd love it if someone could glance throught the code to see if they can spot something less than praise worthy. It will work with the above script but because it can't be done without creating some kind of additional list, and I couldn't get a plain array o' struct pointers to work for me when passed aroundf, you need to add:

Code:

---

struct nodeptr {
        struct _node *np;
};

---

The two functions are:

Code:

---

int LLsplitsort (struct nodeptr *retlist, struct nodeptr *left, int Llen, struct nodeptr *right, int Rlen) {
        int i=0, LC=0, RC=0;
        while ((Llen>LC) && (Rlen>RC)) {
                if (comparenames(left[LC].np->name,right[RC].np->name)==1) {
                        retlist[i].np=left[LC].np;
                        LC++;}
                else {
                        retlist[i].np=right[RC].np;
                        RC++;}
                i++;
        }
        while (Llen>LC) {retlist[i].np=left[LC].np;i++;LC++;}
        while (Rlen>RC) {retlist[i].np=right[RC].np;i++;RC++;}
        return 0;
}
               
int LLmergesort (struct nodeptr *retlist, node *head, int len, int tag) {
        int i, m=len/2, R=m, retv;
        node *middle, *now, *start=head;
        struct nodeptr *left, *right;
        if ((left=malloc(m*sizeof(*left)))==NULL) return -1;
        if ((right=malloc((m+1)*sizeof(*right)))==NULL) return -1;
       
        if (tag==0) {                // first iteration
                head=head->next;        //uses an empty head       
                if ((retlist=malloc(len*sizeof*retlist))==NULL) return -1;
        }
        tag++;
       
        if (len==1) return tag;                // depth of error
        if (len%2>0) R++;
        now=head;       
        if (len<4) middle=head->next;
        else for (i=0;i<=m;i++) {
                middle=now;
                now=now->next;
        }
       
        if (m==1) left[0].np=head;
        else if ((retv=LLmergesort(left,head,m,tag))!=0) return retv;                               
        if (R==1) right[0].np=middle;
        else if ((retv=LLmergesort (right,middle,R,tag))!=0) return retv;       
        LLsplitsort (retlist,left,m,right,R);
        free(left);
        free(right);
       
        if (--tag==0) {                                // THE END
                start->next=retlist[0].np;
                for (i=0;i<len-1;i++) retlist[i].np->next=retlist[i+1].np;
                free(retlist);
        }
        return 0;
}

---

LLsplitsort is called by LLmergesort. Because of the recursion, the first argument to LLmergesort should be set to NULL when first called and the last to 0. If there is an error, it returns -1 for malloc failure or >0 to indicate the depth of a technical mistake, so:

if ((tmp=LLmergesort(NULL,head,num,0))!=0) printf("!! LLmergesort() error at depth %d...\n",tmp);

My result was correctly sorted and made 32 comparisons (13 elements). The same list bubble sorted made 130 comparisons, and assembled with the insertion sort above, 39 comparisons. However, the insertion sort seems kind of better since it builds the list from empty (merge sort just sorts) and doesn't require a temp list while sorting. If I can think of some more names I will try it with a greater number of elements and see what's up.

:D:D:D

Quote:

---

Originally Posted by MK27

However, the insertion sort seems kind of better since it builds the list from empty (merge sort just sorts)

---

I do not understand what you mean by this.

Quote:

---

Originally Posted by MK27

and doesn't require a temp list while sorting.

---

Neither does merge sort require a temporary linked list, as mentioned in that article that I linked to.

Quote:

---

Originally Posted by laserlight

I do not understand what you mean by this.

---

I mean that the insertion sort will be better if the list is already sorted and you are adding a new element, so if you have an empty list, it might be better to add them one at a time with the insertion sort than to just make a list and merge sort it, because the merge sort is kind of overkill for adding one element.

Quote:

---

Neither does merge sort require a temporary linked list, as mentioned in that article that I linked to.

---

Have you done it that way? My reading of the article includes this:

In each pass, we are merging lists of size K into lists of size 2K. (Initially K equals 1.) So we start by pointing a temporary pointer p at the head of the list, and also preparing an empty list L which we will add elements to the end of as we finish dealing with them. Then:

I did try it without one, but if you look at the nature of the recursion I think it will be impossible. Watch what happens if you try changing any of the pointers before the sort is complete! However, you don't need to make two linked lists; you just need an array with the pointers in the proper order. Which is to say I didn't use a temporary linked list, I used a temporary list (array).

edit: But at 17 names, the insert/build does 70 comparisons while the build then merge sort only does 51...
edit: at 21 names, the difference is 117 to 71 (poor ol' Bubble Sort is now 357)...god this fun

Quote:

---

Originally Posted by MK27

I mean that the insertion sort will be better if the list is already sorted and you are adding a new element, so if you have an empty list, it might be better to add them one at a time with the insertion sort than to just make a list and merge sort it, because the merge sort is kind of overkill for adding one element.

---

Yes, merge sort is overkill for adding one element, but your reasoning is that because merge sort is overkill for adding one element, it must be overkill for adding n elements. Consider the same argument for an array: if you are adding a single element to a sorted array, quick sort is overkill; bubble sort could well be the best. Based on this, would you conclude that bubble sort is generally better (as in more efficient) than quick sort?

Quote:

---

Originally Posted by MK27

Have you done it that way?

---

No, but Simon Tatham's own example in C appears to do so.

Quote:

---

Originally Posted by MK27

So we start by pointing a temporary pointer p at the head of the list, and also preparing an empty list L which we will add elements to the end of as we finish dealing with them.

---

L is not a temporary linked list in the sense that it points to a new list of elements. Rather, it consists of two pointers, the head and tail of the linked list of elements that have been dealt with. This is why the space consumption is constant, not proportional to the size of the linked list as you implemented it.

Quote:

---

Originally Posted by laserlight

No, but Simon Tatham's own example in C appears to do so.

---

Maybe. I actually didn't want to look at it first, but I will concede that Simon perhaps did somewhat of a better job.