数据结构实战
本文作者：李德强
第一节 数组
数组实际上可以看作是线性表的一种特殊情况。一般来说，我们定义了数组的维度和大小之后，通常不对这些属性再做修改，也就是说不对数组的大小做修改，也不去对其中的数组元素做排序，而只对其做值的设定与获取。多维数组在内存中存放的方式其实也是线性的。例如，有一个这样的3维数组array[9][4][3]，它在我们的主观想象中是这样的：
{ 0, 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}
其实这个3维数组在内存中也是线性的，如下：
{0, 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}
下面我们就来实现这样一个支持多维的数组：
//最大维度
#define MAX_DIM (8)
typedef struct
{
//数组基地址
void *addr_base;
//每个维度的大小
int *addr_bounds;
//每个维度具有最大元素数
int *addr_counts;
//维度
int dim;
//元素大小
int ele_size;
//元素个数
int ele_count;
//用于释放节点数据的回调函数
void (*free_data)();
//用于访问节点数据内容的回调函数
void (*visit_data)();
} array;
接下来实现数组的功能函数：
//初始化数组
bool array_init(array *arr, void (*free_data)(), void (*visit_data)(), int dim, int ele_size, ...)
{
if (arr == null)
{
return false;
}
if (dim > MAX_DIM)
{
return false;
}
//维度
arr->dim = dim;
//元素大小
arr->ele_size = ele_size;
//释放元素的回调函数
arr->free_data = free_data;
//访问元素的回调函数
arr->visit_data = visit_data;
//按维度申请每个维度最大值
arr->addr_bounds = malloc(sizeof(int) * dim);
if (arr->addr_bounds == null)
{
return false;
}
//按维度申请每个维度最大值
arr->addr_counts = malloc(sizeof(int) * dim);
if (arr->addr_counts == null)
{
return false;
}
//动态参数
va_list ap;
va_start(ap, ele_size);
//计算总元素数量
arr->ele_count = 1;
for (int i = 0; i < dim; ++i)
{
//接收参数，每个维度数
arr->addr_bounds[i] = va_arg(ap, int);
//计算元素总数
arr->ele_count *= arr->addr_bounds[i];
}
va_end(ap);
//计算每个维度所有的元素数量
for (int i = dim - 1; i >= 0; --i)
{
if (i == dim - 1)
{
arr->addr_counts[i] = arr->addr_bounds[i];
}
else
{
arr->addr_counts[i] = arr->addr_counts[i + 1] * arr->addr_bounds[i];
}
}
//申请元素内存基地址
arr->addr_base = malloc(ele_size * arr->ele_count);
if (arr->addr_base == null)
{
free(arr->addr_bounds);
free(arr->addr_counts);
return false;
}
return true;
}
//销毁数组
bool array_destroy(array *arr)
{
if (arr == null)
{
return true;
}
//释放元素
if (arr->free_data != null)
{
for (int i = 0; i < arr->ele_count; ++i)
{
//通过回调函数释放元素所在内存
void *p_del = arr->addr_base + arr->ele_size * i;
arr->free_data(p_del);
}
}
if (arr->addr_bounds != null)
{
free(arr->addr_bounds);
}
if (arr->addr_counts != null)
{
free(arr->addr_counts);
}
if (arr->addr_base != null)
{
free(arr->addr_base);
}
return true;
}
//为数组中指定索引的元素赋值
bool array_setValue(array *arr, void *element, ...)
{
if (arr == null)
{
return false;
}
int index = 0;
va_list ap;
va_start(ap, element);
//根据每个维度的索引号计算元素在内存中的线性索引
for (int i = 0; i < arr->dim; ++i)
{
int k = va_arg(ap, int);
//维度索引不能超过此维度的最大值
if (0 <= k && k < arr->addr_bounds[i])
{
if (i < arr->dim - 1)
{
index += k * arr->addr_counts[i + 1];
}
else
{
index += k;
}
}
//维度索引超过此维度的最大值，失败
else
{
va_end(ap);
return false;
}
}
va_end(ap);
//设置元素内容
memcpy(arr->addr_base + arr->ele_size * index, element, arr->ele_size);
return true;
}
//取得数组中指定索引的元素值
bool array_getValue(array *arr, void *element, ...)
{
if (arr == null)
{
return false;
}
int index = 0;
va_list ap;
va_start(ap, element);
//根据每个维度的索引号计算元素在内存中的线性索引
for (int i = 0; i < arr->dim; ++i)
{
int k = va_arg(ap, int);
//维度索引不能超过此维度的最大值
if (0 <= k && k < arr->addr_bounds[i])
{
if (i < arr->dim - 1)
{
index += k * arr->addr_counts[i + 1];
}
else
{
index += k;
}
}
//维度索引超过此维度的最大值，失败
else
{
va_end(ap);
return false;
}
}
va_end(ap);
//取得元素内容
memcpy(element, arr->addr_base + arr->ele_size * index, arr->ele_size);
return true;
}
//遍历数组访问所有元素
bool array_visit(array *arr)
{
if (arr == null)
{
return false;
}
if (arr->visit_data == null)
{
return false;
}
//根据元素总个数遍历
for (int i = 0; i < arr->ele_count; ++i)
{
//显示元素内容
void *p_del = arr->addr_base + arr->ele_size * i;
arr->visit_data(p_del);
}
return true;
}
在main函数中首先定义一个学生的数据结构和几个用于array数组回调的函数：
//学生数据结构
typedef struct
{
int no;
char *name;
int age;
} student;
//访问int类型
void visit_int(int *p)
{
printf("%d, ", *p);
}
//访问double类型
void visit_double(double *p)
{
printf("%f, ", *p);
}
//访问student类型
void visit_student(student *p)
{
if (p == null)
{
return;
}
if (p->name == null)
{
return;
}
printf("%d\t%s\t%d\t", p->no, p->name, p->age);
}
//释放student类型的函数
void free_student(student *p)
{
if (p == null)
{
return;
}
if (p->name == null)
{
return;
}
free(p->name);
}
接下来编写main函数，使用数组来存取int类型、double类型和结构体类型的数组：
int main(int argc, char **args)
{
//整型数组
array arr_int;
array_init(&arr_int, null, visit_int, DIM, sizeof(int), M, N, O);
int e = 0;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
for (int k = 0; k < O; ++k)
{
array_setValue(&arr_int, &e, i, j, k);
e++;
}
}
}
int v;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
printf("{");
for (int k = 0; k < O; ++k)
{
array_getValue(&arr_int, &v, i, j, k);
if (k < O - 1)
{
printf(" %3d,", v);
}
else
{
printf(" %3d", v);
}
}
if (j < N - 1)
{
printf("}, ");
}
else
{
printf("} ");
}
}
printf("\n");
}
printf("\n");
array_visit(&arr_int);
array_destroy(&arr_int);
printf("\n");
printf("\n");
//浮点型数组
array arr_double;
array_init(&arr_double, null, visit_double, DIM, sizeof(double), M, N, O);
double ed = 0;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
for (int k = 0; k < O; ++k)
{
array_setValue(&arr_double, &ed, i, j, k);
ed += 0.09;
}
}
}
double vd;
for (int i = 0; i < M; ++i)
{
for (int j = 0; j < N; ++j)
{
printf("{");
for (int k = 0; k < O; ++k)
{
array_getValue(&arr_double, &vd, i, j, k);
if (k < O - 1)
{
printf(" %6.2f,", vd);
}
else
{
printf(" %6.2f", vd);
}
}
if (j < N - 1)
{
printf("}, ");
}
else
{
printf("} ");
}
}
printf("\n");
}
printf("\n");
array_visit(&arr_double);
printf("\n");
array_destroy(&arr_double);
printf("\n");
//结构体型数组
array arr_student;
array_init(&arr_student, free_student, visit_student, DIM, sizeof(student), 2, 2, 2);
int name_max_len = 20;
student stu0;
stu0.no = 15051201;
stu0.name = (char *) malloc(name_max_len);
memcpy(stu0.name, "lidq", name_max_len);
stu0.age = 23;
array_setValue(&arr_student, &stu0, 0, 0, 0);
student stu1;
stu1.no = 15051202;
stu1.name = (char *) malloc(name_max_len);
memcpy(stu1.name, "baihq", name_max_len);
stu1.age = 24;
array_setValue(&arr_student, &stu1, 0, 0, 1);
student stu2;
stu2.no = 15051203;
stu2.name = (char *) malloc(name_max_len);
memcpy(stu2.name, "yangx", name_max_len);
stu2.age = 25;
array_setValue(&arr_student, &stu2, 0, 1, 0);
student stu3;
stu3.no = 15051204;
stu3.name = (char *) malloc(name_max_len);
memcpy(stu3.name, "yany", name_max_len);
stu3.age = 23;
array_setValue(&arr_student, &stu3, 0, 1, 1);
student stu4;
stu4.no = 15051205;
stu4.name = (char *) malloc(name_max_len);
memcpy(stu4.name, "shanc", name_max_len);
stu4.age = 22;
array_setValue(&arr_student, &stu4, 1, 0, 0);
student stu5;
stu5.no = 15051206;
stu5.name = (char *) malloc(name_max_len);
memcpy(stu5.name, "wangh", name_max_len);
stu5.age = 21;
array_setValue(&arr_student, &stu5, 1, 0, 1);
student stu6;
stu6.no = 15051207;
stu6.name = (char *) malloc(name_max_len);
memcpy(stu6.name, "caoj", name_max_len);
stu6.age = 26;
array_setValue(&arr_student, &stu6, 1, 1, 0);
student stu7;
stu7.no = 15051208;
stu7.name = (char *) malloc(name_max_len);
memcpy(stu7.name, "baiy", name_max_len);
stu7.age = 23;
array_setValue(&arr_student, &stu7, 1, 1, 1);
student stu;
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
printf("{");
for (int k = 0; k < 2; ++k)
{
array_getValue(&arr_student, &stu, i, j, k);
visit_student(&stu);
printf(", ");
}
printf("}, ");
}
printf("\n");
}
printf("\n");
array_visit(&arr_student);
printf("\n");
array_destroy(&arr_student);
return 0;
}
运行结果：
{ 0, 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}
0, 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,
{ 0.00, 0.09, 0.18}, { 0.27, 0.36, 0.45}, { 0.54, 0.63, 0.72}, { 0.81, 0.90, 0.99}
{ 1.08, 1.17, 1.26}, { 1.35, 1.44, 1.53}, { 1.62, 1.71, 1.80}, { 1.89, 1.98, 2.07}
{ 2.16, 2.25, 2.34}, { 2.43, 2.52, 2.61}, { 2.70, 2.79, 2.88}, { 2.97, 3.06, 3.15}
{ 3.24, 3.33, 3.42}, { 3.51, 3.60, 3.69}, { 3.78, 3.87, 3.96}, { 4.05, 4.14, 4.23}
{ 4.32, 4.41, 4.50}, { 4.59, 4.68, 4.77}, { 4.86, 4.95, 5.04}, { 5.13, 5.22, 5.31}
{ 5.40, 5.49, 5.58}, { 5.67, 5.76, 5.85}, { 5.94, 6.03, 6.12}, { 6.21, 6.30, 6.39}
{ 6.48, 6.57, 6.66}, { 6.75, 6.84, 6.93}, { 7.02, 7.11, 7.20}, { 7.29, 7.38, 7.47}
{ 7.56, 7.65, 7.74}, { 7.83, 7.92, 8.01}, { 8.10, 8.19, 8.28}, { 8.37, 8.46, 8.55}
{ 8.64, 8.73, 8.82}, { 8.91, 9.00, 9.09}, { 9.18, 9.27, 9.36}, { 9.45, 9.54, 9.63}
0.000000, 0.090000, 0.180000, 0.270000, 0.360000, 0.450000, 0.540000, 0.630000, 0.720000, 0.810000, 0.900000, 0.990000, 1.080000, 1.170000, 1.260000, 1.350000, 1.440000, 1.530000, 1.620000, 1.710000, 1.800000, 1.890000, 1.980000, 2.070000, 2.160000, 2.250000, 2.340000, 2.430000, 2.520000, 2.610000, 2.700000, 2.790000, 2.880000, 2.970000, 3.060000, 3.150000, 3.240000, 3.330000, 3.420000, 3.510000, 3.600000, 3.690000, 3.780000, 3.870000, 3.960000, 4.050000, 4.140000, 4.230000, 4.320000, 4.410000, 4.500000, 4.590000, 4.680000, 4.770000, 4.860000, 4.950000, 5.040000, 5.130000, 5.220000, 5.310000, 5.400000, 5.490000, 5.580000, 5.670000, 5.760000, 5.850000, 5.940000, 6.030000, 6.120000, 6.210000, 6.300000, 6.390000, 6.480000, 6.570000, 6.660000, 6.750000, 6.840000, 6.930000, 7.020000, 7.110000, 7.200000, 7.290000, 7.380000, 7.470000, 7.560000, 7.650000, 7.740000, 7.830000, 7.920000, 8.010000, 8.100000, 8.190000, 8.280000, 8.370000, 8.460000, 8.550000, 8.640000, 8.730000, 8.820000, 8.910000, 9.000000, 9.090000, 9.180000, 9.270000, 9.360000, 9.450000, 9.540000, 9.630000,
{15051201 lidq 23 , 15051202 baihq 24 , }, {15051203 yangx 25 , 15051204 yany 23 , },
{15051205 shanc 22 , 15051206 wangh 21 , }, {15051207 caoj 26 , 15051208 baiy 23 , },
15051201 lidq 23 15051202 baihq 24 15051203 yangx 25 15051204 yany 23 15051205 shanc 22 15051206 wangh 21 15051207 caoj 26 15051208 baiy 23
体例代码：
code path chapter.04/e.g.4.1/ https https://github.com/magicworldos/datastructure.git git git@github.com:magicworldos/datastructure.git subverion https://github.com/magicworldos/datastructure
Copyright © 2015-2023 问渠网 辽ICP备15013245号