数据结构-数组

发表于 更新于 分类于 阅读次数：
数据结构之数组的描述与总结

总结

数组是对线性表的顺序存储结构的一种实现。线性表的顺序存储结构（后面就称为顺序表结构）在内存中的存储空间是连续的（线性的），因此只要我们知道顺序表的首地址和单个元素的所占地址大小，我们就可以求出第i个元素的地址。

顺序表在内存中的存储示意图

值得注意的是，在C++语言中，数组的下标从0开始，因此数组的第i个元素的下标为i-1

数组的操作

以一维数组为例，介绍数组的增删查改与排序。

增加

一般的，数组的元素增加分为两步，第一步将要增加的索引的后方的元素全部往后挪动一个地址空间，第二步将要增加的元素定义在相应的索引位置的空间。值得注意的是，如果往后挪动过程的中超出了数组的最大长度，则会丢失超出的部分的值。

删除

一般的，数组的元素删除分为两步，第一步将要删除的索引的地址空间的值无效化，第二步将删除索引后的有元素的内容向前挪动一个地址空间。

查找

查找可以分为两种，一种是按索引查找，第二种是按值查找，按值查找需要使用遍历的方法，从头开始进行对比值是否是目标值，而根据索引则可以直接获取到目标值。

修改

修改方法一般是找到元素的索引，然后根据索引位置，对相应的索引位置的元素的值进行修改。

排序

排序一般是对元素按元素值进行从小到大或者从大到小的顺序进行排序。

代码实现

简单代码实现:

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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <functional>
#include <iostream>

template <class T> class Vector
{
public:
    Vector(int max_len) : max_len_(max_len)
    {
        vec_ptr_ = new T[max_len_];
    }

    ~Vector()
    {
        delete[] vec_ptr_;
    }

    // 输出
    void Show()
    {
        for (int i = 0; i < len_; ++i)
        {
            std::cout << vec_ptr_[i] << " ";
        }
        std::cout << "\n";
    }

    // 增加
    bool Add(int index, T value)
    {
        if (index >= max_len_)
        {
            return false;
        }
        // 往后挪动一个位置
        for (int i = len_ - 1; i >= index; --i)
        {
            vec_ptr_[i + 1] = vec_ptr_[i];
        }

        // 增加并修改当前长度
        vec_ptr_[index] = value;
        if (index >= len_)
        {
            len_ = index + 1;
        }
        return true;
    }

    // 删除
    bool Delete(int index)
    {
        if (index >= max_len_)
        {
            return false;
        }
        // 直接覆盖原位置
        for (int i = index; i < len_ - 1; ++i)
        {
            vec_ptr_[i] = vec_ptr_[i + 1];
        }
        --len_;
        return true;
    }

    // 查找，根据值查找第一个索引
    int Find(T value)
    {
        for (int i = 0; i < len_; ++i)
        {
            if (vec_ptr_[i] == value)
            {
                return i;
            }
        }
        return -1;
    }

    // 获取，根据索引获取值
    int Get(unsigned int index, T& got_value)
    {
        if (index >= len_ || index >= max_len_)
        {
            return -1;
        }
        got_value = vec_ptr_[index];
        return 0;
    }

    // 修改
    bool Modify(unsigned int index, T value)
    {
        if (index >= max_len_ || index >= len_)
        {
            return false;
        }
        vec_ptr_[index] = value;
        return true;
    }

    // 排序 简单的冒泡排序
    void Sort(std::function<bool(T, T)>&& func)
    {
        for (int i = 0; i < len_ - 1; i++)
        {
            for (int j = 0; j < len_ - i - 1; j++)
            {
                if (!func(vec_ptr_[j], vec_ptr_[j + 1]))
                {
                    T temp = vec_ptr_[j];
                    vec_ptr_[j] = vec_ptr_[j + 1];
                    vec_ptr_[j + 1] = temp;
                }
            }
        }
    }

private:
    int max_len_ = 0;
    int len_ = 0;
    T* vec_ptr_;
};

int main()
{
    Vector<char> vec(5);
    // 增加
    vec.Add(0, 'x');
    vec.Add(1, 'a');
    vec.Add(2, 'b');
    vec.Add(3, 'c');
    vec.Add(4, 'd');
    vec.Add(5, 'e');
    vec.Show();
    // 获取
    char got_value = ' ';
    if (-1 != vec.Get(1, got_value))
    {
        std::cout << "Get index:" << 1 << " value:" << got_value << std::endl;
    }
    else
    {
        std::cout << "Get index:" << 1 << " Faild" << std::endl;
    }
    if (-1 != vec.Get(6, got_value))
    {
        std::cout << "Get index:" << 6 << " value:" << got_value << std::endl;
    }
    else
    {
        std::cout << "Get index:" << 6 << " Faild" << std::endl;
    }
    // 删除
    std::cout << "delete index 2:" << std::endl;
    vec.Delete(2);
    vec.Show();
    // 修改
    vec.Modify(3, 'y');
    vec.Show();
    // 查找
    int index = -1;
    index = vec.Find('b');
    std::cout << "value is " << 'b' << " index is " << index << std::endl;
    // 查找
    index = -1;
    index = vec.Find('x');
    std::cout << "value is " << 'x' << " index is " << index << std::endl;
    vec.Show();
    std::cout << "sorted end:" << std::endl;
    vec.Sort([](const char& c1, const char& c2) -> bool { return c1 < c2; });
    vec.Show();
}

执行结果：
x a b c d
Get index:1 value:a
Get index:6 Faild
a b c d
a b c b
value is b index is 1
value is x index is -1
a b c b
sorted end:
a b b c