Polynomials and ADT's

Hello all,

I have an assignment that asks

Recall that a polynomial in a single variable has the form a0xm + a1xm- 1 + a2xm-2 + … + an-2x2 + an-1x + an. An example of a polynomial is 4x12 - 3x10 + 5x8 + x4 -12x2 + x - 6. Notice that not all exponents may be included in a polynomial. Implement an ADT to represent a polynomial in a single variable x whose operations include the following:
degree()
// Returns the degree of the polynomial.
Coefficient(power)
// Returns the coefficient of the xpower term.
changeCoefficient(newCoefficient, power)
// Replaces the coefficient of the xpower term with
// newCoefficient.
For this problem consider only polynomials whose exponents are nonnegative integers. As the programmer, you will decide what data is to be stored and how that data is to be stored. What data type will you use to represent information for each node in this polynomial? What data structure will best represent any polynomial you wish to create?
Write a short program to test your ADT. Remember to separate your definition and implementation of this ADT into two files. Create a third file for your test program.




My question is, I see that I would need to use a class data structure.
But when it says write a short program, the book never went over anything that involves polynomials. I did some searching and it says something about vectors, is this the skill that i need to learn to solve this?

Can anyone steer me in the correct way to go about handling this question

I don't think you need to do any solving of the polynomials. Just write a program that takes input (in whatever format you want) and then call the functions specified in the assignment and make sure they return proper values.

For example, you could ask the user to input each term one at a time, and for each term ask for the power and the coefficient. Store that in an instance of your class, then output the final polynomial when you are done by accessing that class.

So its not asking for an input like (3X^2)+5x , more like

cout << "please put in the coefficient";
cin >> coeficient;

The functions given above are only descriptions. They dont have C++ code in them. Would it be asking basically to right out the description on what it wants or the actual fully functional C++ code?

Also how would I go about making the .h files so i can do

#include<iostream>
#include<somename.h>

using namespace std;

You're not allowed to write something so that you can do #include <somename.h>. However, you allowed to do #include "somename.h"; and the method for doing that is called "typing". The definition of the class would go in the .h file; its implementation in a separate .cpp file.

I just emailed my teacher asking for an explanation and an example of what this asking for . If you all could see my face, it's like a deer looking at headlights

here is what he said:

yes the book only has the ADT which is an abstract structure and for the assignment you need to implement the actual code for these ADT functions. for the polynomial, you may need to use a linked list to store the data such as the degree and coefficient which becomes an abstract model for the polynomial. the question already gives some details and you need to think about how to implement in code. You may search online to find some examples how to represent the polynomial in case you still get confused.


I asked for an example that would give me an idea of what the book is not showing me.
Is a linked list what I want to put my efforts into ?

A linked list is a common way of implementing a polynomial ADT, yes. You can use others, if you want.

You need to do what the question says to do: Design a class for this ADT; decide how to store the data; how to add terms/change terms (via change coefficient); how to spit the data back out (via coefficient, degree). (At this point, you don't have to actually do anything with the polynomial; perhaps that's the next assignment.) And then, for proof of concept, actually type that design into the computer and see if it works.

I really dont get these assignments. If there going by modules linked lists arent until the next chapter. How are u supposed to do an assignement regarding linked lists if u supposedly havent gotten up to it in the book. I am beginning to think these online teachers dont even know the books or material there teaching, just know programming languages and are accredited treachers.
Plus, they teach u the basics of linked list.

Im tempted to pay someone to do the homework so i can actually get somwhere and see how way off base some of the questions are in relation to the way the syllabus is structured for learning

i use map<int,double> for polynomials.

actually i use map<double,double>, but it sounds like you only need to consider integer exponents and it was important to disambiguate that the exponent must be the map key.

using map should make it exceedingly easy for you!

Am I so uninformed about C++ ? What is map<int,double>, is it apart of the STL library? if it is, its nice that the book somehow forgets to say anything about using STL libraries in this chapter.

Quote:

---

Originally Posted by Emeighty

Am I so uninformed about C++ ? What is map<int,double>, is it apart of the STL library? if it is, its nice that the book somehow forgets to say anything about using STL libraries in this chapter.

---

Yes.

I'm guessing, since you seem to be using Walls and Mirrors, that this is a data structures class? If so, your instructor is probably naively assuming that since the class has a programming class prerequisite that you already know how to program.

U hit it exactly. This the second class to C++ programming. THe things i learned briefly about in the first was, how to use functions, operators , simple class, and arrays. Walls and mirrors is the name of the book.

