# -*- coding: utf-8 -*-
# @Time : 2019-11-01 17:10
# @Author : yuzhou_1su
# @ContactMe : https://blog.csdn.net/yuzhou_1shu
# @File : DynamicArray.py
# @Software : PyCharm
import ctypes
class DynamicArray:
"""A dynamic array class akin to a simplified Python list."""
def __init__(self):
"""Create an empty array."""
self.n = 0 # count actual elements
self.capacity = 1 # default array capacity
self.A = self._make_array(self.capacity) # low-level array
def is_empty(self):
""" Return True if array is empty"""
return self.n == 0
def __len__(self):
"""Return numbers of elements stored in the array."""
return self.n
def __getitem__(self, i):
"""Return element at index i."""
if not 0 <= i < self.n:
# Check it i index is in bounds of array
raise ValueError('invalid index')
return self.A[i]
def append(self, obj):
"""Add object to end of the array."""
if self.n == self.capacity:
# Double capacity if not enough room
self._resize(2 * self.capacity)
self.A[self.n] = obj # Set self.n index to obj
self.n += 1
def _resize(self, c):
"""Resize internal array to capacity c."""
B = self._make_array(c) # New bigger array
for k in range(self.n): # Reference all existing values
B[k] = self.A[k]
self.A = B # Call A the new bigger array
self.capacity = c # Reset the capacity
@staticmethod
def _make_array(c):
"""Return new array with capacity c."""
return (c * ctypes.py_object)()
def insert(self, k, value):
"""Insert value at position k."""
if self.n == self.capacity:
self._resize(2 * self.capacity)
for j in range(self.n, k, -1):
self.A[j] = self.A[j-1]
self.A[k] = value
self.n += 1
def pop(self, index=0):
"""Remove item at index (default first)."""
if index >= self.n or index < 0:
raise ValueError('invalid index')
for i in range(index, self.n-1):
self.A[i] = self.A[i+1]
self.A[self.n - 1] = None
self.n -= 1
def remove(self, value):
"""Remove the first occurrence of a value in the array."""
for k in range(self.n):
if self.A[k] == value:
for j in range(k, self.n - 1):
self.A[j] = self.A[j+1]
self.A[self.n - 1] = None
self.n -= 1
return
raise ValueError('value not found')
def _print(self):
"""Print the array."""
for i in range(self.n):
print(self.A[i], end=' ')
print()
def main():
# Instantiate
mylist = DynamicArray()
# Append new element
mylist.append(10)
mylist.append(9)
mylist.append(8)
# Insert new element in given position
mylist.insert(1, 1024)
mylist.insert(2, 2019)
# Check length
print('The array length is: ', mylist.__len__())
# Print the array
print('Print the array：')
mylist._print()
# Index
print('The element at index 1 is :', mylist[1])
# Remove element
print('Remove 2019 in array:')
mylist.remove(2019)
mylist._print()
# Pop element in given position
print('Pop pos 2 in array:')
# mylist.pop()
mylist.pop(2)
mylist._print()
if __name__ == '__main__':
main()
激动人心的时刻揭晓，测试结果如下。请结合测试代码和数组的结构进行理解，如果由疏漏，欢迎大家指出。
The array length is: 5
Print the array：
10 1024 2019 9 8
The element at index 1 is : 1024
Remove 2019 in array:
10 1024 9 8
Pop pos 2 in array:
10 1024 8
