data structures

[Mike Jones]

need help with data structures.Look ing for ways to start, sample code,
anything




Program description:

Design and implement a Visual C++ .NET program that inserts values
into a data structure and then removes them as described below.

First prompt the user to enter 3 values: an integer N from 1 to 100,
and non-negative integers J and K.

Build a data structure of size N that contains the integers 1 through
N as follows. Begin with an empty data structure, and insert the value
1. For each remaining value X from 2 through N, repeat the following
step J times: remove a value from the beginning of the data structure
and re-insert it at the end of the data structure. Then insert the new
value X at the end of the data structure, and print the data structure
after the new value X has been inserted. For example, when N=8 and
J=3:

[ 1 ]
[ 1 2 ]
[ 2 1 3 ]
[ 2 1 3 4 ]
[ 4 2 1 3 5 ]
[ 3 5 4 2 1 6 ]
[ 2 1 6 3 5 4 7 ]
[ 3 5 4 7 2 1 6 8 ]

Next remove all N values from the data structure as follows. Imagine
that the data structure is arranged in a cyclical fashion, so that
whenever you reach the end you automatically start over from the
beginning. At each step, to determine the next value that should be
removed: skip past the first K values, then remove the next value.
Print both the value that is removed and the data structure that
remains. Continuing the previous example, when K=4:

[ 3 5 4 7 2 1 6 8 ]
2
[ 1 6 8 3 5 4 7 ]
5
[ 4 7 1 6 8 3 ]
8
[ 3 4 7 1 6 ]
6
[ 3 4 7 1 ]
3
[ 4 7 1 ]
7
[ 1 4 ]
1
[ 4 ]
4
[ ]

Finally print all the values from 1 to N in the reverse of the order
in which they were previously removed:

4
1
7
3
6
8
5
2

[David Harmon]

Re: data structures

On 20 Feb 2004 16:10:21 -0800 in comp.lang.c++, akickdoe22@hotm ail.com
(Mike Jones) was alleged to have written:[color=blue]
>need help with data structures.Look ing for ways to start, sample code,
>anything[/color]

1. In general, the more specific your question, the better the help you
will get.

2. Let's keep things simple. Use std::vector for your container. Use
the erase member function whenever required to remove an entry. Screw
efficiency until you have working code.

3. Use operator% on the vector index for the "imagine it's circular"
part.

4. When you get stuck, post what code you have written and ask for more
help.

[Brian MacBride]

Re: data structures

"Mike Jones" <akickdoe22@hot mail.com> wrote in message
news:ea6a1a8a.0 402201610.25790 203@posting.goo gle.com...[color=blue]
> need help with data structures.Look ing for ways to start, sample code,
> anything
>
>
>
>
> Program description:
>
> Design and implement a Visual C++ .NET program that inserts values
> into a data structure and then removes them as described below.
>
> First prompt the user to enter 3 values: an integer N from 1 to 100,
> and non-negative integers J and K.
>
> Build a data structure of size N that contains the integers 1 through
> N as follows. Begin with an empty data structure, and insert the value
> 1. For each remaining value X from 2 through N, repeat the following
> step J times: remove a value from the beginning of the data structure
> and re-insert it at the end of the data structure. Then insert the new
> value X at the end of the data structure, and print the data structure
> after the new value X has been inserted. For example, when N=8 and
> J=3:
>
> [ 1 ]
> [ 1 2 ]
> [ 2 1 3 ]
> [ 2 1 3 4 ]
> [ 4 2 1 3 5 ]
> [ 3 5 4 2 1 6 ]
> [ 2 1 6 3 5 4 7 ]
> [ 3 5 4 7 2 1 6 8 ]
>
> Next remove all N values from the data structure as follows. Imagine
> that the data structure is arranged in a cyclical fashion, so that
> whenever you reach the end you automatically start over from the
> beginning. At each step, to determine the next value that should be
> removed: skip past the first K values, then remove the next value.
> Print both the value that is removed and the data structure that
> remains. Continuing the previous example, when K=4:
>
> [ 3 5 4 7 2 1 6 8 ]
> 2
> [ 1 6 8 3 5 4 7 ]
> 5
> [ 4 7 1 6 8 3 ]
> 8
> [ 3 4 7 1 6 ]
> 6
> [ 3 4 7 1 ]
> 3
> [ 4 7 1 ]
> 7
> [ 1 4 ]
> 1
> [ 4 ]
> 4
> [ ]
>
> Finally print all the values from 1 to N in the reverse of the order
> in which they were previously removed:
>
> 4
> 1
> 7
> 3
> 6
> 8
> 5
> 2[/color]

