数据结构实验一：多项式乘法问题

2023-08-06 14:04| 来源: 网络整理| 查看: 265

Exp01 多项式乘法问题

Author: Maskros

实验目的

设计一个一元稀疏多项式简单计算器

实验内容与要求

一元稀疏多项式简单计算器的基本功能是：

（1）输入并建立多项式。

（2）输出多项式，输出形式为整数序列： n , c 1 , e 1 , c 2 , e 2 , . . . , c n , e n n,c_1,e_1,c_2,e_2,...,c_n,e_n n,c1,e1,c2,e2,...,cn,en, 其中 n n n 是多项式的项数， c i c_i ci 和 e i e_i ei 分别是第 i i i 项的系数和指数，序列按指数降序排列。

（3）多项式 a a a 与多项式 b b b 相乘，建立多项式。

实验内容和实验步骤

在这里我们分别通过顺序表和链表两种方法来实现实验要求

大体思路：链表 O ( N 2 ) O(N^2) O(N2)：结构体Pol存储多项式每项的系数和指数CreatePol(Pol *&head)函数用于接收输入的多项式元素，创建一个多项式PrintPol(Pol *&head)函数用于打印多项式MultiPol(Pol *&a, Pol *&b, Pol *&c)函数用于实现多项式的乘法，每次插入一项顺序遍历新链表，按指数升序插入或合并，最后得到以 *c为头结点的链表，即所求结果Getlength(Pol &pol)函数遍历链表返回多项式的项数，用于打印时使用ps：计算出来是空项的判断依据为 pol->c=0 , 故在输出和计算长度时将其直接忽略顺序表 O ( ( l o g N ) 2 ) O((logN)^2) O((logN)2)：使用定义的map类型 typedef map Pol存储多项式每项的系数和指数, key为指数，value为系数，map.size()为多项式项数create()函数用于接收输入的多项式元素，创建一个多项式print(Pol &pol)函数用于打印多项式multi(Pol &p1, Pol &p2)函数用于实现多项式的乘法，完成合并后，返回一个Pol类型的多项式使用map的好处：由于map遍历的特性，不用再次从小到大排序，并且易于查找和合并同类项输入形式：两个多项式，两个整数序列 n , c 1 , e 1 , c 2 , e 2 , . . . , c n , e n n,c_1,e_1,c_2,e_2,...,c_n,e_n n,c1,e1,c2,e2,...,cn,en, 其中 n n n 是多项式的项数， c i c_i ci 和 e i e_i ei 分别是第 i i i 项的系数和指数，序列按指数降序排列输出形式：一个整数序列 n , c 1 , e 1 , c 2 , e 2 , . . . , c n , e n n,c_1,e_1,c_2,e_2,...,c_n,e_n n,c1,e1,c2,e2,...,cn,en，标号规则同上链表实现 //presented by Maskros - 2021/03/31 #include using namespace std; struct Pol{ int c; //coefficient int e; //exponent Pol *next; }; int Getlength(Pol *&head){ //Calculate the number of terms in a polynomial if(head==NULL) {coutc=0; head->e=0; head->next=NULL; Pol *pol=head; int n; cin>>n; for(int i=1;inext=(Pol *) new Pol; pol=pol->next; cin>>pol->c>>pol->e; pol->next=NULL; } return; } void PrintPol(Pol *&head){ //Print polynomial Pol *p=head; int n=Getlength(p); coutnext; t=false; tmpc=p1->c*p2->c; tmpe=p1->e+p2->e; p3=c; pre=c; while(p3->next!=NULL){ p3=p3->next; if(p3->e>tmpe){ //The insertion position is before the current position pre->next=(Pol *)new Pol; pre=pre->next; pre->e=tmpe; pre->c=tmpc; pre->next=p3; t=true; } else if(p3->e==tmpe){ //Combine similar items at current location p3->c+=tmpc; t=true; } else if(p3->next!=NULL && p3->enext->e>tmpe){ //The insertion position is after the current position pre=p3->next; p3->next=(Pol *)new Pol; p3=p3->next; p3->e=tmpe; p3->c=tmpc; p3->next=pre; t=true; } if(t==true) break; pre=p3; } if(t==false){ //Insertion position is at the end of the linked list p3->next=(Pol *)new Pol; p3=p3->next; p3->e=tmpe; p3->c=tmpc; p3->next=NULL; } } } return ; } int main(){ Pol *p1,*p2,*p3; p1=NULL,p2=NULL,p3=NULL; CreatePol(p1); CreatePol(p2); MultiPol(p1,p2,p3); PrintPol(p3); return 0; } 顺序表实现 //presented by Maskros - 2021/03/31 #include using namespace std; typedef map Pol; Pol p1,p2,p3; void create(Pol &pol){ //Create a polynomial int co,ex,n; cin>>n; for(int i=1;i>co>>ex; pol[ex]+=co; } } void print(Pol &pol){ //Print polynomial map::iterator it; cout

【本文地址】

公司简介

联系我们