Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/articles/c-tutorials/)
-   -   Circular linked list (http://www.go4expert.com/articles/circular-linked-list-t1282/)

shabbir 27Aug2006 18:40

Circular linked list
 
Program for singly circular linked list which inserts, deletes, searches .... data in it

Code: C

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

/*****  Structure template  *****/
struct list{
    int roll_no;
    char name[20];
    float marks;
    struct list *next;
};

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

void init(node*);
void ins_aft(node*);       /*** FUNCTION FOR DELETING A NODE AFTER ***/
node* ins_bef(node*);      /*** FUNCTION FOR INSERTING A NODE BEFORE ***/
node* del(node*);          /*** FUNCTION FOR DELETING A NODE ***/
void search(node*);        /*** FUNCTION FOR SEARCHING CRITERIA INPUT ***/
void disp(node*);          /*** FUNCTION DISPLAYING THE NODES ***/
void rollsrch(node*);      /*** FUNCTION SEARCHING THROUGH ROLL NUMBER ***/
void namesrch(node*);      /*** FUNCTION SEARCHING THROUGH NAME ***/
void marksrch(node*);      /*** FUNCTION SEARCHING THROUGH MARKS ***/

/*****  Main function  *****/
void main()
{
    node *head;               /* HEAD OF THE LINK LIST */
    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 */
    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();
}

/*****  Initialisation function  *****/
void init(node *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 before a particular 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));
    current=start;
    printf("\nEnter the roll number before which you want to insert a node\n");
    scanf("%d",&rno);
    init(newnode);
    if(current->roll_no==rno)
    {
        newnode->next=start;
        while(current->next!=start)
            current=current->next;
        current->next=newnode;
        start=newnode;
        return(start);
    }
    while(current->next!=start)
    {
        if(current->next->roll_no==rno)
        {
            newnode->next=current->next;
            current->next=newnode;
            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 inserting after a particular 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=newnode;
            flag=1;
        }
        current=current->next;
    }
    if(flag==0 && current->next==start && current->roll_no==rno)
    {
        /***  Insertion checking for last nodes  ***/
        newnode->next=current->next;    /** start is copied in newnode->next**/
        current->next=newnode;
        flag=1;
    }
    if(flag==0 && current->next==start)
        printf("\nNo match found\n");
}

/*****  deletion function  *****/
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=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;
                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);
}

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);
    }
}

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

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

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

/*****  Output displaying function  *****/
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);
}


Peter_APIIT 31Jan2008 09:45

Re: Circular linked list
 
Good article.

My circular link list concept is tail-> next = head;

Code:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>  // memset

#include "Link_List.h"

// -------------------------------------------------------
/*
  1. Insert Behind            // Done
  2. Insert In Front          // Done
  3. Random Insert Front-nth  // Done
  4. Remove Behind until zero or one only    // Done
  5. Remove In Front          // Done
  6. Random Remove -nth          // Done
  7. Display                    // Done
  8. Length  Index            // Done
  9. Palindrome
  10. Full Reverse            // Circular Link List
  11. merge                    // Done  SortedMerge MergeSort
  12. Count a particular int
  13. Get_Node_At_Index        // Done
  14. Split List
  15. Remove Duplicates
  16. Swap
  17. Empty          // Done
  18. Calcualte number of node can malloc
      from heap memory


Random cannot operate in head and tail

Double Link List
Double Circular Link List
Associate Link List
Skip List

Josephus problem

Searching
move-to-front heuristic = Once an elemnt found move to
                          first node
Index

*/

 /*
        Random must have a index to indicate the postion where
    almost same as array in order to achieve fast
        processing
*/


// -------------------------------------------------------

// tail->next = head; Circular Link List

void draw();

// --------------------List Function----------------------

struct LList* list_allocate(struct LList *);
void list_deallocate(struct LList *);

void Initialize_List(struct LList *);

int LList_ValidateIsAlloc(struct LList *);


struct LList* InsertBehind(struct LList *, struct node *);
struct LList* InsertFront(struct LList *, struct node*);
struct LList* RandomInsert(struct LList *, struct node*);
// Random Insert cannot insert at head and tail

struct LList* RemoveBehind(struct LList *);
struct LList* RemoveFront(struct LList *);
struct LList* RandomRemove(struct LList *);
// Random Remove cannot remove head and tail

struct LList* MergeList(struct LList *, struct LList *);


int get_Value_at_index(struct LList *);

int Validate_Index(struct LList *, int);
int isEmpty(struct LList *);
int length_of_List(struct LList *); 


