Thread: [Dev-C++] merging two sorted lists using file streams...
Open Source C & C++ IDE for Windows
Brought to you by:
claplace
Menu
▾
▴
dev-cpp-users
|
From: chromatonus 7. <chr...@ho...> - 2002-06-08 00:48:52
|
Hi, here is my program that is suppose to read one piece of data from 2
different sorted lists each,
like these two text files:
File A:
1
2
4
8
16
File B:
0
1
1
2
3
5
8
output should be
File C:
0 1 1 1 2 2 3 4 5 8 8 16
Would anyone give a sample program that performs this function, using only
the "basic" file stream operations as in my program below? Thank you very
much
#include "apstring.h"
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
int main()
{
ifstream a; ifstream b;
ofstream c;
a.open("A.dat");
b.open("B.dat");
int ark, bum, j, k, temp;
a >> ark;
a.ignore(80,'\n');
j = ark;
b >> bum;
b.ignore(80,'\n');
k = bum;
if( ark < bum )
{
c << ark << endl;
a >> ark;
a.ignore(80,'\n');
temp = ark;
}
else
{
c << bum << endl;
b >> bum;
b.ignore(80,'\n');
temp = bum;
}
if(j<k)
{
while( b>>bum && bum<temp )
{
b >> bum;
b.ignore(80,'\n');
c << bum << endl;
b >> bum;
b.ignore(80,'\n');
}
c << temp << endl;
temp = bum;
}
else
{
while( a>>ark && ark<temp )
{
a >> ark;
a.ignore(80,'\n');
c << ark << endl;
a >> ark;
a.ignore(80,'\n');
}
c << temp << endl;
temp = ark;
}
while( c << temp )
{
cout << temp << endl;
}
system("PAUSE");
a.close();
b.close();
c.close();
return 0;
}
_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com
|
|
From: Jason H. <jas...@nt...> - 2002-06-08 03:22:32
|
Quick tip:
get 'a'
get 'b'
repeat
if 'a' is greater than 'b'
output 'b'
get 'b'
else
output 'a'
get 'a'
until one of the streams is empty
This is a simplistic algorithm for you to follow, but it demonstrates the way two sorted streams can
be "merged" (lookup that word in an algorithms book). There is still one more thing for you to add:
When one of the streams runs out then you need to continue feeding from the other and outputing it
until it is also empty. And don't forget that the streams may be empty to start with! (tip: use a
while loop)
It would be wise for you to figure the rest out yourself, but one more tip: If you are repeating the
same steps several times in different places in a program, then it's a good idea to make those steps
into a function (i.e. getFromStream(); outputToStream();). Meaningful variable names also help
(instream_a, instream_b, outstream)
Jason.
PS: Not as quick a tip as I had planned, but at least I didn't hand everything to you on a plate.
----- Original Message -----
From: "chromatonus 712" <chr...@ho...>
To: <dev...@li...>
Sent: Saturday, June 08, 2002 1:48 AM
Subject: [Dev-C++] merging two sorted lists using file streams...
Hi, here is my program that is suppose to read one piece of data from 2
different sorted lists each,
like these two text files:
File A:
1
2
4
8
16
File B:
0
1
1
2
3
5
8
output should be
File C:
0 1 1 1 2 2 3 4 5 8 8 16
Would anyone give a sample program that performs this function, using only
the "basic" file stream operations as in my program below? Thank you very
much
#include "apstring.h"
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
int main()
{
ifstream a; ifstream b;
ofstream c;
a.open("A.dat");
b.open("B.dat");
int ark, bum, j, k, temp;
a >> ark;
a.ignore(80,'\n');
j = ark;
b >> bum;
b.ignore(80,'\n');
k = bum;
if( ark < bum )
{
c << ark << endl;
a >> ark;
a.ignore(80,'\n');
temp = ark;
}
else
{
c << bum << endl;
b >> bum;
b.ignore(80,'\n');
temp = bum;
}
if(j<k)
{
while( b>>bum && bum<temp )
{
b >> bum;
b.ignore(80,'\n');
c << bum << endl;
b >> bum;
b.ignore(80,'\n');
}
c << temp << endl;
temp = bum;
}
else
{
while( a>>ark && ark<temp )
{
a >> ark;
a.ignore(80,'\n');
c << ark << endl;
a >> ark;
a.ignore(80,'\n');
}
c << temp << endl;
temp = ark;
}
while( c << temp )
{
cout << temp << endl;
}
system("PAUSE");
a.close();
b.close();
c.close();
return 0;
}
_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com
_______________________________________________________________
Don't miss the 2002 Sprint PCS Application Developer's Conference
August 25-28 in Las Vegas - http://devcon.sprintpcs.com/adp/index.cfm?source=osdntextlink
_______________________________________________
Dev-cpp-users mailing list
Dev...@li...
https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
|
|
From: Jason H. <jas...@nt...> - 2002-06-08 22:31:02
|
Quick tip:
get 'a'
get 'b'
repeat
if 'a' is greater than 'b'
output 'b'
get 'b'
else
output 'a'
get 'a'
until one of the streams is empty
This is a simplistic algorithm for you to follow, but it demonstrates the way two sorted streams can
be "merged" (lookup that word in an algorithms book). There is still one more thing for you to add:
When one of the streams runs out then you need to continue feeding from the other and outputing it
until it is also empty. And don't forget that the streams may be empty to start with! (tip: use a
while loop)
It would be wise for you to figure the rest out yourself, but one more tip: If you are repeating the
same steps several times in different places in a program, then it's a good idea to make those steps
into a function (i.e. getFromStream(); outputToStream();). Meaningful variable names also help
(instream_a, instream_b, outstream)
Jason.
PS: Not as quick a tip as I had planned, but at least I didn't hand everything to you on a plate.
PPS: This is a repost, my first one didn't seem to get through.
----- Original Message -----
From: "chromatonus 712" <chr...@ho...>
To: <dev...@li...>
Sent: Saturday, June 08, 2002 1:48 AM
Subject: [Dev-C++] merging two sorted lists using file streams...
Hi, here is my program that is suppose to read one piece of data from 2
different sorted lists each,
like these two text files:
File A:
1
2
4
8
16
File B:
0
1
1
2
3
5
8
output should be
File C:
0 1 1 1 2 2 3 4 5 8 8 16
Would anyone give a sample program that performs this function, using only
the "basic" file stream operations as in my program below? Thank you very
much
#include "apstring.h"
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
int main()
{
ifstream a; ifstream b;
ofstream c;
a.open("A.dat");
b.open("B.dat");
int ark, bum, j, k, temp;
a >> ark;
a.ignore(80,'\n');
j = ark;
b >> bum;
b.ignore(80,'\n');
k = bum;
if( ark < bum )
{
c << ark << endl;
a >> ark;
a.ignore(80,'\n');
temp = ark;
}
else
{
c << bum << endl;
b >> bum;
b.ignore(80,'\n');
temp = bum;
}
if(j<k)
{
while( b>>bum && bum<temp )
{
b >> bum;
b.ignore(80,'\n');
c << bum << endl;
b >> bum;
b.ignore(80,'\n');
}
c << temp << endl;
temp = bum;
}
else
{
while( a>>ark && ark<temp )
{
a >> ark;
a.ignore(80,'\n');
c << ark << endl;
a >> ark;
a.ignore(80,'\n');
}
c << temp << endl;
temp = ark;
}
while( c << temp )
{
cout << temp << endl;
}
system("PAUSE");
a.close();
b.close();
c.close();
return 0;
}
_________________________________________________________________
Send and receive Hotmail on your mobile device: http://mobile.msn.com
_______________________________________________________________
Don't miss the 2002 Sprint PCS Application Developer's Conference
August 25-28 in Las Vegas - http://devcon.sprintpcs.com/adp/index.cfm?source=osdntextlink
_______________________________________________
Dev-cpp-users mailing list
Dev...@li...
https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
|
|
From: Luigi S. <gi...@li...> - 2002-06-08 16:22:50
|
At 00.48 06/08/02 +0000, chromatonus 712 wrote:
>Hi, here is my program that is suppose to read one piece of data from 2
>different sorted lists each,
>
>like these two text files:
>
>File A: 1 2 4 8 16
>File B: 0 1 1 2 3 5 8
>
>output should be
>File C: 0 1 1 1 2 2 3 4 5 8 8 16
>
>Would anyone give a sample program that performs this function, using only
>the "basic" file stream operations as in my program below? Thank you very much
>
>#include "apstring.h"
>#include <iostream.h>
>#include <fstream.h>
>#include <conio.h>
You are including too many things, the sole you need is:
#include <fstream>
If you plan to use the Dos function "pause", you should also include
"<cstdlib>". Note that if you run console programs from a console (I
recommend you do) there is no need for the line: system("pause"); which,
however, makes your code Dos / Windows specific.
>int main()
>{
> ifstream a; ifstream b;
> ofstream c;
> a.open("A.dat");
> b.open("B.dat");
Files may be attached to streams using the constructor:
std::ifstream a("A.dat");
std::ifstream b("B.dat");
std::ofstream c("C.dat");
> int ark, bum, j, k, temp;
> a >> ark;
> a.ignore(80,'\n');
> j = ark;
> b >> bum;
> b.ignore(80,'\n');
> k = bum;
> if( ark < bum )
> {
> c << ark << endl;
> a >> ark;
> a.ignore(80,'\n');
> temp = ark;
> }
> else
> {
> c << bum << endl;
> b >> bum;
> b.ignore(80,'\n');
> temp = bum;
> }
> if(j<k)
> {
> while( b>>bum && bum<temp )
> {
> b >> bum;
> b.ignore(80,'\n');
> c << bum << endl;
> b >> bum;
> b.ignore(80,'\n');
> }
> c << temp << endl;
> temp = bum;
> }
> else
> {
> while( a>>ark && ark<temp )
> {
> a >> ark;
> a.ignore(80,'\n');
> c << ark << endl;
> a >> ark;
> a.ignore(80,'\n');
> }
> c << temp << endl;
> temp = ark;
> }
The above code, is probably clearer this way:
int n1; // buffer for first stream
int n2; // buffer for second stream
a >> n1; // load buffers
b >> n2;
while (a && b)
if (n1 < n2) // print element of first list
{
c << n1 << ' ';
a >> n1; // load next element of first list
}
else // print element of second list
{
c << n2 << ' ';
b >> n2;
}
> while( c << temp )
> {
> cout << temp << endl;
> }
I don't understand what the above lines do (why are you printing on "c" and
then on the screen?), however, to complete the task, you should copy what
is left of the first or second stream, not forgetting to flush the buffer.
Here is what I mean:
if (a) // while-loop ended because second file exhausted
{
c << n1 << ' '; // flush buffer
copy(a, c); // copy the rest of the first list
}
else
{
c << n2 << ' ';
copy(b, c);
}
The function "copy" could be:
inline void
copy(std::istream is, std::ostream os)
{ int n; while (is >> n) os << n << ' '; }
> system("PAUSE");
> a.close();
> b.close();
> c.close();
>
>
> return 0;
None of these lines is really required. I've already explained the reason
why not to use"system", as far as file streams are concerned, the
destructor will take care of closing them. "return 0" is implicit.
>}
Putting pieces together and testing the program is your fun :)
NOTE: from the way you write include directives, I would say that you are
working with pre-ANSI C++. I strongly suggest you switch to ANSI C++ as
soon as you can.
--
Luigi
gi...@li...
|
