ADT 抽象数据类型名称{
      数据对象(Data):<数据对象的定义>
      数据关系      :<数据关系的定义>
      基本操作(Operation):<基本操作的定义>
}ADT抽象数据类型名称

ADT 线性表（List）

Data
    线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。

Operation
    InitList(): 初始化操作，建立一个空的线性表L。
    DestroyList():线性表已经存在，释放该线性表所占用的存储空间
    ClearList(): 线性表已经存在，重置线性表为空表，将线性表清空。
    ListLength(): 线性表已经存在返回线性表L的元素个数。
    GetElem(): 求线性表L中的第i个位置元素值。
        初始条件：线性表已存在
        输入参数：元素序号i，1<=i<=ListLength(L)
        实现功能：取线性表中序号为i的元素值
        输出数据：如果序号不合理，则给出错误信息；否则返回序号为i的元素序号值
        操作结果：线性表不变
    LocateElem(): 在线性表L中查找与给定值x相等的元素，如果查找成功，返回线性表中第1个值等于x的元素序号;否则返回0。
        初始条件：线性表已存在
        输入参数：元素x
        实现功能：查找线性表中第1个值等于x的元素
        输出数据：如果查找成功，返回线性表中第1个值等于x的元素序号；否则返回0
        操作结果：线性表不变
    ListInsert(): 在线性表L中第i个位置插入新元素e。
        初始条件：线性表已存在
        输入参数：插入位置i,1<=i<=ListLength(L)+1,ListLength(L)表示插入前的表长;待插入元素x
        实现功能：插入x到线性表的第i个位置上
        输出数据：如果插入不成功，则给出错误信息
        操作结果：当插入成功时，线性表中增加了一个元素x，且表长增1
    ListDelete(): 删除线性表L中第i个位置元素，并用e返回其值。
        初始条件：线性表已存在
        输入参数：删除位置i,1<=i<=ListLength(L)+1,ListLength(L)表示插入前的表长
        实现功能：删除线性表中的第i个元素
        输出数据：如果删除不成功，则给出错误信息。否则返回第i个元素值
        操作结果：当删除成功时，线性表中减少了一个元素，且表长减1
endADT

ADT Stack{
    Data：
        栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系
    Operation：
        InitStack()：初始化栈，构造一个空栈
        DestroyStack()：销毁栈，释放栈所占用的存储空间
        StackLength()：求栈的长度
        GetTop()：
              实现功能：读取当前栈顶元素
              输出数据：如果栈空，则给出错误信息；否则返回当前栈顶元素值
        Push()：
              输入参数：待插入元素
              实现功能：插入元素到栈顶
              输出数据：如果插入不成功，则给出错误信息
              操作结果：当插入成功时，栈顶增加了一个元素
        Pop()：
              输入参数：无
              实现功能：删除栈顶元素
              输出数据：如果栈为空，则给出错误信息；否则返回栈顶元素
              操作结果：当删除成功时，栈顶减少了一个元素
}

ADT Queue{
    Data：
        队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系
    Operation：
        InitQueue()：初始化队列，构造一个空队列
        DestroyQueue()：销毁队列，释放队列所占用的存储空间
        QueueLength()：求队列的长度
        GetHead()：
              实现功能：读取当前队列头元素
              输出数据：如果队列空，则给出错误信息；否则返回当前队列头元素值
       EnQueue()：
              输入参数：待插入元素
              实现功能：插入元素到队列尾
              输出数据：如果插入不成功，则给出错误信息
              操作结果：当插入成功时，队列尾增加了一个元素
       DeQueue()：
              输入参数：无
              实现功能：删除队列头元素
              输出数据：如果队列为空，则给出错误信息；否则返回队列头元素
              操作结果：当删除成功时，队列尾减少了一个元素
}

