C语言多维数组数据结构的实现详解
目录
- 数据结构之多维数组
- 各基本操作函数原型说明
- 各基本操作的具体实现
- 测试分析
- 思考与小结
- 1、 对数组的再认识
- 2、调试过程中遇到的问题及解决方案
- 3、算法的时间复杂度分析
- 总结
数据结构之多维数组
定义结构体
typedef struct { ElemType* base;//数组元素基址(数组基址) int dim;//数组维数 int* bounds;//数组维界基址(存放各位长度信息) int* constants;//数组映象函数常量基址 }Array;
各基本操作函数原型说明
(1)创建数组
//若函数参数合法,则构建数组A Status InitArray(Array* A, int dim, ...);
(2)销毁数组
//销毁数组 Status DestroyArray(Array* A);
(3)数组的定位
//获取元素位置(数组定位) Status LocateArray(Array A, va_list ap, int* offset);
(4)数组元素的赋值
//A为n维数组,e为元素变量,随后是n个下标值 //若下标不超界,则将e的值赋给所指定的A的元素(赋值) Status SetArray(Array* A, ElemType e, ...);
(5)获取数组元素
//A为n维数组,e为元素变量,随后是n个下标值 //若下标不超界,则将e赋值为所指定的A的元素(获取) Status GetValue(ElemType* e, Array A, ...);
各基本操作的具体实现
(1)创建数组函数实现
//创建多维数组 Status InitArray(Array* A, int dim, ...) { if (dim <1 || dim>MAX_ARRAY_DIM) return ERROR;//参数不合法 A->dim = dim; A->bounds = (int*)malloc(sizeof(int) * dim); if (!A->bounds) return OVERFLOW;//分配内存失败 //若各维长度合法,则存入A.bounds,并求出A的元素总数elemtotal int elemtotal = 1; va_list ap; va_start(ap, dim); for (int i = 0; i < dim; ++i) { A->bounds[i] = va_arg(ap, int); if (A->bounds[i] < 0)return UNDERFLOW; elemtotal *= A->bounds[i]; } va_end(ap); //为数组分配内存空间内 A->base = (ElemType*)malloc(sizeof(ElemType) * elemtotal); if (!A->base) return OVERFLOW;//分配内存失败 //求映像函数Ci,并存入A.constants[i-1],i = 1,...,dim; A->constants = (int*)malloc(sizeof(int) * dim); if (!A->constants) return OVERFLOW;//分配内存失败 A->constants[dim - 1] = 1; for (int i = dim - 2; i >= 0; --i) { A->constants[i] = A->bounds[i + 1] * A->constants[i + 1]; } return OK; }
(2)销毁数组函数实现
//销毁数组 Status DestroyArray(Array* A) { if (!A->base) return ERROR; free(A->base); A->base = NULL; if (!A->bounds) return ERROR; free(A->bounds); A->bounds = NULL; if (!A->constants) return ERROR; free(A->constants); A->constants = NULL; return OK; }
(3)数组定位函数实现
//数组的定位 Status LocateArray(Array A, va_list ap, int* offset) { int i, instand; //若ap指示的元素下标合理,则求出元素相对位置,返回到offset *offset = 0; for (i = 0; i < A.dim; i++) { instand = va_arg(ap, int); if (instand < 0 || instand > A.bounds[i]) { // printf("instand = %d,定位失败\n",instand);//调试代码 return ERROR; } *offset += A.constants[i] * instand; } return OK; }
(4)数组元素赋值函数实现
//数组赋值 Status SetArray(Array *A, ElemType e, ...) { va_list ap; int offset; va_start(ap, e); if (LocateArray(*A, ap, &offset) == ERROR) return ERROR; va_end(ap); *(A->base + offset) = e; return OK; }
(5)取出数组元素函数实现
//获取数组元素的值,并用E返回 Status GetValue(ElemType* e, Array A, ...) { va_list ap; int offset; va_start(ap, A); if (LocateArray(A, ap, &offset) == ERROR) return ERROR; va_end(ap); *e = *(A.base + offset); return OK; }
测试分析
创建
创建一个二维数组,其第一维长度为4,第二维长度为3。
测试代码:
运行结果:
销毁
将结构体A的地址传入到DestroyArray函数中,执行操作。
测试代码:
运行结果:
数组元素赋值
定义二维数组B[4][3],通过SetArray函数将其值赋给数组A,通过遍历输出A中元素的值,则可以判断出赋值是否准确。
测试代码:
运行结果:
取出数组元素
测试代码:
运行结果:
思考与小结
1、 对数组的再认识
存储器的结构是一维线性的结构,数组是多维的结构。如果要将一个多维的结构放在一个一维的存储单元里,就必须先将多维的数组转换成一个一维的线性序列,才能将其放在存储器当中。数组的存储方式主要有两种:一张是以行序为主的存储方式,另外一种是以列序为主的存储方式。
2、调试过程中遇到的问题及解决方案
1、两次编译报错
①错误信息:va_start argument must not have reference type and must not be parenthesized;
va_start函数的运用问题,函数原型:void va_start(va_list ap,parmN);报错原因为参数不正确。查看c语言开发手册,得出原因。
ap 一个va_list类型的实例
Prmhn 第一个变量参数前的命名参数
②错误信息:*LNK2019 无法解析的外部符号 "int __cdecl SetArray(struct Array ,int,int,…)" (?SetArray@@YAHPAUArray@@HHZZ),函数 _main 中引用了该符号
此错误信息为,找的到定义却又未找到实现的函数,故需将函数实现后才能调用,同时注意参数的对应,避免出现以上问题。
2、运行时报错
运行时报错,数据访问出现问题。通过检查报错信息的前后语句,发现在访问数组的时候忘记i+1,导致i走到-1形成错误原因。
3、运行结果出错
运行结果出现了地址与数值都输出的情况,通过调试,发现第一次进入LocateArray函数之后,函数返回了ERROR,通过打印语句检查,函数确实进入了判断语句内,返回ERROR;
表明参数不准确或者函数判断语句不正确,由于数值为自己控制的,故参数不准确的可能性较小,仔细分析了参数临界以及函数逻辑,将判断参数的条件改成正确判断语句。得到正确的结果。
3、算法的时间复杂度分析
InitArray函数的时间复杂度为O(n);
DestroyArray函数的时间复杂度为O(1);
LocateArray函数的时间复杂度为O(n);
SetArray函数的时间复杂度为O(n);
GetArray函数的时间复杂度为O(n);
SetArray函数和GetArray函数的时间复杂度主要受LocateArray函数影响。
总结
到此这篇关于C语言多维数组数据结构实现的文章就介绍到这了,更多相关C语言多维数组数据结构内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!