首页 > > 程序设计 > C/C++ >

单链表实现多项式的加减乘运算

2018-06-18 04:12:05来源：未知阅读 ()

此处链表是加了表头Head。这个程序有两个头文件poly.h和fatal.h，一个库函数poly.c和一个测试函数testpoly.c

头文件poly.h如下：

#ifndef Poly
typedef int Integer;
struct Node;
typedef struct Node *Polynomial;
typedef Polynomial Position;
Polynomial MakeEmpty(Polynomial L);
void DeleteList(Polynomial L);
void Insert(Integer Coefficient, Integer Exponent, Position P);
void PrintPoly(Polynomial L);
Position Header(Polynomial L);
Position First(Polynomial L);
int IsLast(Position P, Polynomial L);
int IsEmpty(Polynomial L);
Position Advance(Position P, Polynomial L);
Polynomial addpolynomial(const Polynomial poly1, const Polynomial poly2);
Polynomial subpolynomial(const Polynomial poly1, const Polynomial poly2);
//int Max(int A, int B);
Polynomial MultPolynomial(const Polynomial Poly1, const Polynomial Poly2);
void InsertSortPolynomial(const Polynomial Poly);
void CombSimPolynomial(const Polynomial Poly);
int CountPolynomial(const Polynomial Poly);
#endif // !1

头文件fatal.h如下：

#include <stdio.h>
#include <stdlib.h>
#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )

所有的库函数poly.c如下：

