(2011.11.11) 4_a1.cpp -- 下三角矩阵的压缩存储定义

65 阅读 0 评论 43 点赞

我是靠谱客的博主大方老鼠，最近开发中收集的这篇文章主要介绍(2011.11.11) 4_a1.cpp -- 下三角矩阵的压缩存储定义，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

源代码：

// 4_a1.cpp -- 下三角矩阵的压缩存储定义

/* 
 * -> 题目要求：
 * 1.已知矩阵A[5][5]是一个下三角矩阵，如下图
 *   1 0 0 0 0
 *   4 7 0 0 0
 *   6 9 5 0 0
 *   1 8 4 1 0
 *   2 3 0 9 6
 * 2.要求编写算法把矩阵A采用压缩存储，存储到一维数组B[16]中;
 * 3.能依次输出B中各元素的值以验证该算法功能已实现。
 * 4.此题的源程序保存为4_a1.cpp。
 **/

/*
 * -> 题目及相关知识点分析：
 * 1. 所用知识：本次题目，要求用到的知识有数组的定义和压缩存储的方法。
 * 2. 数组的定义：对于数组定义，实际上最原始的是将[n][n]的数组展开为一个n*n的一维数组。
 * 3. 数组的定义：如果想用更符合思路的定义，减少计算量，还可以使用嵌套存放数据的方式来定义二维数组，
 *                不过估计这样的效率不会很高，所以在各教材上才没有说。
 * 4. 压缩存储的思路：
 *    01.目的：实质上，题目就是要将a[5][5]每一个元素在b[16]中找到一个个相对应的元素；调用a[][]，存放b[].
 *    02.需求：需要知道a[i][j]跟b[n]之间的逻辑关系；
 *    03.为什么题目给出16 ？  在a中，现在可以知道的是 0 < i <= 5, 0 < j <= 5;
 *    04. 下三角矩阵中，右上角的元素全为零，可以放在同一个地址中，这就是所谓的压缩了。
 *    05. 这样一来，5*5=25, 5*5/2+5/2+1=15个有元素的地址，再另加上一个存放0的地址，刚刚好，15+1=16。
 *    06. 我想，这就是为什么题目要求将a[5][5]存放在b[16]中的原因了。
 *    07. 注意，刚刚 5*5/2+5/2+1=15的原因是：
 *    08. 先计算5*5一共有多少个元素，再除以2,取得半个矩阵的个数，然后再加上5/2，获得左上角与右上角的连线的元素个数的一半，
 *        此时，在n为偶数的矩阵中，刚刚好可以计算出有元素的地址是多少。
 *        假如，n为奇数的矩阵，因为刚刚用了两次除以2的取整除法，都会有一个余数，最后一步+1实际上就是将两次余数0.5+0.5相加。
 *    09.矩阵中零元素的存放特性：可以看出，当i<j时，a[i][j]存放的就是零元素了，也就是说，这是判断存放时if-else里面的条件之一。
 *    10.矩阵中下三角元素的存放特性：
 *    11.b[k]-a[i][j], 0-[1][1], 1-[2][1], 2-[2][2], 3-[3][1], 4-[3][2], 5-[3][3], 6-[4][1], 7-[4][2], 8-[4][3], 9-[4][4]
 *       可以看出，在每一行中，当j从0递增到i时，即停止，进入i递增，实际上，我们要算出的就是从上面数下来，数了多少个数。
 *       先观察k与i的规律，可以看出，k = k-1+i，仔细列出表可以看出0+1+2+3+4+...i = k，即该式为一次方求和公式，i(i-1)/2,0<i<n
 *       以前数学没学好，费了N大的功夫，终于把一次方求和的公式推出来了，最后，只差一步，j，整个完整的公式就是i(i-1)/2+j-1
 *       晕：做数据结构的题目简直就是在做数学题目啊~
 *       附：一次方求和公式推导过程：1+2+3+...n = s, s = n(n-1)/2，图表  c = r = n
 *          数值：1 2 3 4 5 6，下面将数值以列的方式1+1+1＝数值的方式排列出来
 *                1 1 1 1 1 1
 *                0 1 1 1 1 1
 *                0 0 1 1 1 1
 *                0 0 0 1 1 1
 *                0 0 0 0 1 1
 *                0 0 0 0 0 1
 *          假如将1加到6就是将第1列的1移到第5列中，第2列中的1移到第4列中，这样刚刚可以看出，在这个一矩阵中，6*6，
 *          而满1的位置刚刚占了整个矩阵的一半，跟刚刚所说的原理一样，6*6/2+(对角线)6/2=6*(6+1)/2, 即n(n+1)/2
 *          由于这时需要用到的情况是下标从零开始的，所以，n = n - 1, 式子就变为 (n-1)n/2，于是i(i-1)/2就出来啦。
 *    12.这样一来，总结一下下三角矩阵算法中b[k]与a[i][j]之间的关系：
 *       i >= j 时，k = i(i-1)/2 +j-1
 *       i < j  时，k = n-1最后一位存放0
 **/

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

