数据结构课程设计一元多项式.doc

湖南工学院课程设计

一元多项式计算

班级：
信息本1002
学号：
09
姓名：

班级：
信息本1002
学号：
26
姓名：

班级：
信息本1002
学号：
34
姓名：

班级：
信息本1002
学号：
41
姓名：

目 录
一、课题任务 1
二、概要设计 1
三、具体设计 2
四、调试分析 6
五、测试结果 6
六、课程设计总结 9
七、参考文献 9
八、附录 10

一、课题任务
功能： 1）．可以按照指数降序排列建立并输出多项式；
　　 2）．可以完毕两个多项式的相加，并将结果输出；
3）．能根据输入的多项式及变量的值，能进行计算。并输出计算结果。
4）．能对多个输入的表达式按照指数大小排序输出。
二、概要设计
一元多项式计算系统
降序排列建立并输出多项式
多项式的相加减并输出结果
输入的多项式及变量的值计算
多个表达式按照指数大小排序输出
按指数排序
建立多项式
相减
建立多项式
相加
计算多项式
建立多个多项式
输出多式项或计算值
排序后输出
多个多项式排序

三、具体设计
一元多项式定义系数和指数结构如下：
coef
expn
next

coef域--存放结点的系数值
expn域--存放结点的指数值
next域--存放结点的直接后继的地址（位置）的指针域（链域）

一元多项式单链表存储结构：
typedef struct term
{ float coef; //系数
int expn; //指数
struct term *next;
}term;

有了链表特定的数据类型term，接下来就需要建立这个链表。这里我们自定义一个构造函数CreatePoly（）来构造链表。一方面定义一个term型的指针变量h=p作为头结点，存储多项式的信息（项数），为h分派存储空间建立一个头结点并为其数据域赋值，分派存储空间用malloc()函数来实现；这时输入多项式的项数m，先给p的coef赋值为0，此时运用一个for循环将p链表的coef与expn值从键盘输入，用m来控制循环的次数，若该从键盘输入的coef值不为0，则将该数值插入链表新建链表q，用malloc（）分派给p空间，p=p->next继续从键盘输入coef与expn的值，直到满足p->next=null,输入完毕，返回链表q即为多项式的系数与指数，创建多项式完毕。
在解决多项式相加的问题上，由于事先建立的多项式函数已经按指数大小排好序，那么多项式的相加就变得不那么复杂了，我们只要找出两个相加多项式指数相同的项进行合并，即将指数相同的项的系数相加，其它的保持不变存好即可。而查找指数相同的项，只要按链表从头到尾进行扫描，若发现相同，则两个同时往下移，否则只将其中指数较大的往下移。假若两个指数相同的项进行合并时，其系数相加值为0，则消除该项，继续下去。
在解决输入的多项式及变量的值计算结果的问题时，定义一个C（）函数实现，需要定义一个float变量sum来存储和值，再引用一个pow()函数来计算多项式的和，运用一个for循环来一一计算x的q->expn次方后与q->coef相乘的值，并存储在sum中，q=q->next，直到q->next =unll，跳出for循环，返回 sum的值就是多项式在用x赋值后的值。
对多个输入的表达式按照指数从大到小排序输出:，运用一个for（包含两个函数CreatPolyn(M,n);selsort(M);）循环，用scanf()输入k来控制for的次数可控制输入的多项式个数，并一个trem型数组G[i]来保存每一个多项式，方便后来的按最高指数大小排序。排序的思想运用枚举排序法可将每个多项式最高次expn按从大到小排列并保存在G[i]数组中，再次运用for将排序好的G[i]多项式按指数从大到小输出。
开始
具体子功能流程图如下：

输入变量x的值

N

q不空

Y

sum+=q->coef*pow(x,q->expn)

q=q->next

return sum;

完毕多项式计算

输出

多项式的计算
开始
从键盘输入项数m

m<=0
返回空
定义存储多项式数据类型term
动态分派空间
完毕建立多项式
降次排序
输出
Y
N

多项式的建立

按指数排序
将k个有序多项式用数组G[ i]保存
输入多项式个数k
输出
开始
开始
定义存储和链表h动态分派空间
Pb=Pb->coef*(-1)

两多项式相加
输出
Pb？
Pb=pb->next
Y
N

多个多项式排序 多项式相减

