数据结构笔记(五): 多维数组的实现

发布于 / 程序猿 / 2 条评论

利用线性表(动态数组)实现多维数组,其实本质上就是操作一维数组,找到相应位置进行修改查询操作。若文中存在错误,敬请指出,感谢阅读。

个人感觉多维数组还是比较好理解的,画个图就很清楚了。

(没想到使用latex公式来显示数组下标会出问题?)

基础知识

一维数组(向量)是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。同一数组的不同元素通过不同的下标标识。(a1, a2, ,,, a3)。

二维数组Amn可视为由m个行向量组成的向量,或由n个列向量组成的向量。

二维数组中的每个元素Aij既属于第i行的行向量,又属于第j列的列向量。三维数组可视为以二维数组为数据元素的向量。

四维数组可视为以三维数组为数据元素的向量。三维数组中的每个元素属于三个向量。四维数组中的每个元素都属于四个向量。

由于计算机内存是一维的,多维数组的元素应排成线性序列后存人存储器。

数组一般不做插入和删除操作,即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。


代码

  • 实现1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct Array_Tag
{
    int *base; // 存储数据
    int dim; // 数组维数
    int *bounds; // 每维长度
    int *constants; // 每维元素数量
};

typedef struct Array_Tag *Array; // Array为指向Array_Tag的指针


int _offsetArray(Array const _array, int a[]) // 找到实际对应位置
{
    int tmp, ret = 0;
    for (int i = 0; i < _array->dim; ++i)
    {
        tmp = a[i];
        if (tmp < 0 || tmp >= _array->bounds[i]) // 查找位置越界返回-1
            return -1;
        ret += _array->bounds[i]*tmp;
    }
    return ret;
}

Array createArray(int dim, int a[]) // 创建多维数组
{
    if (dim <= 0) // 维数小于0返回空值
        return NULL;

    Array ret = NULL;
    ret = (Array)malloc(sizeof(Array_Tag)); // 分配内存
    if (!ret)
        return NULL;

    ret->dim = dim; // 保存维数
    ret->bounds = NULL;
    ret->bounds = (int *)malloc(sizeof(int)*dim); // 分配内存
    if (!ret->bounds)
    {
        free(ret);
        return NULL;
    }

    // 获取各维长度
    int total = 1; // 计算总元素个数
    for (int i = 0; i < dim; ++i) // 保存各维长度
    {
        ret->bounds[i] = a[i];
        total *= ret->bounds[i];
    }

    // 分配真正存储数据的地方
    ret->base = NULL;
    ret->base = (int *)malloc(total*sizeof(int)); // 分配内存
    if (!ret->base)
    {
        free(ret->bounds);
        free(ret);
        return NULL;
    }

    // 清零
    memset(ret->base, 0, total*sizeof(int)); // 将数组内所有元素的值初始化为0

    //计算每一维元素数量
    ret->constants = NULL;
    ret->constants = (int *)malloc(dim*sizeof(int)); // 分配内存
    if (!ret->constants)
    {
        free(ret->bounds);
        free(ret->base);
        free(ret);
        return NULL;
    }

    ret->constants[dim-1] = 1; // 保存每一维元素个数
    for (int i = dim - 2; i >= 0; --i)
        ret->constants[i] = ret->bounds[i+1] * ret->constants[i+1];

    return ret;
}

int atArray(Array const _array, int *pResult, int a[]) // 查询
{
    int offset = _offsetArray(_array, a); // 找到相应位置
    if (offset < 0)
        return -1;
    *pResult = *(_array->base + offset); // 保存查询结果
    return 0;
}

int modifyArray(Array _array, int newValue, int a[]) // 修改
{
    int offset = _offsetArray(_array, a); // 找到相应位置
    if (offset < 0)
        return -1;

    *(_array->base + offset) = newValue; // 修改操作
    return 0;
}

int destroyArray(Array *pt) // 销毁数组,回收内存
{
    free((*pt)->base);
    free((*pt)->bounds);
    free((*pt)->constants);
    free(*pt);
    pt = NULL;
    return 0;
}


int main()
{
    int d, n, a[100], b[100];
    cin >> d;
    for (int i = 0; i < d; ++i)
        cin >> a[i];
    Array A = createArray(d, a); // 创建一个维数为d的数组
    int idx, x;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> idx;
        if (idx == 1) // 1表示查询
        {
            int ans = 0;
            for (int i = 0; i < d; ++i)
                cin >> b[i];
            atArray(A, &ans, b);
            cout << ans << endl;
        }
        else if (idx == 2) // 2表示修改
        {
            cin >> x;
            for (int i = 0; i < d; ++i)
                cin >> b[i];
            modifyArray(A, x, b);
        }
    }
    destroyArray(&A);
    return 0;
}
  • 实现2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

struct Array
{
    int *base;
    int dim;
    int *bounds;
    int *constants;
};

int createArray(Array &_array, int dim, int a[]) // 创建数组
{
    if (dim <= 0)
        return -1;

    _array.dim = dim;

    _array.bounds = new int [dim];
    if (!_array.bounds)
        return -1;
    int total = 1;
    for (int i = 0; i < dim; ++i) // 每维长度
    {
        _array.bounds[i] = a[i];
        total *= _array.bounds[i];
    }

    _array.base = new int [total]; // 实际元素存储位置
    if (!_array.base)
    {
        delete [] _array.bounds;
        return -1;
    }

    memset(_array.base, 0, total*sizeof(int)); // 将数组内所有元素初始化为0

    _array.constants = new int [dim];
    if (!_array.constants)
    {
        delete [] _array.bounds;
        delete [] _array.base;
        return -1;
    }
    _array.constants[dim-1] = 1; // 每维元素个数
    for (int i = dim - 2; i >= 0; --i)
        _array.constants[i] = _array.bounds[i+1] * _array.constants[i+1];

    return 0;
}

int atArray(Array const _array, int *pResult, int a[]) // 查询
{
    int pos = 0;
    for (int i = 0; i < _array.dim; ++i) // 找到位置
        pos += _array.constants[i] * a[i];

    *pResult = _array.base[pos];
    return 0;
}

int modifyArray(Array _array, int x, int a[]) // 修改
{
    int pos = 0;
    for (int i = 0; i < _array.dim; ++i) // 找到位置
        pos += _array.constants[i] * a[i];

    _array.base[pos] = x;
    return 0;
}

int destroyArray(Array _array) // 销毁
{
    delete [] _array.base;
    delete [] _array.bounds;
    delete [] _array.constants;

    return 0;
}

int main()
{
    int d, n, a[100], b[100];
    cin >> d;
    for (int i = 0; i < d; ++i)
        cin >> a[i];
    Array A;
    createArray(A, d, a);
    cout << A.dim << endl;
    int idx, x;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> idx;
        if (idx == 1) // 1表示查询
        {
            int ans = 0;
            for (int i = 0; i < d; ++i)
                cin >> b[i];
            atArray(A, &ans, b);
            cout << ans << endl;
        }
        else if (idx == 2) // 2表示修改
        {
            cin >> x;
            for (int i = 0; i < d; ++i)
                cin >> b[i];
            modifyArray(A, x, b);
        }
    }
    destroyArray(A);
    return 0;
}

两种都是一样的,第二种显得稍微简单一些。

本文基础知识部分来自于:多维数组的定义和存储

最后,致敬迅哥


The end.
2017-11-03 星期五

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(五): 多维数组的实现
  1. 闵玧其

    doge代码实现1的第三排注释“数组为数”哈哈哈应该是“数组维数”miao1哈哈哈

    1. TaiFu_S
      @闵玧其

      赞一个 谢谢提醒!