ADT 串(string)
{
    Data
        串中元素仅由一个字符组成,相邻元素具有前驱和后继关系.

    Operation
        StrAssign(T,*chars):生成一个其值等于字符常量chars的串T.
        StrCopy(T,S):串S存在,由S复制得到T.
        ClearString(S):串S存在,将串清空.
        StringEmpty(S):  若串为空,返回true,否则返回false.
        StrLentgth(S) :返回串S的元素个数,即串的长度.
        StrCompare(S,L):比较S和T,若S>T,返回>0,S==T返回0, S<T返回<0
        SubString(Sub, S, pos, len): 串S存在,1<=pos<=StrLentgth(S),且 0<=len<=StrLentgth(S)-pos+1,用Sub返回串S的第pos个起,长度为len的子串.
        Index(S,T,pos)
        Replace(S,T,V)串S,T,V存在,T是非空串,用V替换S中出现的所有与T相等的不重叠的子串.
        StrInsert(S,T,pos): 在串S的第pos个字符之前插入串T.
        StrDelete(S,pos,len):从串S中删除第pos个字符起的长度为len的子串.
}endADT

ADT Array {

Data:

    相同类型元素有序集合，每个元素受n(n>=1)个线性关系的约束并由一组下标唯一标识

Operation:

    InitArray():  //构造一个空数组,数组的维数和各维的长度

    DestroyArray()：//销毁数组,释放数组所占用的存储空间

    GetValue(A,&e,index1,…,indexn) //求值函数,求某个下标元素的值

        初始条件:A是维数组,e为元素变量,随后是n个下标值.

        操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.

    Assign(&A,e,index1,…,indexn)//赋值函数,给下具体的下标的元素赋值

        初始条件:A是n维数组,e为元素变量,随后是n个下标值.

        操作结果:若下标不超界,则将e的值赋给所指定的A的元素,并返回OK.

}ADT Array

ADT Tree{
    Data:
        树
    Operation：
        InitTree(&T):构造空树
        DestroyTree(&T)：销毁树
        CreateTree(&T,dfinition):
            初始条件:defination给出树T的定义
            操作结果：按defination构造树T
        ClearTree(&T):将树清为空树
        TreeEmpty(T):若树为空树，则返回TRUE,否则FALSE
        TreeDepth(T)：返回树的深度
        Root(T):返回T的根
        Value(T,node):树T存在，node是T中的某一个结点，返回node的值
        Assign(T,node,value):树T存在，node是T中的某一个结点，结点node赋值为value
        Parent(T,node):若node是T的非根结点,返回它的双亲，否则函数值为空
        LeftChild(T,node):若node是T的非叶子结点,返回它的最左孩子，否则函数值为空
        RightSiblingChild(T,node):若node右兄弟,返回它的右兄弟，否则函数值为空
        InsertChild(&T,&p,i,c):树T存在，p指向是T中某一个结点，插入c为T中p所指节点的第i颗子树
        DeleteChild(&T,&p,i,c):树T存在，p指向是T中某一个结点，删除T中p所指节点的第i颗子树
        TraveseTree():遍历树
}ADT Tree

ADT 图(Graph)
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G。
    DestroyGraph(*G):      图G存在则销毁。
    LocateVex(G, u):        若图G中存在顶点u，则返回图中的位置。
    GetVex(G, v):          返回图G中顶点v的值。
    PutVex(G, v, value):    将图G中顶点v赋值value。
    FirstAdjVex(G, *v):    返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
    NextAdjVex(G, v, *w):  返回顶点v相对于顶点w的下一个邻接顶点，
                            若w是v的最后一个邻接点则返回“空”。
    InsertVex(*G, v):      在图G中增添新顶点v。
    DeleteVex(*G, v):      删除图G中顶点v及其相关的弧。
    InsertArc(*G, v, w):    在图G中增添弧<v,w>，若G是无向图，还需要增添对称弧<w,v>。
    DeleteArc(*G, v, w):    在图G中删除弧<v,w>，若G是无向图，则还删除对称弧<w,v>。
    DFSTraverse(G):        对图G中进行深度优先遍历，在遍历过程对每个顶点调用。
    HFSTraverse(G):        对图G中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT