8_5_array.c

gc:高级程序员考试用书的c程序源文件

#include <stdio.h>
//#include <stdlib.h>

int colToRow(int k,int n)   /*函数,由按列优先存储下标为k的元素,求其按行优先存储的下标*/
{
	int i = k,j = 0;
	while (i>j) i -= ++j;
	return i*n+j-i*(i+1)/2;
}



/*函数，上三角阵一维数组按行优先存储改为按列优先存储*/
void trans(int b[],int n)
{
	char p;           //我加的
	int m,k,r,c,w;
	m = (n+1)*n/2-4;
	printf("要调整的个数=%d",m);       //我加的
	printf("\n输入一个字符继续");     //我加的
	scanf("%c",&p);         //我加的

	k = 2;
	while (m>0) {    /*每调整一个减一*/
		r = colToRow(k,n);   /*调整后下标为k的元素，求得调整前的下标r  */
		//printf("\n开始这个下标了,前一个下标=%d",r);
		if (r == k) m--;      /*调整前后相同，不调整*/
		else {                 /*调整前后不相同，存在一个调整链*/
			c = k; w = r;
			while(r > k) {  /*遍历循环传送链，看循环结束前是否有比k更小的下标*/
				c = r; r = colToRow(c,n);
				//printf("\n遍历:前一个下标=%d",r);
				//printf("\n搜索一次");
			}
			if(r == k) {      /*循环传送链上没有比k更小的下标，是还未处理的传送链*/
				c = k; r = w; w = b[k];
				while(r != k) {  /*直至循环传送链又回到头，才结束*/
					b[c] = b[r];
				    m--;
					printf("\nb[%d]->b[%d]",r,c);
					c = r; r = colToRow(c,n);

				}
				b[c] = w;
				printf("\nb[%d]->b[%d]",k,c);
				m --;
			}
		}
		k++;               /*准备考察下一个下标*/


	}


}

void main()
{

	int i;
	int j;
	int a [5][5] = {{1,  2,  3,  4,  5},       //原始数组
				   {0,  6,  7,  8,  9},
				   {0,  0, 10, 11, 12},
				   {0,  0,  0, 13, 14},
				   {0,  0,  0,  0, 15}
				   };

	int b[15] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};  //按照行优先存储
	int c[15] = {1,2,6,3,7,10,4,8,11,13,5,9,12,14,15};   //按照列优先存储

	printf("你所输入的数组，原始形式如下\n");
	for (i=0;i<5;i++) {

		for (j=0;j<5;j++)
			printf("  %d",a[i][j]);
		printf("\n");
	}

	printf("\n行优先存储的数组形式如下\n");
	for (i=0;i<15;i++)
		printf("  %d",b[i]);


	printf("\n列优先存储的数组形式如下\n");
	for (i=0;i<15;i++)
		printf("  %d",c[i]);

	printf("\n");



	printf("\n行优先的数组用函数转化后，我们看它是不是和列优先存储的形式一样?\n");
	//if (trans(b,5)) printf("可以转换\n");
	//else printf("\n不可以转换\n");
	printf("\n本程序从b[2]开始,一次循环的循环链,就包括了所有的答案,b[8]不需要移动\n");

	trans(b,5);
	printf("\n");

	for (i=0;i<15;i++)
		printf("  %d",b[i]);


}