数据结构与算法分析——c语言描述 第三章的多项式链表
2016-3-12
用c来写类好酸爽。。。。
有几个地方还没完成，一个是初始化，而是输入输出，三是书中要求以次数递减的顺序排序。这里完全是来个二次循环排序，应该有更好的办法，而且排序嫌麻烦直接交换内容而不是用了链表的交换。还有就是乘完以后没有合并同类项。。。。以后会更新代码的。
2016-3-18
刚好数据结构老师也布置了这个作业，顺便完成，什么都搞定了。可以初始化，输入输出，递减顺序排序不再是二次循环排序了。
几点心得：
功能与功能之间分清楚，类与类之间分清楚，封装起来，模块化，底层细节隐藏。虽然不是c++，其实也是用c来写类，思想都一样。
链表归链表，多项式是基于链表，用的是链表的表层函数，那就不要再管链表了。
输入的时候每输入一个根据合适的位置插入
做加法的时候因为两个都是排好序的，所以不需要每次都根据合适的位置插入，直接选最大的插入就行，然后下一个
乘法、输入都调用了插入函数。
vs2015通过编译，测试无bug，如果有问题请留言谢谢
list.h
typedef struct {
int Coefficient;//系数
int Exponent;//指数
}ElementType;
#ifndef _List_H
#define _List_H
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List CreatList();
List MakeEmpty(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, Position P);
void DeleteList(List L);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
void deleteNext(Position p);
#endif
list.c
#include"list.h"
#include<stdlib.h>
#include"fatal.h"
struct Node {
ElementType Element;
Position Next;
};
int elementCmp(ElementType e1, ElementType e2) {
return e1.Coefficient == e2.Coefficient && e1.Exponent == e2.Exponent;
}
List CreatList() {
List l = malloc(sizeof(struct Node));
if (l == NULL)
Error("out of memory");
l->Next = NULL;
return l;
}
List MakeEmpty(List L) {
if (L == NULL)
Error("L is not created");
DeleteList(L);
L->Next = NULL;
return L;
}
int IsEmpty(List L) {
return L->Next == NULL;
}
int IsLast(Position P, List L) {
return P->Next == NULL;
}
Position Find(ElementType X, List L) {
Position P;
P = L->Next;
while (P != NULL&& elementCmp(P->Element, X))
{
P = P->Next;
}
return P;
}
void Delete(ElementType X, List L) {
Position P;
P = FindPrevious(X, L);
if (!IsLast(P, L)) {
Position TmpCell = P->Next;
P->Next = TmpCell->Next;
free(TmpCell);
}
}
Position FindPrevious(ElementType X, List L) {
Position P;
P = L;
while (P->Next != NULL&& elementCmp(P->Next->Element , X))
P = P->Next;
return P;
}
void Insert(ElementType X, Position P) {
Position tmpCell;
tmpCell = (List)malloc(sizeof(struct Node));
if (tmpCell == NULL)
FatalError("Out of space!!");
tmpCell->Element = X;
tmpCell->Next = P->Next;
P->Next = tmpCell;
}
void DeleteList(List L) {
Position p;
p = L->Next;
L->Next = NULL;
while (p != NULL) {
Position tmp;
tmp = p->Next;
free(p);
p = tmp;
}
}
Position Header(List L) {
return L;
}
Position First(List L) {
return L->Next;
}
Position Advance(Position P) {
return P->Next;
}
ElementType Retrieve(Position P) {
return P->Element;
}
void deleteNext(Position p) {
Position temp = p->Next->Next;
free(p->Next);
p->Next = temp;
}
Polynomial.h
#include<stdlib.h>
#include"list.h"
typedef struct {
List list;
}Polynomial;
struct Node {
ElementType Element;
Position Next;
};
Polynomial creatPolynomial();
void insertMonomials(ElementType e,Polynomial poly);
void inputPolynomial();
void ZeroPolynomial( Polynomial Poly);
void AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum);
void MulPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd);
void printAll(Polynomial poly);
Polynomial.c
#include"Polynomial.h"
#include<stdio.h>
Polynomial creatPolynomial() {
Polynomial poly;
poly.list = CreatList();
return poly;
}
void insertMonomials(ElementType e, Polynomial poly) {
Position p = poly.list;
while (Advance(p) != NULL&& Advance(p)->Element.Exponent > e.Exponent)
p = Advance(p);
if (Advance(p) == NULL) {
Insert(e, p);
}
else if(Advance(p)->Element.Exponent != e.Exponent)
Insert(e, p);
else{
Advance(p)->Element.Coefficient += e.Coefficient;
if (Advance(p)->Element.Coefficient == 0)
deleteNext(p);
}
}
void inputPolynomial(Polynomial poly) {
int coefficient, exponent;
ElementType monomials;
printf("please enter Coefficient and Exponent,alphabet to end\n");
while (scanf("%d", &coefficient) == 1) {
scanf("%d", &exponent);
monomials.Coefficient = coefficient;
monomials.Exponent = exponent;
insertMonomials(monomials, poly);
}
getchar();//字母还留在输入流当中，scanf是不会删去的
}
void ZeroPolynomial(Polynomial Poly) {
MakeEmpty(Poly.list);
}
void AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum) {
ZeroPolynomial(PolySum);
Position p1 = Poly1.list->Next;
Position p2 = Poly2.list->Next;
Position p3 = PolySum.list;
ElementType e;
while (p1 && p2) {
if (Retrieve(p1).Exponent > Retrieve(p2).Exponent) {
Insert(Retrieve(p1), p3);
p1 = Advance(p1);
p3 = Advance(p3);
}
else if (Retrieve(p1).Exponent < Retrieve(p2).Exponent) {
Insert(Retrieve(p2), p3);
p2 = Advance(p2);
p3 = Advance(p3);
}
else {
int temp_coefficient = (Retrieve(p1).Coefficient + Retrieve(p2).Coefficient);
if (temp_coefficient != 0) {
e.Coefficient = temp_coefficient;
e.Exponent = Retrieve(p1).Exponent;
Insert(e, p3);
p1 = Advance(p1);
p2 = Advance(p2);
p3 = Advance(p3);
}
else {
p1 = Advance(p1);
p2 = Advance(p2);
}
}
}
Position temp_p;
temp_p = (p1) ? p1 : p2;
if (temp_p == NULL)
return;
while (temp_p) {
Insert(Retrieve(temp_p), p3);
p3 = Advance(p3);
temp_p = Advance(temp_p);
}
}
void MulPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd) {
ZeroPolynomial(PolyProd);
ElementType prod;
for (Position i = Poly1.list->Next; i != NULL; i = Advance(i)) {
for (Position j = Poly2.list->Next; j != NULL; j = Advance(j)) {
prod.Coefficient = Retrieve(i).Coefficient * Retrieve(j).Coefficient;
prod.Exponent = Retrieve(i).Exponent + Retrieve(j).Exponent;
if (prod.Coefficient != 0)
insertMonomials(prod, PolyProd);
}
}
}
void printAll(Polynomial poly) {
Position p = Advance(poly.list);
printf("%dx^%d", Retrieve(p).Coefficient, Retrieve(p).Exponent);
p = Advance(p);
while (p) {
if (Retrieve(p).Coefficient > 0)
putchar('+');
printf("%dx^%d", Retrieve(p).Coefficient, Retrieve(p).Exponent);
p = Advance(p);
}
printf("\n");
}
main.c
#include"Polynomial.h"
#include<stdio.h>
#define N 1208
int main() {
Polynomial p1, p2,p3;
p1 = creatPolynomial();
p2 = creatPolynomial();
p3 = creatPolynomial();
inputPolynomial(p1);
printAll(p1);
inputPolynomial(p2);
printAll(p2);
MulPolynomial(p1, p2, p3);
printf("\n");
printAll(p3);
}