实验内容
需要设计一个简单的一元稀疏多项式加减法计算器
实验要求
- 输入并建立多项式
例如：
![][1]
[1]: http://latex.codecogs.com/gif.latex?A(x)=7+3x+9x{8}+5x{17}
或：
![][2]
[2]: http://latex.codecogs.com/gif.latex?B(x)=8x+22x{7}-9x{8}
- 输出多项式
- 多项式A和B相加，建立多项式 C = A + B，并输出相加的结果多项式 C
- 多项式A和B相减，建立多项式 C = A - B，并输出相减的结果多项式C (选作)
如何做？
首先根据实验要求，多项式为稀疏一元多项式，因此采用链式线性存储结构表示，链式线性存储结构在理论课中介绍了：
- 单链表
- 双向链表
- 循环链表
在此，为简便起见，我们采用单链表结构。如果使用单链表存储一元多项式，则单链表中的每一个节点用于存储该一元多项式中的某一项。
第一步 定义数据结构类型
由实验要求可知，一元多项式中每一项由系数和指数构成，因此我们定义单链表中节点结构为：
struct tagNode
{
float chef;
int exp;
struct tagNode *next;
};
typedef struct tagNode Node;
typedef struct tageNode * pNode;
typedef struct tagNode * LinkList;
typedef struct tagNode * Poly;
单链表可以采用带头结点的单链表或头指针单链表，为简便起见，我们采用带头结点的单链表。
如上代码所示，我们通过 typedef struct tagNode *Poly 定义了多项式类型。
第二步 定义操作接口
实验要求必须实现如下功能：
- 输入并建立多项式
- 输出多项式
- 多项式A和B相加，建立多项式 C = A + B，并输出相加的结果多项式 C
- 多项式A和B相减，建立多项式 C = A - B，并输出相减的结果多项式C
上述4个功能，可以映射为 对 Poly 类型的四个不同操作接口。
此外， 对于单链表而言，由于是动态分配节点存储空间，因此还需要考虑单链表的建立、销毁操作；
对于多项式如何建立，可以再创建时既确定多项式中每一项的系数及指数；也可以在多项式数据结构实例创建完成后通过其他操作接口添加新的项。
根据上述要求，我们可以给出多项式操作接口的声明：
struct tagNode
{
float chef;
int exp;
struct tagNode *next;
};
typedef struct tagNode Node;
typedef struct tageNode * pNode;
typedef struct tagNode * LinkList;
typedef struct tagNode * Poly;
Poly CreatePoly(); // 创建多项式数据结构实例
bool DestroyPoly(Poly poly); // 销毁多项式实例
void PrintPoly(Poly poly); // 输出多项式
Poly Add(Poly polya, Poly polyb); // 多项式相加
Poly Substract(Poly ploya, Poly polyb); // 多项式相减
bool AddNode(Poly poly, float coef, int exp); // 为poly多项式添加新项(coef, exp)
第三步 建立项目文件
首先，建立一个C或C++项目工程。关于C或C++项目工程，由于使用开发环境的不同，操作步骤不尽相同。这里，我们不使用IDE，直接使用gcc编译器对源文件进行编译。
我们需要建立3个文件，他们分别是：
- Poly.h : 用于定义多项式数据结构及操作接口声明
- Poly.cpp : 用于多项式操作接口实现
- main.cpp : 用于整个实验项目的测试
Poly.h文件
通常而言，我们将数据结构的 定义、操作接口 的声明与 实现 分开，以便于项目的组织及代码复用。
以下给出Poly.h文件的代码：
#ifndef _POLY_H_
#define _POLY_H_
#include <stdio.h>
struct tagNode
{
float chef;
int exp;
struct tagNode *next;
};
typedef struct tagNode Node;
typedef struct tageNode * pNode;
typedef struct tagNode * LinkList;
typedef struct tagNode * Poly;
Poly CreatePoly(); // 创建多项式数据结构实例
bool DestroyPoly(Poly poly); // 销毁多项式实例
void PrintPoly(Poly poly); // 输出多项式
Poly Add(Poly polya, Poly polyb); // 多项式相加
Poly Substract(Poly ploya, Poly polyb); // 多项式相减
bool AddNode(Poly poly, float coef, int exp); // 为poly多项式添加新项(coef, exp)
#endif _POLY_H_
Poly.h 文件中，文件头2行和最后1行使用了 #ifndef 和#define 宏，主要作用是为防止 Poly.h 头文件被重复引用的问题。
Poly.cpp文件
在定义好 Poly.h 文件后，我们开始实现多项式相关的操作接口。与多项式相关的操作接口都在 Poly.cpp 文件中实现。首先来看看 Poly.cpp 文件：
#include "Poly.h"
#include <stdio.h>
Poly CreatePoly()
{
...
}
bool DestroyPoly(Poly poly)
{
...
}
...
在 Poly.cpp 文件中，首先通过头文件包含命令将 Poly.h 引用进来。如此一来，在 Poly.cpp 文件中便可使用 Poly.h 文件所定义的数据类型及相关接口声明。
CreatePoly接口
我们首先来实现创建多项式数据类型实例的方法。由于采用头结点单链表形式，因此我们需要在 CreatePoly 接口中完成如下几步操作：
- 通过
malloc(sizeof(Node))分配头结点； - 完成 Poly 数据类型实例初始化工作；
- 成功则返回 Poly 实例，否则返回错误提示；
CreatePoly 接口实现代码如下所示：
...
Poly CreatePoly()
{
Poly poly = NULL;
PNode head = NULL;
head = (PNode) malloc(sizeof(Node));
if (head != NULL)
{
// 不需要对头结点的coef和exp数据域进行设置
head->next = NULL; // 设置头结点的next指针域为NULL
poly = head;
}
return poly; // 如果分配头结点空间成功，则返回poly非空表示创建多项式实例操作成功，
// 否则返回值为NULL，表示创建多项式实例操作失败
}
...
DestroyPoly接口
在完成 CreatePoly 接口后，我们来实现 DestroyPoly 接口。 该接口需要完成的操作是将参数 poly表示的多项式实例进行销毁。因为 C/C++ 中内存的分配和释放操作需由程序员自行完成。
实现 CreatePoly 接口，需要完成如下几步操作：
- 从头节点开始逐一释放 poly 实例中每个节点的内存空间；
- 返回操作成功与否的结果；
DestroyPoly 接口实现代码如下所示：
...
bool DestroyPoly(Poly poly)
{
PNode p = NULL;
p = poly; // p指向头结点
while (p != NULL)
{
poly = poly->next;
free (p);
p = poly;
}
return true;
}
...
PrintPoly接口
完成 CreatePoly 、 DestroyPoly 两个接口后，我们来实现 PrintPoly 接口。
PrintPoly 接口主要用于输出多项式。此外，我们可以利用该接口测试其他接口实现是否正确。
例如，要测试多项式相加接口 Add 实现是否正确，可在调用 Add 接口之前及之后调用Print接口，通过Print接口的输出结果可以较方便、快捷的判断 Add 接口实现是否存在逻辑问题 。
当遇到程序逻辑问题时，通过调试方式检测逻辑问题是一件耗费时间和精力的事情，在可以通过输出中间结果进行判断检测时，尽量避免过早陷入调试程序的陷阱中。
...
Poly polyA, polyB, polyC;
...
PrintPoly(polyA);
polyC Add(polyA, polyB);
PrintPoly(polyC);
...
以下给出 PrintPoly 接口的实现：
void PrintPoly(Poly poly)
{
PNode p = NULL;
if (poly == NULL)
return ;
p = poly->next; // 忽略头结点
while (p != NULL)
{
if (p->exp != 0)
{
printf("%+.1fX^%d ", p->coef, p->exp);
}
else
{
printf("%+.1f ", p->coef);
}
}
printf("\n");
}
第四步 让我们的代码跑起来
完成CreatePoly、DestroyPoly、PrintPoly 三个接口后。对于剩余的Add、Subtract、AddNode接口，我们暂且放一边。
接下来我们的目标是将项目尽快跑起来，以便对已实现的接口进行测试(包括语法、逻辑错误)。
实际项目开发过程中，我们总是通过不断的迭代开发来完善我们的项目。因此，在开发过程中尽快让项目运行起来，能够有一个可运行版本(最小功能版本、最小系统版本)至关重要。
main.cpp
让我们来编写测试代码。我们把测试代码放在main.cpp文件中。测试代码主要对已编写的接口进行测试，按照本文PrintPoly接口中所写的类似，可以先调用CreatePoly、再调用PrintPoly接口对其他接口进行测试。
#include "Poly.h"
#include <stdio.h>
int main ()
{
Poly ploya = NULL;
polya = CreatePoly();
PrintPoly(polya);
DestroyPoly(polya);
return 0;
}
完成 main.cpp 中测试代码的编写后，我们来对整个项目进行编译。在此，我们使用gcc编译套件进行编译工作。
Step 1
进入 lab01 目录，使用 ls 命令查看当前目录信息：
[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h main.cpp
Step 2
运行 g++ 命令，对 main.cpp 、 Poly.cpp 进行编译。编译后，无语法错误，默认生成 a.out 执行文件。
[localhost:lab01 xgqin]$ g++ main.cpp Poly.cpp
[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h a.out main.cpp
[localhost:lab01 xgqin]$
Step 3
通过 ./a.out 运行编译后的执行文件。从运行结果看， a.out 文件执行后，无任何输出。因为 main.cpp 文件中调用了 CreatePoly 和 PrintPoly 两个方法，但由于 CreatePoly 方法仅仅创建了一个带头结点的空链表，因此 PrintPoly 方法无任何输出。
[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h a.out main.cpp
[localhost:lab01 xgqin]$ ./a.out
[localhost:lab01 xgqin]$
通过上述运行结果，我们并不知道在 Poly.cpp 中所写的 CreatePoly 、 PrintPoly 等接口是否无问题。那接下来我们该如何做？可以考虑以下几个方案：
- 实现 AddNode 接口，从而可以构造出非空的多项式，然后通过 PrintPoly 接口进行测试；
- 在 CreatePoly 接口中新增添加节点的测试代码，再通过PrintPoly接口进行测试；
在此，我们选择方案2，因为可避免在未完成第一次迭代开发前再加入新的接口，尽可能避免让项目代码在开发早期过于复杂。
为CreatePoly接口增加测试代码
新加的测试代码目的是便于我们进行测试，如下代码所示：
Poly CreatePoly()
{
Poly poly = NULL;
PNode head = NULL;
PNode cur = NULL; // 始终指向存储多项式的单链表最后一个节点的指针
int num; // 存储所需输入多项式项数
float coef;
int exp;
head = (PNode) malloc(sizeof(Node));
if (head != NULL)
{
// 不需要对头结点的coef和exp数据域进行设置
head->next = NULL; // 设置头结点的next指针域为NULL
poly = head;
}
cur = poly; // 初始化cur指针，cur当前指向头结点
printf("请输入节点个数:");
scanf("%d", &num);
for (int i = 0; i < num; i++)
{
scanf("%f%d", &coef, &exp);
cur->next = (PNode) malloc(sizeof(Node));
if (cur->next != NULL) // 分配节点成功
{
cur = cur->next; // 确保cur指向最后一个新节点
cur->coef = coef;
cur->exp = exp;
cur->next = NULL;
}
}
return poly; // 如果分配头结点空间成功，则返回poly非空表示创建多项式实例操作成功，
// 否则返回值为NULL，表示创建多项式实例操作失败
}
完成 CreatePoly 接口修改后，我们再次按照Step 1 至 Step 2的步骤对当前项目进行编译：
[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h a.out main.cpp
[localhost:lab01 xgqin]$ g++ main.cpp Poly.cpp
[localhost:lab01 xgqin]$ ls
Poly.cpp Poly.h a.out main.cpp
[localhost:lab01 xgqin]$ ./a.out
请输入节点个数:4
4 -1
7 0
3 1
9 8
+4.0X^-1 +7.0X +3.0X^1 +9.0X^8
[localhost:lab01 xgqin]$
再次使用 g++ 命令可以对 main.cpp、Poly.cpp 进行编译，如无语法错误，编译器会生成新的 a.out 文件覆盖旧版本 a.out 文件。
从程序再一次的运行结果看，我们创建了一个包含4个项的一元多项式，且输入每个项的系数与指数时，按照指数升序的形式进行输入、存储。
![][3]
[3]: http://latex.codecogs.com/gif.latex?A=4x{-1}+7+3x+9x{8}
输入所表示的多项式如上图所示，输出结果如下所示。
+4.0X^-1 +7.0X +3.0X^1 +9.0X^8
从程序运行输出结果看，目前 CreatPoly 、 PrintPoly 两个接口未发现逻辑错误(未发现逻辑错误 不等价于 没有逻辑错误)。
你可以多次运行 a.out 文件输入不同数据对程序进行测试或修改main.cpp中的测试代码(例如：声明新的Poly指针，新增PrintPoly接口调用代码等)。
