数据结构实验报告1

数据结构课程设计

1. 一元多项式的表示及其运算的实现

1.1 问题描述

符号多项式的操作，已经成为表处理的典型用例。在数学上，

一个一元多项式Pn(x)可按升幂写成： Pn(x) = p0+ p1x+ p2x2+?.+ pnxn 它由n+1个系数唯一确定，因此，在计算机里，它可用一个线性表P来表示：

P = (p0 ,p1 ,p2 ,? pn)每一项的指数i隐含在其系数pi的序号里。 假设Qm(x)是一元m次多项式，同样可用线性表Q来表示:Q = (q0 ,q1 ,q2 ,? qm)。

不失一般性，设m

10000

+2x

20000

的多

项式时，就要用一长度为20001的线性表来表示，表中仅有三个非零元素，这种对内存空间的浪费是应当避免的，但是如果只存储非零系数项则显然必须同时存储相应的指数。

一般情况下的一元n次多项式可写成:

Pn(x) = p1xe1 + p2xe2 + ? + pmxem

其中pi，是指数为ei的项的非零系数，且满足0 ≤ e1 < e2 < ?< em = n，若用一个长度为m且每个元素有两个数据项(系数项和指数项)的线性表便可唯一确定多项式Pn(x)。

1

数据结构课程设计

((p1 ,e1) , (p2 ,e2) , ? ,(pm,em))

在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多存储一倍的数据。但是，对于S(x)类的多项式，这种表示将大大节省空间。

本题要求选用线性表的一种合适的存储结构来表示一个一元多项式，并在此结构上实现一元多项式的加法，减法和乘法操作。

1.2 设计方案与概要设计

实现实系数一元多项式的创建，打印以及两个一元多项式的加、减、乘运算。

程序所能达到的功能：

a. 实现一元多项式的输入；

b. 实现一元多项式的输出；

c. 计算两个一元多项式的和并输出结果； d. 计算两个一元多项式的差并输出结果； e. 计算两个一元多项式的积并输出结果。 程序实现：

a. 功能：将要进行运算的二项式输入输出； b. 数据流入：要输入的二项式的系数与指数； c. 数据流出：合并同类项后的二项式； d. 程序流程图：二项式输入流程图；

e. 测试要点：输入的二项式是否正确，若输入错误则重新输入

2

数据结构课程设计

开始 申请结点空间 输入二项式的项数 输入二项式各项的系数 x, 指数 y 输出已输入的二项式 否 是否输入正确 是 合并同类项 结束

数据类型

ADT Polynomial{

数据对象：D={ai| ai ∈TermSet,i=1,2,?,m,m≥0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数}

3

数据结构课程设计

数据关系：R1={< ai-1,ai >| ai-1 , ai ∈D,且ai-1 中的指数值＜

ai 中的指数值，i=2,?,n}

基本操作：sort(Polyn & h); //对多项式进行排序

print(Polyn h); //输出多项式 delZeroCoef(Polyn & h); //判断系数为零的情况 merge(Polyn & h); //合并指数相同的项

createList(); //创建多项式

addPoly(Polyn h1,Polyn h2); //多项式相加

subPoly(Polyn h1,Polyn h2); //多项式相减 multPoly(Polyn h1,Polyn h2); //多项式相乘

} ADT Polynomial

1.3 详细设计

#include #include #include typedef struct LNode { float coef; int expn;

struct LNode *next; }LNode;

LNode* InitPolyn(LNode *La,int n) {

4

数据结构课程设计

if(n <= 0) return NULL;

LNode *h = La = (LNode*)malloc(sizeof(LNode)), *Lb; La->coef = 0.0; int i;

printf(\依次输入%d个非零项（每项前一个为系数，后一个为指数）\\n\for (i = 1; i <= n; ++i) { scanf(\if(La->coef) Lb = La;

La = La->next = (LNode*)malloc(sizeof(LNode)); }

Lb->next = NULL; free(La); return h; }

LNode* selsort(LNode *h) { LNode *g, *La, *Lb; if(!h) return NULL; float f;

int i, fini = 1;

for(g = h;g->next&&fini;g = g->next) { fini = 0;

for(La = h,Lb = h->next;Lb;La = La->next,Lb = Lb->next) if (La->expn < Lb->expn) {

5

数据结构课程设计

f = La->coef;i = La->expn;

La->coef = Lb->coef;La->expn = Lb->expn; Lb->coef = f;Lb->expn = i; fini = 1; } }

for(g = h,La = g->next;La;) if(g->expn==La->expn) { g->coef += La->coef; g->next = La->next; Lb = La; La = La->next; free(Lb); }

else if(g->next) { g = g->next; La = La->next; } return h; }

void PrintfPoly(LNode *La) { LNode *Lb = La; if(!Lb) { putchar('0');

6

数据结构课程设计

return; }

if(Lb->coef!=1) { printf(\if(Lb->expn==1) putchar('X');

else if(Lb->expn) printf(\}

else if(!Lb->expn) putchar('1'); else if(Lb->expn==1) putchar('X'); else printf(\Lb = Lb->next; while (Lb) {

if(Lb->coef > 0) putchar('+'); if(Lb->coef!=1) { printf(\if(Lb->expn==1) putchar('X');

else if(Lb->expn) printf(\}

else if(!Lb->expn) putchar('1'); else if(Lb->expn==1) putchar('X'); else printf(\Lb = Lb->next; } }

7

数据结构课程设计

int Compare(LNode *a, LNode *b) { if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; }

LNode* AddPolyn(LNode *Pa, LNode *Pb) { LNode *h, *qa = Pa, *qb = Pb, *La, *Lb; float sum;

h = La = (LNode*)malloc(sizeof(LNode)); La->next = NULL; while (qa && qb) { switch (Compare(qa,qb)) { case -1: La->next = qb; La = qb; qb = qb->next; break; case 0:

sum = qa->coef + qb->coef; if (sum != 0.0) { La->next = qa; qa->coef = sum; La = qa; qa = qa->next;

8

数据结构课程设计

} else { Lb = qa; qa = qa->next; free(Lb); } Lb = qb; qb = qb->next; free(Lb); break; case 1: La->next = qa; La = qa; qa = qa->next; break; } }

if (Pa) La->next = qa; if (Pb) La->next = qb; Lb = h; h = h->next; free(Lb); return h; }

9

数据结构课程设计

LNode* Add(LNode *Pa, LNode *Pb) { int n;

puts(\再输入1个一元多项式的项数\scanf(\Pb = InitPolyn(Pb,n); Pb = selsort(Pb); PrintfPoly(Pa);

if(Pb && Pb->coef>0) printf(\PrintfPoly(Pb); Pa = AddPolyn(Pa,Pb); printf(\Pa = selsort(Pa); PrintfPoly(Pa); return Pa; }

LNode* SubtractPolyn(LNode *Pa, LNode *Pb) { LNode *La = Pb; while(La) { La->coef *= -1; La = La->next; }

return AddPolyn(Pa,Pb); }

LNode* Subtract(LNode *Pa, LNode *Pb) {

10

本文来源：https://www.bwwdw.com/article/y6e2.html