// --------------------Node Function----------------------

struct node* node_allocate();
void node_deallocate(struct node *);


void Initialize_node(struct node *, int *);
int node_validateIsAlloc(struct node *); 

void userInput(int *);
void display(const struct LList *);



// ------------------------------------------------------
int main(int argc, char *argv[]) // char **argv
{
        struct LList *myList = 0;
        struct LList *myListSecond = 0;
        struct node *node;

        int length = 0, result, number, *numberptr;

        numberptr = &number;
       
        draw();
                         
        myList = list_allocate(myList); // Call by reference
        Initialize_List(myList);


// 1 node
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);//        InitializeCurrent(myList, node);
        myList = InsertBehind(myList, node);

// 2 node
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        myList = InsertBehind(myList, node);

// 3 node
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        myList = InsertBehind(myList, node);

// 4 node
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        myList = InsertBehind(myList, node);

// ----------------------------------------------------

// 2 List
        myListSecond = list_allocate(myList);
        Initialize_List(myListSecond);

// 1 node of 2 list
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        myListSecond = InsertBehind(myListSecond, node);

    myList = MergeList(myList, myListSecond);

        // InsertFront
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        myList = InsertFront(myList, node);

        length = length_of_List(myList);
        display(myList);

        // Random Insert
        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        myList = RandomInsert(myList, node);


        length = length_of_List(myList);
        display(myList);


        myList = RemoveBehind(myList);
        display(myList);


        result = get_Value_at_index(myList);

        node = node_allocate();
        userInput(numberptr);
        Initialize_node(node, numberptr);
        InsertBehind(myList, node);

        display(myList);

        myList = RemoveFront(myList);

        display(myList);

        node_deallocate(node);
        list_deallocate(myList);
       
        return 0;
}

// ------------------------------------------------------
void draw()
{
        int loop;

        printf("\n\n\n\t\t");

        for (loop=0;loop<60;loop++)
        {
                printf("-");
        }
       
        printf("\n\n\t\t\t  Welcome to newly Link List Simulation Program");
        printf("\n\n\n\t\t");
        for (loop=0;loop<60;loop++)
        {
                printf("-");
        }
        printf("\n\n\n\n");
       
}
// -------------------------------------------------------
struct LList* list_allocate(struct LList *myList)
{
        int count = 1;

        do
        {
                myList = (struct LList *)malloc(sizeof(struct LList));
                assert(myList != NULL);
        // Ptr must initialize No dangling ptr

                if (count == 2)
                {
                        fprintf(stdout, "\n\t\t\tList Memory Allocation unsuccessful");
                        exit(0);
                }
                count++;
                fflush(stdout);
        }while( LList_ValidateIsAlloc(myList) == 0 && count < 3);

        /*
          Continue to loop even though memory is exhausted
          for first time but not over second times because
          this is unrealistic
        */

        return myList;
}

// -------------------------------------------------------
void list_deallocate(struct LList *myList)
{
        if (myList != NULL)
        {
                free(myList);
                myList = NULL;
        }
        else
        {
                exit(0);
        }
}
// -------------------------------------------------------
void Initialize_List(struct LList *myList)
{
        if (LList_ValidateIsAlloc(myList) != 0) // Not NULL
        {
                myList->head = NULL;
                myList->tail = NULL;
        }
        else
        {
                exit(0);
        }
}
// -------------------------------------------------------
int LList_ValidateIsAlloc(struct LList *myList)
{
        assert(myList != NULL);

        // If allocation is successful, then return true
        if (myList != NULL)
        {
//                fprintf(stdout, "Memory Allocation successful");
                return 1;
        }// Three control structure
        else
        {
                fprintf(stdout, "Memory exhausted");
                return 0;
        }
}
// -------------------------------------------------------
struct node* node_allocate()
{
        struct node *node;
        int count = 1;

        do
        {
                node = (struct node *)malloc(sizeof(struct node));
                assert(node != 0);

                count++;

        }while(        node_validateIsAlloc(node) == 0 && count < 3);


        if (node != NULL)
        {
                return node;
        }
        else
        {
                exit(0);
        }
}

