Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Double circular linked list (http://www.go4expert.com/articles/double-circular-linked-list-t1281/)

shabbir 27Aug2006 18:37

Double circular linked list
 
Implementation os some some elementary operations like insert, delete, search on doubly circular linked list.
Code: C

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
#define N 100

struct dclinklist
{
    struct dclinklist *prev;  /** Stores address of previous node **/
    int roll_no;                   /** stores roll number **/
    char name[N];             /** stores Name **/
    float marks;              /** stores Marks **/
    struct dclinklist *next;  /** stores address of next node **/
};

/** Redefining dclinklist as node **/
typedef struct dclinklist node;

void init(node*);     /** Input function **/
void ins_aft(node*)/** Function inserting before **/
node* ins_bef(node*); /** Function inserting after **/
node* del(node*);     /** Function deleting a node **/
void search(node*);   /** Function for searching node **/
void disp(node*);     /** Function for displaying node **/
void rollsrch(node*); /** Function for searching node by roll number **/
void namesrch(node*); /** Function for searching node by name **/
void marksrch(node*); /** Function for searching node by marks **/

/*** Main Function ***/
void main()
{
    node *head;
    char ch;                  /* Choice inputing varible */
    int opt;                  /* Option inputing variable*/
    static int flag=0;        /* Unchanged after iniialization */
    clrscr();
    head=(node*)malloc(sizeof(node));
    head->next=NULL; /* NULL is being over written in init function */
    head->prev=NULL;
    do
    {
again:
    printf("\nEnter your option\n");
    printf("\n1. Initialize the node\n");
    printf("\n2. Insert before a specified node\n");
    printf("\n3. Insert after a specified node\n");
    printf("\n4. Delete a particular node\n");
    printf("\n5. Search the nodes\n");
    printf("\n6. Display all the nodes\n");
    scanf("%d",&opt);
    if(flag==0 && opt!=1)
    {
        printf("\nNo. You must first initialize at least one node\n");
        goto again;
    }
    if(flag==1 && opt==1)
    {
        printf("\nInitialisation can occur only once.\n");
        printf("\nNow you can insert a node\n");
        goto again;
    }
    if(opt==4 && head->next==head)
    {
        printf("\nYou cannot delete the one and only the single node\n");
        goto again;
    }
    if(flag==0 && opt==1)
        flag=1;
    switch(opt)
    {
    case 1:
        init(head);
        break;
    case 2:
        head=ins_bef(head);
        break;
    case 3:
        ins_aft(head);
        break;
    case 4:
        head=del(head);
        break;
    case 5:
        search(head);
        break;
    case 6:
        disp(head);
        break;
    }
    printf("\nDo you wish to continue[y/n]\n");
    ch=(char)getche();
    }while(ch=='Y' || ch=='y');
    printf("\nDone by \"SHABBIR\"\n");
    printf("\nPress any key to exit\n");
    getch();
}

/*** Function for inputing data ***/
void init(node *start)
{
    start->prev=start;
    printf("\nEnter Roll number\n");
    scanf("%d",&start->roll_no);
    printf("\nEnter the name\n");
    fflush(stdin);
    gets(start->name);
    printf("\nEnter the marks\n");
    scanf("%f",&start->marks);
    start->next=start;
}

/*** Function for inserting a node after a specified node ***/
void ins_aft(node *start)
{
    int rno;                  /* Roll number for inserting a node */
    int flag=0;
    node *newnode;            /* New inputed node*/
    node *current;            /* Node for travelling the linked list*/
    newnode=(node*)malloc(sizeof(node));
    printf("\nEnter the roll number after which you want to insert a node\n");
    scanf("%d",&rno);
    init(newnode);
    current=start;
    while(current->next!=start)
    {
        /***  Insertion checking for all nodes except last  ***/
        if(current->roll_no==rno)
        {
            newnode->next=current->next;
            current->next->prev=newnode;
            current->next=newnode;
            newnode->prev=current;
            flag=1;
        }
        current=current->next;
    }
    if(flag==0 && current->next==start && current->roll_no==rno)
    {
        /***  Insertion checking for last node  ***/
        newnode->next=current->next;     /* Start is being copied */
        current->next->prev=newnode;
        current->next=newnode;
        newnode->prev=current;
        flag=1;
    }
    if(flag==0 && current->next==NULL)
        printf("\nNo match found\n");
}

/*** Function for inserting a node before a specified node ***/
node* ins_bef(node *start)
{
    int rno;                  /* Roll number for inserting a node*/
    node *newnode;            /* New inputed node */
    node *current;            /* Node for travelling the linked list*/
    newnode=(node*)malloc(sizeof(node));
    printf("\nEnter the roll number before which you want to insert a node\n");
    scanf("%d",&rno);
    init(newnode);
    current=start;
    if(current->roll_no==rno)
    {
        /*** Insertion checking for first node ***/
        newnode->next=current;
        current->prev=newnode;
        while(current->next!=start)
            current=current->next;
        newnode->prev=current;
        current->next=newnode;
        start=newnode;
        return(start);
    }
    while(current->next!=start)
    {
        /*** Insertion checking for all node except first ***/
        if(current->next->roll_no==rno)
        {
            newnode->next=current->next;
            current->next->prev=newnode;
            current->next=newnode;
            newnode->prev=current;
            return(start);
        }
        current=current->next;
    }
    /*
    If the function does not return from any return statement.
    There is no match to insert before the input  roll number.
    */

    printf("\nMatch not found\n");
    return(start);
}

/*** Function for deleting a specified node ***/
node* del(node *start)
{
    int rno;                  /* Roll number for deleting a node*/
    node *delnode;            /* Node to be deleted */
    node *current;            /* Node for travelling the linked list*/
    printf("\nEnter the roll number whose node you want to delete\n");
    scanf("%d",&rno);
    current=start;
    if(current->roll_no==rno)
    {
        /***  Checking condition for deletion of first node  ***/
        delnode=current; /*  Unnecessary step  */
        while(current->next!=start)
            current=current->next;
        current->next=start->next;
        start->next->prev=current;
        start=start->next;
        free(delnode);
        return(start);
    }
    else
    {
        while(current->next->next!=start)
        {
            /***  Checking condition for deletion of   ***/
            /*** all nodes except first and last node  ***/
            if(current->next->roll_no==rno)
            {
                delnode=current->next;
                current->next=current->next->next;
                current->next->prev=current;
                free(delnode);
                return(start);
            }
            current=current->next;
        }
        if(current->next->next==start && current->next->roll_no==rno)
        {
            /***  Checking condition for deletion of last node  ***/
            delnode=current->next;
            free(delnode);
            current->next=start;
            return(start);
        }
    }
    printf("\nMatch not found\n");
    return(start);
}

/*** Function for searching a node ***/
void search(node *start)
{
    int ch;                   /* Choice inputing variable */
    printf("\nEnter the criteria for search\n");
    printf("\n1. Roll number\n");
    printf("\n2. Name\n");
    printf("\n3. Marks\n");
    scanf("%d",&ch);
    switch(ch)
    {
    case 1:
        rollsrch(start);
        break;
    case 2:
        namesrch(start);
        break;
    case 3:
        marksrch(start);
        break;
    default:
        rollsrch(start);
    }
}

/*** Function for searching a specified roll number ***/
void rollsrch(node *start)
{
    int rno;                  /* Roll-number to be searched */
    node *current;            /* Node for travelling the linked list*/
    printf("\nEnter the roll number to search\n");
    scanf("%d",&rno);
    current=start;
    while(current->next!=start)
    {
        if(current->roll_no==rno)
            printf("\n%d\t%s\t%f\n",current->roll_no,current->name,current->marks);
        current=current->next;
    }
    if(current->next==start && current->roll_no==rno)
        printf("\n%d\t%s\t%f\n",current->roll_no,current->name,current->marks);
}

/*** Function for searching a specified name ***/
void namesrch(node *start)
{
    char arr[20];             /* Name to be searched*/
    node *current;            /* Node for travelling the linked list*/
    printf("\nEnter the name to search\n");
    fflush(stdin);
    gets(arr);
    current=start;
    while(current->next!=start)
    {
        if(strcmp(current->name,arr)==NULL)
            printf("\n%d\t%s\t%f\n",current->roll_no,current->name,current->marks);
        current=current->next;
    }
    if(current->next==start && strcmp(current->name,arr)==NULL)
        printf("\n%d\t%s\t%f\n",current->roll_no,current->name,current->marks);
}

/*** Function for searching a specified marks ***/
void marksrch(node *start)
{
    float marks;              /* Marks to be searched */
    node *current;            /* Node for travelling the linked list*/
    printf("\nEnter the marks to search\n");
    scanf("%f",&marks);
    current=start;
    while(current->next!=start)
    {
        if(current->marks==marks)
            printf("\n%d\t%s\t%f\n",current->roll_no,current->name,current->marks);
        current=current->next;
    }
    if(current->next==start && current->marks==marks)
        printf("\n%d\t%s\t%f\n",current->roll_no,current->name,current->marks);
}

/*** Function for displaying the linked list ***/
void disp(node *start)
{
    node *current;            /* Node for travelling the linked list*/
    current=start;
    while(current->next!=start)
    {
        printf("\n %d  %s  %f",current->roll_no,current->name,current->marks);
        current=current->next;
    }
    printf("\n %d  %s  %f",current->roll_no,current->name,current->marks);
}


mirchix 11Jan2008 17:37

Re: Double circular linked list
 
I'm a Btech final year student, this code is definitely a good one however I find a better
one here http://www.openasthra.com/c-tidbits/...-or-tail-node/
let me know your opinion.

shabbir 11Jan2008 19:00

Re: Double circular linked list
 
I don't see any difference but yes its a bit more explained the above one is more commented.

chintzz 2Oct2008 14:58

Re: Double circular linked list
 
supply a downloadable version buddy

hkp819 5Dec2008 15:25

Re: Double circular linked list
 
hello, this is very easy to understand and useful for beginners.
I am beginner in c++. I understood it easily.
That is very help full for me.

elois 30May2009 19:47

Re: Double circular linked list
 
this is a nice and easy code even for me who i am very new person in this stuff. I have a question about the function clrscr() , what is this function doing ?? Please help me

xpi0t0s 30May2009 23:31

Re: Double circular linked list
 
Quote:

Originally Posted by elois (Post 48638)
this is a nice and easy code even for me who i am very new person in this stuff. I have a question about the function clrscr() , what is this function doing ?? Please help me

It clears the screen and IMHO compiler specific code like that shouldn't be in generic code examples.

Quote:

Originally Posted by chintzz (Post 36688)
supply a downloadable version buddy

So you haven't worked out how to use copy and paste yet then? Select some text with your mouse (press the left button, drag, release), press Ctrl-C, start Notepad then press Ctrl-V.

elois 30May2009 23:35

Re: Double circular linked list
 
thank you very much :-)

gemwebhost.com 1Jun2009 12:18

Re: Double circular linked list
 
i am beginner in c++. i request all of to help me, i think it is really difficult, but anyhow i want to learn it. so please i request to guide me
thanks,


All times are GMT +5.5. The time now is 19:14.