(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 << "-----------------------                ---------------------------
";
	cout << " ->       ，      :

";
	TwiArr test;
	test.display();
	cout << endl;

	cout << endl << " ->          :

";
	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
       . . .