// -------------------------------------------------------
void node_deallocate(struct node *node)
{
        if (node != NULL)
        {
                free(node);
                node = NULL;
        }
        else
        {
                exit(0);
        }
}       
// -------------------------------------------------------
void Initialize_node(struct node *node, int * numberptr)
{
        node->next = NULL;
       
        node->value = *numberptr;
}
// -------------------------------------------------------
int node_validateIsAlloc(struct node *node)
{
        // If allocation is successful, then return true
        if (node != NULL)
        {
                fprintf(stdout, "\n\n\t\t\tNode Memory Allocation successful");
                return 1;
        }
        else
        {
                fprintf(stdout, "Memory exhausted");
                return 0;
        }
}
// ------------------------------------------------------
void userInput(int *numberptr)
{
        int number;
       
        fflush(stdin);
        printf("\n\n\t\t\t\tEnter a value : ");
        fflush(stdin);
        scanf("%d", &number);

        *numberptr = number;
}
// ------------------------------------------------------
struct LList* InsertBehind(struct LList *myList, struct node *node)
{       
        if (myList->head == NULL)
        {
                myList->head = node;
                myList->tail = node;        // Traversal ptr         

                myList->tail->next = NULL;
                node->previous = NULL;
                node->next = NULL;

                return myList;
        }
        else
        {
                while (myList->tail != NULL)
                {
                        myList->tail->next = node;  // Previous node point to newly node
                        node->previous = myList->tail;  // New node point to previous node 
                        myList->tail = node;  // Traversal to new node       
                        return myList;
                }
        }
}
// ------------------------------------------------------
struct LList* InsertFront(struct LList *myList, struct node *node)
{
        struct LList *tempHead;
       
        tempHead = (struct LList *)malloc(sizeof(struct LList *));
    assert(tempHead != 0);

        if ( LList_ValidateIsAlloc(tempHead) == 1 )
        {
                tempHead->head = myList->head;
                node->next = myList->head;
                node->previous = NULL;
                myList->head = node;
        }
        else
        {
                exit(0);
        }

        free(tempHead);

        return myList;
}
// ------------------------------------------------------
struct LList* RandomInsert(struct LList *myList, struct node *node)
{
        struct node *traversal_First;
        struct node *traversal_Second;
        struct node *dummy_one;
        struct node *dummy_two;

        // Position of node insert
        int index, length = 1;

        traversal_First = myList->head;
        traversal_Second = myList->head;
        dummy_one = myList->head;
        dummy_two = myList->head;

        do
        {
                printf("\n\n\t\t\t\tEnter a index : ");
                scanf("%d", &index);  // Validate index no exceed length of list
       
                if ( Validate_Index(myList, index) == 1 )
                {
                        length = 1;
                        while (myList->tail != NULL && traversal_Second != NULL)
                        {
                                if (length == index)
                                {
                                        traversal_First = traversal_First->previous;
                                        traversal_First->next = node;
                                        node->next = traversal_Second;
                                        node->previous = traversal_First;
                                        traversal_Second->previous = node;
                                        goto exit;
                                }

                                traversal_First = traversal_First->next;
                                traversal_First->previous = dummy_one;
                                dummy_one = traversal_First;

                                traversal_Second = traversal_Second->next;
                                traversal_Second->previous = dummy_two;
                                dummy_two = traversal_Second;

                                length++;
                        }
                        exit:
                                return myList;
                }
        }while( Validate_Index(myList, index) == 0);
}
// -----------------------------------------------------
struct LList* RemoveBehind(struct LList *myList)
{
        struct node *traversal;
        struct node *dummy;

        int length = 1, real_length;
        int numberNode;

        real_length = length_of_List(myList);

        do
        {
                fprintf(stdout, "\n\n\t\t\tHow many removed node count from behind : ");
                scanf("%d", &numberNode);
        }while(numberNode > real_length || numberNode == 0);
       
        traversal = myList->head;

        length = 1;
        while (traversal->next != NULL)
        {
                traversal = traversal->next;
                length++;
        }

        // 1 2 3 4 5
        numberNode = length - numberNode;

        do
        {
                dummy = myList->tail;
                myList->tail = myList->tail->previous;
                dummy->value = NULL;
                node_deallocate(dummy); // free what pointed by dummy  Error
                length--;

        }while(length != numberNode);

        myList->tail->next = NULL;

        return myList;

}
// -----------------------------------------------------
struct LList* RemoveFront(struct LList *myList)
{
        struct node *removeHead, *removeTail, *traversal, *dummy;
        int numberNode, length, loop;

        removeHead = myList->head;
        removeTail = myList->head;
        traversal = myList->head;
        dummy = myList->head;


        do
        {
                fprintf(stdout, "\n\n\t\t\tHow many removed node count from in front : ");
                scanf("%d", &numberNode);

                length = length_of_List(myList);

        }while(numberNode > length || numberNode == length || numberNode == 0);


