实验二-线性表与其应用(III).docxVIP

电子信息工程学院2013级《数据结构》实验报告 姓名 学号 实验项目 线性表及其应用（III） 实验内容 采用链式存储结构，两个项目选择一个项目完成： 1．编制一个演示集合的并、交和差运算的程序。（具体要求见题集第80页1.3） 2．一元稀疏多项式的计算。要求实现多项式存储、输出显示、相加、相减、相乘。 （具体要求见题集第81页1.5） 算法设计与程序实现： 算法分析 本次实验的目的是理解和掌握线性表链式存储结构的用法。根据多项式的加法运算法则和乘法运算法则进行多项式的运算。 程序设计流程图如下所示： 1.多项式加法运算程序流程 本函数的基本思想是先对两个链表中非空的部分进行指数比较，当指数不等时，将指数小的数据复制到新开辟结点中，指数大的结点继续与下一个结点比较，当指数相等时，将两个结点系数合并，判断系数是否为零，若为零则不开辟新结点，否则开辟新结点复制数据。 2.多项式乘法运算程序流程图: 本函数的基本思想是将用两层循环分别遍历链表，用Pa的任一项乘以Pb的每一项，将乘积结果通过后续函数合并化简。 3.多项式链表排序流程图： 本函数的基本思想是运用选择排序算法，首先通过外层循环确定一个位置，即内层循环起始位置，然后用一个指针p遍历链表，并通过一个指针s指向内层循环中数据最小的结点，最后用内层循环结束后的指针s与内层循环起始指针比较，不等则交换，从而实现排序。 核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下： 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"); //设置控制台窗口的背景色和前景色 system("date /T"); //输出当前的日期 printf("请输入多项式P1(x)的项数："); scanf_s("%d",&m); GreatPolynomial_L(P1,m); //根据输入数据创建一个多项式的单链表P1 SortPolynomial_L(P1); //对多项式按照指数大小排序 printf("P1(x)："); PrintPolynomial_L(P1); //打印多项式P1(x)的表达式 printf("请输入多项式P2(x)的项数："); scanf_s("%d",&m); GreatPolynomial_L(P2,m); //根据输入数据创建一个多项式的单链表P2 SortPolynomial_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); //销毁加法运算生成的多项式P3 SubPolynomial_L(P1,P2,P3); //多项式P1(x)和P2(x)相减 printf("*2 多项式减法 P1(x) - P2(x)："); PrintPolynomial_L(P3); DestroyPolynomial_L(P3); //销毁减法运算生成的多项式P3 MultiPolynomial_L(P1,P2,P3); //多项式P1(x)和P2(x)相乘 printf("*3 多项式乘法 P1(x) * P2(x)："); PrintPolynomial_L(P3); DiffPolynomial_L(P1);