单链表实现多项式相加

矫情吗；* 2022-05-06 11:29 276阅读 0赞

> 这个小项目用C语言实现  
> 代码中有我的注释

思路：  
**用链表的每个节点存储表达式的每一项，因此每个链表就是一个表达式**

链表节点类型的定义：

struct Node{ 
    	DataType _elem; //项的系数
    	Variate _ch;//常量和变量的标志（规定如果为'#'，则该节点为常量项，否则为变量项，_ch为变量）
    	int _power;//变量的次数（规定常量的次数只能为1）
    };

相加逻辑：项类型相同并且系数相同的项可以相加，否则不能相加。eg：

exp1: `3x^3 + 1`  
exp2: `5x^3 + x^2 + 9`  
第一个表达式的`3x^3`和第二个表达式的`5x^3`可以相加，因为他们都含有变量，并且变量的系数相同。

所以，我们可以拿着依次拿着第一个链表中的节点去遍历第二个链表，在第二个链表中查找类型相同（即可以相加）的项，如果找到，则将两个节点（第一个链表中的当前节点和第二个节点中找到的目标节点）的系数相加并插入到新的链表（即相加后的新表达式）：  
![在这里插入图片描述][70]

如果在第二个链表中没有找到和链表1当前节点类型相同的节点，则将链表1的当前节点直接插入到新链表中：  
![在这里插入图片描述][70 1]

当链表1已经走完了后（所有的节点都分别在链表2中查找过），此时得到的新表达式还不是最终的结果，因为有可能会有这种情况：  
![在这里插入图片描述][70 2]

这种情况的处理办法是这样的，依次拿着第二个链表中的节点遍历新链表，只要是类型相同的，则说明已经添加过。反之，说明该节点还没有添加到新链表中。

> 有人可能会疑惑表达式的运算符如何存储？如何表示？
> 
> 这里我是这样设计的：这个程序只是为了让我们熟悉链表这种数据结构，所以我从简考虑，只支持 + / - 两种运算符，那么就容易了，如果系数是正数，那么在打印表达式的时候，在该项前面打印一个 ‘**+**’；如果是系数是负数，那么不用打印，因为负数的符号就可以代表运算符了。具体操作可以参见代码，代码中我附上了注释。

代码：

//mylist.h
    #pragma once
    
    typedef int DataType;
    typedef char Variate;
    
    
    typedef struct Node{ 
      DataType _elem; //项的系数
      Variate _ch;  //规定'#'表示此项为常数项
      int _power; //项的次方
      struct Node* _next;
    }Node, *PNode;
    
    //初始化链表
    void ListInit(PNode* head);
    //添加节点
    //--返回值说明--
    //1 :成功
    //0 :失败
    int ListAdd(PNode* head, DataType elem, Variate ch, int Power);

//mylist.c
    #include <stdio.h>
    #include <assert.h>
    #include "mylist.h"
    
    //初始化链表
    void ListInit(PNode* head){ 
      assert(head);
      *head = NULL;
    }
    //添加节点
    int ListAdd(PNode* head, DataType elem, Variate ch, int Power){ 
      assert(head);
      if(NULL == *head){ 
        *head = (PNode)malloc(sizeof(Node));
        (*head)->_elem = elem;
        (*head)->_ch = ch;
        (*head)->_power = Power;
        (*head)->_next = NULL;
      }else{ 
        PNode tmp = *head;
        while(tmp->_next != NULL){ 
          tmp = tmp->_next;
        }
        tmp->_next = (PNode)malloc(sizeof(Node));
        tmp->_next->_elem = elem;
        tmp->_next->_ch = ch;
        tmp->_next->_power = Power;
        tmp->_next->_next = NULL;
      }
      return 1;
    }

