gc_8_7sanyuan.c

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

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

void transpose(int a[][3],int b[][3])
{
	int m,n,i,j,*x,*y;
	b[0][1] = a[0][0];           /*转置后矩阵的列数*/
	n = b[0][0] = a[0][1];       /*转置后的行数*/
	m = b[0][2] = a[0][2];       /*转置后的矩阵元素个数*/

	if(m <= 0) return;
	y = (int *)malloc(sizeof(int)*(n+1));   /*工作数组*/
	x = y + 1;
	for (i = 0;i < n; i++) x[i] = 0;
	for (i=1;i <= m;i++) x[a[i][1]]++;   /*统计b的各行元素个数*/
	y[0] = 1;
	for(i=1;i<n;i++)
		y[i]=y[i-1]+x[i-1];           /*计算b的各行第一个元素的存储下标*/
	for(i=1;i<=m;i++) {
		j=y[a[i][1]]++;       /*增1是为了预置同行下一个元素的存储下标*/
		b[j][0]=a[i][1];            /*列号改为行号*/
		b[j][1]=a[i][0];           /*行号改为列号*/
		b[j][2]=a[i][2];            /*复制值*/
	}
	free(y);
}

void main()

{
	int index=0;    /*数组数据索引值*/;

    /*原始数组行优先,这些代码可以不用写出,写出来是为了验证结果*/
	int x[5][4] = {{1, 0, 0, 0},
	               {0, 5, 0, 0},
				   {0, 0, 7, 2},
				   {6, 0, 0, 0},
				   {0, 3, 0, 8}};

	  /*原始数组三元组表*/
	  int a[][3] ={{5,4,7},
	               {0,0,1},
				   {1,1,5},
				   {2,2,7},
				   {2,3,2},
				   {3,0,6},
				   {4,1,3},
				   {4,3,8}};
	  int x_compress[10][3];            /*存贮程序压缩的三元组表*/

		 /*转置后的数组,这些代码可以不用写出,写出来是为了验证结果*/
	//int x_trans[4][5] = {{1, 0, 0, 6, 0},
	                 	// {0, 5, 0, 0, 3},
					 	// {0, 0, 7, 0, 0},
						// {0, 0, 2, 0, 8}};


	/*转置后的三元组表三元组表,这些代码可以不用写出,写出来是为了验证结果*/
	int x_trans_a[][3]= {{4,5,7},
	                     {0,0,1},
						 {0,3,6},
						 {1,1,5},
						 {1,4,3},
						 {2,2,7},
						 {3,2,2},
						 {3,4,8}};

	int x_trans[4][5];          /*转置后的矩阵*/
	int i,j;

	int b[20][3];

	printf("原始数组\n");
	for (i=0;i<5;i++) {
		for (j=0;j<4;j++)
			printf("%d  ",x[i][j]);
		printf("\n");
	}


    printf("原始数组的三元组表,是手动输入的,而不是程序压缩的\n");
	for (i=0;i<8;i++) {
		for (j=0;j<3;j++)
			printf("%d  ",a[i][j]);
		printf("\n");
	}


	printf("原始数组的三元组表,是程序压缩的\n");
	for(i=0;i<5;i++)    /*进行数据压缩*/
		for(j=0;j<4;j++)
			if(x[i][j] != 0) {
				index++;   /*增加数据索引值*/
				x_compress[index][0] = i;
				x_compress[index][1] = j;
				x_compress[index][2] = x[i][j];
			}

	x_compress[0][0] = 5;
	x_compress[0][1] = 4;
	x_compress[0][2] = index;
	for (i=0;i<=index;i++) {
		for (j=0;j<3;j++)
			printf("%d  ",x_compress[i][j]);
		printf("\n");
	}

	printf("转置后的矩阵,程序完成\n");
	for (i=0;i<5;i++)
		for(j=0;j<4;j++)
			x_trans[j][i]=x[i][j];

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


	printf("转置后的三元组表,从转置后的矩阵压缩成三元组表\n");
	index=0;
	for (i=0;i<4;i++)
		for(j=0;j<5;j++)
			if(x_trans[i][j] != 0) {
				index++;
				b[index][0]=i;
				b[index][1]=j;
				b[index][2]=x_trans[i][j];
			}
	b[0][0] = i;
	b[0][1]= j;
	b[0][2] = index;
	for (i=0;i<=b[0][2];i++) {
		for (j=0;j<3;j++)
			printf("%d  ",b[i][j]);
		printf("\n");
	}




	printf("转置后的三元组表,直接从三元组表到三元组表转换\n");
	for (i=0;i<20;i++)
		for (j=0;j<3;j++)
			b[i][j]=0;
	transpose(a,b);
	for (i=0;i<=b[0][2];i++) {
		for (j=0;j<3;j++)
			printf("%d  ",b[i][j]);
		printf("\n");
	}
}