定义存储和链表h动态分派空间
Pa&&Pb?
C=a->expn - b->expn
h==UNLL
返回系统
C>=1
C>=0
h=Pb
Pb = Pb->next;
h=Pa
Pa = Pa->next;
sum = Pa->coef + Pb->coef;
sum==0
Pa->coef = sum;
h=Pa;
Pa=Pa->next;
Pa = Pa->next;
Pa==0
Pb==0
h->next = Pa;
h->next = Pa;
h = h->next;
Return h
N
Y
N
Y
N
Y
N
Y
Y
N
Y
Y
N
N
输出
开始
完毕多项式相加

调用函数查找同类项
同类项系数相加进行合并
合并后检查a b扫描是否完整

输出多项式q流程图：

putchar(‘1’)
printf(“x^%d”,q->expn)
Putchar(‘x’)
q->expn==0
p=p->next
putchar (‘0’);
开始
printf(“%g”,q->coef)
q!=UNLL
q->coef!=1
q->expn==1
q->coef>=0
q!=UNLL
Putchar(‘+’)
退出

N

Y

N

Y

Y
N

Y
N

Y
N
Y

N

多项式输出重要是对已建立的多项式按链表从头到尾扫描指数跟系数进行多重判断，根据指数和系数输出相应的数值与符号，直到多项式输出完毕。

四、调试分析
程序的调试是程序顺利完毕中非常关键的一步。通过程序的调试分析可以解决程序的运营错误也可以对程序的性能进行分析。这个多项式运算问题研究的程序最重要的就是看输出的链表是否对的，是否带有空结点，运营结果输出是否对的。决定程序成功与否的第一步是定义的CreatPolyn()函数操作是否对的，假如这一步中出现错误，那么接下来的操作可以说是错上加错。在调试的时候可以在程序中加入删除、释放空结点操作，此操作是由Delet()与free()函数完毕的，若输出的多项式没有空结点说明函数对的，可以继续向下进行。接下来就是函数相加，控制此操作的关键是一个A ()函数，其中调用APolyn（）函数是决定成功与否的关键，而函数的相减正是相加一个负数，将减数多项式的coef变为负值便实现了多项式的相减。可以先在本上写出两个对的的简朴的多项式，使其具有相加后出现空结点的特点，然后变换循环变量的范围，当输出吻合时则说明操作对的。对于根据输入的多项式及变量的值进行计算，控制此操作的关键是如何计算多项式中多次方的值，此操作关键是一个C()函数，调用pow()函数来实现计算次方的功能，其中sum值的计算是否对的起关键作用。而对多个输入的表达式按照指数从大到小排序输出，这个重要是用到了一个trem型数组对各已按指数排序好的多项式保存，然后对数组中的每个多项式的第一个p->expn值运用枚举排序法进行比较将多项式排序。各个关键部分都已检查完毕，剩下的就是对程序的进一步细心的完善化、美观化、清楚化直到满足规定。
下面我们分析一下程序的性能。在主函数中，一方面调用构造单链表函数CreatePoly()，在这个函数中需要通过一个for循环为每个结点分派存储空间，变换节点的next域，时间复杂度为O（n）。接下来执行selsort()函数对多项式进行按指数排序，其中一个双重for循环，在内部的for循环中是对相邻结点指数大小比较进行操作，所以每个结点的操作都需要m次，共n个结点，则需要mn次操作，时间复杂度为O（nn）。其后的for循环是比较将指数相同的数进行合并，时间复杂度为O（n）。
五、测试结果
系统选择界面如图 6-1

图6-1
测试按照指数降序排列输出多项式 8*x^1+9*x^0+7*x^2+6*x^3
输入数据为：
1（enter）
4（enter）
8 1 9 0 7 2 6 3（enter）
输出结果为：6*x^3+7*x^2+8*x^1+9
测试结果如图6-2

图6-2
测试两个多项式相加8*x^1+9*x^0+7*x^2+6*x^3; 0*x^0+1*x^3+5*x^2；
输入数据为：
2（enter）
4（enter）
8 1 9 0 7 2 6 3 （enter）
3（enter）
0 0 1 3 5 2（enter）
输出结果为：7x^3+12x^2+8x+9
测试结果如图6-3

