Circular Linked List

Discussion in 'C' started by shabbir, Aug 27, 2006.

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

    Code:
    #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);
    }
     
  2. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    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.
     
    Last edited by a moderator: Jan 31, 2008
  3. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    Looks well commented but I have not run it.
     
  4. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Any comment about hte program is more than welcome.

    Thanks.
     
  5. lead.smart34

    lead.smart34 New Member

    Joined:
    Feb 14, 2008
    Messages:
    77
    Likes Received:
    0
    Trophy Points:
    0
    i tried it works
     
  6. crazytolearn57

    crazytolearn57 New Member

    Joined:
    Feb 14, 2008
    Messages:
    48
    Likes Received:
    0
    Trophy Points:
    0
    shabbir's is better
     
  7. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    yes.......shabbir's is better....
     
  8. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Is there any post or article on circular array????
     
  9. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    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];
    }
    
     
  10. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Array is random access.

    How can it be circular array A?
     
  11. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Array is random access.

    How can it be circular array A?
     
  12. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    Random access and circularity are not mutually exclusive.
     
  13. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    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???
     
  14. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,009
    Likes Received:
    203
    Trophy Points:
    63
    Occupation:
    Senior Support Engineer
    Location:
    England
    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.)
     
  15. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    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...
     
  16. skp819

    skp819 New Member

    Joined:
    Dec 8, 2008
    Messages:
    89
    Likes Received:
    3
    Trophy Points:
    0
    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.
     
  17. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    What kind of error ?
     
  18. harris

    harris New Member

    Joined:
    Mar 3, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    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..
     
  19. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,375
    Likes Received:
    388
    Trophy Points:
    83
    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.
     
  20. harris

    harris New Member

    Joined:
    Mar 3, 2009
    Messages:
    11
    Likes Received:
    0
    Trophy Points:
    0
    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..
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice