![]() |
| | #1 |
| Registered User Join Date: May 2008 Location: IR, Iran
Posts: 101
| sorting link list 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;
}
}
}
}
|
| behzad_shabani is offline | |
| | #2 |
| Technical Lead Join Date: Aug 2007 Location: London, UK
Posts: 723
| 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 |
| QuantumPete is offline | |
| | #3 | |
| Registered User Join Date: May 2008 Location: IR, Iran
Posts: 101
| this is the error. Quote:
| |
| behzad_shabani is offline | |
| | #4 |
| C++ Witch Join Date: Oct 2003 Location: Singapore
Posts: 10,354
| That error message tends to confirm QuantumPete's observation, so you should go and fix it as hinted.
__________________ C + C++ Compiler: MinGW port of GCC Build + Version Control System: SCons + Bazaar Look up a C/C++ Reference and learn How To Ask Questions The Smart Way |
| laserlight is offline | |
| | #5 |
| Registered User Join Date: May 2008 Location: IR, Iran
Posts: 101
| thanks a lot I think my way to sort a link list was wrong! so I decided to change it completely |
| behzad_shabani is offline | |
| | #6 | |
| Algorithm Dissector Join Date: Dec 2005 Location: New Zealand
Posts: 2,476
| Quote:
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 | |
| iMalc is offline | |
| | #7 |
| Registered User Join Date: May 2008 Location: IR, Iran
Posts: 101
| I thought very much, but I couldn't find any way without error ![]() can somebody suggest me a way ![]() thanks |
| behzad_shabani is offline | |
| | #8 | |
| Kernel hacker Join Date: Jul 2007 Location: Farncombe, Surrey, England
Posts: 15,686
| Quote:
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. | |
| matsp is offline | |
| | #9 |
| subminimalist Join Date: Jul 2008 Location: NYC
Posts: 3,944
| 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] 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;
}
____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.
__________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS |
| MK27 is offline | |
| | #10 |
| Algorithm Dissector Join Date: Dec 2005 Location: New Zealand
Posts: 2,476
| 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.
__________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger Last edited by iMalc; 11-29-2008 at 02:28 PM. |
| iMalc is offline | |
| | #11 | |||
| subminimalist Join Date: Jul 2008 Location: NYC
Posts: 3,944
| Quote:
![]() Quote:
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:
That would make it more effiecient. However, you couldn't do that if you wanted to reorder it with an insertion sort...
__________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS | |||
| MK27 is offline | |
| | #12 |
| subminimalist Join Date: Jul 2008 Location: NYC
Posts: 3,944
| 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;}
}
}
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);
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
__________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS |
| MK27 is offline | |
| | #13 |
| and the Hat of Guessing Join Date: Nov 2007
Posts: 8,740
| 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. |
| tabstop is offline | |
| | #14 |
| Algorithm Dissector Join Date: Dec 2005 Location: New Zealand
Posts: 2,476
| 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;
}
}
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.
__________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger Last edited by iMalc; 11-30-2008 at 12:36 PM. |
| iMalc is offline | |
| | #15 |
| subminimalist Join Date: Jul 2008 Location: NYC
Posts: 3,944
| 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.
__________________ Accuracy and integrity mean nothing if you don't make it past the censors...PYTHAGORAS |
| MK27 is offline | |
![]() |
| Tags |
| link list, pointer |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| reading data from a file - link list | peter_hii | C++ Programming | 7 | 10-25-2006 09:11 AM |
| airport Log program using 3D linked List : problem reading from file | gemini_shooter | C Programming | 3 | 03-04-2005 02:46 PM |
| compiler build error | KristTlove | C++ Programming | 2 | 11-30-2003 10:16 AM |
| 1st Class LIST ADT | Unregistered | C++ Programming | 1 | 11-09-2001 07:29 PM |
| singly linked list | clarinetster | C Programming | 2 | 08-26-2001 10:21 PM |