Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 3 of 3
  1. #1
    New to the CF scene
    Join Date
    Mar 2007
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    C -Linked List problem

    Hello everyone,

    i am trying to program an XOR Linked List in C. I have most of it done, but there seems to be a problem in my delete function. I keep getting segmentation faults when I go into the delete function and I cannot seem to figure out why. Could someone take a look at it and see if they can see something that I cannot? I am fairly new to C, so my apologies for any obvious mistakes I may have made. Here is my code below. Any help is much appreciated.

    I commented out the calls to my delete function in main and with them commented out my program runs successfully.

    I know that using XOR lists is not very common, but I am set on getting this to work.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "rndm.h"
    
    struct node {
           int data;
           unsigned long link;
    };
    struct node *head, *tail, *currN, *prevN, *nextN, *tmp;
    
    void insert(struct node **headN, struct node **tailN, int n);
    void delete(struct node **headN, struct node **tailN, int n);
    void list(struct node *head, int i);
    void nextNode();
    void previNode();
    
    //============================================================
    
    void insert(struct node **headN, struct node **tailN, int numN) {
         struct node *newnode = malloc(sizeof(struct node));
         newnode->link =(unsigned long)(*headN);
         newnode->data = numN;
    	 
         //if empty list
         if (*headN == NULL){
              *headN = newnode;
              currN = *headN;
              (*headN)->link = 0;
         } else if ((*headN)->link == (unsigned long)NULL){
               if (numN <= (*headN)->data){
                    newnode->link = (unsigned long) *headN;
                    (*headN)->link = (unsigned long) newnode;
                    tail = *headN;
                    *headN = newnode;
                    nextN = tail;
                    prevN = NULL;
                } else {
                    newnode->link = (unsigned long) *headN;
                    (*headN)->link = (unsigned long) newnode;
                    tail = newnode;
                    nextN = NULL;
                    currN = tail;
                    prevN = *headN;
                  }
         } else { 
              currN = *headN;
              prevN = NULL;
              nextN = (struct node *)(currN->link ^ (unsigned long) prevN);
              if (numN > tail->data){
                   while (currN!=tail){
                         nextNode();
                   }
                   newnode->link = (unsigned long) currN;
                   currN->link = (unsigned long) newnode ^ (unsigned long) prevN;
                   tail = newnode;
              } else if (numN < head->data){
                   currN->link = (unsigned long) newnode ^ (unsigned long) nextN;
                   newnode->link = (unsigned long) currN;
                   *headN = newnode;
                   nextN = currN;
                   currN = *headN;
              } else {
                   while (numN > currN->data){
                         nextNode();
                   }
                   newnode->link = (unsigned long) prevN ^ (unsigned long) currN;
                   prevN->link ^= (unsigned long) currN ^ (unsigned long) newnode;
                   currN->link ^= (unsigned long) prevN ^ (unsigned long) newnode;
              }
         }
    }  
    
    void delete(struct node **headN, struct node **tailN, int numD){
         
    	 struct node *prevN = NULL;
         struct node *currN = *headN;
    	 
    	 while ( currN != NULL )
      	{
    		struct node *nextN = (struct node *) (currN->link ^ (unsigned long)prevN);	
    		//if the number is found, then delete it
    		if (currN->data == numD)
    		{
    		  if(prevN) 
                 	  {
                         prevN->link ^= (unsigned long)currN ^ (unsigned long)nextN;
               	  }
                	  else 
                         *headN = nextN;
    	    	  if(nextN) 
                	  {
                         nextN->link ^= (unsigned long)currN ^ (unsigned long)prevN;
                	  }	
                	  else 
                         *tailN = prevN;
    		  free(currN);
    		  break;
    		}
        		prevN = currN;
    		currN = nextN;
    	}
    }
    
    void list(struct node *head, int i){
         
    	if(i == 0){ 
    	 currN = head;
         prevN = NULL;
         int count = 1;
         nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
         printf("Linked List in ascending order\n");
         while(currN!=NULL){
              if(count <= 10){
                   printf("%-5d", currN->data);
                   nextNode();
                   count++;
              } 
              else{
                   printf("\n");
                   count = 1;
              }
         }
    	}
         printf("\n\n"); 
    
    	if(i == 1){ 
         printf("Linked List in descending order\n");
         currN = tail;
         int count2 = 1;
         prevN = (struct node *) currN->link;
         nextN = NULL;
         while (currN!=NULL){
             if(count2 <= 10){
                  printf("%-5d", currN->data);
                  previNode();
                  count2++;
              
              }else{
                  printf("\n");
                  count2 = 1;
              }
         } 
        } 	
        printf("\n");         
    }
    
    void nextNode(){
        nextN = (struct node *) (currN->link ^ (unsigned long) prevN);
        prevN = currN;
        currN = nextN;
    }
    
    void previNode(){
        prevN = (struct node *) (currN->link ^ (unsigned long) nextN);
        nextN = currN;
        currN = prevN;		
    }
    
    int main(){
        
        int i, num;
        float seed;
        head = NULL; tail = NULL; currN = NULL; prevN = NULL; nextN = NULL;
        
        init_seed(1234567);
        set_range(1,9999);
        //inserting data into the linked list
        for ( i=0; i<100; ++i){
            num = rndm();
            insert( &head, &tail, num );
        }
    	
        list((struct node*)head, 0);
    	//delete((struct node**)head, (struct node**)tail, 45);
    	//delete((struct node**)head, (struct node**)tail, 4040);
    	//delete((struct node**)head, (struct node**)tail, 9769);
        list((struct node*)head, 1);
        
        
        return 0;
    }
    Edit:

    Also, could anyone tell me why I get these errors when I change the parameters in the function headers from **headN to **head and **tailN to **tail and replace all occurrences of headN and tailN with head and tail?
    These are the errors I get:

    Code:
    main.c: In function `insert':
    main.c:33: warning: assignment from incompatible pointer type
    main.c:35: warning: assignment from incompatible pointer type
    main.c:40: warning: assignment from incompatible pointer type
    main.c:42: warning: assignment from incompatible pointer type
    main.c:49: error: request for member `data' in something not a structure or union
    main.c:50: warning: comparison of distinct pointer types lacks a cast
    main.c:55: warning: assignment from incompatible pointer type
    main.c:56: error: request for member `data' in something not a structure or union
    main.c:181:2: warning: no newline at end of file
    Last edited by aophyz; 03-14-2010 at 07:19 AM.

  • #2
    New to the CF scene
    Join Date
    Sep 2011
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Oh, I'm in the same situation, even the errors are the same
    It's a pitty no one answered

  • #3
    Supreme Overlord Spookster's Avatar
    Join Date
    May 2002
    Location
    Marion, IA USA
    Posts
    6,280
    Thanks
    4
    Thanked 83 Times in 82 Posts
    For problems like this simply running your code in a debugger should reveal what is going wrong.
    Spookster
    CodingForums Supreme Overlord
    All Hail Spookster


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •