数据结构算法C语言实现（十七）--- 5.1&5.2数组：定义、顺序表示及实现
一.简述
理解数组位置的计算公式
LOC(j1, j2, ···, jn) = LOC(0, 0, ..., 0) + (b2x ··· x bnx j1 + b3x ··· x bnx j2 + ··· + bnx jn-1 + jn)L
化简为
可以缩写成
其中 cn = L,ci-1 = bi x ci, 1<i≤n。
二.头文件
1 //5_2.h
2 /**
3 author:zhaoyu
4 date:2016-6-15
5 */
6 //----数组的顺序存储表示----
7 #include "head.h"
8 #include <stdarg.h>//表准头文件，提供宏va_start,va_arg和va_end
9 #define MAX_ARRAY_DIM 8//用于存取变长参数表
10 #define ElemType int
11 typedef struct {
12 ElemType *base;//数组元素基址，由InitArray分配
13 int dim;//数组维数
14 int *bounds;//数组维界基址，有InitArray分配
15 int *constants;//数组映像函数常量基址，由InitArray分配
16 }Array;
17 void test(int x1, ...)
18 {//测试 stdarg
19 va_list ap;
20 va_start(ap, x1);
21 for (int i = 0; i < x1; i++)
22 {
23 printf("%d\t", va_arg(ap, int));
24 }
25 printf("\n");
26 }
27
28 //----基本操作的算法描述----
29 Status InitArray(Array &A, int dim, ...)
30 {//若位数 dim 和各维度长度合法，则构造相应的数组A，并返回 OK
31 if (dim < 1 || dim > MAX_ARRAY_DIM)
32 {
33 return ERROR;
34 }
35 A.dim = dim;
36 A.bounds = (int *)malloc(dim * sizeof(int));
37 if (!A.bounds)
38 {
39 exit(OVERFLOW);
40 }
41 //各维度长度合法，则存入A.bounds,并求出A的元素总数elemtotal
42 int elemtotal = 1;
43 va_list ap;
44 va_start(ap, dim);//ap 为 va_list 类型，是存放变长参数表信息的数组
45 for (int i = 0; i < dim; i++)
46 {
47 A.bounds[i] = va_arg(ap, int);
48 if (A.bounds[i] < 0)
49 {
50 return ERROR;
51 }
52 elemtotal *= A.bounds[i];
53 }
54 va_end(ap);
55 A.base = (ElemType *)malloc(elemtotal * sizeof(ElemType));
56 if (!A.base)
57 {
58 exit(OVERFLOW);
59 }
60 //求映像函数的常数 Ci,存入 A.constant[i-1], i = 1,...,dim
61 A.constants = (int *)malloc(dim * sizeof(int));
62 A.constants[dim-1] = 1;//L=1
63 for (int i = dim-2; i >= 0; --i)
64 {
65 A.constants[i] = A.bounds[i+1] * A.constants[i+1];
66 }
67 return OK;
68 }
69 Status DestroyArray(Array &A)
70 {//销毁数组 A
71 if (!A.base)
72 {
73 return ERROR;
74 }
75 free(A.base);
76 A.base = NULL;
77 if (!A.bounds)
78 {
79 return ERROR;
80 }
81 free(A.bounds);
82 A.bounds = NULL;
83 if (!A.constants)
84 {
85 return ERROR;
86 }
87 free(A.constants);
88 A.constants = NULL;
89 return OK;
90 }
91 Status Locate(Array A, va_list ap, int &off)
92 {//若 ap 指示的各下标之合法， 则求出该元素在 A 的相对地址 off
93 off = 0;
94 for (int i = 0; i < A.dim; ++i)
95 {
96 int index = va_arg(ap, int);
97 if (index < 0 || index > A.bounds[i])
98 {
99 return OVERFLOW;
100 }
101 off += A.constants[i]*index;
102 }
103 return OK;
104 }
105 Status Value(Array A, ElemType &e, ...)
106 {// A 是 n 维数组，e 为元素变量，随后是 n 个下标值
107 //若各下标不越界，则 e 赋值为所指定的 A 的元素值， 并返回 OK
108 va_list ap;
109 va_start(ap, e);
110 int result = 0, off;
111 if ((result = Locate(A, ap, off))<=0)
112 {
113 return result;
114 }
115 e = *(A.base + off);
116 return OK;
117 }
118 Status Assign(Array &A, ElemType e, ...)
119 {// A 是 n 维数组，e 为元素变量，随后是 n 个下标值
120 //若各下标不越界，则 e 赋给所指定的 A 的元素， 并返回 OK
121 va_list ap;
122 va_start(ap, e);
123 int result, off;
124 if ((result = Locate(A, ap, off)) <= 0)
125 {
126 return result;
127 }
128 *(A.base + off) = e;
129 return OK;
130 }
5_2.h
三.CPP文件
1 //5_2.cpp
2 /**
3 author:zhaoyu
4 date:2016-6-15
5 */
6 #include "5_2.h"
7 int main(int argc, char const *argv[])
8 {
9 test(3, 1, 2, 3);
10 Array A;
11 InitArray(A, 3, 4, 2, 2);
12 for (int i = 0; i < 4; ++i)
13 {
14 for (int j = 0; j < 2; ++j)
15 {
16 for (int k = 0; k < 2; ++k)
17 {
18 Assign(A, 100*i+j*10+k, i, j, k);
19 }
20 }
21 }
22 for (int i = 0; i < 4; ++i)
23 {
24 printf("\n");
25 for (int j = 0; j < 2; ++j)
26 {
27 for (int k = 0; k < 2; ++k)
28 {
29 int e;
30 Value(A, e, i, j, k);
31 printf("%d-%d-%d\t%d\n", i, j, k, e);
32 }
33 }
34 }
35 return 0;
36 }
5_2.cpp
四.测试