图6-3
输入的多项式及变量的值计算结果测试
测试多项式4x^3+5x^4+6x^1+7x^0 当x值为2.5时的值为279.8125
输入数据为：
4（enter） 4（enter）
4 3 5 4 6 1 7 0（enter）
2.5（enter）
测试结果如图6-4

图6-4
测试对多个输入的表达式按照指数从大到小排序输出
测试多项式8*x^1+9*x^0+7*x^2+6*x^3; 0*x^0+1*x^3+5*x^2；4x^3+5x^4+6x^1+7x^0
输入数据为：
5（enter） 3（enter）
4（enter） 8 1 9 0 7 2 6 3 （enter）
3（enter） 0 0 1 3 5 2 （enter）
4（enter） 4 3 5 4 6 1 7 0 （enter）
输出结果为：5x^4+4x^3+6x+7； 6*x^3+7*x^2^+8*x +9；x^3+5*x^2
数组测试结果如图6-5

图6-5
六、课程设计总结
计算一元多项式加法，其结果取决于多项式的各项系数与指数，因此程序核心是解决两个多项式的系数与指数。定义结构体将多项式的各项系数与指数存放，定义结构体类型链表为程序的循环控制提供了也许，运用对链表的运算来拟定结果多项式的各项系数与次数，同理算出相应的幂数。链表是在计算机内存中使用一组连续的存储单元保存数据类型和名字相同的变量。就链表这种数据类型而言，在排列上采用的方法也是按序排放，先存放第一行，接着存放第二行，……，直到所有数据元素被存放。多项式采用的是链表形式，以牺牲一定的空间提高程序的运营速度和可行性。
算法思想：采用链式结构存储多项式，用链表结构体的一个域标记多项式的次数，另一个域标记多项式的系数，程序中采用的是m表达最高次系数，进行加法运算时，标记系数域相加即为相加的相应系数，标记指数域相同则表达为同类项。
链表的特性是在中间任意位置添加删除元素的都非常的快，不需要移动其它的元素。链表顾名思义，要把各个元素链接起来才算撒。通常链表每一个元素都要保存一个指向下一个元素的指针（单链表）。
本次课程设计，我查找过资料，请教过同学，以及不懈的努力，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在程序设计中，我学会了很多学习的方法，而这是日后最实用的，真的是受益匪浅。本学期的程序设计课程，我锻炼了能力，学到很多东西，比如思考问题的角度也会从多方面着手；对自己的专业也有自己的想法……在和同学的交流过程中，互动学习，将知识融会贯通。通过这次课程设计，我对很多的函数有了新的结识，也学会了运用多种函数，我也明白了写软件的基本过程和基本方法。在程序的设计过程中碰到拉很多的困难，在程序一次一次的调试失败下曾经想过要放弃，我最后还是让自己坚持啦下来，毫不畏惧困难，在同学的帮助与讲解下我总算是顺利的完毕了程序的课程设计。
在这几天的编写过程中我对语言有了更进一步的结识和了解，也感受到了编程给我带来的快乐与充实，明白了想成为一个合格的甚至是优秀的程序员，我还需要更多更难的锻炼。所以我还要不断地学习不断地说活，不断地成长，为我的抱负而奋斗。
七、参考文献
1） 严蔚敏 吴伟民 《数据结构(C语言版)》 清华大学出版社.2023.
2） 恰汗 合孜尔 《C语言程序设计 》中国铁道出版社2023.
3） 杨永斌 《数据结构(理论与实践).》 天津科学技术出版社
4） 百度资料

