题目
给定稀疏矩阵A(int型),然后创建其三元组存储结构B,查找给定元素x是否在矩阵中。
分析
三元组存储结构是一 种顺序结构,因此也是一 种顺序表,表中的每个结点对应稀疏矩阵的一个非零元素,其中包括3个字段,分别为该元素的值、行下标和列下标。另外,用第0行的第1个元素存储矩阵中非零元素的个数,第0行的第2个元素存储矩阵的行数,第0行的第3个元素存储矩阵的列数。
代码
根据给定稀疏矩阵创建三元组存储结构的代码如下:
/* 根据给定的稀疏矩阵A(int型)创建三元组存储结构 */
/* A[][MAXSIZE]指的是稀疏矩阵;m指的是稀疏矩阵的行数;n指的是稀疏矩阵的列数;trimat[][3]指的是三元组 */
void createTrimat(int A[][MAXSIZE],int m,int n,int trimat[][3]) {
int k=1;// 计数器,记录三元组的行下标,从1开始,0存储稀疏矩阵的基本信息
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){// 双层嵌套循环,遍历稀疏矩阵的所有元素
if(A[i][j]!=0){
trimat[k][0]=A[i][j];// trimat[k][0]存储稀疏矩阵中非零元素的值
trimat[k][1]=i;// trimat[k][1]存储稀疏矩阵中非零元素的行下标
trimat[k][2]=j;// trimat[k][2]存储稀疏矩阵中非零元素的列下标
k++;// 计数器加1
}
}
}
/* 存储一些稀疏矩阵的基本信息 */
trimat[0][0]=k-1;// 保存矩阵中非零元素的个数
trimat[0][1]=m;// 保存矩阵的行数
trimat[0][2]=n;// 保存矩阵的列数
}
查找给定的元素x是否在矩阵中的代码如下:
/* 查找给定元素x是否在矩阵中 */
/* trimat[][3]指的是三元组;x指的是要查找的指定元素 */
int search(int trimat[][3],int x) {
for(int k=1;k<=trimat[0][0];k++){
if(trimat[k][0]==x){
return 1;
}
}
return 0;
}
完整代码如下:
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
/* 题目:给定稀疏矩阵A,创建其三元组存储结构B,查找给定元素x是否在其中 */
/* 根据给定的稀疏矩阵A(int型)创建三元组存储结构 */
/* A[][MAXSIZE]指的是稀疏矩阵;m指的是稀疏矩阵的行数;n指的是稀疏矩阵的列数;trimat[][3]指的是三元组 */
void createTrimat(int A[][MAXSIZE],int m,int n,int trimat[][3]) {
int k=1;// 计数器,记录三元组的行下标,从1开始,0存储稀疏矩阵的基本信息
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){// 双层嵌套循环,遍历稀疏矩阵的所有元素
if(A[i][j]!=0){
trimat[k][0]=A[i][j];// trimat[k][0]存储稀疏矩阵中非零元素的值
trimat[k][1]=i;// trimat[k][1]存储稀疏矩阵中非零元素的行下标
trimat[k][2]=j;// trimat[k][2]存储稀疏矩阵中非零元素的列下标
k++;// 计数器加1
}
}
}
/* 存储一些稀疏矩阵的基本信息 */
trimat[0][0]=k-1;// 保存矩阵中非零元素的个数
trimat[0][1]=m;// 保存矩阵的行数
trimat[0][2]=n;// 保存矩阵的列数
}
/* 查找给定元素x是否在矩阵中 */
/* trimat[][3]指的是三元组;x指的是要查找的指定元素 */
int search(int trimat[][3],int x) {
for(int k=1;k<=trimat[0][0];k++){
if(trimat[k][0]==x){
return 1;
}
}
return 0;
}
/* 打印矩阵 */
/* A[][MAXSIZE]指的是稀疏矩阵;m指的是稀疏矩阵的行数;n指的是稀疏矩阵的列数 */
void printMat(int A[][MAXSIZE],int m,int n){
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
printf("%d\t",A[i][j]);
}
printf("\n");
}
}
/* 根据三元组打印出原来的稀疏矩阵 */
/* trimat[][3]指的是三元组 */
void printTrimat(int trimat[][3]) {
int m=trimat[0][1];// 稀疏矩阵的行数
int n=trimat[0][2];// 稀疏矩阵的列数
int k=1;// 三元组数组的下标,初始为1,因为trimat[0][0-2]保存的是三元组的一些基本信息
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) { // 双层循环遍历稀疏矩阵
if(i==trimat[k][1]&&j==trimat[k][2]) { // 如果i和j能够匹配三元组的下标trimat[k][1]和trimat[k][2]
printf("%d\t",trimat[k][0]);// 如果能够配对则输出三元组的非零元素的值
k++;// 继续遍历三元组的元素
} else {
printf("0\t");// 如果没有匹配则代表该处位置是0
}
}
printf("\n");// 换行
}
}
/* 打印三元组 */
void print(int trimat[][3]){
printf("\n");
for(int k=1;k<=trimat[0][0];k++){
printf("%d\t",trimat[k][0]);
}
printf("\n");
}
int main() {
// 稀疏矩阵
int A[][MAXSIZE]= {
{0,0,0,1},
{0,0,3,2},
{1,0,0,0},
{0,2,0,0},
{1,0,0,0}
};
int m=5,n=4;// 指的是稀疏矩阵的行数和列数
printf("稀疏矩阵:\n");
printMat(A,m,n);// 打印稀疏矩阵
int trimat[MAXSIZE][3];
createTrimat(A,m,n,trimat);// 根据稀疏矩阵创建三元组
printf("三元组所打印的稀疏矩阵:\n");
printTrimat(trimat);// 根据三元组打印原矩阵
printf("三元组:\n");
print(trimat);// 打印三元组
int i=search(trimat,3);// 查找3是否在稀疏矩阵中
printf("查找结果:\n");
printf("%d",i);// 打印结果,如果在返回1,否则返回0
return 0;
}
运行结果如下: