浙江大学数据结构:02-线性结构2 一元多项式的乘法与加法运算 (20分)
数据结构 结构 20 运算 02 线性 乘法 加法
2023-09-14 08:57:14 时间
02-线性结构2 一元多项式的乘法与加法运算 (20分)
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。
输出格式:
输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0
。
输入样例:
4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0
提交代码:
//2020/10/08
#include <stdio.h> #include <stdlib.h> typedef int ElemType; typedef struct PolynomialNode *Poly; struct PolynomialNode{ int Exponent; int Coeff; Poly Next; }; void Attach(int coef, int exp, Poly *rear){ Poly poly = (Poly)malloc(sizeof(struct PolynomialNode)); poly->Exponent = exp; poly->Coeff = coef; poly->Next = NULL; (*rear)->Next = poly; (*rear) = poly; } Poly ReadPoly(){ Poly pHead = (Poly)malloc(sizeof(struct PolynomialNode)); Poly pPre = pHead; int exp; int coef; int N; scanf("%d", &N); for(int i = 0; i < N; ++i){ scanf("%d %d", &coef, &exp); Attach(coef, exp, &pPre); } Poly pTemp = pHead; pHead = pHead->Next; free(pTemp); return pHead; } Poly Add(Poly poly1, Poly poly2){ Poly pHead = (Poly)malloc(sizeof(struct PolynomialNode)); pHead->Next = NULL; Poly pPre = pHead; Poly p1 = poly1; Poly p2 = poly2; int coef = 0; while(p1 && p2){ if(p1->Exponent == p2->Exponent){ coef = p1->Coeff + p2->Coeff; if(coef != 0){ Attach(coef, p1->Exponent, &pPre); } p1 = p1->Next; p2 = p2->Next; } else if(p1->Exponent > p2->Exponent){ Attach(p1->Coeff, p1->Exponent, &pPre); p1 = p1->Next; } else{ Attach(p2->Coeff, p2->Exponent, &pPre); p2 = p2->Next; } } while(p1){ Attach(p1->Coeff, p1->Exponent, &pPre); p1 = p1->Next; } while(p2){ Attach(p2->Coeff, p2->Exponent, &pPre); p2 = p2->Next; } Poly pTemp = pHead; pHead = pHead->Next; free(pTemp); return pHead; } Poly Multiple(Poly poly1, Poly poly2){ if(!poly1||!poly2){ return NULL; } Poly pHead = (Poly)malloc(sizeof(struct PolynomialNode)); pHead->Next = NULL; Poly pPre = pHead; Poly p1 = poly1; Poly p2 = poly2; int e,c; while(p2){ Attach(p1->Coeff*p2->Coeff, p1->Exponent+p2->Exponent, &pPre); p2 = p2->Next; } p1 = p1->Next; while(p1){ p2 = poly2; pPre = pHead; while(p2){ e = p1->Exponent + p2->Exponent; c = p1->Coeff*p2->Coeff; while(pPre->Next&&pPre->Next->Exponent > e) pPre = pPre->Next; if(pPre->Next && pPre->Next->Exponent == e){ if(pPre->Next->Coeff + c){ pPre->Next->Coeff +=c; } else{ Poly temp = pPre->Next; pPre->Next = temp->Next; free(temp); } } else{ Poly temp = (Poly)malloc(sizeof(struct PolynomialNode)); temp->Coeff = c; temp->Exponent = e; temp->Next = pPre->Next; pPre->Next = temp; pPre = pPre->Next; } p2 = p2->Next; } p1 = p1->Next; } p2 = pHead; pHead = pHead->Next; free(p2); return pHead; } void PrintPoly(Poly p){ if(!p){ printf("0 0\n"); return; } printf("%d %d", p->Coeff, p->Exponent); p = p->Next; while(p){ printf(" %d %d", p->Coeff, p->Exponent); p = p->Next; } printf("\n"); } int main(){ //读取第一个多项式; Poly poly1 = ReadPoly(); //读取第二个多项式; Poly poly2 = ReadPoly(); Poly polyProduct = Multiple(poly1, poly2); PrintPoly(polyProduct); Poly polySum = Add(poly1, poly2); PrintPoly(polySum); return 0; }
2021/07/04
#include <stdlib.h> #include <stdio.h> typedef struct Poly *PtrPoly; struct Poly{ int coeff;//系数 int expo;//指数 PtrPoly next; }; PtrPoly NewPoly(int nCoeff, int nExpo){ PtrPoly p = (PtrPoly)malloc(sizeof(struct Poly)); p->coeff = nCoeff; p->expo = nExpo; p->next = NULL; return p; } PtrPoly ReadPoly(){ int nPolyLen = 0; scanf("%d",&nPolyLen); //构建头节点 PtrPoly pHead = NewPoly(0,0); PtrPoly p = pHead; int c = 0; int e = 0; for(int i = 0; i < nPolyLen; ++i){ scanf("%d %d", &c, &e); p->next = NewPoly(c, e); p = p->next; } return pHead; } void CopyNode(PtrPoly* pDst, PtrPoly* pSrc){ (*pDst)->next = NewPoly((*pSrc)->coeff, (*pSrc)->expo); *pDst = (*pDst)->next; *pSrc = (*pSrc)->next; } PtrPoly Add(PtrPoly p1, PtrPoly p2){ //构建多项式链表头节点 PtrPoly pHead = NewPoly(0,0); PtrPoly p = pHead; p1 = p1->next; p2 = p2->next; while(p1 && p2){ if(p1->expo == p2->expo){ if(p1->coeff + p2->coeff == 0){ p1 = p1->next; p2 = p2->next; } else{ p->next = NewPoly(p1->coeff + p2->coeff, p1->expo); p = p->next; p1 = p1->next; p2 = p2->next; } } else if(p1->expo > p2->expo){ CopyNode(&p, &p1); } else{ CopyNode(&p, &p2); } } while(p1){ CopyNode(&p, &p1); } while(p2){ CopyNode(&p, &p2); } return pHead; } void AddNode(PtrPoly pHead, int c, int e) { PtrPoly front = pHead; PtrPoly p = pHead->next; while(p){ if(p->expo == e){ if((p->coeff + c) == 0){ PtrPoly tmp = p; front->next = p->next; free(tmp); return; } else{ p->coeff += c; return; } } else if (p->expo < e){ PtrPoly tmp = NewPoly(c, e); front->next = tmp; tmp->next = p; return; } front = p; p = p->next; } front->next = NewPoly(c, e); } PtrPoly Multiply(PtrPoly pHead1, PtrPoly pHead2){ PtrPoly product = NewPoly(0,0); PtrPoly p1 = pHead1->next; while(p1){ PtrPoly p2 = pHead2->next; while(p2){ AddNode(product, p1->coeff*p2->coeff, p1->expo+p2->expo); p2 = p2->next; } p1 = p1->next; } return product; } void PrintPoly(PtrPoly p) { if(!p->next){ printf("0 0"); } else{ p = p->next; printf("%d %d",p->coeff, p->expo); while(p->next){ p = p->next; printf(" %d %d", p->coeff, p->expo); } } printf("\n"); } int main() { PtrPoly poly1 = ReadPoly(); PtrPoly poly2 = ReadPoly(); PtrPoly sum = Add(poly1, poly2); PtrPoly product = Multiply(poly1, poly2); PrintPoly(product); PrintPoly(sum); return 0; }
提交结果:
相关文章
- 数据结构完全二叉树性质
- 常见数据结构-特殊操作
- 数据结构之线性结构和非线性结构介绍
- mysql查看表的数据结构_mysql查找表结构
- 数据结构视频教程哪个好[通俗易懂]
- 数据结构–线性结构专题
- 数据结构:图结构
- 数据结构:线性结构
- 哈夫曼树 编码-【数据结构】树形结构——哈夫曼编码
- 【数据结构-二叉树】堆(Heap)
- 【数据结构】线性表代码实现:顺序存储结构 | 链式存储结构
- 数据结构与算法:鸡蛋问题
- 【Linux 内核 内存管理】内存映射相关数据结构 ② ( vm_area_struct 结构体成员分析 | vm_mm 成员 | vm_page_prot 成员 | vm_flags 成员 )
- [数据结构]二叉树的顺序存储结构
- PNG文件解读(2):PNG格式文件结构与数据结构解读—解码PNG数据
- 浅谈redis五大数据结构和使用场景
- Java数据结构学习笔记之二Java数据结构与算法之栈(Stack)实现详解编程语言
- 据结构 Linux下实现高效的并发数据结构(linux并发数)
- Oracle 集合:多元数据结构实现多样化存储(oracle集合)
- 深入了解:Redis数据库的数据结构(redis数据库结构)
- 如何导入MSSQL数据结构?(导入mssql数据和结构)
- 形结构SQL Server查询树形数据结构的技巧分析(sqlserver查询树)
- MSSQL:查询数据库结构的快速方法(mssql 查询数据结构)
- 三国杀查询Redis的数据结构与存储(三国杀查询redis)
- 结构的运用Oracle数据库中强大的树形数据结构应用(oracle中树形数据)
- 结构Redis面试深入理解数据结构(redis面试中的数据)
- Redis评论灵活的数据结构(redis评论什么结构)