数组的定义及实现

文章目录

前言
一、定义
二、抽象数据类型定义
三、顺序存储
四、具体实现
总结

前言

T_T此专栏用于记录数据结构及算法的（痛苦）学习历程，便于日后复习（这种事情不要啊）。所用教材为《数据结构 C语言版第2版》严蔚敏。

一、定义

数组：由类型相同的数据元素构成的有序集合。
数据元素：受 n(n>=1) 个线性关系的约束，在 n 个线性关系中的序号i1,i2, …,in称为该元素的下标，可以通过下标访问该数据元素。因为数组中每个元素处于n(n>=1) 个关系中，故称该数组为 n 维数组。
数组是线性表的推广，其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型。例如，一维数组可以看成是一个线性表，二维数组可以看成数据元素是线性表的线性表。

二、抽象数据类型定义

数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
数组的抽象数据类型定义为：

ADT Array{
数据对象： ji=0, ···,bi-1, i=1, 2, …, n,
D = { aj1j2…jn | n(n>0)称为数组的维数，bi是数组第 i 维的长度，
ji是数组元素的第 1 维下标，aj1j2…jn∈ElemSet }
数据关系： R = {Rl,R2, …, Rn}
基本操作：
InitArray (&A, n, bound i, ···, boundn)
操作结果：若维数n和各维长度合法，则构造相应的数组A, 并返回OK。
DestroyArray (&A)
操作结果：销毁数组A。
Value(A,&e, index1, …, indexn)
初始条件：A是 n 维数组，e 为元素变量，随后是n个下标值。
操作结果：若各下标不超界，则e赋值为所指定的 A 的元素值，并返回OK。
Assign(&A,e, index1, …，indexn)
初始条件：A是 n 维数组，e 为元素变量，随后是 n 个下标值。
操作结果：若下标不超界，则将 e 的值赋给所指定的A的元素，并返回OK。
} ADT Array

三、顺序存储

由于数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。因此，采用顺序存储结构表示数组比较合适。
由于存储单元是一维的结构，而数组可能是多维的结构，则用一组连续存储单元存放数组的数据元素就有次序约定问题。一般有以行序优先和以列序优先两种方式。在扩展 Basic 、Pascal 、Java 和 C 语言中，用的都是以行序为主序的存储结构，而在 FORTRAN 语言中，用的是以列序为主序的存储结构。
假设每个数据元素占 L 个存储单元，则二维数组 A[0… m-1, 0 … n-1] (即下标从 0 开始，共有 m 行 n 列）中任一元素 aij 的存储位置可由下式确定：
LOC(i, j) = LOC(0, 0) + (n * i + j ) *L
式中， LOC(i,j)是 aij 的存储位置； LOC(0, 0) 是 a00 的存储位置，即二维数组 A 的起始存储位置，也称为基地址或基址。
由此可知，数组是一种随机存取结构。

四、具体实现

#include <iostream>
using namespace std;#define maxline 5
#define maxcolu 5
#define maxpage 5
#define maxdime 5#define fail 0;
#define ok 1;typedef int status;typedef int Elemtype;typedef struct {Elemtype* Addr;  //数组基地址int dime;    //维数int page;    //页维int line;    //行维int colu;    //列维int length;  //数组长度
}Array;//初始化数组
status InitArray(Array&A, int n,int bound1,int bound2,int bound3)
{if (n<0 || n>maxdime)return fail;A.Addr = NULL;if (n == 1 && bound1 > 0 && bound1 < maxline)A.Addr = new Elemtype[bound3];else if (n == 2 && bound1 > 0 && bound1 < maxline && bound2 > 0 && bound2 < maxcolu)A.Addr = new Elemtype[bound3 * bound2];else if (n == 3 && bound1 > 0 && bound1 < maxline && bound2 > 0 && bound2 < maxcolu && bound3 > 0 && bound3 < maxpage)A.Addr = new Elemtype[bound3 * bound2 * bound1];if (!A.Addr)return fail;A.dime = n; A.page = bound1; A.line = bound2; A.colu = bound3;A.length = bound1 * bound2 * bound3;return ok;
}
//销毁数组
status DestroyArray(Array& A)
{delete[] A.Addr;A.Addr = NULL;A.length = 0;return ok;
}
//注意，无需乘以数据元素长度sizeof(Elemtype),因为A.Addr在new时已经分配好了各个元素的空间位置
//如果乘以数据元素长度sizeof(Elemtype)，会导致堆错误
status Value(const Array A, Elemtype* e, int index1,int index2,int index3)
{if (!A.length)return fail;*e = *(A.Addr + (index1 * A.line * A.colu + index2 * A.colu + index3));return ok;
}
//注意，无需乘以数据元素长度sizeof(Elemtype),因为A.Addr在new时已经分配好了各个元素的空间位置
//如果乘以数据元素长度sizeof(Elemtype)，会导致堆错误
status Assign(const Array A, Elemtype* e, int index1, int index2, int index3)
{if (!A.length)return fail;*(A.Addr + (index1 * A.line * A.colu + index2 * A.colu + index3) ) = *e;return ok;
}Array a;
Elemtype e = 0;
int main()  //测试程序
{InitArray(a, 3, 2, 2, 2);cout << a.length << endl;for (int i = 0; i<a.page; i++)for(int j=0;j<a.line;j++)for (int z = 0; z < a.colu; z++){Assign(a, &e, i, j, z);e++;}for (int i = 0; i < a.page; i++)for (int j = 0; j < a.line; j++)for (int z = 0; z < a.colu; z++){Value(a, &e, i, j, z);cout << e << " ";}cout << a.Addr << endl;cout << a.Addr+1 << endl;return 0;
}