Sure, it is only a few lines of code.

Consider...

#include <iostream>
using namespace std;
#include <iterator>

void print (const int *a, const int v, const char *const t = " ") {
ostream_iterato r <int> oi (cout, t);
if (*t != '\n')
cout << "[ ";
copy (a, a + v, oi);
if (*t != '\n')
cout << ']';
cout << endl;
}

void build (int *const a, const int J, const int v) {
for (int i = J % (v - 1); i; --i) {
a[v - 1] = *a;
memmove (a, a + 1, (v - 1) * sizeof *a);
}
a[v - 1] = v;
print (a, v);
}

void remove (int *const a, const int K, const int v) {
int i = v > K ? K : K % v;
cout << a[i] << endl;
for (; i < (v - 1); ++i) {
const int k = a[v - 1];
memmove (a + 1, a, (v - 1) * sizeof *a);
*a = k;
}
print (a, v - 1);
}

int main () {
const int N = 8, J = 3, K = 4;
int *const a = new int[N], v;
print (a, *a = 1);

for (v = 2; v <= N; ++v)
build (a, J, v);
cout << endl;

for (v = N; v; --v)
remove (a, K, v);
cout << endl;

print (a, N, "\n");

delete[] a;

return 0;
}

/*
[ 1 ]
[ 1 2 ]
[ 2 1 3 ]
[ 2 1 3 4 ]
[ 4 2 1 3 5 ]
[ 3 5 4 2 1 6 ]
[ 2 1 6 3 5 4 7 ]
[ 3 5 4 7 2 1 6 8 ]

2
[ 1 6 8 3 5 4 7 ]
5
[ 4 7 1 6 8 3 ]
8
[ 3 4 7 1 6 ]
6
[ 3 4 7 1 ]
3
[ 4 7 1 ]
7
[ 1 4 ]
1
[ 4 ]
4
[ ]

4
1
7
3
6
8
5
2
*/

--
Regards,

Brian

[Dietmar Kuehl]

Re: data structures

"Brian MacBride" <macbride@ix.ne tcom.com> wrote:[color=blue]
> Sure, it is only a few lines of code.[/color]

If you do someone's homework assignment, do it in a form utterly useless
for them! At minimum, it should be plain to the person correcting the
homework, that the student hadn't written it. Here is an example:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

int main()
{
int n = 0, j = 0, k = 0;
if (std::cin >> n >> j >> k && 1 <= n && n <= 100 && 0 <= j && 0 <= k)
{
std::vector<int > v;
struct vp {
vp(std::vector< int> const& v): mv(v) {}
std::vector<int > const& mv;
friend std::ostream& operator<< (std::ostream& o, vp const& v) {
std::copy(v.mv. begin(), v.mv.end(),
std::ostream_it erator<int>(o << "[ ", " "));
return o << "]";
}
};

for (int i = 0; i < n; std::cout << vp(v) << "\n")
v.push_back((st d::rotate(v.beg in(),
v.begin() + j % (i? i: j),
v.end()), ++i));
std::vector<int > s(v.size());
for (std::vector<in t>::iterator i = s.end();
!v.empty() && std::cout << vp(v) << "\n"
<< (*--i = v[k % v.size()]) << "\n";
v.erase(v.begin ()))
std::rotate(v.b egin(), v.begin() + k % v.size(), v.end());
std::copy(s.beg in(), s.end(),
std::ostream_it erator<int>(std ::cout << vp(v) << "\n", "\n"));
}
else
std::cerr << "you goofed!\n";
}
--
<mailto:dietmar _kuehl@yahoo.co m> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.co m/>