《实验二-线性表及其应用(iii).doc》由会员分享，可在线阅读，更多相关《实验二-线性表及其应用(iii).doc（11页珍藏版）》请在金锄头文库上搜索。
1、电子信息工程学院2013级数据结构实验报告姓名学号实验项目线性表及其应用（III）实验内容采用链式存储结构，两个项目选择一个项目完成：1编制一个演示集合的并、交和差运算的程序。（具体要求见题集第80页1.3）2一元稀疏多项式的计算。要求实现多项式存储、输出显示、相加、相减、相乘。（具体要求见题集第81页1.5）算法设计与程序实现：算法分析本次实验的目的是理解和掌握线性表链式存储结构的用法。根据多项式的加法运算法则和乘法运算法则进行多项式的运算。程序设计流程图如下所示：1.多项式加法运算程序流程 本函数的基本思想是先对两个链表中非空的部分进行指数比较，当指数不等时，将指数小的数据复制到新开辟结点
2、中，指数大的结点继续与下一个结点比较，当指数相等时，将两个结点系数合并，判断系数是否为零，若为零则不开辟新结点，否则开辟新结点复制数据。 2.多项式乘法运算程序流程图: 本函数的基本思想是将用两层循环分别遍历链表，用Pa的任一项乘以Pb的每一项，将乘积结果通过后续函数合并化简。 3.多项式链表排序流程图： 本函数的基本思想是运用选择排序算法，首先通过外层循环确定一个位置，即内层循环起始位置，然后用一个指针p遍历链表，并通过一个指针s指向内层循环中数据最小的结点，最后用内层循环结束后的指针s与内层循环起始指针比较，不等则交换，从而实现排序。核心程序 此程序中用到的自己编写的头文件以在下面给出，而
3、头文件的说明则在主函数中文件包含部分的注释处，核心程序如下：1.主函数如下：#include stdafx.h /标准输入输出函数头文件#include windows.h /cmd窗口设置函数头文件#include ADT.h /数据结构中相关结构体类型定义及相关数据类型定义#include DataStructure_LinearList.h /数据结构第二章线性表中相关函数的定义及声明int main()Polynomial P1,P2,P3;int m;system(title 数据结构实验 实验二：线性表及其应用（） ); /设置标题system(color F1); /设置控制台窗
4、口的背景色和前景色system(date /T); /输出当前的日期printf(请输入多项式P1(x)的项数：);scanf_s(%d,&m);GreatPolynomial_L(P1,m); /根据输入数据创建一个多项式的单链表P1SortPolynomial_L(P1); /对多项式按照指数大小排序printf(P1(x)：);PrintPolynomial_L(P1); /打印多项式P1(x)的表达式printf(请输入多项式P2(x)的项数：);scanf_s(%d,&m); GreatPolynomial_L(P2,m); /根据输入数据创建一个多项式的单链表P2 SortPoly
5、nomial_L(P2); /对多项式按照指数大小排序printf(P2(x)：);PrintPolynomial_L(P2); AddPolynomial_L(P1,P2,P3); /多项式P1(x)和P2(x)相加printf(*1 多项式加法 P1(x) + P2(x)：);PrintPolynomial_L(P3);DestroyPolynomial_L(P3); /销毁加法运算生成的多项式P3SubPolynomial_L(P1,P2,P3); /多项式P1(x)和P2(x)相减printf(*2 多项式减法 P1(x) - P2(x)：);PrintPolynomial_L(P3)
6、;DestroyPolynomial_L(P3); /销毁减法运算生成的多项式P3MultiPolynomial_L(P1,P2,P3); /多项式P1(x)和P2(x)相乘printf(*3 多项式乘法 P1(x) * P2(x)：);PrintPolynomial_L(P3);DiffPolynomial_L(P1); /对多项式P1求微分printf(*4 多项式微分 dP1(x)/dx：);PrintPolynomial_L(P1);IntegralPolynomial_L(P2); /对多项式P2求积分printf(*5 多项式积分 IntP2(x),x：);PrintPolynom
7、ial_L(P2);DestroyPolynomial_L(P1); /销毁多项式链表P1DestroyPolynomial_L(P2); /销毁多项式链表P2 DestroyPolynomial_L(P3); /销毁多项式链表P3return 0; 2.头文件”ADT.h”的部分程序如下：#ifndef ADT_H_#define ADT_H_/* 常 量 和 数 据 类 型 预 定 义*/* -函数结果状态代码- */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OV
8、ERFLOW -2/* 数 据 结 构 类 型 定 义*/*线 性 表*/* -多项式存储结构类型定义- */typedef structfloat coef; /系数int expn; /指数PElemType; /多项式指数、系数结构类型typedef struct PNodePElemType data; /多项式结点数据struct PNode * next; /多项式结点指针PNode,*Polynomial; /多项式链表结构体类型及指针结构类型3.头文件”DataStructure_LinearList.h”中部分函数定义如下：#include #include #include
9、 ADT.h/* 功 能 函 数 声 明 区*/* -链 表- */Status GreatPolynomial_L(Polynomial &P, int m); /输入m项系数与指数,建立链表PStatus InitPolynomial_L(Polynomial &P); /初始化多项式结构变量Status DestroyPolynomial_L(Polynomial &P); /销毁多项式链表Pint CompareExpn_L(PElemType Ea, PElemType Eb); /比较多项式的指数Status PrintPolynomial_L(Polynomial &P); /打
10、印输出一元多项式PStatus UnitePolynomial_L(Polynomial &P); /合并多项式P中的同类项Status SortPolynomial_L(Polynomial &P); /实现指数按照从小到大排序Status DiffPolynomial_L(Polynomial &P); /实现多项式P的微分运算Status IntegralPolynomial_L(Polynomial &P); /实现多项式P的积分运算Status AddPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc); /完成多项
11、式Pa和Pb的相加运算Status SubPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc); /完成多项式Pa和Pb的相减运算Status MultiPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc);/完成多项式Pa和Pb的相乘运算/* 功 能 函 数 定 义 区*/* 函数原型：Status SortPolynomial_L(Polynomial &P)* 函数功能：完成多项式指数按照从小到大顺序排序* 入口参数：多项式结构体指针类型的引用&P* 出口参数：返回函数结果状态*/Status SortPolynomial_L(Polynomial &P)Polynomial p,q,s;float coef_temp;int expn_temp;for (p = P-next; p-next != NULL; p = p-next) /遍历整个链表s = p;for (q = p-next; q; q = q-next
