数组实际上可以看作是线性表的一种特殊情况。一般来说,我们定义了数组的维度和大小之后,通常不对这些属性再做修改,也就是说不对数组的大小做修改,也不去对其中的数组元素做排序,而只对其做值的设定与获取。多维数组在内存中存放的方式其实也是线性的。例如,有一个这样的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号