这是我的数据结构课程设计，搬运至博客做一份保存，也把弄清楚的一些知识记录下来。

题目

1. 按照行优先顺序将输入的数据建成4维数组，按照列优先顺序输出结果；
2. 给出任意处的元素值，并给出对应的一维数组中的序号；
3. 用 squeeze 函数来消除数组中的”孤维”，即大小等于1的维，从而起到降维的作用；
4. 用 sub2ind 函数将下标转换为单一索引数值；
5. 用 ind2sub 函数将数组的单一索引数值转换为数组的下标。

相关概念

1.行优先存储与列优先存储

说到存储，计算机的存储方式只有两种，物理结构——顺序存储结构和链式存储结构。而一切数据结构中的类型，如栈、队列、二叉树、图等都是使用这两种存储结构进行实现与表示的，这些结构都是逻辑上的结构，同样的，数组，无论多少维度都是采用这两种物理结构实现的，其在内存之中都只是一堆连续或者不连续的数据。

对于多维数组来说，存储的顺序可以不同，因为其下标不止一个，存储数据的先后次序也就可以不一样。

举个栗子，二维数组。行优先存储，优先存储每一行，依次向后，对应的下标变换为a[0][0]至a[0][1]至a[0][2]…。低下标先开始变化，直至结束。因此，以行序为主序存储方式也称为低下标优先。C语言采用的就是这种方式。

列优先存储，优先存储每一列，依次向后，对应的下标变换为a[0][0]至a[1][0]至a[2][0]…。高下标先开始变化，直至结束。因此，以列序为主序存储方式也称为高下标优先。Matlab采用的就是这种方式。

参考链接

行优先存储和列优先存储

行优先和列优先的原则问题——Matlab

2.C语言多维数组的理解

C语言数组，是一个用于存储固定大小的相同类型元素的集合。

int a[4] = {0,1,2,3};
int b[2][4] = {
                {0,1,2,3},
                {4,5,6,7}
              };

如上所示的一维数组，基本元素是int类型的数据，这个数组可称为int类型数据的数组。而二维数组，基本元素是int类型数据的数组，这个数组可称为一维数组的数组。同理，n维数组的基本元素就是n-1维数组。

声明数组 int c[3][4][5]; 表示数组 c 包含三个元素: c[0],c[1],c[2] ，而这每一个元素又都是二维数组，而每一个二维数组又包含四个元素——一维数组。

参考链接

C语言多维数组，以及多维数组中的二维数组

3.几个名词：维度、维界与孤维（未找到定义，自己的理解）

• 维度：几维数组对应的维度就是几。如 int c[3][4][5]; 是三维数组。

• 维界：对应每一个维度的范围，一般下界为0。如 int c[3][4][5]; ，其第三维维界为0至2。

• 孤维，就是维界只能存储数量为1的维度，如 int c[3][1][5]; ，共能存放15个数据，而int c[3][5]; 也是存放15个数据，故可以消除孤维，来简化多维数组。

数据结构与核心算法

数据结构

采用顺序存储的方式来存储数组：

1. 一旦建立数组，数组存储的数量和结构中的元素之间的关系不需要再发生变化。
2. 不需要插入和删除操作，还需要实现随机存取（时间复杂度为O(1)）。

//参考自《数据结构》清华大学出版社 严蔚敏
typedef struct{
	ElemType * base;	//元素基址,ElemType为此数组要存储的数据类型
	int dim;			//维数
	int elemtotal;		//总数
	int * bounds;		//数组各个维界
	int * constants;	//映像函数常量基址，参看映像函数⬇
}Array;

核心算法——映像函数

映像函数是为了便于计算多维下标对应的内存基址。由于四维数组只是逻辑上的四维数组，其在内存上的真实分配情况也只是顺序存储结构，为了实现四维数组随机存取的特点，就要使用映像函数求得其地址。故上述结构体中 int * constants 的存在就是为了使得计算方便。

例如：int c[3][4][5] 这个三维数组，按照行优先存储，下标(1,2,3)对应的基址如何求得呢？
LOC(1，2，3) = 首元素基址 + 1 * 4 * 5 + 2 * 5 + 5 * 1 。而这里的 int * constants 就是把每一个维度能存储的元素个数存储了下来。对于 int c[3][4][5] 它的第三维包含三个元素 c[0][4][5]、c[1][4][5]、c[2][4][5]，每个元素都能存储 4 * 5 = 20 个元素，第三维下标为1，故1 * 4 *5 = 20 ,其余同理。

