473,320 Members | 1,719 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Merge algorithm

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
1 2606
weaknessforcats
9,208 Expert Mod 8TB
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

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

Similar topics

9
by: Hunter Hou | last post by:
Folks, I am just curious why standard library doesn't provide a "merge" operation without sorting, because sometimes I don't require sorting, just merge. I looked at list.merge() and merge()...
8
by: ilikesluts | last post by:
Hi Group, I'm new to XML, here is my question: Would it be possible to write an algorithm that takes in two XML documents with the only condition being that they have the same root element? ...
9
by: rkk | last post by:
Hi, I have written a generic mergesort program which is as below: --------------------------------------------------------- mergesort.h ----------------------- void MergeSort(void...
7
by: Zeba | last post by:
Hi, I have to write program in C# to merge sort a linked list (doubly linked). Is it true that the best way to do it is copy it into an array, sort it and then convert back ? I'm new to C#,...
0
by: phanipep | last post by:
write recursive algorithm for 2 way merge sort
0
by: subramanian100in | last post by:
consider : template<class InIt1, class InIt2, class OutIt> OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt dest); Can the destination container already contain some...
3
by: subramanian100in | last post by:
Consider the following program: #include <cstdlib> #include <iostream> #include <set> #include <map> #include <algorithm> #include <iterator> #include <utility>
9
by: Tem | last post by:
List<inta = new List<int>(); a.Add(1); a.Add(2); a.Add(3); List<intb = new List<int>(); b.Add(3); b.Add(4); b.Add(5);
2
by: jimgym1989 | last post by:
can someone show me how to implement a merge sort algorithm, i've been trying to search the net and all i found are pseudocodes. I already tried to translate the pseudocodes to java program but I...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.