数据结构

尚蕾

目录

  • 1 绪论
    • 1.1 课程简介与导学
    • 1.2 什么是数据结构
    • 1.3 基本概念和术语
    • 1.4 抽象数据类型
    • 1.5 算法与算法分析
    • 1.6 本章小结与习题
  • 2 线性表
    • 2.1 线性表的逻辑结构
    • 2.2 线性表的顺序存储和实现
      • 2.2.1 顺序表的初始化
      • 2.2.2 顺序表的插入
      • 2.2.3 顺序表的删除
      • 2.2.4 顺序表的查找
      • 2.2.5 顺序表的空满判断
    • 2.3 线性表的链式存储结构和实现
      • 2.3.1 单链表的初始化
      • 2.3.2 单链表的插入与删除
      • 2.3.3 单链表的查找
      • 2.3.4 单链表的判空
      • 2.3.5 循环单链表
    • 2.4 安全专题--线性表的应用与安全
    • 2.5 小结与练习（附教材电子版）
    • 2.6 实验作品展示--顺序表
    • 2.7 实验作品展示--单链表
    • 2.8 测验
  • 3 栈和队列
    • 3.1 栈
      • 3.1.1 栈的操作_初始化与销毁
      • 3.1.2 栈的操作_入栈与出栈
    • 3.2 队列
    • 3.3 应用举例
    • 3.4 本章小结（电子版教材课件）
    • 3.5 实验作品展示
  • 4 字符串
    • 4.1 字符串的表示和实现
    • 4.2 扩展学习
    • 4.3 小结（电子版教材）
  • 5 多维数组
    • 5.1 数组的表示和实现
    • 5.2 测验
    • 5.3 稀疏矩阵
    • 5.4 拓展学习
    • 5.5 小结（电子版教材）
  • 6 树和二叉树
    • 6.1 树的定义和基本术语
    • 6.2 二叉树
    • 6.3 遍历二叉树
    • 6.4 线索二叉树
    • 6.5 树和森林
    • 6.6 哈夫曼树及其应用
    • 6.7 小结（电子版教材）
    • 6.8 小测验
    • 6.9 实验作品展示--二叉树遍历
    • 6.10 实验作品展示--二叉树应用
  • 7 图
    • 7.1 图的定义、基本术语
    • 7.2 图的存储
    • 7.3 图的遍历
    • 7.4 最小生成树
    • 7.5 最短路径
    • 7.6 拓扑排序
    • 7.7 实验观摩
    • 7.8 小结（附电子版教材）
    • 7.9 学生作品展示
  • 8 查找技术
    • 8.1 线性表查找
    • 8.2 树表查找
    • 8.3 查找技术在互联网的应用—搜索引擎
    • 8.4 学生作品展示
  • 9 排序技术
    • 9.1 排序的基本概念
    • 9.2 插入排序
      • 9.2.1 直接插入入排序
      • 9.2.2 希尔排序
    • 9.3 交换排序
      • 9.3.1 冒泡排序
      • 9.3.2 快速排序
    • 9.4 选择排序
    • 9.5 小结
  • 10 课程设计
    • 10.1 题目汇总
扩展学习

学习目标：

KMP算法一种改进的模式匹配算法，是D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表，KMP算法又称克努特-莫里斯-普拉特操作。它的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配，不回溯i，而是利用已经得到的部分匹配结果，将一种假想的位置定位“指针”在模式上向右滑动尽可能远的一段距离到某个位置后，继续按规则进行下一次的比较。

算法难点：对NEXT函数的理解与计算