维基百科，自由的百科全书
当二维数组A[m][n]有k个非零元素，若k<<m*n，则称A为稀疏矩阵。存储时只放非零元素，常用的存储方式有顺序存储和链接存储。顺序存储方法包括三元组顺序表表示法和伪地址表示法。链接存储包括带行指针微量的单链表（行逻辑链接的顺序表）表示法（行逻辑链接的顺序表）和十字链表方法。
[编辑] 三元组行逻辑链接顺序存储表示
[编辑] 存储结构
/* 稀疏矩阵的三元组行逻辑链接的顺序表存储表示 */
#define MAX_SIZE 100 /* 非零元个数的最大值 */
#define MAX_RC 20 /* 最大行列数 */
typedef struct
{
int i,j; /* 行下标,列下标 */
ElemType e; /* 非零元素值 */
}Triple; /* 同c5-2.h */
typedef struct
{
Triple data[MAX_SIZE+1]; /* 非零元三元组表，data[0]未用 */
int rpos[MAX_RC+1]; /* 各行第一个非零元素的位置表，比c5-2.h增加的项 */
int mu,nu,tu; /* 矩阵的行数、列数和非零元个数 */
}RLSMatrix;
[编辑] 基本操作
/* 行逻辑链接稀疏矩阵的基本操作(8个) */
Status CreateSMatrix(RLSMatrix *M)
{ /* 创建稀疏矩阵M */
int i,j;
Triple T;
Status k;
printf("请输入矩阵的行数,列数,非零元素数：");
scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);
if((*M).tu>MAX_SIZE||(*M).mu>MAX_RC)
return ERROR;
(*M).data[0].i=0; /* 为以下比较做准备 */
for(i=1;i<=(*M).tu;i++)
{
do
{
printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值:",i,(*M).mu,(*M).nu);
scanf("%d,%d,%d",&T.i,&T.j,&T.e);
k=0;
if(T.i<1||T.i>(*M).mu||T.j<1||T.j>(*M).nu) /* 行、列超出范围 */
k=1;
if(T.i<(*M).data[i-1].i||T.i==(*M).data[i-1].i&&T.j<=(*M).data[i-1].j) /* 没有按顺序输入非零元素 */
k=1;
}while(k); /* 当输入有误，重新输入 */
(*M).data[i]=T;
}
for(i=1;i<=(*M).mu;i++) /* 给rpos[]赋初值0 */
(*M).rpos[i]=0;
for(i=1;i<=(*M).tu;i++) /* 计算每行非零元素数并赋给rpos[] */
(*M).rpos[(*M).data[i].i]++;
for(i=(*M).mu;i>=1;i--) /* 计算rpos[] */
{
(*M).rpos[i]=1; /* 赋初值1 */
for(j=i-1;j>=1;j--)
(*M).rpos[i]+=(*M).rpos[j];
}
return OK;
}
void DestroySMatrix(RLSMatrix *M)
{ /* 销毁稀疏矩阵M(使M为0行0列0个非零元素的矩阵) */
(*M).mu=(*M).nu=(*M).tu=0;
}
void PrintSMatrix(RLSMatrix M)
{ /* 输出稀疏矩阵M */
int i;
printf("%d行%d列%d个非零元素。\n",M.mu,M.nu,M.tu);
printf("行 列 元素值\n");
for(i=1;i<=M.tu;i++)
printf("%2d%4d%8d\n",M.data[i].i,M.data[i].j,M.data[i].e);
for(i=1;i<=M.mu;i++)
printf("第%d行的第一个非零元素是本矩阵第%d个元素\n",i,M.rpos[i]);
}
void PrintSMatrix1(RLSMatrix M)
{ /* 按矩阵形式输出M */
int i,j,k=1;
Triple *p=M.data;
p++; /* p指向第1个非零元素 */
for(i=1;i<=M.mu;i++)
{
for(j=1;j<=M.nu;j++)
if(k<=M.tu&&p->i==i&&p->j==j) /* p指向非零元，且p所指元素为当前处理元素 */
{
printf("%3d",p->e); /* 输出p所指元素的值 */
p++; /* p指向下一个元素 */
k++; /* 计数器+1 */
}
else /* p所指元素不是当前处理元素 */
printf("%3d",0); /* 输出0 */
printf("\n");
}
}
void CopySMatrix(RLSMatrix M,RLSMatrix *T)
{ /* 由稀疏矩阵M复制得到T */
*T=M;
}
Status AddSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{ /* 求稀疏矩阵的和Q=M+N */
int k,p,q,tm,tn;
if(M.mu!=N.mu||M.nu!=N.nu)
return ERROR;
(*Q).mu=M.mu; /* Q矩阵行数 */
(*Q).nu=M.nu; /* Q矩阵列数 */
(*Q).tu=0; /* Q矩阵非零元素数初值 */
for(k=1;k<=M.mu;++k) /* 对于每一行，k指示行号 */
{
(*Q).rpos[k]=(*Q).tu+1; /* Q矩阵第k行的第1个元素的位置 */
p=M.rpos[k]; /* p指示M矩阵第k行当前元素的序号 */
q=N.rpos[k]; /* q指示N矩阵第k行当前元素的序号 */
if(k==M.mu) /* 是最后一行 */
{
tm=M.tu+1; /* tm，tn分别是p，q的上界 */
tn=N.tu+1;
}
else
{
tm=M.rpos[k+1];
tn=N.rpos[k+1];
}
while(p<tm&&q<tn) /* M，N矩阵均有第k行元素未处理 */
if(M.data[p].j==N.data[q].j) /* M矩阵当前元素的列=N矩阵当前元素的列 */
{
if(M.data[p].e+N.data[q].e!=0) /* 和不为0，存入Q */
{
(*Q).data[++(*Q).tu]=M.data[p];
(*Q).data[(*Q).tu].e+=N.data[q].e;
}
p++;
q++;
}
else if(M.data[p].j<N.data[q].j) /* M矩阵当前元素的列<N矩阵当前元素的列 */
(*Q).data[++(*Q).tu]=M.data[p++]; /* 将M的当前值赋给Q */
else /* M矩阵当前元素的列>N矩阵当前元素的列 */
(*Q).data[++(*Q).tu]=N.data[q++]; /* 将N的当前值赋给Q */
while(p<tm) /* M矩阵还有第k行的元素未处理 */
(*Q).data[++(*Q).tu]=M.data[p++]; /* 将M的当前值赋给Q */
while(q<tn) /* N矩阵还有k行的元素未处理 */
(*Q).data[++(*Q).tu]=N.data[q++]; /* 将N的当前值赋给Q */
}
if((*Q).tu>MAX_SIZE)
return ERROR;
else
return OK;
}
Status SubtSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{ /* 求稀疏矩阵的差Q=M-N */
int i;
if(M.mu!=N.mu||M.nu!=N.nu)
return ERROR;
for(i=1;i<=N.tu;++i) /* 对于N的每一元素，其值乘以-1 */
N.data[i].e*=-1;
AddSMatrix(M,N,Q); /* Q=M+(-N) */
return OK;
}
Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)
{ /* 求稀疏矩阵乘积Q=M×N。算法5.3改 */
int arow,brow,p,q,ccol,ctemp[MAX_RC+1],t,tp;
if(M.nu!=N.mu) /* 矩阵M的列数应和矩阵N的行数相等 */
return ERROR;
(*Q).mu=M.mu; /* Q初始化 */
(*Q).nu=N.nu;
(*Q).tu=0;
if(M.tu*N.tu==0) /* M和N至少有一个是零矩阵 */
return ERROR;
for(arow=1;arow<=M.mu;++arow)
{ /* 从M的第一行开始，到最后一行，arow是M的当前行 */
for(ccol=1;ccol<=(*Q).nu;++ccol)
ctemp[ccol]=0; /* Q的当前行的各列元素累加器清零 */
(*Q).rpos[arow]=(*Q).tu+1; /* Q当前行的第1个元素位于上1行最后1个元素之后 */
if(arow<M.mu)
tp=M.rpos[arow+1];
else
tp=M.tu+1; /* 给最后1行设界 */
for(p=M.rpos[arow];p<tp;++p)
{ /* 对M当前行中每一个非零元 */
brow=M.data[p].j; /* 找到对应元在N中的行号(M当前元的列号) */
if(brow<N.mu)
t=N.rpos[brow+1];
else
t=N.tu+1; /* 给最后1行设界 */
for(q=N.rpos[brow];q<t;++q)
{
ccol=N.data[q].j; /* 乘积元素在Q中列号 */
ctemp[ccol]+=M.data[p].e*N.data[q].e;
}
} /* 求得Q中第arow行的非零元 */
for(ccol=1;ccol<=(*Q).nu;++ccol) /* 压缩存储该行非零元 */
if(ctemp[ccol]!=0)
{
if(++(*Q).tu>MAX_SIZE)
return ERROR;
(*Q).data[(*Q).tu].i=arow;
(*Q).data[(*Q).tu].j=ccol;
(*Q).data[(*Q).tu].e=ctemp[ccol];
}
}
return OK;
}
void TransposeSMatrix(RLSMatrix M,RLSMatrix *T)
{ /* 求稀疏矩阵M的转置矩阵T */
int p,q,t,col,*num;
num=(int *)malloc((M.nu+1)*sizeof(int));
(*T).mu=M.nu;
(*T).nu=M.mu;
(*T).tu=M.tu;
if((*T).tu)
{
for(col=1;col<=M.nu;++col)
num[col]=0; /* 设初值 */
for(t=1;t<=M.tu;++t) /* 求M中每一列非零元个数 */
++num[M.data[t].j];
(*T).rpos[1]=1;
for(col=2;col<=M.nu;++col) /* 求M中第col中第一个非零元在T.data中的序号 */
(*T).rpos[col]=(*T).rpos[col-1]+num[col-1];
for(col=1;col<=M.nu;++col)
num[col]=(*T).rpos[col];
for(p=1;p<=M.tu;++p)
{
col=M.data[p].j;
q=num[col];
(*T).data[q].i=M.data[p].j;
(*T).data[q].j=M.data[p].i;
(*T).data[q].e=M.data[p].e;
++num[col];
}
}
free(num);
}
[编辑] 十字链表存储表示
[编辑] 存储结构
/* 稀疏矩阵的十字链表存储表示 */
typedef struct OLNode
{
int i,j; /* 该非零元的行和列下标 */
ElemType e; /* 非零元素值 */
struct OLNode *right,*down; /* 该非零元所在行表和列表的后继链域 */
}OLNode,*OLink;
typedef struct
{
OLink *rhead,*chead; /* 行和列链表头指针向量基址，由CreatSMatrix_OL()分配 */
int mu,nu,tu; /* 稀疏矩阵的行数、列数和非零元个数 */
}CrossList;
[编辑] 基本操作
/* 稀疏矩阵的十字链表存储的基本操作(9个)*/
void InitSMatrix(CrossList *M)
{ /* 初始化M(CrossList类型的变量必须初始化，否则创建、复制矩阵将出错)。加 */
(*M).rhead=(*M).chead=NULL;
(*M).mu=(*M).nu=(*M).tu=0;
}
void InitSMatrixList(CrossList *M)
{ /* 初始化十字链表表头指针向量。加 */
int i;
(*M).rhead=(OLink*)malloc(((*M).mu+1)*sizeof(OLink)); /* 生成行表头指针向量 */
if(!(*M).rhead)
exit(OVERFLOW);
(*M).chead=(OLink*)malloc(((*M).nu+1)*sizeof(OLink)); /* 生成列表头指针向量 */
if(!(*M).chead)
exit(OVERFLOW);
for(i=1;i<=(*M).mu;i++) /* 初始化矩阵T的行表头指针向量，各行链表为空 */
(*M).rhead[i]=NULL;
for(i=1;i<=(*M).nu;i++) /* 初始化矩阵T的列表头指针向量，各列链表为空 */
(*M).chead[i]=NULL;
}
void InsertAscend(CrossList *M,OLink p)
{ /* 初始条件：稀疏矩阵M存在,p指向的结点存在。操作结果：按行列升序将p所指结点插入M */
OLink q=(*M).rhead[p->i]; /* q指向待插行表 */
if(!q||p->j<q->j) /* 待插的行表空或p所指结点的列值小于首结点的列值 */
{
p->right=(*M).rhead[p->i]; /* 插在表头 */
(*M).rhead[p->i]=p;
}
else
{
while(q->right&&q->right->j<p->j) /* q所指不是尾结点且q的下一结点的列值小于p所指结点的列值 */
q=q->right; /* q向后移 */
p->right=q->right; /* 将p插在q所指结点之后 */
q->right=p;
}
q=(*M).chead[p->j]; /* q指向待插列表 */
if(!q||p->i<q->i) /* 待插的列表空或p所指结点的行值小于首结点的行值 */
{
p->down=(*M).chead[p->j]; /* 插在表头 */
(*M).chead[p->j]=p;
}
else
{
while(q->down&&q->down->i<p->i) /* q所指不是尾结点且q的下一结点的行值小于p所指结点的行值 */
q=q->down; /* q向下移 */
p->down=q->down; /* 将p插在q所指结点之下 */
q->down=p;
}
(*M).tu++;
}
void DestroySMatrix(CrossList *M)
{ /* 初始条件：稀疏矩阵M存在。操作结果：销毁稀疏矩阵M */
int i;
OLink p,q;
for(i=1;i<=(*M).mu;i++) /* 按行释放结点 */
{
p=*((*M).rhead+i);
while(p)
{
q=p;
p=p->right;
free(q);
}
}
free((*M).rhead);
free((*M).chead);
InitSMatrix(M);
}
void CreateSMatrix(CrossList *M)
{ /* 创建稀疏矩阵M，采用十字链表存储表示。算法5.4改 */
int i,k;
OLink p;
if((*M).rhead)
DestroySMatrix(M);
printf("请输入稀疏矩阵的行数 列数 非零元个数: ");
scanf("%d%d%d",&(*M).mu,&(*M).nu,&i);
InitSMatrixList(M); /* 初始化M的表头指针向量 */
printf("请按任意次序输入%d个非零元的行 列 元素值:\n",(*M).tu);
for(k=0;ki,&p->j,&p->e); /* 给结点的3个成员赋值 */
InsertAscend(M,p); /* 将结点p按行列值升序插到矩阵M中 */
}
}
void PrintSMatrix(CrossList M)
{ /* 初始条件：稀疏矩阵M存在。操作结果：按行或按列输出稀疏矩阵M */
int i,j;
OLink p;
printf("%d行%d列%d个非零元素\n",M.mu,M.nu,M.tu);
printf("请输入选择(1.按行输出 2.按列输出): ");
scanf("%d",&i);
switch(i)
{
case 1: for(j=1;j<=M.mu;j++)
{
p=M.rhead[j];
while(p)
{
printf("%d行%d列值为%d\n",p->i,p->j,p->e);
p=p->right;
}
}
break;
case 2: for(j=1;j<=M.nu;j++)
{
p=M.chead[j];
while(p)
{
printf("%d行%d列值为%d\n",p->i,p->j,p->e);
p=p->down;
}
}
}
}
void PrintSMatrix1(CrossList M)
{ /* 按矩阵形式输出M */
int i,j;
OLink p;
for(i=1;i<=M.mu;i++)
{ /* 从第1行到最后1行 */
p=M.rhead[i]; /* p指向该行的第1个非零元素 */
for(j=1;j<=M.nu;j++) /* 从第1列到最后1列 */
if(!p||p->j!=j) /* 已到该行表尾或当前结点的列值不等于当前列值 */
printf("%-3d",0); /* 输出0 */
else
{
printf("%-3d",p->e);
p=p->right;
}
printf("\n");
}
}
void CopySMatrix(CrossList M,CrossList *T)
{ /* 初始条件：稀疏矩阵M存在。操作结果：由稀疏矩阵M复制得到T */
int i;
OLink p,q;
if((*T).rhead) /* 矩阵T存在 */
DestroySMatrix(T);
(*T).mu=M.mu;
(*T).nu=M.nu;
InitSMatrixList(T); /* 初始化T的表头指针向量 */
for(i=1;i<=M.mu;i++) /* 按行复制 */
{
p=M.rhead[i]; /* p指向i行链表头 */
while(p) /* 没到行尾 */
{
q=(OLNode*)malloc(sizeof(OLNode)); /* 生成结点q */
if(!q)
exit(OVERFLOW);
*q=*p; /* 给结点q赋值 */
InsertAscend(T,q); /* 将结点q按行列值升序插到矩阵T中 */
p=p->right;
}
}
}
int comp(int c1,int c2)
{ /* AddSMatrix函数要用到，另加 */
if(c1<c2)
return -1;
if(c1==c2)
return 0;
return 1;
}
void AddSMatrix(CrossList M,CrossList N,CrossList *Q)
{ /* 初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的和Q=M+N */
int i;
OLink pq,pm,pn;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("两个矩阵不是同类型的,不能相加\n");
exit(OVERFLOW);
}
(*Q).mu=M.mu; /* 初始化Q矩阵 */
(*Q).nu=M.nu;
(*Q).tu=0; /* Q矩阵元素个数的初值为0 */
InitSMatrixList(Q); /* 初始化Q的表头指针向量 */
for(i=1;i<=M.mu;i++) /* 按行的顺序相加 */
{
pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */
pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */
while(pm&&pn) /* pm和pn均不空 */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
switch(comp(pm->j,pn->j))
{
case -1: *pq=*pm; /* M的列<N的列，将矩阵M的当前元素值赋给pq */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pm=pm->right; /* 指针向后移 */
break;
case 0: *pq=*pm; /* M、N矩阵的列相等，元素值相加 */
pq->e+=pn->e;
if(pq->e!=0) /* 和为非零元素 */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
else
free(pq); /* 释放结点 */
pm=pm->right; /* 指针向后移 */
pn=pn->right;
break;
case 1: *pq=*pn; /* M的列>N的列，将矩阵N的当前元素值赋给pq */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pn=pn->right; /* 指针向后移 */
}
}
while(pm) /* pn=NULL */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
*pq=*pm; /* M的列<N的列，将矩阵M的当前元素值赋给pq */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pm=pm->right; /* 指针向后移 */
}
while(pn) /* pm=NULL */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
*pq=*pn; /* M的列>N的列，将矩阵N的当前元素值赋给pq */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pn=pn->right; /* 指针向后移 */
}
}
if((*Q).tu==0) /* Q矩阵元素个数为0 */
DestroySMatrix(Q); /* 销毁矩阵Q */
}
void SubtSMatrix(CrossList M,CrossList N,CrossList *Q)
{ /* 初始条件：稀疏矩阵M与N的行数和列数对应相等。操作结果：求稀疏矩阵的差Q=M-N */
int i;
OLink pq,pm,pn;
if(M.mu!=N.mu||M.nu!=N.nu)
{
printf("两个矩阵不是同类型的,不能相减\n");
exit(OVERFLOW);
}
(*Q).mu=M.mu; /* 初始化Q矩阵 */
(*Q).nu=M.nu;
(*Q).tu=0; /* Q矩阵元素个数的初值为0 */
InitSMatrixList(Q); /* 初始化Q的表头指针向量 */
for(i=1;i<=M.mu;i++) /* 按行的顺序相减 */
{
pm=M.rhead[i]; /* pm指向矩阵M的第i行的第1个结点 */
pn=N.rhead[i]; /* pn指向矩阵N的第i行的第1个结点 */
while(pm&&pn) /* pm和pn均不空 */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
switch(comp(pm->j,pn->j))
{
case -1: *pq=*pm; /* M的列<N的列，将矩阵M的当前元素值赋给pq */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pm=pm->right; /* 指针向后移 */
break;
case 0: *pq=*pm; /* M、N矩阵的列相等，元素值相减 */
pq->e-=pn->e;
if(pq->e!=0) /* 差为非零元素 */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
else
free(pq); /* 释放结点 */
pm=pm->right; /* 指针向后移 */
pn=pn->right;
break;
case 1: *pq=*pn; /* M的列>N的列，将矩阵N的当前元素值赋给pq */
pq->e*=-1; /* 求反 */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pn=pn->right; /* 指针向后移 */
}
}
while(pm) /* pn=NULL */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
*pq=*pm; /* M的列<N的列，将矩阵M的当前元素值赋给pq */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pm=pm->right; /* 指针向后移 */
}
while(pn) /* pm=NULL */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成矩阵Q的结点 */
*pq=*pn; /* M的列>N的列，将矩阵N的当前元素值赋给pq */
pq->e*=-1; /* 求反 */
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
pn=pn->right; /* 指针向后移 */
}
}
if((*Q).tu==0) /* Q矩阵元素个数为0 */
DestroySMatrix(Q); /* 销毁矩阵Q */
}
void MultSMatrix(CrossList M,CrossList N,CrossList *Q)
{ /* 初始条件：稀疏矩阵M的列数等于N的行数。操作结果：求稀疏矩阵乘积Q=M×N */
int i,j,e;
OLink pq,pm,pn;
InitSMatrix(Q);
(*Q).mu=M.mu;
(*Q).nu=N.nu;
(*Q).tu=0;
InitSMatrixList(Q); /* 初始化Q的表头指针向量 */
for(i=1;i<=(*Q).mu;i++)
for(j=1;j<=(*Q).nu;j++)
{
pm=M.rhead[i];
pn=N.chead[j];
e=0;
while(pm&&pn)
switch(comp(pn->i,pm->j))
{
case -1: pn=pn->down; /* 列指针后移 */
break;
case 0: e+=pm->e*pn->e; /* 乘积累加 */
pn=pn->down; /* 行列指针均后移 */
pm=pm->right;
break;
case 1: pm=pm->right; /* 行指针后移 */
}
if(e) /* 值不为0 */
{
pq=(OLink)malloc(sizeof(OLNode)); /* 生成结点 */
if(!pq) /* 生成结点失败 */
exit(OVERFLOW);
pq->i=i; /* 给结点赋值 */
pq->j=j;
pq->e=e;
InsertAscend(Q,pq); /* 将结点pq按行列值升序插到矩阵Q中 */
}
}
if((*Q).tu==0) /* Q矩阵元素个数为0 */
DestroySMatrix(Q); /* 销毁矩阵Q */
}
void TransposeSMatrix(CrossList M,CrossList *T)
{ /* 初始条件：稀疏矩阵M存在。操作结果：求稀疏矩阵M的转置矩阵T */
int u,i;
OLink *head,p,q,r;
CopySMatrix(M,T); /* T=M */
u=(*T).mu; /* 交换T.mu和T.nu */
(*T).mu=(*T).nu;
(*T).nu=u;
head=(*T).rhead; /* 交换T.rhead和T.chead */
(*T).rhead=(*T).chead;
(*T).chead=head;
for(u=1;u<=(*T).mu;u++) /* 对T的每一行 */
{
p=(*T).rhead[u]; /* p为行表头 */
while(p) /* 没到表尾，对T的每一结点 */
{
q=p->down; /* q指向下一个结点 */
i=p->i; /* 交换.i和.j */
p->i=p->j;
p->j=i;
r=p->down; /* 交换.down和.right */
p->down=p->right;
p->right=r;
p=q; /* p指向下一个结点 */
}
}
}