八、附录
#include<stdlib.h>
#include<stdio.h>
#include<ctype.h>
#include<iostream>
#include<math.h>
#define null 0
#define W 10
using namespace std;
typedef struct term
{ //项的表达，多项式的项作为LinkList的数据元素
float coef; //系数
int expn; //指数
struct term *next;
}term;
int Empty(term *L)
{
if(L->next!=null)
return 1;
return 0;
}
void Delete(term * L,term * p)
{ term * s,*q;
s=L;
q=L->next;
while(p!=q)
{s=q;
q=q->next;}
s->next=q->next;
free(q);
}
term* CreatPolyn(term *P,int m)
{ // 输入m项的系数和指数，建立表达一元多项式的有序链表P
if(m <= 0) return NULL;
term *h = P = (term*)malloc(sizeof(term)), *q;
P->coef = 0.0;
int i;
printf("依次输入%d个数（前一个为系数，后一个为指数）\n",m*2);
for (i = 1; i <= m; ++i)
{ // 依次输入m个非零项
scanf("%f%d",&P->coef,&P->expn);
if(P->coef)
q = P; //若该系数值不为0，则p数值插入链表q
P = P->next = (term*)malloc(sizeof(term));
}
q->next = NULL;
free(P);
return h;
} // CreatPolyn
term* selsort(term *h)
{ //将有序链表进行指数排列
term *g, *p, *q;
if(!h) return NULL;
float f;
int i, fini = 1;
for(g = h;g->next&&fini;g = g->next) //拟定排序需要扫描的次数
{ fini = 0;
for(p = h,q = h->next;q;p = p->next,q = q->next)
//相邻的指数进行比较，一次循环将最小指数排到最后，若两两比较没互换，则...
if (p->expn < q->expn) //将链表中的元素按指数从高到低排列
{ f = p->coef;i = p->expn;
p->coef = q->coef;p->expn = q->expn;
q->coef = f;q->expn = i;
fini = 1;
}
}
for(g = h,p = g->next;p;) //比较将指数相同的数进行合并
if(g->expn==p->expn)
{g->coef += p->coef;
g->next = p->next; //合并后跳过一个元素，并删除该结点
q = p;
p = p->next;
free(q);
}
else
if(g->next)
{ g = g->next;
p = p->next;
}
return h;
}

void PrintfPoly(term *P)
{ //输出按指数从大到小排列后的一元多次式
term *q = P;
if(!q)
{
putchar('0');
return;
}
if(q->coef!=1)
{ printf("%g",q->coef);
//%g用来输出实数，它根据数值的大小，自动选f格式或e格式，且不输出无意义的0
if(q->expn==1) putchar('X'); //若指数值大小为1，则指数省略
else if(q->expn) printf("X^%d",q->expn);
}
else if(!q->expn) putchar('1');
else if(q->expn==1) putchar('X');
else printf("X^%d",q->expn);
q = q->next;
while (q)
{
if(q->coef > =0) putchar('+');
if(q->coef!=1)
{
printf("%g",q->coef);
if(q->expn==1) putchar('X');
else if(q->expn) printf("X^%d",q->expn);
}
else if(!q->expn) putchar('1');
else if(q->expn==1) putchar('X');
else printf("X^%d",q->expn);
q = q->next;
}
}
int Compare(term *a, term *b)
{
if (a->expn < b->expn) return -1;
if (a->expn > b->expn) return 1;
return 0;
}

float C(term *c,float x) //计算输入变量的多项式的值
{ float sum=0,a;
int b;
term *q=c;
for(;q ;q=q->next)
{ a=q->coef ;b=q->expn ;
sum+=a*pow(x,b);
}
return sum;
}

