数据结构概述

程序设计 = 数据结构 + 算法 1 数据结构 数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 1.1 基本概念 数据：能别计算机识别、处理的符号集合 数据对象：性质相同的数据元素的集合，是数据的子集。 数据元素：组成数据的、有一定意义的基本单位。通常作为整体被计算机处理。 数据项：数 ...
2020-03-20 01 数据结构与算法 > 数据结构 > 01 数据结构

栈与队列

一、栈 1 基本概念 栈：是限定仅在表尾进行插入和删除操作的线性表。后进先出LIFO 栈顶(top)：允许插入和删除的一端 核底(bottom)：另一端 栈的引入简化了程序设计，使关注范围缩小，聚焦于要解决的问题核心。 2 栈的顺序存储结构 - 顺序栈 1）存储结构 栈是线性表的特例，栈的 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

线性表（List）

一、线性表的定义和基本操作 1）定义 线性表：零个或多个数据元素的有序排列。 除第一个元素外，每个元素有且只有一个直接前驱元素；初最后一个元素外，每个元素有且只有一个直接后继元素。 2）基本操作 InitList：初始化 ListEmpty：判空 ClearList：清空 GetElem：取值 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

数组和广义表

1 数组的概念、多维数组的实现 1）数组的概念 数组的特点：元素数目固定；下标有界。 数组的操作：按照下标进行读写。 2）多维数组的实现 行优先顺序 存储时先按行从小到大的顺序存储，在每一行中按列号从小到大存储。 列优先顺序 存储时先按列从小到大的顺序存储，在每一列中按行号从小到大存储。 2 矩 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

串（string）

1 基本概念 串：是由零个或多个字符组成的优先序列，又名叫字符串。 本质是一种线性表的扩展，但更多的是关注子串的应用问题 子串在主串中的位置就是子串的第一个字符在主串中的序号。 字符编码 ASCII：7位 拓展 ASCII：8位 Unicode：16位 串的比较 挨个比较字符，以第一个不同 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

树与二叉树

一、树的基本概念 树：是 n ( n>=0 ) 个结点的有限集。 n = 0 时称为空树。 在任意一棵非空树中: 有且仅有一个根结点 当 n > 1 时，其余结点可分为一个或多个互不相交的有限集。 其中每一个集合本身又是一棵树，并且称为根的子树。 1、结点分类 结点的度：结点 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

堆

堆（Heap）是一种特别的树状数据结构：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。分为最小堆和最大堆。 二叉堆 左倾堆 斜堆 二项堆 斐波那契堆 索引堆 Treap 树堆 1、二叉堆 二叉堆是完全二元树或者是近似完全二元树，按照数 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

图

一、图的基本概念 图：由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中，G 表示一个图，V 是图 G 中顶点的集合。E 是图 G 中边的集合。 1、各种图定义 无向边：若顶点 $V_i$ 到 $V_j$，之间的边没有方向，则称这条边为无向边(Edge)。 用无序偶对 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构

红黑树

1、红黑树定义 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。可以在 O(logn) 时间内做查找，插入和删除。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。 满足如下条件： 每 ...
2019-12-25 01 数据结构与算法 > 数据结构 > 01 数据结构