数据结构

线性表

$$定义线性表为n(n>=0)个数据元素的一个有限数列。记作$$

$$L=（a_1,a_2,...a_i,a_{i+1},...,a_n)$$

$$其中，L是表名，a_i是表中的数据元素，n是表中的元素的个数，如果n=0，则L为空表$$

$$线性表的第一个元素称为表头(head),最后一个元素称为表尾(tail)$$

线性表的特点

1. 线性表是一个有限数列，意味着表中的元素的个数有限，且各个表中元素三相继排列的，每两个相邻的元素之间都有.
2. 对顺序表中的所有元素,即可以进行顺序访问,也可以随即访问.
3. 顺序表可以用C语言的一维数组实现
4. 线性表存储数组的数据类型就是顺序表中元素的数据类型，数组的大小要大于等于顺序表的长度
5. 顺序表中的第i个元素被存储在数组下表为i-1的位置上

栈

栈的概念

栈是只允许在表的一端插入和删除的线性表

• 栈顶：允许删除与插入
• 栈底：不允许删除与插入
• 空栈： 没有元素

栈的操作

void InitStack(Stack& S)
    前提：无
    结果：为栈S分配空间，并对各数据成员赋值
int Push(Stack&S,SElemType x)
    前提： 栈S已经存在且未满
    结果：新元素x进栈S并成为新的栈顶
int Pop(Stack&S,SElemType& x)
    前提:栈S已经存在且栈非空
    结果：若栈S空，则返回0,x不可用，否则栈顶元素推栈，退出元素由x返回，函数返回1
int GetTop(Stack&S,SelemType&x)
    前提：栈S已经存在且栈非空
    操作结果：若栈S空，则函数返回0,x不可用,否则由引用型参数x返回栈顶元素的值但不退栈，函数返回1
int StackEmpty(Stack& S)
     前提:栈S已经存在
     结果：函数测试栈S空否，若栈空，则返回1,否则函数返回0
int StackFull(Stack&S)
     前提：栈S已经存在
     结果：函数测试栈S满否，若栈满，则函数返回1,否则函数返回0
int StackSize(Stack&S)
     前提：栈S已存在
     结果：函数返回栈S的长度，即栈S中元素个数
    

队列

队列的概念

队列是一种限定存取位置的线性表。它只允许在表中一端插入，在另一端删除。

• 队尾：允许插入的一端
• 队头：允许删除的一段

队列的主要操作

void InitQueue(Queue& Q)
 前提：无
 结果：队列置空，并对各数据成员赋初值
int Enqueue(Queue&Q,QElemType x)
 前提：队列Q已存在且未满
 结果： 新元素x进队列Q并成为新的队尾
int Dequeue(Queue& Q,QElemType &X)
 前提：队列Q已经存在且为空
 结果：若队列Q空，则函数返回0,x不可用，否则队列Q的队头元素退队，退出元素由x返回，函数返回1.
int GetFront(Queue&Q,QElemType&x)
 前提：队列Q已经存在且队列非空
 结果：若队列Q空，则函数返回0,x不可用；否则由引用参数x返回队列元素的值但不退出队列，函数返回1
int QueueEmpty(Queue&Q)
    前提：队列Q已存在
    结果：判队列Q空否，若队列空，则函数返回1,否则函数返回0
int QueueFull（Queue& Q)
    前提：队列Q已经存在
    结果：判队列Q满否，否队满，则函数返回1,否则函数返回0
int QueueSize(Queue&Q)
    前提：队列Q已经存在
    结果 函数返回队列Q的长度，即队列Q中的元素个数

字符串

字符串是一串文字和符号的序列

字符串的概念

$$字符串简称串，是n(n\ge 0)个字符串的一个有限序列，通常可记为$$

$$S{=}^{″}{a}_0{a}_1{a}_2...a_n-1^{″}$$

$$其基本组成元素是单个字符，字符串的长度可变$$

1. 串值和串名：串值是可以直接引用的串，如“helloworld”，一般用单引号或者双引号作为分界符括起来
2. 串长度：串中字符个数。长度为0的串为空串，长度大于零的串为非空串
3. 子串：若一个字符串不为空，从这个串中连续取出若干个字符组成的串叫做原串的子串
4. 前缀子串：从串的开始连续取出若干个字符组成的串
5. 后缀子串：从串的某一位置开始到串的最后位置连续取出若干个位置组成的串

