Java线性表多项式求和_C算法与数据结构-线性表的应用,多项式求和---ShinePans

/*---上机作业作业,二项式加法---*/

/*---By 潘尚 ---*/

/*---日期: 2014-5-8 . ---*/

/*---题目:---*/

//如果有两个稀疏多项式A和B,设计算法完毕下列任务

//1.输入并建立多项式A和B;

//2.求两个多项式的和多项式C;

//3.求两个多项式的积多项式D;

//输出4个多项式A,B,C,D;

#include

#include

#include

typedef struct Node{

float A; //系数

int m; //指数

struct Node *next;

}LNode, *LinkList; //链表类型,若採用嵌套结构体怎样用->以指针的方式訪问

void Initialize(LNode *plist);

LinkList PolyAdd(LNode *plist1, LNode *plist2);

int Cmp(int a, int b);

void Append(LNode *pa, LNode *pb);

int ListIsEmpty(const LinkList *plist);

void EmptyTheList(LNode *plist);

void PrintList(LNode *plist);

void PolySort(LNode *plist);

int GetLength(LNode *plist);

void PolyMerge(LNode *plist);

float HornorEvaluate(LNode *plist, float x);

LinkList PolyMultiply(LNode *plist1, LNode *plist2);

int GetMaxExpn(LNode *plist);

/**

*主函数

*/

int main(void)

{

LNode *p1 = (LNode*)malloc(sizeof(LNode));

LNode *p2 = (LNode*)malloc(sizeof(LNode));

LNode *result1 = (LNode*)malloc(sizeof(LNode));

LNode *result2 = (LNode*)malloc(sizeof(LNode));

Initialize(p1);

Initialize(p2);

PolySort(p1); //多项式排序

PolySort(p2);

printf("np1 = ");

PrintList(p1);

printf("np1(value) = %f", HornorEvaluate(p1, 2));

printf("np2 = ");

PrintList(p2);

printf("np2(value) = %f", HornorEvaluate(p2, 2));

result1 = PolyAdd(p1, p2);

result2 = PolyMultiply(p1, p2);

//printf("n%d",GetLength(p1));

//PolyMerge(p1); //合并同类项

//UnitePoly(p1); //合并同类项

//EmptyTheList(p1);

printf("np1 + p2 = ");

PrintList(result1);

printf("np1 * p2 = ");

PrintList(result2);

getchar();

getchar();

return 0;

}

/**

*Operation: 初始化一个多项式

*Precondition:

*Postcondition:

*/

void Initialize(LNode *plist)

{

int i, n;

float c;

int e;

LNode *prev = NULL, *current = NULL;

plist->next = NULL;

prev = plist;

printf("nPlease input the length of the polynomial: ");

scanf_s("%d", &n);

plist->A = 0;

plist->m = n; //链表长度

printf("Please input the coefficient and the exponent of each term: n");

for (i = 1; i <= n; i++)

{

current = (LNode*)malloc(sizeof(LNode));

scanf_s("%2f%d", &c, &e);

current->A = c;

current->m = e;

prev->next = current;

prev = current;

/*plist->next = current;

plist = current;*/

}

current->next = NULL;

PolySort(plist);

}

/**

*Operation: 将两个多项式相加

*Precondition:

*Postcondition:

*Notes: 能够採用先将两多项式合并(拼接)后再合并同类项来实现相加

*/

LinkList PolyAdd(LNode *plist1, LNode *plist2)

{

LNode *pa, *pb;

LNode *result = (LNode*)malloc(sizeof(LNode));

int a, b;

result->next = NULL;

LNode *r = result;

pa = plist1->next;

pb = plist2->next;

while (pa && pb)

{

LNode *current = (LNode*)malloc(sizeof(LNode));

a = pa->A;

b = pb->m;

switch (Cmp(a, b)){

case -1:

current->A= pa->m;

current->A = pa->m;

pa = pa->next;

break;

case 0:

current->A = pa->A + pb->A;

current->m = pa->m;

pa = pa->next;

pb = pb->next;

break;

case 1:

current->A = pb->A;

current->m = pb->m;

pb = pb->next;

break;

}

r->next = current;

r = r->next; //结果多项式指针后移

current->next = NULL;

}

if (!pa || !pb)

{

if (!pa) Append(r, pb);

if (!pb) Append(r, pa);

}

//free(current);

return result;

}

/**

*比較两整数大小

*/

int Cmp(int a, int b)

