C++ Dynamic deque - find smallest number

[preslav_milev]

Hello !

How i can find the smallest number, higher than average value. For example in deque I have these numbers: 46 84 25 93 91 25 37 32 64 49 17 81 59 38 79 22 57 17 61 11 (transferred from file Stack.txt to deque.txt). Тhe average of these numbers is 49.4, and the smallest number greater than this value should be 57. I should find it without using arrays.

Тhis is my code:

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <stdio.h>

using namespace std; 

int temp;
int br = 1;

struct delem
{

    int key;
    delem *next;

} *l = NULL, *r = NULL;

void push_l(int n) 
{

    delem *p;      
    p = l;           
    l = new delem;     
    l->key = n; 
    l->next = p;             
    if (r == NULL) 
    {

        r = l;
    }

}

void push_r(int n)             
{

    delem *p;           
    p = r;             
    r = new delem;    
    r->key = n;               
    r->next = NULL;   
    if (l == NULL)             
    {

        l = r; 

    }
    else                 
        p->next = r; 

}

int pop_l(int &n)             
{
    delem *p;                
    if (l)                     
    {
        n = l->key;        
        p = l;                  
        l = l->next;    
        if (l== NULL)             
            r = NULL;         
        delete p;             
        return 1;
    }
    else
        return 0;
}

int pop_r(int &n)
{
    delem *p;                 
    if (r)                     
    {

        n = r->key;                
        if (l == r)           
        {
            delete r;          
            l = r = NULL;  
        }
        else
        {
            p = l;                     
            while (p->next != r)
                p = p->next;                   
                //p++;
                n = r->key;                        
                p->next = NULL;         
                delete r;                  
                       r = p;                    
                       return 1;
        }

   }
   else
       return 0;

}

void get(int n)
{

    int i, t;
    for (i = 1; i < br; i++) 
    {

        pop_l(t); 
        if (i == n)
        {

            temp = t;

        }

        push_r(t); 

    }

}

void print_deque()
{

    for (int i = 1; i<br; i++) 
    {

        get(i);
        cout << temp << " ";

    }

}

void input_deque() 
{
    int a;
    ifstream i_file;
    i_file.open("Stack.txt", ios::in);
    if (i_file)
    {

        while (i_file >> a)
        {

            push_l(a);

        }

        ofstream f_file;
        f_file.open("deque.txt", ios::out);
        while (pop_l(a))
        {

            f_file << a << " ";
            cout << a << " ";

        }
        f_file.close();

        i_file.close();

    }
    else
        cout << "Error while opening input file!" << endl;

}

void find_number()
{

    int n, m;
    int total = 0;
    double min = 1;
    double count = 0;
    double average = 0;
    ifstream deque_file;
    deque_file.open("deque.txt", ios::in);

    if (deque_file)
    {

        while (deque_file >> n)
        {

            push_l(n);

            while(pop_l(n))
            {

                //min = (n<min)?n:min;
                total+=n;
                count++;

            }

        }

        average = total/count;

        cout<<"\nSum: " << total << " Count: " << count << " Average: " << average << endl;

    }
    else
        cout << "Error while opening input file!" << endl;

    deque_file.close();

    ifstream deque_file2;
    deque_file2.open("deque.txt", ios::in);
    if(deque_file2)
    {

        while(deque_file2 >> m)
        {

            push_l(m);

            while(pop_l(m))
            {

                //min = (m>average)?m:average;
                if(m > average)
                {

                    min = m;

                }


            }

        }

        cout << "\nMin: " << min << endl;

    }
    else
        cout << "Error while opening input file!" << endl;

    deque_file2.close();

}

void dclean()
{

    ifstream deque_file;
    deque_file.open("deque.txt", ios::trunc);
    deque_file.close();

}

int main()
{

    input_deque();

    print_deque();

    cout << endl;

    find_number();
    dclean();
    cout << endl;

    system("pause");
    return 0;

}

[David W]

So you have several problems ...

/*
1) using the C++ library deque (FIFO) container to the hold the int's input from file
2) using pop / push onto a 2nd deque ...  get sum/size to get average
3) start with setting the 1st int in the new deque as the x value.
   if the next val is greater than the average and less than that previous x value, update x
    when you have emptied the deque you will have the desired x value;
4) when you get all the above debugged and working ok, code you own class Deque 
    (if you must) 
    and use that in the place of the C++ library deque you developed with above.
    */

[rubberman]

Do you have ANY idea what your are doing? Are you trying to use std::deque for your code? Are you trying to "roll your own" version? See this: http://www.cplusplus.com/reference/deque/deque/

[David W]

