数据结构课件(前)数组讲.pptVIP

多项式 (Polynomial) n阶多项式Pn(x)有n+1项。 系数 a0, a1, a2, …, an 指数 0, 1, 2, …, n。按升幂排列 多项式(Polynomial)的抽象数据类型 class Polynomial { public: Polynomial ( ); //构造函数 bool operator ! ( ); //判是否零多项式 Coefficient Coef (Exponent e); Exponent LeadExp ( ); //返回最大指数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); //求值 } 创建power类，计算x的幂 #include iostream.h class power { double x; int e; double mul; public: power (double val, int exp); double get_power ( ) { return mul; } }; //按val值计算乘幂 power::power (double val, int exp) { x = val; e = exp; mul = 1.0; if (exp == 0 ) return; for ( ; exp0; exp--) mul = mul * x; } void main ( ) { power pwr ( 1.5, 2 ); cout pwr.get_power ( ) “\n”; } 多项式的存储表示 第一种： 静态数组表示 private: int degree; float coef [maxDegree+1]; Pn(x)可以表示为： pl.degree = n pl.coef[i] = ai, 0 ? i ? n 第二种： 动态数组表示 private: int degree; float * coef; Polynomial::Polynomial (int sz) { degree = sz; coef = new float [degree + 1]; } 以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如P101(x) = 3 + 5x50 - 14x101, 不经济。 第三种 class Polynomial; class term { //多项式的项定义 friend Polynomial; private: float coef; //系数 int exp; //指数 }; //多项式定义 class Polynomial { public: …… private: static term termArray[MaxTerms]; //项数组 static int free; //当前空闲位置指针 // term Polynomial::termArray[MaxTerms]; // int Polynomial::free = 0; int start, finish; //多项式始末位置 } 两个多项式存放在termArray中 A(x) = 2.0x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101 两个多项式的相加 结果多项式另存 扫描两个相加多项式，若都未检测完： 若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。 若当前被检测项指数不等，将指数小者加到结果多项式。 若有一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。 Polynomial Polynomial::Add ( Polynomial B ) { Polynomial C; int a = start;