文章目录
- 前言
- 一、定义
- 二、抽象数据类型定义
- 三、顺序存储
- 四、具体实现
- 总结
前言
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;
}
&emps; 测试现象:
总结
路漫漫其修远兮,吾将上下而摆烂。(delete你少报点错!_ !)
有任何疑问和补充,欢迎交流。(但我显然不会T_T)