【数据结构】笔记

发表于 更新于 分类于 阅读次数： 本文字数： 1.6k 阅读时长 ≈ 6 分钟

学习浙江大学【数据结构】做的笔记。

第二讲 线性结构

2.1 线性表及其实现

多项式表示问题的启示：
1.同一个问题可以有不同的表示（存储）方法
2.有一类共性问题：有序线性序列的组织和管理

线性表（Linear List）：由同类型 数据元素 构成 有序序列 的线性结构

  • 表中元素个数称为线性表的 长度
  • 线性表没有元素时，称为 空表
  • 表起始位置称为 表头，表结束位置称为 表尾

线性表的基本操作：

  • 创建：创建一个空表
  • 查找：查找某个元素是否在线性表中
  • 插入：在某个位置插入一个元素
  • 删除：删除某个位置上的元素

广义表（Generalized List）

  • 广义表是线性表的推广
  • 对于线性表而言，n 个元素都是基本的单元素
  • 广义表中，这些元素不仅可以是单元素也可以是另一个广义表

多重链表

多重链表：链表中的节点可能同时隶属于多个链

  • 多重链表中节点指针域会有多个，如前面例子包含了 Next 和 SubList 两个指针域
  • 但包含两个指针域的链表并不一定是多重链表，比如 双向链表不是多重链表

多重链表有广泛的用途：
基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储

2.2 堆栈

后缀表达式

后缀表达式求值策略：从左向右“扫描”，逐个处理运算数和运算符号

堆栈的抽象数据类型描述

堆栈（Stack）：具有一定操作约束的线性表，只在一端（栈顶，Top）做插入、删除

  • 插入数据：入栈（Push）
  • 删除数据：出栈（Pop）
  • 后入先出：Last In First Out(LIFO)

2.3 队列

队列（Queue）：具有一定操作约束的线性表。插入和删除操作：只能在一端插入，而在另一端删除。

  • 数据插入：入队
  • 数据删除：出队
  • 先来先服务
  • 先进先出：FIFO

第三讲 树（上）

3.1 树与树的表示

查找：根据某个给定关键字 K， 从集合 R 中找出关键字 K 相同的记录

  • 静态查找：集合中记录是固定的，没有插入和删除操作，只有查找
  • 动态查找：集合中记录是动态的，除查找，还可能发生插入和删除

树的一些基本术语

  1. 结点的度（Degree）：节点的字树个数
  2. 树的度：树的所有节点中最大的度数
  3. 叶节点（Leaf）：度为 0 的节点
  4. 父节点（Parent）：有子树的节点是其子树的根节点的父节点
  5. 子节点（Child）：若 A 结点是 B 结点的父节点，则称 B 结点是 A 结点的子结点；子结点也称孩子结点
  6. 兄弟节点（Sibling）：具有同一父节点的各结点彼此是兄弟节点
  7. 路径和路径长度：从结点 n1 到 nk 的路径为一个节点序列 n1，n2，n3，……，nk， ni 是 ni+1 的父结点。路径所包含边的个数为路径的长度。
  8. 祖先节点（Ancestor）：沿树根到某一结点路径上的所有节点都是这个结点的祖先节点。
  9. 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙。
  10. 结点的层次（Level）：规定根节点在 1 层，其它任一节点的层数是其父结点的层数加 1 。
  11. 树的深度（Depth）：树种所有结点中的最大层次是这棵树的深度。

3.2 二叉树及其存储结构

二叉树 T：一个有穷的结点集合。

  • 这个集合可以为空。
  • 若不为空，则它是由根结点和称为其左子树 TL 和右字树 TR 的两个不相交的二叉树组成。

二叉树几个重要性质

  • 一个二叉树第 i 层的最大结点数为： 2i-1，i ≥ 1
  • 深度为 k 的二叉树有最大节点总数为： 2k-1，k ≥ 1
  • 对任何非空二叉树 T ，若 n0 表示叶节点个数、 n2 是度为 2 的非叶节点个数，那么两者满足关系 n0 = n2 + 1 。

3.3 二叉树的遍历

先序遍历

遍历过程为：
1.访问根节点
2.先序遍历其左子树
3.先序遍历其右字树

中序遍历

遍历过程为：
1.中序遍历其左子树
2.访问根节点
3.中序遍历其右字树

后序遍历

遍历过程为：
1.后序遍历其左子树
2.后序遍历其右字树
3.访问根节点

先序、中序和后序遍历过程：遍历过程中经过节点的路线一样，真是访问各结点的时机不同。

第四讲 树（中）

4.1 二叉搜索树

二叉搜索树（BST, Binary Search Tree），也称二叉排序树或二叉查找树。

二叉搜索树：一棵二叉树，可以为空：如果不为空，满足以下性质：
1.非空左子树的所有键值小于其根节点的键值。
2.非空右字树的所有键值大于其根节点的键值。
3.左、右字树都是二叉搜索树。

第五讲 树（下）

5.1 堆

优先队列（Priority Queue）：特殊的“队列”，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

5.2 哈夫曼树与哈夫曼编码

哈夫曼树的特点：

  • 没有度为 1 的结点；
  • n 个叶子结点的哈夫曼树共有 2n - 1 个结点；
  • 哈夫曼树的任意非叶节点的左右字树交换后仍是哈夫曼树；

第六讲 图（上）

6.1 什么是图

什么是“图”（Graph）

  • 表示“多对多”的关系
  • 包含：
  • 一组顶点：通常用 V（Vertex）表示顶点集合
  • 一组边：通常用 E（Edge）表示边的集合