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 3 2364
On 20 Feb 2004 16:10:21 -0800 in comp.lang.c++, ak********@hotm ail.com
(Mike Jones) was alleged to have written: need help with data structures.Look ing 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.
"Mike Jones" <ak********@hot mail.com> wrote in message
news:ea******** *************** ***@posting.goo gle.com... 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
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
"Brian MacBride" <ma******@ix.ne tcom.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_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:di***** ******@yahoo.co m> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.co m/> This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: hzy_104 |
last post by:
Please recommend book on data structures for searching(c++)?
|
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.
Thanks.
|
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 universities
seem to teach this class. I tried taking one but just found it too
boring and irrelevant for what I was doing. What are your thoughts?
|
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 that doesn't offer dynamic
memory allocation (to be clear: no malloc, no realloc), and with
rather tight memory constraints.
Writing my own...
|
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
structures are read only)
Ideally one should be able to put the redundant
information there automatically so no mistakes are possible, but in a...
| |
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
structures?
Thanks for any hints,
Leszek Taratuta
|
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
osp
|
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 appreciate it:
1. What exactly is a Python list? If one writes a, then is the
complexity Theta(n)? If this is O(1), then why was the name "list"
chosen? If...
|
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 books about data structures in C+
+ etc., could anyone please recommend me such a C -specific book ? And
another question: are data structures (like...
|
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 on strings.
It can run through a million randomly generated strings in less than
half of a second (in most tests). The built-in dictionary class...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |