【2012四川大学,数据结构与算法设计】第4讲 数组和广义表

Chapter 4 Array & General List

Section 1Array

ADT Array { D={ aj1,j2, ...,,ji, jn|ji=0,...,bi-1, i=1,2,..,n } (n称数组的维数，bi是数组第i维的长度，ji是数组元素的第i维下标)

数组的抽象数据类型定义

基本操作

R={R1, R2, ..., Rn} Ri={<aj1,... ji,... jn ,aj1, ...ji+1, ...jn >|0 jk bk-1, 1 k n且k i, 0 ji bi-2,i=2,...,n }

} ADT Array

二维数组的定义数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1}

数据关系:R = { ROW, COL }

COL = {<ai,j,ai+1,j>| 0≤i≤b1-2, 0≤j≤b2-1}ROW = {<ai,j,ai,j+1>| 0≤i≤b1-1, 0≤ j≤b2-2}

基 本 操 作InitArray(&A, n, bound1, ..., boundn) DestroyArray(&A) Value(A, &x, index1, ..., indexn) Assign(&A, x, index1, ..., indexn)

InitArray(&A, n, bound1, ..., boundn)操作结果：若维数 n 和各维长度 合法，则构造相应的 数组A,并返回OK。

DestroyArray(&A)操作结果：销毁数组A。

Value(A, &x, index1, ..., indexn)初始条件： A是n维数组，x为元素变

量，随后是n 个下标值。操作结果：若各下标不超界，则x赋值 为所指定的A 的元素值，并

返回OK。

Assign(&A, x, index1, ..., indexn)初始条件： A是n维数组，x为 元素变量，随后是n 个下标值。 操作结果：若下标不超界，则 将 x的值赋给所指 定的A的元素，并 返回 OK。

一维数组

定义 相同类型的数据元素的集合。 一维数组的示例0 1 2 3 4 5 6 7 8 9 35 27 49 18 60 54 77 83 41 02

与顺序表的不同在于数组可以按 元素的下标直接存储和访问数组 元素。

一维数组(Array) 类的定义

template <class Type> class Array { Type *elements; //数组存放空间 int ArraySize; //当前长度 void getArray ( ); //建立数组空间 public: Array( int Size=DefaultSize ); Array( const Array<Type>& x );

~Array( ) { delete [ ]elements;} Array<Type> &operator= //数组赋值 ( const Array<Type> & A ); Type &operator[ ]( int i ); //取元素值 int Length()const { return ArraySize; } //取数组长度 void ReSize ( int sz ); //扩充数组 }

一维数组公共操作的实现

template <class Type> void Array<Type> :: getArray ( ) { //私有函数：创建数组存储空间 elements = new Type[ArraySize]; }

template <class Type> Array<Type> :: Array ( int sz ) { ArraySize = sz; getArray ( ); }

template <class Type> Array<Type>::Array(Array<Type> &x){ int n = ArraySize = x.ArraySize; elements = new Type[n]; Type *srcptr = x.elements; Type *destptr = elements; while ( n-- ) * destptr++ = * srcptr++; }

template <class Type> Array<Type>::Array(Array<Type> &x){ int Size = x.ArraySize; elements = new Type[Size]; for(int i=0;i<Size;i++) elements[i]=x.elements[i]; }

template <class Type> Type& Array<Type>::operator[ ](int i){ if ( i < 0 || i > ArraySize-1 ) { cerr << “数组下标超界” << endl; return NULL; } return elements[i]; }

template <class Type> void Array<Type> :: Resize ( int sz ) { if ( sz >= 0 &

& sz != ArraySize ) { Type * newarray = new Type[sz]; int n = ( sz < ArraySize ) ? sz : ArraySize; //按新的大小确定传送元素个数

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