故使用 int * constants 来作为映像函数常量基址，每个 A.constands[i] 代表比 dim - i 低一维的所有元素的个数。

A.constants = (int *)malloc(A.dim * sizeof(int));
A.constants[A.dim - 1] = 1;
for (int i = A.dim - 2; i >= 0; --i)
{
	A.constants[i] = A.bounds[i + 1] * A.constants[i + 1];
}

映像函数如下图

计算方法，求四维下标(a,b,c,d)对应的基址：

ind = base + A.constants[0] * a + A.constants[1] * b + A.constants[2] * c + A.constants[3] * d;

参考链接

C语言中什么是数组映像函数常量基址

实现代码

我的代码分文件编程，Array.h 是关于数据结构的定义与声明，Array.cpp 是关于Array.h 内函数的实现，main.cpp 是运用这些函数进行流程控制之后的演示。编译环境是VS2013。

Array.h

#pragma once	//防止头文件重复

#define OK 1
#define ERROR 0
#define OVERFLO -1
#define MAX 8		//维界最大值为8

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

using namespace std;

typedef int ElemType;
typedef int Status;

typedef struct{
	ElemType * base;	//元素基址
	int dim;			//维数
	int elemtotal;		//总数
	int * bounds;		//数组各个维界
	int * constants;	//映像函数常量基址
}Array;

typedef struct{
	int a;
	int b;
	int c;
	int d;
}Sub;//四维数组下标结构体

//1.建立数组
Status InitArray(Array &A, int dim, int *boundary);

//2.按照行优先顺序存储数据
Status ValueArray(Array &A);

//3.行优先顺序输出结果
void PrintArrayByRow(Array &A);

//4.列优先顺序输出结果
void PrintArrayByCol(Array &A);

//5.给定下标求取对应下标的元素
Status GetValue(Array A, Sub sub,ElemType &elem);

//6.给定下标求取对应一维数组的序号（sub2ind）
Status sub2ind(Array A,Sub sub,int &ind);

//7.给定一位数组的单一索引值抓换成数组下标（ind2sub）
Status ind2sub(Array A, int ind, Sub &sub);

//8.消除孤维（squeeze）
Status squeeze(Array A, Array &B);

//9.显示当前数组信息
void ShowDate(Array A);

//10.销毁数组
Status DestroyArray(Array &A);

Array.cpp

#include "Array.h"

//1.建立数组
Status InitArray(Array &A, int dim, int *boundary)//此处的boundary形参为数组，便于在main函数中检验数据是否正常，便于传参。
{
	if (dim<0 || dim>MAX) return ERROR;
	A.dim = dim;
	A.bounds = (int *)malloc(dim*sizeof(int));
	if (!A.bounds) exit(OVERFLO);
	A.elemtotal = 1;
	for (int i = 0; i < dim; ++i)
	{
		A.bounds[i] = boundary[i];
		A.elemtotal *= A.bounds[i];
	}
	A.base = (ElemType *)malloc(A.elemtotal * sizeof(ElemType));
	if (!A.base) exit(OVERFLO);
	A.constants = (int *)malloc(A.dim * sizeof(int));
	if (!A.constants) exit(OVERFLO);
	A.constants[A.dim - 1] = 1;
	for (int i = A.dim - 2; i >= 0; --i)
	{
		A.constants[i] = A.bounds[i + 1] * A.constants[i + 1];
	}
	return OK;
}

//2.按照行优先顺序存储数据
Status ValueArray(Array &A)
{
	cout << "您一共要输入 " << A.elemtotal << " 个数据（int类型）" << endl;
	for (int i = 0; i < A.elemtotal; ++i)
	{
		cin >> A.base[i];
	}
	return OK;
}

//3.行优先顺序输出结果
void PrintArrayByRow(Array &A)
{
	cout << "按照行优先顺序输出结果" << endl;
	for (int i = 0; i < A.elemtotal; ++i)
	{
		cout << A.base[i]<<" ";
	}
	cout << endl;
}

