数据结构 实验 多项式求和.doc

实验目的 掌握线性表的顺序存储结构和链式存储结构； 掌握线性表插入、删除等基本运算； 掌握线性表的典型运用——多项式求和。 实验内容 编程实现多项式的求和运算： 顺序存储结构的实现 例如，已知：f(x)=8x^6+5x^5-10x^4+32x^2-x+10，g(x)=7x^5+10x^4-20x^3-10x^2+x， 求和结果：f(x)+g(x)=8x^6+12x^5-20x^3+22x^2+10。 顺序表的定义类型如下： #define MAXLEN 100 typedef struct { int data[MAXLEN]; Int last; }SeqList; 链式存储结构的实现 例如，已知：f(x)=100x^100+5x^50-30x^10 +10，g(x)=150x^90-5x^50+40x^20-20x^10+3x， 求和结果：f(x)+g(x)= 100x^100+150x^90+40x^20-10x^10+3x+10。 实验要求 利用C（C++）语言完成程序设计。 上机调试通过实验程序。 输入数据，检验程序运行结果。 给出具体的算法分析，包括时间复杂度和空间复杂度等。 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。 实验步骤与源程序 ⑴ 实验步骤 我先从具体的问题中抽象出适当的数学模型，然后设计出相应的算法，对于用顺序存储结构实现多项式求和而言，需要设计3个main函数调用的子函数，分别实现创建多项式，多项式相加和显示多项式；对于用链式存储结构实现多项式求和，也同样需要3个这样的子函数，最后，编写程序，并调试程序，得出实验结果。 ⑵ 源代码 顺序存储结构： #includestdio.h #define MAXLEN 100 typedef struct { int data[MAXLEN]; int last; } SeqList; void add_List(SeqList A, SeqList B, SeqList *C) { int i; C-last=A.lastB.last? A.last:B.last; for(i=0;i=C-last;i++) C-data[i]=A.data[i]+B.data[i]; } void show_list(SeqList C) { int i; for(i=C.last;i=1;i--) if(C.data[i]) printf(\(%dx^%d\)+,C.data[i],i); printf(\(%dx^%d\)\n,C.data[0],0); } void create_list(SeqList *D) { int n,i; printf(\t\t请输入多项式X的最高次数：); scanf(%d,n); for(int k=99;k=0;k--) D-data[k]=0; printf(\t\t请输入多项式X的次数由大到小输入系数，缺少项用0补齐\n); for(i=n;i=0;i--) { printf(\t\t输入X^%d项的系数: ,i); scanf(%d,D-data[i]); } D-last=n; } void main() { SeqList A,B,C; printf(\t\t创建多项式f(x):\n); create_list(A); printf(\t\tf(x)=); show_list(A); printf(\t\t创建多项式g(x):\n); create_list(B); printf(\t\tg(x)=); show_list(B); printf(\t\t多项式f(x)和g(x)的和: ); add_List (A,B,C); printf(\n\t\tf(x)+g(x)=); show_list(C); } 链式存储结构： #includestdio.h #includemalloc.h #includemath.h 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;