链表实现多项式相乘<线性表>

初学数据结构,我这个菜鸟 没看教程完全自己想. 这个题做好了好久. 不过还好总于做出来了. 

　　先上代码,代码里有注释. 可以把注释变为cout<<注释  看一下向乘的过程.

　　　　后面再做详细的补充说明

问题描述 :

　　输入两个多项式,多项式的第一个数是项数.后续是两两一对,一个系数,一个指数. 多项式有序,按照系数的降序. 通过单链表实现两个多项式相乘. 输出结果多项式.同样第一项为项的个数, 后续安装指数降序排列.

要通过链表实现.

解决思路:

　　初始时把两个多项式的第一项存下来,这就是结果多项式的第一项.因为有序的原因,后面的都没有这一项的指数大,因此不用考虑这一项的本位相加和向前插入.之后遍历链表每一项,三个基本过程,本位相加,向前插入,向后插入.就实现了,两个多项式相乘,这个新构建的链表就是结果多项式.

上代码:

 1 #include<iostream>  2 #define ends " "; //linux ends不输出  3 using namespace std;  4  5 typedef struct polynomial  6 {  7 int coef; //项的系数  8 int index; //指数  9 polynomial * next;  10 }term,*pTerm;  11  12 pTerm creatterm();  13 void showterm(pTerm);  14 pTerm mult(pTerm,pTerm);  15  16 int main(){  17  pTerm term1,term2,termAns;  18 term1=creatterm();  19 term2=creatterm();  20 cout<<"输入的两个多项式分别是："<<endl;  21  showterm(term1);  22  showterm(term2);  23 cout<<"结果是："<<endl;  24 termAns=mult(term1,term2);  25  showterm(termAns);  26 return 0;  27 }  28 //建立多项式  29 pTerm creatterm(){  30 int val,m,c,f;  31  pTerm phead, ptail;  32 phead = (pTerm)malloc(sizeof(term));  33 ptail=phead;  34 ptail->next=NULL;  35 cout<<"输入多项式的项数：";  36 cin>>m;  37 for(int i=0;i<m;i++){  38 cin>>c>>f;  39 pTerm pnew=(pTerm)malloc(sizeof(term));  40 pnew->coef=c;  41 pnew->index=f;  42 ptail->next=pnew;  43 pnew->next=NULL;  44 ptail=pnew;  45  }  46 phead->coef=m;  47 return phead;  48 }  49 //显示多项式的值  50 void showterm(pTerm phead){  51  pTerm p;  52 p=phead->next;  53 while(p!=NULL){  54 cout<<p->coef <<" "<< p->index<<" ";  55 p=p->next;  56  }  57 cout<<endl;  58 }  59 //多项式相乘  60 pTerm mult(pTerm t1,pTerm t2){  61 pTerm p1,p2,p,pre,phead;//第一个多项式 第二个多项式 工作节点指向当前的比较项 p的前一项 头节点  62 int n=1; //项数  63 //分配空间  64 p=(pTerm)malloc(sizeof(term));  65 pre=(pTerm)malloc(sizeof(term));  66 phead=(pTerm)malloc(sizeof(term));  67 p1=t1->next; //第一个多项式的第一项  68 p2=t2->next; //第二个多项式的第一项  69 //p初始化为第一项  70 p->coef=p1->coef*p2->coef;  71 p->index=p1->index+p2->index;  72 p->next=NULL;  73 pre->next=p;  74 phead->next=p;  75 //循环遍历处理每一项  76 while(p1!=NULL){  77 p2=t2->next;  78 while(p2!=NULL){  79 p=phead->next;  80 pTerm pnew=(pTerm)malloc(sizeof(term));  81 pnew->coef=p1->coef*p2->coef;  82 pnew->index=p1->index+p2->index;  83 pnew->next=NULL;  84 for(int i=0;i<t1->coef*t2->coef;i++)  85  {  86 if(p->index==pnew->index){ //本位相加  87 if(n==1) break; //第一项已有直接退出循环  88 else{p->coef+=pnew->coef;  89 n++;  90 break;}  91 }else if(p->index>pnew->index){  92 pre=p;  93 if(p->next==NULL) { //向后插入  94 p->next=pnew;  95 n++;  96 break;  97  }  98 else p=p->next;  99 }else if(p->index<pnew->index) { //向前插入 100 pre->next=pnew; 101 pnew->next=p; 102 pre=pnew; 103 n++; 104 break; 105  } 106  } 107 p2=p2->next; //p2移动 108  } 109 p1=p1->next; //p1移动 110  } 111 cout<<n<<" "; //输出项数 112 return phead; 113 }