广义表

广义表的概念

$$一个广义表元素可定义为n(n\ge 0)个元素a_0,a_1,a_2,...a_{n-1}组成的有限序列$$

$$LS=(a_0,a_1,a_2,...a_{n-1})$$

$$其中LS为表名，a_i(0\le i\le n-1)是表中元素，它或是数据元素（原子），亦或是子表$$

$$n是表的长度，即表中元素个数，长度为0的表为空表$$

$$如果n\ge 1,则称广义表的第一个元素a_0为广义表的表头，其他元素为表的表尾$$

广义表的性质

• 次序：在广义表中，各元素在表中以线性序列排列，顺序不能交换
• 有长度：广义表元素个数是一定的，不能是无限的，可以是空表
• 有深度：广义表的表元素可以是原表的子表，子表还可以是字表...因此广义表是多层次结构
• 可递归：广义表本身可以是自己的子表
• 可共享：广义表可以为其他广义表共享

树

树的概念

树的具体:家族家谱,公司的组织结构,书的章节

树的定义与术语

树的定义

$$一颗树是n(n\ge 0)个结点的有限集合,n=0为空树,非空记作$$

$$T=r,T_1,T_2...T_n$$

$$r是T的根结点，T_1,T_2...T_m是除其他结点构成的互不相交的m（m\ge 0)个子集合。$$

$$每颗子树的跟结点都有一个直接前趋（即它的上层结点)，但可以有0个或多个直接后继（即它的下层结点）。$$

$$m称为r的分支数$$

树的基本术语

$$结点：它包含数据元素的值及指向其他结点的分支指针$$

$$结点的度：是结点所拥有的子树棵树。$$

$$叶结点：即度为0的结点，又称为终端结点$$

$$分支结点：除叶结点外的其他结点，又称非终端结点$$

$$子女结点：若结点x有子树，则子树的根结点即为结点x的子女。$$

$$双亲结点：若结点x有子树，它即为子女的双亲。$$

$$兄弟结点：同一双亲的子女结点为兄弟。$$

$$祖先结点：从根结点到该结点所经分支上的所有结点$$

$$子孙结点：某一结点的子女，以及这些子女的子女都是该结点的子孙$$

$$结点间的路径：树中任一结点v_1，v_2,...,v_k到v_j,其中(v_i,v_i),(v_1,v_2),...(v_k,v_j)是树中的分支$$

$$则v_i，v_1,v_2,...v_k,v_j是v_i与v_j间的路径$$

$$结点的深度：即结点所处层次，简称结点的层次，即从根到该结点的路径上分支数加1$$

$$结点的高度：空树的高度为0,叶结点的高度为1,非叶结点的高度等于两个子女结点高度中的最大值加1$$

$$树的深度：树中距离根结点最远的结点，结点所处层次即为树的深度。空树的深度为0$$

$$只有一个根结点的树的深度为1$$

$$树的高度：树的高度等于根结点的高度$$

$$树的宽度：统计树中每一层结点个数$$

$$树的度：树中结点的度的最大值$$

$$有序树：树中结点的各树子树T_0,T_1,....是有次序的，即为有序树$$

$$无序树：树中结点的各颗子树之间的次序是不重要的，可以互换位置$$

$$森林：是m(m\ge 0)颗树的集合。$$

void InitTree(Tree&T)
    前提：无
    结果：建立一个根指针为T的空树
void ClearTree(TreeNode*& T )
    前提：树非空
    结果:将树T中所有结点释放，将树清空
position FirstChild(Tree&T,position p)
     前提：结点p是树T的结点
     结果：返回结点p的第一个子女结点地址，若无子女，则函数返回0
position NextSibing(Tree& T,position p)
        前提：结点p是树T的结点
        结果：返回结点p的下一个兄弟结点地址，若无一个兄弟，返回0
position Parent(Tree & T,position p)
        前提：结点p是树T的结点
        结果：返回结点p的双亲地址，若结点p为根，返回0