//引入头文件
#include "poly.h"
#include "fatal.h"
//结构体，Coefficient表示多项式系数，Exponent表示多项式的指数
struct Node
{
int Coefficient;
int Exponent;
Position Next;
};
//初始化链表
Polynomial MakeEmpty(Polynomial L)
{
if (L != NULL)
DeleteList(L);
L = malloc(sizeof(struct Node));
if (L == NULL)
Error("Out of Space!!!");
L->Next = NULL;
return L;
}
//删除链表
void DeleteList(Polynomial L)
{
Position P, Temp;
P = L->Next;
L->Next = NULL;
while (P != NULL)
{
Temp = P->Next;
free(P);
P = Temp;
}
free(L);
}
//在链表中插入值，在P指向的位置后插入
void Insert(Integer Coefficient, Integer Exponent, Position P)
{
Position TempCell;
TempCell = malloc(sizeof(struct Node));
if (TempCell == NULL)
FatalError("Out of Space!!!");
TempCell->Coefficient = Coefficient;
TempCell->Exponent = Exponent;
TempCell->Next = P->Next;
P->Next = TempCell;
}
//打印链表
void PrintPoly(Polynomial L)
{
Position P = First(L);
if (IsEmpty(L))
printf("Empty List!");
else
{
while (P->Next != NULL)
{
if (P->Exponent == 0)//如果是常数
{
if (P->Next->Coefficient < 0)//如果后面是负的，就不加"+"因为会自带负号
printf("%d", P->Coefficient);
else
printf("%d+", P->Coefficient);//如果后面是正的，就加"+"
}
else
{
if (P->Next->Coefficient < 0)
printf("%dx^%d", P->Coefficient, P->Exponent);
else
printf("%dx^%d+", P->Coefficient, P->Exponent);
}
P = P->Next;
}
if (P->Exponent == 0)
printf("%d", P->Coefficient);
else
printf("%dx^%d", P->Coefficient, P->Exponent);
}
}
//获取链表的表头
Position Header(Polynomial L)
{
return L;
}
//获取除去表头后链表的第一个指针位置
Position First(Polynomial L)
{
return L->Next;
}
//判断P是不是未指针，是，返回1，不是，返回0
int IsLast(Position P, Polynomial L)
{
return P->Next == NULL;
}
//判断链表是不是空链表，如果是，返回1，不是，返回0
int IsEmpty(Polynomial L)
{
return L->Next == NULL;
}
//获取链表中 P位置的后一个位置
Position Advance(Position P, Polynomial L)
{
return P->Next;
}
//实现两个多项式相加，新建了一个链表Result作为存储结果
Polynomial addpolynomial(const Polynomial poly1, const Polynomial poly2)
{
Polynomial Result;
Integer InsertCoe, InsertExp;
Position poly1_pos, poly2_pos, ResultPos;
poly1_pos = First(poly1); poly2_pos = First(poly2);
Result = MakeEmpty(NULL);
ResultPos = Header(Result);
while (poly1_pos != NULL&&poly2_pos != NULL)
{
if (poly1_pos->Exponent > poly2_pos->Exponent)
{
InsertCoe = poly1_pos->Coefficient;
InsertExp = poly1_pos->Exponent;
poly1_pos = Advance(poly1_pos,poly1);
}
else if(poly2_pos->Exponent > poly1_pos->Exponent)
{
InsertCoe = poly2_pos->Coefficient;
InsertExp = poly2_pos->Exponent;
poly2_pos = Advance(poly2_pos, poly2);
}
else
{
InsertCoe = poly1_pos->Coefficient+ poly2_pos->Coefficient;
InsertExp = poly1_pos->Exponent;
poly1_pos = Advance(poly1_pos, poly1);
poly2_pos = Advance(poly2_pos, poly2);
}
Insert(InsertCoe, InsertExp, ResultPos);
ResultPos = Advance(ResultPos,Result);
}
while (poly1_pos != NULL)
{
Insert(poly1_pos->Coefficient, poly1_pos->Exponent, ResultPos);
poly1_pos = Advance(poly1_pos,poly1);
ResultPos = Advance(ResultPos,Result);
}
while (poly2_pos != NULL)
{
Insert(poly2_pos->Coefficient, poly2_pos->Exponent, ResultPos);
poly2_pos = Advance(poly2_pos, poly2);
ResultPos = Advance(ResultPos, Result);
}
return Result;
}
//实现两个多项式相减，新建了一个链表Result作为存储结果
Polynomial subpolynomial(const Polynomial poly1, const Polynomial poly2)
{
Polynomial Result;
Integer InsertCoe, InsertExp;
Position poly1_pos, poly2_pos, ResultPos;
poly1_pos = First(poly1); poly2_pos = First(poly2);
Result = MakeEmpty(NULL);
ResultPos = Header(Result);
while (poly1_pos != NULL&&poly2_pos != NULL)
{
if (poly1_pos->Exponent > poly2_pos->Exponent)
{
InsertCoe = poly1_pos->Coefficient;
InsertExp = poly1_pos->Exponent;
poly1_pos = Advance(poly1_pos, poly1);
}
else if (poly2_pos->Exponent > poly1_pos->Exponent)
{
InsertCoe = -poly2_pos->Coefficient;
InsertExp = poly2_pos->Exponent;
poly2_pos = Advance(poly2_pos, poly2);
}
else
{
InsertCoe = poly1_pos->Coefficient - poly2_pos->Coefficient;
InsertExp = poly1_pos->Exponent;
poly1_pos = Advance(poly1_pos, poly1);
poly2_pos = Advance(poly2_pos, poly2);
}
Insert(InsertCoe, InsertExp, ResultPos);
ResultPos = Advance(ResultPos, Result);
}
while (poly1_pos != NULL)
{
Insert(poly1_pos->Coefficient, poly1_pos->Exponent, ResultPos);
poly1_pos = Advance(poly1_pos, poly1);
ResultPos = Advance(ResultPos, Result);
}
while (poly2_pos != NULL)
{
Insert(-poly2_pos->Coefficient, poly2_pos->Exponent, ResultPos);
poly2_pos = Advance(poly2_pos, poly2);
ResultPos = Advance(ResultPos, Result);
}
return Result;
}
//插入排序算法实现链表中由大到小排序
void InsertSortPolynomial(const Polynomial Poly)
{
//插入排序算法
Position head = Poly;
Position first; /*为原链表剩下用于直接插入排序的节点头指针*/
Position t; /*临时指针变量：插入节点*/
Position p=head; /*临时指针变量,初始化*/
Position q; /*临时指针变量*/
if (Advance(head, Poly) == NULL)
printf("Empty List!");//判断是不是空链表
else
{
first = head->Next->Next; /*原链表剩下用于直接插入排序的节点链表：可根据图12来理解。*/
head->Next->Next = NULL; /*只含有一个节点的链表的有序链表：可根据图11来理解。*/
while (first != NULL) /*遍历剩下无序的链表*/
{
/*注意：这里for语句就是体现直接插入排序思想的地方*/
for (t = first, q = head->Next; ((q != NULL) && (q->Exponent > t->Exponent)); p = q, q = q->Next); /*无序节点在有序链表中找插入的位置*/
/*退出for循环，就是找到了插入的位置*/
first = first->Next; /*无序链表中的节点离开，以便它插入到有序链表中。*/
if (q == head->Next)
head->Next = t;
else p->Next = t;
t->Next = q; /*完成插入动作*/
/*first = first->next;*/
}
}
}
//将排序后的链表合并同类项
void CombSimPolynomial(const Polynomial Poly)
{
//输入链表为已经排好序的链表
Position p = Poly->Next;
Position q;
if (p != NULL)//防止链表只有一个元素
{
q = p->Next;
while (q != NULL)//搜索链表结束标志
{
if (p->Exponent == q->Exponent)
{
p->Coefficient += q->Coefficient;
p->Next = q->Next;
q = q->Next;
}
else
{
p = q;
q = q->Next;
}
}
}
}
//实现链表的相乘
Polynomial MultPolynomial(const Polynomial Poly1, const Polynomial Poly2)
{
Polynomial MultResult = MakeEmpty(NULL);//对结果进行初始化
Position p1, p2, p;
p1 = First(Poly1);
p2 = First(Poly2);
p = Header(MultResult);
Integer Coe, Exp;
if (IsEmpty(Poly1) || IsEmpty(Poly2))
Error("EmptyList!!!");
while (p1 != NULL)
{
p2 = First(Poly2);
while (p2 != NULL)
{
Coe = p1->Coefficient*p2->Coefficient;
Exp = p1->Exponent + p2->Exponent;
Insert(Coe, Exp, p);
p = p->Next;
p2 = p2->Next;
}
p1 = p1->Next;
}
InsertSortPolynomial(MultResult);//给多项式乘积排序
CombSimPolynomial(MultResult);//给多项式合并同类项
return MultResult;
}
//判断链表中有多少个元素
int CountPolynomial(const Polynomial Poly)
{
int i = 0;
Position P = First(Poly);
while (P != NULL)
{
i += 1;
P = Advance(P,Poly);
}
return i;
}