Linked list & radix sort question, please help!

Hey everyone,

I'm in my first year in college and I've been cracking my brain for about a week over this program, but no luck. Let me just describe a couple of basic problems i have, and if anybody can provide any help, it'd be much appriciated!

First of all, I want to add items to the end of a linked list. I know how to do it using a function that gets a pointer to the start of the list, but the function i need to write is supposed to get a pointer to the end of the list. That is very confusing to me. I don't even know what to send the function....

The main purpse of the program i'm writing is to sort a bunch of numbers (input includes the exact number) using radix sort. The trick is though, that i need to do it using the binary repesentation of the numbers, and use only 1 linked list. I have yet to come up with an algoritm to do this, I really need some help! I've tried asking my classmates but they don't know either.

Thanks in advance,
Lior

ok linked lists are kinda easy to do if you write it on a piece of paper using a box to represent each item in a linked list and arrows representing the pointers in them, ok assume you have a linked list like:

Code:

typedef struct myrecords
{
  int number1;
  long value;
  struct myrecords *next;
} MYRECORDS;

and then you create a pointer to this structure:
MYRECORDS recordptr = NULL;

and as you create every record with the maloc command you set the value of *next as NULL

and then in your function to add the data its just a matter of doing something like:

Code:

int addvalue(MYRECORDS **recordptr, MYRECORDS *temprecord)
{
  MYRECORDS *tempptr=*recordptr;
  if(*recordptr==NULL)           //IF NO RECORDS EXIST
  {
    *recordptr = (MYRECORDS *) malloc(sizeof(MYRECORDS));
    tempptr=*recordptr;
  }
  else
  {
    while(tempptr->next!=NULL)
      tempptr = tempptr->next;
    tempptr->next = (MYRECORDS *) malloc(sizeof(MYRECORDS));
    if(tempptr->next == NULL)
    {
      printf("MEMORY FULL\n");
      return 1;
    }
  }
  tempptr->next=NULL;
  tempptr->number1=temprecord->number1;
  tempptr->value=temprecord->value;
  return 0;
}

hope this helps a little in understanding it all, basically you always keep your list's 'next' pointer equal to NULL then when to find the list you go through the list until you reach NULL and thats where you put your record.

Thanks, I understand what you're saying but I need to do something a little different. In my main program, I will need to add a lot of records to the end of the list. To make that process more useful, I thought I'd keep track of the "tail" of the list at all times and send the tail pointer to the add function. That way I won't have to loop around and find where to add the record, cause i'll have the pointer tail.

In theory, I pretty much understand what i have to do, but i get lost trying to use that tail pointer...

So create another structure like so

Code:

typedef struct node_tag {
  struct node_tag *next;
  int data;
} node;

typedef struct {
  node *head;
  node *tail;
} list;

An empty list is
list my_list = { NULL, NULL };

And an insert tail function might look like this

Code:

void add_tail ( list *mylist, int data ) {
  node *newnode = malloc( sizeof(node) );
  newnode->next = NULL;
  newnode->data = data;
  if ( mylist->head == NULL ) {
    mylist->head = mylist->tail = newnode;
  } else {
    mylist->tail->next = newnode;
    mylist->tail = newnode;
  }
}

And you would call it
add_tail ( &my_list, 1 );
add_tail ( &my_list, 2 );
add_tail ( &my_list, 3 );

ok we'll if I understand it correctly you want to keep 1 pointer which will point to the front of the list and one to the very last one. Probably easiest way would be slight modification from my last post:

Code:

int addvalue(MYRECORDS **lastptr, MYRECORDS *temprecord)
{
  MYRECORDS *tempptr=*lastptr;
  if(*recordptr==NULL)           //IF NO RECORDS EXIST
  {
    *recordptr = (MYRECORDS *) malloc(sizeof(MYRECORDS));
    tempptr=*recordptr;
  }
  else
  {
    while(tempptr->next!=NULL)
      tempptr = tempptr->next;
    tempptr->next = (MYRECORDS *) malloc(sizeof(MYRECORDS));
    if(tempptr->next == NULL)
    {
      printf("MEMORY FULL\n");
      return 1;
    }
  }
  tempptr->next=NULL;
  tempptr->number1=temprecord->number1;
  tempptr->value=temprecord->value;
  *lastptr=tempptr;   // SAVES THE POINTER OF THE LAST RECORD
  return 0;
}

ok and in the main function you would do something like

Code:

int main()
{
MYRECORDS *mainptr=NULL;
MYRECORDS *lastptr=NULL;
MYRECORDS temprecord;

// Create a record here called temprecord

addvalue(&lastptr,&temprecord);
if(mainptr==NULL)    // Make mainptr point to the first record
  mainptr=lastptr;

and loop around the last 3 statements everytime you add a record, because your passing the memory address of lastptr it can be updated inside the addvalue function, alternativally you could make it a global variable, eliminating the need for passing extra pointers to the function.

I pretty much understand what i have to do, but i get lost trying to use that tail pointer

What is so hard about keeping track of the address of something in memory? Geeeezzzzz. Doesn't matter if it's the first object, middle object, or last object. It's just an address of a RAM object.

And I have to ask-- what does this have to do with Radix sorting? Radix sorting is used to sort using partial keys, not doing comparisons of entire keys.