Skip to content

Latest commit

 

History

History
118 lines (110 loc) · 5.45 KB

0x01.md

File metadata and controls

118 lines (110 loc) · 5.45 KB
Raw

常见数据结构的ADT类型

线性表

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

栈

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

队列

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

串

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

树

ADT 树 tree
Data
  树是由一个根节点和若干棵子树构成。树中节点具有相同数据类型及层次关系
Operation
  InitTree(*T) 构造空树T
  DestroyTree(*T) 销毁树T
  CreateTree(*T, definition) 按definition中给出树的定义来构造树
  ClearTree(*T) 若树T存在, 则将树T清为空树
  TreeEmpty(T) 若T为空树,返回true,否则返回false
  TreeDepth(T) 返回T的深度
  Root(T) 返回T的根节点
  Value(T, cur_e) cure_e是树T中一个结点,返回此节点的值
  Assign(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有右兄弟,则返回它的右兄弟,否则返回空
  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棵子树

图

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中进行广度优先遍历，在遍历过程对每个顶点调用

习题

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

思路

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