//4.列优先顺序输出结果
void PrintArrayByCol(Array &A)
{
	//本程序采用的是行优先存储方式创建的，对于所谓的列优先输出，因为列优先也就是高下标优先，所以按照高下标的遍历方式，依次将四维下标转换成一维基址(sub2ind函数)，然后输出。
	int ind;
	Sub sub;
	cout << "按照列优先顺序输出结果" << endl;
	for (sub.d = 0; sub.d < A.bounds[3]; ++sub.d)
	{
		for (sub.c = 0; sub.c < A.bounds[2]; ++sub.c)
		{
			for (sub.b = 0; sub.b < A.bounds[1]; ++sub.b)
			{
				for (sub.a = 0; sub.a < A.bounds[0]; ++sub.a)
				{
					sub2ind(A, sub, ind);
					cout << A.base[ind] << " ";
				}
			}
		}
	}
	cout << endl;
}

//5.给定下标求取对应下标的元素
Status GetValue(Array A, Sub sub, ElemType &elem)
{
	if ((sub.a<0 || sub.a>A.bounds[0] - 1) || (sub.b<0 || sub.b>A.bounds[1] - 1) || (sub.c<0 || sub.c>A.bounds[2] - 1) || (sub.d<0 || sub.d>A.bounds[3] - 1)) return ERROR;
	int ind;
	sub2ind(A, sub, ind);
	elem = A.base[ind];
	return OK;
}

//6.给定下标求取对应一维数组的序号（sub2ind）
Status sub2ind(Array A, Sub sub, int &ind)
{
	if ((sub.a<0 || sub.a>A.bounds[0] - 1) || (sub.b<0 || sub.b>A.bounds[1] - 1) || (sub.c<0 || sub.c>A.bounds[2] - 1) || (sub.d<0 || sub.d>A.bounds[3] - 1)) return ERROR;
	ind = 0;
	ind += A.constants[0] * sub.a;
	ind += A.constants[1] * sub.b;
	ind += A.constants[2] * sub.c;
	ind += A.constants[3] * sub.d;
	return OK;
}

//7.给定一位数组的单一索引值抓换成数组下标（ind2sub）
Status ind2sub(Array A, int ind, Sub &sub)
{
	//相关解释请参看底下注意事项第7条
	if (ind<0 || ind>A.elemtotal - 1) return ERROR;
	sub.a = ind / A.constants[0];
	sub.b = (ind % A.constants[0]) / (A.constants[1]);
	sub.c = ((ind % A.constants[0]) % (A.constants[1])) / A.constants[2];
	sub.d = (((ind % A.constants[0]) % (A.constants[1])) % A.constants[2]) % A.constants[2];
	return OK;
}

//8.消除孤维（squeeze）
Status squeeze(Array A,Array &B)
{
	bool is = false;
	int dim = A.dim;
	int boundary[MAX];
	int j = 0;
	for (int i = 0; i < A.dim; ++i)
	{
		if (A.bounds[i] == 1)
		{
			is = true;
			--dim;
		}
		else{
			boundary[j] = A.bounds[i];
			++j;
		}
	}
	if (!is) return ERROR;
	else{
		if (dim == 0) //防止全是1维界的情况
		{
			dim = 1;
			boundary[0] = 1;
		}
		InitArray(B, dim, boundary);
		for (int i = 0; i < A.elemtotal; ++i)
		{
			B.base[i] = A.base[i];
		}
		return OK;
	}
}

//9.显示当前数组信息
void ShowDate(Array A)
{
	cout << "-------------------------------------------" << endl;
	cout << "                当前数组信息                  " << endl;
	cout << "\t维数：" << A.dim << endl;
	cout << "\t形如A[a][b][c][d]这样的形式，当前数组对应的各维维度是" << endl;
	for (int i = 0; i < A.dim; ++i)
	{
		cout <<"\t"<< char('a' + i) << " :" << A.bounds[i] << endl;
	}
	cout << "\t数据总数是" << A.elemtotal << endl<<"\t";
	PrintArrayByRow(A);
	cout << "----------------------END------------------" << endl;
}

//10.销毁数组
Status DestroyArray(Array &A)
{
	if (!A.base) return ERROR;
	free(A.base); A.base = NULL;
	if (!A.bounds) return ERROR;
	free(A.bounds); A.bounds = NULL;
	if (!A.constants) return ERROR;
	free(A.constants); A.constants = NULL;
	return OK;
}

main.cpp

#include "Array.h"

