清华大学：《数据结构》课程教学资源（PPT课件讲稿）第二章 数组

第章数组 o作为抽象数据类型的数组 o顺序表(Sequential List) o多项式抽象数据类型 (Polynomial ADT) o稀疏矩阵(Sparse Matrix) o字符串(String)

作为抽象数据类型的数组 顺序表 (Sequential List) 多项式抽象数据类型 (Polynomial ADT) 稀疏矩阵 (Sparse Matrix) 字符串 (String)

作为抽象数据类型的数组 0一维数组 口一维数组的示例 0123456789 35274918605477834102

作为抽象数据类型的数组 一维数组 一维数组的示例

一雏数组的特点 a连续存储的线性聚集(别名向量) a除第一个元素外,其他每一个元素有 个且仅有一个直接前驱。 a除最后一个元素外,其他每一个元素 有一个且仅有一个直接后继。 012345678 a352749186054778341 90 乙*

一维数组的特点 连续存储的线性聚集（别名 向量） 除第一个元素外，其他每一个元素有 一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素 有一个且仅有一个直接后继

数组的定义和初始化 #include class szci int eo public score=0; scl(int value ie=value; 3 int get value( return e; 3

数组的定义和初始化 #include class szcl { int e; public: szcl ( ) { e = 0; } szcl ( int value ) { e = value; } int get_value ( ) { return e; } }

main(i scl a13]={3,5,7},*elem; for(inti=0,3,计++) cout <<alli.get value o<<"n; /打印静恋数组 elem = &al for(inti=0,3,计+){ cout << elem-get value(<<"n; /打印动恋数组 elem++ return 0;

main ( ) { szcl a1[3] = { 3, 5, 7 }, *elem; for ( int i=0, i<3, i++ ) cout << a1[i].get_value ( ) << “\n”; //打印静态数组 elem = &a1; for ( int i=0, i<3, i++ ) { cout << elem→get_value( ) << “\n”; //打印动态数组 elem++; } return 0; }

一维数组Ar类的义 #include #include template class Array i Type elemen;数组存放空间 int ArraySize /前长度 void getArray(;∥建立数组空间 public C° Array(int Size- DefaultSize ) Array(const Array&x)

一维数组(Array)类的定义 #include #include template class Array { Type *elements; //数组存放空间 int ArraySize; //当前长度 void getArray ( ); //建立数组空间 public: Array(int Size=DefaultSize ); Array(const Array& x );

cArrayoi delete l elements; 3 array K& operator const Array &A); Type& operato[](int i); Array operator Type *( const i return elements; y int Length( const f return Array Size; j void Resize( int sz)

~Array( ) { delete [ ]elements;} Array & operator = ( const Array & A ); Type& operato [ ] ( int i ); Array operator Type * ( ) const { return elements; } int Length ( ) const { return ArraySize; } void ReSize ( int sz ); }

一雏数组公共操作的实现 template void Array:getArray o& /私有函数:创建数组存储空 elements new Type[Array Size]: if (elements ==0) cerr << Memory allocation Error/ <Kendl

template void Array::getArray ( ) { //私有函数：创建数组存储空间 elements = new Type[ArraySize]; if ( elements == 0 ) cerr << "Memory Allocation Error" <<endl; } 一维数组公共操作的实现

template void Array:: Array( int sz)& /构造函数 f(sz<=0){ cerr < "Invalid Array size"<< endl; return Array Size =Sz; getarray(

template void Array::Array ( int sz ) { //构造函数 if ( sz <= 0 ) { cerr << "Invalid Array Size" << endl; return; } ArraySize = sz; getArray ( ); }

template Array:: Array( const Array &xi )制构造函数 int n= Array Size =x Array Size elements= new Typen; if (elements ==0) cerr<<"Memory Allocation Error < endl Type *srcptr=x elements, Type * destptr =elements; whille(n-)*destptr++=*srcptr++

template Array:: Array ( const Array & x ) { //复制构造函数 int n = ArraySize = x.ArraySize; elements = new Type[n]; if ( elements == 0 ) cerr << "Memory Allocation Error" << endl; Type *srcptr = x.elements; Type *destptr = elements; while ( n-- ) * destptr++ = * srcptr++; }