        myList->head = myList->head->next;
        for (loop=0;loop<numberNode - 1;loop++)
        {
                myList->head = myList->head->next;
                removeTail = removeTail->next;
        }

        removeTail->next = NULL;
        myList->head->previous = NULL;

        do
        {
                dummy = removeHead;
                removeHead = removeHead->next;
                traversal = traversal->next;

                dummy->value = NULL;
                node_deallocate(dummy);

        }while(traversal != NULL);

        return myList;
}
// ------------------------------------------------------
struct LList* RandomRemove(struct LList *myList)
{
        int indexOne, indexTwo; // To form a range

        fprintf(stdout, "Enter an index or range to remove : ");
       
        fprintf(stdout, "Enter first index : ");
        scanf("%d", &indexOne);

        fprintf(stdout, "Enter first index : ");
        scanf("%d", &indexTwo);

        return myList;
}
// ------------------------------------------------------
struct LList* MergeList(struct LList *first, struct LList *second)
{
        struct node *dummy;

        dummy = first->tail;

        first->tail->next = second->head;  // first list point to second list
        first->tail = first->tail->next;  // traverse to new tail after merge list
        first->tail->previous = dummy;    // tail node point back to second last node

        second = NULL;
        dummy = NULL;
       
        free(second);
        free(dummy);

        return first;
}
// ------------------------------------------------------
int get_Value_at_index(struct LList *myList)
{
        struct node *traversal;
        int length = 1, index, value, real_length;
       
        traversal = myList->head;

        do
        {
                fprintf(stdout, "\n\n\t\t\t\tEnter an index : ");
                scanf("%d", &index);

                real_length = length_of_List(myList);
        }while(index > real_length || index == 0);

        length = 1;
        do
        {
                if (index == length )
                {
                        value = traversal->value;
                        goto exit;
                }

                traversal = traversal->next;
                length++;
        }while (traversal->next != NULL && index != length);
       
        exit:
                value = traversal->value;
                fprintf(stdout, "\n\n\t\t\t\tValue at node %d of list is %d\n\n", index, value);
        return value;
}

// ------------------------------------------------------
int Validate_Index(struct LList *myList, int index)
{
        struct node *traversal;
        int length = 1;

        traversal = myList->head;

        length = 1;

        while (traversal->next != NULL)
        {
                traversal = traversal->next;
                length++;
        }

        if (index < length && index != 0)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}
// ------------------------------------------------------
int isEmpty(struct LList *myList)
{
        if (myList->head == NULL)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}
// ------------------------------------------------------
int length_of_List(struct LList *myList)
{
        struct node *traversal;
        int length = 1;
       
        traversal = myList->head;

        length = 1;
        while (traversal->next != NULL)
        {
                traversal = traversal->next;
                length++;
        }

        printf("\n\n\t\t\t\tLength of List is %d", length);
       

        return length;
}
// ------------------------------------------------------
void display(const struct LList * myList)
{
        printf("\n\n\n");

        struct node *traversal;
        int length;

        traversal = myList->head;

        length = 1;
        while(traversal != NULL)
        {
                printf("\t\t\t\tNode %d of List : %d\n", length, traversal->value);
                traversal = traversal->next;
                length++;
        }
       
}
// ------------------------------------------------------


[/QUOTE]

[QUOTE]
#ifndef _LList_
#define _LList_

// Single Node
struct node
{
        int value;
        struct node *next;
        struct node *previous;
};


// Consists of many nodes
struct LList
{
        struct node *head;
        struct node *tail;
};

       
// Add index to struct

#endif


Any comment about my program ?

Thanks.

shabbir 31Jan2008 17:25

Re: Circular linked list
 
Looks well commented but I have not run it.

Peter_APIIT 9Feb2008 08:37

Re: Circular linked list
 
Any comment about hte program is more than welcome.

Thanks.

lead.smart34 26Feb2008 18:25

Re: Circular linked list
 
Quote:

Originally Posted by Peter_APIIT
Any comment about hte program is more than welcome.

Thanks.

i tried it works

crazytolearn57 26Feb2008 18:32

Re: Circular linked list
 
shabbir's is better

back from retirement 9Nov2008 11:58

Re: Circular linked list
 
yes.......shabbir's is better....

back from retirement 30Nov2008 12:28

Re: Circular linked list
 
Is there any post or article on circular array????

