Like Tree2Likes

Get the Union Set in Single Link List

This is a discussion on Get the Union Set in Single Link List within the C Programming forums, part of the General Programming Boards category; hello everyone, i have a problem in blew program,i dont know how to get the union set without changing the ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Location
    beijing
    Posts
    23

    Get the Union Set in Single Link List

    hello everyone, i have a problem in blew program,i dont know how to get the union set without changing the head1. i want to put the union set in the head3.

    Code:
    /************************************************************************/
    /*                Get the Union Set in Single Link List                 */
    /************************************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct _tagLinkNode
    {
        int data;
        struct _tagLinkNode *next;
    }LinkNode;
    
    
    LinkNode* CreateList(LinkNode *head)
    {
        head = (LinkNode *)malloc(sizeof(LinkNode));
        if (NULL == head)
        {
            printf("malloc error\n");
            return;
        }
    	head->data = 0;
    	head->next = NULL;
    
    	return head;
    }
    
    void InputData(LinkNode *head)
    {
        LinkNode *p = NULL;
        LinkNode *pNode = NULL;
        int data = 0;
    
        p = head;
    
        scanf("%d", &data);
    
        while(-1 != data)
        {
            pNode = (LinkNode *)malloc(sizeof(LinkNode));
            if (NULL == pNode)
            {
                printf("malloc error\n");
                return;
            }
            if (-1 != data)
            {
                pNode->data = data;
                pNode->next = NULL;
                p->next = pNode;
                p = pNode;
            }
            scanf("%d", &data);
        }
    }
    
    void OutPutData(LinkNode *pHead)
    {
        LinkNode *p = pHead;
    
        if (NULL != p)
        {
            p = p->next;
        }
    
        while (NULL != p)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    LinkNode** GetUnion(LinkNode *head1, LinkNode *head2, LinkNode **head3)
    {
        LinkNode *p1 = head1;
        LinkNode *p2 = head2;
        LinkNode *p3 = NULL;
        LinkNode *p3pre = NULL;
    
        if (NULL == p1 && NULL == p2)
        {
            return;
        }
    
    	head3 = (LinkNode **)malloc(sizeof(LinkNode));
    	*head3 = (LinkNode *)malloc(sizeof(LinkNode));
    	
    	if (NULL == *head3 || NULL == head3)
    	{
    		printf("malloc error\n");
    		return NULL;
    	}
    
    	(*head3)->data = 0;
    	(*head3)->next = NULL;
    
        p1 = p1->next;
        p2 = p2->next;
        p3 = *head3 = head1;
        p3 = p3->next;
    
        while (NULL != p2)
        {
            p3pre = *head3;
            p3 = p3pre->next;
            while (NULL != p3)
            {
                if (p2->data == p3->data)
                {
                    break;
                }
                p3pre = p3pre->next;
                p3 = p3->next;
            }
            if (NULL == p3)
            {
                p3pre->next = p2;
                p3pre = p3pre->next;
            }
            p2 = p2->next;
    	}
    	return head3;
    }
    
    int main()
    {
        LinkNode *list1 = NULL;
        LinkNode *list2 = NULL;
        LinkNode **list3 = NULL;
    
        list1 = CreateList(list1);
        printf("please input single link list1(-1 end): ");
        InputData(list1);
    
    	  list2 = CreateList(list2);
        printf("please input single link list2(-1 end): ");
        InputData(list2);
    
        printf("\n\nThe Set 1: ");
        OutPutData(list1);
        printf("The Set2: ");
        OutPutData(list2);
    
        //list3 = CreateList(list3);
    
        printf("The Union Set is :");
        list3 = GetUnion(list1, list2, list3);
        OutPutData(*list3);
    
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Apr 2008
    Posts
    395
    If you can't solve a problem, divide it into smaller problems, try to first write a function to copy() a list and a function to concatenate() two existing lists without creating a new one.
    Your getunion function will simply be a composition of those two functions.
    You're talking about sets, if this last function must return a set then write a set() function that remove duplicated elements in a list.
    Compose everything and you're done.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Get rid of line 87.
    If the first thing you do with something that was passed in is to overwrite its value, then there wasn't any point in passing it in.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User
    Join Date
    Jun 2010
    Location
    beijing
    Posts
    23
    maybe i didn't express clearly, i mean, i want to use two single link list to get their union set. The "GetUnion" function has logical error but i dont know how to fix it.

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Quote Originally Posted by ampc
    i want to use two single link list to get their union set.
    Well, if by "set" you mean that there are no duplicates, I would ask: are the two linked lists sorted and without duplicates? If so, then this is just a matter of merging them, discarding duplicates as you do so. If not, you can either sort them then merge, or simply join the two linked lists, then sort and remove duplicates.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User
    Join Date
    Jun 2010
    Location
    beijing
    Posts
    23
    i mean list 1: 1 2 3 4, list 2: 3 4 5 6, then the union set is 1 2 3 4 5 6

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Quote Originally Posted by ampc
    i mean list 1: 1 2 3 4, list 2: 3 4 5 6, then the union set is 1 2 3 4 5 6
    I would rather you have answered my questions explicitly, but anyway, I assume that your linked lists are sorted and without duplicates. Hence, just merge them. This involves comparing the current nodes of each linked list. The one that is "less than" the other is appended to the new linked list. If both nodes have equal value, you append one and skip the other.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,421
    Is there a reason that list3 was declared in main() with multiple indirection?

    It seems to me that you should be declaring it as "LinkNode *list3 = NULL;" and passing &list3 into getunion() -> That way you are passing by reference and not value.

    Other than that, it should be straight forward: If element is not already in head3, add it to the end.

    <edit>
    [edit]
    Oh, and you'll want to do get rid of line 87
    [/edit]
    Last edited by Click_here; 08-17-2012 at 12:14 AM. Reason: Additional information
    iMalc likes this.

  9. #9
    Registered User
    Join Date
    Jun 2010
    Location
    beijing
    Posts
    23
    i've improved the GetUnion function.
    Code:
    LinkNode* GetUnion(LinkNode *head1, LinkNode *head2, LinkNode *head3)
    {
        LinkNode *p1 = NULL;
        LinkNode *p2 = NULL;
        LinkNode *p3 = NULL;
    
        if (NULL != head1 && NULL != head2)
        {
    		p3 = head3 = head1;
            p1 = head1->next;
    		p2 = head2->next;
    		p3 = p1;
    
    		while (NULL != p1 && NULL != p2)
    		{
    			if (p2->data != p1->data)
    			{
    				if (NULL != p1->next)
    				{
    					p1 = p1->next;
    				}
    				else
    				{
    					p1->next = p2;
    					p3 = p2;
    					p1 = head1->next;
    					p2 = p2->next;
    					p3->next = NULL;
    				}
    			}
    			else
    			{
    				p2 = p2->next;
    				if (NULL != p2 && NULL == p3->next)
    				{
    					p3->next = p2;
    				}
    			}
    		}
        }
    	return head3;
    }
    may i still improve it?

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Hmm... did you test your code with various possible input linked lists? The algorithm I had in mind goes something like this:
    Code:
    LinkNode* GetUnion(LinkNode *head1, LinkNode *head2)
    {
        LinkNode *union_head = NULL;
        LinkNode *union_tail = NULL;
    
        if ((head1 && head2 && head1->data < head2->data) || (head1 && !head2))
        {
            /* set union head and tail to head1; set head1 to its next node */
        }
        else if (head2)
        {
            /* set union head and tail to head2; set head2 to its next node */
        }
    
        while (head1 && head2)
        {
            if (head1->data < head2->data)
            {
                /* set union tail's next node to head1;
                   set union tail to its next node;
                   set head1 to its next node */
            }
            else
            {
                /* set union tail's next node to head2, etc*/
            }
        }
    
        while (head1)
        {
            /* set union tail's next node to head1, etc */
        }
    
        while (head2)
        {
            /* set union tail's next node to head2, etc */
        }
    
        return union_head;
    }
    ampc likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Quote Originally Posted by ampc View Post
    Code:
    				if (NULL != p1->next)
    You're using Yoda Conditions... Please don't.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jun 2010
    Location
    beijing
    Posts
    23
    im afraid of missing a '=' in the middle of if

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,794
    Eh, by the way, in my post #10, the latter two while loops just need to be if statements instead, i.e.,
    Code:
    if (head1)
    {
        /* set union tail's next node to head1 */
    }
    else if (head2)
    {
        /* set union tail's next node to head2 */
    }
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,307
    Quote Originally Posted by ampc View Post
    im afraid of missing a '=' in the middle of if
    That's what compiler warnings are for.

    Besides, it's only as much effort to remember to use == as it is to remember to write it backwards, so you gain nothing.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    May 2012
    Location
    Arizona, USA
    Posts
    383
    Quote Originally Posted by iMalc View Post
    You're using Yoda Conditions... Please don't.
    Before I read that page, I half-expected Yoda Conditions to look like this:
    Code:
    if (DO || !DO) {
        // there is no try
    }
    Or like this:
    Code:
    if (x == 0) {
    } else if (x != 0) {
    }
    By the way, I've recently seen the following if...else if pattern in production code at work:
    Code:
    if (0 == x) {
        // do something
    } else if (0 != x) {
        // do something else
    }
    It's a double Yoda! The Force must be strong in this code.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 05-12-2011, 03:41 AM
  2. Left justification using linked list of link list
    By hykyit in forum C Programming
    Replies: 7
    Last Post: 08-29-2005, 10:04 PM
  3. Help with Insertion sort on a single linked list
    By goron350 in forum C++ Programming
    Replies: 4
    Last Post: 07-11-2005, 08:38 PM
  4. single linked list
    By Max in forum C Programming
    Replies: 1
    Last Post: 11-21-2002, 09:27 AM
  5. Single-linked list help.
    By Nit in forum C Programming
    Replies: 3
    Last Post: 03-21-2002, 05:08 PM

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