I appear to have made the moderators close the other thread [and it was much of a duplicate, so I think the moderators did the right thing].

If you had actually produced a more concrete question, such as "What does degree of a polynomial mean", which I think was one of your primary question, then I would think:
1. The thread would still be open.
2. You would more quickly have got to this:
http://en.wikipedia.org/wiki/Degree_of_a_polynomial

Of course, it would have been less typing [even if you Copy'n'pasted the actual polynomial task text itself] to type in "degree polynomial" in Google, and get to the link I posted above, which is the first link when you get it back from google.

--
Mats

since you're having trouble, and it's not a part of your assignment, here's part of the map implementation i suggested.

Code:

---

double polynomial::eval(double x)
{
    double result=0;
    for(map<int,double>::iterator it = coeffMap.begin();it!=coeffMap.end();it++)
    {
        result+=it->second*pow(x,it->first);
    }
    return result;
}

---

hope that helps (but not too much ;) )

I agree that I should have just added to the last thread, I was just not thinking about it like that. My bad on that one.
You guys are are the experts in this, and have no doubt that u are trying to lead me in the right direction to solve my troubles. Again, my apologies .
The suggestions that are posted here seem to be more advanced than what I have ever seen in the textbook, maybe if I were to ask the right questions and post what the textbook has went over currently I may give u all a feel for level I am at in my studies.

when in doubt, RTFM

Summary

An associative container with access to non-key values using unique keys. A map supports bidirectional iterators.

Synopsis

#include <map>
template <class Key, class T, class Compare = less<Key>
class Allocator = allocator<pair<const Key, T>> >
class map;

Description

map <Key, T, Compare, Allocator> gives fast access to stored values of type T that are indexed by unique keys of type Key. The default operation for key comparison is the < operator.

map has bidirectional iterators that point to an instance of pair<const Key x, T y> where x is the key and y is the stored value associated with that key. The definition of map includes a typedef to this pair called value_type.

The types used for both the template parameters Key and T must include the following (where T is the type, t is a value of T and u is a const value of T):

Copy constructors T(t) and T(u)
Destructor t.~T()
Address of &t and &u yielding T* and const T* respectively
Assignment t = a where a is a (possibly const) value of T

The type used for the Compare template parameter must satisfy the requirements for binary functions.

Interface

template <class Key, class T, class Compare = less<Key>
class Allocator = allocator<pair<const Key, T>> >
class map {
public:
// types
typedef Key key_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
typedef Allocator allocator_type;
typedef typename
Allocator::reference reference;

typedef typename
Allocator::const_reference const_reference;
class iterator;
class const_iterator;
typedef typename
Allocator::size_type size_type;
typedef typename
Allocator::difference_type difference_type;
typedef typename std::reverse_iterator<iterator>
reverse_iterator;
typedef typename std::reverse_iterator<const_iterator>
const_reverse_iterator;

class value_compare
: public binary_function<value_type, value_type, bool>
{
friend class map<Key, T, Compare, Allocator>;
protected :
Compare comp;
value_compare(Compare c): comp(c) {}
public :
bool operator() (const value_type&,
const value_type&) const;
};
// Construct/Copy/Destroy
explicit map (const Compare& = Compare(),
const Allocator& = Allocator ());
template <class InputIterator>

map (InputIterator, InputIterator,
const Compare& = Compare(),
const Allocator& = Allocator ());
map (const map<Key, T, Compare, Allocator>&);
~map();
map<Key, T, Compare, Allocator>&
operator= (const map<Key, T, Compare, Allocator>&);
allocator_type get_allocator () const;
// Iterators
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

reverse_iterator rend();
const_reverse_iterator rend() const;
// Capacity
bool empty() const;
size_type size() const;
size_type max_size() const;
// Element Access
mapped_type& operator[] (const key_type&);
// Modifiers
pair<iterator, bool> insert (const value_type&);
iterator insert (iterator, const value_type&);
template <class InputIterator>
void insert (InputIterator, InputIterator);
void erase (iterator);
size_type erase (const key_type&);

void erase (iterator, iterator);
void swap (map<Key, T, Compare, Allocator>&);
void clear();
// Observers
key_compare key_comp() const;
value_compare value_comp() const;
// Map operations
iterator find (const key_value&);
const_iterator find (const key_value&) const;
size_type count (const key_type&) const;
iterator lower_bound (const key_type&);
const_iterator lower_bound (const key_type&) const;
iterator upper_bound (const key_type&);

const_iterator upper_bound (const key_type&) const;
pair<iterator, iterator> equal_range (const key_type&);
pair<const_iterator, const_iterator>
equal_range (const key_type&) const;
};
// Non-member Map Operators
template <class Key, class T, class Compare, class Allocator>
bool operator== (const map<Key, T, Compare, Allocator>&,
const map<Key, T, Compare, Allocator>&);
template <class Key, class T, class Compare, class Allocator>

