常见数据结构的ADT类型

线性表

  1.  ADT 线性表 List
  2.  Data 
  3.   线性表数据对象的集合为{a1,a2,...,aN},每个元素的类型均为DataType。其中除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素aN外，每一个元素有且仅有一个直接后继元素。
  4.  Operation
  5.   InitList(*L) 初始化操作
  6.   ListEmpty(L) 若线性表为空，返回true，否则返回false
  7.   ClearList(*L) 将线性表清空
  8.   GetElem(L, i, *e) 将线性表L中的第i个元素值返回给e
  9.   LocateElem(L, e) 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则返回0表示失败
  10.   ListInsert(*L, i, e) 在线性表L中的第i个位置插入新元素e
  11.   ListLength(L) 返回线性表L的元素个数

栈

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

队列

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

串

  1. ADT 串 string
  2. Data
  3.   串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
  4. Operation
  5.   StrAssign(T, *chars) 生成一个其值等于字符串常量的chars的串T
  6.   StrCopy(T, S) 传S存在，由串S复制得到串T
  7.   ClearString(S) 串S存在，将串清空
  8.   StringEmpty(S) 若串S存在，将串清空
  9.   StrLength(S) 返回串S的元素个数，即串的长度
  10.   StrCompare(S, T) 若S>T, 返回值>0， 若S=T, 返回0, 若S<T, 返回值<0
  11.   Concat(T, S1, S2) 用T返回由S1和S2联结而成的新串
  12.   SubString(Sub, S, pos, len) 用Sub返回串S的第pos个字符起长度为len的子串
  13.   Index(S, T, pos) 若主串S中存在和串T值相同的子串, 则返回它在主串S中第pos个字符之后第一次出现的位置,否则返回0
  14.   Replace(S, T, V) 串S、T和V存在, T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串
  15.   StrInsert(S, pos, T) 在串S的第pos个字符之前插入串T
  16.   StrDelete(S, pos, len) 从串S中删除第pos个字符起长度为len的子串

树

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

图

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

习题

  1. 已知：先序 ABCDEF 中序 CBAEDF 求后序
  2. 已知：中序 ABCDEF 后序 BDCAFE 求先序

思路

先序和后序确定根结点，找到根结点后在中序找到左右子树，然后重新查找根结点