Linked List implementation of Queue

This is a discussion on Linked List implementation of Queue within the C Programming forums, part of the General Programming Boards category; I am trying to create a queue using LL implementation that will be used for Radix Sort. The algorithm of ...

  1. #1
    Registered User
    Join Date
    Oct 2001
    Posts
    1

    Question Linked List implementation of Queue

    I am trying to create a queue using LL implementation that will be used for Radix Sort.

    The algorithm of the radix sort is described as follows:
    (a) Read in the numbers from a file and create a queue called
    Master.
    (b) Create 10 other queues called Subqueue[0], Subqueue
    [1],. . . ,Subqueue[9].
    (c) Remove a number from the Master queue and extract its most
    right digit (ones).
    (d) Add the number to the Subqueue[digit]
    (e) Repeat the (c) and (d) until Master queue is empty.
    (f) Remove the first element from the Subqueue[0] and insert it
    into the Master queue.
    (g) Repeat the previous step until the Subqueue[0] is empty.
    (h) Repeat the last step for consecutive Subqueue[i] where i
    takes on values from 2 to 9.
    (i) Repeat the procedure starting from (b) Max times where the
    value of Max is equal to the number of digits
    in the largest number of the sequence.

    I don't know how to start (newbie). Can someone please help.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    Start by creating a few functions to allow you to insert and remove items (in this case ints).

    Code:
    typedef struct _ll_node {
        int data;
        struct _ll_node *next;
    } ll_node;
    So then you can declare
    ll_node *master;
    ll_node *subqueue[10];

    And perhaps a function with this prototype
    ll_node *add_to_list ( ll_node *head, int data );

    And you would perhaps call it like
    master = add_to_list( master, my_data );
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Unregistered
    Guest
    Originally posted by Salem


    ....
    ....

    And perhaps a function with this prototype
    ll_node *add_to_list ( ll_node *head, int data );

    And you would perhaps call it like
    master = add_to_list( master, my_data );


    Can we return the new value of master without using a return statement?? I mean return it by reference to an argument???





  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > Can we return the new value of master without using a return statement?
    Yes, like so

    And perhaps a function with this prototype
    void add_to_list ( ll_node **head, int data );

    And you would perhaps call it like
    add_to_list( &master, my_data );
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    11
    Originally posted by Salem
    > Can we return the new value of master without using a return statement?
    Yes, like so

    And perhaps a function with this prototype
    void add_to_list ( ll_node **head, int data );

    And you would perhaps call it like
    add_to_list( &master, my_data );

    Can you tell me which is the preferred way? Which one is used more often... The return statement or by reference to an argument?
    The ** confuses me..
    head point to the pointer who's value we want to change????
    The pointer we want is *head???

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > Can you tell me which is the preferred way?
    Both are valid, and both are useful.

    > Which one is used more often... The return statement or by reference to an argument?
    I'd go for the return, but that's just me.

    > The pointer we want is *head???
    Thats it, you would say
    Code:
    ll_node *new_node = malloc( sizeof( ll_node ) );
    // some code which decides new_node should be the head
    *head = new_node;
    It's all about counting & and *'s - an & (indirection) in the caller function has to be balanced by a *(dereference) in the called function, in order to update the caller's variable.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 12:56 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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