实验二-线性表及其应用.doc

《实验二-线性表及其应用.doc》由会员分享，可在线阅读，更多相关《实验二-线性表及其应用.doc（14页珍藏版）》请在三一文库上搜索。

1、学号姓名实验 项 目线性表及其应用（ III ）实 验 内 容采用链式存储结构，两个项目选择一个项目完成：1编制一个演示集合的并、交和差运算的程序。（具体要求见题集第 80 页 1.3）2一元稀疏多项式的计算。要求实现多项式存储、输出显示、相加、相减、相乘。 （具体要求见题集第 81页 1.5）算法设计与程序实现：算法 分 析本次实验的目的是理解和掌握线性表链式存储结构的用法。根据多项式的加法 运算法则和乘法运算法则进行多项式的运算。程序设计流程图如下所示：1.多项式加法运算程序流程pa->data.coef + pb-开始pa = Pa->next pb = Pb->nex

2、tPc=(Polynomial)malloc(sizeof(PNode)pc = Pcpa && pb = 1 ?Npa = NULL ?比较多项式系数CompareExpn_L(pa->data,pb->data)pb = NULLNpc->next =pc->next =(Polynomial)malloc(sizeof(Polynomial)malloc(sizeo(PNode)f(PNode)pc = pc->nextpc = pc->next？pa = pa->next pb = pb->nextpc->data.

3、coef = pa- >data.coef + pb->data.coef pc->data.expn = pa- >data.expnpc->next = (Polynomial)malloc(sizeof(P Node)pc = pc->nextpc->next =NULL结束本函数的基本思想是先对两个链表中非空的部分进行指数比较， 当指数不等时， 将指数小的数据复制到新开辟结点中，指数大的结点继续与下一个结点比较，当指 数相等时，将两个结点系数合并，判断系数是否为零，若为零则不开辟新结点，否 则开辟新结点复制数据。2.多项式乘法运算程序流程图 :

4、用 Pa的任一项乘以 Pb 的每本函数的基本思想是将用两层循环分别遍历链表， 项，将乘积结果通过后续函数合并化简。3.多项式链表排序流程图：开始p = P->nextp->next != NULL ?s = pp = p->next结束核心程序本函数的基本思想是运用选择排序算法，首先通过外层循环确定一个位置，即 内层循环起始位置，然后用一个指针 p 遍历链表，并通过一个指针 s 指向内层循环 中数据最小的结点，最后用内层循环结束后的指针s 与内层循环起始指针比较，不等则交换，从而实现排序。此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中 文件包含部分的注

5、释处，核心程序如下：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 数据结构实验 实验二：线性表及其应

6、用() "); / 设置标题system( "color F1" );/ 设置控制台窗口的背景色和前景色system( "date /T" );/ 输出当前的日期printf( "请输入多项式 P1(x) 的项数：");scanf s( "%d",&m);GreatPolynomial L(P1,m);/ 根据输入数据创建一个多项式的单链表P1SortPolynomial L(P1);/ 对多项式按照指数大小排序printf( "P1(x) ：");PrintPolynomia

7、l L(P1);/ 打印多项式 P1(x) 的表达式printf( "请输入多项式 P2(x) 的项数：");scanf s( "%d",&m);GreatPolynomial L(P2,m);/ 根据输入数据创建一个多项式的单链表P2SortPolynomial L(P2);/ 对多项式按照指数大小排序printf( "P2(x) ：");PrintPolynomial_L(P2);AddPolynomial L(P1,P2,P3);/ 多项式 P1(x) 和P2(x) 相加printf( "*1 多项式加法 P1

8、(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);DestroyPolynomial_L(P3);/ 销毁减法运算生成的多项式P3MultiPolynomial L(P1,P2,P3);/ 多项式 P1(x) 和P2(x) 相乘printf( "*

9、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：");PrintPolynomial L(P2);DestroyPolynomial L(P1);/ 销毁多项式链表 P1DestroyPolynomi

10、al_L(P2);/ 销毁多项式链表 P2DestroyPolynomial L(P3);/ 销毁多项式链表 P3return 0;2. 头文件 ”ADT.h”的部分程序如下： #ifndef ADT_H_#define ADT_H_* 常 量 和 数 据 类 型 预 定 义 */* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERRO R 0 #define INFEASIBLE -1 #define OVERFLO W -2数据结构类型定义线 性 表 */*多项式存储结构类型定义*/typedef structfl

11、oat coef;/ 系数int expn;/ 指数 PElemType;/ 多项式指数、系数结构类型typedef struct PNodePElemType data;/ 多项式结点数据struct PNode * next;/ 多项式结点指针 PNode,* Polynomial ;/ 多项式链表结构体类型及指针结构类型3. 头文件 ”DataStructure_LinearList.h”中部分函数定义如下：#include <stdio.h>#include <malloc.h>#include "ADT.h" /* 功 能 函 数 声 明

12、区 */* 链 表 */Status GreatPolynomial_L( Polynomial &P, int m); / 输入 m项系数与指数 , 建立链表 PStatus InitPolynomial_L( Polynomial &P); / 初始化多项式结构变量Status DestroyPolynomial_L( Polynomial &P); / 销毁多项式链表 P int CompareExpn_L(PElemType Ea, PElemType Eb);/ 比较多项式的指数Status PrintPolynomial_L(Polynomial &

13、P);/ 打印输出一元多项式 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, Poly

14、nomial &Pb, Polynomial &Pc); / 完成多项式 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(Polyno

15、mial &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)if (q->dat

16、a.expn < s->data.expn)s = q;if (s != p)/ 从p指针的下一结点开始遍历链表/s 指针指向 p结点及其之后链表中数据最小的结点/ 将 s结点与 p结点交换数据coef_temp = p->data.coef; expn_temp = p->data.expn; p->data.coef = s->data.coef;p->data.expn = s->data.expn;s->data.coef = coef_temp;s->data.expn = expn_temp; return OK; /So

17、rtPolynomial L函数原型函数功能入口参数Status UnitePolynomial L(Polynomial &P)合并多项式 P中的同类项多项式结构体指针类型的引用 &P* 出口参数：返回函数结果状态*/Status UnitePolynomial_L( Polynomial &P) Polynomial p, q;for (p = P->next; p->next !=NULL; p = p->next)if (p->data.expn = p->next->data.expn)/ 判断是否为同类项q = p->

18、;next;/ 保存下一结点，便于系数相加后释放p->data.coef += p->next->data.coef;/ 同类项系数相加p->next = q->next; free(q);return OK; /UnitePolynomial L /* 函数原型： Status AddPolynomial_L(Polynomial &Pa, Polynomial &Pb, Polynomial &Pc)* 函数功能：完成多项式 Pa和 Pb的相加运算* 入口参数：多项式结构体指针类型的引用 &Pa,&Pb* 出口参数：返回

19、函数结果状态*/Status AddPolynomial_L( Polynomial &Pa, Polynomial &Pb, Polynomial &Pc) Polynomial pa, pb, pc;pa = Pa->next;pb = Pb->next;Pc = ( Polynomial )malloc( sizeof ( PNode);if (! Pc)return OVERFLO; Wpc = Pc;while (pa && pb)switch (CompareExpn_L(pa->data, pb->data) / 判

20、断指数的大小关系case -1:/pa 指向的结点指数小于 pb指向结点的指数pc->next = ( Polynomial )malloc( sizeof ( PNode); / 开辟新结点，复 制指数较小的结点数据到新结点pc = pc->next;pc->data.coef = pa->data.coef; pc->data.expn = pa->data.expn;pa = pa->next; / 较小指数结点后移，与上一指数较大结点再次比较 break ;case 0:/ 指数相等if (pa->data.coef + pb->d

21、ata.coef = 0)/ 判断系数是否为 0pc->next = ( Polynomial )malloc( sizeof ( PNode); / 开辟新结点 pc = pc->next;pc->data.coef = pa->data.coef + pb->data.coef; pc->data.expn = pa->data.expn;pa = pa->next; pb = pb->next; break ;case 1: /pa 指向的结点指数大于 pb指向结点的指数 pc->next = ( Polynomial )mal

22、loc( sizeof ( PNode); pc = pc->next;pc->data.coef = pb->data.coef; pc->data.expn = pb->data.expn; pb = pb->next;break ;while (pa)/ 复制 Pa剩余结点数据pc->next = ( Polynomial )malloc( sizeof ( PNode); pc = pc->next;pc->data.coef = pa->data.coef; pc->data.expn = pa->data.ex

23、pn; pa = pa->next;while (pb) / 复制 Pb剩余结点数据pc->next = ( Polynomial )malloc( sizeof ( PNode); pc = pc->next;pc->data.coef = pb->data.coef; pc->data.expn = pb->data.expn; pb = pb->next; pc->next = NULL; /Pc 尾结点指针置空return OK; /AddPolynomial L/* 函数原型： Status MultiPolynomial_L(P

24、olynomial &Pa, Polynomial &Pb, Polynomial &Pc)* 函数功能：完成多项式 Pa和 Pb的相乘运算* 入口参数：多项式结构体指针类型的引用 &Pa,&Pb* 出口参数：返回函数结果状态*/Status MultiPolynomial_L( Polynomial &Pa, Polynomial &Pb, Polynomial &Pc) Polynomial pa, pb, pc;pa = Pa->next;pb = Pb->next;Pc = ( Polynomial )mall

25、oc( sizeof ( PNode);while (pa)/ 遍历链表 Pa,Pa的每一项乘以 Pbwhile (pb) / 遍历 Pb,Pa的一项乘 Pb的每一项pc->next = ( Polynomial )malloc( sizeof ( PNode);pc = pc->next;pc->data.coef = pa->data.coef * pb->data.coef;/ 系数相乘pc->data.expn = pa->data.expn + pb->data.expn;/ 指数相加pb = pb->next;pa = pa-&

26、gt;next;/pa 指针后移pb = Pb->next;/pb 指针重置pc->next = NULL;/ 尾结点指针置空SortPolynomial L( Pc);/ 对相乘得到的多项式 Pc按指数排序UnitePolynomial_L( Pc);/ 合并同类项 Pcreturn OK; /MultiPolynomial L运行结果实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的基本内容。实1、通过此次实验，我学会了链表建立、插入、删除、修改等基本操作，加深了实 对指针、结构体的了解，对 c 语言有了更进一步的认识。在大量运用指针的过程中验 当然避免不了使用的指针

27、发生指向错误导致程序崩溃，但通过长时间的单步调试观验 察，最终解决了指针指向未知区域发生错误的问题。由于教材上是逆序建立链表，尾指针的指针域在初始化时就被置空了，所以就不必注意这个问题，由于本实验的 程序中建立链表都采用顺序建立，所以一开始也没注意，从而造成了错误。从中我 学到的就是链表尾结点的指针域一定要置成 NULL ，否则就会发生错误。2、此次实验我遇到的难点，不是多项式的加、减或乘运算，而是对链表数据的 排序，开始想通过起泡法直接排序，但发现排序时需要前后两个结点的数据进行比 较，不管采用何种循环判断都不能实现，要么发生指针指向错误，要么就是不能对所以的数据进行比较，最后经交换得到启发，故最后实现了链表的排序。3、在此次实验中我发现了一个问题，在多项式加法运算时，其中的一个判断条件 (!pb | pa->data.expn > pb->data.expn)会发生指针指向错误， 即当 pb=NULL 时，会 对或逻辑运算符后的条件进行判断，但根据标准 C 中逻辑或的判断原则，只要前一 条件为真，后面条件不判断的原则，该函数又是正确的，多次单步调试都是这个问 题，在网上搜索也没有解决，不知道是什么原因。