数据结构课程设计
20##年 7 月 14 日
目录
一、 课程题目………………………………………………………1
二、 需求分析………………………………………………………1
三、 测试数据………………………………………………………2
四、 概要设计………………………………………………………2
五、 调用关系图……………………………………………………3
六、 程序代码………………………………………………………3
七、 心得体会及总结………………………………………………12
数据结构课程设计
一、课程题目
一元稀疏多项式计算器
二、需求分析
1、一元稀疏多项式简单计算器的功能是:
1.1 输入并建立多项式;
1.2 输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,………cn,en,其中n是多项式的项数,ci和ei分别是第i项的系数和指数,序列按指数降序排列;
1.3 求多项式a、b的导函数;
1.4 计算多项式在x处的值;
1.5多项式a和b相加,建立多项式a+b;
1.6 多项式a和b相减,建立多项式a-b。
2、设计思路:
2.1 定义线性表的动态分配顺序存储结构;
2.2 建立多项式存储结构,定义指针*next
2.3利用链表实现队列的构造。每次输入一项的系数和指数,可以输出构造的一元多项式
2.4演示程序以用户和计算机的对话方式执行,即在计算机终站上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运行命令;最后根据相应的输入数据(滤去输入中的非法字符)建立的多项式以及多项式相加的运行结果在屏幕上显示。多项式显示的格式为:c1x^e1+c2x^e2+…+cnx^en
3、设计思路分析
要解决多项式相加,必须要有多项式,所以必须首先建立两个多项式,在这里采用链表的方式存储链表,所以我将结点结构体定义为
运用尾插法建立两条单链表,以单链表polyn p和polyn h分别表示两个一元多项式a和b,a+b的求和运算等同于单链表的插入问题(将单链表polyn p中的结点插入到单链表polyn h中),因此“和多项式”中的结点无须另生成。
为了实现处理,设p、q分别指向单链表polya和polyb的当前项,比较p、q结点的指数项,由此得到下列运算规则:
① 若p->expn<q->expn,则结点p所指的结点应是“和多项式”中的一项,令指针p后移。
② 若p->expn=q->expn,则将两个结点中的系数相加,当和不为0时修改结点p的系数。
③ 若p->expn>q->expn,则结点q所指的结点应是“和多项式”中的一项,将结点q插入在结点p之前,且令指针q在原来的链表上后移。
三、测试数据:
1、(2x+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7);
2、(6x^-3-x+4.4x^2-1.2x^9+1.2x^9)-(-6x^-3+5.4x^2-x^2+7.8x^15
)=(-7.8x^15-1.2x^9+12x^-3-x);
3、(1+x+x^2+x^3+x^4+x^5)+(-x^3-x^4)=(1+x+x^2+x^5);
4、(x+x^3)+(-x-x^3)=0;
5、(x+x^100)+(x^100+x^200)=(x+2x^100+x^200);
6、(x+x^2+x^3)+0=x+x^2+x^3.
四、概要设计
1、元素类型、结点类型和指针类型:
typedef struct Polynomial{
float coef; //系数
int expn; //指数
struct Polynomial *next;
}*Polyn,Polynomial;
2、建立一个头指针为head、项数为m的一元多项式, 建立新结点以接收数据, 调用Insert函数插入结点:
Polyn CreatePolyn(Polyn head,int m){
int i;
Polyn p;
p=head=(Polyn)malloc(sizeof(struct Polynomial));
head->next=NULL;
for(i=0;i<m;i++)
{
p=(Polyn)malloc(sizeof(struct Polynomial));
printf("请输入第%d项的系数与指数:",i+1);
scanf("%f %d",&p->coef,&p->expn);
Insert(p,head);
}
return head;
}
3、主函数和其他函数:
void main()
{
int m,n,a,x;
char flag;
Polyn pa=0,pb=0,pc;
}
float ValuePolyn(Polyn head,int x) //输入x值,计算并返回多项式的值
五、调用关系图(图1)
六、程序代码:
#include<stdio.h>
#include<stdlib.h> //定义多项式的项
typedef struct Polynomial{
float coef; //系数
int expn; //指数
struct Polynomial *next;
}*Polyn,Polynomial;
void Insert(Polyn p,Polyn h){
if(p->coef==0) free(p); //系数为0的话释放结点
else
{
Polyn q1,q2;
q1=h;
q2=h->next;
while(q2&& p->expn < q2->expn)
{ //查找插入位置
q1=q2;
q2=q2->next;
}
if(q2&& p->expn == q2->expn)
{ //将指数相同相合并
q2->coef += p->coef;
free(p);
if(!q2->coef)
{ //系数为0的话释放结点
q1->next=q2->next;
free(q2);
}
}
else
{ //指数为新时将结点插入
p->next=q2;
q1->next=p;
}
}
}
Polyn CreatePolyn(Polyn head,int m){ //建立一个头指针为head、项数为m的一元多项式
int i;
Polyn p;
p=head=(Polyn)malloc(sizeof(struct Polynomial));
head->next=NULL;
for(i=0;i<m;i++)
{
p=(Polyn)malloc(sizeof(struct Polynomial)); //建立新结点以接收数据
printf("请输入第%d项的系数与指数:",i+1);
scanf("%f %d",&p->coef,&p->expn);
Insert(p,head); //调用Insert函数插入结点
}
return head;
}
void DestroyPolyn(Polyn p){ //销毁多项式p
Polyn q1,q2;
q1=p->next;
q2=q1->next;
while(q1->next)
{
free(q1);
q1=q2;
q2=q2->next;
}
}
void PrintPolyn(Polyn P){
Polyn q=P->next;
int flag=1; //项数计数器
if(!q)
{ //若多项式为空,输出0
putchar('0');
printf("\n");
return;
}
while(q)
{
if(q->coef>0&& flag!=1) putchar('+'); //系数大于0且不是第一项
if(q->coef!=1&&q->coef!=-1)
{ //系数非1或-1的普通情况
printf("%g",q->coef);
if(q->expn==1) putchar('X');
else if(q->expn) printf("X^%d",q->expn);
}
else
{
if(q->coef==1)
{
if(!q->expn) putchar('1');
else if(q->expn==1) putchar('X');
else printf("X^%d",q->expn);
}
if(q->coef==-1)
{
if(!q->expn) printf("-1");
else if(q->expn==1) printf("-X");
else printf("-X^%d",q->expn);
}
}
q=q->next;
flag++;
}
printf("\n");
}
int compare(Polyn a,Polyn b){
if(a&&b)
{
if(!b||a->expn>b->expn) return 1;
else if(!a||a->expn<b->expn) return -1;
else return 0;
}
else if(!a&&b) return -1; //a多项式已空,但b多项式非空
else return 1; //b多项式已空,但a多项式非空
}
Polyn AddPolyn(Polyn pa,Polyn pb){ //求解并建立多项式a+b,返回其头指针
Polyn qa=pa->next;
Polyn qb=pb->next;
Polyn headc,hc,qc;
hc=(Polyn)malloc(sizeof(struct Polynomial)); //建立头结点
hc->next=NULL;
headc=hc;
while(qa||qb)
{
qc=(Polyn)malloc(sizeof(struct Polynomial));
switch(compare(qa,qb)){
case 1:
{
qc->coef=qa->coef;
qc->expn=qa->expn;
qa=qa->next;
break;
}
case 0:
{
qc->coef=qa->coef+qb->coef;
qc->expn=qa->expn;
qa=qa->next;
qb=qb->next;
break;
}
case -1:
{
qc->coef=qb->coef;
qc->expn=qb->expn;
qb=qb->next;
break;
}
}
if(qc->coef!=0)
{
qc->next=hc->next;
hc->next=qc;
hc=qc;
}
else free(qc); //当相加系数为0时,释放该结点
}
return headc;
}
Polyn SubtractPolyn(Polyn pa,Polyn pb){ //求解并建立多项式a-b,返回其头指针
Polyn h=pb;
Polyn p=pb->next;
Polyn pd;
while(p)
{ //将pb的系数取反
p->coef*=-1;
p=p->next;
}
pd=AddPolyn(pa,h);
for(p=h->next;p;p=p->next) //恢复pb的系数
p->coef*=-1;
return pd;
}
float ValuePolyn(Polyn head,int x){ //输入x值,计算并返回多项式的值
Polyn p;
int i,t;
float sum=0;
for(p=head->next;p;p=p->next)
{
t=1;
for(i=p->expn;i!=0;)
{
if(i<0){t/=x;i++;} //指数小于0,进行除法
else{t*=x;i--;} //指数大于0,进行乘法
}
sum+=p->coef*t;
}
return sum;
}
Polyn Derivative(Polyn head){ //求解并建立导函数多项式,并返回其头指针
Polyn q=head->next,p1,p2,hd;
hd=p1=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点
hd->next=NULL;
while(q)
{
if(q->expn!=0)
{ //该项不是常数项时
p2=(Polyn)malloc(sizeof(struct Polynomial));
p2->coef=q->coef*q->expn;
p2->expn=q->expn-1;
p2->next=p1->next; //连接结点
p1->next=p2;
p1=p2;
}
q=q->next;
}
return hd;
}
Polyn MultiplyPolyn(Polyn pa,Polyn pb){ //求解并建立多项式a*b,返回其头指针
Polyn hf,pf;
Polyn qa=pa->next;
Polyn qb=pb->next;
hf=(Polyn)malloc(sizeof(struct Polynomial));//建立头结点
hf->next=NULL;
for(;qa;qa=qa->next)
{
for(qb=pb->next;qb;qb=qb->next)
{
pf=(Polyn)malloc(sizeof(struct Polynomial));
pf->coef=qa->coef*qb->coef;
pf->expn=qa->expn+qb->expn;
Insert(pf,hf); //调用Insert函数以合并指数相同的项
}
}
return hf;
}
void main()
{
int m,n,a,x;
char flag;
Polyn pa=0,pb=0,pc;
printf(" --------------------------------------------------\n");
printf(" | ***班 *** ******** |\n");
printf(" --------------------------------------------------\n");
printf(" 欢迎使用多项式操作程序\n");
printf("请输入a的项数:");
scanf("%d",&m);
pa=CreatePolyn(pa,m); //建立多项式a
printf("请输入b的项数:");
scanf("%d",&n);
pb=CreatePolyn(pb,n); //建立多项式b
//输出菜单
printf(" **************************************************\n");
printf(" * 多项式操作程序 *\n");
printf(" * *\n");
printf(" * A:输出多项式a B:输出多项式b *\n");
printf(" * *\n");
printf(" * C:输出a的导数 D:输出b的导数 *\n");
printf(" * *\n");
printf(" * E:代入x的值计算a F:代入x的值计算b *\n");
printf(" * *\n");
printf(" * G:输出a+b H:输出a-b *\n");
printf(" * *\n");
printf(" * I:输出a*b J:退出程序 *\n");
printf(" * *\n");
printf(" *************************************************\n");
while(a)
{
printf("\n请选择操作:");
scanf(" %c",&flag);
switch(flag)
{
case'A':
case'a':
{
printf("\n 多项式a=");
PrintPolyn(pa);
break;
}
case'B':
case'b':
{
printf("\n 多项式b=");
PrintPolyn(pb);
break;
}
case'C':
case'c':
{
pc=Derivative(pa);
printf("\n 多项式a的导函数为:a'=");
PrintPolyn(pc);
break;
}
case'D':
case'd':
{
pc=Derivative(pb);
printf("\n 多项式b的导函数为:b'=");
PrintPolyn(pc);
break;
}
case'E':
case'e':
{
printf("输入x的值:x=");
scanf("%d",&x);
printf("\n x=%d时,a=%.3f\n",x,ValuePolyn(pa,x));
break;
}
case'F':
case'f':
{
printf("输入x的值:x=");
scanf("%d",&x);
printf("\n x=%d时,b=%.3f\n",x,ValuePolyn(pb,x));
break;
}
case'G':
case'g':
{
pc=AddPolyn(pa,pb);
printf("\n a+b=");
PrintPolyn(pc);
break;
}
case'H':
case'h':
{
pc=SubtractPolyn(pa,pb);
printf("\n a-b=");
PrintPolyn(pc);
break;
}
case'I':
case'i':
{
pc=MultiplyPolyn(pa,pb);
printf("\n a*b=");
PrintPolyn(pc);
break;
}
case'J':
case'j':
{
printf("\n 感谢使用此程序!\n");
DestroyPolyn(pa);
DestroyPolyn(pb);
a=0;
break;
}
default:
printf("\n 您的选择错误,请重新选择!\n");
}
}
}
七、心得体会及总结
通过这次课程设计,我感觉到要真正做出一个程序并不很容易,但只要用心去做,总会有收获,特别是当我遇到问题,与同学互相探讨,想尽办法去解决,最后终于找到方法时,心里的那份喜悦之情真是难以形容.编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清为止。
对于数据结构有了更深层次的理解,循环队列中对边界条件的处理,满足什么条件为队满,满足什么条件为队空。