数据结构实战

    返回首页    发表留言
本文作者:李德强
          第一节 数组
 
 

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