三元十字链存储方法

⑴ 三元组法和十字链表法可以存储普通的数组吗

没听过，新的数据结构吗？数据结构都可以存数组的。

⑵ 稀疏矩阵一般的压缩存储方法有两种

分别是三元组和十字链表。

三元组是指形如（（x，y），z）的集合（这就是说，三元组是这样的偶，其第一个射影亦是一个偶），常简记为（x，y，z）。

三元组是计算机专业的一门公共基础课程——数据结构里的概念。主要是用来存储稀疏矩阵的一种压缩方式，也叫三元组表。假设以顺序存储结构来表示三元组表（triple table），则得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。

十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。

拓展资料：

十字链表（Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧都有一个结点，对应于每个定顶点也有一个结点。

十字链表之于有向图，类似于邻接表之于无向图。

也可以理解为 将行的单链表和列的单链表结合起来存储稀疏矩阵称为十字链表， 每个节点表示一个非零元素。

三元组解释：

1、所谓“三元组”是指图形的几何元素构成、图线间的拓扑关系和尺寸约束。如果一组图形的前二元相同而只是尺寸大小不同，则这组图形构成一族形状相同的系列化图形。

2、把组成一个元素的三个数称为三元组。一个三元组包含以下三部分的内容SDO_STARTING_OFFSET表明每个几何元素的第一个坐标在SDO_ORDINATES数组中的存储位置。

3、…Mt：N2）的表示称为三元组...…Mt称为标号，N1、N2为结点R为关系。当n≠0时，称Li为对结点N1的修饰。t≠0时，称Mj为对结点N2的修饰。

参考资料：网络：十字链表

网络：三元组

⑶ 用十字链表存储结稀疏矩阵，并进行矩阵的转置。 要C的，c++的我看不懂。。。。~

这个吧 功能比你要的还多：http://wenku..com/view/3d744dd950e2524de5187e68.html
建立稀疏矩阵A 的十字链表首先输入的信息是：m（A 的行数），n（A 的列数），r（非零项的数目），紧跟着输入的是r 个形如（i,j,aij）的三元组。

算法的设计思想是：首先建立每行（每列）只有头结点的空链表，并建立起这些头结点拉成的循环链表；然后每输入一个三元组（i，j，aij），则将其结点按其列号的大小插入到第i 个行链表中去，同时也按其行号的大小将该结点插入到第j 个列链表中去。在算法中将利用一个辅助数组MNode *hd[s+1]; 其中s=max(m , n) , hd [i]指向第i 行(第i 列)链表的头结点。这样做可以在建立链表时随机的访问任何一行（列），为建表带来方便。

算法如下：
MLink CreatMLink( ) /* 返回十字链表的头指针*/
｛
MLink H;
Mnode *p,*q,*hd[s+1];
int i,j,m,n,t;
datatype v;
scanf(“%d,%,%d”,&m,&n,&t);
H=malloc(sizeof(MNode)); /*申请总头结点*/
H->row=m; H->col=n;
hd[0]=H;
for(i=1; i<S; i++)
{ p=malloc(sizeof(MNode)); /*申请第i 个头结点*/
p->row=0; p->col=0;
p->right=p; p->down=p;
hd[i]=p;
hd[i-1]->v_next.next=p;
}
hd[S]->v_next.next=H; /*将头结点们形成循环链表*/
for (k=1;k<=t;k++)
{ scanf (“%d,%d,%d”,&i,&j,&v); /*输入一个三元组，设值为int*/
p=malloc(sizeof(MNode));
p->row=i ; p->col=j; p->v_next.v=v
/*以下是将*p 插入到第i 行链表中去，且按列号有序*/
q=hd[i];
while ( q->right!=hd[i] && (q->right->col)<j ) /*按列号找位置*/
q=q->right;
p->right=q->right; /*插入*/
q->right=p;
/*以下是将*p 插入到第j 行链表中去，且按行号有序*/
q=hd[i];
while ( q->down!=hd[j] && (q->down->row)<i ) /*按行号找位置*/
q=q->down;
p-> down =q-> down; /*插入*/
q-> down =p;
} /*for k*/
return H;
} /* CreatMLink */