bool operator!= (const map<Key, T, Compare, Allocator>&,
const map<Key, T, Compare, Allocator>&);
template <class Key, class T, class Compare, class Allocator>
bool operator< (const map<Key, T, Compare, Allocator>&,
const map<Key, T, Compare, Allocator>&);
template <class Key, class T, class Compare, class Allocator>
bool operator> (const map<Key, T, Compare, Allocator>&,
const map<Key, T, Compare, Allocator>&);

template <class Key, class T, class Compare, class Allocator>
bool operator<= (const map<Key, T, Compare, Allocator>&,
const map<Key, T, Compare, Allocator>&);
template <class Key, class T, class Compare, class Allocator>
bool operator>= (const map<Key, T, Compare, Allocator>&,
const map<Key, T, Compare, Allocator>&);

// Specialized Algorithms
template <class Key, class T, class Compare, class Allocator>
void swap (map<*Key,T,Compare,Allocator>&,

map<Key,T,Compare,Allocator>&);

Constructors

explicit map(const Compare& comp = Compare(),
const Allocator& alloc = Allocator());

Constructs an empty map that uses the relation comp to order keys, if it is supplied. The map uses the allocator alloc for all storage management.

template <class InputIterator>
map(InputIterator first, InputIterator last,
const Compare& comp = Compare(),
const Allocator& alloc = Allocator());

Constructs a map containing values in the range [first, last). Creation of the new map is only guaranteed to succeed if the iterators first and last return values of type pair<class Key, class Value> and all values of Key in the range[first, last) are unique. The map uses the relation comp to order keys, and the allocator alloc for all storage management.

map(const map<Key,T,Compare,Allocator>& x);

Creates a new map by copying all pairs of key and value from x.

Destructors

~map();

Releases any allocated memory for this map.

Allocators

allocator_type get_allocator() const;

Returns a copy of the allocator used by self for storage management.

Iterators

iterator
begin();

Returns an iterator pointing to the first element stored in the map. “First“ is defined by the map’s comparison operator, Compare.

const_iterator
begin() const;

Returns a const_iterator pointing to the first element stored in the map.

iterator
end();

Returns an iterator pointing to the last element stored in the map (in other words, the off-the-end value).

const_iterator
end() const;

Returns a const_iterator pointing to the last element stored in the map.

reverse_iterator
rbegin();

Returns a reverse_iterator pointing to the first element stored in the map. “First“ is defined by the map’s comparison operator, Compare.

const_reverse_iterator
rbegin() const;

Returns a const_reverse_iterator pointing to the first element stored in the map.

reverse_iterator
rend();

Returns a reverse_iterator pointing to the last element stored in the map (in other words, the off-the-end value).

const_reverse_iterator
rend() const;

Returns a const_reverse_iterator pointing to the last element stored in the map.

Member Operators

map<Key, T, Compare, Allocator>&
operator=(const map<Key, T, Compare, Allocator>& x);

Replaces the contents of *this with a copy of the map x.

mapped_type&
operator[](const key_type& x);

If an element with the key x exists in the map, then a reference to its associated value is returned. Otherwise the pair x,T() is inserted into the map and a reference to the default object T() is returned.

Member Functions

void
clear();

Erases all elements from the self.

size_type
count(const key_type& x) const;

Returns a 1 if a value with the key x exists in the map. Otherwise returns a 0.

bool
empty() const;

Returns true if the map is empty, false otherwise.

pair<iterator, iterator>
equal_range (const key_type& x);

Returns the pair (lower_bound(x), upper_bound(x)).

pair<const_iterator,const_iterator>
equal_range (const key_type& x) const;

Returns the pair (lower_bound(x), upper_bound(x)).

void
erase(iterator position);

Deletes the map element pointed to by the iterator position. Returns an iterator pointing to the element following the deleted element, or end() if the deleted item was the last one in this list.

void
erase(iterator first, iterator last);

If the iterators first and last point to the same map and last is reachable from first, all elements in the range (first, last) are deleted from the map. Returns an iterator pointing to the element following the last deleted element, or end() if there were no elements after the deleted range.

