need a crash course on union-find data structure

This is a discussion on need a crash course on union-find data structure within the C++ Programming forums, part of the General Programming Boards category; as the title suggest, im looking for any link/example tutorials on how to implement union-find data structure. im not exactly ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    494

    need a crash course on union-find data structure

    as the title suggest, im looking for any link/example tutorials on how to implement union-find data structure. im not exactly very familiar with link lists either but in order to do a union-find i have to work with link lists, so i need some info regarding that as well.

    thanks for the help.
    When no one helps you out. Call google();

  2. #2
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    here's an example of how a simple linked list works.
    Code:
    #include <iostream>
    
    int main()
    {
    	//use a prototype - it's needed for the pointer in the struct
    	struct link;
    	//define the prototype
    	struct link
    	{
    		//this is the payload
    		int data;
    		//this is the pointer to the next in the list
    		link*next;
    	};
    
    	//create a pointer to the "head" or first link in the list
    	link*head=new link;
    	//this is the pointer to the "current" link in the list
    	link*curr=head;
    	//this is the pointer to the "next" link in the list
    	link*next=0;
    
    	//fill the first link with null data
    	curr->data=-1;
    	//point the first link's pointer to nothing
    	curr->next=0;
    
    	//a simple for loop, creating 11 nodes
    	for(register short int i=0;i<12;i++)
    	{
    		//create a fresh node
    		next=new link;
    		//point the current link's pointer to that node
    		curr->next=next;
    		//move into the node
    		curr=next;
    		//fill it with data
    		curr->data=i;
    		//point it's pointer to nothing
    		curr->next=0;
    	}
    
    	//point the "current" pointer to the top of the list
    	curr=head;
    	//we're not going to need the "head" pointer anymore
    	head=0;
    
    	//this time we're going to read from the list and delete it
    	for(register short int i=0;i<12;i++)
    	{
    		//output what's in the current node (note we're printing the 
    		//first node we filled with null input)
    		std::cout<<curr->data<<std::endl;
    		//set the "next" pointer to the next node in the list
    		//if this was the last node, it'll be pointing to nothing (0)
    		next=curr->next;
    		//delete this node
    		delete curr;
    		//move into the next node.  If this was the last node, it
    		//assigns nothing (0) to the curr pointer.
    		curr=next;
    	}
    
    	//be nice.
    	return 0;
    }
    edit: I think that's right, but it's been a while since I've written a linked list, so if anybody catches any memory leaks or anything please speak up
    Last edited by major_small; 03-09-2006 at 12:15 AM.
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    494
    thanks for the help man
    When no one helps you out. Call google();

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Data structure for french-english dictionary
    By officedog in forum C Programming
    Replies: 9
    Last Post: 03-20-2009, 02:43 AM
  2. Data Structure Eror
    By prominababy in forum C Programming
    Replies: 3
    Last Post: 01-06-2009, 09:35 AM
  3. Program Crashing
    By Pressure in forum C Programming
    Replies: 3
    Last Post: 04-18-2005, 11:28 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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