xpi0t0s 30Nov2008 17:38

Re: Circular linked list
 
What are you looking for? C doesn't implement circular arrays, but you can achieve that with a modulo function:
Code:

// warning: untested
int data[size];
void set_circ_array(int data, int index)
{
  arr[index % size] = data;
}
int get_circ_array(int index)
{
  return arr[index % size];
}


Peter_APIIT 1Dec2008 07:58

Re: Circular linked list
 
Array is random access.

How can it be circular array A?

Peter_APIIT 1Dec2008 07:59

Re: Circular linked list
 
Array is random access.

How can it be circular array A?

xpi0t0s 1Dec2008 13:29

Re: Circular linked list
 
Random access and circularity are not mutually exclusive.

back from retirement 3Dec2008 21:16

Re: Circular linked list
 
Excuse me....what I wanted to mean is that we can design a stack or a queue through array implementation. Can we do the same for doubly linked list or circular linked list???

xpi0t0s 3Dec2008 22:08

Re: Circular linked list
 
Probably, but the point of linked lists is that they're dynamic in size, whereas an array is a static size. Why would you want to implement a linked list with an array? (I can think of a reason but I'd like to hear your reason.)

back from retirement 5Dec2008 11:05

Re: Circular linked list
 
Nothing....just interested....I know that array is static....in that case, in the initialisation function, we will take an array of nodes....
And then follow the latter functions as usual...initial no. of nodes will be determined, I mean asked from the user, with their data as well....
But, it is really difficult....I am trying and trying....if I succeed, I will post it in a new article...

skp819 3Feb2009 11:10

Re: Circular linked list
 
It is good post. But when i run it occur some error.
but it is good commented and explain every thing in nice way which is easy to understand.

shabbir 3Feb2009 14:02

Re: Circular linked list
 
What kind of error ?

harris 3Mar2009 11:38

Re: Circular linked list
 
Quote:

Originally Posted by shabbir (Post 42357)
What kind of error ?

Well, it seems like the DO while is not working properly.. When i enter y after 'do ya want to continue' it's forever looping...

btw, shabbir, i need your help on this assignment...

Task

Write a program (YourName_queue.cpp) to implement a circular queue (max 5) to capture the taxis in a queue. Program should maintain the following information:

> License Number (max. 7 characters)
> Driver Name (max. 20 characters)
> Taxi Type (ie Comfort, CityCab, SMRT, Premier, Transcab)

Write a main program that display a menu of choices for user to perform the queue operations. You are to use an appropriate data structure to meet all requirements. Your program shall provide the following functions:

QUEUE OPERATIONS
1. Initialize queue
2. Insert a taxi at back of queue
3. Remove a taxi in front of queue
4. Count number of taxis in queue
5. View all taxis in queue
6. View taxi types in queue
7. Is queue empty?
8. Is queue full?
9. Quit

