几乎所有的语言都把数组作为一种固有的数据类型,数组也是我们最常用的数据结构之一。在语言底层,数组是如何实现的呢?本文以抽象数据类型的形式,定义、实现数组。
创建数组,理论上,我们可以使用创建任意维度的数组;但这个多维只是我们“感知”上的多维度,实际上,内存是一种线性存储单元,不可能实现真正的多维。换言之,多维数组在内存中也是顺序的排在一维,占用连续的一段存储空间。
以二维数组为例。存储数组时,可以使用行优先存储,即先存第一行…再存第二行……当然也可以使用列优先(Fortran语言就采用了列优先)。大多数语言还是行优先的,下面我就以行优先存储,定义和表示数组。
Def:n维数组的映像函数
一个数组的各个维度的下标与内存中的存储单元有着一一对应,这是必然的。这个对应关系称作映像函数。以三维为例,映像函数是:(这里就不展开一般情况了)
Loc(i,j,k) = Loc(0,0,0) + ((b2b3)i + (b3) * j + i) * L
其中:
Loc(0,0,0): 基地自
bi: 为第i维的长度 ;
L : 地址的加减以元素大小为单位为了方便程序,映像函数显然可以定义如下:
Loc(j1,j2,j3) = Loc(0,0,0) + sum(ci*ji)
其中:
i = 1 to n
cn = L;ci-1 = ci*bi
可见,计算各元素位置的时间相同,存取任意元素时间都是单位O(1)。这叫做“随机存储结构” 。
有了上述定义,就可以实现数组,以及实现数组的基本操作。下面的实现使用了“可变长参数”,后面我可给出了比较详细的参考资料。下面的注释非常清楚了。
1 #include<cstdio>
2 #include<iostream>
3 #include<stdlib.h>
4 #include<stdarg.h> //标准头文件,提供宏va_start,va_arg,va_end。来使用可变长参数
5 #define MAX_DIM 8 //最大维度
6 #define ElemType int //数据类型
7 using namespace std;
8 //数组 表示
9 typedef struct{
10 ElemType *base; //数组的基地址
11 int dim; //维度
12 int *bounds; //维度是可变参数,存各维度的长度
13 int *constants; //这里就是上面说的ci
14 }Array;
15
16 /*
17 基本操作如下
18 */
19 void InitArray(Array &A,int dim,...){
20 /*先判断维度,以及各维度长度是否合法*/
21 if(dim<1||dim >MAX_DIM) return;
22 A.dim = dim;
23 A.bounds = (int*)malloc(dim*sizeof(int)); //bounds存各维度的长度,故开辟空间为dim*dizeof(int)
24 if(!A.bounds) exit(0);
25 int elemtotal = 1; //元素总个数,实际上,总个数为各维度长度的乘积
26 //先传一个数组,用来存可变长参数信息表的数组, dim是长度
27 va_list argp;
28 //等同于 char*argp,va_list就是一个指向第一个可变参数的指针
29 /*argp指向传入的第一个可选参数,第二个参数是可变参数之前的第一个参数名,必须有,因为要靠这个去找可变参数在哪里*/
30 /*这里把上面得到的字符指针argp,后移动4个字节,就是跳过dim的内存地址 */
31 va_start(argp,dim);
32 for(int i = 0;i<dim;i++){
33 A.bounds[i] = va_arg(argp,int);//这里把ap往后跳过4个字节(sizeof(int)大小)指向下一个参数,返回的是当前参数(而非下一个参数)
34 if(A.bounds[i]<0) return;
35 elemtotal *= A.bounds[i];
36 }
37 va_end(argp);
38
39 A.base = (ElemType*)malloc(elemtotal * sizeof(ElemType));
40 if(!A.base) exit(0);
41
42 //下面再求映像函数的参数常数ci,有了这个可以很方便地取每一个元素
43 A.constants = (int*)malloc(dim*sizeof(int));
44 if(!A.constants) exit(0);
45 A.constants[dim-1] = 1;//L = 1,指针得增减以元素的大小为单位
46 for(int i = dim-2;i>=0;i--){
47 A.constants[i] = A.bounds[i+1] * A.constants[i+1];
48 }
49 return;
50 }
51 /*销毁函数*/
52 void Destory(Array &A){
53 if(!A.base){
54 return;
55 }
56 free(A.base);A.base = NULL;
57 if(!A.bounds){
58 return;
59 }
60 free(A.bounds);A.bounds = NULL;
61 if(!A.constants){
62 return;
63 }
64 free(A.constants);A.constants = NULL;
65 return;
66 }
67 /*求指定元素的地址,即off,求的是相对基地址的偏移*/
68 void Locate(Array A,va_list ap,int &off){
69 off = 0;
70 for(int i = 0;i<A.dim;i++){
71 //用va_arg去取元素,然后自动后移int位
72 //va_list ap就是第一个元素的地址
73 int ind = va_arg(ap,int);
74 if(ind<0||ind>=A.bounds[i]) return; //是否合法
75 //求地址的公式!
76 off += ind * A.constants[i];
77 }
78 //return off;
79 }
80
81 void Value(Array A,ElemType &e,...) {
82 //A是n维数组 e 是要去取得元素,...是n个下标
83
84 //创建取不定参数的指针
85 va_list ap;
86 //初始化,通过va_start() 实现
87 va_start(ap,e);
88
89 int off;
90 //off存放元素e地址
91 Locate(A,ap,off);
92 //取元素,返回e
93 if(off <= 0) return; //这其实也判断了下标是否合法
94 //关闭
95 va_end(ap);
96 e = *(A.base+off);
97 }
98 //赋值语句
99 void Assign(Array &A,ElemType e,...){
100 //A是n维数组,e是元素变量,...是下标
101 //即把指定下标的元素赋值成e
102 va_list ap;
103 va_start(ap,e);
104 int off;
105 Locate(A,ap,off);
106 if(off <= 0) return;
107 *(A.base + off) = e;
108 va_end(ap);
109 return;
110 }
111
112 int main(){
113 //测试
114
115 Array A;
116 InitArray(A,3,3,3,3);
117 Assign(A,10,0,0,1);
118 Assign(A,2,1,1,1);
119 int e = 1000;
120 Value(A,e,1,1,1);
121 printf("e1:%d\n",e);
122 int e2 = 99;
123 Value(A,e2,0,0,1);
124 printf("e2:%d\n",e2);
125 printf("成功...");
126 }
上面用到的可变参数以及stdarg头文件的比较好的学习信息:
https://www.cnblogs.com/justinzhang/archive/2011/09/29/2195969.html
总结使用stdarg的步骤:
va_start() va_arg() va_end() va_list 的使用:
<Step 1> 在调用参数表之前,定义一个 va_list 类型的变量,(假设va_list 类型变量被定义为ap);
<Step 2> 然后应该对ap 进行初始化,让它指向可变参数表里面的第一个参数,这是通过 va_start 来实现的,第一个参数是 ap 本身,第二个参数是在变参表前面紧挨着的一个变量,即“...”之前的那个参数;
<Step 3> 然后是获取参数,调用va_arg,它的第一个参数是ap,第二个参数是要获取的参数的指定类型,然后返回这个指定类型的值,并且把 ap 的位置指向变参表的下一个变量位置;
<Step 4> 获取所有的参数之后,我们有必要将这个 ap 指针关掉,以免发生危险,方法是调用 va_end,他是输入的参数 ap 置为 NULL,应该养成获取完参数表之后关闭指针的习惯。说白了,就是让我们的程序具有健壮性。通常va_start和va_end是成对出现。
原文链接: https://www.cnblogs.com/duye/p/8889449.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/272658
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!