data structures

Discussion in 'C++' started by Mike Jones, Feb 21, 2004.

  1. Mike Jones

    Mike Jones Guest

    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
     
    Mike Jones, Feb 21, 2004
    #1
    1. Advertising

  2. Mike Jones

    David Harmon Guest

    On 20 Feb 2004 16:10:21 -0800 in comp.lang.c++,
    (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.
     
    David Harmon, Feb 21, 2004
    #2
    1. Advertising

  3. "Mike Jones" <> wrote in message
    news:...
    > 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 << 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, Feb 22, 2004
    #3
  4. "Brian MacBride" <> 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::eek:stream& operator<< (std::eek:stream& o, vp const& v) {
    std::copy(v.mv.begin(), v.mv.end(),
    std::eek: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::eek:stream_iterator<int>(std::cout << vp(v) << "\n", "\n"));
    }
    else
    std::cerr << "you goofed!\n";
    }
    --
    <mailto:> <http://www.dietmar-kuehl.de/>
    Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
     
    Dietmar Kuehl, Feb 23, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dennis Gavrilov
    Replies:
    1
    Views:
    1,454
    Dennis Gavrilov
    Jul 24, 2003
  2. MIke Beam

    Data Structures help

    MIke Beam, Oct 10, 2003, in forum: Java
    Replies:
    5
    Views:
    519
    antroy
    Oct 14, 2003
  3. learningjava

    data structures in java reference

    learningjava, Oct 15, 2003, in forum: Java
    Replies:
    3
    Views:
    436
    Samuel Barber
    Oct 16, 2003
  4. tweak
    Replies:
    14
    Views:
    2,791
    Eric Sosman
    Jun 11, 2004
  5. Alfonso Morra
    Replies:
    11
    Views:
    722
    Emmanuel Delahaye
    Sep 24, 2005
Loading...

Share This Page