Maple's Blog.

动态数组

算法与数据结构
字数统计: 553阅读时长: 2 min
2019/07/05 Share 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
//栈中的ArraY头文件


#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
template<typename T>
class Array{
private:
    T *data;         //数组名
    int size;         //数组中元素的个数
    int Capacity;    //数组容量
public:
    Array(int Capacity){
        data=new T [Capacity];
        this->size=0;
        this->Capacity=Capacity;
    }

    Array(){
        data=new T [100];
        this->size=0;
        this->Capacity=100;
    }

    //获得数组的元素个数
    int  getSize(){
        return size;
    }

    //判断数组是否为空
    bool isEmpty(){
        return size==0;
    }

    //获得数组的容量
    int getArray(){
        return Capacity;
    }

    //在数组中插入一个元素
    void add(int index,T elem){
        if(index<0||index>Capacity){
            cout<<"插入的位置有误"<<endl;
            return ;
        }
        if(size>=Capacity){
            resize(Capacity*2);
        }
        for(int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=elem;
        size++;
    }

    //在数组的最后一个位置添加一个新元素elem;
    void addLast(T elem){
        data[size]=elem;
        size++;
    }

    //获取index位置的数组元素
    T get(int index){
        if(index<0||index>=size){
            cout<<"您输入的位置有误";
            return -1;
        }
        return data[index];
    }

    //在index位置处修改数组元素的值
    void set(int index,T elem){
        if(index<0||index>=size){
            cout<<"您输入的位置有误";
            return ;
        }
        data[index]=elem;
    }


    //查找数组中是否有元素e
    bool contains(T e){
        for(int i=0;i<size;i++){
            if(data[i]==e)
                return true;
        }
        return false;
    }

    //查找数组中元素e的索引index
    int find(T e){
        for(int i=0;i<size;i++){
            if(data[i]==e)
                return i;
        }
        return -1;
    }

    //删除数组中索引为index位置的元素，并且返回被删除的元素的值
    T remove(int index){
        if(index<0||index>=size){
            return -1;
        }
        T ret=data[index];
        for(int i=index+1;i<size;i++){
            data[i-1]=data[i];
        }
        size--;
        //缩容的时候防止复杂度的震荡
        if(size<Capacity/4&&Capacity/2!=0)
            resize(Capacity/2);
        return ret;
    }

    //改变数组的容量
    void resize(int newCapacity){
        T  *newdata=new T [newCapacity];
        for(int i=0;i<size;i++){
            newdata[i]=data[i];
        }
        data=newdata;
        Capacity=newCapacity;
    }

    //打印数组元素
    void PrintArray(){
        for(int i=0;i<size;i++)
            cout<<data[i]<<" ";
        cout<<endl;
    }
};

原文作者：Maple

原文链接：http://yoursite.com/2019/07/05/动态数组/

发表日期：July 5th 2019, 3:01:50 pm

更新日期：July 5th 2019, 11:41:13 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 51
2019
Leetcode 算法与数据结构 C++ 洛谷