//main.c
    #include <stdio.h>
    #include "mylist.c"
    
    /* * 1. 规定只能表达式只能计算 +/- 运算 * 2. 规定常数项的次数只能是1 */
    
    void ExpressionPrint(PNode list){ 
      assert(list);
      PNode tmp = list;
      while(tmp != NULL){ 
      	//如果当前项系数大于零且不为表达式首项，打印加号（注意格式控制，加号前有空格）
        if(tmp->_elem > 0 && tmp != list){ 
          printf(" +");
        }
        //如果变量的次数不为1
        if(tmp->_ch != '#' && tmp->_power != 1){ 
          printf(" %d%c^%d", tmp->_elem, tmp->_ch, tmp->_power);
        }//如果变量的次数为1，则不打印该项变量的次数
        else if(tmp->_ch != '#' && tmp->_power == 1){ 
          printf(" %d%c", tmp->_elem, tmp->_ch);
        }//输出常量
        else if(tmp->_ch == '#'){ 
          printf(" %d", tmp->_elem);
        }
        tmp = tmp->_next;
      }//end while(tmp != NULL)
      printf("\n");
    }
    
    PNode ExpressionAdd(PNode list1, PNode list2){ 
      if(list1 == NULL){ 
        return list2;
      }
      if(list2 == NULL){ 
        return list1;
      }
      //拿着链表1中的项遍历链表2中的项
      PNode tmp1 = list1;
      PNode tmp2 = list2;
      PNode new_list;
      ListInit(&new_list);//一定不能忘记初始化链表！
      while(tmp1 != NULL){ 
        while(tmp2 != NULL){ 
          //如果链表1当前项和链表2项匹配，则将两者的系数相加并添加到新链表
          if(tmp1->_ch == tmp2->_ch && tmp1->_power == tmp2->_power){ 
            ListAdd(&new_list, tmp1->_elem + tmp2->_elem, 
            		tmp1->_ch, tmp1->_power);
            break;
          }
          tmp2 = tmp2->_next;
        }//end while(tmp2 != NULL)
        //如果没找到相同类型的项，则将链表1中的项添加到新链表中
        if(NULL == tmp2){ 
          ListAdd(&new_list, tmp1->_elem, tmp1->_ch, tmp1->_power);
        }//end while(tmp1 != NULL)
        tmp1 = tmp1->_next;//指向链表1的指针向后走
        tmp2 = list2;//让指向链表2的指针重新指向链表2的头部
      }
      PNode tmp3 = new_list;
      //将链表2中没有添加到新链表中的项找出来添加到新链表
      while(tmp2 != NULL){ 
        while(tmp3 != NULL){ 
          //如果在新链表中找到了相同类型的项，则退出循环
          if(tmp2->_ch == tmp3->_ch && tmp2->_power == tmp3->_power){ 
            break; 
          }
          tmp3 = tmp3->_next;
        }//end while(tmp3 != NULL)
        //如果在新链表中没有找到相同类型的项，则将链表2的当前项添加到新链表
        if(NULL == tmp3){ 
          ListAdd(&new_list, tmp2->_elem, tmp2->_ch, tmp2->_power);
        }
        tmp2 = tmp2->_next;
        tmp3 = new_list;//将指向新链表的指针重新指向新链表的头部
      }//end while(tmp2 != NULL)
      return new_list;
    }
    
    //测试用例
    //由于我在实现的时候已经把一些特殊情况考虑到，所以这里的测试用例只是简单的
    //看一下实现后的效果
    int main() { 
      PNode list_1;
      ListInit(&list_1);
      ListAdd(&list_1, 3, 'x', 29);
      ListAdd(&list_1, -2, 'x', 12);
      ListAdd(&list_1, 3, '#', 1);
      ExpressionPrint(list_1);
      PNode list_2;
      ListInit(&list_2);
      ListAdd(&list_2, 5, 'x', 29);
      ListAdd(&list_2, 4, 'x', 20);
      ListAdd(&list_2, 1, 'x', 2);
      ListAdd(&list_2, 12, '#', 1);
      ExpressionPrint(list_2);
      PNode result = ExpressionAdd(list_1, list_2);
      ExpressionPrint(result);
      return 0;
    }

> 后记：这个程序在实现的过程中要考虑很多细节，这些细节由于我在写的时候就直接考虑了，所以并没有具体写出来，阅读这篇博客的朋友在自己实现的时候要考虑各种细节，具体可以比对我的代码。

[70]: /images/20220506/8c92fc35f4384fff98592957cbf6ffe9.png
[70 1]: /images/20220506/c790fb7cbe1d43fa8f6e8b0039dd539c.png
[70 2]: /images/20220506/e641fe7e22214fbf8741da6049578ef6.png