我必须在python中实现Vector ADT。所有其他方法都有效，但我坚持执行insert和remove。
insert（index，element）：将给定元素插入位置索引处的向量中。给定位置处和之后的元素向下移动以为新项目腾出空间。索引必须在有效范围内，并且向量不能满。如果index是向量末尾之外的一个位置，则该项目将附加到向量上。
remove（index）：从向量中移除位置索引处的元素。将返回已删除的元素。移除的元素之后的所有元素向下移动一个位置以关闭由移除的元素产生的间隙。
我的代码：
from ezarrays import Array
class Vector :
# Creates an empty vector instance.
def __init__(self) :
self._theArray = Array( 2 )
self._capacity = 2
self._numItems = 0
# Returns the number of elements in the vector.
def __len__(self):
return self._numItems
# Returns the element at the given index position.
def __getitem__(self, index) :
assert index >= 0 and index < self._numItems, "Index out of range."
return self._theArray[index]
# Stores the given element at the given index position.
def __setitem__(self, index, element) :
assert index >= 0 and index <= self._numItems, "Index out of range."
if index == self._numItems :
self.append(element)
else :
self._theArray[index] = element
# Returns a string representation of the vector in the form: [e1, e2 ...]
def __repr__(self) :
if self._numItems == 0 :
return "[]"
else :
result = ""
i = 0
while i < self._numItems - 1 :
result = result + str(self._theArray[i]) + ", "
i = i + 1
result = result + str(self._theArray[i])
return "[" + result + "]"
# Appends the given element to the end of the vector.
def append(self, element) :
if self._numItems == self._capacity :
self._expandArray()
index = self._numItems
self._theArray[index] = element
self._numItems = self._numItems + 1
# Returns a Boolean indicating if the given element is in the vector.
def __contains__(self, element) :
for i in range(self._numItems):
if self._theArray[i] == element:
return True
return False
# Returns the position index within the vector that contains the given element
def index(self, element) :
assert element in self, "The element must be in the list."
for i in range(self._numItems) :
index = self._theArray[i]
if index == element :
return i
# Inserts the given element into the vector at position index
def insert(self, index, element) :
assert index >= 0 and index <= self._numItems, "Index out of range."
if self._numItems == self._capacity:
self._expandArray()
i=0
while i < len(self._theArray):
element = self._theArray[i]
do_action(element)
if check(element):
del self.-_theArray[i]
else:
i+=1
# Removes the element at position index from the vector.
def remove(self, index) :
pass
# Removes all elements from the vector resulting in an empty vector
def clear(self) :
self.theArray = Array(2)
self._capacity = 2
self._numItems = 0
# expands the array by expanding capacity and making a new array
def _expandArray(self) :
newCapacity = self._capacity * 2
newArray = Array( newCapacity )
for i in range (len(self._theArray)):
newArray[i] = self._theArray[i]
self._theArray = newArray
执行ezarrays（这是数组）导入ctypes
class Array :
# Creates an array with size elements.
def __init__( self, size ):
assert size > 0, "Array size must be > 0"
self._size = size
# Create the array structure using the ctypes module.
PyArrayType = ctypes.py_object * size
self._elements = PyArrayType()
# Initialize each element.
self.clear(None)
# Returns the size of the array.
def __len__( self ):
return self._size
# Gets the contents of the index element.
def __getitem__( self, index ):
assert index >= 0 and index < len(self), "Array subscript out of range"
return self._elements[ index ]
# Puts the value in the array element at index position.
def __setitem__( self, index, value ):
assert index >= 0 and index < len(self), "Array subscript out of range"
self._elements[ index ] = value
# Clears the array by setting each element to the given value.
def clear( self, value ) :
for i in range(len(self)) :
self._elements[i] = value
# Implementation of the Array2D ADT using an array of arrays.
class Array2D :
# Creates a 2-D array of size numRows x numCols.
def __init__( self, numRows, numCols ):
# Create a 1-D array to store an array reference for each row.
self._theRows = Array(numRows)
# Create the 1-D arrays for each row of the 2-D array.
for i in range( numRows ) :
self._theRows[i] = Array(numCols)
# Returns the number of rows in the 2-d array.
def numRows( self ):
return len( self._theRows )
# Returns the number of columns in the 2-d array.
def numCols( self ):
return len( self._theRows[0] )
# Clears the array by setting every element to the given value.
def clear( self, value ):
for row in range(len(self._theRows)) :
self._theRows[row].clear(value)
# Get the contents of the element at position [i, j]
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]
# Set the contents of the element at position [i,j] to value.
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
好的，因为我没有你正在使用的模块我无法真正测试代码，但这是我的想法：
def remove(self, idx):
elem = self._theArray[idx]
new_array = Array(self._capacity-1)
for i in range(0, self._numItems):
if i != idx:
new_array.append(self._theArray[i])
self._theArray = new_array
return elem
def insert(self, index, element) :
assert index >= 0 and index <= self._numItems, "Index out of range."
if self._numItems == self._capacity:
self._expandArray()
for i in reversed(range(index, self._numItems)):
self._theArray[i+1] = self._theArray[i]
self._theArray[index] = element