⑷ 数据结构分别在什么时候应该采用三元组、十字链表来存储矩阵

据我所知有下面几种情况
1.数据结构教材上
2.作业或考试题
3.对于三元组，在不同人交换数据的时候经常采用，因为这个格式最简单

实际存贮稀疏矩阵不用这两种方式，一般用列压缩格式或者行压缩格式，这和三元组一样是标准格式，但是节省存贮量。

⑸ 稀疏矩阵的应用（三元组和十字链法）

十字链表是这样构成的：用链表模拟矩阵的行（或者列，这可以根据个人喜好来定），然后，再构造代表列的链表，将每一行中的元素节点插入到对应的列中去。十字链表的逻辑结构就像是一个围棋盘（没见过，你就想一下苍蝇拍，这个总见过吧），而非零元就好像是在棋盘上放的棋子，总共占的空间就是，确定那些线的表头节点和那些棋子代表的非零元节点。最后，我们用一个指针指向这个棋盘，这个指针就代表了这个稀疏矩阵。
=================
说了一堆还是举个例子吧：
#include <malloc.h>
#include <stdio.h>

/*十字链表的结构类型定义如下：*/
typedef struct OLNode
{
int row,col; /*非零元素的行和列下标*/
ElementType value;
struct OLNode *right; /*非零元素所在行表、列表的后继链域*/
struct OLNode *down;
}OLNode; *OLink;

typedef struct
{
OLink *row_head; /*行、列链表的头指针向量*/
OLink *col_head;
int m,n,len; /*稀疏矩阵的行数、列数、非零元素的个数*/
}CrossList;

/*建立稀疏矩阵的十字链表的算法*/

void CreateCrossList(CrossList *M)
{
/*采用十字链表存储结构，创建稀疏矩阵M*/
scanf(&m,&n,&t); /*输入M的行数,列数和非零元素的个数*/
M->m=m;
M->n=n;
M->len=t;
if(!(M->row_head=(OLink *)malloc((m+1)sizeof(OLink))))
exit(OVERFLOW);
if(!(M->col_head=(OLink * )malloc((n+1)sizeof(OLink))))
exit(OVERFLOW);
M->row_head[ ]=M->col_head[ ]=NULL; /*初始化行、列头指针向量，各行、列链表为空的链表*/
for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e))
{
if(!(p=(OLNode *)malloc(sizeof(OLNode))))
exit(OVERFLOW);
p->row=i;
p->col=j;
p->value=e; /*生成结点*/
if(M->row_head[i]==NULL)
M->row_head[i]=p;
else
{
/*寻找行表中的插入位置*/
for(q=M->row_head[i];q->right&&q->right->col<j;q=q->right); /*空循环体*/
p->right=q->right;
q->right=p; /*完成插入*/
}
if(M->col_head[j]==NULL)
M->col_head[j]=p;
else
{
/*寻找列表中的插入位置*/
for(q=M->col_head[j];q->down&&q->down->row<i;q=q->down); /*空循环体*/
p->down=q->down;
q->down=p; /*完成插入*/
}
}
}

更多相关知识自己去找数据结构的书来看。
编程爱好者群：24410693 只要对c有兴趣就可以申请加入本群.

⑹ 线性表最主要的两个应用是他们之间最重要的区别是

队列和堆栈
队列是先进先出FIFO
堆栈是先进后出FILO

⑺ 十字链表的介绍

十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。

⑻ 画图表示下列稀疏矩阵的三元组和十字链表存储方式。

如图

⑼ 如何用行逻辑链接顺序表及十字链表存储稀疏矩阵

来自 严蔚敏《数据结构》 稀疏矩阵的压缩方法主要有： 1：三元组顺序表 （行下标，列下标，值） 2：行逻辑链接的顺序表。 3：十字链表。

