数组10——数组的压缩存储2——上三角阵的压缩存储

编写一个算法，将一个以行为主序存储的一维数组转换为以列为主序压缩存储的一维数组。例如，设有n×n的上三角矩阵A的上三角元素已按行为主序连续存放在数组b中，请设计一个算法Trans将b中元素按列为主序存放在数组c中。当n=5时，

矩阵A如图所示：

其中b=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15),c=(1,2,6,3,7,10,4,8,11,13,5,9,12,14,15)

【分析】

本题是软件设计师考试题目和上海交通大学考研题目，主要考察特殊矩阵的压缩存储中对数组下标的灵活使用程度。用i和j分别表示矩阵中元素的行列下标，用k表示压缩矩阵b元素的下标。本题最重要是找出以行为主序和以列为主序的对应关系，即

c[j*(j+1)/2+i]=b[k];

其中，j*(j+1)/2+i就是根据等差数列得出的。根据这个对应关系，直接把b中的元素赋值给c中对应的位置即可。但是读出c中一列即b中的一行之后，还要改变行下标i和列下标，开始读6，7，8元素时，列下标j需要从1开始，行下标也需要增加1，依此类推，可以得出以下修改行下标和列下标的办法：

当一行还没有结束时，j++；否则i++修改下一行的元素个数及i、j的值，直到k=n(n+1)/2为止。
main.cpp

#include<iostream>
#include<iomanip>
using namespace std;
#define MAX 200
void CreateArray(int a[][MAX], int n);
void PrintArray(int a[MAX][MAX], int n);
void Trans(int b[], int c[], int n);
int PriorRow(int a[][MAX], int n, int b[]);
void main()
{
	int a[MAX][MAX], b[MAX], c[MAX], n, m, i;
	cout << "请输入一个整数（<100）:" << endl;
	cin >> n;
	CreateArray(a, n);
	cout << "二维数组为:" << endl;
	PrintArray(a, n);
	m = PriorRow(a, n, b);
	cout << "数组b中的元素:" << endl;
	for (i = 0; i < m; i++)
		cout << setw(4) << b[i];
	cout << endl;
	Trans(b, c, n);
	cout << "数组c中的元素:" << endl;
	for (i = 0; i < m; i++)
		cout << setw(4) << c[i];
	cout << endl;


	system("pause");
}
int PriorRow(int a[MAX][MAX], int n, int b[])
//行优先存储上三角矩阵到b中
{
	int i, j, k = 0;
	for (i = 0; i < n; i++)
		for (j = i; j < n; j++)
			b[k++] = a[i][j];
	return k;
}
void CreateArray(int a[][MAX], int n)
//创建一个上三角1-n的二维数组（矩阵）
{
	int i, j, m;
	m = 1;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < i; j++)
			a[i][j] = 0;
		for (j = i; j < n; j++)
			a[i][j] = m++;
	}
}
void PrintArray(int a[MAX][MAX], int n)
//打印矩阵
{
	int i, j;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			cout << setw(4) << a[i][j];
		cout << endl;
	}
}
void Trans(int b[], int c[], int n)
{
	int step = n, count = 0, i = 0, j = 0, k;
	for (k = 0; k < n*(n + 1) / 2; k++)
	{
		count++;			/*记录一行是否读完*/
		c[j*(j + 1) / 2 + i] = b[k];/*把以行为主序的数存放到对应以列为主序的数组中*/
		if (count == step)/*一行读完后*/
		{
			step--;
			count = 0;/*下一行重新开始计数*/
			i++;/*下一行的开始行*/
			j = n - step;/*一行读完后，下一轮的开始列*/
		}
		else
			j++;/*一行还没有读完，继续下一列的数*/
	}
}

结果：

最后

以上就是知性大树为你收集整理的数组10——数组的压缩存储2——上三角阵的压缩存储的全部内容，希望文章能够帮你解决数组10——数组的压缩存储2——上三角阵的压缩存储所遇到的程序开发问题。

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