三元组存储地址计算方法

① 数据结构、数组存储的地址怎么计算

数组存储地址的计算：

以二维数组为例，其他的依次类推

假设起始下标从0开始，按行存储(总共有M行，N列）：

A[i][j]=A[0][0]+(i*N+j)*L

这地方的L是数组中的一个元素所占的存储空间。

或：

即使A[8][5]前面有多少个元素，

行下标i从1到8,列下标j从1到10，所有A[8][5]之前共有n7*10+4（74）个元素，

每个元素的长度为3个字节，故共有3*74=222个字节

首地址是SA，则A[8][5]地址是SA+222

(1)三元组存储地址计算方法扩展阅读：

在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到，访问任一元素的时间与该元素结点在链式存储结构中的位置有关。

② 稀疏矩阵三元组存储结构的定义及其有关算法的实现

/*我写的一个例子，基本上将稀疏矩阵三元组存储结构的定义和其有关的算法都实现了，你可以借一本关于数据结构c语言实现的书来看一下*/
#include<stdio.h>
#define MAXSIZE 1000//非零元素的个数最多为1000
typedef struct {
int row;
int col;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE];//非零元素的三元组表
int m;//矩阵的行数
int n;//矩阵的列数
int non_zero_num;//非零元数的个数
}XSMatrix;
XSMatrix XSM_Info_Input(XSMatrix s){
int i;
printf("输入矩阵的行数：");
scanf("%d",&s.m);
printf("输入矩阵的列数：");
scanf("%d",&s.n);
printf("输入矩阵的非零元素的个数：");
scanf("%d",&s.non_zero_num);
for(i=0;i<s.non_zero_num;i++){
printf("输入第%d个非零元数的信息：\n",i+1);
printf("行下标:");
scanf("%d",&s.data[i].row);
printf("列下标:");
scanf("%d",&s.data[i].col);
printf("元素的值");
scanf("%d",&s.data[i].e);
}
return s;
}
void XSM_Info_Output(XSMatrix s){
int i;
printf("\n稀疏矩阵行数和列数：%d\t%d\n",s.m,s.n);
printf("稀疏矩阵三元组表如下：\n");
printf("行下标\t列下标\t值\n");
for(i=0;i<s.non_zero_num;i++){
printf("%d\t%d\t%d\n",s.data[i].row,s.data[i].col,s.data[i].e);
}
}
//列序递增转置法
XSMatrix TransXSM(XSMatrix s){
XSMatrix d;
int i,j,k=0;
d.m=s.n;
d.n=s.m;
d.non_zero_num=s.non_zero_num;
for(i=0;i<s.n;i++){
for(j=0;j<s.non_zero_num;j++){
if(s.data[j].col==i)
{
d.data[k].row=s.data[j].col;
d.data[k].col=s.data[j].row;
d.data[k].e=s.data[j].e;
k++;
}
}
}
return d;
}
main(){
XSMatrix source,dest;
source=XSM_Info_Input(source);
XSM_Info_Output(source);
dest=TransXSM(source);
XSM_Info_Output(dest);
}

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

/*~~~~稀疏矩阵的三元组顺序表存储结构类型定义及部分常见操作算法（smatrix.c）~~~~*/
#ifndef __SPARSEMATRIX__
#define __SPARSEMATRIX__

#ifndef COMMONELEM
#define COMMONELEM 0 /*公共元的值*/
#endif

#include <stdlib.h>
/*三元组顺序表存储空间长度的最小值*/
#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(size<MATRIXMINSIZE)
size=MATRIXMINSIZE;
pM->listsize = 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; i<M.rows; i++)
{
for(j=0; j<M.cols; j++)
if(k<M.len && i==M.base[k].row && j==M.base[k].col)
(*cout)(M.base[k++].value);/*输出特殊元*/
else
(*cout)(COMMONELEM); /*输出公共元*/
printf("\n");
}
}

/*取矩阵元素*/
BOOL GetElem(SMatrix M, MatrixDT *pd, int i, int j)
{
int k, addr;
BOOL flg=TRUE;
if(i<0 || i>M.rows-1 || j<0 || j>M.cols-1)
flg=FALSE;/*访问越界*/
else
{
*pd = COMMONELEM;
/*
由于三元组顺序表中特殊元是按"以行优先的顺序并保持同一行中列号从小到大的
规律"保存的，故，可以把矩阵中每个特殊元的二元（行号和列号）逻辑地址转换
成递增有序的一元伪地址addr=行号*列数+列号；
本算法采用的是最简单的顺序查找方法。
由于关键字序列是递增有序的,所以也可以使用折半查找（详见第10章）等算法，
那样效率会更高。
*/
addr=i*M.cols+j;
for(k=0; k<M.len && M.base[k].row*M.cols +M.base[k].col <addr; k++)
;
if(k<M.len && i==M.base[k].row && j==M.base[k].col)
/*M[i][j]是特殊元*/
*pd = M.base[k].value;
}
return flg;
}