int InsertChild(Tree& T,position p,TElemType x)
        前提：树T非空且结点p为树T的结点
        结果:在结点p下插入值为x的新子女，若插入失败，函数返回0,否则函数返回1
int DeleteChild(Tree& T,position p,int i)
            前提：树T非空且结点p是树T的结点
            结果：删除结点p的第i个结点，若删除失败，则函数返回0,否则函数返回1
void DeleteSubTree(Tree &T,position i)
            前提：t是树T的结点
            结果：删除以t为根的子树的全部结点且t置为空
void Traversal(Tree &T ,position p)
            前提：树T非空且结点p是树的结点
            结果：遍历以结点p为根的子树

二叉树及其存储

二叉树的概念

二叉树的性质

二叉树的主要操作

二叉树的顺序存储表示

二叉树的链表存储表示

二叉树的遍历

二叉树的递归遍历算法

递归遍历算法的应用举例

二叉树遍历的非递归算法

堆

小根堆和大根堆

图

$$简单路径与回路：若路径上各顶点v_i,v_2,...v_m均不互相重复，则称这样的路径为简单路径。$$

$$若路径上第一个顶点v_1与最后一个顶点v_m重合，则称这样的路径为回路或环。$$

$$若回路中的路径是简单路径，则称这样的回路是简单回路$$

$$连同图与连同分量：在无向图中，从顶点v_1到顶点v_2有路径，则称顶点v_1与v_2是连同的$$

$$如果图中任意一对顶点都是连通的，则称此图是连通图。非连通图的极大连通子图叫做连通分量$$

$$强连通图与强连通分量：在有向图中，若每一对顶点v_i和v_j之间的都存在一条v_i到v_j的路径，$$

$$也存在一条从v_j到v_i的路径，则称此图是强连通图$$

$$非强连通图的极大强连通子图叫做强连通分量$$

$$生成树：一个无向连通图的生成树是它的极小连通子图，若图中含有n个顶点，则其生成树是由n-1条边构成$$

$$若是有向图，则可能得到它的由若干有向树组成的生成森林$$

图的基本操作

假设图的顶点数据的数据类型是Type,边上权值的数据类型是weight，则有如下操作
void CreateGraph(Graph&G,int n,int m)
    前提：无。
    结果从键盘输入n个顶点和m条边的信息，建立一个图
 void PrintGraph(Graph& G)
    前提：图G已存在
    结果 输出所有边和顶点的信息。
 void InitGraph(Graph& G)
    前提：图已经建立
    结果：将图的顶点数和边数的都置为0.
 int GetVertexPos(Graph& G,Type x)
    前提： 该顶点属于图的顶点集合
    结果： 从顶点的数据值找出该顶点的顶点号，如果查找失败 ，返回-1
 int NumberOfVertices(Graph& G)
    前提 ：图以及存在；
    结果： 函数返回图中当前已有的顶点数
 int NumberOfEdges(Graph& G)
    前提:图已存在
    结果：函数返回图中当前图中已有的边数
 Type GetValue(Graph& G,int i)
     前提：图已存在，且i是合法的顶点号
     结果： 函数返回顶点i的值，若i不合理则返回0
 Weight GetWeight(Graph& G.int V1,int V2)
     前提：图已经存在，且V1 ，V2是合理的顶点号，（V1,V2）是图中的边
     结果：函数返回边V1,V2所带回的权值
int FirstNeighbor(Graph& G,int v)
     前提：图已经存在，V是合理的顶点号
     结果：函数返回第一个邻接顶点V的顶点号，若无则返回-1
int NextNeighbor(Graph & G,int V，int W)
     前提：图已经存在，v和W都是合理的顶点号
     结果：函数返回顶点V的邻接顶点W后下一邻接顶点的顶点号，若无则返回-1
void InsertVertex(Graph& G,Type vertex)
    前提： 图的顶点数未到达最大顶点数
    结果： 在图中插入一个顶点vertex ,该顶点暂时没有边
void InsertEdge(Graph& G,int V1,int V2)
    前提：V1和V2都是图中的顶点，且依附于V1和V2的边还不存在
    结果：在图中插入一条边（V1,V2）
void RemoveVertex(Graph& G,int V)
    前提：图已经存在，且V是图中合理的顶点号
    结果：删去顶点V和所有关联它的边
void RemoveEdge(v                                   Grapg& G,int V1,int V2)
     前提：图已经存在，V1,V2是合理的顶点号，且（V1,V2）是合理的边
     结果：在图中删去边（V1,V2）
    

查找

查找的概念

• 查找表：查找的元素集合

  • 静态查找表：如果对表执行插入和删除操作等操作表后表结构不发生改变
  • 动态查找表：如果对表执行插入和删除等操作后，为保持较高的查找效率，结构本身要调整

• 关键码：在查找表中，每一个元素有若干个属性，其中应当有一个属性，其值可唯一地被标识

查找的算法性能分析

$$设查找表中有n个元素，查找第i(1\le i\le n),找到它的关键码比较次数是c_i$$

$$则p_i\times c_i是成功查找第i个元素可能的关键码比较次数$$

$$AS{L}_{成功}=\sum _{i=1}^n{p}_i{c}_i,\sum _{i=1}^n{P}_i=1$$

$$AS{L}_{不成功}：查找在查找表中不存在元素，还定义查找不成功的平均查找长度，它被定义在查找表中有n个元素$$

$$现在要查找表中的第n+1个元素，找到其插入元素的平均比较次数$$

顺序查找法

折半查找法

次优查找树

斐波那契查找

插值查找

二叉查找树

二叉查找树的概念

二叉查找树又称二叉排序树，它或者是一颗空树

• 每个结点都有一个作为查找依据的关键码（key），所有结点的关键码互不相同

• 左子树（如果非空)上所有结点的关键码的都小于根结点的关键码

• 右子树（如果非空）上所有结点的关键码都大于根结点的关键码

• 左子树和右子树也是二叉查找树

  如果对一个二叉查找树进行中序遍历，可以将个结点的关键码按从小到大的顺序排列

平衡二叉树

二叉树的概念

定义：左子树与右子树的高度之差的绝对值不会超过1

排序

排序的相关概念

• 数据表：它是待排序元素的有限集合

• 排序码：通常定义排序码为元素中用来标识与阿努斯，作为排序依据的属性

• 排序的确切定义：递增or递减

• 原地排序：排序过程中只使用了规模为O（1）的额外空间存储空间，排序结果仍然保留在原来的数据表内

• 排序算法的稳定性：如果在元素序列中两个元素Ri和Rj，它们的排序码Ki=Kj

  • 如果排序前Ri在Rj之前，排序后为改变，则说排序是稳定的

• 排序方法分类

  • 有序区增长：

​ 将数据表分为有序区和无序区，在排序过程中逐步扩大有序区，缩小无序区

• 有序程度增长：

​ 数据表无能明确区分有序区和无序区，随着排序过程的执行，逐步调整表中的元素的排列，

​ 使得表中有序程度不断提高，直到完全有序

• 内排序与外排序
  • 内排序：内排序是子阿排序期间数据元素全部放在内存中
  • 外排序：排序期间元素太多，不能完全放在内存中，需要按照排序要求在内存宇外存移动排序
• 静态排序与动态排序
  • 静态排序：
    • 采用顺序表存储代排序元素
    • 采用链表存储排序元素，经通过增加一个指针地址信息来改变元素之间的逻辑顺序
    • 动态排序
      • ​ 通过动态链表存储带排序元素，通过修改链接指针来改变元素之间的逻辑顺序，但表的结构不会改 变

排序算法的性能分析

• 执行时间
• 额外内存空间
  • 除使用有限的几个负责元素交换的工作单元之外，不需要使用其他额外内存空间
  • 使用链表指针或树组下标表明元素的逻辑顺序，指针或下标需要额外的内存空间
  • 需要额外的空间来存储待排序元素序列的副本或排序的中间结果

插入排序

插入排序

基于静态链表的直接插入排序

折半插入排序

希尔排序

交换排序

起泡排序

快速排序

选择排序

简单选择排序

锦标赛排序

堆排序

归并排序

二路归并排序

基数排序

MSD基数排序

LSD基数排序