Linked list & radix sort question, please help!

This is a discussion on Linked list & radix sort question, please help! within the C Programming forums, part of the General Programming Boards category; Hey everyone, I'm in my first year in college and I've been cracking my brain for about a week over ...

  1. #1
    Registered User
    Join Date
    Aug 2002
    Posts
    5

    Question 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

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    95
    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.

  3. #3
    Registered User
    Join Date
    Aug 2002
    Posts
    5

    Re: Linked list & radix sort question, please help!

    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...

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,556
    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 );

  5. #5
    Registered User
    Join Date
    Mar 2002
    Posts
    95
    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.

  6. #6
    Visionary Philosopher Sayeh's Avatar
    Join Date
    Aug 2002
    Posts
    212
    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.
    It is not the spoon that bends, it is you who bends around the spoon.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  3. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 04:16 PM
  4. Linked list question
    By caduardo21 in forum C Programming
    Replies: 2
    Last Post: 01-30-2005, 12:29 AM
  5. sort linked list using BST
    By Micko in forum C Programming
    Replies: 8
    Last Post: 10-04-2004, 02:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21