单链表实现多项式相加

这个小项目用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;
}

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

单链表实现多项式相加

相关推荐