实现动态数组

实现动态数组

关键点：

1. 增删查改方法齐全
2. 自动扩容缩容：
   • 当数组容量达到静态数组容量上限时，扩容为原来的2倍
   • 当数组容量小于等于静态数组容量的1/4时，缩容为原来的1/2
3. 索引越界时抛出异常
4. 删除元素防止内存泄漏

以下为c++实现动态数组样例：

#include <iostream>
#include <stdexcept>

template <typename E>
class MyArray {
    private:
        E* data;
        int size;
        static const int INIT_CAP = 1;
        int cap;
    public:
        MyArray() {
            this->data = new E[INIT_CAP];
            this->size = 0;
            this->cap = INIT_CAP;
        }

        MyArray(int capacity) {
            this->data = new E[capacity];
            this->size = 0;
            this->cap = capacity;
        }
        //增
        void addLast(E e) {
            if (size == cap) {
                resize(2 * cap);
            }
            data[size] = e;
            size++;
        }

        void add(E e, int index) {
            checkPositionIndex(index);
            if (size == cap) {
                resize(2 * cap);
            }
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }

        void addFirst(E e) {
            add(e, 0);
        }
        //删
        E removeLast() {
            if (size == 0) {
               throw std::out_of_range("No element in array");
            }
            if (size <= cap / 4) {
                resize(cap / 2);
            }
            E deleteval = data[size - 1];
            data[size - 1] = NULL;
            size--;
            return deleteval;
        }

        E remove(int index) {
            checkElementIndex(index);
            if (size <= cap / 4) {
                resize(cap / 2);
            }
            E deleteval = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            data[size - 1] = NULL;
            size--;
            return deleteval;
        }

        E removeFirst() {
            return remove(0);
        }
        //改
        E set(E e, int index) {
            checkElementIndex(index);
            E oldval = data[index];
            data[index] = e; 
            return oldval;
        }
        //查
        E get(int index) {
            checkElementIndex(index);
            return data[index];
        }
        //工具
        int getSize() {
            return size;
        }

        bool isEmpty() {
            return size == 0;
        }

        void resize(int newcap) {
            E* temp = new E[newcap];
            for (int i = 0; i < size; i++) {
                temp[i] = data[i];
            }
            delete[] data;
            data = temp;
            cap = newcap;
        }

        bool isPositionIndex(int index) {
            return (index >= 0 && index <= size);
        }

        bool isElementIndex(int index) {
            return (index >= 0 && index < size);
        }

        void checkPositionIndex(int index) {
            if (!isPositionIndex(index)) {
                throw std::out_of_range("Index out of bounds");
            }
        }

        void checkElementIndex(int index) {
            if (!isElementIndex(index)) {
                throw std::out_of_range("Index out of bounds");
            }
        }

        void display() {
            std::cout<<"size = "<<size<<"capacity = "<<cap<<std::endl;
            for (int i = 0; i < size; i++) {
                std::cout<<data[i]<<" ";
            }
            std::cout<<std::endl;
        }

        ~MyArray() {
            delete[] data;
        }
};


int main()
{
    MyArray<int> a(3);
    for (int i = 1; i <= 5; i++) {
        a.addLast(i);
    }
    a.remove(3);
    a.add(9, 1);
    a.addFirst(100);
    int val = a.removeLast();

    //100 1 9 2 3
    for (int i = 0; i < a.getSize(); i++) {
        std::cout<<a.get(i)<<std::endl;
    }

    return 0;
}

以下为Python版：

class MyArray:
    INIT_CAP = 1

    def __init__(self, init_cap = None):
        self.data = [None] * (
            init_cap if init_cap is not None else self.INIT_CAP
        )
        self.size = 0

    #增
    def addLast(self, e):
        cap = len(self.data)
        if self.size == cap:
            self.reSize(cap * 2)
        self.data[self.size] = e
        self.size += 1
    
    def add(self, e, index):
        self.checkPositionIndex(index)
        cap = len(self.data)
        if self.size == cap:
            self.reSize(cap * 2)
        for i in range(self.size - 1, index - 1, -1):
            self.data[i + 1] = self.data[i]
        self.data[index] = e
        self.size += 1

    def addFirst(self, e):
        self.add(e, 0)

    #删
    def removeLast(self):
        if self.size == 0:
            raise IndexError("No such element")
        cap = len(self.data)
        if self.size <= cap / 4:
            self.reSize(cap / 2)
        deleteval = self.data[self.size - 1]
        self.size -= 1
        return deleteval

    def remove(self, index):
        self.checkPositionIndex(index)
        cap = len(self.data)
        if self.size <= cap / 4:
            self.reSize(cap / 2)
        deleteval = self.data[index]
        for i in range(index, self.size):
            self.data[i - 1] = self.data[i]
        self.data[self.size - 1] = None
        self.size -= 1
        return deleteval

    def removeFirst(self):
        return self.remove(0)

    #改
    def set(self, e, index):
        self.checkElementIndex(index)
        oldval = self.data[index]
        self.data[index] = e
        return oldval

    #查
    def get(self, e):
        return self.data[e]

    #工具
    def getSize(self):
        return self.size

    def isEmpty(self):
        return self.size == 0

    def reSize(self, newcap):
        temp = [None] * newcap
        for i in range(self.size):
            temp[i] = self.data[i]
        self.data = temp

    def isPositionIndex(self, index):
        return 0 <= index <= self.size

    def isElementIndex(self, index):
        return 0 <= index <= self.size
    
    def checkPositionIndex(self, index):
        if not self.isPositionIndex(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    def checkElementIndex(self, index):
        if not self.isElementIndex(index):
            raise IndexError(f"Index: {index}, Size: {self.size}")

    #展示
    def display(self):
        for i in range(self.size):
            print(f"Size = {self.size}, Capacity = {len(self.data)}")
            print(self.data)
            

if __name__ == "__main__":
    a = MyArray(init_cap = 3)

    for i in range(1, 6):
        a.addFirst(i)
    
    a.remove(3)
    a.add(9, 1)
    a.addFirst(100)
    val = a.removeLast()
    
    #100 1 9 2 3
    for i in range(a.size):
        print(a.get(i))