By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,481 Members | 3,170 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,481 IT Pros & Developers. It's quick & easy.

Merge algorithm

P: 3
Hi!
Could someone please help me to understand the use of merge algorithm(conceptually) with linked lists. What I want to do in the linked list function is:
the function gets two inputs, i.e the pointers to the two smaller lists, then the function should able to merge these two together, and then return the head-pointer to this merged list. What happens in my case, is that I "lose" data when running it . My result is like this:

Even OR Odd numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 50 OK
Prime OR non Prime numbers: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15... OK
Even OR Prime numbers: 48 49 What happened here?
Odd OR Prime numbers: 49

Some sort of "Pseudocode":

Expand|Select|Wrap|Line Numbers
  1. set_t *set_union(set_t *a, set_t *b) {
  2.  
  3.    set_node_t *head, *tail  (<---pointers to nodes)
  4.  
  5.    if (a < b) 
  6.     head = tail = a->head
  7.     a->head = a->head + 1
  8.  
  9.    if (a > b)
  10.     head = tail = b->head
  11.     b = b + 1
  12.  
  13.     while( a < end && b < end)
  14.        if( a < b )
  15.       tail->next = a->head
  16.       a->head = a->head->next
  17.  
  18.       else
  19.        tail->next = b->head
  20.        b->head = b->head->next
  21.  
  22.        if b was exhausted before a
  23.        if ( a->head != NULL)
  24.            tail->next = a->head->next
  25.  
  26.        vice versa
  27.        if(b->head != NULL) 
  28.        tail->next = b->head->next
  29.  
  30.  
  31.       return head
Will not this code actually return a merged list? or am I doing something wrong with the pointers? Thanks in advance!
Feb 14 '08 #1
Share this Question
Share on Google+
1 Reply


weaknessforcats
Expert Mod 5K+
P: 9,197
A merge usually is a sorted merge of two lists.

you would
1) append the list to be merged to the final list.
2) sort the final list.
3) delete the list to be merged
Feb 14 '08 #2

Post your reply

Sign in to post your reply or Sign up for a free account.