⑽ 稀疏矩阵的加法和乘法c语言（十字链算法）

你没有写具体要求，是用采用三元组作存储结构还是数组，下面是我们以前做过的数据结构习题你参考一下：
能区分加法、减法、乘法和转置；能处理任意输入的典型数据和进行出错数据处理（例如乘法，当第一个矩阵的列数不等于第二个矩阵的行数时）；必须采用三元组作存储结构，不能采用数组等形式；输出要求用矩阵的形式输出（即习题集136页的形式），当第一个矩阵的行数不等于第二个矩阵的行数时，注意如第三个乘法的形式输出

******************************************************************************************

#include<stdio.h>
#define maxsize 100
typedef struct
{
int i,j; //该非零元的行和列
int v; //该非零元的值
}triple;
typedef struct
{
triple data[maxsize]; //非零元三元组表，data[0]未用
int rpos[maxsize];
int m,n,t; //矩阵的行数，列数和非零元个数
}tripletable;

void convert() //矩阵的转置

{
int k;
tripletable A,B;
printf("输入稀疏矩阵A的行数，列数和非零元个数：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
B.m=A.m;B.n=A.n;B.t=A.t;
if(B.t)
{
int q=1,col;
for(col=1;col<=A.n;++col)
for(int p=1;p<=A.t;++p)
if(A.data[p].j==col)
{
B.data[q].i=A.data[p].j;
B.data[q].j=A.data[p].i;
B.data[q].v=A.data[p].v;
++q;
}
}
int shuru[100][100]={0};
for(k=1;k<=B.t;k++)
{
shuru[B.data[k].j][B.data[k].i]=B.data[k].v;
}
printf("输入为：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",shuru[k][l]);
printf("\n");
}
int result[100][100]={0};

for(k=1;k<=B.t;k++)
{
result[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("结果为：\n");
for(k=1;k<=B.n;k++)
{
for(int l=1;l<=B.m;l++)
printf("%d ",result[k][l]);
printf("\n");
}
}

void add() //矩阵的加法
{
int k;
tripletable A,B;
printf("输入稀疏矩阵A的行数，列数和非零元个数：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
printf("输入稀疏矩阵B的行数，列数和非零元个数：");
scanf("%d %d %d",&B.m,&B.n,&B.t);
for(k=1;k<=B.t;k++)
{
printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&B.data[k].i,&B.data[k].j,&B.data[k].v);
}
if(A.m!=B.m||A.n!=B.n)
{
printf("输入错误：A与B的行数或列数不相同，请重新输入\n");
return;
}
int a[100][100]={0};
for(k=1;k<=A.t;k++)
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf("A输入为：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",a[k][l]);
printf("\n");
}

int b[100][100]={0};
for(k=1;k<=B.t;k++)
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("B输入为：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",b[k][l]);
printf("\n");
}
int c[100][100]={0};
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
{
c[k][l]=a[k][l]+b[k][l];
}
}
printf("加法结果C为：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",c[k][l]);
printf("\n");
}
}

void jian() //矩阵的减法
{
int k;
tripletable A,B;
printf("输入稀疏矩阵A的行数，列数和非零元个数：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
printf("输入稀疏矩阵B的行数，列数和非零元个数：");
scanf("%d %d %d",&B.m,&B.n,&B.t);
for(k=1;k<=B.t;k++)
{
printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&B.data[k].i,&B.data[k].j,&B.data[k].v);
}
if(A.m!=B.m||A.n!=B.n)
{
printf("输入错误：A与B的行数或列数不相同，请重新输入\n");
return;
}
int a[100][100]={0};
for(k=1;k<=A.t;k++)
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf("A输入为：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",a[k][l]);
printf("\n");
}

int b[100][100]={0};
for(k=1;k<=B.t;k++)
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("B输入为：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",b[k][l]);
printf("\n");
}
int c[100][100]={0};
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
{
c[k][l]=a[k][l]-b[k][l];
}
}
printf("减法结果C为：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",c[k][l]);
printf("\n");
}
}

