数据结构与算法学习-数组

前言

这一篇笔记主要记录总结了线性表数据结构中的数组概念以及相关的算法。

名词解释

1. 线性表（Linear List）

线性表是数据排成像一条线一样的结构，每个线性表上的数据最多有向前和向后两个方向。除了数组外，链表、队列、栈也是线性表数据结构。

image

2. 非线性表

和线性表相对立，数据之间不是简单的前后关系，这样的结构称为非线性表，如图、树、堆等数据结构。

image

数组

数组是一种线性表数据结构，是用一组连续的内存空间，来存储一组具有相同数据类型的数据。几乎在所有的编程语言都存在数组这中最基本的数据结构类型。在 Objective-C 语言中是 NSArray，当然 Objective-C 是 C 的超集，所以也完全可以使用 C 语言的数组类型。

image

随机访问

正式因为数组是用一组连续的内存空间来存储数据的，所以数组支持下标随机访问，复杂度是 O(1)。

int[] a = new int[10]

// 数组a 首地址
base_address = 1000

// 寻址公式 data_type_size：数组中元素的数据类型长度
a[i]_address = base_address + i * data_type_size

插入和删除

相比于复杂度是 O(1)的随机访问操作，对于数组而言，插入和删除操作的复杂度都为O(n)，因为每次要在数组的第 k 个位置插入或者删除一个元素的话，都需要移动 k ~ n 个元素的位置。

优化技巧：

插入操作：如果不需要追求数组中元素的有序，则可以考虑直接将第 k 个位置的元素移到数组的末尾，然后把要插入的新元素放到第 k 个位置就行，这样，复杂度也就是O(1)。
删除操作：在一些场景下，并不追求数组中数据的连续性，可以将多次删除操作集中在一起执行。先记录下已经删除的元素，并不真的删除，当数组没有更多空间时，再触发真正的删除操作，这样可以省下大量重复的数据移动操作。

警惕数组越界问题

看一段 C 语言代码：

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

这里就会出现数组越界问题，C语言的执行结果是未决，就是没有规定数组访问越界时编译器应该如何处理。如果该内存是一块可以访问的不受限内存，在x86架构机器下，那么执行结果是会无线循环打印hello world。原因是内存分配从栈的高位到低位开始，i 变量实际上与数组元素 arr[2] 相邻。数组下标从 0 开始，当执行到循环最后一次 i = 3 时，根据根据之前的寻址公式 a[i]_address = base_address + i * data_type_size，实际上 arr[3] 访问的会是变量 i 的地址，赋值给 i = 0，然后死循环。

这里还和使用的编译器内存分配以及字节对齐有关系，有些编译器会默认开启堆栈保护，当如果变量访问一块不属于自己的内存时，会出现编译错误。
为了不让程序出现这种不确定的错误，导致 debug 难度大，还有就是容易被黑客利用攻击，所以写代码时要特别警惕数组越界。不过很多高级语言的都会默认做越界检查，如 Objective-C 里面的数组，如果越界访问就会下面这种经典错误。

image

怎么选择容器还是数组？

容器优点

1. 将很多数组插入删除等操作细节封装起来，提供很多易用的API。
2. 动态扩容，如果插入数据的时候发现数组的空间不够，就需要重新申请一块更大的内存空间，并把原来的数据都复制进新的数组，在将新的数据插入。但是如果事先知道数据的大小，可以创建的时候就制定好数据的大小，这样可以避免不必要的动态扩容操作。

数组优点

1. 存储基本数据类型。
2. 当数组大小事先已知，并且数据操作比较简单。

总结

日常业务开发，使用高级语言提供的数组容器就行，如 Objective-C 的 NSArray，损失一点性能，但写起来方便简单。如果是做比较注重性能的底层开发，可以考虑使用数组。

数组的下标为什么从 0 开始？

1. 寻址算法，如果下标不从 0 开始，从 1 开始会怎样，寻址算法就变成 a[i]_address = base_address + （i - 1 * data_type_size），转成汇编指令，对于 CPU 而言，就多了一条要执行的减法指令，而这种数组的操作是很频繁很底层的操作，为了优化，所以数组的下标都设计从 0 开始。
2. 历史原因，由于 C 语言是后面很多语言设计的参考，为了保持程序员的编码习惯，所以后面的程序语言设计者也保持和 C 语言数组一样的风格。

课后思考题