int main()
{
	system("color 3E");//设置控制台背景颜色和字体颜色
	int inso;//需要输入的值，用于流程控制
	int inso1;//需要输入的值，用于流程控制
	char ch;//需要输入的值，用于流程控制
	Array A;
	A.elemtotal = 0;//用于判断是否创建了四维数组，便于流程控制
	Array B;
	Sub sub;//定义一个四维数据
	int ind;//定义一个一维数据
	bool creat = false;//用于判断降维数组是否成功
	ElemType elem;//定义一个数组元素类型的数据
	cout << "\t欢迎使用四维数组程序" << endl;
	while (1)
	{
		cout << "+------------------------------------------+" << endl;
		cout << "|\t1.创建四维数组                     |" << endl;
		cout << "|\t2.查看四维数组信息                 |" << endl;
		cout << "|\t3.输入下标查看四维数组值           |" << endl;
		cout << "|\t4.按照行优先顺序打印               |" << endl;
		cout << "|\t5.按照列优先顺序打印               |" << endl;
		cout << "|\t6.将下标转换为单一索引数值；       |" << endl;
		cout << "|\t7.将单一索引数值转换为数组的下标； |" << endl;
		cout << "|\t8.降维\t\t                   |" << endl;
		cout << "|\t9.退出\t\t                   |" << endl;
		cout << "+------------------------------------------+" << endl;
		cout << "请输入相关序号执行操作" << endl;
		cout << "Input:";
		cin >> inso;
		while (1)
		{
			if (inso == 1)
			{
				system("cls");
				cout << "将创建形如 A[a][b][c][d] 形式的四维数组，请依次输入个维度对应的维界值\n各维对应的值应当大于零！请严格输入" << endl;
				int boundary[MAX];//存放各个维度对应的维界
				for (int i = 0; i < 4; ++i)
				{
					cout << "\t" << char('a' + i) << " :";
					too: cin >> inso1;
					if (inso1 <= 0)
					{
						cout << "输入错误，不符合要求，请重新输入:";
						goto too;
					}
					boundary[i] = inso1;
				}
				InitArray(A, 4, boundary);//数组作为参数传入
				ValueArray(A);
				cout << "-----四维数组创建成功!-----" << endl;
				break;
			}
			else if (inso == 2)
			{
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else ShowDate(A);
				break;
			}
			else if(inso == 3){
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else{
					while (1)
					{
						cout << " 请输入你要查看的下标值，共四个数据" << endl;
						cout << " 形如 A[a][b][c][d] ，各个下标对应的取值范围" << endl;
						cout << " a: 0 - " << A.bounds[0]-1 << endl;
						cout << " b: 0 - " << A.bounds[1]-1 << endl;
						cout << " c: 0 - " << A.bounds[2]-1 << endl;
						cout << " d: 0 - " << A.bounds[3]-1 << endl;
						cin >> sub.a >> sub.b >> sub.c >> sub.d;
						if (GetValue(A, sub, elem))
						{
							cout << " 下标 A[" << sub.a << "][" << sub.b << "][" << sub.c << "][" << sub.d << "]对应的值为: " << elem << endl;
							cout << "是否继续查看？（N键退出查看，其余键继续）:";
							cin >> ch;
							if (ch == 'n' || ch == 'N')
								break;
						}
						else{
							cout << " 您输入的数据有误，请重新输入" << endl;
						}
					}
					break;
				}
			}
			else if (inso == 4)
			{
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else{
					PrintArrayByRow(A);
					break;
				}
			}
			else if (inso == 5)
			{
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else{
					PrintArrayByCol(A);
					break;
				}
			}
			else if (inso == 6){
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else{
					while (1)
					{
						cout << " 请输入你要转换的下标值，共四个数据" << endl;
						cout << " 形如 A[a][b][c][d] ，各个下标对应的取值范围" << endl;
						cout << " a: 0 - " << A.bounds[0] - 1 << endl;
						cout << " b: 0 - " << A.bounds[1] - 1 << endl;
						cout << " c: 0 - " << A.bounds[2] - 1 << endl;
						cout << " d: 0 - " << A.bounds[3] - 1 << endl;
						cin >> sub.a >> sub.b >> sub.c >> sub.d;
						if (sub2ind(A, sub, ind) == OK)
						{
							cout << " 下标 A[" << sub.a << "][" << sub.b << "][" << sub.c << "][" << sub.d << "]对应的索引值为: " << ind << endl;
							cout << "是否继续转换？（N键退出转换，其余键继续）:";
							cin >> ch;
							if (ch == 'n' || ch == 'N')
								break;
						}
						else{
							cout << " 您输入的下标值不符合要求，请重新输入" << endl;
						}
						
					}
					break;
				}
			}
			else if (inso == 7){
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else{
					while (1)
					{
						cout << " 请输入你要转换的索引值，范围： 0 - " <<A.elemtotal-1<< endl;
						cin >> ind;
						if (ind2sub(A, ind, sub) == OK)
						{
							cout << " 索引值: " << ind << " 对应的下标未 A[" << sub.a << "][" << sub.b << "][" << sub.c << "][" << sub.d << "] " << endl;
							cout << "是否继续转换？（N键退出转换，其余键继续）:";
							cin >> ch;
							if (ch == 'n' || ch == 'N')
								break;
						}
						else{
							cout << "您输入的索引值不符合范围，请重新输入" << endl;
						}
					}
					break;
				}
			}
			else if (inso == 8)
			{
				system("cls");
				if (A.elemtotal == 0)
				{
					cout << " 四维数组还未创建，请您前去创建四维数组！" << endl;
					break;
				}
				else{
					cout << "执行降维操作" << endl;
					if (squeeze(A, B) == ERROR) cout << "本数组无维数为1的维度，无法降维" << endl;
					else
					{
						creat = true;
						ShowDate(B);
					}
					break;
				}
			}
			else if (inso == 9)
			{
				if (A.elemtotal != 0)
				{
					DestroyArray(A);
				}

				if (creat == true)
				{
					DestroyArray(B);
				}
				system("cls");
				cout << "  谢谢使用，再见！\n按任意键继续....";
				_getch();
				exit(0);
			}
			else{
				cout << "您输入的字符有误，请重新输入" << endl;
				break;
			}
		}
	}
}

