Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > data structures

Reply
Thread Tools

data structures

 
 
Mike Jones
Guest
Posts: n/a
 
      02-21-2004
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
 
Reply With Quote
 
 
 
 
David Harmon
Guest
Posts: n/a
 
      02-21-2004
On 20 Feb 2004 16:10:21 -0800 in comp.lang.c++, http://www.velocityreviews.com/forums/(E-Mail Removed)
(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.


 
Reply With Quote
 
 
 
 
Brian MacBride
Guest
Posts: n/a
 
      02-22-2004
"Mike Jones" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) 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

 
Reply With Quote
 
Dietmar Kuehl
Guest
Posts: n/a
 
      02-23-2004
"Brian MacBride" <(E-Mail Removed)> 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:stream& operator<< (std:stream& o, vp const& v) {
std::copy(v.mv.begin(), v.mv.end(),
std:stream_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:stream_iterator<int>(std::cout << vp(v) << "\n", "\n"));
}
else
std::cerr << "you goofed!\n";
}
--
<(E-Mail Removed)> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
structures, structures and more structures (questions about nestedstructures) Alfonso Morra C Programming 11 09-24-2005 07:42 PM
Type Casting IPv4 and IPv6 structures to Generic Structures tweak C Programming 14 06-11-2004 02:43 PM
data structures in java reference learningjava Java 3 10-16-2003 07:31 AM
Data Structures help MIke Beam Java 5 10-14-2003 09:53 AM
sharing complex data structures between threads in mod_perl2 Dennis Gavrilov Perl 1 07-24-2003 07:22 AM



Advertisments