数据结构课程设计报告（一元多项式的计算）

Question

一元多项式计算**
任务：能够按照指数降序排列建立并输出多项式；
能够完成两个多项式的相加、相减，并将结果输入；

请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度

报告分为以下四个部分：

1)需求分析：
在该部分中叙述每个模块的功能要求
2)概要设计
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。
3）详细设计
各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
4）调试分析
测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考
请求高手帮帮忙！！！ 如果在网上搜索到设计报告可以附上链接！非常感谢！

源程序有了！那个需求分析和概要设计不会写！ 麻烦帮帮忙！

要求用C语言编写！还有哪位高手帮帮忙啊？！不胜感激！

Answer 1

【问题描述】
编程实现一元多项式的加法计算。
【基本要求】
能用链表实现一元多项式的加法计算，并能打印出计算结果。
【所需知识】
（1）基本编程方法和程序设计知识。
（2）链表的理解和运算与运用。
【所用算法】
遍历算法和递归算法。
【操作平台】
Visual C++

#include<stdio.h>
#include<graphics.h>
#define MAX 100
typedef struct polynode
{ float coef;
int expn;
struct polynode *next;
}node;

node * create(void) /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/
{
node *h,*r,*s;
float c;
int e;
h=(node *)malloc(sizeof(node)); /*建立多项式的头结点，为头结点分配存储空间*/
r=h; /*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
printf("coef:");
scanf("%f",&c); /*输入系数*/
printf("expn: ");
scanf("%d",&e); /*输入指数*/
while(c!=0.0) /*输入系数为0时，表示多项式的输入结束*/
{
s=(node *)malloc(sizeof(node)); /*申请新结点*/
s->coef=c; /*申请新结点后赋值*/
s->expn=e; /*申请新结点后赋值*/
r->next=s; /*做尾插，插入新结点*/
r=s; /*r始终指向单链表的表尾*/
printf("coef:");
scanf("%f",&c);
printf("expn: ");
scanf("%d",&e);
}
r->next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/
return(h);
}

void polyadd(node *pa, node *pb) /*一元多项式相加函数，用于将两个多项式相加，
然后将和多项式存放在多项式pa中，并将多项式pb删除*/
{
node *p,*q,*pre,*temp;
int sum;
p=pa->next; /*令p和q分别指向pa和pb多项式链表中的第一个结点*/
q=pb->next;
pre=pa; /*位置指针，指向和多项式pa*/
while(p!=NULL&&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/
{
if(p->expn<q->expn) /*若p指向的多项式指数小于q指的指数*/
{
pre->next=p; /*将p结点加入到和多项式中*/
pre=pre->next;
p=p->next;
}
if(p->expn==q->expn) /*若指数相等，则相应的系数相加*/
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;p=p->next;
temp=q;q=q->next;free(temp);
}
else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/
{
temp=p->next;free(p);p=temp;
temp=q->next;free(q);q=temp;
}
}
if (q->expn<p->expn)
{
pre->next=q; /*将q结点加入到和多项式中*/
pre=pre->next;
q=q->next;
}
}
if(p!=NULL) /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/
pre->next=p;
else /*否则将B的结点加入到和多项式中*/
pre->next=q;
}

void print(node * p) /*输出函数，打印出一元多项式*/
{
while(p->next!=NULL)
{
p=p->next;
printf(" %f*x^%d",p->coef,p->expn);
}
}