term* APolyn(term *Pa, term *Pb)
{ // 多项式加法：Pa = Pa＋Pb，运用两个多项式的结点构成"和多项式"。
term *h, *qa = Pa, *qb = Pb, *p, *q;
float sum;
h = p = (term*)malloc(sizeof(term));
p->next = NULL;
while (qa && qb)
{ // Pa和Pb均非空
switch (Compare(qa,qb))
{
case -1: // 多项式PA中当前结点的指数值小
p->next = qb;
p = qb;
qb = qb->next;
break;
case 0: // 两者的指数值相等
sum = qa->coef + qb->coef;
if (sum != 0.0)
{ // 修改多项式PA中当前结点的系数值
p->next = qa;
qa->coef = sum;
p = qa;
qa = qa->next;
}
else
{ // 删除多项式PA中当前结点
q = qa;
qa = qa->next;
free(q);
}
q = qb;
qb = qb->next;
free(q);
break;
case 1: // 多项式PB中当前结点的指数值小
p->next = qa;
p = qa;
qa = qa->next;
break;
} // 结束switch
} // 结束while
if (Pa) p->next = qa; // 链接Pa中剩余结点
if (Pb) p->next = qb; // 链接Pb中剩余结点
q = h;
h = h->next;
free(q);
return h;
} // APolyn
term* A(term *Pa, term *Pb)
{ int n;
printf("请输入第二个一元多项式的项数: ");
scanf("%d",&n);
Pb = CreatPolyn(Pb,n);
Pb = selsort(Pb);
cout<<"两个多项式相加结果为：";
PrintfPoly(Pa);
if(Pb && Pb->coef>0) printf(" + ");
PrintfPoly(Pb);
Pa = APolyn(Pa,Pb);
printf(" = ");
Pa = selsort(Pa);
PrintfPoly(Pa);
return Pa;
}
term* BPolyn(term *Pa, term *Pb)
{ // 多项式减法：Pa = Pa-Pb，运用两个多项式的结点构成"差多项式"。
term *p = Pb;
while(p)
{ p->coef *= -1;
p = p->next;
}
return APolyn(Pa,Pb);
} // BPolyn
term* B(term *Pa, term *Pb)
{ int n;
printf("请输入第二个一元多项式的项数: ");
scanf("%d",&n);
Pb = CreatPolyn(Pb,n);
Pb = selsort(Pb);
cout<<"两个多项式相减结果为：";
PrintfPoly(Pa);
printf(" - ");
putchar('(');PrintfPoly(Pb);putchar(')');
Pa = BPolyn(Pa,Pb);
printf(" = ");
Pa = selsort(Pa);
PrintfPoly(Pa);
return Pa;
}
void main()
{ term *M,*N;
term *q;
int i,j,n;
float x,y;
term *G[W];
int k;
f: puts("\t================ 一元多项式计算系统：===================");
printf("\n\t\t\t1:按照指数降序排列输出多项式\n\t\t\t2:一元多项式的加法运算");
printf("\n\t\t\t3:一元多项式的减法运算\n\t\t\t4:输入的多项式及变量的值计算结果");
puts("\n\t\t\t5:对多个输入的表达式按照指数从大到小排序输出\n\t\t\t0:退出系统");
puts("\t========================================================");
printf("\n请选择您要进行的操作：");
cin>>i;
switch(i)
{
case 1:
printf("\n\t\t\t按照指数降序排列输出多项式:\n请输入该一元多项式的项数: ");
scanf("%d",&n);
M = CreatPolyn(M,n);
M = selsort(M);
cout<<"您输入的多项式按指数降序排列为： ";
PrintfPoly(M);
cout<<endl<<endl;
goto f;
case 2:
printf("\n\t\t\t一元多项式加法计算:\n请输入第一个一元多项式的项数: ");
scanf("%d",&n);
M = CreatPolyn(M,n);
M = selsort(M);
M = A(M,N);
cout<<endl<<endl;
goto f;
case 3:
printf("\n\t\t\t一元多项式减法计算:\n请输入第一个一元多项式的项数: ");
scanf("%d",&n);
M = CreatPolyn(M,n);
M = selsort(M);
M = B(M,N);
cout<<endl<<endl;
goto f;
case 4:
printf("\n\t\t\t根据输入的多项式及变量的值进行计算:\n请输入您将要计算的一元多项式的项数: ");
scanf("%d",&n);
M = CreatPolyn(M,n);
M = selsort(M);
cout<<"您输入的一元多项式按指数降序排列为： ";
PrintfPoly(M);
cout<<"\n请输入变量x的值： ";
scanf("%f",&x);
y=C(M,x);
printf("多项式的值为: %f\n",y);
cout<<endl<<endl;
goto f;
case 5:
printf("\n\t\t\t对多个输入的表达式按照指数大小排序输出:\n请输入需要排序的一元多项式的个数: ");
scanf("%d",&k);
for(i=0;i<k;i++)
{ printf("请输入第%d个一元多项式的项数: ",i+1);
scanf("%d",&n);
M = CreatPolyn(M,n);
M = selsort(M);
G[i]=M; //用数组记住每一个多项式
}
for(j=0;j<k;j++)
for(i=1;i<k;i++)
if(G[i-1]->expn<G[i]->expn)
{ q=G[i];G[i]=G[i-1];G[i-1]=q;}
printf("输入的表达式按照指数从大到小排序输出结果为：\n");
for(i=0;i<k;i++)
{ printf("\t%d: ",i+1);
PrintfPoly(G[i]);
cout<<endl;
}
cout<<endl<<endl;
goto f;
case 0:
break;
printf("=================谢谢您使用该系统!==================\n");
default: puts("您输入的数据有误,请重新输入!");
goto f;
}
}