1. 前面我基于数组的原理引出 JVM 的标记清除垃圾回收算法的核心理念，我不知道你是否使用 Java 语言，理解 JVM，如果你熟悉回顾下你理解的标记清除垃圾回收算法。

   • 解答： 不熟悉 Java 语言。

2. 前面我们讲到一维数组的内存寻址公式，那你可以思考一下，类比一二维数组的寻址公式是怎样？

   • 解答： m * n 数组，a[i][j]_address = base_address + （i * n + j data_type_size），其中 i < m，j < n。内存布局如下：
   image

数组相关编程题目

1. 实现一个支持动态扩容的数组

// 头文件 ————————————————————————————————————————————————————————
#ifndef DynamicExpansionArray_h
#define DynamicExpansionArray_h

#include <stdio.h>

typedef struct {
    int *array;// 指针数组
    int size; // 数组大小
}Array;

// 创建数组
Array array_creat(int init_size);
// 释放数组
void array_free(Array *a);
// 获取数组大小
int array_size(const Array *a);

// 根据下标获取数组
int* array_at(Array *a, int index);

// 根据下标获取值
int array_get(const Array *a, int index);
// 根据下标设置值
void array_set(Array *a, int index, int value);

// 数组扩容
void array_inflate(Array *a, int more_size);


#endif /* DynamicExpansionArray_h */


// 实现文件 ————————————————————————————————————————————————————
#include "DynamicExpansionArray.h"
#include <stdlib.h>
#include <string.h>

//typedef struct {
//    int *array;
//    int size;
//}Array;

const int BLOCK_SIZE = 20;

// 创建数组
Array array_creat(int init_size)
{
    Array a;
    a.size = init_size;
    a.array = (int *)malloc(sizeof(int) * a.size);
    
    return a;
}

// 释放数组
void array_free(Array *a)
{
    free(a->array);
    a->size = 0;
    // 防止外界重复free导致崩溃，free(NULL) 是没问题的。
    a->array = NULL;
}

// 获取数组大小
int array_size(const Array *a)
{
    return a->size;
}

// 返回对应index的内存地址
int* array_at(Array *a, int index)
{
    if (index < 0) {
        printf("下标不合法！！！！");
    }
    
    // 如果下标大于等于当前最大的size，则数组需要扩容
    if (index >= a->size) {
        array_inflate(a, (index / BLOCK_SIZE + 1) * BLOCK_SIZE - a->size);
    }
    
    // array[index] ：如果分配的是连续的内存空间，指针array可以像数组一样使用
    return &(a->array[index]);
}

// 根据下标获取值
int array_get(const Array *a, int index)
{
    return a->array[index];
}

// 根据下标设置值
void array_set(Array *a, int index, int value)
{
    a->array[index] = value;
}

// 数组扩容
void array_inflate(Array *a, int more_size)
{
    int *p = (int *)malloc((a->size + more_size) * sizeof(int));
    
    // memcoy，将a->array内存拷贝到p
    memcpy(p, a->array, sizeof(int) * a->size);
//    for (int i = 0; i < a->size; i++)
//    {
//        p[i] = a->array[i];
//    }
    
//    free(a->array);
    a->array = p;
    a->size += more_size;
}

// 测试 ——————————————————————————————————————————————————————————
#include <stdio.h>
#include "DynamicExpansionArray.h"

int main(int argc, const char * argv[]) {

    // 创建一个大小 100 数组结构
    Array a = array_creat(10);
    int b[] = {0,1,2,3,4,5,6,7,8,9};
    a.array = b;
    
    printf("size = %d\n", array_size(&a));
    
    // 根据索引下标设置值
    *array_at(&a, 0) = 10;
    *array_at(&a, 1) = 12;
    
    // 根据索引下标取值
    int index_0_Value = *array_at(&a, 0);
    int index_1_Value = *array_at(&a, 1);
    printf("index_0_Value = %d\nindex_1_Value = %d\n",index_0_Value, index_1_Value);
    
    // 设置值
    array_set(&a, 2, 20);
    array_set(&a, 3, 21);
    
    // 测试超出数组下标出插入，动态扩容数组，原来数组空间为 10，现在是120
    *array_at(&a, 101) = 101;
    int index_101_Value = *array_at(&a, 101);
    printf("index_101_Value = %d\n", index_101_Value);
    
    // 打印原来的值
    for (int i = 0; i < 10; i ++) {
        printf("---index_%d_Value %d\n", i, array_get(&a, i));
    }
    
    
    // 释放内存空间
    array_free(&a);
    
    return 0;
}