void calculate() /*给多项式赋值并计算*/
{ float cal=1.0,mid=0.0,las;
int j;
float num, x;
int i=0;
float later=0.0;
int e[MAX];float c[MAX];
printf("Please input num:"); /*输入常数的值*/
scanf("%f",&num);
printf("Please input x:"); /*输入未知数X的值*/
scanf("%f",&x);
printf("Please input e[0]:"); /*输入数组的初值以判断是否循环*/
scanf("%d",&e[0]);
printf("Please input c[0]:");
scanf("%f",&c[0]);
while(e[i]!=0 && c[i]!=0.0 ) /*此循环用于多项式的计算*/
{ cal=1;
for(j=0;j<e[i];j++) /*表示出X的几次方*/
{
cal=cal*x;
}
i++;
mid=cal*c[i-1]; /*表示出单项*/
later+=mid;
printf("Please input e[%d] and c[%d] :",i,i);
scanf("%d%f",&e[i],&c[i]);

}
las=later+num; /*表示出完整的多项式*/
printf("The Result is :\n");
printf("%f",las); /*最终的计算结果*/
sleep(3);

}
void main()
{
node * pa,* pb,*pc,*p,*q,*pre;
int driver=VGA,mode=VGAHI;
initgraph(&driver,&mode,"c:\\tc ");
setbkcolor(BLUE);
setcolor(RED);
printf("Welcome,Let's go!\n");
printf("Next, you will see the process of computing !");
printf("\nPlease input the coef and expn of pa:\n");
pa=create(); /*调用建立链表函数，创建多项式A*/
print(pa);
printf("\nPlease input the coef and expn of pb:\n");
pb=create(); /*同理，创建B*/
print(pb);
p=pa->next; /*以下代码用于排序*/
pa->next=NULL;
while(p!=NULL)
{
if(pa->next==NULL)
{
pa->next=p;p=p->next;
pa->next->next=NULL;
}
else
{ pre=pa;q=pre->next;
while(q!=NULL && p->expn>q->expn)
{
pre=q;q=q->next;
}
q=p->next;
p->next=pre->next;
pre->next=p;
p=q;

}
}
printf("\nthe first ordered one:\n");print(pa); /*输出排序后的pa*/
p=pb->next; /*以下代码用于给pb排序*/
pb->next=NULL;
while(p!=NULL)
{
if(pb->next==NULL)
{
pb->next=p;p=p->next;
pb->next->next=NULL;
}
else
{ pre=pb;q=pre->next;
while(q!=NULL && p->expn>q->expn)
{
pre=q;q=q->next;
}
q=p->next;
p->next=pre->next;
pre->next=p;
p=q;

}
}
printf("\nthe second ordered one:\n");print(pb); /*输出排序后的pb*/
printf("\nSum of the polys is:\n");
polyadd(pa,pb); /*调用一元多项式相加函数*/
print(pa); /*调用输出函数，打印结果*/
printf("\n");
setbkcolor(RED);
calculate(); /*调用计算多项式值的函数*/
}

【编后总结】
本程序在逻辑设计，详细设计，程序编码和程序调试阶段时本来都城有设计save()保存函数，和load()下载函数，分别用来保存创建的多项式，和下载其它需计算的多项式数据，这样这个系统才能更加实用，void createadj()原来的函数原型为arcnode *createdj()函数中用链表结构把adjmatrix[][]的数据都保存其中，这样就能实现数据的保存，但随之要把Dijkstra中的adjmatrix[][]转换成用arcnode 指针的形式进行表示，因为只有这样，下载后的数据才能使用。但在最后的调试阶段中，发现dijkstra无法运行，但又苦于无法用save()函数保存adjmatrix[][],最后只放弃save()和load()函数，在 main()主函数中初始化该算式。从这次程序设计中我看到自己的不足之处，今后要更努力的学习和掌握好数据结构程序设计的知识。

Answer 2