/*写矩阵元素*/
BOOL PutElem(SMatrix *pM, MatrixDT d, int i, int j,
BOOL (*equal)(MatrixDT,MatrixDT))
{
int k,m,addr;
BOOL flg=TRUE;
if(i<0 || i>pM->rows-1 || j<0 || j>pM->cols-1 || pM->len >=pM->listsize)
flg=FALSE;/*访问越界*/
else
{
addr=i*pM->cols +j;
/*扫描到i行中j列元素应在的位置*/
for(k=0;k<pM->len &&
pM->base[k].row* pM->cols +pM->base[k].col<addr; k++)
;
if(k<pM->len && i==pM->base[k].row && j==pM->base[k].col)
{
/*原来是特殊元*/
if((*equal)(d,COMMONELEM))
{
/*第1种情况：原来是特殊元，写入的是公共元值。从表中删除元素*/
for(m=k+1; m<pM->len; 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; i<pM->len; 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(i<M.len && j<N.len)
{
/*计算矩阵M和矩阵N递增有序的一元伪地址addrM和addrN*/
addrM=M.base[i].row*M.cols + M.base[i].col;
addrN=N.base[j].row*N.cols + N.base[j].col;
if(addrM==addrN)/*两个矩阵中存在位置相同的特殊元*/
{
/*d是两个位置相同的特殊元相加之和*/
d=(*add)(M.base[i].value , N.base[j].value);
if(!(*equal)(d, COMMONELEM))
{
/*d是特殊元,把（i,j,d）追加到base数组*/
base[k].row =M.base[i].row;
base[k].col =M.base[i].col;
base[k++].value =d;
}
i++;
j++;
}
else if(addrM < addrN) /*矩阵M中当前特殊元应先追加到base数组*/
{
base[k]=M.base[i++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
else /*矩阵N中当前特殊元应先追加到base数组*/
{
base[k++]=N.base[j++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
}
/*将矩阵M或矩阵N中剩余的特殊元追加到base数组*/
for(; i<M.len; i++)
{
base[k]=M.base[i++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
for(; j<N.len; j++)
{
base[k]=N.base[j++];
base[k++].value=(*add)(base[k].value, COMMONELEM);
}
if(k>pM->listsize)
exit(EXIT_FAILURE);
/*复制结果数据到pM->base区*/
for(i=0; i<k; i++)
pM->base[i]=base[i];
free(base);
pM->rows=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; col<M.cols; col++) /*col是转置后矩阵的行号*/
for(j=0; j<M.len; j++)
if(M.base[j].col == col)
{
/*特殊元行列对换后写入新表空间*/
base[i].row = M.base[j].col;
base[i].col = M.base[j].row;
base[i].value = M.base[j].value;
i++;
}
pM->listsize =M.listsize;
pM->len =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);
}

④ 怎么计算三维数组的存储地址

假设数组各维的下界是不是1,二维数组A(mn)按“行优先顺序”存储在内存中，假设每个元素占用d个存储单元。元素a(ij)的存储地址应是数组的基地址加上排在a(ij)前面的元素所占用的单元数。因为a(ij)位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，第i行上a(ij)前面又有j-1个元素，故它前面一共有(i-1) ×n+j-1个元素。
因此，a（ij）的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d。
同样，三维数组A(ijk)按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d。

上述讨论均是假设数组各维的下界是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。a(ij)前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上a(ij)前一共有j-c2个元素。
因此，a(ij)的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d。

例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d。

⑤ 什么是数据结构中的二元组、三元组和五元组

二元组的定义:<K,R>
三元组的定义:<D,F,A>
五元组的定义:<V,O,G,M,S>
V是值的集合,O是操作的集合,G是构成名字的文法,M是存储的集合,S是从G能构成的名字几个到M的映射.

⑥ 三元组的存储及转置

#include <iostream>
using namespace std;

int b[100][100]={0};
int c[100][100]={0};
int d[100][100]={0};

struct node
{
int i;
int j;
int e;
};
class jz
{
node a[100];
int p,s,m,n,k,n1,n2;
public:
void datain();
void datacal();
void dataout();
};

void jz::datain()
{

cin>>m>>n1;
cin>>s;
for(p=1;p<=s;p++)
{
cin>>a[p].i>>a[p].j>>a[p].e;
b[a[p].i][a[p].j]=a[p].e;
}

cin>>n2>>k;
cin>>s;
for(p=1;p<=s;p++)
{
cin>>a[p].i>>a[p].j>>a[p].e;
c[a[p].i][a[p].j]=a[p].e;
}
if (n1==n2) n=n1;
else n=-100;
}
void jz::datacal()
{

if(n<0) exit(1);
else
{
for (int s=1;s<=m;s++)
for (p=1;p<=n;p++)
for (int l=1;l<=k;l++)
d[s][l]+=b[s][p]*c[p][l];
}
}
void jz::dataout()
{
// cout<<"**m"<<m<<"**n"<<n<<"**k"<<k<<endl;
if(n<0) cout<<"Error"<<endl;
else
for(int s=1;s<=m;s++)
{
for(int l=1;l<=k;l++)
cout<<d[s][l]<<' ';
cout<<'\n';
}
}
int main()
{
jz t1;
t1.datain();
t1.datacal();
t1.dataout();
return 0;
}

⑦ 三元组行表怎么找

行表就是求之前每行有多少个元素

⑧ 能详细描述一下顺序存储的数组元素的存放地址的计算方法吗

元素a(ij)的存储地址应是数组的基地址加上排在a(ij)前面的元素所占用的单元数。因为a(ij)位于第i行、第j列，前面i-1行一共有(i-1)×n个元素，第i行上a(ij)前面又有j-1个元素，故它前面一共有(i-1) ×n+j-1个元素。 因此，a（ij）的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d。 同样，三维数组A(ijk)按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p+(k-1)]*d。 上述讨论均是假设数组各维的下界是1，更一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是1。a(ij)前一共有i-c1行，二维数组一共有d2-c2+1列，故这i-c1行共有(i-c1)*(d2-c2+1)个元素，第i行上a(ij)前一共有j-c2个元素。 因此，a(ij)的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+j-c2)]*d。