1200字范文 > 【C语言X数据结构】用静态链表实现的多项式计算器加减乘除求导求值输入输出样样在

【C语言X数据结构】用静态链表实现的多项式计算器加减乘除求导求值输入输出样样在

时间：2019-06-14 19:20:06

实验要求
以动态或者静态链表存储一元多项式，在此基础上按要求完成对一元多项式的运算。（为保证多项式的值的准确性，多项式的系数可以用分数表示，涉及到两个分数相除时，结果也可以用分数表示。）
1. 能够输入多项式（可以按各项的任意输入顺序，建立按指数降幂排列的多项式）和输出多项式（按指数降幂排列）,以文件形式输入和输出，并显示。
2. 能够给出计算两个多项式加法、减法、乘法和除法运算的结果多项式，除法运算的结果包括商多项式和余数多项式。
3. 能够计算一元多项式的 k 阶导函数。
4. 能够计算多项式在某一点 x=x0 的值，其中 x0是一个浮点型常量，返回结果为浮点数。
5. 要求尽量减少乘法和除法运算中间结果的空间占用和结点频繁的分配与回收操作。（提示：利用循环链表结构或者可用空间表的思想，把循环链表表示的多项式返还给系统或者可用空间表，从而解决上述问题）。

完整代码

#include <stdio.h>#include <stdlib.h>#include <math.h>#define MAXSIZE 4096#define MAXLEN 256typedef 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; //游标1head cursor_s2 = -1; //游标2int 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++;}