#include "stdafx.h"
#include "iostream"
using namespace std;
#define MAXSIZE 10
typedef struct
{
int xi;
int zhi;
}DataType;
typedef struct node
{
DataType data[MAXSIZE];
int length;
}Dx,*PDx;
PDx Init_List()
{
Dx *S;
S=(Dx *)malloc(sizeof(Dx));
if(S)
S->length=0;
return S;
}
int Empty(Dx *S)
{
if(S->length==0)
return 1;
else return 0;
}
int In_list(Dx *S,DataType a)//建立多项式存储结构
{
if(S&&S->length<MAXSIZE)
{
S->length++;
S->data[S->length-1]=a;
return 1;
}
else return 0;
}
int Insert_list(Dx *S,int j,DataType e)//插入
{
if(S&&S->length<MAXSIZE)
{
S->length++;
for(int i=S->length-1;i>j;i--)
S->data[i]=S->data[i-1];
S->data[j]=e;
return 1;
}
else return 0;
}
int Delete_list(Dx *S,int m)//m就是数组下标
{
if(!S)
{
cout<<"多项式不存在！"<<endl;
return -1;
}
if(m<1||m>S->length)
{
cout<<"删除位置不合法！"<<endl;
return 0;
}
for(int j=m;j<S->length;j++)
S->data[j-1]=S->data[j];
S->length--;
return 1;
}
PDx Luru(int n)//录入多项式，并存储起来,n为多项式的项数！
{
Dx *S;
S=Init_List();
DataType e;
cout<<"按从高指数到低指数，输入一元多项式的系数和指数；"<<endl;
for(int i=0;i<n;i++)
{
cout<<"指数：";
cin>>e.zhi;
if((S->length-1>=0&&e.zhi>=S->data[S->length-1].zhi)||e.zhi<0)
{
i--;
cout<<"输入指数大于前一项错误请重输或小于0！"<<endl;
continue;
}
cout<<"系数：";
cin>>e.xi;
In_list(S,e);
}
return S;
}
void print(Dx *S)
{
for(int i=0;i<S->length;i++)
{
if(i>0&&S->data[i].xi>=0)
cout<<"+";
cout<<S->data[i].xi<<"X^"<<S->data[i].zhi;
}
cout<<endl;
}
PDx Add(Dx *S1,Dx *S2)
{
Dx *S3;
S3=Init_List();
for(int x=0;x<S1->length;x++)
{
S3->length++;
S3->data[S3->length-1]=S1->data[x];
}
for(int i=0;i<S2->length;i++)
{ for(int j=0;j<S3->length;j++)
{
if(S2->data[i].zhi==S3->data[j].zhi)
{
S3->data[j].xi+=S2->data[i].xi;
break;
}
else if(S2->data[i].zhi>S3->data[j].zhi)
{
Insert_list(S3,j,S2->data[i]);
break;
}
}
if(S2->data[i].zhi<S3->data[S3->length-1].zhi)
{
In_list(S3,S2->data[i]);
}
}
return S3;
}
PDx Sub(Dx *S1,Dx *S2)//S1-S2
{
Dx *S3;
S3=Init_List();
DataType e;
for(int x=0;x<S1->length;x++)
{
S3->length++;
S3->data[S3->length-1]=S1->data[x];
}
for(int i=0;i<S2->length;i++)
{ for(int j=0;j<S3->length;j++)
{
if(S2->data[i].zhi==S3->data[j].zhi)
{
S3->data[j].xi-=S2->data[i].xi;
if(S3->data[j].xi==0)
Delete_list(S3,j+1);
break;
}
else if(S2->data[i].zhi>S3->data[j].zhi)
{
e=S2->data[i];
e.xi=-1*e.xi;
Insert_list(S3,j,e);
break;
}
}
if(S2->data[i].zhi<S3->data[S3->length-1].zhi)
{
e=S2->data[i];
e.xi=-1*e.xi;
In_list(S3,e);
}
}
return S3;
}
PDx Bin(Dx *S1,Dx *S2)
{
Dx *S3;
S3=Init_List();
DataType e,a;
a.xi=0;
a.zhi=0;
In_list(S3,a);
for(int i=0;i<S1->length;i++)
for(int j=0;j<S2->length;j++)
{
e.xi=S1->data[i].xi*S2->data[j].xi;
e.zhi=S1->data[i].zhi*S2->data[j].zhi;
for(int k=0;k<S3->length;k++)
{
if(e.zhi==S3->data[k].zhi)
{
S3->data[k].xi+=S2->data[j].xi;
break;
}
else if(e.zhi>S3->data[k].zhi)
{
Insert_list(S3,k,e);
break;
}
if(S3->length-2>=0&&e.zhi<S3->data[S3->length-2].zhi)
{
Insert_list(S3,S3->length-1,e);
}
}
}
return S3;
}

int _tmain(int argc, _TCHAR* argv[])
{
Dx *S1,*S2,*S3,*S4,*S5;
int i,j;
cout<<"要录入的1多项式项数:";
cin>>i;
S1=Luru(i);
cout<<"要录入的2多项式项数:";
cin>>j;
S2=Luru(j);
S3=Add(S1,S2);
S4=Sub(S1,S2);
S5=Bin(S1,S2);
cout<<"第一个多项式:"<<endl;
print(S1);
cout<<"第二个多项式:"<<endl;
print(S2);
cout<<"两多项式的和:"<<endl;
print(S3);
cout<<"两多项式的差"<<endl;
print(S4);
cout<<"两多项式的积"<<endl;
print(S5);
return 0;
}本回答被提问者采纳