《数据结构与算法》（25年秋季学期计算机科学技术专业-专升本）

胡捷臻、沈良忠、邓文华、沈家骏、张丹、李叶光、罗晓丹、姚家朋、李浩鹏、郭华峰

目录

  • 1 绪论
    • 1.1 绪论介绍
    • 1.2 数据结构与数据类型
      • 1.2.1 基本概念与逻辑结构
      • 1.2.2 存储结构
      • 1.2.3 数据类型
      • 1.2.4 章节小结
    • 1.3 算法及算法分析
      • 1.3.1 什么是算法
      • 1.3.2 算法描述
      • 1.3.3 算法设计目标
      • 1.3.4 算法效率分析1-基本概念
      • 1.3.5 算法效率分析2-常见时间复杂度
      • 1.3.6 算法效率分析3-最好、平均、最坏时间复杂度
      • 1.3.7 算法空间复杂度
    • 1.4 课程讨论说明
    • 1.5 章节测验
    • 1.6 PTA题目专场
      • 1.6.1 PTA题目专场-基础编程专题
      • 1.6.2 PTA题目专场--数组专题
  • 2 线性表
    • 2.1 线性表介绍
    • 2.2 线性表定义
    • 2.3 顺序表
    • 2.4 链表
      • 2.4.1 链表-基本概念
      • 2.4.2 链表-基本操作
      • 2.4.3 链表插入操作
      • 2.4.4 链表删除操作
      • 2.4.5 建立单链表(头插法、尾插法)
      • 2.4.6 双链表、循环链表
    • 2.5 线性表的应用-表的自然连接
    • 2.6 有序表
      • 2.6.1 有序表的插入
      • 2.6.2 有序表的归并
    • 2.7 综合练习：QQ联系人列表
    • 2.8 章节测验
    • 2.9 PTA题目专场
      • 2.9.1 PTA题目专场-顺序表删除结点
      • 2.9.2 PTA题目专场-链表删除结点
      • 2.9.3 PTA题目专场-有序链表插入
  • 3 栈与队列
    • 3.1 栈
      • 3.1.1 栈的定义
      • 3.1.2 顺序栈
      • 3.1.3 链栈
      • 3.1.4 章节讨论1：栈与递归
    • 3.2 队列
      • 3.2.1 队列的定义
      • 3.2.2 顺序队列
      • 3.2.3 链队列
      • 3.2.4 章节讨论2：队列及其应用
    • 3.3 章节测验
    • 3.4 PTA题目专场
      • 3.4.1 PTA题目专场-括号匹配
      • 3.4.2 PTA题目专场-迷宫
      • 3.4.3 PTA题目专场-递归应用基础
  • 4 树和二叉树
    • 4.1 树的基本概念与性质
    • 4.2 树遍历与存储结构
    • 4.3 二叉树
      • 4.3.1 二叉树的基本概念
      • 4.3.2 二叉树存储结构
      • 4.3.3 二叉树递归遍历
      • 4.3.4 非递归遍历及层次遍历
      • 4.3.5 二叉树遍历应用
      • 4.3.6 二叉树的构造
      • 4.3.7 二叉树线索化
    • 4.4 二叉树的应用-哈夫曼树
      • 4.4.1 哈夫曼树
      • 4.4.2 哈夫曼树算法实现
    • 4.5 本章小结
    • 4.6 章节测试
    • 4.7 PTA题目专场
      • 4.7.1 PTA题目专场-后与中序输出先序
      • 4.7.2 PTA题目专场-二叉树实现表达式求值
  • 5 图
    • 5.1 图的基本概念与存储结构
    • 5.2 图的遍历
    • 5.3 生成树和最小生成树-普里姆算法
    • 5.4 生成树和最小生成树-克鲁斯卡尔算法
    • 5.5 最短路径和Dijkstra算法
    • 5.6 拓扑排序
    • 5.7 AOE网与关键路径
    • 5.8 章节讨论1：图的基本概念
    • 5.9 章节讨论2：图的遍历与最短路径
    • 5.10 章节讨论3：拓扑排序、关键路径
    • 5.11 章节测验
    • 5.12 PTA题目专场
      • 5.12.1 PTA题目专场-MagicPig密室出逃
      • 5.12.2 PTA题目专场-列出连通集
  • 6 查找
    • 6.1 基本概念
    • 6.2 线性表查找
      • 6.2.1 顺序查找
      • 6.2.2 二分查找
      • 6.2.3 分块查找
      • 6.2.4 章节讨论1：加速查找
    • 6.3 树表查找
      • 6.3.1 二叉排序树--查找
      • 6.3.2 二叉排序树--插入和生成
      • 6.3.3 二叉排序树--结点删除
      • 6.3.4 AVL树--定义
      • 6.3.5 AVL树--插入与调整
      • 6.3.6 AVL树--结点删除
      • 6.3.7 章节讨论2：外部查找
    • 6.4 哈希表的查找
      • 6.4.1 构造哈希函数
      • 6.4.2 哈希冲突的解决方法
      • 6.4.3 章节讨论3：查找的应用
    • 6.5 本章小结
    • 6.6 章节测验
    • 6.7 PTA题目专场
      • 6.7.1 PTA题目专场-整型关键字的散列映射
      • 6.7.2 PTA题目专场-树种统计
  • 7 排序
    • 7.1 排序的基本概念
    • 7.2 插入排序
    • 7.3 快速排序
      • 7.3.1 快速排序1-基本算法与实现
      • 7.3.2 快速排序2-递归调用树与性能分析
      • 7.3.3 快速排序3-总结与拓展
    • 7.4 堆排序
      • 7.4.1 堆排序1-基本概念
      • 7.4.2 堆排序2-算法
      • 7.4.3 堆排序3-建堆与总结
    • 7.5 归并排序
      • 7.5.1 归并排序1-简介、一次归并及其实现
      • 7.5.2 归并排序2-归并排序算法实现及总结
    • 7.6 基数排序
    • 7.7 排序总结
    • 7.8 章节讨论：排序综合
    • 7.9 章节测验
    • 7.10 PTA题目专场-互评成绩
  • 8 数组与广义表
    • 8.1 数组的定义
    • 8.2 特殊矩阵的压缩存储
    • 8.3 广义表的基本概念
    • 8.4 章节测验
    • 8.5 PTA题目专场
      • 8.5.1 PTA题目专场-找鞍点
      • 8.5.2 PTA题目专场-上三角矩阵
      • 8.5.3 PTA题目专场-简易连连看
  • 9 字符串
    • 9.1 串的定义
    • 9.2 顺序串
    • 9.3 链串
    • 9.4 串的模式匹配—BF
    • 9.5 串的模式匹配-KMP
    • 9.6 章节测验
    • 9.7 PTA题目专场-统计子串数量
课程讨论说明

课程讨论

课程中将提供一些与课程内容相关的一些开放式讨论，分布在mooc的一些视频

通过参与这些讨论，大家可以进一步的加深对课本中的内容的理解与认识。同时，通过观看他人的讨论内容，也将进一步拓展自己的思路。因此，请大家务必参加讨论。

课程讨论纳入平时成绩的计分，请务必积极参与。