Functional requirements
1. Initialize queue. This option initializes/clears all items in the queue.
2. Insert a taxi at back of queue. If the queue is not full, program will prompt user to enter the taxi license number. It checks if the taxi already exists in queue. If yes, display error message, else prompt user to enter other taxi’s info and insert into the queue.
3. Remove a taxi in front of queue. If the queue is not empty, program will delete the taxi in front of the queue.
4. Count number of taxis in queue. This option will display the total number of taxis in the queue.
5. View all taxis in queue. This option will display all the taxis’ info in the queue, starting from the first taxi in front of the queue to the last taxi at the rear of the queue.
6. View taxi types in queue. This option will display the breakdown of the taxi types in the queue, ie the number of Comfort, CityCab, SMRT, Premier & Transcab. Assignment 3 Page 2
7. Is queue empty? This option checks whether the queue is empty and print an appropriate message.
8. Is queue full? This option checks whether the queue is full and print an appropriate message.
9. Quit. End the program.
Note: You can assume user will always start the program and initialises the queue (i.e. invoke option (1) first prior to any operations.

If ya got free time, try this program.. thanks..

shabbir 3Mar2009 12:16

Re: Circular linked list
 
I don't do other peoples school assignments and also please do not jump into any thread with your assignment and if you want some help with the assignment like you are stuck somewhere you can post as separate threads and we can help you out.

harris 3Mar2009 13:11

Re: Circular linked list
 
Quote:

Originally Posted by shabbir (Post 43757)
I don't do other peoples school assignments and also please do not jump into any thread with your assignment and if you want some help with the assignment like you are stuck somewhere you can post as separate threads and we can help you out.

Well, i don't usually pop out with this kind of thing but i need it urgent and using blood dev C is really pain in the ar5e.. i tried your progam but it's not working, something is wrong with your do while statement, it's infinite loop..

harris 3Mar2009 13:14

Re: Circular linked list
 
Well, i need a similar sample for my assignement (not really mine but have to do it) but what i found in the internet, most of them are not working with the blood dev c so it's really difficult for me to work it out.. think ya can help me out??

shabbir 3Mar2009 14:45

Re: Circular linked list
 
Quote:

Originally Posted by harris (Post 43759)
Well, i don't usually pop out with this kind of thing but i need it urgent and using blood dev C is really pain in the ar5e.. i tried your progam but it's not working, something is wrong with your do while statement, it's infinite loop..

I am not sure which while loop or function you are referring to but all of them as of the following format

Code:

while(current->next!=start)
which cannot be a infinite one.

Also I ran the program as well and it works perfectly fine on VC++ 6 Environment.

harris 3Mar2009 18:37

Re: Circular linked list
 
Quote:

Originally Posted by shabbir (Post 43766)
I am not sure which while loop or function you are referring to but all of them as of the following format

Code:

while(current->next!=start)
which cannot be a infinite one.

Also I ran the program as well and it works perfectly fine on VC++ 6 Environment.

It's
Code:

While (ch=='Y' || ch=='y');
When i choose 'y', there forever looping.. Well, I tried it in blood dev c environment...

shabbir 3Mar2009 18:46

Re: Circular linked list
 
Choose something else and it would break :D

harris 3Mar2009 19:25

Re: Circular linked list
 
I know about that, i didn't choose anything else.. I chose 'y' and it's not working.. My software is blood dev c so it's really difficult for me to work it out from the sample as it's not working when i tried it.. And ya can call this stuck.. Well, btw, if ya got free time or ya're bored, ya can try that assignment, think it as a lil bit of practise or whatever.. :nice:

shabbir 3Mar2009 20:28

Re: Circular linked list
 
The try Flushing the variable before the input

pandaren23 5Mar2009 13:17

Re: Circular linked list
 
@harris
The program is perfect. Maybe you might just have placed a character value on the roll number or at the mark then it would of course result into an infinite loop.

by the way.. the program was good.. ^_^ it would help me a lot in my machine problem.. thanks for the upload. :p

harris 5Mar2009 14:46

Re: Circular linked list
 
Quote:

Originally Posted by shabbir (Post 43797)
The try Flushing the variable before the input

Very good, it works!! Thank ya m8.. :happy:

shabbir 5Mar2009 14:51

Re: Circular linked list
 
Quote:

Originally Posted by harris (Post 43972)
Very good, it works!! Thank ya m8.. :happy:

The pleasure is all mine.

harris 5Mar2009 16:07

Re: Circular linked list
 
Btw, can ya give me some pointer?? i wanna to limit the queue for just 5.. Yours one seems like no limit there..

shabbir 5Mar2009 16:36

Re: Circular linked list
 
Change the loop condition of 'y' for a variable looping 5 times.

harris 5Mar2009 22:06

Re: Circular linked list
 
Code:


/* Circular Queues */
#include<iostream.h>
#include<conio.h>
#include <stdlib.h>
#include <string.h>
const int MAX = 5;
class cqueue
{
int a[MAX],front,rear;
public :
cqueue()
{
front=rear=-1;
}
void insert(char);
int deletion();
void display();
};
void cqueue :: insert(char TaxLic)
{
if((front==0 && rear==MAX-1) || (rear+1==front))
cout<<" Circular Queue is Full";
else
{
if(rear==MAX-1)
rear=0;
else
rear++;
a[rear]=TaxLic;
}
if(front==-1)
front=0;
}
int cqueue :: deletion()
{
int k;
if(front==-1)
cout<<"Circular Queue is Empty";
else
{
k=a[front];
if(front==rear)
front=rear=-1;
else
{
if(front==MAX-1)
front=0;
else
front++;
}
}
return k;
}
void cqueue :: display()
{
int i;
if(front==-1)
cout<<"Circular Queue is Empty";
else
{
if(rear < front)
{
for(i=front;i<=MAX-1;i++)
cout<<a[i]<<" ";
for(i=0;i<=rear;i++)
cout<<a[i]<<" ";
}
else
{
for(i=front;i<=rear;i++)
cout<<a[i]<<" ";
cout<<endl;
}
}
}
int main()
{
cqueue c1;
char TaxLic [7];
char Dname [20];
char TaxTyp [15];
int ch,val;
char op;
do
{
//clrscr();
system("cls");
cout<<"-----------Menu-------------\n";
cout<<"1.Insertion\n";
cout<<"2.Deletion\n";
cout<<"3.Display\n";
cout<<"4.Exit\n";
cout<<"Enter Your Choice <1..4> ?";
cin>>ch;
switch(ch)
{
case 1 : cout<<"Enter Taxi License Number: ";
fflush(stdin);
gets(TaxLic);
//cin>>val;
 
c1.insert(TaxLic);
break;
case 2 : val=c1.deletion();
cout<<"Deleted Element :"<<val<<endl;
break;
case 3 : c1.display();
break;
}
cout<<"Do you want to continue<Y/N> ?";
fflush(stdin);
cin>>op;
}while(op=='Y' || op=='y');
getch();
}

Help me out, i'm stuck.. Well, it's running ok but when i change the input from int type to char, then it shows error..

shabbir 6Mar2009 08:49

Re: Circular linked list
 
Again the same question. What kind of error. Also if you have some problem with your code try creating a new thread rather than into this thread.

Also intend your code so that its easy to understand

pandaren23 7Mar2009 19:46

Re: Circular linked list
 
Code:

#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

                /*COE116L - C1
          Machine Problem: Implementation of a
            circular linked list!*/

struct Prof
{
    int node_no,nNo,ctr,m,p,nCount,ctr2;
    char name[20],*list[];
    Prof *next;
};

Prof trans;

void Initialize(Prof *start)
{
    cout<<"\nEnter node number: ";
    cin>>start->node_no;
    cout<<"\nEnter the name of the student: ";
    gets(start->name);
    start->next=start;
    trans.nCount++;
}

Prof* ins_bef(Prof *start)
{
    Prof *newnode, *current;
    newnode = new Prof;
    current = start;
    cout<<"\nEnter the node number before which you want to insert a node: ";
    cin>>trans.nNo;
    Initialize(newnode);
    if(current->node_no == trans.nNo)
    {
      newnode->next = start;
      while(current->next != start)
        current = current->next;
      current->next = newnode;
      start = newnode;
      return(start);
    }
    while(current->next!=start)
    {
      if(current->next->node_no == trans.nNo)
      {
        newnode->next=current->next;
        current->next=newnode;
        return(start);
      }
      current = current->next;
    }
    clrscr();
    cout<<"\trans.nNo match found!\n";
    return(start);
}

void ins_aft(Prof *start)
{
    int  x = 0;
    Prof *newnode, *current;
    newnode = new Prof;
    cout<<"\nEnter the node number after which you want to insert a node: ";
    cin>>trans.nNo;
    Initialize(newnode);
    current = start;
    while(current->next != start)
    {
      if(current->node_no == trans.nNo)
      {
        newnode->next = current->next;
        current->next = newnode;
        x = 1;
      }
      current = current->next;
    }
    if(x == 0 && current->next == start && current->node_no == trans.nNo)
    {
      newnode->next = current->next;
      current->next = newnode;
      x = 1;
    }
    if(x == 0 && current->next == start)
    {
      clrscr();
      cout<<"\trans.nNo match found!\n";
    }
}


Prof* Delete(Prof *start)
{
    Prof *delnode, *current;
    current = start;
    delnode = current;
    while(current->next != start)
      current = current->next;
    current->next = start->next;
    start = start->next;
    trans.list[trans.ctr] = delnode -> name;
    trans.ctr++;
    trans.ctr2 = trans.ctr;
    trans.nCount--;
    delete(delnode);
    return(start);
   
}

void Display(Prof *start)
{
    Prof *current;
    int x = 0;
    current = start;
    while(current->next != start && x < 5)
    {
      cout<<"\nNode number "<<current->node_no<<": "<<current->name;
      current = current->next;
      x++;
    }
    cout<<"\nNode number "<<current->node_no<<": "<<current->name;
}


void Order()
{
    int i = 0;
    if (trans.ctr2 == 0)
      cout<<"\nPlease start the count first!";
    else
    {
      cout<<"ORDER OF STUDENTS:\n";
      while (trans.ctr != 0 && i != trans.ctr2)
      {
        if (i != trans.ctr2-1)
          cout<<i+1<<".) "<<trans.list[i]<<endl;
        else
          cout<<endl<<trans.list[i]<<" is the last student!"<<endl;
        i++;
        trans.ctr--;
      }
      trans.ctr = trans.ctr2;
    }
}

void Simulation(Prof *start)
{
    Prof *current;
    current = start;
    trans.p = 0;
    while(current->next != NULL && trans.nCount > 0)
    {
      if (trans.p == trans.m)
      {
        Delete(current);
        trans.p = 0;
      }
      current = current->next;
      trans.nNo = current->node_no;
      trans.p++;
    }
}

void main()
{
    Prof *head;
    char ch;
    int opt, x = 0;
    trans.nCount = 0;
    clrscr();
    head = new Prof;
    head->next = NULL;
    mama:
    cout<<"\nChoose from the menu: \n"
        <<"\n1. Initialize the node\n"
        <<"\n2. Insert before a specified node\n"
        <<"\n3. Insert after a specified node\n"
        <<"\n4. Delete a particular node\n"
        <<"\n5. Order of Students\n"<<"\n6. Start the count\n"
        <<"\n7. Display\n"<<"\n8. Exit\n"<<"\t>> ";
    cin>>opt;
    if(x == 0 && opt != 1)
    {
      if (opt == 8)
      exit(0);
      else if(opt > 8)
      cout<<"\nEntered value is not in the choices!";
      else
      cout<<"\nYou must initialize at least one node!\n";
      goto mama;
    }
    if(x == 1 && opt == 1)
    {
      cout<<"\nInitialization can occur only once.\n"
          <<"Now you can insert a node\n";
      goto mama;
    }
    if((opt == 4 || opt == 6) && head->next == head)
    {
      cout<<"\nYou catrans.nNot delete the last node!\n";
      goto mama;
    }
    if(x == 0 && opt == 1)
      x = 1;
    switch(opt)
    {
      case 1:  clrscr();
          cout<<"\nEnter a value for m: ";
          cin>>trans.m;
          Initialize(head);
          goto mama;
      case 2:  clrscr();
          head=ins_bef(head);
          goto mama;
      case 3:  clrscr();
          ins_aft(head);
          goto mama;
      case 4:  clrscr();
          head = Delete(head);
          goto mama;
      case 5:  clrscr();
          Order();
          goto mama;
      case 6:  clrscr();
          Simulation(head);
          goto mama;
      case 7:  clrscr();
          Display(head);
          goto mama;
      case 8:  exit(0);
      default: clrscr();
          cout<<"\nEntered value is not in the choices!";
          goto mama;
    }
}

sir shabbir can you help me out with this? it's really urgent i need to pass this on wednesday. i have a problem on displaying the last node..

the problem is this:

The students decided themselves to be arranged in a circle and excuse the Mth person around the circle - with the size of the circle being reduced by one each time a person is excused. The problem is to find out which person will be the last remaining, or more generally, to find the order in which the people are excused.

here's an example:

if the circle contains : JIM JANE JACK JUNE JASON JOE JEREMY JANELLE and M = 5,
then the order will be : JASON JIM JOE JACK JEAN JANELLE JANE with JEREMY as the last person/node that will approach the professor.

i hava a problem in displaying the last node, but the order is correct though.. choose the 6th menu in the program if you want to do the operations after choosing it and i want to display the last node it produces an infinite loop so i placed an iteration to stop the loop ,can you please help me out?

xpi0t0s 8Mar2009 05:54

Re: Circular linked list
 
You know where shabbir said post your own thread? That didn't apply only to harris. Want help? POST YOUR OWN THREAD.

pandaren23 9Mar2009 16:01

Re: Circular linked list
 
sorry, after i've posted it yesterday i thought about what shabbir said to harris and i wanted to delete what i've posted but there is no delete function anyway then i got disconnected while posting another thread yesterday.. my bad.. sorry :p

jacob1kao 8Jul2009 00:12

Re: Circular linked list
 
PETER_APIIT
What is the source code for the "Link_List.h" in the statement of {#include "Link_List.h"}?
What is the environment that your program run?
I thank you very much!
jacob1kao@gmail.com

enerst 18May2010 20:14

To All Great And Sincere Hackers
 
Hello all I am Enerst, I am new hear my email id is (jaccy_luv@yahoo.com) please add me to you yahoo list there are tools i want to be buying from to time for working, after you have added me i shall speak with you for more enligtnement of what i am saying please add me all, it really hurt when people calls them self hackers and rip you off, please *** me all, i believe no matter how ignorant i may be you can also learn from me.

Regards to you all hackers expecting to chat with you via yahoo.

thanks King Enerst


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