472,969 Members | 1,733 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,969 software developers and data experts.

data structures

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
3 2280
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
"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
"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

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: hzy_104 | last post by:
Please recommend book on data structures for searching(c++)?
1
by: Amit | last post by:
Hello, Can any of you recommend a really good book on data structures and more so, if it relates to STL data structures, and how they are used to build far more complex data structures. ...
5
by: el_roachmeister | last post by:
For being a good web programmer, is a course on data structures important? It seems php already has built-in functions for what they teach in a data structures course. On the other hand all...
4
by: Thomas Paul Diffenbach | last post by:
Can anyone point me to an open source library of /statically allocated/ data structures? I'm writing some code that would benefit from trees, preferably self balancing, but on an embedded system...
10
by: Bart Goeman | last post by:
Hi, I have a question about how to put redundant information in data structures, initialized at compile time. This is often necessary for performance reasons and can't be done at run time (data...
13
by: Leszek Taratuta | last post by:
Hello, I have several drop-down lists on my ASP.NET page. I need to keep data sources of these lists in Session State. What would be the most effective method to serialize this kind of data...
3
by: osp | last post by:
hi to every one.... i just started out with c++ and i think i am doing well.i use Robert Laffore to study. which book should i use for data structures ? please help. thank you with regards ...
11
by: efrat | last post by:
Hello, I'm planning to use Python in order to teach a DSA (data structures and algorithms) course in an academic institute. If you could help out with the following questions, I'd sure...
29
by: Mik0b0 | last post by:
Hallo to everyone. This fall I am going to start data structures as a part of C language course. The problem is I could not find any satisfying tutorial about structures in C. There are plenty of...
4
by: jehugaleahsa | last post by:
Hello: When developing data structures for C#, there is an obvious performance hit when utilizing primitive types. For instance, a recent hash table implementation I wrote works exceedingly fast...
0
by: lllomh | last post by:
Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 4 Oct 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
0
by: Aliciasmith | last post by:
In an age dominated by smartphones, having a mobile app for your business is no longer an option; it's a necessity. Whether you're a startup or an established enterprise, finding the right mobile app...
0
tracyyun
by: tracyyun | last post by:
Hello everyone, I have a question and would like some advice on network connectivity. I have one computer connected to my router via WiFi, but I have two other computers that I want to be able to...
4
NeoPa
by: NeoPa | last post by:
Hello everyone. I find myself stuck trying to find the VBA way to get Access to create a PDF of the currently-selected (and open) object (Form or Report). I know it can be done by selecting :...
1
by: Teri B | last post by:
Hi, I have created a sub-form Roles. In my course form the user selects the roles assigned to the course. 0ne-to-many. One course many roles. Then I created a report based on the Course form and...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 1 Nov 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM) Please note that the UK and Europe revert to winter time on...
3
by: nia12 | last post by:
Hi there, I am very new to Access so apologies if any of this is obvious/not clear. I am creating a data collection tool for health care employees to complete. It consists of a number of...
0
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.