当前课程知识点：数据结构 > 第1章 绪论 > 1.1 数据结构是什么 > 讲解
同学们，大家好
从这一章开始
我们正式进入数据结构的内容
首先
第一章，绪论
在这一章当中
我们会讲解五部分内容
首先进入第一部分——数据结构是什么
前面我们曾讲到，数据结构
这门课程
对于编写实际的软件、求解现实世界当中的问题，是非常重要的
那么，用计算机来求解现实世界当中的问题，需要经历哪些步骤呢
首先
我们要分析问题
也就是所谓的需求分析。有了需求之后
我们要建立合适的数学模型
也就是所谓的建模
然后，设计合适的算法
再上机写代码、调试、
得到结果。可能
我们很难做到程序一写完、
一运行就能得到预期的正确结果
所以要经过反复的迭代
这里最重要的建立数学模型，也是所谓的建模
他的本质是什么
建模的本质
首先，要从问题当中抽取出关键的对象
也就是，要解决的问题当中存在哪些要处理的数据
这些数据之间有什么样的关系
因为现实问题当中的数据往往并不是孤立的，不同类型的数据
之间往往有各种各样的关系
有了数据对象和关系之后
然后以合适的语言或者符号来描述它们
当然
这里的语言、符号，可以是自然语言
也可以是数学语言，甚至是你习惯的一些符号都可以，因为现在我们还没有进入编程的环节
只是建模的环节
现实世界当中的问题又可以分为哪几类呢
可以分为两类
第一类
是数值型的问题
比如，很多同学在学习C语言的时候都做过百钱百鸡、
百马百担、
水仙花数
这样的问题
这样的问题有一类特点
就是在题干当中，已经说明了问题所涉及到的一些数据
比如，百钱百鸡，一百块钱
买一百只鸡
最后问你，每一种面额的钱花了多少
水仙花数
一个三位数
它的个、十、百位的立方之和，等于这个数本身
这些问题很明显
都是数值型的问题
但是，我们在实际工程实践当中遇到的问题，大多都是非数值型的
比如选课系统、
人脸识别。至少在题面上，我们并没有明显地看到
这些问题所涉及到的一些数据
所以，像非数值型问题
一定要经过建模的步骤
我们这里以学生选课为例
学生选课
我们能够很容易找到这个问题当中出现的一些数据
如果是人工选课
我们可能会在纸上
画出两张表
分别是学生表和课程表
每个表里面
可能会带有一些列
比如学生表里面带有学号、姓名
课程表里面带有课程的编号、
课程的名称。那如何来表达某一个学生选了哪些课
或者说某一门课被哪些学生选了这样的关系呢
我们很可能去列出第三张表
也就是所谓的选课表
尽管选课表涉及到的数据并没有直接反映在学生选课这个问题当中
你看，学生选课
从问题字面上就有学生和课
而这两种对象之间的关系所对应的选课表，是我们自己抽象出来的
我们只需要在选课表里面记录某一个学生的学号、
他选择课程的编号、这门课
他得了多少分，以及其他所需要的一些信息
这三张表实际上就是建模、
我们得到的模型
如果从关系的角度来看，学生选择课程
一个学生可以选择多门课程
反过来看，课程
被学生选择，一门课程会被多个学生选择
那么这两种
数据，实际上是多对多的关系
图当中的方框，代表着数据对象
或者实体，实体这种称法
实际上是数据库这门课当中对数据对象的称法
而菱形代表对象之间的关系
这个图实际上就是数据库当中的E-R图——实体关系图
再来看另外一个例子，文件系统。文件系统是操作系统里面非常重要的一部分
比如，打开“我的电脑”
首先，它底下有很多的盘符
C盘、
D盘
每一个盘符底下
又有很多的文件夹
实际上
文件系统对应着一棵树
我们后面会讲到树这种数据结构
它实际上是一个递归的定义
比如，我们把图当中的那些文件、文件夹都抽象成这里的方框——数据对象
一个文件夹底下
可以包含子文件夹、子文件夹底下
又可以包含其他的子文件夹以及文件
如果我们从上往下看
一个文件夹
包含子文件夹和文件
从下往上看
一个文件夹或者文件
隶属于它的父级文件夹
这实际上是数据结构当中的树状结构
接下来，我们来看数据结构
的起源
数据结构是1968年，由美国的Donald Ervin Knuth教授开创的
说起这个人，我们就不得不提
他是截止到目前为止，最年轻的图灵奖获得者
他在1974年，36岁的时候就获得了图灵奖
这个记录也一直保持到现今
另外
他还是《计算机编程艺术》丛书的作者，按照他的计划
这本书准备出七卷
但目前还没有出完
还有一个需要提及的是
他是排版软件LaTeX的前身——TeX的作者
这个排版软件
可能对于一些科研写作的同学会非常熟悉
数据结构这门课所处的地位
首先
它来源于数学
它是介于数学、
计算机程序设计和硬件系统三者之间的
这里的硬件系统主要是指内、外存
实际上，数据结构这门课，从总体上来划分
还是属于软件学科
底下的。软件学科很少去关注硬件
如果说非要关注
无外乎关注的就是内存
我们后面也会详细地向大家介绍一下内存
的结构
程序=数据结构+算法，这句话强调了数据结构与算法的重要性
说的意思
就是：我们编写一个程序
首先要设计良好的数据结构，以及合适的算法
这句话
是Pascal之父说的
从今天的软件规模看这句话
实际上有一些不太合理的地方
毕竟今天的软件，无论是从用户量、并发、数据量、
用户体验、功能的修改频繁度来说
都要比七十年代
复杂得多
我们现在做软件，更强调工程性
可能会用一些设计模式
除了数据结构之外
设计模式、框架，还有一些软件工程方面的东西
软件方法学方面的东西
但不管怎么样，做任何软件，数据结构都是非常重要的
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
