データ構造--抽象データ型(ADT)の表現と実現

*資料整理出所:『データ構造(C言語版)』–厳蔚敏、呉偉民編著
1.ADT記述抽象データ型(abstract data type,ADT)は、数学モデルおよびモデル上で定義された一連の動作を指す.
ADT抽象データ型名{

データオブジェクト:

データ関係:

基本操作:

}ADT抽象データ型名
ここで、データオブジェクトとデータ関係の定義は擬似コードで記述され、基本操作の定義フォーマットは
基本操作名(パラメータテーブル)

初期条件:

操作結果:

基本操作には2つのパラメータがあります.付与パラメータは操作に入力値を提供するだけです.参照パラメータは&で始まり、入力値のほか、操作結果も返されます.
2.共通コード文(1)定義済定数とタイプ:

//        
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status      ，           
typedef int Status

(2)データ構造の表示(記憶構造)はタイプ定義(typedef)で記述される.データ要素タイプはElemTypeとして規定されており、ユーザがそのデータ型を使用する際に自ら定義する.(3)基本操作のアルゴリズムは以下の形式の関数で記述される.

        (     ){
    //    
        
} //   

3.例抽象データ型三元グループTripletの表現と実現

//              
typedef ElemType *Triplet;  // InitTriplet  3        

//           
Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3);
    //    :      T，  e1，e2 e3       v1，v2 v3  
Status DestroyTriplet(Triplet &T);
    //    ：   T   
Status Get(Triplet T,int i,ElemType &e);
    //    ：   T   ，1<=i<=3
    //    : e  T  i    
Status Put(Triplet &T,int i,ElemType e); 
    //    ：   T   ，1<=i<=3
    //    ：  T  i    e
Status IsAscending(Triplet T);
    //    ：   T   
    //    ：  T 3        ，   1，    0
Status IsDescending(Triplet T);
    //    ：   T   
    //    ：  T 3        ，   1，    0
Status Max(Triplet T,ElemType &e);
    //    ：   T   
    //    ： e  T 3        
Status Min(Triplet T,ElemType &e);
    //    ：   T   
    //    ： e  T 3        

//       
Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3)
{
    T=new ElemType[2];  //  3         
    if(!T) exit(OVERFLOW);  //         
    T[0]=v1;
    T[1]=v2;
    T[2]=v3;
    return OK;
}
Status DestroyTriplet(Triplet &T)
{
    delete []T;
    T=NULL;
    return OK;
}
Status Get(Triplet T,int i,ElemType &e)
{
    if(i<1||i>3)    return ERROR;
    e=T[i-1];
    return OK;
}
Status Put(Triplet &T,int i,ElemType e)
{
    if(i<1||i>3)    return ERROR;
    T[i-1]=e;
    return OK;
}
Status IsAscending(Triplet T)
{
    return (T[0]<=T[1])&&(T[1]<=T[2]);
}
Status IsDescending(Triplet T)
{
    return (T[0]>=T[1])&&(T[1]>=T[2]);
}
Status Max(Triplet T,ElemType &e)
{
    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)
{
    e=(T[0]<=T[1])?((T[0]<=T[2])?T[0]:T[2])
                    :((T[1]<=T[2])?T[1]:T[2]);
    return OK;
}