这个小项目用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可以相加，因为他们都含有变量，并且变量的系数相同。
所以，我们可以拿着依次拿着第一个链表中的节点去遍历第二个链表，在第二个链表中查找类型相同（即可以相加）的项，如果找到，则将两个节点（第一个链表中的当前节点和第二个节点中找到的目标节点）的系数相加并插入到新的链表（即相加后的新表达式）：
如果在第二个链表中没有找到和链表1当前节点类型相同的节点，则将链表1的当前节点直接插入到新链表中：
当链表1已经走完了后（所有的节点都分别在链表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;
}
后记：这个程序在实现的过程中要考虑很多细节，这些细节由于我在写的时候就直接考虑了，所以并没有具体写出来，阅读这篇博客的朋友在自己实现的时候要考虑各种细节，具体可以比对我的代码。