3) start with setting the 1st int in the new deque as the x value. If the next val is greater than the average and less than that previous x value, update x ... when you have emptied the deque you will have the desired x value;

The above idea was missing some things here ...

You need to firstly go though the container and select, as a comparator, the first element that was greater than the average ... then the above idea is valid.

Also ... you can traverse a deque with iterators.

See below ...
(an example of how this could be coded using the C++ library deque.)

// findNextNumAfterAvg.cpp //

/*
    How i can find the smallest number, higher than average value.

    For example in deque I have these numbers:
    46 84 25 93 91 25 37 32 64 49 17 81 59 38 79 22 57 17 61 11
    (transferred from file Stack.txt to deque.txt).

    The average of these numbers is 49.4,
    and the smallest number greater than this value should be 57.
    I should find it without using arrays.

*/


#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

const char* FNAME = "numbers.txt";
/*
46 84 25 93 91 25 37 32 64 49 17 81 59 38 79 22 57 17 61 11
*/


bool load_from_file( const char* fname, deque< int >& dq )
{
    ifstream fin( fname );
    if( fin )
    {
        int i;
        while( fin >> i ) dq.push_back(i);
        fin.close();
        return true;
    }
    // else if reach here ...
    cout << "There was a problem opening file: '" << fname
         << "'\n";
    return false;
}


