数组Array是最基本的数据结构,在内存中为一段定长连续内存,很多编程语言都有实现。
一、一维数组
下面代码实现了一维数组和它的遍历。
clear并非清空数组,而是采用具体值对数组进行初始化。
import ctypes class Array : def __init__( self, size ): assert size > 0, "Array size must be > 0" self._size = size PyArrayType = ctypes.py_object * size self._elements = PyArrayType() self.clear( None ) def __len__( self ): return self._size def __getitem__( self, index ): assert index >=0 and index < len(self), "Array subscript out of range" return self._elements[ index ] def __setitem__( self, index, value ): assert index >=0 and index < len(self), "Array subscript out of range" self._elements[ index ] = value def clear( self, value ): for i in range( len(self) ) : self._elements[i] = value def __iter__( self ): return _ArrayIterator( self._elements )
class _ArrayIterator : def __init__( self, theArray ): self._arrayRef = theArray self._curNdx = 0 def __iter__( self ): return self def __next__( self ): if self._curNdx < len( self._arrayRef ) : entry = self._arrayRef[ self._curNdx ] self._curNdx += 1 return entry else : raise StopIteration if __name__=='__main__': myarray=Array(5) myarray.clear(1) myarray.__setitem__(2,5) print myarray.__getitem__(2) it=myarray.__iter__() while True: try: print it.__next__() except StopIteration: break
二、二维数组
二维数组的构造基于一维数组Array,它可以看做是一个以行数为size的一维数组,区别在于数组中的每个元素并不是具体的值,而是由以列数为size的数组构成。如下图所示:
class Array2D : def __init__( self, numRows, numCols ): self._theRows = Array( numRows ) for i in range( numRows ) : self._theRows[i] = Array( numCols ) def numRows( self ): return len( self._theRows ) def numCols( self ): return len( self._theRows[0] ) def __getitem__( self, ndxTuple ): assert len(ndxTuple) == 2, "Invalid number of array subscripts." row = ndxTuple[0] col = ndxTuple[1] assert row >=0 and row < self.numRows() and col >=0 and col < self.numCols(), "Array subscript out of range." the1dArray = self._theRows[row] return the1dArray[col] def __setitem__( self, ndxTuple, value ): assert len(ndxTuple) == 2, "Invalid number of array subscripts." row = ndxTuple[0] col = ndxTuple[1] assert row >=0 and row < self.numRows() and col >=0 and col < self.numCols(), "Array subscript out of range." the1dArray = self._theRows[row] the1dArray[col] = value