// 打印日志 ——————————————————————————————————————————————————————————
size = 10
index_0_Value = 10
index_1_Value = 12
index_101_Value = 101
---index_0_Value 10
---index_1_Value 12
---index_2_Value 20
---index_3_Value 21
---index_4_Value 4
---index_5_Value 5
---index_6_Value 6
---index_7_Value 7
---index_8_Value 8
---index_9_Value 9
Program ended with exit code: 0

2. 实现一个大小固定的有序数组，支持动态增删改操作

// 头文件 -----------------------------------------------------
#ifndef SortArray_h
#define SortArray_h

#include <stdio.h>

typedef struct {
    int size;// 数组大小
    int used; // 数组已经使用了多少
    int *array; // 指针
}Array;

// 根据数组大小初始化一个数组
Array arrayCreat(int init_size);

// 释放空间
void arrayFree(Array *a);

// 增，在数组末尾插入新数据
void arrayAdd(Array *a, int value);

// 删
void arrayDelete(Array *a, int index);

// 改，修改指定下标位置的值
void arrayUpdate(Array *a, int index, int value);

#endif /* SortArray_h */


// 实现文件 --------------------------------------------------------
#include "SortArray.h"
#include <stdlib.h>

//typedef struct {
//    int size;// 数组大小
//    int *array; // 指针
//}Array;

// 创建固定大小数组
Array arrayCreat(int init_size)
{
    Array a;
    a.array = (int *)malloc(init_size*sizeof(int));
    a.size = init_size;
    a.used = 0;
    
    return a;
}

// 释放空间
void arrayFree(Array *a)
{
    free(a->array);
    a->size = 0;
    a->used = 0;
    // 防止外界重复free导致崩溃，free(NULL) 是没问题的。
    a->array = NULL;
}

// 增，在数组末尾插入新数据
void arrayAdd(Array *a, int value)
{
    // 先判断数组空间是否满了
    if (a->used == a->size) {
        printf("添加失败，数组空间已满！！！");
    } else {
        // 如果数组为空
        if (a->used == 0) {
            a->array[a->used] = value;
        } else if (value >= a->array[a->used - 1]) {
            // 比数组中最大的还大
            a->array[a->used] = value;
        } else {
            // 循环遍历数组中的元素，比较新加入的值是否比原来每一个元素大，大的话就往前再比
            for (int i = a->used - 1; i >= 0; i--) {
                // 将 i ~ used -1 下标都要往后移动一位
                a->array[i+1] = a->array[i];
                if (value >= a->array[i]) {
                    a->array[i + 1] = value;
                    break;
                } else {
                    if (i == 0) {
                        a->array[i] = value;
                    }
                }
            }
        }
       
        // 加入元素成功，更新used
        a->used += 1;
    }
}

// 删，根据下标删除一个元素
void arrayDelete(Array *a, int index)
{
    // 判断下标是否合法
    if (index >= a->size || index < 0) {
        printf("下标不合法!!!");
    } else {
        // 从 index + 1 ~ used 位置的元素都需要向前移动
        for (int i = index + 1; i < a->used; i ++) {
            a->array[i - 1] = a->array[i];
        }
        
        // 更新used
        a->used -= 1;
    }
}

// 改，修改指定下标位置的值
void arrayUpdate(Array *a, int index, int value)
{
    // 判断下标是否合法
    if (index >= a->used || index < 0) {
        printf("下标 = %d 不合法!!!", index);
    } else {
        if (value != a->array[index]) {
            // 先删掉index位置的元素
            arrayDelete(a, index);
            
            // 重新把value加入进来
            arrayAdd(a, value);
        }
    }
}

// 测试 ------------------------------------------------------------------
// 1. 创建一个 10 大小的固定数组
Array a = arrayCreat(10);
    
// 2.添加元素
printf("-----插入\n");
arrayAdd(&a, -4);
arrayAdd(&a, 8);
arrayAdd(&a, 2);
arrayAdd(&a, 19);
arrayAdd(&a, 4);
arrayAdd(&a, 78);
arrayAdd(&a, 100);
arrayAdd(&a, 11);
arrayAdd(&a, 12);
arrayAdd(&a, 5);
// 插入失败
arrayAdd(&a, 10);
    
printf("\n");
    
// 打印数组元素
for (int i = 0; i < a.used; i++) {
    printf("a[%d] = %d\n", i, a.array[i]);
}
    
// 3. 删除
printf("-----删除\n");
arrayDelete(&a, 0);
arrayDelete(&a, 1);
arrayDelete(&a, 2);
arrayDelete(&a, 3);
arrayDelete(&a, 4);
printf("\n");
    
for (int i = 0; i < a.used; i++) {
    printf("a[%d] = %d\n", i, a.array[i]);
}
    
// 4. 修改
printf("-----修改\n");
arrayUpdate(&a, 0, 10);
arrayUpdate(&a, 5, 50);
printf("\n");
    
for (int i = 0; i < a.used; i++) {
    printf("a[%d] = %d\n", i, a.array[i]);
}
    
// 释放空间
arrayFree(&a);

// 打印日志 --------------------------------------------------------------
-----插入
添加失败，数组空间已满！！！
a[0] = -4
a[1] = 2
a[2] = 4
a[3] = 5
a[4] = 8
a[5] = 11
a[6] = 12
a[7] = 19
a[8] = 78
a[9] = 100
-----删除

a[0] = 2
a[1] = 5
a[2] = 11
a[3] = 19
a[4] = 100
-----修改
下标 = 5 不合法!!!
a[0] = 5
a[1] = 10
a[2] = 11
a[3] = 19
a[4] = 100
Program ended with exit code: 0

3. 实现两个有序数组合并为一个有序数组

// 合并两个有序数组
Array mergeSortArray(const Array *a, const Array *b)
{
    Array p;
    // 申请内存空间
    p.array = (int *)malloc(sizeof(int) * (a->used + b->used));
    p.size = a->used + b->used;
    p.used = a->used + b->used;
    
    // 长短数组同时遍历，如果短数组遍历完了，剩下的就是长数组里面的数据，直接加上去就行，前面的数据都已经排好序了
    int i = 0, j = 0, k = 0;
    while (i < a->used && j < b->used) {
        if (a->array[i] <= b->array[j]) {
            p.array[k++] = a->array[i++];
        } else {
            p.array[k++] = b->array[j++];
        }
    }
    
    while (i < a->used) {
        p.array[k++] = a->array[i++];
    }
    
    while (j < b->used) {
        p.array[k++] = b->array[j++];
    }
    
    return p;
}

//测试 --------------------------------------------------------
Array a = arrayCreat(10);
Array b = arrayCreat(10);
    
printf("-----a数组插入数据\n");
arrayAdd(&a, 20);
arrayAdd(&a, 93);
arrayAdd(&a, 3);
arrayAdd(&a, 43);
arrayAdd(&a, 65);
    
for (int i = 0; i < a.used; i++) {
    printf("a[%d] = %d\n", i, a.array[i]);
}
    
printf("-----b数组插入数据\n");
arrayAdd(&b, 100);
arrayAdd(&b, 125);
arrayAdd(&b, 34);
arrayAdd(&b, 2);
arrayAdd(&b, 11);
arrayAdd(&b, 19);
arrayAdd(&b, 78);
arrayAdd(&b, 89);
    
for (int i = 0; i < b.used; i++) {
    printf("b[%d] = %d\n", i, b.array[i]);
}
    
printf("数组合并\n");
Array c = mergeSortArray(&a,  &b);
for (int i = 0; i < c.used; i++) {
    printf("c[%d] = %d\n", i, c.array[i]);
}
    
arrayFree(&a);
arrayFree(&b);

// 打印日志 ----------------------------------------------------
-----a数组插入数据
a[0] = 3
a[1] = 20
a[2] = 43
a[3] = 65
a[4] = 93
-----b数组插入数据
b[0] = 2
b[1] = 11
b[2] = 19
b[3] = 34
b[4] = 78
b[5] = 89
b[6] = 100
b[7] = 125
数组合并
c[0] = 2
c[1] = 3
c[2] = 11
c[3] = 19
c[4] = 20
c[5] = 34
c[6] = 43
c[7] = 65
c[8] = 78
c[9] = 89
c[10] = 93
c[11] = 100
c[12] = 125
Program ended with exit code: 0

---

分享个人技术学习记录和跑步马拉松训练比赛、读书笔记等内容，感兴趣的朋友可以关注我的公众号「青争哥哥」。

image