size_type
erase(const key_type& x);

Deletes the element with the key value x from the map, if one exists. Returns 1 if x existed in the map, 0 otherwise.

iterator
find(const key_type& x);

Searches the map for a pair with the key value x and returns an iterator to that pair if it is found. If such a pair is not found the value end() is returned.

const_iterator find(const key_type& x) const;

Same as find above but returns a const_iterator.

pair<iterator, bool>
insert(const value_type& x);
iterator
insert(iterator position, const value_type& x);

If a value_type with the same key as x is not present in the map, then x is inserted into the map. Otherwise, the pair is not inserted. A position may be supplied as a hint regarding where to do the insertion. If the insertion is done right after position, then it takes amortized constant time. Otherwise it takes O(log N) time.

template <class InputIterator>
void
insert(InputIterator first, InputIterator last);

Copies of each element in the range [first, last) that possess a unique key (one not already in the map) are inserted into the map. The iterators first and last must return values of type pair<T1,T2>. This operation takes approximately O(N*log(size()+N)) time.

key_compare
key_comp() const;

Returns a function object capable of comparing key values using the comparison operation, Compare, of the current map.

iterator
lower_bound(const key_type& x);

Returns a reference to the first entry with a key greater than or equal to x.

const_iterator
lower_bound(const key_type& x) const;

Same as lower_bound above but returns a const_iterator.

size_type
max_size() const;

Returns the maximum possible size of the map. This size is only constrained by the number of unique keys that can be represented by the type Key.

size_type
size() const;

Returns the number of elements in the map.

void
swap(map<Key, T, Compare, Allocator>& x);

Swaps the contents of the map x with the current map, *this.

iterator
upper_bound(const key_type& x);

Returns a reference to the first entry with a key less than or equal to x.

const_iterator
upper_bound(const key_type& x) const;

Same as upper_bound above but returns a const_iterator.

value_compare
value_comp() const;

Returns a function object capable of comparing pair<const Key, T> values using the comparison operation, Compare, of the current map. This function is identical to key_comp for sets.

Non-member Operators

template <class Key, class T, class Compare, class Allocator>
bool operator==(const map<Key, T, Compare, Allocator>& x,
const map<Key, T, Compare, Allocator>& y);

Returns true if all elements in x are element-wise equal to all elements in y, using (T::operator==). Otherwise it returns false.

template <class Key, class T, class Compare, class Allocator>
bool operator!=(const map<Key, T, Compare, Allocator>& x,
const map<Key, T, Compare, Allocator>& y);

Returns !(x==y).

template <class Key, class T, class Compare, class Allocator>
bool operator<(const map<Key, T, Compare, Allocator>& x,
const map<Key, T, Compare, Allocator>& y);

Returns true if x is lexicographically less than y. Otherwise, it returns false.

template <class Key, class T, class Compare, class Allocator>
bool operator>(const map<Key, T, Compare, Allocator>& x,
const map<Key, T, Compare, Allocator>& y);

Returns y < x.

template <class Key, class T, class Compare, class Allocator>
bool operator<=(const map<Key, T, Compare, Allocator>& x,
const map<Key, T, Compare, Allocator>& y);

Returns !(y < x).

template <class Key, class T, class Compare, class Allocator>
bool operator>=(const map<Key, T, Compare, Allocator>& x,
const map<Key, T, Compare, Allocator>& y);

Returns !(x < y).

Specialized Algorithms

template <class Key, class T, class Compare, class Allocator>
void swap(map<Key, T, Compare, Allocator>& a,
map<Key, T, Compare, Allocator>& b);

Swaps the contents of a and b.

Example

//
// map.cpp
//
#include <string>
#include <map>
#include <iostream>
using namespace std;
typedef map<string, int, less<string> > months_type;
// Print out a pair
template <class First, class Second>
ostream& operator<<(ostream& out,
const pair<First,Second> & p)
{
cout << p.first << " has " << p.second << " days";
return out;
}
// Print out a map
ostream& operator<<(ostream& out, const months_type & l)
{

copy(l.begin(),l.end(), ostream_iterator
<months_type::value_type,char>(cout,"\n"));
return out;
}