{

if (a>b) return 1;

if (a

else return 0;

}

/**

*链接pb剩余节点到pa上

*/

void Append(LNode *pa, LNode *pb)

{

LNode *r = pa;

LNode *p = pb;

while (p)

{

LNode *current = (LNode*)malloc(sizeof(LNode));

current->A= p->A;

current->m = p->m;

p = p->next;

r->next = current; //SEGIVE

current->next = NULL;

}

}

/**

*Operation: 推断多项式是否为空

*/

int ListIsEmpty(const LinkList *plist)

{

if (*plist == NULL)

return 1;

else

return 0;

}

/**

*Operation: 清空一个多项式链表

*Precondition：plist指向一个多项式列表

*Postcondition：该列表被清空并释放

*/

void EmptyTheList(LNode *plist)

{

LNode *psave;

while (plist != NULL)

{

psave = plist->next;

free(plist);

plist = psave;

}

}

/**

*Operation: 输出一个多项式链表

*/

void PrintList(LNode *plist)

{

LNode *p = plist;

p = p->next; //跳过头指针

while (p != NULL)

{

if (p->next != NULL)

printf("%0.1f*x^%d + ", p->A, p->m);

else

printf("%0.1f*x^%d;", p->A, p->m);

p = p->next;

}

printf("n");

}

/**

*Operation: 将输入的无序多项式链表排序

*Precondition:无序多项式链表

*Postcondition:递增顺序的多项式链表

*/

void PolySort(LNode *plist)

{

LNode *pa = plist->next, *pb = pa->next;

LNode *temp = (LNode*)malloc(sizeof(LNode));

int length = GetLength(plist);

int i;

for (i = 0; i

{

while (pb)

{

if (pa->m > pb->m)

{

temp->A = pa->A; temp->m = pa->m;

pa->A = pb->A; pa->m = pb->m;

pb->A = temp->A; pb->m = temp->m;

}

pa = pa->next;

pb = pa->next;

}

pa = plist->next;

pb = pa->next; //这两句用于将pa,pb又一次指向头节点

}

}

/**

*Operation: 将输入的多项式中的指数同样项合并(合并同类项)

*Precondition:有序多项式链表

*Postcondition:无同类项的有序多项式链表

*/

void PolyMerge(LNode *plist)

{

LNode *prev, *current;

int l = GetLength(plist);

int i;

prev = plist->next;

current = prev->next;

for (i = 0; i

{

while (current)

{

if (prev->m == current->m)

{

prev->A += current->A; // why " prev->coef += current->coef " is wrong?

prev->next = current->next;

free(current);

current = prev->next;

continue; //! without this sentence ,the function will be wrong and report an problem

}

prev = prev->next;

current = prev->next;

}

if (current)

{

prev = plist->next;

current = prev->next;

}

}

}

/* //合并同类项

void UnitePoly(LNode *h)//合并同类项

{

LNode *p1,*p2,*q1,*q2,*temp;

q1=h;

p1=q1->next;

while(p1!=NULL)

{

p2=p1->next;

q2=p1;

while(p2!=NULL)

{

if(p1->expn==p2->expn)

{

p1->coef=p1->coef+p2->coef;

if(p1->coef==0)

{

temp=p2;

q2->next=p2->next;

free(temp);

temp=p1;

q1->next=p1->next;

p1=q1;

free(temp);

break;

}

else

{

temp=p2;

q2->next=p2->next;

p2=p2->next;

free(temp);

}

}

else

{

q2=p2;

p2=p2->next;

}

}

q1=p1;

p1=p1->next;

}

}

*/

/**

*求链表长度

*/

int GetLength(LNode *plist)

{

LNode *p = plist;

int lenght = 0;

p = p->next; //跳过节点

while (p)

{

lenght++;

p = p->next;

}

return lenght;

//return lenght-1; //若没跳过头结点则返回值减一

}

/**

*Operation: 求两多项式乘积

*Precondition:

*Postcondition:

*/

LinkList PolyMultiply(LNode *plist1, LNode *plist2)

{

LNode *pa, *pb;

LNode *result = (LNode*)malloc(sizeof(LNode));

LNode *r = result; // 不能少！否则result所指不是头指针

pa = plist1->next; pb = plist2->next;

while (pa)

{

while (pb)

{

LNode *current = (LNode*)malloc(sizeof(LNode));

current->A= pa->m * pb->A; //系数相乘

current->m = pa->m + pb->m; //指数相加

r->next = current;

current->next = NULL;

r = r->next;

pb = pb->next;

}

pa = pa->next;

pb = plist2->next; //pb又一次指向头结点

}

PolyMerge(result);

return result;

}

/**

*Operation: Computing the value of the polynomia

*Precondition: Ordered Polynomial Linklist

*Postcondition: The value of the polynomial

*/

float HornorEvaluate(LNode *plist, float x)

{

//int max = GetMaxExpn(plist) + 10;

int n = 0;

int i;

float result = 0;

//float Poly[max]; //VC6 sidn't support VLA

float Poly[20];

LNode *p = plist->next;

memset(Poly, 0, sizeof(Poly));

while (p)

{

if (p->m == n)

{

Poly[n++] = p->A;

p = p->next;

}

else

Poly[n++] = 0;

} //Transform linklist to array to store the polynomial

/*for(i=0;i

{

printf("[%d]:%0.2f ",i,Poly[i]);

}

printf("n");*/

result = Poly[n - 1];

for (i = n - 1; i>0; i--) //循环次数及下标关系千万不能错!

{

result = result*x + Poly[i - 1];

//printf("[%d %0.2f] ",i,result); //调试时输出中间变量方便调试

}

return result;

}

/**

*Operation:

*Precondition:

*Postcondition:

*/

int GetMaxExpn(LNode *plist)

{

LNode *p = plist->next;

int max = p->m;

while (p)

{

if (p->m > max)

max = p->m;

p = p->next;

}

return max;

}