数据结构

熊昌泰

目录

  • 1 绪论
    • 1.1 课程概述
    • 1.2 什么是数据结构
      • 1.2.1 数据结构的基本概念
      • 1.2.2 抽象数据类型
    • 1.3 什么是算法
      • 1.3.1 算法的定义及性能分析（上）
      • 1.3.2 算法的定义及性能分析（下）
    • 1.4 章节测验
    • 1.5 学习笔记
  • 2 线性表之顺序表
    • 2.1 本章学习目标
    • 2.2 顺序表
      • 2.2.1 案例引入—手机通讯录系统
      • 2.2.2 线性表及顺序存储
      • 2.2.3 顺序表的定义及初始化
      • 2.2.4 顺序表的插入操作
      • 2.2.5 顺序表的删除操作
      • 2.2.6 顺序表的其他操作
      • 2.2.7 编程实现—手机通讯录顺序结构及相关操作
    • 2.3 章节测验
  • 3 线性表之链表
    • 3.1 本章学习目标
    • 3.2 链表
      • 3.2.1 案例引入-手机通讯录系统的设计与实现
      • 3.2.2 单链表的基本概念
      • 3.2.3 单链表的创建方式
        • 3.2.3.1 头插法建单链表
        • 3.2.3.2 尾插法建单链表
      • 3.2.4 单链表的插入及删除操作
      • 3.2.5 单链表的其他操作
      • 3.2.6 编程实现-手机通讯录链式结构及相关操作的设计与实现
    • 3.3 章节测验
  • 4 栈
    • 4.1 本章学习目标
    • 4.2 栈
      • 4.2.1 案例引入-手机计算器的简单表达式求值问题
      • 4.2.2 栈的基本概念
      • 4.2.3 栈的顺序存储及操作
      • 4.2.4 栈的链式存储及操作
      • 4.2.5 栈与递归
      • 4.2.6 简单表达式求值的过程分析
      • 4.2.7 简单表达式求值的算法分析
      • 4.2.8 编程实现-手机计算器的简单表达式求值的设计与实现
    • 4.3 章节测验
  • 5 队列
    • 5.1 本章学习目标
    • 5.2 队列
      • 5.2.1 案例引入 -银行排队叫号问题
      • 5.2.2 队列的基本概念
      • 5.2.3 队列的顺序存储
      • 5.2.4 利用循环队列实现银行排队
      • 5.2.5 队列的链式存储
      • 5.2.6 利用链队列实现银行排队
      • 5.2.7 编程实现-银行排队问题的设计与实现
    • 5.3 章节测验
  • 6 串
    • 6.1 本章学习目标
    • 6.2 串
      • 6.2.1 案例引入-文本处理问题研究
      • 6.2.2 串的基本概念与存储
      • 6.2.3 串的模式匹配-BF算法
      • 6.2.4 串的模式匹配-KMP算法介绍
      • 6.2.5 串的模式匹配-KMP算法分析
      • 6.2.6 编程实现-基于顺序串的文本处理问题的设计与实现
    • 6.3 章节测验
  • 7 树和二叉树
    • 7.1 本章学习目标
    • 7.2 概述
    • 7.3 树的基本概念
    • 7.4 树的存储与遍历
    • 7.5 二叉树的基本概念
    • 7.6 二叉树的基本性质
    • 7.7 二叉树的存储结构
    • 7.8 二叉树的先序遍历
    • 7.9 二叉树的中序遍历
    • 7.10 二叉树的后序及层次遍历
    • 7.11 二叉树的基本运算与实现（上）
    • 7.12 二叉树的基本运算与实现（中）
    • 7.13 二叉树的基本运算与实现（下）
    • 7.14 由遍历序列构造二叉树
    • 7.15 树与二叉树的转换
    • 7.16 章节测验
  • 8 哈夫曼树
    • 8.1 本章学习目标
    • 8.2 哈夫曼编码简介
    • 8.3 哈夫曼树
    • 8.4 哈夫曼编码的案例分析
    • 8.5 构造哈夫曼树的算法分析（上）
    • 8.6 构造哈夫曼树的算法分析（下）
    • 8.7 哈夫曼编码算法分析
    • 8.8 编程实现-哈夫曼编码和译码的设计与实现
  • 9 图的定义、存储及遍历
    • 9.1 本章学习目标
    • 9.2 案例引入-公园导游系统与景点介绍问题
    • 9.3 图的基本概念
    • 9.4 图的存储-邻接矩阵
    • 9.5 图的存储-邻接表
    • 9.6 基于邻接矩阵的公园导览图存储
    • 9.7 编程实现-公园导览图的存储与实现
    • 9.8 案例引入-公园导游系统与游览线路问题
    • 9.9 图的遍历-深度优先
    • 9.10 图的遍历-广度优先
    • 9.11 基于深度优先遍历的公园图遍历
    • 9.12 编程实现-公园导游系统游览线路规划
    • 9.13 章节测验
  • 10 图的最小生成树
    • 10.1 本章学习目标
    • 10.2 案例引入-公园导游系统与管道修建问题
    • 10.3 最小生成树的概念
    • 10.4 最小生成树-Prim算法
    • 10.5 最小生成树-Kruskal算法
    • 10.6 解决方案- 基于Prim算法的公园管道修建方案
    • 10.7 编程实现-公园管道修建方案的设计与实现
    • 10.8 章节测验
  • 11 图的最短路径
    • 11.1 本章学习目标
    • 11.2 案例引入-公园导游系统与景点间最短路径问题
    • 11.3 最短路径的概念
    • 11.4 最短路径-Dijkstra算法
    • 11.5 最短路径-Floyd算法
    • 11.6 解决方案-  基于Dijkstra算法的公园两景点间的最短路径
    • 11.7 编程实现-公园两景点之间的最短路径的计算与实现
    • 11.8 章节测验
  • 12 查找
    • 12.1 本章学习目标
    • 12.2 案例引入-手机通讯录的检索系统
    • 12.3 查找的基本概念
    • 12.4 线性表查找
      • 12.4.1 二分查找
      • 12.4.2 分块查找
    • 12.5 树表查找
      • 12.5.1 二叉查找树
      • 12.5.2 平衡二叉树*
    • 12.6 哈希表查找
      • 12.6.1 哈希表的基本概念
      • 12.6.2 构造哈希函数
      • 12.6.3 解决哈希冲突
    • 12.7 解决方案- 手机通讯录的查找操作
    • 12.8 编程实现-手机通讯录检索程序的设计与实现
    • 12.9 章节测验
  • 13 排序
    • 13.1 本章学习目标
    • 13.2 案例引入-手机通讯录的排序问题
    • 13.3 内排序的基本概念
    • 13.4 交换类排序
    • 13.5 插入类排序
    • 13.6 选择类排序
    • 13.7 归并排序
    • 13.8 基数排序
    • 13.9 解决方案- 手机通讯录的排序操作
    • 13.10 编程实现-手机通讯录的排序设计与实现
    • 13.11 章节测试
  • 14 总复习
    • 14.1 数据结构复习3
    • 14.2 数据结构复习
本章学习目标

本章学习目标

1. 掌握最短路径的基本概念；

2. 掌握计算单源最短路径的Dijkstra算法；

3. 掌握计算多源最短路径的Floyd算法；