初识数据结构之三元组

大家好，欢迎来到IT知识分享网。

三元组

一、什么是三元组

在初步了解了数据结构的研究内容后，做一个简单的尝试——三元组。

三元组是数据结构里的一个基本概念。主要是用来存储稀疏矩阵的一种压缩方式，也叫三元组表。

三元组中存放三个值（x,y,z)分别代表矩阵的行、列、值。

二、三元组抽象数据类型描述

ADT Triplet {

数据对象：D = {e1,e2,e3 | e1,e2,e3属于ElemType}

数据关系：R = {<e1，e2> | <e2，e3>}

基本操作：

initTriplet(&T,v1,v2,v3)

操作结果：构造一个空的三元组T。

destroyTriplet(&T)

初始条件：三元组T已存在。

操作结果：销毁三元组。

getElem(T,i,&e)

初始条件：三元组T已存在，且1<=i<=3。

操作结果：用e返回T中第i个元素的值。

putElem(&T,i,e)

初始条件：三元组T已存在，且1<=i<=3。

操作结果：将第i个元素置换为e。

printTriplet(Triplet &T)

初始条件：三元组T已存在。

操作结果：显示三元组。

getMax(T,&e)

初始条件：三元组T已存在。

操作结果：用e返回三元组T中的最大值。

getMin(T,&e)

初始条件：三元组T已存在。

操作结果：用e返回三元组T中的最小值。

}

三、三元组操作实现

1、预定义

#define OK 1 #define ERROR 0 typedef int Status; //三元组的类型先定义为float,可以随时变换成别的类型 typedef float ElemType; typedef ElemType *Triplet; 

2、初始化

Status initTriplet(Triplet &T, ElemType v0, ElemType v1, ElemType v2) { //动态分配3个字节的内存来存储三元组中的三个值。 T = (Triplet)malloc(3 * sizeof(v0, v1, v2)); T[0] = v0; T[1] = v1; T[2] = v2; return OK; } 

在C语言中没有动态数组类型，数组的长度是预先定义好的，而在实际的开发中，经常无法确定空间大小的情况。因此需要根据实际动态分配和回收内存空间。这里用到动态分配内存函数malloc();

3、销毁三元组

Status DestroyTriplet (Triplet &T) { free(T); return OK; } 

4、用e获取T的第i个元素的值

Status getElem(Triplet T, int i, ElemType e) { //参数i输入范围为1~3。 if (i < 1 || i > 3) //非法输入返回ERROR。 return ERROR; else //正常输入，用e返回。 e = T[i - 1]; printf("%f", e); return OK; } 

5、置T的第i元的值为e

Status putElem(Triplet T, int i, ElemType &e) { if (i < 1 || i > 3) return ERROR; else T[i - 1] = e; printf("%f", e); return OK; } 

6、用e返回指向T的最大元素的值

ElemType getMax(Triplet T, ElemType &e) { if (T[0] > T[1]) e = T[0]; else e = T[1]; if (T[2] > e) e = T[2]; printf("%f", e); return e; } 

7、用e返回指向T的最小元素的值

ElemType getMin(Triplet T, ElemType &e) { //比较第一、二个元素，将较大值赋给e，用e与第三个元素比较，将较大值赋给e并返回。 if (T[0] < T[1]) e = T[0]; else e = T[1]; if (T[2] < e) e = T[2]; printf("%f", e); return e; } 

8、显示三元组

Status printTriplet (Triplet &T) { int i; for (i = 0; i < 3; i++) { printf("%f\n", T[i]); } printf("\n"); return OK; } 

9、主函数

int main() { int n; int i; Triplet T; Status flag;s ElemType v0, v1, v2, e; //提示输入 printf("请进入三元组的三个值v0,v1,v2:\n"); scanf("%f%f%f", &v0, &v1, &v2); //初始化 flag = initTriplet(T, v0, v1, v2); //提示输入 printf("调用初始化函数后,flag=%d,T的三个值为%4.2f,%4.2f,%4.2f\n", flag, T[0], T[1], T[2]); printf("0 结束程序：\n"); printf("1 取三元组的任意一个分量：\n"); printf("2 置三元组的任意一个分量：\n"); printf("3 求三元组的最大分量：\n"); printf("4 求三元组的最小分量：\n"); printf("5 显示三元组：\n"); printf("6 销毁三元组：\n"); //用一个循环反复实现各种功能。 while (1) { printf("请输入你想完成的功能编号：\n"); scanf("%d", &n); if (n == 0) { break; } else { switch (n) { case 1: scanf("%d", &i); getElem (T, i, e); break; case 2: scanf("%d%f", &i, &e); putElem (T, i, e); break; case 3: getMax (T, e); break; case 4: getMin (T, e); break; case 5: printTriplet (T); break; case 6: DestroyTriplet (T); break; default: printf("没有你想完成的功能\n"); break; } } } return 0; } 

三元组操作实现完整代码

#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef float ElemType; typedef ElemType *Triplet; Status initTriplet(Triplet &T, ElemType v0, ElemType v1, ElemType v2) { T = (Triplet)malloc(3 * sizeof(v0, v1, v2)); T[0] = v0; T[1] = v1; T[2] = v2; return OK; } Status getElem(Triplet T, int i, ElemType e) { if (i < 1 || i > 3) return ERROR; else e = T[i - 1]; printf("%f", e); return OK; } Status putElem(Triplet T, int i, ElemType &e) { if (i < 1 || i > 3) return ERROR; else T[i - 1] = e; printf("%f", e); return OK; } ElemType getMax(Triplet T, ElemType &e) { if (T[0] > T[1]) e = T[0]; else e = T[1]; if (T[2] > e) e = T[2]; printf("%f", e); return e; } ElemType getMin(Triplet T, ElemType &e) { if (T[0] < T[1]) e = T[0]; else e = T[1]; if (T[2] < e) e = T[2]; printf("%f", e); return e; } Status printTriplet (Triplet &T) { int i; for (i = 0; i < 3; i++) { printf("%f\n", T[i]); } printf("\n"); return OK; } Status DestroyTriplet (Triplet &T) { free(T); return OK; } int main() { int n; int i; Triplet T; Status flag;s ElemType v0, v1, v2, e; printf("请进入三元组的三个值v0,v1,v2:\n"); scanf("%f%f%f", &v0, &v1, &v2); flag = initTriplet(T, v0, v1, v2); printf("调用初始化函数后,flag=%d,T的三个值为%4.2f,%4.2f,%4.2f\n", flag, T[0], T[1], T[2]); printf("0 结束程序：\n"); printf("1 取三元组的任意一个分量：\n"); printf("2 置三元组的任意一个分量：\n"); printf("3 求三元组的最大分量：\n"); printf("4 求三元组的最小分量：\n"); printf("5 显示三元组：\n"); printf("6 销毁三元组：\n"); while (1) { printf("请输入你想完成的功能编号：\n"); scanf("%d", &n); if (n == 0) { break; } else { switch (n) { case 1: scanf("%d", &i); getElem (T, i, e); break; case 2: scanf("%d%f", &i, &e); putElem (T, i, e); break; case 3: getMax (T, e); break; case 4: getMin (T, e); break; case 5: printTriplet (T); break; case 6: DestroyTriplet (T); break; default: printf("没有你想完成的功能\n"); break; } } } return 0; } 

运行结果：