Thread: Merge two lists!

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    67

    Merge two lists!

    Write a program that merges the numbers in two files and writes all the numbers into a third file.Each input list contains a list of numbers of type int in sorted order from the smallest to the largest.After running this program,then the new list should contain the all the numbers in the two input files and in sorted from smallest to largest.We must use a function which contains two input-file streams and one output-file stream.

    I ask my professor to give me some hint,he told me like this:

    a1 b1
    a2 b2
    . .
    . .
    . .

    since a1<a2<......,b1<b2<.....,so we just compare a1 and b1,if a1<b1 then write a1 to the third list,then compare a2 and b1.

    It sounds that it is a very easy problem,but how to apply this?
    I think we can do this:

    input1>>num1;
    input2>>num2;
    if(num1<num2)
    output<<num1;
    else
    output<<num2;

    but how to do compare a2 with b1(or b2 with a1)?we use two arrays to store these numbers?

    At first,I think we can do this:first input all the two lists into the third file,so we have a new
    total list which contains the whole numbers,then sort only this list,of course it will be a bad
    program since it will cost more time to finish the task.

    So how to do?

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Lund, Sweden
    Posts
    18
    Start by taking one value from each file (say x comes from A and y comes from B).

    P: Now compare x and y, record the smallest to a file, remember the other one. If x was the smallest, read a new value from A into x, otherwise read a new from B into y. Goto P.

    Of course, once there's nothing left in one file, just copy the remainder of the other one and you are done.

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    67
    I understand your meaning,and also I had thought of those,but it is much easier to talk than to do.we go through your method:
    Start by taking one value from each file (say x comes from A and y comes from B).

    P: Now compare x and y, record the smallest to a file, remember the other one. If x was the smallest, read a new value from A into x, otherwise read a new from B into y. Goto P.

    Of course, once there's nothing left in one file, just copy the remainder of the other one and you are done.
    how do you know where to stop?there maybe different numbers in the two lists and you don't know the size.



    like some c ode like this:

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You missed adding the code, I think. But if the lists are of different size doesn't matter - you are going to reach one end or the other. If there's anything left in one file only, then that must be appended to the output file - because it's obviously larger than the values in the other file.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    Lund, Sweden
    Posts
    18
    Quote Originally Posted by tx1988 View Post
    how do you know where to stop?there maybe different numbers in the two lists and you don't know the size.



    like some c ode like this:
    That is simple to tell, since there's a function called eof() in ifstream, which returns true if you're at the end of file and false otherwise.

    And yes, I could easily post the code for this, but I doubt your professor would appreciate it. At least try implementing the algorithm I suggested, if you don't get it to work then we can look at it again and point out what's wrong.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge Module Problems
    By mercury529 in forum Windows Programming
    Replies: 0
    Last Post: 11-29-2006, 03:30 PM
  2. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  3. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM