前言
这一篇笔记主要记录总结了线性表
数据结构中的数组
概念以及相关的算法
。
名词解释
1. 线性表(Linear List)
线性表
是数据排成像一条线一样的结构
,每个线性表上的数据最多有向前和向后两个方向。除了数组
外,链表、队列、栈
也是线性表
数据结构。
2. 非线性表
和线性表相对立,数据之间不是简单的前后关系
,这样的结构称为非线性表
,如图、树、堆
等数据结构。
数组
数组是一种线性表
数据结构,是用一组连续的内存空间
,来存储一组具有相同数据类型
的数据。几乎在所有的编程语言都存在数组这中最基本的数据结构类型。在 Objective-C 语言中是 NSArray
,当然 Objective-C 是 C 的超集,所以也完全可以使用 C 语言的数组类型。
随机访问
正式因为数组是用一组连续的内存空间
来存储数据的,所以数组支持下标随机访问
,复杂度是 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,然后死循环。
image这里还和使用的编译器
内存分配以及字节对齐
有关系,有些编译器会默认开启堆栈保护
,当如果变量访问一块不属于自己的内存时,会出现编译错误。
为了不让程序出现这种不确定的错误,导致 debug 难度大,还有就是容易被黑客利用攻击,所以写代码时要特别警惕数组越界
。不过很多高级语言的都会默认做越界检查
,如 Objective-C 里面的数组,如果越界访问就会下面这种经典错误。
怎么选择容器还是数组?
容器优点
- 将很多数组插入删除等操作细节封装起来,提供很多易用的API。
-
动态扩容
,如果插入数据的时候发现数组的空间不够,就需要重新申请一块更大的内存空间,并把原来的数据都复制进新的数组,在将新的数据插入。但是如果事先知道数据的大小,可以创建的时候就制定好数据的大小,这样可以避免不必要的动态扩容
操作。
数组优点
- 存储基本数据类型。
- 当数组大小事先已知,并且数据操作比较简单。
总结
日常业务开发,使用高级语言提供的数组容器就行,如 Objective-C 的 NSArray
,损失一点性能,但写起来方便简单。如果是做比较注重性能的底层开发,可以考虑使用数组。
数组的下标为什么从 0 开始?
- 寻址算法,如果下标不从 0 开始,从 1 开始会怎样,寻址算法就变成
a[i]_address = base_address + (i - 1 * data_type_size)
,转成汇编指令,对于 CPU 而言,就多了一条要执行的减法指令
,而这种数组的操作是很频繁很底层的操作,为了优化,所以数组的下标都设计从 0 开始。 - 历史原因,由于 C 语言是后面很多语言设计的参考,为了保持程序员的编码习惯,所以后面的程序语言设计者也保持和 C 语言数组一样的风格。
课后思考题
-
前面我基于数组的原理引出 JVM 的标记清除垃圾回收算法的核心理念,我不知道你是否使用 Java 语言,理解 JVM,如果你熟悉回顾下你理解的标记清除垃圾回收算法。
- 解答: 不熟悉 Java 语言。
-
前面我们讲到一维数组的内存寻址公式,那你可以思考一下,类比一二维数组的寻址公式是怎样?
-
解答: m * n 数组,
a[i][j]_address = base_address + (i * n + j data_type_size)
,其中 i < m,j < n。内存布局如下:
-
解答: m * n 数组,
数组相关编程题目
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
网友评论