三元组顺序表的存储结构形成

三元组顺序表的存储结构形成
数据结构问题用C语言编译

/*~~~~稀疏矩阵的三元组顺序表存储结构类型定义及部分常见操作算法（smatrix.c）~~~~*/
#ifndef __SPARSEMATRIX__
#define __SPARSEMATRIX__
#ifndef COMMONELEM
#define COMMONELEM 0 /*公共元的值*/
#endif
#include
/*三元组顺序表存储空间长度的最小值*/
#define MATRIXMINSIZE 10
/*三元组顺序表存储结构类型定义*/
typedef struct
{
int row; /*行号*/
int col; /*列号*/
MatrixDT value; /*特殊元的值*/
}ThrElem; /*三元组元素类型*/
typedef struct
{
ThrElem *base; /*三元组表的基地址*/
int listsize; /*三元组表的存储空间尺寸*/
int len; /*三元组表的长度,即矩阵中特殊元的个数*/
int rows,cols; /*矩阵的行数、列数*/
}SMatrix;
/*矩阵初始化*/
void MatrixInitialize(SMatrix *pM, int size, int rows, int cols)
{
if(sizelistsize = size;
pM->base=(ThrElem *)malloc(pM->listsize*sizeof(ThrElem));
if(!pM->base)
exit(EXIT_FAILURE);
pM->rows=rows;
pM->cols=cols;
pM->len=0;
}
/*输出矩阵*/
void MatrixPrint(SMatrix M, void (*cout)(MatrixDT))
{
int i,j,k;
for(k=0,i=0; ilistsize)
flg=FALSE;/*访问越界*/
else
{
addr=i*pM->cols +j;
/*扫描到i行中j列元素应在的位置*/
for(k=0;klen &&
pM->base[k].row* pM->cols +pM->base[k].colbase[k].row && j==pM->base[k].col)
{
/*原来是特殊元*/
if((*equal)(d,COMMONELEM))
{
/*第1种情况：原来是特殊元,写入的是公共元值.从表中删除元素*/
for(m=k+1; mlen; m++)
pM->base[m-1]=pM->base[m];
pM->len--;
}
else
/*第2种情况：原来是特殊元,写入的是特殊元值,更改元素值*/
pM->base[k].value=d;
}
else /*原来是公共元*/
{
if(!(*equal)(d,COMMONELEM))
{
/*第3种情况：原来是公共元,写入的是特殊元值.在表中k位置插入新元素*/
for(m=pM->len-1; m>=k; m--)
pM->base[m+1]=pM->base[m];
pM->base[k].row=i;
pM->base[k].col=j;
pM->base[k].value =d;
pM->len++;
}
else
/*第4种情况：原来是公共元,写入的是公共元值.空操作*/
;
}
}
return flg;
}
/*拷贝矩阵*/
void MatrixCopy(SMatrix* pM, SMatrix M)
{
int i;
pM->listsize = M.listsize;
pM->rows = M.rows;
pM->cols = M.cols;
pM->len = M.len;
/*申请存储空间*/
pM->base=(ThrElem *)malloc(pM->listsize*sizeof(ThrElem));
if(!pM->base)
exit(EXIT_FAILURE);
for(i=0; ilen; i++)
pM->base[i]=M.base[i];/*复制数组中单元的值*/
}
/*矩阵加法*/
BOOL MatrixAdd(SMatrix* pM, SMatrix M, SMatrix N,
MatrixDT (*add)(MatrixDT,MatrixDT),BOOL (*equal)(MatrixDT,MatrixDT))
{
int i,j,k,addrM,addrN;
/*pM所指矩阵有可能是矩阵M或矩阵N,故先用base缓存结果,最后再给pM->base*/
ThrElem *base;
MatrixDT d;
BOOL flg=TRUE;
if(M.rows !=N.rows || M.cols!=N.cols)
flg=FALSE;
else
{
base=(ThrElem*)malloc((M.len + N.len)*sizeof(ThrElem));
if(!base)
exit(EXIT_FAILURE);
/*i、j和k分别指示M.base、N.base和临时数据区base的首位置*/
i=j=k=0;
while(irows=M.rows;
pM->cols=M.cols;
pM->len =k;
}
return flg;
}
/*矩阵转置*/
void MatrixTranspose(SMatrix *pM, SMatrix M)
{
int col,i,j;
ThrElem *base;
/*
本函数允许如下调用方式：
MatrixTranspose(&m, m);
所以要额外申请存储空间base
*/
base=(ThrElem*)malloc(M.listsize*sizeof(ThrElem));
if(!base)
exit(EXIT_FAILURE);
for(i=0,col=0; collen =M.len;
pM->rows=M.cols;
pM->cols=M.rows;
free(pM->base);
pM->base=base;
}
/*销毁矩阵*/
void MatrixDestroy(SMatrix M)
{
free(M.base);
}
#endif
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
/*
建议性测试用程序
*/
typedef enum {TRUE=1,FALSE=0} BOOL;
typedef int MatrixDT;
#include "smatrix.c"
#define inFORMAT "%d"
#define outFORMAT "%3d"
void printdata(MatrixDT x)
{
printf(outFORMAT,x);
}
MatrixDT add(MatrixDT x, MatrixDT y)
{
return x+y;
}
BOOL equal(MatrixDT x, MatrixDT y)
{
return x==y ? TRUE: FALSE;
}
void main()
{
int i,j,x, y, tlimit;
MatrixDT d;
SMatrix M,N;
BOOL valid=TRUE;
printf("请输入矩阵M的行数、列数及特殊元个数的上限值：\n");
scanf("%d%d%d",&x,&y, &tlimit);
MatrixInitialize(&M,tlimit, x, y);
while(valid)
{
printf("请输入特殊元的行号、列号(行号或列号无效时结束)：\n");
scanf("%d%d",&x, &y);
printf("请输入特殊元的值\n");
scanf(inFORMAT, &d);
valid=PutElem(&M,d,x,y,equal);
}
printf("原矩阵=\n");
MatrixPrint(M, printdata);
MatrixTranspose(&M,M);
printf("转置后矩阵=\n");
MatrixPrint(M, printdata);
printf("请输入要读取的单元的行号和列号：\n");
scanf("%d%d",&i,&j);
if(GetElem(M,&d,i,j))
{
printf("M[%d][%d]=",i,j);
printf(outFORMAT, d);
printf("\n");
}
else
printf("Invalid.\n");
MatrixPrint(M, printdata);
printf("Copy M to N.\n");
MatrixCopy(&N,M);
if(MatrixAdd(&M,M,N, add, equal))
{
printf("M+N=\n");
MatrixPrint(M, printdata);
}
MatrixDestroy(M);
}