抽象数据类型 Triplet 的表示和实现（第一章：P12）

前言

注意：《数据结构》课本中函数参数使用引用时，采用的是 & ，而我在这里用 C 实现的引用参数使用的是 * ，下面我解析下原因。

引用，指针，地址是联系密切的概念。地址是在电脑内存中的地址（一般是一些变量的值在内存中的储存位置），指针是存地址的变量，所以指针可以“指向”内存地址。概念上讲，引用变量本质上是指针的另一个名字（但是并不能被编译器实例化）

C++中使用&可以表示变量类型引用变量（简单说来为引用），这种&的用法在C中不存在。但是在C语言中用指针也可以实现类似的功能。

实例：

（1） C++中（引用在函数的参数中被使用）

void main(void)  
{  
int i=3; 
f(i);  
cout << i;  
} 
void f(int& r)  
{  
r = 2*r;  
}

这段程序输出“6”（2*r使被r引用的变量加倍，也就是指i）

（2）在C语言中

实现同样的功能，我们可以通过声明f()为void f(int *r)，其中r是指向整数类型的指针，然后调用参数&i(i的地址)调用函数f()，在函数f()内使用r的解引用。

void main(void)  
{  
int i=3; 
f(&i);  
cout << i;  
} 
void f(int *r)  
{  
r = 2*r;  
}

抽象数据类型 Triplet 的表示和实现（C语言）

typedef int ElemType; /* 定义抽象数据类型ElemType在本程序中为整型 */
/*typedef double ElemType; /* 定义抽象数据类型ElemType在本程序中为双精度型 */

typedef ElemType *Triplet; /* 由InitTriplet分配三个元素存储空间 */
/* Triplet类型是ElemType类型的指针，存放ElemType类型的地址 */

#include<malloc.h> /* malloc()等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<process.h> /* exit() */

/* 函数结果状态代码 */
#define OK 1
#define ERROR 0
#define OVERFLOW -2 

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */


/* 抽象数据类型Triplet和ElemType的基本操作(8个) */

/* -------------        基本操作的函数原型说明     ---------------*/
Status InitTriplet(Triplet *T, ElemType v1, ElemType v2, ElemType v3);
Status DestroyTriplet(Triplet *T);
Status Get(Triplet T, int i, ElemType *e);
Status Put(Triplet T, int i, ElemType e);
Status IsAscending(Triplet T);
Status IsDescending(Triplet T);
Status Max(Triplet T, ElemType *e);
Status Min(Triplet T, ElemType *e);



/* -------------           基本操作的实现        ---------------*/

Status InitTriplet(Triplet *T, ElemType v1, ElemType v2, ElemType v3)
{ /* 操作结果:构造三元组T,依次置T的三个元素的初值为v1,v2和v3 */
 *T = (ElemType *)malloc(3 * sizeof(ElemType));
 if (!*T)
  exit(OVERFLOW);
 (*T)[0] = v1, (*T)[1] = v2, (*T)[2] = v3;
 return OK;
}

Status DestroyTriplet(Triplet *T)
{ /* 操作结果：三元组T被销毁 */
 free(*T);
 *T = NULL;
 return OK;
}

Status Get(Triplet T, int i, ElemType *e)
{ /* 初始条件：三元组T已存在，1≤i≤3。操作结果：用e返回T的第i元的值 */
 if (i < 1 || i>3)
  return ERROR;
 *e = T[i - 1];
 return OK;
}

Status Put(Triplet T, int i, ElemType e)
{ /* 初始条件：三元组T已存在，1≤i≤3。操作结果：改变T的第i元的值为e */
 if (i < 1 || i>3)
  return ERROR;
 T[i - 1] = e;
 return OK;
}

Status IsAscending(Triplet T)
{ /* 初始条件：三元组T已存在。操作结果：如果T的三个元素按升序排列，返回1，否则返回0 */
 return(T[0] <= T[1] && T[1] <= T[2]);
}

Status IsDescending(Triplet T)
{ /* 初始条件：三元组T已存在。操作结果：如果T的三个元素按降序排列，返回1，否则返回0 */
 return(T[0] >= T[1] && T[1] >= T[2]);
}

Status Max(Triplet T, ElemType *e)
{ /* 初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最大值 */
 *e = (T[0] >= T[1]) ? (T[0] >= T[2] ? T[0] : T[2]) : (T[1] >= T[2] ? T[1] : T[2]);
 return OK;
}

Status Min(Triplet T, ElemType *e)
{ /* 初始条件：三元组T已存在。操作结果：用e返回T的三个元素中的最小值 */
 *e = (T[0] <= T[1]) ? (T[0] <= T[2] ? T[0] : T[2]) : (T[1] <= T[2] ? T[1] : T[2]);
 return OK;
}

/* main 检验基本操作的主函数 */
void main()
{
 Triplet T;
 ElemType m;
 Status i;
 i = InitTriplet(&T, 5, 7, 9);
 //i=InitTriplet(&T,4.0,8.1,9.3); /* 当ElemType为双精度型时,可取代上句 */
 printf("调用初始化函数后，i=%d(1:成功) T的三个值为：%d %d %d\n", i, T[0], T[1], T[2]); /* 当ElemType的类型变化时，要相应改变printf()的格式符。 */
 i = Get(T, 2, &m);
 if (i == OK)
  printf("T的第2个值为：%d\n", m);
 i = Put(T, 2, 6);
 if (i == OK)
  printf("将T的第2个值改为6后，T的三个值为：%d %d %d\n", T[0], T[1], T[2]);
 i = IsAscending(T); /* 此类函数实参与ElemType的类型无关,当ElemType的类型变化时,实参不需改变 */
 printf("调用测试升序的函数后，i=%d(0:否 1:是)\n", i);
 i = IsDescending(T);
 printf("调用测试降序的函数后，i=%d(0:否 1:是)\n", i);
 if ((i = Max(T, &m)) == OK) /* 先赋值再比较 */
  printf("T中的最大值为：%d\n", m);
 if ((i = Min(T, &m)) == OK)
  printf("T中的最小值为：%d\n", m);
 DestroyTriplet(&T); /* 函数也可以不带回返回值 */
 printf("销毁T后，T=%u(NULL)\n", T);
}

运行结果：