《数据结构》-顺序数组的实现和表示

/*
数组的特点：结构固定--定义后，维数和维界不再改变
数组的基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作。
*/
#include <string.h>
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h> // 标准头文件，提供宏va_start，va_arg和va_end，用于存取变长参数表
#include <math.h>
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
// Status 是函数的类型,其值是函数结果状态代码，如 OK 等
typedef int Boolean; // Boolean 是布尔类型,其值是 TRUE 或 FALSE
typedef int ElemType;
// c 数组的顺序存储表示
#define MAX_ARRAY_DIM 8 // 假设数组维数的最大值为 8
typedef struct Array
{
ElemType *base; // 数组元素基址，由 InitArray 分配
int dim;
// 数组维数
int *bounds;
// 数组维界基址，由 InitArray 分配
int *constants; // 数组映象函数常量基址，由 InitArray 分配
} Array;
// 顺序存储数组的基本操作(5个)
/* 构造数组 A */
Status InitArray(Array *A, int dim, ...)
{
// 若维数 dim 和各维长度合法，则构造相应的数组 A，并返回 OK
int elemtotal = 1, i; // elemtotal 是数组元素总数，初值为 1(累乘器)
va_list ap;
if (dim < 1 || dim > MAX_ARRAY_DIM)
return ERROR;
A->dim = dim;
A->bounds = (int *)malloc(dim * sizeof(int));
if (!A->bounds)
exit(-1);
va_start(ap, dim);
for (i = 0; i < dim; ++i)
{
A->bounds[i] = va_arg(ap, int);
if (A->bounds[i] < 0)
return -2; // 在 math.h 中定义为 4
elemtotal *= A->bounds[i];
}
va_end(ap);
A->base = (ElemType *)malloc(elemtotal * sizeof(ElemType));
if (!A->base)
exit(-1);
A->constants = (int *)malloc(dim * sizeof(int));
if (!A->constants)
exit(-1);
A->constants[dim - 1] = 1;
for (i = dim - 2; i >= 0; --i)
A->constants[i] = A->bounds[i + 1] * A->constants[i + 1];
return OK;
}
/* 销毁数组 A */
void DestroyArray(Array *A)
{ // 销毁数组 A
if (A->base)
free(A->base);
if (A->bounds)
free(A->bounds);
if (A->constants)
free(A->constants);
A->base = A->bounds = A->constants = NULL;
A->dim = 0;
}
Status Locate(Array A, va_list ap, int *off) // Value()、Assign() 调用此函数
{
// 若 ap 指示的各下标值合法，则求出该元素在 A 中的相对地址 off
int i, ind;
*off = 0;
for (i = 0; i < A.dim; i++)
{
ind = va_arg(ap, int);
if (ind < 0 || ind >= A.bounds[i])
return -1;
*off += A.constants[i] * ind;
}
return OK;
}
/* 取数组元素值 */
Status Value(ElemType *e, Array A, ...) // 在 VC++ 中，...之前的形参不能是引用类型
{
// ...依次为各维的下标值，若各下标合法，则 e 被赋值为 A 的相应的元素值
va_list ap;
int off;
va_start(ap, A);
if (Locate(A, ap, &off) == -1) // 调用 Locate()
return ERROR;
*e = *(A.base + off);
return OK;
}
/* 给数组元素赋值 */
Status Assign(Array A, ElemType e, ...) // 变量 A 的值不变，故不需要 &
{
// ...依次为各维的下标值，若各下标合法，则将 e 的值赋给 A 的指定的元素
va_list ap;
int off;
va_start(ap, e);
if (Locate(A, ap, &off) == -1) // 调用 Locate()
return ERROR;
*(A.base + off) = e;
return OK;
}
int main(int argc, char *argv[])
{
Array A;
int i, j, k, *p, dim = 3, bound1 = 3, bound2 = 4, bound3 = 2; // A[3][4][2] 数组
ElemType e, *p1;
InitArray(&A, dim, bound1, bound2, bound3); // 构造 3×4×2 的 3 维数组 A
p = A.bounds;
printf("A.bounds=");
for (i = 0; i < dim; i++) // 顺序输出 A.bounds
printf("%d ", *(p + i));
p = A.constants;
printf("nA.constants=");
for (i = 0; i < dim; i++) // 顺序输出 A.constants
printf("%d ", *(p + i));
printf("n%d page %d hang %d lie is:n", bound1, bound2, bound3);
for (i = 0; i < bound1; i++)
{
for (j = 0; j < bound2; j++)
{
for (k = 0; k < bound3; k++)
{
Assign(A, i * 100 + j * 10 + k, i, j, k); // 将 i×100+j×10+k 赋值给 A[i][j][k]
Value(&e, A, i, j, k);
// 将 A[i][j][k] 的值赋给 e
printf("A[%d][%d][%d]=%2d ", i, j, k, e); // 输出 A[i][j][k]
}
printf("n");
}
printf("n");
}
p1 = A.base;
printf("A.base=n");
for (i = 0; i < bound1 * bound2 * bound3; i++) // 顺序输出 A.base
{
printf("%4d", *(p1 + i));
if (i % (bound2 * bound3) == bound2 * bound3 - 1)
printf("n");
}
printf("A.dim=%dn", A.dim);
DestroyArray(&A);
return 1;
}
/*
A.bounds=3 4 2
A.constants=8 2 1
3 page 4 hang 2 lie is:
A[0][0][0]= 0 A[0][0][1]= 1
A[0][1][0]=10 A[0][1][1]=11
A[0][2][0]=20 A[0][2][1]=21
A[0][3][0]=30 A[0][3][1]=31
A[1][0][0]=100 A[1][0][1]=101
A[1][1][0]=110 A[1][1][1]=111
A[1][2][0]=120 A[1][2][1]=121
A[1][3][0]=130 A[1][3][1]=131
A[2][0][0]=200 A[2][0][1]=201
A[2][1][0]=210 A[2][1][1]=211
A[2][2][0]=220 A[2][2][1]=221
A[2][3][0]=230 A[2][3][1]=231
A.base=
0
1
10
11
20
21
30
31
100 101 110 111 120 121 130 131
200 201 210 211 220 221 230 231
A.dim=3
*/
/****************** end of file ******************/

最后

以上就是清爽老虎为你收集整理的《数据结构》-顺序数组的实现和表示的全部内容，希望文章能够帮你解决《数据结构》-顺序数组的实现和表示所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。