Merge(M,N); Print(M); }
七、利用指针表示的线性表(链表)表示一个多项式，并实现两个多项式的相加和相乘运算。假设多项式形式为：A(x)?amtem?am?1xem?1e?...?a1x1
其中，系数ai≠0，指数ei满足em>em-1>…>e2>e1>=0。 要求：1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main函数中，构建两个多项式，并测试相加和相乘运算。 #ifndef POLYNOMIAL_H #define POLYNOMIAL_H #include
//链表结构
typedef struct Node{ struct Node *next; double coefficient; int exponent;
} Node, *Polynomial; //链表初始化 void initList(Polynomial *L) { //头结点
if (NULL == *L) {
*L = (Polynomial)malloc(sizeof(Node));
(*L)->coefficient = 0.0; (*L)->exponent = -1;
(*L)->next = NULL; } else
{
cout<<\表已经存在！\ }
} //判断指数同否
int compareExponent(Polynomial nodeA, Polynomial nodeB) {
int a = nodeA->exponent; int b = nodeB->exponent; if (a == b) {
return 0; } else {
return a > b ? 1 : -1; }
} //系数判断
bool isZeroByCoefficient(Polynomial node) {
if (node->coefficient >= -LDBL_EPSILON && node->coefficient <= LDBL_EPSILON) {
return true; } else {
return false; }
} //判断2 //系数判断
bool isZeroByDouble(double a) {
if (a >= -LDBL_EPSILON && a <= LDBL_EPSILON) {
return true; else {
return false; }
} //尾插法建表
void creatListByTail(Polynomial *L, int n) {
//头结点
if (NULL == *L) {
*L = (Polynomial)malloc(sizeof(Node)); (*L)->coefficient = 0.0; (*L)->exponent = -1; (*L)->next = NULL; Polynomial tail = NULL;
Polynomial ptr = *L; //初始化？ if (NULL == (*L)->next) {
Cout<<\请按照指数升幂，连续的输入项的系数（double）和指数（int）：（中间 空格隔开）\循环建表
for (int i = 0; i < n; i++) {
tail = (Polynomial)malloc(sizeof(Node)); tail->next = NULL;
scanf(\
while (getchar() != '\\n') {
continue; }
//链接
ptr->next = tail; //移动指针 ptr = ptr->next; //尾结点 } } else {
Cout<<\表已经建立！\ } } else {
Cout<<\表头已经存在！\ } } //遍历
void traverseList(Polynomial L) {
Polynomial ptr = L->next; int i = 1;
while (ptr != NULL) {
Cout<<\一元多项式的第%d项：%g X ^ %d\\n\
<
i++;
ptr = ptr->next; }
} //求最高阶数
int getMaxExp(Polynomial L) {
Polynomial ptr = L;
while (ptr->next != NULL)
{
ptr = ptr->next; }
return ptr->exponent;
} //删除结点,删除L中ptr指向的结点
void deleteNode(Polynomial L, Polynomial ptr) {
Polynomial p = L;
while (p->next != ptr) {
p = p->next; }
ptr = p->next;
p->next->next = ptr->next; free(ptr);
ptr = NULL; 165 }//多项式相加，本质是链表的归并算法
//可以另外开辟空间，也可以使用已存在的空间存储，这里使用后者的算法 void addPolynomial(Polynomial LA, Polynomial LB) { //不再开辟内存
Polynomial a = LA->next; Polynomial b = LB->next; Polynomial LC = LB; Polynomial tail = LC;
while (a != NULL && b != NULL)
{//判断指数的关系 a > b ? 1 : -1 else 0 switch (compareExponent(a, b)) {
case 1: tail->next = b; tail = tail->next; b = b->next;
break;
case -1: tail->next = a;
tail = tail->next; a = a->next; break; default:
double temp = a->coefficient + b->coefficient;// 0？ if (isZeroByDouble(temp)) {
a = a->next;
b = b->next; //删除
deleteNode(LC, tail->next); } else {
tail->next = b; tail = tail->next;
b->coefficient = temp; a = a->next;
b = b->next; }// end of if }// end of switch }//end of while //一表比完
if (NULL == a) {
tail->next = b; } else {
tail->next = a; }// end of if
free(LA); LA = NULL; }
//多项式相乘
void mulPolynomial(Polynomial LA, Polynomial LB, Polynomial LC) {
Polynomial a = LA->next; Polynomial b = LB->next; Polynomial c = LC;
Polynomial ptr = NULL; //两多项式的阶数
int numA = getMaxExp(LA); int numB = getMaxExp(LB); //结果多项式的阶数
int maxNum = numA + numB; //动态开辟数组空间
double *receive = (double *)malloc((maxNum + 1) * sizeof(double)); //为数组赋值
for (int i = 0; i < maxNum + 1; i++) {