int main(void)
{
// create a map of months and the number of days
// in the month
months_type months;
typedef months_type::value_type value_type;
// Put the months in the multimap
months.insert(value_type(string("January"), 31));
months.insert(value_type(string("February"), 28));
months.insert(value_type(string("February"), 29));

months.insert(value_type(string("March"), 31));
months.insert(value_type(string("April"), 30));
months.insert(value_type(string("May"), 31));
months.insert(value_type(string("June"), 30));
months.insert(value_type(string("July"), 31));
months.insert(value_type(string("August"), 31));
months.insert(value_type(string("September"), 30));
months.insert(value_type(string("October"), 31));
months.insert(value_type(string("November"), 30));

months.insert(value_type(string("December"), 31));
// print out the months
// Second February is not present
cout << months << endl;
// Find the Number of days in June
months_type::iterator p = months.find(string("June"));
// print out the number of days in June
if (p != months.end())
cout << endl << *p << endl;

return 0;
}

Program Output

April has 30 days
August has 31 days
December has 31 days
February has 28 days
January has 31 days
July has 31 days
June has 30 days
March has 31 days
May has 31 days
November has 30 days
October has 31 days
September has 30 days

Warnings

Member function templates are used in all containers included in the Standard Template Library. An example of this feature is the constructor for map<Key,T,Compare,Allocator> that takes two templatized iterators:

template <class InputIterator>
map (InputIterator, InputIterator,
const Compare& = Compare(),
const Allocator& = Allocator());

map also has an insert function of this type. These functions, when not restricted by compiler limitations, allow you to use any type of input iterator as arguments. For compilers that do not support this feature, substitute functions allow you to use an iterator obtained from the same type of container as the one you are constructing (or calling a member function on), or you can use a pointer to the type of element you have in the container.

For example, if your compiler does not support member function templates, you can construct a map in the following two ways:

map<int, int, less<int> >::value_type intarray[10];
map<int, int, less<int> > first_map(intarray,
intarray + 10);
map<int, int, less<int> > second_map(first_map.begin(),
first_map.end());

But not this way:

map<long, long, less<long> > long_map(first_map.begin(),
first_map.end());

Since the long_map and first_map are not the same type.

Also, many compilers do not support default template arguments. If your compiler is one of these, you always need to supply the Compare template argument and the Allocator template argument. For instance, you have to write:

map<int, int, less<int>, allocator<int> >

instead of:

map<int, int>

If your compiler does not support namespaces, then you do not need the using declaration for std.

See Also

allocator, Containers, Iterators, multimap


declare maps like this:

std::map<key_type,mapped_type> mapName;
insert data into them either using the insert method above or using brackets like so:

key_type k;
mapped_type m;

map[k]=m;

you iterate over maps (and many stl containers) with iterators.

in my code, this:

Code:

---

for(map<int,double>::iterator it = coeffMap.begin();it!=coeffMap.end();it++)
{
    result+=it->second*pow(x,it->first);
}

---

instantiates an iterator for the types of your map.

the map methods begin and end return an iterator that corresponds to...the beginning and the end of the data in the map.

All I can say is wow. U blew my mind away with this. This is going to take a long while for the light bulb to turn on. I have a book called C++ from the ground by Herbert Schildt that I am going to look read and come back to your example so i can hopefully get a grasp on this. Thanks for your time in trying to break through so i can understand this.

Quote:

---

Originally Posted by Emeighty

All I can say is wow. U blew my mind away with this. This is going to take a long while for the light bulb to turn on. I have a book called C++ from the ground by Herbert Schildt

---

Stop! Put the book down and go get yourself a good quality book. See the thread at the top of this board for recommendations. In fact you should consider burning the Schildt book to ensure you don't get infected by it.

wow why is it so bad? After i post this i'll read the post u said.
It just seems like the book is written easy enough to understand. I'll look into the others.

Quote:

---

Originally Posted by Emeighty

wow why is it so bad?

---

It's one thing to give readers successive approximations to the truth, as they increase their understanding and knowledge. It's another to just be wrong.

Edit: I suppose I should mention that I have not read any Schildt book in any great depth, just some flip throughs and reading some fairly thorough critiques on the web.

Wow, incorrect code and errors. Well thanks for the tips. Also will agree with ppl when they say the writing style makes it easy to understand. Wish I would have read this before i went out and bought these 2 books from the author.

everything between here:

Quote:

---

Originally Posted by me

when in doubt, RTFM

---

and here:

Quote:

---

Originally Posted by me

declare maps like this:

---

was just a copy & paste of the documentation page for map. imho, learning to read the documentation is the most critical skill you can learn. it takes some getting used to, it took me years before i read the documentation first and asked questions later, but now that i can adeptly decipher documentation-ese, i rarely have to ask questions!

my rule #1 of programming: RTFM :)