目录
实验要求
完整代码
逻辑设计
哈喽各位好，我是李博轩，一个刚转到计算机的大二学生。这个标题是随手打上去的，感觉还蛮顺口，就这样了。
这个学期在学【数据结构与算法】，而这是我面对的第一个实验题。因为大一不在计算机，编程能力落后于人，这个作业也花了很多时间和精力。总之，下面把题目要求和代码附上，希望得到各位的指点。
实验要求
以动态或者静态链表存储一元多项式，在此基础上按要求完成对一元多项式的运算。（为保证多项式的值的准确性，多项式的系数可以用分数表示，涉及到两个分数相除时，结果也可以用分数表示。）
1. 能够输入多项式（可以按各项的任意输入顺序，建立按指数降幂排列的多项式）和输出多项式（按指数降幂排列）,以文件形式输入和输出，并显示。
2. 能够给出计算两个多项式加法、减法、乘法和除法运算的结果多项式，除法运算的结果包括商多项式和余数多项式。
3. 能够计算一元多项式的 k 阶导函数。
4. 能够计算多项式在某一点 x=x0 的值，其中 x0是一个浮点型常量，返回结果为浮点数。
5. 要求尽量减少乘法和除法运算中间结果的空间占用和结点频繁的分配与回收操作。（提示：利用循环链表结构或者可用空间表的思想，把循环链表表示的多项式返还给系统或者可用空间表，从而解决上述问题）。
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXSIZE 4096
#define MAXLEN 256
typedef struct{
int numerator; //分子
int denumerator;//分母
int index; //指数
}elemtype;
typedef struct{
elemtype val;
int next; //下一结点的指针
}LISTNODE;
LISTNODE SPACE[MAXSIZE]; //储存池
typedef int position, head; //表头和指针
head av = 0, L;
//初始化存储池
head load[MAXLEN] = {-1};
head save[MAXLEN] = {-1};
int loaded = 0; //是否已经加载
head cursor_s1 = -1; //游标1
head cursor_s2 = -1; //游标2
int cursor_save = 0; //保存用
int cursor_load = 0; //加载用
int number_load = 0; //加载数量
int number_save = 0; //结果数量
char cursor_menu = '9'; //菜单
//初始化菜单
void Init(){ //DONE!
printf("正在初始化中...\n");
//链接结点
int i;
for(i=0; i<MAXSIZE-1; i++){
SPACE[i].val.numerator = 0;
SPACE[i].val.denumerator = 1;
SPACE[i].val.index = 0;
SPACE[i].next = i+1;
}
//设定表尾
SPACE[i].val.numerator = 0;
SPACE[i].val.denumerator = 1;
SPACE[i].val.index = 0;
SPACE[i].next = -1;
//表示可用线性表
av = 0;
};
//获得可用空间
position GetNode(){ //DONE!!
position p;
if(SPACE[av].next==-1){
p = -1;
printf("可用空间为空！\n");
}else{
p = SPACE[av].next;
SPACE[av].next = SPACE[p].next;
}
return p;
};
//回收可用空间
void FreeNode(position p){ //DONE!
SPACE[p].next = SPACE[av].next;
SPACE[av].next = p;
};
//创建链表
head Create(void){ //DONE!
head p;
if(SPACE[av].next==-1){
p = -1;
printf("创建链表时可用空间不足！\n");
}
else{
p = GetNode();
position q = GetNode();
SPACE[p].next = q;
SPACE[q].next = -1;
}
return p;
};
//链表插入
void Insert(elemtype x,position p){ //DONE!
position q = GetNode();
SPACE[q].val = x;
SPACE[q].next = SPACE[p].next;
SPACE[p].next = q;
};
//链表删除
void Delete(position p){ //DONE! （注：删除当前而非下一位）
if(SPACE[p].next!=-1){
position q = SPACE[p].next;
SPACE[p].next = SPACE[q].next;
SPACE[p].val = SPACE[q].val;
FreeNode(q);
}
};
//找到末尾元素
position End(head p){ //DONE!!
position q = p;
while(SPACE[SPACE[q].next].next!=-1){
q = SPACE[q].next;
}
return q;
};
//找到起始元素
position First(head p){ //DONE!!
//清空链表
return SPACE[p].next;
};
head Destory(head L){ //DONE!!
position p =First(L);
position q = p;
while(SPACE[p].next!=-1){
q = p;
p = SPACE[p].next;
FreeNode(q);
}
};
//复制链表
head Copy(head L){ //DONE!!
head newone = Create();
position p =First(L);
while(SPACE[p].next!=-1){
Insert(SPACE[p].val,End(newone));
p = SPACE[p].next;
}
return newone;
};
void MENU(void); //陈列功能
void DISPLAY(void); //显示全部多项式
void SELECT(void); //重新选择多项式
void COLLECT(void); //加载结果多项式
void SAVE(void); //保存输出多项式
head INPUT(void);
void LOAD(FILE* STR);
void SHOW(head L);
void LAST(void);
head PLUS(head L1,head L2);
head SUBTRACT(head L1,head L2);
head MULTIPLY(head L1,head L2);
void DIVIDE(head L1,head L2);
head DERIVALTIVE(head L);
double VALUE(head L,double x);
void CLEAR(head L);
head ZERO();
elemtype fractionPlus(elemtype a,elemtype b);
elemtype fractionSubtract(elemtype a,elemtype b);
elemtype fractionMultiply(elemtype a,elemtype b);
elemtype fractionDivide(elemtype a,elemtype b);
elemtype fractionGCD(elemtype x);
int main(){
Init();
MENU();
FILE *str;
str = fopen("INPUT.txt","r");
if(str == NULL){
printf("打开文件失败！");
exit(0);
}
LOAD(str);
DISPLAY();
SELECT();
while(cursor_menu!='0'){
getchar();
printf("请选择功能：");
scanf("%c",&cursor_menu);
switch (cursor_menu){
case 'A':{
DISPLAY();
}break;
case 'B':{
SELECT();
}break;
case 'C':{
head newone = INPUT();
printf("输入为：\n");
SHOW(newone);
load[number_load] = newone;
number_load ++;
save[cursor_save] = newone;
cursor_save++;
number_load = cursor_load;
}break;
case 'D':{
COLLECT();
number_load = cursor_load;
}break;
case 'E':{
SAVE();
}break;
case 'F':{
LAST();
}break;
case 'H':{
MENU();
}break;
case '1':{
head newone = PLUS(load[cursor_s1],load[cursor_s2]);
printf("和为：\n");
SHOW(newone);
save[cursor_save] = newone;
cursor_save++;
}break;
case '2':{
head newone = SUBTRACT(load[cursor_s1],load[cursor_s2]);
printf("差为：\n");
SHOW(newone);
save[cursor_save] = newone;
cursor_save++;
}break;
case '3':{
head newone = MULTIPLY(load[cursor_s1],load[cursor_s2]);
printf("积为：\n");
SHOW(newone);
save[cursor_save] = newone;
cursor_save++;
}break;
case '4':{
DIVIDE(load[cursor_s1],load[cursor_s2]);
}break;
case '5':{
head newone = DERIVALTIVE(load[cursor_s1]);
printf("导数为：\n");
SHOW(newone);
save[cursor_save] = newone;
cursor_save++;
}break;
case '6':{
printf("请输入求值的点：");
double x;
scanf("%lf",&x);
VALUE(load[cursor_s1],x);
}break;
}
}
printf("正在关机...\n");
fclose(str);
}
head INPUT(void){ //DONE!!
printf("请按照“系数分子/系数分母 指数”的顺序输入多项式，分母为0结束：\n");
printf("例：-1/2 2 3/1 4 4/1 3 3/2 5 1/0 1\n");
int fz, fm, zh;
head newone = Create();
int count = 0;
while(1){
scanf("%d/%d %d",&fz,&fm,&zh);
if(fm == 0) break;
count += 1;
elemtype x;
x.numerator = fz;
x.denumerator = fm;
x.index = zh;
Insert(x,End(newone));
}
for(int i=0; i<count-1;i++){
position p = SPACE[newone].next;
for(int j=0; j<count-1-i;j++){
if((SPACE[p].val.index)<(SPACE[SPACE[p].next].val.index)){
elemtype temp = SPACE[p].val;
SPACE[p].val = SPACE[SPACE[p].next].val;
SPACE[SPACE[p].next].val = temp;
}
p = SPACE[p].next;
}
}
CLEAR(newone);
return newone;
}
void LOAD(FILE* STR){ //DONE!!
if(loaded == 0){
printf("正在从文件中读取多项式...\n");
fscanf(STR,"%d",&number_load);
printf("读取到%d个多项式!!\n",number_load);
cursor_load = 0;
int fz, fm, zh;
while(cursor_load < number_load && number_load < MAXLEN){
head newone = Create();
int count = 0;
while(1){
fscanf(STR,"%d/%d %d",&fz,&fm,&zh);
if(fm == 0) break;
elemtype x;
x.numerator = fz;
x.denumerator = fm;
x.index = zh;
Insert(x,End(newone));
count ++;
}
for(int i=0; i<count-1;i++){
position p = First(newone);
for(int j=0; j<count-1-i;j++){
if((SPACE[p].val.index)<(SPACE[SPACE[p].next].val.index)){
elemtype temp = SPACE[p].val;
SPACE[p].val = SPACE[SPACE[p].next].val;
SPACE[SPACE[p].next].val = temp;
}
p = SPACE[p].next;
}
}
load[cursor_load] = newone;
cursor_load ++;
}
loaded = 1;
return;
}
else printf("多项式已加载！\n");
}
void SHOW(head L){ //DONE!!
position p = First(L);
printf("\t\t");
while(SPACE[p].next!=-1){
if(SPACE[p].val.index==0){
printf("(%d/%d)",SPACE[p].val.numerator,SPACE[p].val.denumerator);
}else{
printf("(%d/%d) x^%d",SPACE[p].val.numerator,SPACE[p].val.denumerator,SPACE[p].val.index);
}
if(SPACE[SPACE[p].next].next!=-1) printf(" + ");
p = SPACE[p].next;
}
printf("\n");
}
head PLUS(head L1,head L2){ //DONE!!
head newone = Create();
head List1 = Copy(L1);
head List2 = Copy(L2);
//SHOW(List1);
//SHOW(List2);
position p1 = First(List1);
position p2 = First(List2);
while(SPACE[p1].next!=-1&&SPACE[p2].next!=-1){
if(SPACE[p1].val.index>SPACE[p2].val.index){
elemtype x = SPACE[p1].val;
Insert(x,End(newone));
p1 = SPACE[p1].next;
}
else if(SPACE[p1].val.index<SPACE[p2].val.index){
elemtype x = SPACE[p2].val;
Insert(x,End(newone));
p2 = SPACE[p2].next;
}
else if(SPACE[p1].val.index==SPACE[p2].val.index){
elemtype x = fractionPlus(SPACE[p1].val,SPACE[p2].val);
Insert(x,End(newone));
p1 = SPACE[p1].next;
p2 = SPACE[p2].next;
}
else{
printf("ERROR WHEN PLUS!!\n");
}
}
SPACE[End(newone)].next = (SPACE[p1].next==-1)?p2:p1;
CLEAR(newone);
return newone;
}
head SUBTRACT(head L1,head L2){ //DONE!!
head newone = Create();
head List1 = Copy(L1);
head List2 = Copy(L2);
//SHOW(List1);
//SHOW(List2);
position p1 = First(List1);
position p2 = First(List2);
while(SPACE[p1].next!=-1&&SPACE[p2].next!=-1){
elemtype x = SPACE[p1].val;
elemtype y = SPACE[p2].val;
if(SPACE[p1].val.index>SPACE[p2].val.index){
Insert(x,End(newone));
p1 = SPACE[p1].next;
}
else if(SPACE[p1].val.index<SPACE[p2].val.index){
y.numerator *= -1;
Insert(y,End(newone));
p2 = SPACE[p2].next;
}
else{
elemtype z = fractionSubtract(x,y);
Insert(z,End(newone));
p1 = SPACE[p1].next;
p2 = SPACE[p2].next;
}
}
if(SPACE[p2].next==-1){
SPACE[End(newone)].next = p1;
CLEAR(newone);
return newone;
}
while(SPACE[p2].next!=-1){
elemtype y = SPACE[p2].val;
y.numerator *= -1;
Insert(y,End(newone));
p2 = SPACE[p2].next;
}
CLEAR(newone);
return newone;
}
head MULTIPLY(head L1,head L2){ //DONE!!
position p = First(L1); int s1 = SPACE[p].val.index;
position q = First(L2); int s2 = SPACE[q].val.index;
head* arrL = (head*) malloc(sizeof(position)*(s1+1)*(s2+1));
int count = 0;
while(SPACE[p].next!=-1){
arrL[count] = Create();
q = First(L2);
while(SPACE[q].next!=-1){
elemtype newnode = fractionMultiply(SPACE[p].val,SPACE[q].val);
Insert(newnode,End(arrL[count]));
q = SPACE[q].next;
//printf("q动了一下！");
}
//printf("p动了一下！");
count ++;
p = SPACE[p].next;
}
//printf("需要相加的有%d个式子:\n",count);
head* L = (head*) malloc(sizeof(position)*(s1+s2+1));
L[0] = ZERO();
for(int i=0; i<count; i++){
L[i+1] = Create();
//printf("第%d个式子为：",i+1);
//SHOW(arrL[i]);
//SHOW(L[i]);
L[i+1] = PLUS(L[i],arrL[i]);
//printf("第%d个he式为：",i+1);
//SHOW(L[i+1]);
}
free(arrL); arrL = NULL;
CLEAR(L[count]);
return L[count];
}
elemtype fractionMultiply(elemtype a,elemtype b){ //DONE!!
elemtype x;
x.index = a.index + b.index;
x.numerator = a.numerator * b.numerator;
x.denumerator = a.denumerator * b.denumerator;
return fractionGCD(x);
}
elemtype fractionPlus(elemtype a,elemtype b){
if(a.index!=b.index){
printf("指数不同无法相加！\n");
return a;
}
int fz1 = a.numerator; int fm1 = a.denumerator;
int fz2 = b.numerator; int fm2 = b.denumerator;
int fz = fz1*fm2 + fz2*fm1; int fm = fm1*fm2;
elemtype x;
x.numerator = fz;
x.denumerator = fm;
x.index = a.index;
return fractionGCD(x);
}
elemtype fractionSubtract(elemtype a,elemtype b){
if(a.index!=b.index){
printf("指数不同无法相减！\n");
return a;
}
int fz1 = a.numerator; int fm1 = a.denumerator;
int fz2 = b.numerator; int fm2 = b.denumerator;
int fz = fz1*fm2 - fz2*fm1; int fm = fm1*fm2;
elemtype x;
x.numerator = fz;
x.denumerator = fm;
x.index = a.index;
return fractionGCD(x);
}
elemtype fractionGCD(elemtype x){ //DONE!!
int fz = abs(x.numerator);
int fm = abs(x.denumerator);
if(fm==0){
printf("出现分母为零!\n");
return x;
}
if(fz==0){
x.denumerator = 1;
return x;
}
int GCD = fz>fm?fm:fz;
while(GCD>1){
if((fz%GCD==0)&&(fm%GCD==0)){
break;
}
GCD--;
}
fm = x.denumerator/GCD;
fz = x.numerator/GCD;
elemtype xgcd;
xgcd.numerator = fz;
xgcd.denumerator = fm;
xgcd.index = x.index;
return xgcd;
}
head DERIVALTIVE(head L){
head newone = Create();
position p = First(L);
while(SPACE[p].next!=-1){
elemtype x;
if(SPACE[p].val.index==0){
x.numerator = 0;
}else{
x.numerator = SPACE[p].val.numerator * SPACE[p].val.index;
}
x.denumerator = SPACE[p].val.denumerator;
x.index = SPACE[p].val.index - 1;
Insert(fractionGCD(x),End(newone));
p = SPACE[p].next;
}
CLEAR(newone);
return newone;
}
double VALUE(head L,double x){
double ans = 0;
position p = First(L);
while(SPACE[p].next!=-1){
ans += SPACE[p].val.numerator*1.0/SPACE[p].val.denumerator*1.0*pow(x,SPACE[p].val.index);
p = SPACE[p].next;
}
printf("该多项式在%.2lf处的值为：%.2f\n",x,ans);
return ans;
}
void DIVIDE(head L1,head L2){
//多项式相除->获得商元素->获得余数多项式->余数多项式作为被除数
//直到被除数的最高次数小于除数的最高次数
const head divide = Copy(L2); //divide_除数
head bedivided = Copy(L1);//一直在变化的被除数
head quotient = ZERO();//创建商多项式
head sub_bedivided = Create();
sub_bedivided = bedivided;//创建一个被减元素
while(SPACE[SPACE[sub_bedivided].next].val.index>=SPACE[SPACE[divide].next].val.index){
bedivided = sub_bedivided;
//新的余数作为新的被除数
elemtype part = fractionDivide(SPACE[First(bedivided)].val,SPACE[First(divide)].val);
//计算商元素
CLEAR(quotient);
//商元素插入商多项式中
head quotient_part = Create();
Insert(part,End(quotient_part));
quotient = PLUS(quotient_part,quotient);
//printf("商元素为:\t");
//SHOW(quotient_part);
//创建一个商元素多项式
head mul_divide = MULTIPLY(quotient_part,L2);
//printf("乘过的为:\t");
//SHOW(mul_divide);
sub_bedivided = SUBTRACT(bedivided,mul_divide);
//获取余数
CLEAR(sub_bedivided);
//printf("余数为:\t");
//SHOW(sub_bedivided);
Destory(quotient_part);
}
printf("商为：\n");
SHOW(quotient);
save[cursor_save] = quotient;
cursor_save++;
printf("余数为：\n");
SHOW(sub_bedivided);
save[cursor_save] = sub_bedivided;
cursor_save++;
}
elemtype fractionDivide(elemtype a,elemtype b){
if(a.index<b.index){
printf("被除多项数次数小于除数多项式，不能再除！\n");
return a;
}
int fz1 = a.numerator; int fm1 = a.denumerator;
int fz2 = b.numerator; int fm2 = b.denumerator;
elemtype x;
x.index = a.index-b.index;
x.numerator = fz1 * fm2;
x.denumerator = fz2 * fm1;
x = fractionGCD(x);
return x;
}
head ZERO(void){
head newone = Create();
elemtype x;
x.numerator = 0;
x.denumerator = 1;
x.index = 0;
Insert(x,End(newone));
return newone;
}
void CLEAR(head L){
position p = First(L);
while(SPACE[p].next!=-1){
if(SPACE[p].val.numerator==0){
Delete(p);
}else{
p = SPACE[p].next;
}
}
}
void MENU(void){ //DONE!
printf("------欢迎使用一元多项式计算器------\n");
printf("将读入多项式，请选择功能：\n");
printf("A->显示所有\t");
printf("B->重新选中\t");
printf("C->键盘输入\t");
printf("D->加载结果\t");
printf("E->保存结果\t");
printf("F->选中最新\t");
printf("H->帮助\n");
printf("0->退出\t\t");
printf("1->求和\t\t");
printf("2->做差\t\t");
printf("3->乘积\t\t");
printf("4->相除\t\t");
printf("5->求导\t\t");
printf("6->求值\n");
}
void DISPLAY(void){
printf("初始输入多项式：\n");
for(int i=0; i<number_load; i++){
printf("编号：%d-->\n",i);
SHOW(load[i]);
}
printf("结果多项式：\n");
for(int i=0; i<cursor_save; i++){
printf("编号：%d-->\n",i);
SHOW(save[i]);
}
}
void SELECT(void){
printf("按次序选择两个多项式：");
scanf("%d %d",&cursor_s1,&cursor_s2);
if (cursor_s1>0){
if(cursor_s1>number_load||cursor_s2>number_load){
printf("数字过大！\n");
return;
}
printf("你选中了：\n");
printf("第一个->\n");
SHOW(load[cursor_s1]);
printf("第二个->\n");
SHOW(load[cursor_s2]);
}
}
void COLLECT(void){
fflush(stdin);
printf("选择结果多项式：\n");
for(int i=0; i<cursor_save; i++){
printf("编号：%d-->\n",i);
SHOW(save[i]);
}
int s;
scanf("%d",&s);
if(0<=s&&s<=cursor_save){
printf("载入输出编号%d-->",s);
load[cursor_load] = save[s];
printf("输入编号%d！",cursor_load);
cursor_load++;
}
}
void SAVE(void){
FILE* PUT;
PUT = fopen("OUTPUT.txt","w");
if(PUT == NULL){
printf("保存失败！！\n");
return;
}
printf("正在储存数据...\n");
number_save = cursor_save;
fprintf(PUT,"%d\n",number_save);
for(int i=0; i<number_save; i++){
position p = First(save[i]);
while(SPACE[p].next!=-1){
fprintf(PUT,"%d/%d %d ",SPACE[p].val.numerator,SPACE[p].val.denumerator,SPACE[p].val.index);
p = SPACE[p].next;
}
fprintf(PUT,"1/0 1 \n");
}
fclose(PUT);
printf("储存完毕！！正在返回计算器...\n");
MENU();
}
void LAST(void){
load[cursor_load] = save[cursor_save-1];
printf("载入最新结果！\t");
cursor_s1 = cursor_load;
cursor_load++;
}
逻辑设计
主程序流程图
程序模块间的调用关系
