2022年数据结构实验多项式求和资料 .pdf

《2022年数据结构实验多项式求和资料 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验多项式求和资料 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析实验报告- 1 - 1、实验目的（1)掌握线性表的顺序存储结构和链式存储结构；（2)掌握线性表插入、删除等基本运算；（3)掌握线性表的典型运用多项式求和。2、实验内容编程实现多项式的求和运算：（1)顺序存储结构的实现例如，已知： f(x)=8x6+5x5-10 x4+32x2-x+10，g(x)=7x5+10 x4-20 x3-10 x2+x，求和结果： f(x)+g(x)=8x6+12x5-20 x3+22x2+10。顺序表的定义类型如下：#define MAXLEN 100 typedef struct int dataMAXLEN; Int last; SeqList; （

2、2)链式存储结构的实现例如，已知： f(x)=100 x100+5x50-30 x10 +10，g(x)=150 x90-5x50+40 x20-20 x10+3x，求和结果： f(x)+g(x)= 100 x100+150 x90+40 x20-10 x10+3x+10。3、实验要求（1)利用 C（C+）语言完成程序设计。（2)上机调试通过实验程序。（3)输入数据，检验程序运行结果。（4)给出具体的算法分析，包括时间复杂度和空间复杂度等。（5)撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。4、实验步骤与源程序 实验步骤我先从具体的问题中抽象出适当的数学模型，然后设计出

3、相应的算法，对于用顺序存储结构实现多项式求和而言，需要设计 3 个 main 函数调用的子函数，分别实现创建多项式，多项式相加和显示多项式； 对于用链式存储结构实现多项式求和，也同样需要3 个这样的子函数，最后，编写程序，并调试程序，得出实验结果。 源代码顺序存储结构：#include #define MAXLEN 100 typedef struct int dataMAXLEN; int last; SeqList; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7

4、 页 - - - - - - - - - 算法设计与分析实验报告- 2 - void add_List(SeqList A, SeqList B, SeqList *C) int i; C-last=A.lastB.last? A.last:B.last; for(i=0;ilast;i+) C-datai=A.datai+B.datai; void show_list(SeqList C) int i; for(i=C.last;i=1;i-) if(C.datai) printf(%dx%d)+,C.datai,i); printf(%dx%d)n,C.data0,0); void cre

5、ate_list(SeqList *D) int n,i; printf(tt请输入多项式X的最高次数： ); scanf(%d,&n); for(int k=99;k=0;k-) D-datak=0; printf(tt请输入多项式X的次数由大到小输入系数，缺少项用0 补齐 n); for(i=n;i=0;i-) printf(tt输入 X%d项的系数 : ,i); scanf(%d,&D-datai); D-last=n; void main() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

6、- - - 第 2 页，共 7 页 - - - - - - - - - 算法设计与分析实验报告- 3 - SeqList A,B,C; printf(tt创建多项式f(x):n); create_list(&A); printf(ttf(x)=); show_list(A); printf(tt创建多项式g(x):n); create_list(&B); printf(ttg(x)=); show_list(B); printf(tt多项式 f(x)和 g(x) 的和 : ); add_List (A,B,&C); printf(nttf(x)+g(x)=); show_list(C); 链式

7、存储结构：#include #include #include typedef struct linknode float coef; int expn; struct linknode *next; Node; void create_link_list(Node *L) Node *p,*q; int n=1; float x=1; q=L; printf(n请按多项式指数由大到小输入系数和指数:n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - -

8、- - - - - - - 算法设计与分析实验报告- 4 - printf(提示 : 系数和指数间用空格间隔，每组数据之间用回车间隔( 系数和指数为0 时结束输入)n); while(fabs(x)0.000001 ) scanf(%f %d,&x,&n); if(fabs(x)0.00001) p=(Node *) malloc(sizeof(Node); p-coef=x; p-expn=n; p-next=NULL; q-next=p ; q=p; void show_link_list(Node *L) Node *p; p=L-next; while(p&p-next ) print

9、f(%.1fx%d) + ,p-coef,p-expn); p=p-next; printf(%.1fx%d) ,p-coef,p-expn); printf(n); void mergelist(Node *La,Node *Lb,Node *Lc) / 多项式合并 Node *pa,*pb,*pc; Node *q1,*q2; Lc=La; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 算法设计与分析实验报告- 5 - p

10、c=Lc; pa=La-next; pb=Lb-next; while(pa & pb) if(pa-expn pb-expn) pc-next=pa;pc=pa;pa=pa-next; else if(pa-expn expn) pc-next=pb;pc=pb;pb=pb-next; else if(fabs(pa-coef+pb-coef)next; pb=pb-next; free(q1); free(q2); else q1=pb;pa-coef=pa-coef+pb-coef; pc-next=pa; pc=pa; pa=pa-next; pb=pb-next; free(q1);

11、 if(pa) pc-next=pa; else pc-next=pb; void main() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 算法设计与分析实验报告- 6 - Node *LA,*LB,*LC; LA=(Node *)malloc(sizeof(Node); LA-next=NULL; LB=(Node *)malloc(sizeof(Node); LB-next=NULL; LC=LA; create_li

12、nk_list( LA); printf(f(x) = ); show_link_list(LA); create_link_list( LB); printf(g(x) = ); show_link_list(LB); mergelist(LA,LB,LC); printf(nf(x)+g(x)= ); show_link_list(LC); 5、测试数据与实验结果（可以抓图粘贴）顺序存储结构的实现调试结果如图所示：链式存储结构的实现调试结果如图所示：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

13、 - - - 第 6 页，共 7 页 - - - - - - - - - 算法设计与分析实验报告- 7 - 6、结果分析与实验体会本次实验是参考了范例程序，经过自己的改写，从而实现要求。先做简单的输出，一步步的再做其它格式的设置。而且，在具体操作中我对顺序存储结构和链式存储结构的优点和缺点有了更深刻的体会，顺序存储结构的算法较为简单，但是在输入的过程中有很大的局限性，必须从大到小依次且连续的输入多项式次数，所以，它只适合最高次数较小的多项式求和，而链式存储结构设计的算法则更灵活，输入时，不需要次数在数值上连续，所以，它更具有普遍性、实用性。再从算法效率的角度来评价，顺序存储结构在做次数大小跨度大的多项式求和时，会浪费很多的存储空间，而链式存储结构则可以充分利用，不会浪费，即其空间复杂度较小。最后，我想说，通过调试程序，我不光学会编程了的基本步骤、基本算法，也使自己更有耐心去做好每一件事情。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -