数据结构与算法

杨顺民

目录

  • 1 1 绪论
    • 1.1 1.0 课程介绍
      • 1.1.1 1.0.1 课程简介
      • 1.1.2 1.0.2 为什么学？
      • 1.1.3 1.0.3 学什么？如何学？
      • 1.1.4 1.0.4 课程目标和考核方式
      • 1.1.5 1.0.5 实验示例_C语言函数
      • 1.1.6 1.0.6 作业
      • 1.1.7 1.0.7 本章内容和目标
    • 1.2 1.1 数据结构的基本概念和术语
    • 1.3 1.2 什么是数据结构
    • 1.4 1.3 数据结构的研究内容
      • 1.4.1 1.3.1 示例_逻辑结构和物理结构
    • 1.5 1.4 抽象数据类型的表示和实现
      • 1.5.1 1.4.1 引用
      • 1.5.2 1.4.2 抽象数据类型
        • 1.5.2.1 1.4.2.1 示例_抽象数据类型
        • 1.5.2.2 1.4.2.2 实验示例_ 指针和动态内存分配
        • 1.5.2.3 1.4.2.3 实验示例_结构体和typedef
        • 1.5.2.4 1.4.2.4 实验示例_C语言综合应用
    • 1.6 1.5 算法和算法分析
      • 1.6.1 1.5.1 算法与数据结构的关系
        • 1.6.1.1 1.5.1.1 示例_算法与数据结构的关系
      • 1.6.2 1.5.2 算法的要求和效率
      • 1.6.3 1.5.3 时间复杂度
        • 1.6.3.1 1.5.3.1 示例_时间复杂度
        • 1.6.3.2 1.5.3.2 实验示例_时间复杂度
      • 1.6.4 1.5.4 空间复杂度
      • 1.6.5 1.5.5 本章总结
    • 1.7 1.6 第一章作业
    • 1.8 实验示例_实验1讲解_1
    • 1.9 实验示例_实验1讲解_2
  • 2 2 线性表
    • 2.1 2.0 本章内容及目标
    • 2.2 2.1 线性表的类型定义
      • 2.2.1 2.1.1 线性表的定义及特点
      • 2.2.2 2.1.2 线性表抽象数据类型定义
      • 2.2.3 2.1.3 算法描述中什么时候使用引用
      • 2.2.4 2.1.4 示例_集合的合并
      • 2.2.5 2.1.5 示例_有序集合的合并
    • 2.3 2.2 线性表的顺序表示与存储
      • 2.3.1 2.2.1 顺序表的描述和基本操作
      • 2.3.2 2.2.2 指针和数组的关系
      • 2.3.3 2.2.3 顺序表的插入操作
      • 2.3.4 2.2.4 顺序表的删除和其它操作
      • 2.3.5 实验示例_顺序表的应用
    • 2.4 2.3 线性表的链式表示与存储
      • 2.4.1 2.3.1 单链表
        • 2.4.1.1 2.3.1.1 单链表的定义
        • 2.4.1.2 2.3.1.2 单链表存储结构实现
        • 2.4.1.3 2.3.1.3 单链表的查找
        • 2.4.1.4 2.3.1.4 单链表的插入
        • 2.4.1.5 2.3.1.5 单链表的删除
        • 2.4.1.6 2.3.1.6 单链表的建立
        • 2.4.1.7 2.3.1.7 示例_有序单链表的合并
        • 2.4.1.8 2.3.1.8 静态链表
        • 2.4.1.9 2.3.1.9 小测验
      • 2.4.2 2.3.2 循环链表
      • 2.4.3 2.3.3 双向循环链表
    • 2.5 2.4 一元多项式的表示及相加
    • 2.6 实验示例---单链表的应用
    • 2.7 第二章总结
  • 3 3 栈和队列
    • 3.1 3.0 本章内容及目标
    • 3.2 3.1 栈
      • 3.2.1 3.1.1 栈的定义
      • 3.2.2 3.1.2 栈的顺序表示和实现_1
      • 3.2.3 3.1.3 栈的顺序表示和实现_2
      • 3.2.4 3.1.4 链栈的表示
      • 3.2.5 实验示例--顺序栈的基本操作
    • 3.3 3.2 栈的应用
      • 3.3.1 3.2.1 示例_数值转换
      • 3.3.2 3.2.2 示例_表达式求值
      • 3.3.3 实验示例--栈的应用实例
    • 3.4 3.3 队列
      • 3.4.1 3.3.1 队列的定义
      • 3.4.2 3.3.2 队列的链式表示和实现
      • 3.4.3 3.3.3 循环队列的表示和实现
      • 3.4.4 实验示例--链式队列的基本操作
  • 4 4 串
    • 4.1 4.0 本章内容及目标
    • 4.2 4.1 串的类型定义
      • 4.2.1 示例_串的基本操作的应用
    • 4.3 4.2 串的表示和实现
      • 4.3.1 4.2.1 串的定长顺序存储
      • 4.3.2 4.2.2 串的堆分配存储
      • 4.3.3 4.2.3 串的块链存储
    • 4.4 4.3 串的模式匹配算法
      • 4.4.1 4.3.1 BF算法
      • 4.4.2 4.3.2 KMP算法
    • 4.5 4.4 实验示例_串的存储结构应用
    • 4.6 实验示例_BF算法的应用
  • 5 5 数组和广义表
    • 5.1 5.0 本章内容及目标
    • 5.2 5.1 数组的定义
    • 5.3 5.2 数组的表示和实现
    • 5.4 5.3 矩阵的压缩存储
      • 5.4.1 5.3.1 对称矩阵的压缩存储
      • 5.4.2 5.3.2~3 三角矩阵和对角矩阵的压缩存储
      • 5.4.3 5.3.4 稀疏矩阵的压缩和转置_1
      • 5.4.4 5.3.4 稀疏矩阵的压缩和转置_2
      • 5.4.5 5.3.5 实验示例1--矩阵初始化及转置运算
      • 5.4.6 5.3.6 实验示例2--稀疏矩阵的压缩存储
    • 5.5 5.4 广义表的类型定义
    • 5.6 5.5 广义表的表示方法
  • 6 6 树和二叉树
    • 6.1 6.1 树的定义和基本术语
    • 6.2 6.2 二叉树
      • 6.2.1 6.2.1 二叉树的定义和性质
      • 6.2.2 6.2.2 二叉树的存储结构
    • 6.3 6.3 遍历二叉树和线索二叉树
      • 6.3.1 6.3.1 二叉树的遍历
      • 6.3.2 6.3.2 二叉树的遍历算法和建树算法
      • 6.3.3 6.3.3 线索二叉树
      • 6.3.4 6.3.4实验示例_二叉树的遍历算法
    • 6.4 6.4 树和森林
    • 6.5 6.5 赫夫曼树及其应用
      • 6.5.1 6.5.1 赫夫曼树的构造
      • 6.5.2 6.5.2 赫夫曼编码算法
      • 6.5.3 6.5.3哈夫曼树及其应用（1）
      • 6.5.4 6.5.4哈夫曼树及其应用（2）
  • 7 7 图
    • 7.1 7.0 本章内容及目标
    • 7.2 7.1 图的抽象数据类型
    • 7.3 7.2 图的存储结构
      • 7.3.1 7.2.1 图的邻接矩阵存储表示
      • 7.3.2 7.2.2 图的邻接表存储表示
      • 7.3.3 7.2.3 图的十字链表存储表示
      • 7.3.4 实验示例-图的创建
    • 7.4 7.3 图的遍历
      • 7.4.1 7.3.1 图的深度优先搜索遍历
      • 7.4.2 7.3.2 图的广度优先搜索遍历
    • 7.5 7.4 图的最小生成树
      • 7.5.1 7.4.1 连通图的生成树
      • 7.5.2 7.4.2 最小代价生成树
        • 7.5.2.1 7.4.2.1 普里姆算法
        • 7.5.2.2 7.4.2.2 克鲁斯卡尔算法
        • 7.5.2.3 实验实例-最小生成树
    • 7.6 7.5 拓扑排序
    • 7.7 7.6 关键路径
    • 7.8 7.7 最短路径
      • 7.8.1 7.7.1 迪杰斯特拉算法
      • 7.8.2 7.7.2 弗洛伊德算法
      • 7.8.3 实验实例-迪杰斯特拉算法实例第一部分
      • 7.8.4 实验实例-迪杰斯特拉算法实例第二部分
  • 8 8 查找
    • 8.1 8.1 查找的基本概念
    • 8.2 8.2 静态查找表
    • 8.3 8.3 动态查找表
      • 8.3.1 8.3.1 二叉排序树
        • 8.3.1.1 实验示例_二叉排序树
      • 8.3.2 8.3.2 平衡二叉树
    • 8.4 8.4 哈希表
      • 8.4.1 8.4.1 哈希表的定义
      • 8.4.2 8.4.2 哈希表的构建方法
      • 8.4.3 8.4.3 哈希表解决冲突的方法
  • 9 9 排序
    • 9.1 9.1 内部排序的分类和概述
    • 9.2 9.2 插入排序
    • 9.3 9.3 交换排序
      • 9.3.1 9.3.1交换排序应用实例
    • 9.4 9.4 其它排序
  • 10 学生作品展示区
    • 10.1 线性结构
      • 10.1.1 王彦伟同学的字符画
    • 10.2 树结构
      • 10.2.1 王彦伟同学的一笔画
      • 10.2.2 张佳豪同学的扫雷
    • 10.3 图结构
      • 10.3.1 王彦伟同学的图着色问题
实验示例---单链表的应用