class TwiArr
{
private:
	double * ta;			// 存放顺序表的数组
	int arrsize;			// 记录矩阵行列长度
	int maxsize;			// 记录顺序表总长度
	enum a{defaultsize = 5};// 默认矩阵行列长度
	int leftsize;			// 记录现在的位置

// 构造、析构
	void init(int ms)
	{
		int judgejo(ms % 2);	// 用于判断奇偶
		if (judgejo == 0)		// 偶数
		{ 
			maxsize = ms * ms / 2 + ms / 2;
		}
		else					// 奇数
		{
			maxsize = ms * ms / 2 + ms / 2 + 2;
		}
		ta = new double[maxsize];	// 将数组中的数将被初始化为零
		for (int i = 0; i != maxsize; ++i)
		{
			ta[i] = 0;
		}
		arrsize = ms;
		leftsize = 0;
		return;
	}
	void removeall()
	{
		delete [] ta;
		leftsize = 0;
		maxsize = 0;
		return;
	}

public:
// 构造，析构
	TwiArr(int ms = defaultsize){init(ms);}
	~TwiArr(){removeall();}
// 修改距阵中的值
	void changeelem(const double &, int vi, int vj);
// 显示距阵
	void display();
};

/*
 * 函数名称：TwiArr::display
 * 函数功能：将两种形式显示TwiArr.ta里面的值。
 * 函数参数：无。
 */

void TwiArr::display()
{
	cout << "-> 以下数组以b[k]的顺序显示：" << endl;
	cout << "   ";
	for (int i = 0; i != maxsize; ++i)
	{
		cout <<  ta[i];
		if (i != maxsize - 1)
			cout << " | ";
		else 
			cout << endl;
	}
	cout << endl;
	cout << "-> 以下数组以a[i][j]的顺序显示：" << endl;
	for (int i = 1; i <= arrsize; ++i)
	{
		cout << "    ";
		for (int j = 1; j <= arrsize; ++j) 
		{
			if ( i < j)
			{
				cout << ta[(maxsize - 1)] ;
			}
			else
			{
				cout << ta[(i*(i-1)/2 + j-1)];
			}
			cout << "  ";
		}
		cout << endl;
	}
	return ;
}

/*
 * 函数名称：TwiArr::changeelem
 * 函数功能：将单个元素的值赋入TwiArr中的数据成员*ta里面存储。
 * 函数参数：该函数有三个形参，第一个为double形用于修改二维数组里面值的参数
 *           第二个与第三个为用于用户调用的二维数组的行与列。
 */
void TwiArr::changeelem(const double & value,int vi, int vj)
{	
	if ( vi < vj)		// 因为这个为下三角矩阵，所以当vi<vj时，直接返回，如果程序再完善，这里还应出现错误信息。
	{
		return;
	}
	else
	{
		ta[(vi*(vi-1)/2 + vj-1)] = value;
	}
	return;
}

// --------------------------------------------------------- main start -----------------------------------------------

int main()
{
	cout << "----------------------- 现在开始二维数组的顺序表测试 ---------------------------n";
	cout << " -> 刚开始测试时，未赋值的数组:nn";
	TwiArr test;
	test.display();
	cout << endl;

	cout << endl << " -> 现开始赋值后的测试:nn";
	void giveValue(TwiArr &);
	giveValue(test);
	test.display();
	system("pause");	
	return 0;
}

void giveValue(TwiArr & test)
{
	/* 给二维数组初始化下面的值
	 *   1 0 0 0 0
	 *   4 7 0 0 0
	 *   6 9 5 0 0
	 *   1 8 4 1 0
     *   2 3 0 9 6
     */
	test.changeelem(1, 1, 1);
	test.changeelem(4, 2, 1);
	test.changeelem(7, 2, 2);
	test.changeelem(6, 3, 1);
	test.changeelem(9, 3, 2);
	test.changeelem(5, 3, 3);
	test.changeelem(1, 4, 1);
	test.changeelem(8, 4, 2);
	test.changeelem(4, 4, 3);
	test.changeelem(1, 4, 4);
	test.changeelem(2, 5, 1);
	test.changeelem(3, 5, 2);
	test.changeelem(0, 5, 3);
	test.changeelem(9, 5, 4);
	test.changeelem(6, 5, 5);
	return;
}

运行结果：

----------------------- 现在开始二维数组的顺序表测试 ---------------------------

 -> 刚开始测试时，未赋值的数组:

-> 以下数组以b[k]的顺序显示：
   0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

-> 以下数组以a[i][j]的顺序显示：
    0  0  0  0  0
    0  0  0  0  0
    0  0  0  0  0
    0  0  0  0  0
    0  0  0  0  0


 -> 现开始赋值后的测试:

-> 以下数组以b[k]的顺序显示：
   1 | 4 | 7 | 6 | 9 | 5 | 1 | 8 | 4 | 1 | 2 | 3 | 0 | 9 | 6 | 0

-> 以下数组以a[i][j]的顺序显示：
    1  0  0  0  0
    4  7  0  0  0
    6  9  5  0  0
    1  8  4  1  0
    2  3  0  9  6
请按任意键继续. . .