xor linked list

This is a discussion on xor linked list within the C Programming forums, part of the General Programming Boards category; I have to develop a linked list similar to one I found asked about on this site: http://cboard.cprogramming.com/c-pro...nked-list.html Mine has ...

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    36

    xor linked list

    I have to develop a linked list similar to one I found asked about on this site:

    xor linked list

    Mine has a twist though.

    The function signatures include pointers to pointers for the head and tail, along with the integer number.

    Here is my source.

    Code:
                                                                         
                                                                         
                                                                         
                                                 
    #include <stdio.h>
    #include "rndm.h"
    #include <stdlib.h>
    
    #define init_seed
    #define set_range
    #define SIZERANGE 100
    
    
    typedef struct node
    {
    	int data;
    	unsigned long link;
    }node ;
    
    node *head, *tail;
    
    
    void insert(node **head,node **tail, int n)
    {
    	node *prev, *cur, *next, *tmp;
    	node *newnode = malloc(sizeof(node));
    	head = &cur;
    	prev = NULL;	
    
    	while(cur->data < n)
    		{
                    next = (node *)(cur->link ^ (unsigned long)prev);
                    prev = cur;
                    cur = next;
    	}
    	
    	newnode->link ^= (unsigned long) prev ^(unsigned long) cur;
    	prev->link ^= (unsigned long) cur ^ (unsigned long) newnode;
    	cur->link ^= (unsigned long) prev ^ (unsigned long) newnode;
    
    }//end insert
    
    void delete(node **head, node **tail, int n)
    {
    
    }
    
    void list(node *head)
    {
    
    }
    
    main ()
    {
    	
    	head=NULL;
    	tail=head;
    	int startRange, endRange, n,i;
    	long inputSeed;
    	printf("Seed: ");
    	scanf("%l\n", &inputSeed);
    	init_seed(inputSeed);
    
    	printf("Range: ");
    	scanf("%d %d\n", &startRange, &endRange);
    	set_range(startRange, endRange);
    
    	for(i=0; i <= SIZERANGE; i++)
    	{
    		insert(&head, &tail, rndm());	
    	}
    
    }
    I am only working on the insert method at this time. I am kind of just code pushing for the declarations in that function, no really knowledge on what I should be doing. I am very confused with the **head and **tail variables.

    Can someone kind of give me a push in the right direction concerning how this function should be operating and the variable declarations?

    Thanks!

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    It should insert a node into your list, with the given integer as the value. Presumably you are keeping your list sorted? If so, then you need to walk the list to find where it belongs and insert it there.

  3. #3
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    Quote Originally Posted by tabstop View Post
    It should insert a node into your list, with the given integer as the value. Presumably you are keeping your list sorted? If so, then you need to walk the list to find where it belongs and insert it there.
    I'm just struggling on how to handle the pointers.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by ollie88r View Post
    I'm just struggling on how to handle the pointers.
    You say that as though it means something. They're the head and tail of your list, passed in by pointer so that you can change them should you need to (if the new item ends up in the first/last position).

  5. #5
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    Quote Originally Posted by tabstop View Post
    You say that as though it means something. They're the head and tail of your list, passed in by pointer so that you can change them should you need to (if the new item ends up in the first/last position).
    Well for instance

    head is **head. and i need to set that to cur, which is also a pointer

    I am having trouble figuring out how to pass that variable correctly.

    I just tried *cur = *head inside my insert method, and the NULL passed correctly to cur.

    I am just confused because head has 2 dereferences and I dont know how to handle that for assignments to other points. I am often getting segmentation errors

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by ollie88r View Post
    Well for instance

    head is **head. and i need to set that to cur, which is also a pointer

    I am having trouble figuring out how to pass that variable correctly.

    I just tried *cur = *head inside my insert method, and the NULL passed correctly to cur.

    I am just confused because head has 2 dereferences and I dont know how to handle that for assignments to other points. I am often getting segmentation errors
    *cur = *head looks really wrong here. head is a pointer to a pointer to the head of the list; therefore *head is a pointer to the first element of the list; therefore **head is the first element of the list.

  7. #7
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    Quote Originally Posted by tabstop View Post
    *cur = *head looks really wrong here. head is a pointer to a pointer to the head of the list; therefore *head is a pointer to the first element of the list; therefore **head is the first element of the list.
    So I want cur to be pointing to the first node in the list, which is **head.

    so node *cur = **head

    ?

    that gives me an incompatible types error

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    If you want cur to point at the first node of the list, then you do exactly that
    Code:
    cur = *head;
    by setting the value of cur to be the thing that points at the first node of the list.

  9. #9
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    Quote Originally Posted by tabstop View Post
    If you want cur to point at the first node of the list, then you do exactly that
    Code:
    cur = *head;
    by setting the value of cur to be the thing that points at the first node of the list.
    Ok thanks tabstop.

    So say for testing purposes. Since in the main i set

    head = NULL;

    if I want

    head = 2;

    I am not sure how to change this with pointers from the insert method

    I tried *head = 2; and **head=2;

    EDIT: I guess I am kinda asking some pointless questions to my problem

    I am not sure what to assign head to, if I even need a cur variable considering I am passing a pointer to head, and how to adapt the formulas my teacher gave me to move up and down an xor list along with inserting a node (below)

    Code:
    tmp->link = (unsgne long) prv ^ (unsigned long) cur;
    prv->link ^= (unsigned long) cur ^ (unsigned long) tmp;
    cur->link ^= (unsigned long) prv ^ (unsigned long) tmp;
    All in all im just really confused about the whole thing to be honest
    Last edited by ollie88r; 10-10-2009 at 04:24 PM.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You cannot possibly want head = 2. 2 is not a valid pointer. (Well, I mean I suppose it is; but you don't own the memory where it points.)

  11. #11
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    ok.



    so in my insert method i now have

    Code:
    node *newnode, *cur, *prev = NULL, *next = NULL, *tmp = NULL;
    newnode = malloc(sizeof(node));
    newnode->data = n;
    so this at least gets me as far as putting a new randomly generated number into newnode, 100 times. i need to compare the data in head. i dont think i put any data in head? i declared a *head node globally, do i assign head->data to NULL in the main? currently it is just head = null. Then place the new node correctly in the list....

    And i am not even sure that logic is right...
    Last edited by ollie88r; 10-10-2009 at 04:39 PM.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You shouldn't, ever, put data directly in head. That's not what it is for. It is to point at the (already existing) element of the list that is in front. When, in the course of inserting events, you find yourself inserting an element into first position, you will then need to change head to point at that new element.

  13. #13
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    ok so after your advice and some fidgetting, i still havent managed to figure out what to do with the head. not sure if i am any closer though

    Code:
    void insert(node **head,node **tail, int n)
    {
            node *newnode;
            newnode = malloc(sizeof(node));
            newnode->data = n;
    
            while(newnode->data < cur->data)
            {
                    next = (node *)(cur->link ^ (unsigned long)prev);
                    prev = cur;
                    cur = next;
            }
    
            tmp->link = (unsigned long) prev ^ (unsigned long) cur;
            prev->link ^= (unsigned long) cur ^ (unsigned long) tmp;
            cur->link ^= (unsigned long) prev ^ (unsigned long) tmp;
    
    
    
    
    }//end insert
    in my main i added

    Code:
    cur = malloc(sizeof(node));
            cur->data = 0;
    so that i had a base case to build the organized list off of.

    I get segmentation errors when adding the

    Code:
    tmp->link = (unsigned long) prev ^ (unsigned long) cur;
            prev->link ^= (unsigned long) cur ^ (unsigned long) tmp;
            cur->link ^= (unsigned long) prev ^ (unsigned long) tmp;
    part. im assuming this has something to do with initializing but i am not sure

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So that's pretty horrendous, as insert functions go. You must be prepared for (1) an empty list (2) the new element to go at the front of the list (3) the new element to go at the end of the list.

  15. #15
    Registered User
    Join Date
    Sep 2009
    Posts
    36
    Quote Originally Posted by tabstop View Post
    So that's pretty horrendous, as insert functions go. You must be prepared for (1) an empty list (2) the new element to go at the front of the list (3) the new element to go at the end of the list.
    Well I know its horrendous :/

    That's why I'm here...don't really know what im doing.

    And my insert is no where near done I know that. Just kinda posting it to see if I am heading in the right direction.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. c program that accepts and executes commands?
    By Cimposter in forum C Programming
    Replies: 3
    Last Post: 09-30-2009, 02:58 PM
  2. instantiated from here: errors...
    By advocation in forum C++ Programming
    Replies: 5
    Last Post: 03-27-2005, 08:01 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. List class
    By SilasP in forum C++ Programming
    Replies: 0
    Last Post: 02-10-2002, 04:20 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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