void multi() //矩阵的乘法
{
int k;
tripletable A,B,C;
printf("输入稀疏矩阵A的行数，列数和非零元个数：");
scanf("%d %d %d",&A.m,&A.n,&A.t);
for(k=1;k<=A.t;k++)
{
printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&A.data[k].i,&A.data[k].j,&A.data[k].v);
}
int row=1;
for(k=1;k<=A.t;k++)
{
while(row<=A.data[k].i)
{
A.rpos[row++]=k;
}
}
while(row<=A.m)A.rpos[row++]=A.t+1;
printf("输入稀疏矩阵B的行数，列数和非零元个数：");
scanf("%d %d %d",&B.m,&B.n,&B.t);
for(k=1;k<=B.t;k++)
{

printf("输入第%d个非0元素的行数，列数和值:",k);
scanf("%d %d %d",&B.data[k].i,&B.data[k].j,&B.data[k].v);
}
row=1;
for(k=1;k<=B.t;k++)
{
while(row<=B.data[k].i)
{
B.rpos[row++]=k;
}
}
while(row<=B.m)B.rpos[row++]=B.t+1;
if(A.n!=B.m)
{
printf("输入错误：A的列数不等于B的行数，请重新输入\n");
return;
}

C.m=A.m;C.n=B.n;C.t=0;
int arow,p,q,ccol,t,tp;
if(A.t*B.t!=0)
{
for(arow=1;arow<=A.m;++arow)
{
int ctemp[maxsize]={0};
C.rpos[arow]=C.t+1;
if(arow<A.m){tp=A.rpos[arow+1];}
else{tp=A.t+1;}
for(p=A.rpos[arow];p<tp;++p)
{
int brow=A.data[p].j;
if(brow<B.m){t=B.rpos[brow+1];}
else{t=B.t+1;}
for(q=B.rpos[brow];q<t;++q)
{
ccol=B.data[q].j;
ctemp[ccol]+=A.data[p].v*B.data[q].v;

}

}
for(ccol=1;ccol<=C.n;++ccol)
{
if(ctemp[ccol])
{
if(++C.t>maxsize)return;
C.data[C.t].i=arow;
C.data[C.t].j=ccol;
C.data[C.t].v=ctemp[ccol];
}
}

}

}

int a[100][100]={0};
for(k=1;k<=A.t;k++)
{
a[A.data[k].i][A.data[k].j]=A.data[k].v;
}
printf("A输入为：\n");
for(k=1;k<=A.m;k++)
{
for(int l=1;l<=A.n;l++)
printf("%d ",a[k][l]);
printf("\n");
}

int b[100][100]={0};
for(k=1;k<=B.t;k++)
{
b[B.data[k].i][B.data[k].j]=B.data[k].v;
}
printf("B输入为：\n");
for(k=1;k<=B.m;k++)
{
for(int l=1;l<=B.n;l++)
printf("%d ",b[k][l]);
printf("\n");
}
int c[100][100]={0};
for(k=1;k<=C.t;k++)
{
c[C.data[k].i][C.data[k].j]=C.data[k].v;
}
printf("乘法结果C为：\n");
for(k=1;k<=C.m;k++)
{
for(int l=1;l<=C.n;l++)
printf("%d ",c[k][l]);
printf("\n");
}

}

void main()
{
printf("============= 菜 单 ==============\n");
printf(" 1 矩阵转置\n");
printf(" 2 矩阵加法\n");
printf(" 3 矩阵减法\n");
printf(" 4 矩阵乘法\n");
printf("======================================\n\n");
loop: printf("请选择相应操作的序号:");
int y;
scanf("%d",&y);
switch(y)
{
case 1: convert();
printf("\n");
goto loop;
case 2: add();
printf("\n");
goto loop;
case 3: jian();
printf("\n");
goto loop;
case 4: multi();
printf("\n");
goto loop;
}
}