网课网站_滨州网站建设制作系统_网站友情链接查询_服务网站排名咨询

一、基本概念

• 数据结构:计算机存储、组织数据的方式.通常情况下,精心选择的数据结构可以带来最优效率的算法
  • 解决问题方法的效率跟数据的组织方式有关
  • 解决问题方法的效率跟空间的利用率有关
  • 解决问题方法的效率跟算法的巧妙程度有关
• 算法
  • 一个有限指令集
  • 接受一些输入
  • 产生输出
  • 一定在有限步骤之后终止
  • 评估算法:空间复杂度、时间复杂度

二、线性结构

• 线性表:由同类型数据元素构成有序序列的线性结构
  • 顺序存储:利用空间的连续存储顺序存放线性表的各元素
  • 链式存储:不要求逻辑上相邻的元素物理上也相邻
• 堆栈
  • LIFO后入先出

  • 类型名称:队列Stack
    数据对象集:一个有0个或多个元素的有穷线性表
    操作集
    Stack CreateStack(int MaxSize);
    int IsFull(Stack S, int MaxSize);
    void Push(Stack S, ElementType item);
    int IsEmpty(Stack S);
    ElementType Pop(Stack s);删除并返回栈顶元素

• 队列
  • FIFO先进先出

  • 类型名称:队列Queue
    数据对象集:一个有0个或多个元素的有穷线性表
    操作集
    Quque CreateQueue(int MaxSize);
    int IsFullQ(Queue Q, int MaxSize);
    void AddQ(Queue Q, ElementType item);
    int IsEmptyQ(Queue Q);
    ElementType DeleteQ(Queue Q);删除头元素并返回

三、树

• 树的表示
  • n个节点构成的有限集合
  • 树中有一个根节点R
  • 其余节点可分为m个互不相交的有限集,其中每个集合本身又是一颗树,称为子树

树的基本术语:

1、节点的度:节点的子树个数

2、树的度:树的所有节点中最大的度数

3、叶节点:度为0的节点

4、父节点:

5、子节点

6、兄弟节点:具有同一夫节点的各节点彼此为兄弟节点

7、路径和路径长度:路径所保护边的个数为路径的长度

8、祖先节点

9、节点层次:规定根节点在1层,其它任意节点的层数是夫节点层数+1

10、树的深度:树中所有节点中的最大层次就是树的深度

• 二叉树及存储
  • 种类:满二叉树、完全二叉树
  • 性质
    • 二叉树第i层最大节点树为2^(i - 1),i>= 1
    • 深度k的二叉树最大节点树为2^k - 1,k>=1
    • 叶节点个数 = 度为2的节点数 + 1
  • 存储
    • 顺序存储

      完全二叉树:按从上至下、从左至右顺序存储n个节点大的完全二叉树的节点父子关系
      1、非根节点(i>1)的夫节点序号为[i/2]
      2、节点(序号i)的左子树节点是2i(2i <= n,否则没有左子树)
      3、节点(序号i)的右子树节点是2i + 1(2i + 1<= n,否则没有右子树)一般二叉树也可采用这种结构,单会造成空间浪费

    • 链式存储

      class TreeNode{int val;TreeNode left;TreeNode right;
      }

• 二叉树的遍历
  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历
• 二叉搜索树
  • BST:非空左子树值小于根节点值;非空右子树值大于根节点树;左右都是BST
• 平衡二叉树
  • 任意节点左、右子树高度差的绝对值不超过1
• 堆
  • 优先队列:特殊的队列,取元素的顺序是依照元素的优先权

  • 类型名称:最大堆MaxHeap
    数据对象集:完全二叉树,每个节点的元素值不小于其子节点的元素值
    操作集
    MaxHeap Create(int MaxSize);
    int IsFull(MaxHeap H);
    void insert(MaxHeap H, ElementType item);
    int IsEmpty(MaxHeap H);
    ElementType DeleteMax(MaxHeap H);删除头元素并返回

• 哈夫曼树与哈夫曼编码
  • 哈夫曼树(最优二叉树):WPL最小的二叉树
  • 带权路径长度WPL:设二叉树有n节点,每叶子节点带权值Wk,从根节点到叶子节点的长度Lk,则每个叶子节点的带权路径长度之和:WPL=
  • 构造:每次把权值最小的两棵二叉树合并
  • 特点:
    • 没有度为1的节点
    • n个叶子节点的哈夫曼树共有2n - 1个节点
    • 堆同一组权值存在不同结构的哈夫曼树
  • 哈夫曼编码
• 集合(并查集)
  • 集合并、查某元素属于什么集合-判断两元素是否属于同一集合
  • 可用树结构表示集合,树的每个节点代表一个集合元素
    • 采用数组的形式进行存储

      public class unionFind{int[] father = new int[1024];public void init() {for (int i = 0; i < father.length; i++) {father[i] = i;}}public int find (int u) {if (u == father[u]) {return u;}father[u] = find(father[u]);//压缩路径}//u -> v加入并查集public void join(int u, int v) {u = find(u);v = find[v];if (u != v) {father[u] = v;}    }public boolean isSame(int u, int v) {u = find(u);v = find(v);return u == v;}}

四、图

• 图
• 图的遍历
  • DFS
  • BFS
• 建立图
  • 邻接矩阵
  • 邻接表
• 最短路径问题
  • 单源
    • 无权:BFS
    • 有权:Dijkstra
  • 多源:Floyd
• 最小生成树
  • Prim:让一颗小树长大
  • Kruskal:将森林合并成树
• 拓扑排序
  • 拓扑序:如果图中从v到w有一条有向路径,则v一定排在w之前,满足此条件的顶点序列称为拓扑序
  • 获得一个拓扑序的过程就是拓扑排序

五、排序

• 简单排序
• 希尔排序
• 堆排序
• 归并排序
• 快排
• 基数排序

六、散列查找

• 散列表
• 散列函数
• 散列冲突
  • 开放地址法:线性探测法、平方探测、双散列、再散列(扩容)
  • 分离链表法

七、其他

• KMP