The following rules should be observed throughout the assignment: • Each polynom
ID: 3861347 • Letter: T
Question
The following rules should be observed throughout the assignment:
• Each polynomial should be represented as a singly-linked list (see files “list.h” and “list.c” from the book).
• Each element in the linked list should represent one of the terms in the polynomial.
• The data held by each element should be type double representing the constant for that term.
• For example, the polynomial 6.0x3 - 5.3x + 3.1 would be represented by the linked list 6.0 0.0 -5.3 3.1.
a) (1 point) Implement a function called appendTerm:
void appendTerm(List *pPolynomial, double constant);
This function should append (insert at the end) the value constant to pPolynomial. For example, appending 3.1 to pPolynomial already containing 6.0 0.0 -5.3 should result in the value 3.1 being added at the end: 6.0 0.0 -5.3 3.1. If the append fails the program should exit.
b) (2 points) Implement a function called display:
void display(List *pPolynomial);
This function should output the polynomial to stdout in proper polynomial format. For example, displaying polynomial 6.0 0.0 -5.3 3.1 should result in 6.0x^3 - 5.3x + 3.1 being output.
c) (2 points) Implement a function called evaluate:
double evaluate(List *pPolynomial, double x);
This function should evaluate the polynomial for the given value of x and return the result. For example, given polynomial 6.0 0.0 -5.3 3.1 and x having value 7.0 the function should return 2024.0 (the result of evaluating 6.0*7.03 - 5.3*7.0 + 3.1).
d) (4 points) Write a program to test the functions from parts a – c. Your test program should demonstrate creating, displaying, and evaluating the following polynomials with the given values for x:
• x + 1.0 with x = 1.0
• x 2 - 1.0 with x = 2.03
• -3.0x3 + 0.5x2 - 2.0x with x = 05.0
• -0.3125x4 - 9.915x2 - 7.75x - 40.0 with x = 123.45
e. (1 point) Make sure your source code is well-commented, consistently formatted, uses no magic numbers/values, follows programming best-practices, and is ANSI-compliant.
#LIST.H FILE#
#LIST.C FILE#
Explanation / Answer
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include <stdlib.h>
/*
* Singly-linked list element
*/
typedef struct ListElmt_
{
void *data;
struct ListElmt_ *next;
} ListElmt;
/*
* Singly-linked list
*/
typedef struct List_
{
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
ListElmt *head;
ListElmt *tail;
} List;
/*
* Public interface
*/
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);
void appendTerm(List* pPolynomial, double constant);
void display(List* pPolynomial);
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)
#endif // LIST_H_INCLUDED
#include <stdlib.h>
#include <string.h>
#include<stdio.h>
#include "list.h"
void list_init(List *list, void (*destroy)(void *data)) {
/* Initialize the list */
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;
}
void list_destroy(List *list)
{
void *data;
/* Remove each element */
while (list_size(list) > 0) {
if (list_rem_next(list, NULL, (void **)&data) == 0 && list->destroy !=
NULL) {
/* Call a user-defined function to free dynamically allocated
data. */
list->destroy(data);
}
}
/* No operations are allowed now, but clear the structure as a
precaution. */
memset(list, 0, sizeof(List));
}
int list_ins_next(List *list, ListElmt *element, const void *data)
{
ListElmt *new_element;
/* Allocate storage for the element. */
if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
return -1;
/* Insert the element into the list. */
new_element->data = (void *)data;
if (element == NULL) {
/* Handle insertion at the head of the list. */
if (list_size(list) == 0)
list->tail = new_element;
new_element->next = list->head;
list->head = new_element;
}
else {
/* Handle insertion somewhere other than at the head. */
if (element->next == NULL)
list->tail = new_element;
new_element->next = element->next;
element->next = new_element;
}
/* Adjust the size of the list to account for the inserted element. */
list->size++;
return 0;
}
int list_rem_next(List *list, ListElmt *element, void **data)
{
ListElmt *old_element;
/* Do not allow removal from an empty list. */
if (list_size(list) == 0)
return -1;
/* Remove the element from the list. */
if (element == NULL) {
/* Handle removal from the head of the list. */
*data = list->head->data;
old_element = list->head;
list->head = list->head->next;
if (list_size(list) == 1)
list->tail = NULL;
}
else {
/* Handle removal from somewhere other than the head. */
if (element->next == NULL)
return -1;
*data = element->next->data;
old_element = element->next;
element->next = element->next->next;
if (element->next == NULL)
list->tail = element;
}
/* Free the storage allocated by the abstract data type. */
free(old_element);
/* Adjust the size of the list to account for the removed element. */
list->size--;
return 0;
}
void appendTerm(List* pPolynomial, double constant)
{
ListElmt *newterm;
double pd=&constant;
/*allocate space for the new term*/
if ((newterm = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
return;
newterm->data=(void*)constant; /*fill data in the new term*/
newterm->next=NULL;
pPolynomial->tail->next=newterm; /*append the new term to the polynomial*/
pPolynomial->tail=newterm;
(pPolynomial->size)++;
}
void display(List *pPolynomial)
{
int power, neg_flag=0; /*neg_flag is used to handle when plus sign is to be displayed*/
ListElmt *temp;
temp=pPolynomial->head;
power=(pPolynomial->size)-1;
while(power>=0)
{
if(temp->data!=0)/*display only non-zero terms*/
{
if(temp!=pPolynomial->head) /*if term is not the first term*/
if(neg_flag==0) /*if the term is not negative*/
printf(" + "); /*display the + sign before displaying the term*/
printf("%D",temp->data); /*show the data*/
printf("x");
if(power>0) /*decide whether or not the term is a constant*/
printf("x");
if(power>1) /*decide whether or not the power is to be shown*/
printf("^%d",power);
}
temp=temp->next;
power--;
if(temp!=NULL)
if(temp->data<0)
neg_flag=1; /*set negative flag if next term to be displayed is negative*/
}
printf(" ");
}
double evaluate(List *pPolynomial, double x)
{
double sum=0;
ListElmt *temp;
int power,i;
temp=pPolynomial->head;
power=(pPolynomial->size)-1;
while(power>=0)
{
for(i=1;i<power;i++) /*get value of x to the power of the term*/
x*=x;
sum=sum+((temp->data) * x); /*multiply x with the constant part of the term and add it to sum*/
temp=temp->next;
power--;
}
return sum;
}
/*main.c*/
#include <stdio.h>
int main()
{
List *poly1,*poly2,*poly3,*poly4;
ListElmt *temp;
/*polynomial:- x+1.0*/
list_init(poly1); /*create the polynomial*/
list_ins_next(poly1,temp,1.0);
list_ins_next(poly1,temp,1.0);
display(poly1); /*display the polynomial*/
printf("The value of the polynomial when x=1.0 is %D ",evaluate(poly1,1.0)); /*display its value*/
/*polynomial:- x^2-1.0*/
list_init(poly2); /*create the polynomial*/
list_ins_next(poly2,temp,1.0);
list_ins_next(poly2,temp,0.0);
list_ins_next(poly2,temp,-1.0);
display(poly2); /*display the polynomial*/
printf("The value of the polynomial when x=2.03 is %D ",evaluate(poly2,2.03)); /*display its value*/
/*polynomial:- -3.0x^3+0.5x^2-2.0x*/
list_init(poly3); /*create the polynomial*/
list_ins_next(poly3,temp,-3.0);
list_ins_next(poly3,temp,0.5);
list_ins_next(poly3,temp,-2.0);
list_ins_next(poly3,temp,-0.0);
display(poly3); /*display the polynomial*/
printf("The value of the polynomial when x=05.0 is %D ",evaluate(poly3,5.0)); /*display its value*/
/*polynomial:- -0.3125x^4 - 9.915x^2 - 7.75x - 40.0 with x = 123.45*/
list_init(poly4); /*create the polynomial*/
list_ins_next(poly4,temp,-0.3125);
list_ins_next(poly4,temp,0.0);
list_ins_next(poly4,temp,-9.915);
list_ins_next(poly4,temp,-7.75);
list_ins_next(poly4,temp,-40.0);
display(poly4); /*display the polynomial*/
printf("The value of the polynomial when x=123.45 is %D ",evaluate(poly4,123.45)); /*display its value*/
list_destroy(poly1);
list_destroy(poly2);
list_destroy(poly3);
list_destroy(poly4);
return 0;
}