sorting and saving a linked list

[zanza]

how would one go about sorting (by whatever value) a linked list?

also, i havent the slightest idea how to save and load a linked list to and from a file in binary mode because fwrite() obviously wont resolve pointers.

žÅNžÅ

 

[marsd]

I don't know what you mean about by 'whatever value', but
if you are just sorting list data any of the established sorts
will work if you are willing to use an intermediate data structure. (An array).

Trying to sort a simple linked list by shuffling
list members around is not a lot of fun.
It's not very fast either.

A hash table sounds like something you should look
into.

 

[butthead]

I apologize for the brevity. this is what I use to retrieve a file that was saved from a linked list.
it loads more than one linked list.

// Load the dat file to memory. This is a linked list.
int LoadList (DATAPTR headptr, int setuplines, char *Logfile,
char *start1limits, char *end1limits, char datasetup [][256])
{
// Open the file for input to memory.
FILE *file;

if ( (file = fopen(Logfile, "r&quot) != NULL )
{
//Reset the ptr variable to the first entry.
wrkptr = headptr;

DATAPTR nextptr;

// Temp storage for text line recieved.
char *buff = new char[256];

// Skip over the first 10 lines.
for (int x = 0; x <= setuplines; x++)
{
fgets (buff, 256, file);
strcpy (datasetup [x], buff);
}

//*********************************
// This is the first check of the integrity of the dat file.

// Set end of the string to be compared.
buff [17] = NULL;

// If the these strings compare the initial data is correct.
if (strcmp (buff, &quot;** START DATABASE&quot)
{
return 3;
}
//*********************************

int done = false;

// Load the file to a linked list in memory.
// Until the end of the file is reached.
// If the previous check for the start database line
// fails, this while loop does not process because the
// done variable is set to true in the previous lines.
// The next seven lines are processed as if these lines
// were without error. The error check comes after when
// the start notes line is checked for its proper position.
while (!done)
{
// For removing the newline character.
int strln;

//*************************************
//load each Group field.
for(x = 0; x <= 7; x++)
{
//Read the next line from the disk.
fgets (buff, 256, file);

//Remove the newline character from the end of the string.
strln = strlen (buff);
buff [strln - 1] = NULL;

switch (x)
{
case 0:
strcpy (wrkptr->field1, buff);
break;
case 1:
strcpy (wrkptr->field2, buff);
break;
case 2:
strcpy (wrkptr->field3, buff);
break;
case 3:
strcpy (wrkptr->field4, buff);
break;
case 4:
strcpy (wrkptr->field5, buff);
break;
case 5:
strcpy (wrkptr->field6, buff);
break;
case 6:
strcpy (wrkptr->field7, buff);
break;
case 7:
strcpy (wrkptr->field8, buff);
break;
default:
break;
}//End of switch.
}//End of for. Loading the group fields for the entry is done.
//*************************************

//Read the next line from the disk.
fgets (buff, 256, file);

//Remove the newline character from the end of the string.
strln = strlen (buff);
buff [strln - 1] = NULL;

//*************************************
// Load notes1.

// If the next line is the start header line read the notes.
if (!strcmp (buff, start1limits))
{
// This is the working textptr.
TXTPTR tptr;

// Initalize the first line of the notes.
wrkptr->firstline1 = AddTextLine ();
tptr = wrkptr->firstline1;

//*****************************
// This is the counter for the number of lines
// read by the notes.
int y = 0;
//This is the limiting number of lines to be read.
int z = 1000;
//*****************************

int x = 0;

while (!x)
{
if (y < z)
y++;
else
{
// There are to many lines in the notes.
// This error can occur when the notes limits
// are not terminated properly at the end of
// the last entry.
return 2;
}

fgets (buff, 256, file);

//Remove the newline character from the end of the string.
strln = strlen (buff);
buff [strln - 1] = NULL;

//If this string is txtlimits this is the end of the notes.
if (!strcmp (buff, end1limits))
x = 1;

//Get the notes.
else
{
//******************************************
//The first line of the notes is placed in the first line ptr.
strcpy (tptr->textline, buff);
tsavedptr = AddTextLine ();
tptr->nextptr = tsavedptr;
tptr = tsavedptr;
//******************************************
}
}// end of while (!x).
}// end of if (!strcmp (buff, start1limits)).
//*************************************

// If we do not break here, the function adds an empty
// structure and fills all the fields with the field4
// of the last structure.
if (feof (file))
{
//done = true;
//continue;
return 0;
}
//*************************************

//*************************************
// Inialize the nextptr and link it to the previous ptr.
nextptr = AddNode ();
wrkptr->nextptr = nextptr;
wrkptr = nextptr;
//*************************************

}//End of while (!done), load fields and notes.

delete nextptr;
delete buff;
fclose(file);

}// end of if file open.

else
return 1; // file acess error.

return 0;

/* Return values

0 - file load OK
1 - unable to open file
2 - notes exceeds limit
3 - the start of the data is not in the correct spot
4
5

*/
}

email me and I will send yu the full code that resolves some of the pointers that are rather vague as listed here.

 

[marsd]

After some more research I found some code online:

http://www.funducode.com/freec/datastructure/datastruct6/datastruct6.htm

And also include a selection sort of my own which sorts by
an integer data member, but using a more generic function wouldn't be difficult. it just depends basically on finding
the lists length and reconciling it while iterating through the list and creating a sorted one recursively.
There was a complicated example of a generic mergesort
that I found but lost the url for, that would handle
all list types supposedly,. I'll post it if I can find it.
Hopefully this will give you some ideas.

SORTED *selectsortList(SORTED *main,SORTED *cpt,SORTED *ppv, SORTED *pnew, SORTED *pnhd, int ct) {
int p , x;
SORTED *ppt;
         /*( if at beginning or end of list start over */   
       
         if (cpt == NULL) {
            cpt = main;
         }         

         /*memprint(cpt,"Assigned mem to cpt");*/
         /* check for values */
         for (ppt=main ; ppt != NULL ; ppt = ppt->pnxt) {
                 printf("comparing %d ppt to %d cpt\n",ppt->data, cpt->data);
              if (cpt->data < ppt->data && ppt->data > 0) {
                  printf(&quot;At count: %d\n&quot;, ct);
                  ct++;
                  ct = ct <= printList(main,0) ? ct  : 0; 
                  return selectsortList(main,cpt->pnxt,ppv,pnew,pnhd,ct);
              }         
         }
         
         
         x = printList(main,0); p = printList(pnhd,0);
         if (x == p) {
              printList(pnhd,1);
              return pnhd;
         }
         
          if (ppv == NULL) {
             pnew = createnewElement();
             pnew->data = cpt->data;
             setNull(main,cpt->data);
             cpt = NULL;
             ppv = pnew;
             pnhd = pnew;
             return selectsortList(main,cpt,ppv,pnew,pnhd,ct);
          } else {
             pnew = createnewElement();
             ppv->pnxt = pnew;
             pnew->data = cpt->data;
             setNull(main,cpt->data);
             cpt = NULL;
             return selectsortList(main,cpt,ppv->pnxt,ppv,pnhd,ct);
          }
return NULL;
}

 

[lionelhill]

Saving a linked list is very easy.
Simply save the values in order of list. I'm sure you must already have code to create a linked list from values
(some sort of InsertValue(thingy) function), so when you load the file, just read each value and send it to your InsertValue function; this will recreate a new linked list with all the pointers pointing to what they ought to.
Same method applies to almost any data structure, even binary trees and more complicated things.

 

[lionelhill]

Oh, I'm as daft as a brush. Another extra is that if you are going to load a linked list from file, that may be a good time to think about sorting it, because you can simply insert new list members in their correct places as you read the values from the file. Of course this is not a very efficient sort method.

The fastest way to load from file is to insert each new value at the top of the list.

But, if you do that, I think you will reverse the list every time you save it (I'm assuming a singly-linked list. Doubly-linked is obviously the same either way round). This is a very important point, because an exactly-reversed list is the worst possible case for many sort algorithms, and it would be a pity to take a perfectly sorted file and turn it into the worst case when you open it....

Any text-book will have chapters on sorting linked lists. The major point I'd make is to put sentinels on each end of your list. That means, start it with a list item that has a smaller value than anything in the &quot;real&quot; data set, and end it with a list item that is larger. That way you need never test pointers to see if you've hit the end of the list, which saves extra sort time. But this is mostly relevant if you have big lists.