另：一些注意事项

1. 数组的维界是严格大于0的，所以维界值要格外注意。
2. 本程序采用的是行优先存储方式创建的，对于所谓的列优先输出，因为列优先也就是高下标优先，所以按照高下标的遍历方式，依次将四维下标转换成一维基址(sub2ind函数)，然后输出。
3. 销毁空间时，如果那段空间本来就没有被 malloc 分配内存，就会报错，所以 main.cpp 中的流程9有两个判断语句。
4. Array.h里定义的大部分函数返回值都是 Status ，这是为了便于 main.cpp 里的流程控制，因为判断数据是否正确写在 main.cpp 里回过于冗杂，也为了不让计算产生莫名奇妙的值，所以这些函数刚开始都是判断数据是否合理，不合理就不会继续进行计算。
5. 本程序的大部分函数都不可扩展，参数直接写死了，只能对四维坐标进行操作，尤其是数组被降维之后，对应 低于四维数组 的操作函数寥寥无几，设计函数是应当注意！
6. 消除孤维的时候要注意，如果都是1维，就要最后保留一个维度，为1维。
7. 关于 ind2sub函数（单一索引值转换成四维数组下标）的计算问题。刚开始稀里糊涂的写了上去，发现没啥问题，也没细想，写博客的时候又觉得有点不对劲，现在终于弄明白了。参看函数sub2ind的计算，简化式ind = A * (constants[0]) + B * (constants[1]) + C*(constants[2]) + D *(constants[3]);ABCD为四维数组下标。由此进行逆推，A = ind / constants[0]; ，那是因为其余部分的值B * (constants[1]) + C*(constants[2]) + D *(constants[3])除以 constants[0] 都要小于1。

功能展示

比较辣鸡，展示部分功能。

起始界面

创建四维数组

查看当前数组信息

下标转换为索引值

降维操作

完结感言

本次课设的难度一般，想清楚该怎么做后，几个小时就可以做完。但与之相比，课设的报告书，还有这篇博客都是非常的费时间。自己也挺菜的，函数写成了那个样子，没法复用，也得感谢严蔚敏老师的《数据结构》提供了非常好的数据结构与方法，但是为了一些操作的方便就没有使用原书中的用到的stdarg.h 和变参方法。太菜了，继续努力吧！

END! 2019/1/11 22:24:36

---