数据结构与算法.ppt
《数据结构与算法.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法.ppt(67页珍藏版)》请在三一文库上搜索。
1、数据结构与算法,2006.9-2007.1,作为抽象数据类型的数组,一维数组 一维数组的示例,一维数组的特点,连续存储的线性聚集(别名 向量) 除第一个元素外,其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外,其他每一个元素有一个且仅有一个直接后继。,数组的定义和初始化,#include class szcl int e; public: szcl ( ) e = 0; szcl ( int value ) e = value; int get_value ( ) return e; ,main ( ) szcl a13 = 3, 5, 7 , *elem; for ( int i=
2、0, i3, i+ ) cout a1i.get_value ( ) “n”; /打印静态数组 elem = ,一维数组(Array)类的定义,#include #include template class Array Type *elements; /数组存放空间 int ArraySize; /当前长度 void getArray ( ); /建立数组空间 public: Array(int Size=DefaultSize ); Array(const Array,Array( ) delete elements; Array ,template void Array:getArray
3、 ( ) /私有函数:创建数组存储空间 elements = new TypeArraySize; if ( elements = 0 ) cerr “Memory Allocation Error“ endl; ,一维数组公共操作的实现,template void Array:Array ( int sz ) /构造函数 if ( sz = 0 ) cerr “Invalid Array Size“ endl; return; ArraySize = sz; getArray ( ); ,template Array: Array ( const Array ,template Type 使
4、用该函数于赋值语句 Positioni = Positioni -1 + Numberi -1,template void Array:Resize (int sz) if ( sz = 0 ,二维数组 三维数组,行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k,数组的连续存储方式,一维数组,LOC ( i ) = LOC ( i -1 ) + l =+ i*l,二维数组,行优先 LOC ( j, k ) = j * m + k,n维数组,各维元素个数为 m1, m2, m3, , mn 下标为 i1, i2, i3, , in 的数组元素的存储地址:,
5、顺序表 (Sequential List),顺序表的定义和特点 定义 n( 0)个表项的有限序列 (a1, a2, , an) ai是表项,n是表长度。 特点 顺序存取 遍历 逐项访问 从前向后 从后向前 从两端向中间,顺序表(SeqList)类的定义,template class SeqList Type *data; /顺序表存储数组 int MaxSize; /最大允许长度 int last; /当前最后元素下标 public: SeqList ( int MaxSize = defaultSize ); SeqList ( ) delete data; int Length ( ) c
6、onst return last+1; int Find ( Type ,int IsIn ( Type ,顺序表部分公共操作的实现,template SeqList:SeqList ( int sz ) /构造函数 if ( sz 0 ) MaxSize = sz; last = -1; data = new TypeMaxSize; ,template int SeqList:Find ( Type ,顺序搜索图示,x = 48 x = 50,搜索成功 若搜索概率相等,则 搜索不成功 数据比较 n 次,表项的插入,template int SeqList:Insert ( Type /插入
7、成功 ,表项的删除,template int SeqList:Remove ( Type /表中没有 x ,顺序表的应用:集合的“并”运算,template void Union ( SeqList ,template void Intersection ( SeqList /未找到在LA中删除它 ,顺序表的应用:集合的“交”运算,多项式 (Polynomial),n阶多项式Pn(x)有n+1项。 系数 a0, a1, a2, , an 指数 0, 1, 2, , n。按升幂排列,class Polynomial public: Polynomial ( ); /构造函数 int operat
8、or ! ( ); /判是否零多项式 Coefficient Coef (Exponent e); Exponent LeadExp ( ); /返回最大指数 Polynomial Add (Polynomial poly); Polynomial Mult (Polynomial poly); float Eval ( float x); /求值 ,多项式(Polynomial)的抽象数据类型,#include class power double x; int e; double mul; public: power (double val, int exp); double get_po
9、wer ( ) return mul; ;,创建power类,计算x的幂,power:power (double val, int exp) /按val值计算乘幂 x = val; e = exp; mul = 1.0; if (exp = 0 ) return; for ( ; exp0; exp-) mul = mul * x; main ( ) power pwr ( 1.5, 2 ); cout pwr.get_power ( ) “n”; ,多项式的存储表示,第一种: private: (静态数 int degree; 组表示) float coef maxDegree+1; Pn(
10、x)可以表示为: pl.degree = n pl.coefi = 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; priv
11、ate: float coef; /系数 int exp; /指数 ;,class Polynomial /多项式定义 public: private: static term termArrayMaxTerms; /项数组 static int free; /当前空闲位置指针 / term Polynomial:termArrayMaxTerms; / int Polynomial:free = 0; int start, finish; /多项式始末位置 ,A(x) = 2.0x1000+1.8 B(x) = 1.2 + 51.3x50 + 3.7x101,两个多项式存放在termArra
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法
链接地址:https://www.31doc.com/p-3185605.html