集合一般被定义为：由一个或多个确定的元素所构成的整体。
列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序 ，排列而成的数据项的集合。
在编程语言中，列表最常见的表现形式有数组和链表，而我们熟悉的栈和队列则是两种 特殊类型的列表。除此之外，向列表中添加、删除元素的具体实现方式会根据编程语言 的不同而有所区分。
Last In First Out, LIFO 后进先出 插入和删除操作的一端称为栈顶(Top), 栈底(Bottom) 栈的存储结构: 1. 顺序存储; 2. 栈的链式存储; 3. 栈的应用
操作: 1. InitStack(S) 2. isEmpty(S) 3. Push(S,x) 4. Pop(S) 5. Top(S)
First In First Out, FIFO 先进先出 允许插入元素的一端称为队尾(Rear), 允许删除元素的一端称为队头(Front) 队列的存储结构: 1. 队列的顺序存储 > 循环队列, 如果非循环队列, 那么不能简单的入队修改队尾指针, 出队修改队头指针(需要移动内存内容) > 循环队列, 入队Q.rear = (Q.rear+1)%MAXSIZE, 出队Q.front = (Q.front+1)%MAXSIZE > 判断空和满状态, 1: 加个标识; 2: 空个空间(队尾下一个位置是队头指针时是满) > 如果入导致Q.rear=Q.front, 那么就是满状态; 如果出队导致Q.rear=Q.front, 那么就是空状态 2. 队列的链式存储 3. 队列的应用
操作: 1. InitQueue(Q) 2. isEmpty(Q) 3. EnQueue(Q,x) 4. DelQueue(Q) 5. FrontQue(Q)
操作: 1. StrAssign(s,t) 2. Concat(s,t) 3. StrLength(s) 4. StrCompare(s,t) 5. SubString(s,start,len)
串的存储结构: 1. 顺序存储; 2. 链式存储 串的模式匹配(子串定位): 1. 朴素的模式匹配算法(布鲁斯-福斯算法) 2. 改进的模式匹配算法(KMP算法)
特殊矩阵, 若矩阵中元素(或非0元素)的分布有一定的规律, 则称之为特殊矩阵. 常见的 特殊矩阵有对称矩阵, 三角矩阵和对角矩阵等. 对于特殊矩阵, 由于其非0元素的分布有 一定的规律, 所以可将其压缩存储在一维数组中, 并建立起每个非0元素在矩阵中的位置 与其在一维数组中的位置之间的对应关系.
对称矩阵: 若矩阵Anxn中的元素特点为aij=aji(1<=i, j<=n), 则称之为n阶对称矩阵.
三对角矩阵: k=3x(i-1)-1+j-i+1+1=2i+j=2 (1<=i, j<=n)
稀疏矩阵: 在一个矩阵中, 若非0元素的个数远远少于0元素的个数, 且非0元素的分布没有 规律, 则称之为稀疏矩阵. 对于稀疏矩阵, 存储非0元素时必须同时存储其位置(即行号和 列号), 所以三元组(i, j, aij)
广义表是线性表的推广, 是由0个或多个单元素或子表组成的有限序列. 一般记为: LS=(a1, a2, …., an) 广义表的长度是指广义表中元素的个数. 广义表的深度是指广义表展开后所含的括号的最 大层数. 广义表通常采用链式存储结构.
树是n(>=0)个结点的有限集合, 当n=0时称为空树. 树的定义是递归的, 它表明了树本身 的固有特性, 也就是一棵树由若干棵子树构成, 而子树又由更小的子树构成.
树的基本概念: 1. 双亲, 孩子和兄弟. 2. 结点的度, 一个结点的子树的个数记为该结点的度. 3. 叶子结点, 叶子结点也称为终端结点, 指度为0的结点. 4. 内部结点, 度不为0的结点, 也称为分支结点或非终端结点. 5. 结点的层次, 根为第一层. 6. 树的高度(深度), 一棵树的最大层数记为树的高度(或深度). 7. 有序(无序)树, 若将树中结点的各子树看成是从左到右具有次序的, 即不能交换, 则 称该树为有序树, 否则称为无序树.
二叉树: 1. 结点最大度为2 2. 结点的子树要区分左子树和右子树 3. 二叉树第i层(i>=1)上最多有2^i - 1个结点. 4. 高度为k的二叉树最多有2^k - 1个结点(k>=1). 5. 对于任何一棵二叉树, 若其终端结点数为n0, 度为2的结点数为n2, 则n0=n2 + 1 6. 具有n个结点的完全二叉树的深度为[log2n] + 1.
满二叉树: 若深度为k的二叉树有2^k - 1
完全二叉树: 约定编号从根结点起, 自上而下, 自左至右依次进行. 如果与满二叉树编号
一一对应, 那么称为完全二叉树.
存储结构: 顺序存储(按编号顺序存储), 链式存储结构(二叉链表-左子, 值, 右子), 三叉
链表(左子, 值, 双亲, 右子)
遍历:
先序-根结点, 左子树, 右子树
中序-左子树, 根结点, 右子树
后序-左子树, 右子树, 根结点
线索二叉树: 可以直接得到结点在任一遍历序列中的前驱和后继. 二叉链表中添加ltag和
rtag标志, 0为孩子, 1为直接前驱或后继.
访问线索二叉树: rtag==1, 则p->rchild即指向其后继结点.
rtag==0, 则后缀必然是其右子树中进行遍历得到的第一个结点.
线索链表
线索-指向前驱和后继的指针
线索二叉树
线索化
最优二叉树(哈夫曼树): 它是一类带权路径长度最短的树.
路径: 是从树中一个结点到另一个结点之间的通路.
路径长度: 路径上的分支数目.
树的路径长度: 是从树根到每一个叶子之间的路径长度之和.
结点的带权路径长度: 为从该结点到树根之间的路径长度与该结点权值的乘积.
树的带权路径长度: 为树中所有叶子结点的带权路径长度之和.
哈夫曼编码: 左为0, 右为1. 选取了一个叶子结点后, 重复从根结点开始.
树的存储: 双亲表示法; 孩子表示法; 孩子兄弟表示法
树的遍历: 先根遍历; 后根遍历
森林遍历: 先序遍历; 中序遍历
树, 森林, 二叉树之间的相互转换
有向图: 图中每条边都是有方向的, 有向边也称为弧, 起点称为弧尾, 终点称为弧头. 无向图: 图中每条边都是无方向的 完全图: 若一个无向图具有n个顶点, 而每一个顶点与其他n-1个顶点之间都有边, n(n-1)/2条边. 度, 出度和入度: 顶点v的度是指关联于该顶点的边的数目, 记作D(v). 顶点的入度是以该顶点 为终点的有向边的数目; 顶点的出度指以该顶点为起点的有向边的数目. 路径: 路径长度是路径上边或弧的数目; 第一个顶点和最后一个顶点相同的路径称为回路或 环; 若一条路径上除了起点和终点可以相同外, 其余顶点均不同, 则称其为简单路径. 子图: G=(V,E) G’=(V’, E’) V’属于V, E’属于E, 则G’是G的子图 连通图与连通分量: 无向图中- 两点间有路径就是连通的; 每个点间都是连通的就是连通图; 无向图G的极大连通子图称为G的连通分量 强连通图与强连通分量: 有向图中 - 每两个点都有来加路径就是强连通图; 有向图中的极大 连通子图称为有向图的强连通分量. 网: 边(或弧)带权值的图称为网. 有向树: 如果一个有向图恰有一个顶点的入席为0, 其余顶点的入度均为1, 则是一个棵有向树.
图的存储结构: 邻接矩阵表示法 0, 1 表示有无边; 无限和权值表示网的有无边 邻接链表表示法 每个结点都建一个单链表;
图的遍历 深度优先搜索(Depth First Search, DFS), 邻接矩阵遍历时间为O(n^2); 邻接链表遍历时间为O(n+e) 广度优先搜索(Breadth First Search, BFS), 先访问优后访问, 一般引入队列来保存已访问过的顶点序列
生成树是该图的极小连通子图
最小生成树: 连通网中, 边是带权值, 生成树的各边也带权值, 因此把生成树各边的权值总和 称为生成树的权, 把权值最小的生成树称为最小生成树.
最小生成树求解算法: 普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法