2009210107 김태호
CNCE210-02, Spring 2010
Assignment #1: Implementation of polynomial addition
1. Test Environment
Microsoft Windows Vista 32-bit, Visual C++ 2008
2. How to Use
There are three executable files, [Link], [Link], [Link], in the bin\ directory. Each
program has a common interface, but they use different data structure implementations.
When you run the program, “Num of terms:” prompt will be shown. You can type the number of
terms in the first polynomial. Then you’ll see “coef expon>” prompt. You will type the coefficient
and exponent of the term. The exponent shouldn’t be negative number since you’re calculating
polynomials. Also the exponents should be input in decreasing order. (If you give invalid input, the
program will show the error.)
After you finish typing all terms, you will see “Num of terms:” prompt again. This is for the
second polynomial. Repeat the same procedure that I explained above. Finally, two polynomials
you gave will be added and the result will be printed.
3. Implemetation Details
0) main.c
In order to reduce the duplication of code, I used #define and #ifdef macros. The data
structure implementation will be selected according to which constant is defined. These constant
definitions are commented by default. Please uncomment ONLY ONE line to compile the
program. By this way, all three implementations use some common test routines. Each data
structure implements these common function interfaces.
Poly *poly_new();
Create new zero polynomial and returns its pointer.
void poly_attach(Poly *, int coef, int expon);
Attach the term to the end of the given polynomial.
Poly *poly_add(Poly *, Poly *);
Add two polynomials and returns its result’s pointer.
void poly_print(Poly *);
Print the polynomial in the readable form.
I assumed that terms will be ‘attached’ in the descending order, to simplify the implementation.
Therefore the terms will not be sorted.
1) array_impl.c (Array Implementation)
(1) Basic Logics
This version allocates some space in
a = poly_new();
the memory statically. The size of space is
a->start
determined by the value of MAX_TERMS
a->end
constant. When the poly_new function
avail
called, a structure containing the start
0 1 2 … MAX_TERMS - 1
index and end index in the array will be
returned.
A polynomial term can be added by poly_attach(a, 3, 8);
poly_attach function. Then the a->end a->start a->end
and avail increase 1. avail
0 1 2 … MAX_TERMS - 1
coef=3
expon=8
If we create a new polynomial, it will start from avail index.
b = poly_new();
a->start a->end
b->start
b->end
avail
0 1 2 … MAX_TERMS - 1
coef=3
expon=8
(2) Polynomial Addition Algorithm (in pseudo code)
define padd(a, b) {
result = poly_new()
while (a and b have terms left) {
if ([Link] == [Link]) {
attach term coef=[Link] + [Link], expon=[Link]
advance a to the next term
advance b to the next term
}
else if ([Link] < [Link]) {
attach term same with b
advance b to the next term
}
else if ([Link] > [Link]) {
attach term same with a
advance a to the next term
}
}
attach terms left in a to the result
attach terms left in b to the result
return result
}
(3) Problem of Array Version
The number of terms is limited to MAX_TERMS. Moreover, if we don’t handle not much terms,
the memory space will be wasted.
2) list_impl.c (Linked List Implementation)
Nodes are “linked” in a linked list, by each node pointing to the next node. When we attach a
term to the end of the list, we can just make the last term node to point the node we attaching.
Benefit of using linked list instead of array is clear. The number of terms is unlimited and no
space is wasted. However there is some cost when allocating new node.
Polynomial addition algorithm is almost same with array version.
3) circular_impl.c (Circular List Implementation)
Circular list is similar with linked list, because nodes are linked. The difference is that the last
node points to the first node. In this way, we can reuse the removed nodes without newly allocating
memory and reduce the cost of memory allocation. However, the test program doesn’t have term
removal feature, so the benefit isn’t pretty significant.
In my implementation of circular list, when poly_new function is called, a new “zero” term will
be returned. Its exponent is -1, which is impossible in polynomial, so we can use it to represent a
zero polynomial.