数据结构之抽象数据类型

抽象数据类型(Abstract Data Type 简称ADT)

定义:一个数学模型以及定义在该模型上的一组操作。

作用:抽象数据类型可以使我们更容易描述现实世界。

关键:使用它的人可以只关心它的逻辑特征,不需要了解它的存储方式。

其实按照面向对象的思想,ADT相当于接口。

描述抽象数据类型的标准格式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ADT   抽象数据类型名
 
Data
          数据元素之间逻辑关系的定义
           
Operation
          操作1
                   初始条件
                   操作结果描述
          操作2
                  ......
          操作n
                  ......
                   
endADT

线性表的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ADT List
 
Data
         /*线性表的数据对象集合为{a1,a2,...,an},每个元素的类型均为DataType.
           其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一
           个元素an外,每一个元素有且只有一个直接后继元素。数据元素直接是一对一的关系。*/
       
Operation
         InitList(*L);       //初始化操作,建立一个空的线性表
         ListEmpty(L);       //若线性表为空,返回true,否则返回false
         ClearList(*L);      //清空线性表
         GetElem(L,i,*e);    //查找线性表中的第i个位置的元素值,并赋值给e
         LocateElem(L,e);    //查找线性表L中与给定值e相等的元素,如果查找成功,
                             //则返回第一个相同的元素在L中的下标;否则,返回0表示失败
         ListInsert(*L,i,e); //在线性表L的第i个位置插入元素e
         ListDelete(*L,i,*e);//删除线性表L中第i个位置元素,并用e返回其值
         ListLength(L);      //返回线性表L的元素的个数,也就是线性表的长度
          
end ADT

的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ADT   Stack
 
Data  
         /*同线性表。元素具有相同类型,相邻元素具有前驱和后继关系。*/
          
Operation
         InitStack(*S);     //初始化操作,建立一个空栈S
         DestroyStack(*S);  //若栈存在,则销毁它
         ClearStack(*S);    //将栈清空
         StackEmpty(S);     //若栈为空,则返回true,否则返回false
         GetTop(S,*e);      //若栈存在且非空,用e返回S的栈顶元素
         Push(*S,e);        //若栈S存在,插入新元素e到栈S中并成为栈顶元素
         Pop(*S,*e);        //若栈S不空,删除栈中栈顶元素,并用e返回其值
         StackLength(S);    //返回栈S的元素个数
          
endADT

队列的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ADT   Queue
Data  
          /*同线性表。元素具有相同的类型,响铃元素具有前驱和后继关系*/
           
Operation         
       InitQueue(*Q);       //初始化操作,建立一个空队列Q        
       DestroyQueue(*Q);    //若队列Q存在,则销毁它         
       ClearQueue(*Q);      //将队列Q清空        
       StackQueue(Q);       //若队列Q为空,则返回true,否则返回false         
       GetHead(Q,*e);       //若队列Q存在且非空,用e返回Q的队头元素        
       EnQueue(*Q,e);       //若队列Q存在,插入新元素e到队列Q中并成为队尾元素         
       DeQueue(*Q,*e);      //若队列Q不空,删除队列中队头元素,并用e返回其值         
       QueueLength(Q);      //返回队列Q的元素个数 
                
endADT

的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ADT   String
   
Data  
          /*串中的元素仅由一个字符组成,相邻元素具有前驱和后继关系*/ 
       
Operation  
      StrAssign(T,*chars);        //生成一个其值等于字符串常量chars的串T    
      StrCopy(T,S);               //串S存在,由串S复制得串T 
      StrEmpty(S);                //若S为空串,则返回true,否则返回false 
      StrCompare(S,T);            //若S>T,则返回值>0;若S=T,则返回值=0;若S < T,则返回值 < 0  
      StrLength(S);               //返回S的元素个数,称为串的长度
      ClearString(S);             //清空串  
      Concat(T,S1,S2);            //用T返回由S1和S2联接而成的新串   
      SubString(Sub,S,pos,len);   //串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1,用Sub返回
                                  //串S的第pos个字符长度为len的子串  
      Index(S,T,pos);             //串S和T存在,T是非空串,1≤pos≤StrLength(S),若主串S中存在和串T值相同的
                                  //子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0 
      Replace(S,T,V);             //初始条件:串S, T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不
                                  //重叠的子串      
      StrInsert(S,pos,T);         //串S和T存在, 1≤pos≤StrLength(S)+1,在串S的第pos个字符之前插入串T
      StrDelete(S,pos,len);       //串S存在, 1≤pos≤StrLength(S)-len+1,从串S中删除第pos个字符起长度
                                  //为len的子串
      DestroyString(S);           //若串S存在,则销毁它  
 
endADT

的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ADT   Tree
 
Data    
          /*树是一个由根节点和若干棵子树构成。树中结点具有相同数据结构类型及层次关系*/
           
Operation
     InitTree(*T);                 //构造空树T
     DestoryTree(*T);              //销毁树T
     CreateTree(*T,definition);    //按definition中给出树的定义来构造树
     CleateTree(*T);               //若树T存在,则清空树
     TreeEmpty(T);                 //若T为空树则返回true,否则返回false
     TreeDepth(T);                 //返回T的深度
     Root(T);                      //返回T的根节点
     Value(T,cur_e);               //cur_e是树T中一个,返回此结点的值
     Assgin(T,cur_e,value);        //给树T的结点cur_e赋值为value
     Parent(T,cur_e);              //若cur_e是树T的非根节点,则返回它的父节点,否则返回空
     LeftChild(T,cur_e);           //若cur_e是树T的非叶结点,则返回它的左孩子,否则返回空
     RightSibling(T,cur_e);        //若cur_e是树T的非叶结点,则返回它的右兄弟,否则返回空
     InsertChild(*T,*p,i,c);       //其中p指向树T的某个结点,i为所指向结点p的度加上1,
                                   //若非空树c与T不相交,操作结果为:插入c为树T中p指向结点的第i棵子树
     DeleteChild(*T,*p,i);         //其中p指向树T的某个结点,i为所指向结点p的度,则删除T中p指向结点的第i棵子树
      
endADT

的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ADT  Graph
 
Data
           /*定点的有穷非空集合和边的集合*/
        
Operation
      CreateGraph(*G,V,VR);       //按V和VR的定义构造图G
      DestroyGraph(*G);           //若图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是无向的,则还增添对称弧<v,w>
      DeleteArc(*G,v,w);          //在G中删除弧<v,w>,若G是无向的,则还删除对称弧<v,w>
      DFSTraverse(G);             //对图G进行深度优先遍历
      HFSTraverse(G);             //对图G进行广度优先遍历
       
endADT

搞了一天,终于总结完毕!O(∩_∩)O~


 MORE:


 ? 算法数据结构_百度脑图
 ? 动态链接库(DLL)--MFCDLL
 ? 一个简约,轻量,可定制的jQuery返回顶部插件
 ? 安全通信系统--OpenSSL服务器和客户端
 ? Linux常用命令
 ? WindowDemo
 ? CListCtrl使用方法
 ? 杭电1166敌兵布阵
 ? UVA572油田问题(DFS求连通块)
 ? 古典密码学