python数据结构之数组

代码思路是对python Array的类的重写，实现动态数组。不过有点小问题，先Mark起来，debug完再补充进来。

class Array(object):
    """Represents an array."""

    def __init__(self, capacity, fillValue = None):
        """Capacity is the static size of the array.
        fillValue is placed at each position."""
        self._items = list()
        for count in range(capacity):
            self._items.append(fillValue)

    def __len__(self):
        """-> The capacity of the array."""
        return len(self._items)

    def __str__(self):
        """-> The string representation of the array."""
        return str(self._items)

    def __iter__(self):
        """Supports iteration over a view of an array."""
        return iter(self._items)

    def __getitem__(self, index):
        """Subscript operator for access at index."""
        return self._items[index]

    def __setitem__(self, index, newItem):
        """Subscript operator for replacement at index."""
        self._items[index] = newItem

"""
1. 利用动态数组解决数据存放问题

编写一段代码，要求输入一个整数N，用动态数组A来存放2~N之间所有5或7的倍数，输出该数组。

示例：

输入：
N = 100

输出：
5 7 10 14 15 20 21 25 28 30 35 40 42 45 49 50 55 56 60 63 65 70 75 77 80 84 85 90 91 95 98 100

"""

from arrays import Array

# a = Array(5)
#
# print(len(a))
# for i in range(len(a)):
#     print(a[i])


class DynamicArray(Array):
    """
    capacity 物理长度 即对于给定N=100,则初始化长度为100的数组
    logicalSize 逻辑长度，根据其和物理长度的关系决定insert delete 等等
    """
    def __init__(self, capacity, fillValue=None, logicalSize=0):
        super(DynamicArray, self).__init__(capacity, fillValue=None)
        # if fillValue != None:
        #     for i in range(capacity):
        #         self._items = fillValue[i]


        def produce_array(capacitys, logicalsizes, fillValue=None):
            if fillValue == None:
                tem = Array(capacitys, fillValue=None)
                for i in range(capacitys):
                    tem[i] = i + 1
                    logicalsizes += 1
                return tem, logicalsizes
            else:
                tem = Array(capacitys, fillValue)
                for i in range(capacitys):
                    tem[i] = fillValue[i]
                    logicalsizes += 1
                return tem, logicalsizes

        self.array, self.logicalSize = produce_array(capacity, logicalSize)

    #
    def dynamic_append(self, in_array, value):
        if in_array.logicalSize == len(in_array.array):
            temp = Array(capacity=len(in_array.array) + 1)
            for i in range(in_array.logicalSize):
                temp[i] = in_array.array[i]
            temp[in_array.logicalSize] = value
            in_array = temp
            return in_array


#
class OutputX5X7():
    def __init__(self):
        pass

    def __call__(self, length):
        self.in_array = DynamicArray(capacity=length)
        self.out_array = DynamicArray(capacity=1)
        k = 1
        for i in range(length):
            if self.in_array.array[i] % 5 == 0 or self.in_array.array[i] % 7 == 0:
                if k:
                    self.out_array.array[0] = self.in_array.array[i]
                    k = 0
                else:
                    self.out_array = self.out_array.dynamic_append(self.out_array, self.in_array.array[i])
                    self.out_array = DynamicArray(capacity=len(self.out_array), fillValue=self.out_array._items)

        return self.out_array


A = OutputX5X7()
print(A(100))