int main()
{
    deque< int > dq;
    if( load_from_file( FNAME, dq ) )
    {
        deque< int >::const_iterator it;
        double sum = 0;
        for( it = dq.begin(); it != dq.end(); ++ it )
        {
            sum += *it;
        }
        double avg = sum / dq.size();
        cout << "Sum is: " << sum
             << " and average is: " << avg << endl;

        it = dq.begin();
        while( ++it != dq.end() )
        {
            if( *it > avg ) break;
        }

        int low = *it;

        while( ++it != dq.end() )
        {
            if( *it > avg && *it < low ) low = *it;
        }

        cout << "The next largest value after the average value of "
             << avg << " is: " << low << endl;
    }

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

But note that since your spec's were only that ...

I should find it without using arrays.

You could have use a list constainer ... which is what you seemed to have been coding in a ...'roll your own version' ... of the C++ library list container. Note also that you could replace everywhere above deque with list and the code will compile and run with correct output. (Try it and see?)

[preslav_milev]

David W, thank you for helping, but i need to do it without using STL. I found the higher value less than the average value, which is 49. Now i need to find smallest number, higher than average.

Here is the updated code:

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <stdio.h>

using namespace std; 

int temp;
int br = 0;

struct delem
{

    int key;
    delem *next;

} *l = NULL, *r = NULL;

void push_l(int n) 
{

    br++;
    delem *p;      
    p = l;           
    l = new delem;     
    l->key = n; 
    l->next = p;             
    if (r == NULL) 
    {

        r = l;
    }

}

void push_r(int n)             
{

    br++;
    delem *p;           
    p = r;             
    r = new delem;    
    r->key = n;               
    r->next = NULL;   
    if (l == NULL)             
    {

        l = r; 

    }
    else                 
        p->next = r; 

}

int pop_l(int &n)             
{
    delem *p;                
    if (l)                     
    {
        n = l->key;        
        p = l;                  
        l = l->next;    
        if (l== NULL)             
            r = NULL;         
        delete p;             
        return 1;
    }
    else
        return 0;
}

int pop_r(int &n)
{
    delem *p;                 
    if (r)                     
    {

        n = r->key;                
        if (l == r)           
        {
            delete r;          
            l = r = NULL;  
        }
        else
        {
            p = l;                     
            while (p->next != r)
                p = p->next;                   
                n = r->key;                        
                p->next = NULL;         
                delete r;                  
                       r = p;                    
                       return 1;
        }

   }
   else
       return 0;

}

void print_deq()
{

    delem *beg = l;

    while (l != r)
    {
        cout << l->key << " ";
        l = l->next;
    }

    cout << l->key;
    cout << endl;
    l = beg;

}

void sort_deq()
{

    delem *T;
    int n, flag;
    if (l == NULL) cout << "Empty deque!";
    else{
        do
        {
            flag = 0;
            T = l;
            while (T->next)
            {
                if (T->key > T->next->key)
                {
                    n = T->key;
                    T->key = T->next->key;
                    T->next->key = n;
                    flag = 1;
                }
                T = T->next;
            }
        } while (flag);
    }

}

void find_avg()
{

    sort_deq();
    double sum = 0;
    double avg;
    delem *beg = l;
    while (l->next)
    {
        sum+=l->key;
        l = l->next;
    }
    sum += l->key;
    avg = sum/br;
    l = beg;

    while (l->next->key < avg)
    {
        l = l->next;
    }
    cout << "br: " << br << endl;
    cout << "avg: " << avg << endl;
    cout << "min: " << l->key << endl;
    l = beg;

}

int main()
{

    int n;

    ifstream deq_file;
    deq_file.open("deque.txt", ios::in);

    if (deq_file)
    {

        while (deq_file >> n)
        {

            push_l(n);

        }

        print_deq();
        sort_deq();
        print_deq();
        find_avg();

    }
    else
        cout << "Error while opening input file!" << endl;

    deq_file.close();

    system("pause");
    return 0;

}

Oops, i have a mistake:

while (l->next->key < avg)
should be:
while (l->key < avg)

[David W]

Did you notice the steps I took to get a solution?

Firstly using the C++ library container to solve the problem at hand.

Then, if you need to code your own 'home-grown' List container ... (a single-link linked list is what you looked to be coding) ... that is a SEPARATE problem.

And when that List is working ok ... just plug-in that List.

See below:

#include <iostream>
#include <fstream>
#include <climits>

using namespace std; 

const char* FNAME = "numbers.txt";

struct Node
{
    int key;
    Node *next;

    // ctor...
    Node( int key=0, Node* next = 0 ) : key(key), next(next) {}
} ;

struct List
{
    Node* head;
    Node* tail;
    int len;

    // ctor...
    List( Node* head=0, Node* tail=0 ) :  head(head), tail(tail), len(0) {}
    // detor...
    ~List() { clear();   }

    void clear()
    {
        while( head != 0 )
        {
            Node* cur = head;
            head = head->next;
            delete cur;
        }
        tail = 0;
        len = 0;
    }

    int size() const { return len; }

    void push_front( int key )
    {
        head = new Node( key, head );
        if( !len ) tail = head;

        ++ len;
    }

    void push_back( int key )
    {
        Node* old_tail = tail;
        tail = new Node( key );
        if( len ) old_tail->next = tail;
        else head = tail;

        ++ len;
    }

    int pop_front()
    {
        if( len )
        {
            Node* cur = head;
            head = head->next;

            --len;
            if( !len ) tail = 0;
            int key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << INT_MIN << '\n';
        return INT_MIN;
    }

    int pop_back()
    {
        if( len )
        {
            Node* cur = head;
            if( len > 1 )
            {
                while( cur && cur->next )
                    cur = cur->next;
                tail = cur;
            }
            else // len == 1
                tail = 0;

            --len;

            if( !len ) head = 0;
            int key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << INT_MIN << '\n';
        return INT_MIN;
    }

    void print( ostream& os, const char end = ' ' ) const
    {
        for( Node* cur = head; cur != 0; cur = cur->next )
            os << cur->key << end;
    }

    void bubble_sort()
    {
        if( len > 1 )
        {
            bool swap;
            do
            {
                swap = false;
                Node* cur  = head;
                while( cur->next )
                {
                    if( cur->next->key < cur->key ) // swap //
                    {
                        int tmp = cur->key;
                        cur->key = cur->next->key;
                        cur->next->key = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
            }
            while( swap );
        }
        else
            cout << "Size was less than 2  ... so NO sort needed.\n";
    }

} ;


void process_display( List& lst )
{
    if( lst.size() )
    {

        // sort and show sorted list //
        lst.bubble_sort();
        lst.print( cout );
        cout << endl;

        // get sum and average //
        Node* cur  = lst.head;
        double avg, sum = 0;

        while( cur )
        {
            sum += cur->key;
            cur = cur->next;
        }

        avg = sum / lst.size();

        cur = lst.head;

        int low = cur->key;
        while( cur != 0 && cur->key <= avg )
            cur = cur->next;
        if( cur )
            low = cur->key;

        cout << "size            : " << lst.size() << endl;
        cout << "sum             : " << sum << endl;
        cout << "avg             : " << avg << endl;
        cout << "first after avg : " << low << endl;
    }
}


int main()
{
    ifstream fin( FNAME );

    if( fin )
    {
        int key;
        List lst; // get an enpty list //
        while( fin >> key )
        {
            lst.push_back( key );
        }
        fin.close();

        cout << "Showing list ...\n";
        lst.print( cout );
        cout << endl;

        cout << "Process and firstly show sorted ...\n";
        process_display( lst ) ;

    }
    else
        cout << "Error while opening input file!"
             << FNAME << '\n';

    cout << "Press 'Enter' to continue/exit ... " << flush;
    cin.get();
    return 0;
}

[David W]

And just to round out this demo ...
the edits needed to go to a template class
are fairly straight forward
once you have some code working ok for the class List (or struct List) with just an int data type;

Take a look:

// findNextGreatestAfterAvg2.cpp //


#include <iostream>
#include <fstream>

using namespace std; 

const char* FNAME = "numbers.txt";

template < typename T >
class List; // forward declaration //

template < typename T >
class Node
{
public:
    // ctor...
    Node( T key=0, Node* next = 0 ) : key(key), next(next) {}
    T get_key() const { return key; }
private:
    T key;
    Node* next;
    friend class List< T >;
} ;


template < typename T >
class List
{
private:
    Node< T >* head;
    Node< T >* tail;
    size_t len;
public:
    // ctor...
    List( Node< T >* head=0, Node< T >* tail=0 ) :  head(head), tail(tail), len(0) {}
    // detor...
    ~List() { clear();   }

    void clear()
    {
        while( head != 0 )
        {
            Node< T >* cur = head;
            head = head->next;
            delete cur;
        }
        tail = 0;
        len = 0;
    }

    size_t size() const { return len; }

    void push_front( const T& key )
    {
        head = new Node< T >( key, head );
        if( !len ) tail = head;

        ++ len;
    }

    void push_back( const T& key )
    {
        Node< T >* old_tail = tail;
        tail = new Node< T >( key );
        if( len ) old_tail->next = tail;
        else head = tail;

        ++ len;
    }

    T pop_front()
    {
        if( len )
        {
            Node< T >* cur = head;
            head = head->next;

            --len;
            if( !len ) tail = 0;
            T key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << T() << '\n';
        return T();
    }


    T pop_back()
    {
        if( len )
        {
            Node< T >* cur = head;
            if( len > 1 )
            {
                while( cur && cur->next )
                    cur = cur->next;
                tail = cur;
            }
            else // len == 1
                tail = 0;

            --len;

            if( !len ) head = 0;
            T key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << T() << '\n';
        return T();
    }

    void print( ostream& os, const char end = ' ' ) const
    {
        for( Node< T >* cur = head; cur != 0; cur = cur->next )
            os << cur->key << end;
    }

    void bubble_sort()
    {
        if( len > 1 )
        {
            bool swap;
            do
            {
                swap = false;
                Node< T >* cur  = head;
                while( cur->next )
                {
                    if( cur->next->key < cur->key ) // swap //
                    {
                        T tmp = cur->key;
                        cur->key = cur->next->key;
                        cur->next->key = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
            }
            while( swap );
        }
        else
            cout << "Size was less than 2  ... so NO sort needed.\n";
    }

    class Iterator
    {
    private:
        Node< T >* cur;
    public:
        Iterator( Node< T >* p = 0 ) : cur(p) {}

        Iterator operator ++ () { cur = cur->next; return *this; }
        Iterator operator ++ (int) { cur= cur->next; return *this; }

        bool operator == ( Iterator it ) const { return cur == it.cur; }
        bool operator != ( Iterator it ) const { return cur != it.cur; }

        T operator * () { return cur->key; }

    } ;

    Iterator begin() { Iterator it(head); return it; }
    Iterator end() { Iterator it; return it; }

} ;



void process_display( List< int >& lst )
{
    if( lst.size() )
    {

        // sort and show sorted list //
        lst.bubble_sort();
        lst.print( cout );
        cout << endl;

        // get sum and average //
        List< int >::Iterator it = lst.begin();
        double avg, sum = 0;

        while( it != lst.end() )
        {
            sum += *it;
            ++it;
        }

        avg = sum / lst.size();

        // Since the list is now in increasing sorted order ...
        // get 1st element value right after average ... if exists //

        it = lst.begin();

        int low = *it;
        while( it != lst.end() && *it <= avg )
            ++it;
        if( it != lst.end() )
            low = *it;

        cout << "size            : " << lst.size() << endl;
        cout << "sum             : " << sum << endl;
        cout << "avg             : " << avg << endl;
        cout << "first after avg : " << low << endl;
    }
}




int main()
{
    ifstream fin( FNAME );

    if( fin )
    {
        int key;
        List< int > lst; // get an enpty list //
        while( fin >> key )
        {
            lst.push_back( key );
        }
        fin.close();

        cout << "Showing list ...\n";
        lst.print( cout );
        cout << endl;

        cout << "Process but firstly show sorted ...\n";
        process_display( lst ) ;

    }
    else
        cout << "Error while opening input file!"
             << FNAME << '\n';

    cout << "Press 'Enter' to continue/exit ... " << flush;
    cin.get();
    return 0;
}