data structures

Mike Jones

need help with data structures.Looking 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

Jul 22 '05 #1

David Harmon

On 20 Feb 2004 16:10:21 -0800 in comp.lang.c++, ak********@hotmail.com
(Mike Jones) was alleged to have written:

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

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.

Jul 22 '05 #2

Brian MacBride

"Mike Jones" <ak********@hotmail.com> wrote in message
news:ea**************************@posting.google.c om...

need help with data structures.Looking 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

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_iterator <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

Jul 22 '05 #3

Dietmar Kuehl

"Brian MacBride" <ma******@ix.netcom.com> wrote:

Sure, it is only a few lines of code.

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_iterator<int>(o << "[ ", " "));
return o << "]";
}
};

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

Jul 22 '05 #4