////////////////////////////////////////////////////////////////////////////////////////
//文件名：noncollision2.cpp
//功能：實現4×4二維數組的無沖突存放演示。其中存儲體個數為4。該算法不會浪費
//      存儲體空間。
//基本思想：一般情況下要實現轉換，需要專門定義一個結構體存儲原數組的下標i，j，但本算法
//      巧妙利用了原數組下標與元素之間的聯系，非常簡單地實現了存儲體號體內地址與原數組
//      下標之間的關系。例如，原數組元素a23,其下標i＝2，j＝3，而a23＝11，其二進制表示為
//      1011，其前兩位10（十進制為2）恰好是下標i，其后兩位11（十進制3）恰好是j，這樣對
//      數組下標的操作，轉化為對數組元素的操作，實現起來非常簡單。其核心代碼在函數newj
//      中共5行。
//
//      江南大學   王向宇   學號：s070502026     2007.10.30
////////////////////////////////////////////////////////////////////////////////////////

#include <Math.h>
#include <iostream.h>
#include <iomanip.h>
//定義一個短整形數組，數組元素的二進制表示恰好是下標的二進制表示，這樣處理非常方便
short int a[4][4]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
short int b[4][4];//存放數組元素在存儲體中的體號及位置的數組
short int iH,iL,jH,jL,i,j,line,col;

////////////////////////////////////////////////////////////////////////////////////
//該函數根據數組的下標求出存儲體的體號
short int newj(short int i,short int j)
{
	iL=(a[i][j]>>2)&1;//求i的低位
	iH=(a[i][j]>>3);//求i的高位
	jL=a[i][j]&1;//求j的低位
	jH=(a[i][j]>>1)&1;//求j的高位
	return (2*(iL^jH)+(iH^iL^jL));//求出存儲體的體號
}

////////////////////////////////////////////////////////////////////////////////////////
//主程序
void main()
{
	//輸出原始數組,用下標代表元素，這樣更直觀
	cout<<"原始數組為："<<endl;
	for (i=0;i<4;i++)
	{
		for (j=0;j<4;j++)
		{
			 cout<<setw(5)<<"a["<<a[i][j]/4<<"]["<<a[i][j]%4<<"]";//僅輸出下標代表輸出元素值
		}
		cout<<endl;
	}
	//計算無沖突的數組在存儲體中的位置
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
		{
			b[j][newj(i,j)]=a[i][j];//體內地址為j
		}
	//輸出無沖突的數組在存儲體中的位置
	cout<<"數組中各元素在存儲體中的位置為："<<endl;
	cout<<"體號： 0        1         2          3"<<endl;
	for(i=0;i<4;i++)
	{
		for(j=0;j<4;j++)
		{
			cout<<setw(5)<<"a["<<b[i][j]/4<<"]["<<b[i][j]%4<<"]";//僅輸出下標代表輸出元素值	
		}
		cout<<endl;
	}

	cout<<endl;
	cout<<"請輸入原始數組元素地址(下標),";
	cout<<"行下標為：";
	cin>>line;
	cout<<endl;
	cout<<"列下標為：";
	cin>>col;
	cout<<endl;
	cout<<"體號是:"<<newj(line,col)<<endl;//數組第一個元素的體號地址k=0
	cout<<"體內地址是:"<<col<<endl;
	cout<<"該元素值為:"<<line<<col<<endl;//僅輸出下標代表輸出元素值
}