计算机网络三元组,三元组 - Cache One

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

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

中文名

三元组

外文名

Three tuple研究领域

计算机

含    义

用来存储稀疏矩阵的一种压缩方式

别    名

三元组表

三元组研究目的

编辑

语音

对于在实际问题中出现的大型的稀疏矩阵,若用常规分配方法在计算机中储存,将会产生大量的内存浪费,而且在访问和操作的时候也会造成大量时间上的浪费,为了解决这一问题,从而产生了多种解决方案。

由于其自身的稀疏特性,通过压缩可以大大节省稀疏矩阵的内存代价。具体操作是:将非零元素所在的行、列以及它的值构成一个三元组(i,j,v),然后再按某种规律存储这些三元组,这种方法可以节约存储空间[1]

三元组结构描述

编辑

语音

typedef struct{

int i ,j ;

ElemType v ;

}Mat;

typedef struct{

int m,n,t;

Mat data[MAXSIZE];

}Spmatrix;

Spmatrix  a,b;

较完整的方式:

struct node

{

int i,j;  //定义三元组的行、列号

int v;   //三元组的值

};

struct sparmatrix

{

int rows,cols; //稀疏矩阵的行、列数

int terms;   //稀疏矩阵的非零元个数

struct node data[maxsize]; //存放稀疏矩阵的三元组表

};

三元组解释

编辑

语音

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

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

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

三元组求三元组合

编辑

语音

三元组思路

对于二元组的和等于给定值的情况, 即将数组排序后,用两个指向数组的指针,一个从前向后扫描,一个从后向前扫描,记为first和last,当first + last == sum 则找到了一对二元组,它们的和等于sum,如果first + last < sum 则 first++, first + last > sum 则last--。同样,三元组的情况,先将数组排序,然后固定一个元素,再去寻找一个二元组的和为sum - val,这样就将三元组的问题,转换成了二元组的问题[2]

三元组程序

#include 

#include 

using namespace std;

bool find3Numbers(int A[], int arr_size, int sum)

{

int l, r;

/* Sort the elements */

sort(A, A + arr_size);

/* Now fix the first element one by one and find the

* other two elements

*/

for (int i = 0; i 

{

// to find the other two elements, start two index variables

//from two corners of the array and move toward each other

l = i + 1; //index of the first element in the remaining elements

r = arr_size - 1;//index of the last element

while (l 

{

if (A[i] + A[l] + A[r] == sum)

{

cout <

return true;

}

else if (A[i] + A[l] + A[r] 

{

l++;

}

else // A[i] + A[l] + A[r] > sum

{

r--;

}

}

}

// If we reach here, then no triplet was found

return false;

}

/* Driver program to test above function */

int main(int argc, char* argv[])

{

int A[] = {1, 4, 45, 6, 10, 8};

int sum = 22;

int arr_size = sizeof(A) / sizeof(A[0]);

find3Numbers(A, arr_size, sum);

return 0;

}参考资料

1.

算法----稀疏矩阵之三元组

.博客园[引用日期2018-01-23]

2.

算法系列:三元组和

.博客园[引用日期2018-01-23]

为您推荐