Again, Circular Linked list ???

This is a discussion on Again, Circular Linked list ??? within the C Programming forums, part of the General Programming Boards category; Dear Friends; First, thanks ( Mr. Salem) and others. Another, I became a member of this sites and my ID ...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    11

    Circular Linked list, again problem ???

    Dear Friends;
    First, thanks ( Mr. Salem)
    and others. Another, I became a member of this sites and my ID is yescha, now.
    Here is my linked list and I am trying to change it circular. But I am not able to change. It prints very strange when I changed its last link to head.
    So, please suggest me and send me if you have any solutions or such programms.

    ***********Program***********
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    struct node *head = (struct node *) NULL;
    struct node *end = (struct node *) NULL;

    struct node * initnode( char *, int );
    void printnode( struct node * );
    void printlist( struct node * );
    void add( struct node * );
    void insertnode( struct node * );

    struct node {
    char name[20];
    int id;
    struct node *next;
    };

    struct node * initnode( char *name, int id )
    {
    struct node *ptr;
    ptr = (struct node *) malloc( sizeof(struct node ) );
    if( ptr == NULL )
    return (struct node *) NULL;
    else {
    strcpy( ptr->name, name );
    ptr->id = id;
    return ptr;
    }
    }

    void printnode( struct node *ptr )
    {
    printf("Name : %s\n", ptr->name );
    printf("ID : %d\n", ptr->id );
    }


    void printlist( struct node *ptr )
    {
    while( ptr != NULL )
    {
    printnode( ptr );
    ptr = ptr->next;
    /* when I insert here if (ptr==head) break; it is not working */
    /* printing same thing infininely */
    /* Can you say why???? */
    }

    }

    void add( struct node *new )
    {
    if( head == NULL )
    head = new;
    end->next = new;
    new->next = NULL;
    end = new;
    }

    void insertnode( struct node *new )
    {
    struct node *temp, *prev;

    if( head == NULL ) {
    head = new;
    end = new;
    head->next = NULL;
    return;
    }

    temp = head;
    while( strcmp( temp->name, new->name) < 0 ) {
    temp = temp->next;
    if( temp == NULL )
    break;
    }

    if( temp == head ) {
    new->next = head;
    head = new;
    }
    else {
    prev = head;
    while( prev->next != temp ) {
    prev = prev->next;
    }
    prev->next = new;
    new->next = temp;
    if( end == prev )
    end = new;
    }
    }


    main()
    {
    char name[20];
    int id, ch = 1;
    struct node *ptr;

    clrscr();
    while( ch != 0 ) {
    printf("1 add a name \n");
    printf("2 list all names \n");
    printf("3 insert a name \n");
    printf("0 quit\n");
    scanf("%d", &ch );
    switch( ch )
    {
    case 1: /* add a name to end of list */
    printf("Enter in name -- ");
    scanf("%s", name );
    printf("Enter in id -- ");
    scanf("%d", &id );
    ptr = initnode( name, id );
    add( ptr );
    break;
    case 2: /* list all nodes */
    printlist( head );
    break;
    case 5: /* insert a name in list */
    printf("Enter in name -- ");
    scanf("%s", name );
    printf("Enter in id -- ");
    scanf("%d", &id );
    ptr = initnode( name, id );
    insertnode( ptr );
    break;

    }
    }
    }


    ** I changed * changed the add and insert to similarly but not working .......*/
    Please, help me if any one has any idea regarding this
    I am also trying...........

    BYE!!!!!
    Last edited by yescha; 11-17-2001 at 06:28 PM.

  2. #2
    Sayeh
    Guest

    Circular Linked List

    This is also called a head & tail queue.


    Basics:
    ========
    You have n number of nodes in your linked list. These can grow, or shrink in number.

    You have a 'next' and a 'previous' link in each node.

    The 'head' pointer points to your virtual 'first' node.

    The 'tail' pointer points to your virtual 'last' node.

    head & tail are never the same unless--

    - nothing in list
    - only 1 entry in list
    - head or tail has overrun the other pointer

    ---------

    For example:

    typedef struct nodeStruc
    {
    struct nodeStruct *next; /* previous node */
    struct nodeStruct *prev; /* next node */
    short field_1; /* fields */
    long field_2;
    ...
    long *userData;
    }node,*nodeP;


    Insertion, deletion, and all that is very easy to do. Having both a 'next' and a 'prev' pointer allows you to easily traverse the linked list in multiple directions. This allows much easier head/tail management when a node is deleted/inserted.

    Let's say we've dynamically allocated 5 such nodes. Further, for our example, let's say that each node has the following (arbitrary) address in RAM:

    Address Node
    ---------------------------------------
    0x00438462 1 <- h
    0x00436388 2
    0x0044A73E 3
    0x005CA019 4
    0x0067A3B6 5 <- t

    head = 0x00438462
    tail = 0x0067A3B6

    ----

    If we look at the linking fields in 'head', they appear as follows:

    head->prev = 0x0067A3B6
    head->next = 0x00436388

    Likewise for 'tail':

    tail->prev = 0x005CA019
    tail->next = 0x00438462

    -----

    If a node were inserted in the middle, it would appear as follows:


    Address Node
    ---------------------------------------
    0x00438462 1 <- h
    0x00436388 2
    0x0044A73E 3
    0x003A67D8 6 <- new node
    0x005CA019 4
    0x0067A3B6 5 <- t

    Neither 'head' nor 'tail' would be changed at all-- they are oblivious to the addition.

    ===========================

    Okay, now for a basic point-- The usual reason you have a circular linked list, is because your application is "pulling" information off the head of the list while new information is being "pushed" onto the tail of the list.

    For example, let's say you are writing a GUI. In this GUI, you will need to read "events". These events can be defined as:

    mouse down
    mouse up
    disk insert
    window update
    window activation
    window deactivation
    key up
    key down
    idle

    The structure for the event might be something like:

    typedef struct eStruc
    {
    struct eStruc *prev; /* previous event */
    struct eStruc *next; /* next event */
    long clock; /* time event occurred
    portP window; /* which window event occurred in */
    int event; /* kind of event */
    long msg; /* data associated with event */
    ...
    USERPROC callback; /* user defined callback */
    }eventRec;

    Now, suppose that the person double-click's the mouse-- That would generate 4 events. mouse down, mouse up, mouse down, mouse up. Other events (such as activation, or idle events might occur between the two mouse events)...

    In short, you register that the hardware event has occurred, you go to the tail of the list, increment it to the next position and fill that node in with the information about the event. This is doen for each event.

    It is assumed that other things are 'pulling' events off the queue fast enough so that your tail never runs into your head pointer. If this does occur, it means the queue needs more initial nodes.

    Most operating systems only have 20 nodes in their event queue.

    ----

    Okay, now that you've built a GUI, you have also had to build a 'toolbox' or 'api' that applications can call, that wish to use your GUI. One of those functions you've provided is

    Bool GetAnEvent(eventRec*);

    When an application calls this procedure, your GUI copies the information out of 'head' into the storage space the application has provided an address to. The GUI then increments 'head' to the next position in the queue.

    Ideally, 'head' should be incrementing through the queue faster than 'tail', because this would indicate that applications are pulling events off the queue faster than they are being generated and pushed on the queue. In this case, if 'head' and 'queue' were equal, it would indicate that no events were pending in the queue, and the system could then generate an idle event, in order to parcel free time out to applications to do with as they wished.

    The application writer's code might look like this:

    int main(void)
    {
    eventRec myEvent;
    Bool eventFlag;
    Bool doneFlag;

    doneFlag = FALSE; /* TRUE when user hits 'quit' */

    while(!doneFlag)
    {
    eventFlag = GetAnEvent(&myEvent);
    if(eventFlag)
    {
    switch(myEvent->event)
    {
    case mousedown:
    break;
    case mouseup:
    break;
    case diskinsert:
    break;
    case wupdate:
    break;
    case activate:
    break;
    case deactivate:
    break;
    case keydown:
    switch(msg & 0x000000FF)
    {
    case 'q':
    case 'Q':
    doneFlag = TRUE;
    break;
    };
    break;
    case keyup:
    break;
    case idle:
    break;
    };
    };
    };

    /* cleanup and exit */
    }

    -----

    Okay, I wandered a little bit there, but it can be really useful to put a context around things...

    enjoy.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    You know, the problem is that you seem to want to use a circular linked list for a situation where a circular list really is unsuitable. So a few things...
    1) Do you really have to use a circular list? I mean, is it an assignment or something (As you can see, the posters here are more than willing to put good uses of it's use )

    2) Are there some global variables not included in the code? Your head and tale variables seem to elude me.

    3) I suggest using code tags as spacing does a lot to help understand code.... that is...something like this...
    [codee]int main()
    {
    printf ("When using code tags, don't spell it codee.\n");
    return 0;
    }[/codee]
    Callou collei we'll code the way
    Of prime numbers and pings!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 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