circular linked list question..

This is a discussion on circular linked list question.. within the C Programming forums, part of the General Programming Boards category; i need to go from the head of the linked list and check if i got to the same place ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    circular linked list question..

    i need to go from the head of the linked list
    and check if i got to the same place
    after making circle.
    the problem is if tell ptr=head;
    and then the while condition checks if i didnt got to this place.
    so it doesnt even enters this loop.

    how to solve it

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    typedef struct node node;
    struct node{
    	int value;
    	struct node * next;
    };
    
    void main()
    {
    node* head;
    head=(node*)malloc(sizeof(node));
    	head->next=(node*)malloc(sizeof(node));
    	head->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next->next->next=(node*)malloc(sizeof(node));
        head->next->next->next->next->next->next=head;
    	head->value=2;
    	head->next->value=4;
    	head->next->next->value=1;
    	head->next->next->next->value=5;
    	head->next->next->next->next->value=3;
    	head->next->next->next->next->next->value=8;
    
    }
    
     int checkround(node *head)
     {
    	 int temp=head->value,n_temp;
    	 node * ptr;
    	 node * h_ptr
    
    
    	   ptr=head;//i need this in order to start going threw the list from this place
          while(ptr!=head)///have problem here
          {
              for(temp=n_temp;tem>0;temp=temp-1)
              {
    	           ptr=ptr->next;
              }
              n_temp=ptr->value;
              ptr->value=-1;
          }
    
     }

  2. #2
    Making mistakes
    Join Date
    Dec 2008
    Posts
    476
    Code:
    while(ptr!=head)///have problem here {
        for(temp=n_temp;tem>0;temp=temp-1) {
    	ptr=ptr->next;
        }
    
        n_temp=ptr->value;
        ptr->value=-1;
    }
    should really be a do-while loop. Or do one pass and then add the loop.

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i cant understand why it doesnt skip 4 nodes
    in the end of the first "for " loop it should point to
    node 8
    but it points to point 3
    why??

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    typedef struct node node;
    struct node{
    	int value;
    	struct node * next;
    };
    int checkround(node *head);
    void main()
    {
    	int g;
    node* head;
    head=(node*)malloc(sizeof(node));
    	head->next=(node*)malloc(sizeof(node));
    	head->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next->next->next=(node*)malloc(sizeof(node));
        head->next->next->next->next->next->next=head;
    	head->value=2;
    	head->next->value=4;
    	head->next->next->value=1;
    	head->next->next->next->value=5;
    	head->next->next->next->next->value=3;
    	head->next->next->next->next->next->value=8;
    g=checkround(head->next);
    }
    
     int checkround(node *head)
     {
    	 int temp,n_temp;
    	 node * ptr;
     
    
    
    	   ptr=head;
          do 
          {
              for(temp=ptr->value;temp>0;temp=temp-1)   \\here is the problem
              {
    	           ptr=ptr->next;
              }
              n_temp=ptr->value;
    		  if (n_temp==-1) return 0;
              ptr->value=-1;
          }while(ptr!=head);
    
            ptr=head;
    		do
    		{
               if (ptr->value!=-1)
    		   {
                return 1;
    		   }
    	           ptr=ptr->next;
               
    		}while(ptr!=head);
    	  return 2;
    
     }
    i have written the for loop
    so it will count from 4 to 1
    and in each count it will go next on the list

    so why it stops one step before the target
    Last edited by transgalactic2; 06-20-2009 at 04:57 AM.

  4. #4
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,708
    Code:
     void main()
    Did you forget that main returns an int?

    Code:
    head=(node*)malloc(sizeof(node));
    FYI, the cast is unnecessary.

    Code:
    int checkround(node *head);
    The name "checkaround" is misleading, since it actually alters the data structure. Try to use more meaningful names.

    Code:
    head=(node*)malloc(sizeof(node));
    	head->next=(node*)malloc(sizeof(node));
    	head->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next->next=(node*)malloc(sizeof(node));
    	head->next->next->next->next->next=(node*)malloc(sizeof(node));
        head->next->next->next->next->next->next=head;
    	head->value=2;
    	head->next->value=4;
    	head->next->next->value=1;
    	head->next->next->next->value=5;
    	head->next->next->next->next->value=3;
    	head->next->next->next->next->next->value=8;
    Think modular. A simple function would make this so much easier. Consider something along these lines:

    Code:
    node * add_node(node **head, int value)
    {
    	node* ptr = (node*)malloc(sizeof(node));
    	if(ptr == NULL)
    		return NULL;
    	if(*head == NULL)
    		*head = ptr;	
    	ptr->next = *head;
    	ptr->value = value;	
    	node *current = *head;
    	while(current->next != *head)
    		current = current->next;
    	current->next = ptr;
    	return ptr;	
    }
    Then, in main, you can simply do:

    Code:
    int main( void )
    {
    	node *head = NULL;
    	add_node(&head, 2);
    	add_node(&head, 4);
    	add_node(&head, 1);
    	add_node(&head, 5);
    	add_node(&head, 3);
    	add_node(&head, 8);
    	return 0;
    }
    >> so why it stops one step before the target

    Print the values of all of the variables involved as you go around the data structure.

    Code:
    void print_list(node *head)
    {
    	if(head == NULL)
    		return;
    	node *current = head;
    	do
    	{
    		printf("%x: %d\n", current, current->value);
    		current = current->next;
    	}
    	while(current != head);		
    }
    
    int checkround(node *head)
     {
    	 int temp,n_temp;
    	 node * ptr;
    	   ptr=head;
          do 
          {
    	  printf("Begin Loop: ptr: %x, ptr->value: %d\n", ptr, ptr->value);      
              for(temp=ptr->value;temp>0;temp=temp-1)   //here is the problem
              {
    		  printf("ptr: %x, ptr->value: %d, temp: %d\n", ptr, ptr->value, temp);
    	           ptr=ptr->next;
              }
              n_temp=ptr->value;
    		  if (n_temp==-1) return 0;
              ptr->value=-1;
          }while(ptr!=head);
    
            ptr=head;
    		do
    		{
               if (ptr->value!=-1)
    		   {
                return 1;
    		   }
    	           ptr=ptr->next;
               
    		}while(ptr!=head);
    	  return 2;
    
     }
    
    int main( void )
    {
    	node *head = NULL;
    	add_node(&head, 2);
    	add_node(&head, 4);
    	add_node(&head, 1);
    	add_node(&head, 5);
    	add_node(&head, 3);
    	add_node(&head, 8);
    	puts("List:");
    	print_list(head);
    	puts("Check:");
    	checkround(head);
    	return 0;
    }
    Finally, I would recommend indenting your code consistently, and giving your variables more "room to breath" (eg: instead of "a==-1" use "a == -1").
    Code:
    #include <cmath>
    #include <complex>
    bool euler_flip(bool value)
    {
        return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) 
            * std::complex<float>(std::atan(1.0)
            *(1 << (value + 2)))
        ).real() < 0;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  4. linked list question
    By yeahdixon in forum C++ Programming
    Replies: 2
    Last Post: 03-28-2002, 09:16 AM
  5. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21