南邮数据结构实验1.5：一元多项式的相加和相乘
题目：编写程序实现一元多项式的创建、输出、撤销以及两个一元多项式相加和相乘的操作。
部分代码：
带表头结点一元多项式的结构体定义：
typedef struct PNode{
int coef; //系数
int exp; //指数
struct PNode* link;
}PNode;
typedef struct{
struct PNode *head;
}polynominal; 一元多项式的创建：
//多项式的创建
void Create(polynominal *p){
PNode *pn,*pre,*q;
p->head = (PNode*)malloc(sizeof(PNode));
p->head->exp = -1;
p->head->link = p->head; //对教材做了修改
//p->head->link = NULL; //教材原代码
for(;;){
pn=(PNode*)malloc(sizeof(PNode));
printf("coef:\n");
scanf("%d",&pn->coef);
printf("exp:\n");
scanf("%d",&pn->exp);
if(pn->exp<0) break;
pre = p->head;
q = p->head->link;
while(q && q->exp > pn->exp){
pre = q;
q = q->link;
}
pn->link = q;
pre->link = pn;
}
} 多项式的输出：
//多项式输出
void Output(polynominal p){
PNode *q;
int flag = 1; //打标记,记录是否为第一项
q = p.head->link;
if (!q){
return;
}
while(q != p.head){
if (!flag && (q->coef > 0)) printf("+"); //在非第一项的正系数前输出+号
flag = 0; //flag置为0,表示不是第一项
if(q->coef == 0){ //当前项系数为0
return;
}
printf("%d",q->coef); //当前项系数不为0
switch(q->exp){ //判断当前项指数
case 0:break; //当前项指数为0,退出
case 1:printf("X");break; //当前项指数为1,输出X
default:printf("X^%d",q->exp);break; //当前项指数不为0,也不为1
}
q = q->link;
}
} 多项式的相加：
教材上的代码：
//多项式加法,书上的原代码,有问题
void Add(polynominal *px,polynominal *qx){
PNode *q,*q1 = qx->head,*p,*temp;
p = px->head->link;
q = q1->link;
while(p&&q){
while(p->exp < q->exp){
q1 = q;
q = q->link;
}
if(p->exp == q->exp){
q->coef = q->coef + p->coef;
if(q->coef == 0){
q1->link = q->link;
free(q);
q = q1->link;
p = p->link;
}
else{
q1 = q;
q = q->link;
p = p->link;
}
}
else{
temp = (PNode*)malloc(sizeof(PNode));
temp->coef = p->coef;
temp->exp = p->exp;
temp->link = q1->link;
q1->link = temp;
p = p->link;
}
}
} 对教材进行修改后的代码：
//多项式的相加,结果存入qx中
void Add(polynominal *px,polynominal *qx){
PNode *q,*q1 = qx->head,*p, *p1,*temp; //q1指向qx的表头结点
p = px->head->link; //p指向多项式px的第一个结点
p1 = px->head;
q = q1->link; //q1是q的前驱
while(p->exp >= 0){
while(p->exp < q->exp){ //跳过q->exp大的项
q1 = q;
q = q->link;
}
if(p->exp == q->exp){ //当指数相等时,系数相加
q->coef = q->coef + p->coef;
if(q->coef == 0){ //若相加后系数为0
q1->link = q->link; //删除q
free(q); //释放q的空间
q = q1->link; //重置q指针
p = p->link;
}
else{ //若相加后系数不为0
q1 = q; //q1后移
q = q->link;
p = p->link; //p也后移
}
}
else{ //p->exp > q->exp的情况
temp = malloc(sizeof(PNode)); //以p的系数和指数生成新结点
temp->coef = p->coef;
temp->exp = p->exp;
temp->link = q1->link;
q1->link = temp;
q1 = q1->link;
p = p->link;
}
}
} 多项式乘法：
//多项式乘法,暂时没有问题
void Multiply(polynominal *px,polynominal *qx){
polynominal qx1,qx2;
PNode *q1,*q2,*q3,*q4,*pre,*q;
qx1.head = (PNode*)malloc(sizeof(PNode)); //生成新多项式qx1
qx1.head->exp = -1;
qx1.head->link = qx1.head; //qx1改造成循环链表
q1 = px->head->link; //q1指向px的第一项
q2 = qx->head->link; //q2指向qx的第一项
while(q2->exp != -1){ //当q2的指数不为-1时,px先和qx的每一项相乘
q3 = (PNode*)malloc(sizeof(PNode)); //q3存放相乘的结果
q3->coef = q1->coef * q2->coef;
q3->exp = q1->exp + q2->exp;
if(qx1.head->link->exp == -1){ //q3插入到qx1多项式第一项中
q3->link = qx1.head->link;
qx1.head->link = q3;
pre = qx1.head->link;
}
else{ //q3插入到qx1多项式最后一项中
q3->link = qx1.head;
pre->link = q3;
pre = pre->link;
}
q2 = q2->link;
}
q1 = q1->link; //q1后移一位
while(q1->exp != -1){ //px剩下来每一项都和qx每一项相乘
q2 = q2->link;
qx2.head = (PNode*)malloc(sizeof(PNode)); //生成新多项式qx2
qx2.head->exp = -1;
qx2.head->link = qx2.head;
while(q2->exp != -1){
q4 = (PNode*)malloc(sizeof(PNode));
q4->coef = q1->coef * q2->coef;
q4->exp = q1->exp + q2->exp;
if(qx2.head->link->exp == -1){
q4->link = qx2.head->link;
qx2.head->link = q4;
pre = qx2.head->link;
}
else{
q4->link = qx2.head;
pre->link = q4;
pre = pre->link;
}
q2 = q2->link;
}
Add(&qx2,&qx1); //合并同类项
q1 = q1->link;
}
Output(qx1);
} 完整代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct PNode{
int coef; //系数
int exp; //指数
struct PNode* link;
}PNode;
typedef struct{
struct PNode *head;
}polynominal;
//多项式的创建
void Create(polynominal *p){
PNode *pn,*pre,*q;
p->head = (PNode*)malloc(sizeof(PNode));
p->head->exp = -1;
p->head->link = p->head; //对教材做了修改
//p->head->link = NULL; //教材原代码
for(;;){
pn=(PNode*)malloc(sizeof(PNode));
printf("coef:\n");
scanf("%d",&pn->coef);
printf("exp:\n");
scanf("%d",&pn->exp);
if(pn->exp<0) break;
pre = p->head;
q = p->head->link;
while(q && q->exp > pn->exp){
pre = q;
q = q->link;
}
pn->link = q;
pre->link = pn;
}
}
//多项式输出
void Output(polynominal p){
PNode *q;
int flag = 1; //打标记,记录是否为第一项
q = p.head->link;
if (!q){
return;
}
while(q != p.head){
if (!flag && (q->coef > 0)) printf("+"); //在非第一项的正系数前输出+号
flag = 0; //flag置为0,表示不是第一项
if(q->coef == 0){ //当前项系数为0
return;
}
printf("%d",q->coef); //当前项系数不为0
switch(q->exp){ //判断当前项指数
case 0:break; //当前项指数为0,退出
case 1:printf("X");break; //当前项指数为1,输出X
default:printf("X^%d",q->exp);break; //当前项指数不为0,也不为1
}
q = q->link;
}
}
//多项式的相加,结果存入qx中
void Add(polynominal *px,polynominal *qx){
PNode *q,*q1 = qx->head,*p, *p1,*temp; //q1指向qx的表头结点
p = px->head->link; //p指向多项式px的第一个结点
p1 = px->head;
q = q1->link; //q1是q的前驱
while(p->exp >= 0){
while(p->exp < q->exp){ //跳过q->exp大的项
q1 = q;
q = q->link;
}
if(p->exp == q->exp){ //当指数相等时,系数相加
q->coef = q->coef + p->coef;
if(q->coef == 0){ //若相加后系数为0
q1->link = q->link; //删除q
free(q); //释放q的空间
q = q1->link; //重置q指针
p = p->link;
}
else{ //若相加后系数不为0
q1 = q; //q1后移
q = q->link;
p = p->link; //p也后移
}
}
else{ //p->exp > q->exp的情况
temp = malloc(sizeof(PNode)); //以p的系数和指数生成新结点
temp->coef = p->coef;
temp->exp = p->exp;
temp->link = q1->link;
q1->link = temp;
q1 = q1->link;
p = p->link;
}
}
}
//多项式乘法,暂时没有问题
void Multiply(polynominal *px,polynominal *qx){
polynominal qx1,qx2;
PNode *q1,*q2,*q3,*q4,*pre,*q;
qx1.head = (PNode*)malloc(sizeof(PNode)); //生成新多项式qx1
qx1.head->exp = -1;
qx1.head->link = qx1.head; //qx1改造成循环链表
q1 = px->head->link; //q1指向px的第一项
q2 = qx->head->link; //q2指向qx的第一项
while(q2->exp != -1){ //当q2的指数不为-1时,px先和qx的每一项相乘
q3 = (PNode*)malloc(sizeof(PNode)); //q3存放相乘的结果
q3->coef = q1->coef * q2->coef;
q3->exp = q1->exp + q2->exp;
if(qx1.head->link->exp == -1){ //q3插入到qx1多项式第一项中
q3->link = qx1.head->link;
qx1.head->link = q3;
pre = qx1.head->link;
}
else{ //q3插入到qx1多项式最后一项中
q3->link = qx1.head;
pre->link = q3;
pre = pre->link;
}
q2 = q2->link;
}
q1 = q1->link; //q1后移一位
while(q1->exp != -1){ //px剩下来每一项都和qx每一项相乘
q2 = q2->link;
qx2.head = (PNode*)malloc(sizeof(PNode)); //生成新多项式qx2
qx2.head->exp = -1;
qx2.head->link = qx2.head;
while(q2->exp != -1){
q4 = (PNode*)malloc(sizeof(PNode));
q4->coef = q1->coef * q2->coef;
q4->exp = q1->exp + q2->exp;
if(qx2.head->link->exp == -1){
q4->link = qx2.head->link;
qx2.head->link = q4;
pre = qx2.head->link;
}
else{
q4->link = qx2.head;
pre->link = q4;
pre = pre->link;
}
q2 = q2->link;
}
Add(&qx2,&qx1); //合并同类项
q1 = q1->link;
}
Output(qx1);
}
int main(){
polynominal p,q;
int x;
printf("Please enter the first poly:\n");
Create(&p);
Output(p);
printf("\n\nPlease enter the second poly:\n");
Create(&q);
Output(q);
printf("\n\nPlease choose the function:\n");
scanf("%d",&x);
switch(x){ //选择加法还是乘法功能
case 0:printf("Add:\n");
Add(&p,&q);
Output(q);
break;
case 1:printf("Multiply:\n");
Multiply(&p,&q);
default:break;
}
return 0;
} 实验结果：
加法：
乘法：
版权声明：本文为博主原创文章，未经博主允许不得转载。
谷歌公司福利 178人发布
查看2道真题和解析
投递华为等公司10个岗位