noncollision2.cpp

实现4×4的数组元素的无冲突的存储

////////////////////////////////////////////////////////////////////////////////////////
//文件名：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;//仅输出下标代表输出元素值
}