数据结构论文一元多项式的计算

1、目 录一.一元多项式的计算21.1 问题描述21.2 数据结构设计21.3 算法设计21.4 源代码51.5运行结果12二. 排序系统132.1 问题描述132.2数据结构设计132.3算法设计132.4源代码142.5运行结果20总结22参考文献22一.一元多项式的计算1.1 问题描述建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，能够完成两个多项式的加减运算并输出结果1.2 数据结构设计一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及

2、指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。typedef struct Polynomial float coef; /系数 int expn; /指数 struct Polynomial *next;*Polyn,Polynomial; 1.3 算法设计1）、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入开始申请结点

3、空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 合并同类项结束否是是否输入正确开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 x, 指数 y输出已输入的多项式 合并同类项结束否是是否输入正确图12）、多项式的加法（1）功能：将两多项式相加。（2）数据流入：输入函数。（3）数据流出：多项式相加后的结果。（4）程序流程图：多项式的加法流程图如图2所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。开始定义存储结果的空链 r是 否输出存储多项式的和的链r结

4、束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项 图23）、多项式的减法（1）功能：将两多项式相减。（2）数据流入：调用输入函数。（3）数据流出：多项式相减后的结果。（4）程序流程图：多项式的减法流程图如图3所示。（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中把p中各项系数改变符号后存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项 图31.4 源

5、代码#include<stdio.h>#include<malloc.h>typedef struct Polynomial float coef; /系数 int expn; /指数 struct Polynomial *next;*Polyn,Polynomial; /Polyn为结点指针类型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

6、->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; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一个头指针为head、项数为m的一元多

7、项式 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 hea

8、d;/CreatePolynvoid 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; wh

9、ile (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) / 系数等于1的情况 if

10、(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d",q->expn); if(q->coef=-1) / 系数等于-1的情况 if(!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+;

11、/while printf("n");/PrintPolynint 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多项式非空/comparePolyn AddPolyn(Polyn pa

12、,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-&g

13、t;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; /switch if(qc->coef!=0) qc->next=hc->next; hc->next=qc; hc=qc; els

14、e free(qc);/当相加系数为0时，释放该结点 /while return headc;/AddPolynPolyn 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;/Subtra

15、ctPolynint main() int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定义各式的头指针，pa与pb在使用前付初值NULL printf("请输入a的项数:"); scanf("%d",&m); pa=CreatePolyn(pa,m);/建立多项式a printf("请输入b的项数:"); scanf("%d",&n); pb=CreatePolyn(pb,n);/建立多项式a /输出菜单 printf("*n&qu

16、ot;); printf("操作提示：nt1.输出多项式a和bnt2.建立多项式a+bnt3.建立多项式a-bn"); printf("t4.退出n*n"); for(;flag=0) printf("执行操作："); scanf("%d",&flag); if(flag=1) printf("多项式a：");PrintPolyn(pa); printf("多项式b：");PrintPolyn(pb);continue; if(flag=2) pc=AddPolyn(

17、pa,pb); printf("多项式a+b：");PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=3) pd=SubtractPolyn(pa,pb); printf("多项式a-b：");PrintPolyn(pd); DestroyPolyn(pd);continue; if(flag=4) break; if(flag<1|flag>4) printf("Error!n");continue; /for DestroyPolyn(pa); DestroyPoly

18、n(pb); return 0;1.5运行结果1）测试的数据及结果输出结果：2）算法的时间复杂度及改进算法的时间复杂度：一元多项式的加法运算的时间复杂度为O(m+n）,减法运算的时间复杂度为O(m-n)，其中m，n分别表示二个一元多项式的项数。问题和改进思想：在设计该算法时，出现了一些问题，例如在建立链表时头指针的设立导致了之后运用到相关的指针时没能很好的移动指针出现了数据重复输出或是输出系统缺省值，不能实现算法。实现加法时该链表并没有向通常那样通过建立第三个链表来存放运算结果，而是再度利用了链表之一来进行节点的比较插入删除等操作。为了使输入数据按指数降序排列，可在数据的输入后先做一个节点的排

19、序函数，通过对链表排序后再进行之后加减运算。二. 排序系统2.1 问题描述编制一个运用排序算法对输入数进行排序的程序。包括冒泡排序、快速排序。2.2数据结构设计typedef structint key;char otherinfo;RecType;typedef RecType SeqlistL+1;开始2.3算法设计结束2.4源代码#include<stdio.h>#include<stdlib.h>#include <math.h>#define L 8 /排序元素个数#define FALSE 0#define TRUE 1typedef struc

20、tint key;char otherinfo;RecType;typedef RecType SeqlistL+1;int num; /定义排序趟数的全局变量 Seqlist R;/冒泡排序void Bubblesort()int i,j,k;int exchange;printf("ntt原始数据为（按回车键开始排序）：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");for(i=1;i<L;i+)exchange=FALSE;for(j=

21、L;j>=i+1;j-)if(Rj.key<Rj-1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;exchange=TRUE;if(exchange)printf("tt第%d趟排序的结果为（按回车键开始排序）：ntt",i);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");printf("ntt排序最终结果是：ntt");for(i=1;i<=L;i+)printf

22、("%5d",Ri.key);printf("n");int Partition(int i,int j) /i和j为形式参数，分别代表low和high RecType pirot=Ri;while(i<j)while(i<j&&Rj.key>=pirot.key) j-;if(i<j)Ri+=Rj;while(i<j&&Ri.key<=pirot.key)i+; if(i<j)Rj-=Ri;Ri=pirot;return i; /递归排序void Quicksort(int lo

23、w,int high)int pirotpos,k;if(low<high)pirotpos=Partition(low,high);num+;printf("tt第%d趟排序的结果为（按回车键开始排序）：ntt",num);for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");Quicksort(low,pirotpos-1);Quicksort(pirotpos+1,high);main()Seqlist S;int i,k;char ch1,ch2,q;

24、printf("ntt请输入%d个待排序的数据（按回车键分隔）：ntt",L);for(i=1;i<=L;i+)scanf("%d",&Si.key);getchar();printf("tt");printf("ntt数据输入完毕！");ch1='y'while(ch1='y'|ch1='Y')printf("n"); printf("ntt 排 序 子 系 统 n"); printf("ntt*n&q

25、uot;); printf("ntt* 1-冒 泡 排 序 *n"); printf("ntt* 2-快 速 排 序 *n"); printf("ntt* 0-返回 *n"); printf("ntt*n"); printf("ntt请选择菜单号（0到2）");scanf("%c",&ch2);getchar();for(i=1;i<=L;i+)Ri.key=Si.key;switch(ch2)case '1':Bubblesort();brea

26、k;case '2':printf("ntt原始数据为（按回车键开始排序）：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);getchar();printf("n");num=0;Quicksort(1,L);printf("ntt排序最终结果是：ntt");for(k=1;k<=L;k+)printf("%5d",Rk.key);printf("n");break;case '0':ch1='n'break;default:system("cls");printf("ntt对不起，您输入有误，请重新输入！n");break;if(ch2!='0')if(ch2='1'|ch2='2' )printf("nntt排序完毕！");printf("ntt按回车键继续！");q=getchar();if