数据结构

开发平台：
Visual C++

CalcSparseMatrix.cpp：源码内容
							
/*******************************************************************************
  《数据结构》之上机实践源代码 1 - 稀疏矩阵的操作
   功    能：实现稀疏矩阵的加、减、乘法和转置操作
   作    者：刘伟
   编写日期：2008-05-08
   版 本 号：v 1.0
   备    注：使用标准 C 代码实现
 	 
*******************************************************************************/
// 使用的库定义
#include <stdio.h>
// 常量定义
#define MAX_ELEM_NUM 100    // 稀疏矩阵中的最大元素个数，假定矩阵操作（如加、减等）后的元素个数
                            // 也不超过这个值。注意：因为采用三元组法表示稀疏矩阵，因此相加等操作
                            // 后的矩阵元素个数可能比相加前的矩阵要多。 
#define TRUE  1
#define FALSE 0
// 稀疏矩阵元素类型定义（三元组结构） - 记录体
struct SparseMatrixElem
{
  // 非零元素的行号
  int RowNo;
  // 非零元素的列号
  int ColNo;
  // 非零元素的值（假定全部为整数）
  int ElemValue;
};
// 采用一维数组的方式将稀疏矩阵中的元素组织起来 ...
// 注意：数组的第一个元素（下标为 0）的 3 个数据域
// 的含义依次为：矩阵的行数、列数、非零元素的个数
SparseMatrixElem A[MAX_ELEM_NUM], B[MAX_ELEM_NUM], C[MAX_ELEM_NUM];
// 按照给定的行号和列号在三元组组数组中寻找稀疏矩阵的元素值并返回 ...
// 返回索引号（索引号为 0 - FALSE 则表示未找到） ...
int GetElemValue(SparseMatrixElem *pA, int TargetRowNo, int TargetColNo)
{
  int i;
  for(i=1; i<=pA -> ElemValue; i++)
  {
    if ( ((pA + i) -> RowNo == TargetRowNo) && ((pA + i) -> ColNo == TargetColNo) )
      return i;
  }
  return 0;
}
// 注意：在 C 语言中，数组名表示数组的首地址，是一个指针
// 下面的许多操作采用指针进行。该指针指向 SparseMatrixElem
// 类型的元素。
// 将三元组形式表示的稀疏矩阵输出为常规形式 ...
// 如三元组表示为：
// 
// 3   3   3
// 1   1   4
// 2   1   5
// 2   3   1
//
// 调用本函数后显示为：
// 
// 4   0   0
// 5   0   1
// 0   0   0
void DisplayMatrix(SparseMatrixElem *pA)
{
  int m, n, k;
  for (m=1; m<=pA->RowNo; m++)
  {
	printf("| ");
    for (n=1; n<=pA->ColNo; n++)
    {
      k = GetElemValue(pA, m, n);
      if (k > 0)
        printf("%d", (pA + k) -> ElemValue);
	  else
        putchar('0');
	  // 输出 2 个空格符保证美观，最后一个元素不输出空格 ...
	  if (n < pA->ColNo)
	  {
	    putchar(' ');
	    putchar(' ');
	  }
	}
	printf(" |");
	// 矩阵一行元素输出完毕，换行 ...
	printf("n");
  }
}
// 显示三元组数据 ...
void DisplayTripleArray(SparseMatrixElem *pA)
{
  int k;
  for (k=0; k<=pA->ElemValue; k++)
  {
	printf("| %d  ", (pA + k) -> RowNo);
    printf("%d  ", (pA + k) -> ColNo); 
	printf("%d |", (pA + k) -> ElemValue);
    
	// 矩阵一行元素输出完毕，换行 ...
	printf("n");
  }
}
// 显示稀疏矩阵数据 ...
// (1) 显示矩阵格式；
// (2) 显示三元组格式；
void DisplaySparseMatrix(SparseMatrixElem *pA)
{
  printf("---------------------------------n");
  printf("[Matrix] n");
  DisplayMatrix(pA);
  printf("[Triple Array] n");
  DisplayTripleArray(pA);
  printf("---------------------------------n");
}
// 从键盘输入稀疏矩阵数据 ...
void GetSparseMatrixData(SparseMatrixElem *pA)
{
  int TotalRowNum;
  int k;
  // 表示 Triple Array 格式输入，如：
  // 3   3   3
  // 1   1   4
  // 2   1   5
  // 2   3   1
  printf("Input matrix data with [Triple Array] format : n");
  printf("n");
  // 输入行数（三元组的总行数）：
  printf("Total row number for triple array : ");
  scanf("%d", &TotalRowNum);
  
  // 输入实际数据 ...
  printf("[Triple Array] data : n");
  for(k=0; k<TotalRowNum; k++)
  {
    // 只有 3 列 ...
    scanf("%d%d%d", &((pA + k) -> RowNo), &((pA + k) -> ColNo), &((pA + k) -> ElemValue));
  }
}
// 从文件输入稀疏矩阵数据 ...
int GetSparseMatrixData(SparseMatrixElem *pA, char*filename)
{
  FILE *fp;
  int TotalRowNum;
  int k;
  // 打开数据文件 ...
  if ((fp = fopen(filename, "r")) == NULL)
  {
    printf("Error open sparse matrix data file %s !n", filename);
    return FALSE;
  }
  
  // 读入行数（三元组的总行数）：
  fscanf(fp, "%d", &TotalRowNum);
  
  // 输入实际数据 ...
  for(k=0; k<TotalRowNum; k++)
  {
    // 只有 3 列 ...
    fscanf(fp, "%d%d%d", &((pA + k) -> RowNo), &((pA + k) -> ColNo), &((pA + k) -> ElemValue));
  }
  
  // 关闭数据文件 ...
  fclose(fp);
  
  return TRUE;
}
// pA 和 pB 为指向 SparseMatrixElem 类型数据的指针，计算时将数组的名称传入 ...
// 本函数的功能是：稀疏矩阵 pA 和 pB 相加，计算结果存入 pC 中 ...
// C = A + B
void AddSparseMatrix(SparseMatrixElem *pA, SparseMatrixElem *pB, SparseMatrixElem *pC)
{
  int m, k;
  int OverlapElemNum = 0; // 2 个矩阵对应重叠位置元素的个数 ...
  int N = 0;
  // 只有大小相等的矩阵才能相加 ...
  if ( (pA -> RowNo !=  pB -> RowNo) || (pA -> ColNo !=  pB -> ColNo) )
  {
    printf("Matrix''s size NOT equal !n");
	return;
  }
  // 设置 C 矩阵的大小 ：在大小上 'C = A = B' ...
  pC -> RowNo = pA -> RowNo;
  pC -> ColNo = pA -> ColNo;
  
  // 算法如下：
  // (1) 将 A 矩阵中的所有元素 copy 到 C 矩阵中;
  pC -> ElemValue = pA -> ElemValue;
  N = pC -> ElemValue; // 记录当前 C 矩阵中元素的个数 ...
  for (m=1; m<= pA -> ElemValue; m++)
  {
    (pC + m) -> RowNo     = (pA + m) -> RowNo;
    (pC + m) -> ColNo     = (pA + m) -> ColNo;
    (pC + m) -> ElemValue = (pA + m) -> ElemValue;
  }
  
  // (2) 依次处理 B 矩阵中的每个元素，如果该元素对应位置上存在 A 矩阵元素则运算，否则
  //     在 C 矩阵中增加一个新元素;
  for (m=1; m<= pB -> ElemValue; m++)
  {
    // 在 C 矩阵中查找是否存在某个位置上的元素 ...
	// 如找到则返回该元素的位置，否则返回 0 ...
	k = GetElemValue(pC, (pB + m) -> RowNo, (pB + m) -> ColNo);
    if (k > 0)
    {
      // 相加 ...
      (pC + k) -> ElemValue = (pC + k) -> ElemValue + (pB + m) -> ElemValue;
      OverlapElemNum++; // 重叠位置数累加，用于计算 C 矩阵的三元组表示中元素的个数 ...
	}
	else // 返回 0 - FALSE，表示矩阵 B 中出现一个新位置的元素 ...
	{
      N++;
      (pC + N) -> RowNo     = (pB + m) -> RowNo;
      (pC + N) -> ColNo     = (pB + m) -> ColNo;
      (pC + N) -> ElemValue = (pB + m) -> ElemValue;
	}
  }
  // 计算 C 矩阵中元素的个数 ...
  pC -> ElemValue = (pA -> ElemValue + pB -> ElemValue) - OverlapElemNum;
  // (3) 对 C 矩阵中元素进行排序，保证其行、列标号为递增序（暂略）;
  // ...
}
// pA 和 pB 为指向 SparseMatrixElem 类型数据的指针，计算时将数组的名称传入 ...
// 本函数的功能是：稀疏矩阵 pA 和 pB 相减，计算结果存入 pC 中 ...
// C = A - B
void SubtractSparseMatrix(SparseMatrixElem *pA, SparseMatrixElem *pB, SparseMatrixElem *pC)
{
  int k;
  
  // C = A - B = A + (-B)
  // 本函数可以调用 [AddSparseMatrix] 函数 ...
  // 注意：下面的循环从 1 开始，这是存放稀疏矩阵中非零元素开始的位置 ...
  for (k=1; k<=pB -> ElemValue; k++)
  {
    (pB + k) -> ElemValue = -1 * (pB + k) -> ElemValue; 
  }
   
  AddSparseMatrix(pA, pB, pC);
  // 因为可能进行后续计算，所以必须将 B 矩阵的值复原 ...
  for (k=1; k<=pB -> ElemValue; k++)
  {
    (pB + k) -> ElemValue = -1 * (pB + k) -> ElemValue; 
  }
}
// pA 和 pB 为指向 SparseMatrixElem 类型数据的指针，计算时将数组的名称传入 ...
// 本函数的功能是：稀疏矩阵 pA 和 pB 相乘，计算结果存入 pC 中 ...
// C = A * B
//
// 提示：先要判断 2 个矩阵是否可以进行相乘运算 ...
void MultipleSparseMatrix(SparseMatrixElem *pA, SparseMatrixElem *pB, SparseMatrixElem *pC)
{
// [上机作业] - 自己上机实现 ...
}
// 本函数的功能是：稀疏矩阵 pA 进行转置操作，计算结果存入 pC 中 ...
// C = A - B
void TransposeSparseMatrix(SparseMatrixElem *pA, SparseMatrixElem *pC)
{
  int m;
  // 设置 C 矩阵的大小 ：在大小上 'C = A' ...
  pC -> RowNo = pA -> RowNo;
  pC -> ColNo = pA -> ColNo;
  // “转置”操作：交换“三元组”中各个元素的行、列号即可 ...
  pC -> ElemValue = pA -> ElemValue;
  for (m=1; m<= pA -> ElemValue; m++)
  {
    (pC + m) -> RowNo     = (pA + m) -> ColNo;
    (pC + m) -> ColNo     = (pA + m) -> RowNo;
    (pC + m) -> ElemValue = (pA + m) -> ElemValue;
  }
}
// ####################################################################### //
//                                                                         // 
//                           下面是主程序开始                              // 
//                                                                         // 
// ####################################################################### //
void main(void)
{
  SparseMatrixElem *pA;
  SparseMatrixElem *pB;
  SparseMatrixElem *pC;
  char ch;
  char *filename_A = "SparseMatrix_A.txt";
  char *filename_B = "SparseMatrix_B.txt";
  /************************************************
    
                       初始化
  *************************************************/
  // C 语言中，数组的首地址即为指针 ...
  pA = A;
  pB = B;
  pC = C;
  /************************************************
    
                输入稀疏矩阵数据
  *************************************************/
  // 显示菜单 ...
  printf("**********************************n");
  printf("!         Menu Selection         !n");
  printf("!                                !n");
  printf("! 1) Input from file             !n");
  printf("! 2) Input from keyboard         !n");
  printf("! 0) Exit                        !n");
  printf("!                                !n");
  printf("**********************************n");
  printf("Your choice[1/2/0] : ");
  do
  {
    ch = getchar();
  }
  while ( (ch != '0') && (ch != '1') && (ch != '2') );
  switch (ch)
  {
    case '1' : // 从文件输入稀疏矩阵数据
      // 输入 A 矩阵数据 ...
      printf("Loading from data file for matrix A : n");
      if (!GetSparseMatrixData(pA, filename_A))
      {
        return; 
	  }
      printf("Matrix A is : n");
      DisplaySparseMatrix(pA);
      
      printf("n");
      
      // 输入 B 矩阵数据 ...
	  printf("Loading from data file for matrix B : n");
      if (!GetSparseMatrixData(pB, filename_B))
	  {
        return;
	  }
      printf("Matrix B is : n");
      DisplaySparseMatrix(pB);
      
	  break;
    case '2' : // 从键盘输入稀疏矩阵数据
      // 输入 A 矩阵数据 ...
      printf("Input data for matrix A : n");
      GetSparseMatrixData(pA);
      printf("Matrix A is : n");
      DisplaySparseMatrix(pA);
  
      printf("n");
      // 输入 B 矩阵数据 ...
      printf("Input data for matrix B : n");
      GetSparseMatrixData(pB);
      printf("Matrix B is : n");
      DisplaySparseMatrix(pB);
	  break;
    case '0' : // 退出
      return;
	  
	  break;
    default :
      return;
	  
	  break;
  } 
  /************************************************
    
                      稀疏矩阵运算
  *************************************************/
  // 加法 ...
  printf("n");
  printf("Matrix [ADDITION] operation : n");
  printf("[C = A + B] ==> Matrix C is : n");
  AddSparseMatrix(pA, pB, pC);
  DisplaySparseMatrix(pC);
  // 减法 ...
  printf("n");
  printf("Matrix [SUBTRACTION] operation : n");
  printf("[C = A - B] ==> Matrix C is : n");
  SubtractSparseMatrix(pA, pB, pC);
  DisplaySparseMatrix(pC);
  
  // 乘法 ...
  printf("n");
  printf("Matrix [MULTIPLICATION] operation : n");
  printf("[C = A x B] ==> Matrix C is : n");
  MultipleSparseMatrix(pA, pB, pC);
  DisplaySparseMatrix(pC);
  // 转置 ...
  printf("n");
  printf("Matrix [TRANSPOSE] operation : n");
  printf("[C = A'] ==> Matrix C is : n");
  TransposeSparseMatrix(pA, pC);
  DisplaySparseMatrix(pC);
}

						