Thread: Linked List Anamoly

  1. #1
    Registered User
    Join Date
    Feb 2005
    Posts
    91

    Linked List Anamoly

    Hi !

    This is a small program I wrote its creates a linked list of passengers of a single flight, everything works fine except that I noticed something very strange which I couldn't explain.

    The function "passenger* create_passenger_node(passenger *start)" has a for loop,

    "for (count_node1 = start; (strcmp(count_node1->name, node->name) <= 0) && (count_node1 != NULL); count_node2 = count_node1, count_node1 = count_node1->next); "

    In this for loop if I change the order of the condition tested the other way around i.e. " (count_node1 != NULL) && (strcmp(count_node1->name, node->name) <= 0)); the program doesn't works fine on the first name entered but if the second name entered is higher than the first name the program doesn't work and it gives me a an error, I tried this on VC++ 6.0. The code is listed as follows:



    Code:
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    struct passenger                                 //Passenger Structure includes name of the passenger and the ponter to the next
    {                                                // passenger node, structure declaration also declares start as the first node
    	char *name;                                  // and declares it NULL.
    	struct passenger *next;
    } *start = NULL;
    
    
    
    passenger* create_passenger_node(passenger *start);             //Function Declarations
    passenger* enter_passenger_info(passenger *node);
    passenger* delete_passenger_node(passenger *start);
    passenger* passenger_menu(passenger *start);
    void print(passenger *node); 
    
    
    
    
    //----------------------------- MEMBER FUNCTIONS TO MANIPULATE THE LINKED LIST --------------------------------------------
    
    
    
    
    passenger* create_passenger_node(passenger *start)  //Creates a sorted list of passengers by entering the passenger node at the
    {                                                   // sorted position, it calls the function "enter_passenger_info() to
                                                        // allocate memory to the node and assign ask the user for its information
    	if (start == NULL)                              
    	{
    		start = (passenger *) malloc(sizeof(passenger));
    		start = enter_passenger_info(start);
    		start->next = NULL;
    	}
    	else
    	{
    		passenger *count_node1, *count_node2, *node;
    		node = (passenger *) malloc(sizeof(passenger));
    		node = enter_passenger_info(node);
    		for (count_node1 = start; (strcmp(count_node1->name, node->name) <= 0) && (count_node1 != NULL); count_node2 = count_node1, count_node1 = count_node1->next);
    		if(count_node1 == start)
    		{
    			node->next = start;
    			start = node;
    		}
    		else if (count_node1 == NULL)
    		{
    			count_node2->next = node;
    			node->next = NULL;
    		}
    		else
    		{
    			count_node2->next = node;
    			node->next = count_node1;
    		}
    	}
    	return start;
    }
    
    
    passenger* enter_passenger_info(passenger *node)     // Function to enter the name of the passenger, this function is called 
    {                                                    // from the function create_passenger_node(passenger *start)by itself.   
    	printf(" Welcome to the passenger list\n");
    	printf("Please enter your name\n");
    	fflush(stdin);
    	node->name = new char [80];
    	gets(node->name);
    	return node;
    }
    
    passenger* delete_passenger_node(passenger *start)   // Function to delete the name of a passenger in the flight, function 
    {                                                    // searches for the name and deletes if it is found.
    	if(start == NULL)
    	{
    		printf("Sorry, the passenger list is empty\n");
    	}
    	else
    	{
    		char name[80];
    		printf("Please enter the name you want to delete\n");
    		gets(name);
    		passenger *count_node1, *count_node2;
    		passenger *temp;
    		for(count_node1 = start; (count_node1 != NULL) && (strcmp(count_node1->name, name) != 0); count_node2 = count_node1, count_node1 = count_node1->next);
    		if(count_node1!= NULL)
    		{
    			if (count_node1 == start)
    			{
    				temp = start;
    				start = start->next;
    				free(temp);
    			}
    			else if(count_node1->next == NULL && count_node1 != start) 
    			{
    				temp = count_node1;
    				count_node2->next = NULL;
    				free (temp);
    			}
    			else
    			{
    				temp = count_node1;
    				count_node2->next = count_node1->next;
    				free (temp);
    			}
    		}
    		else 
    		{
    
    			printf("Sorry, this name was not found in this list\n");
    		} 
    	}
    	return start;
    }
    
    passenger* passenger_menu(passenger *start)                                // Menu Function which is called from main and takes 
    {                                                                          // over the program list after that
    	int choice;
    	printf("Welcome to the passenger menu\n");
    	printf("Please enter your choice from the menu shown below\n");
    	printf("1: Add a passenger to this flight\n");
    	printf("2: Delete a passenger from this flight\n");
    	printf("3: Display the passenger list for this flight\n");
    	printf("4: Return back to the Main Menu\n");
    	scanf ("%d", &choice);
    	switch(choice)
    	{
    	case 1: 
    		{ 
    			start = create_passenger_node(start);
    		} break;
    	case 2:
    		{  
    			start = delete_passenger_node(start);
    		} break;
    	case 3:
    		{
    			print(start);
    		} break;
    	case 4:
    		{
    			start = passenger_menu(start);
    		} break;
    	}
    	start = passenger_menu(start);
    	return start;
    }
    
    
    
    void print(passenger *start)
    {
    	passenger *count;
    	for (count = start; count != NULL; count = count->next)
    	printf("%s\n", count->name);
    }
    
    
    
    //--------------------------------- MAIN FUNCTION CALLING THE MENU FUNCTION ------------------------------------------------
    
    void main()
    {
    	start = passenger_menu(start);
    }

  2. #2
    Registered User
    Join Date
    Feb 2005
    Posts
    91
    Sorry made some errors in the posting , the posted code doesn't work properly,

    1. Function "passenger* delete_passenger_node(passenger *start)" needs a fflush(stdin) to get rid of "\n" character in the stream.
    2. The input to the list doesn't work properly when the order of condition in the for loop of the function "passenger* create_passenger_node(passenger *start) " is (strcmp(count_node1->name, node->name) <= 0) && (count_node1 != NULL); but works fine if it is reverserved to " (count_node1 != NULL) && (strcmp(count_node1->name, node->name) <= 0) "

    I would be very thankful for an explanation..

  3. #3
    VA National Guard The Brain's Avatar
    Join Date
    May 2004
    Location
    Manassas, VA USA
    Posts
    903
    Be careful when using strcmp( ).. use it only to test for equality (if one cstring equals another cstring.. or if a cstring does not equal a cstring) Basically, this is the only guarantee you will get with strcmp( ).

    So in this code:
    Code:
    for (count_node1 = start; (strcmp(count_node1->name, node->name) <= 0)
    I'm thinking you are trying to return something other than a comparison of cstring equality (perhaps you are trying to return the difference in string length..??) Anywhoo.. seeing strcmp( ) being used as a for loop condition concerns me.

    Maybe you want to try something like this..??
    Code:
    while(strcmp(count_node1->name, node->name)&&(count_node1 != NULL))   //while count_node->name does not equal node->name & count_node1 does not equal NULL
    Last edited by The Brain; 02-28-2005 at 03:47 PM.
    • "Problem Solving C++, The Object of Programming" -Walter Savitch
    • "Data Structures and Other Objects using C++" -Walter Savitch
    • "Assembly Language for Intel-Based Computers" -Kip Irvine
    • "Programming Windows, 5th edition" -Charles Petzold
    • "Visual C++ MFC Programming by Example" -John E. Swanke
    • "Network Programming Windows" -Jones/Ohlund
    • "Sams Teach Yourself Game Programming in 24 Hours" -Michael Morrison
    • "Mathmatics for 3D Game Programming & Computer Graphics" -Eric Lengyel

  4. #4
    Registered User
    Join Date
    Feb 2005
    Posts
    91
    Hey,

    The strcmp function is to find the node where the new passenger name should be entered, the for loop finds the exact postion for the name alphabeticaly in the linked list before its entered so the list remains sorted at all times,

    The strcmp returns a -ve value the for loop exits since it has found a name alphabetically greater than the one to be just entered and the new name is entered just before that name.

    My problem was that in the nested condition, when the order of the nested condtion in the for loop is:
    (strcmp(count_node1->name, node->name)&&(count_node1 != NULL)) and lets say I enter the name "Sonny" first and then enter "Uma" next it gives me an error since Uma is alphabetically greater than Sonny. However when i switched the nested condition in reverse order to :
    ((count_node1 != NULL)&&strcmp(count_node1->name, node->name)) the above name entries worked fine and the program also works fine. I wasn't able to understand this ???????

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM