当前课程知识点：数据结构 > 第8章 排序 > 讨论 > 讲解
同学们，大家好，欢迎来到数据结构课程
我们先用几分钟时间，来了解一下这门课程所涉及到的一些东西
大家看到这里的编号
是从0开始的
我们搞计算机的都喜欢从0开始(如数组下标)
课程简介
我打算从以下四个方面来讲述。课程的意义、
内容、
方法以及实践环境
首先来看课程的意义
从知识角度来说
数据结构这门课程
实际上是计算机相关学科
各专业都涉及到的专业基础课
比如计算机科学与技术、
软件工程、物联网
包括现在比较热门的大数据、
人工智能等。数据结构课程
在这几个专业当中都是比较重要的
通过学习数据结构课程
可以锻炼我们的数据抽象思维
我们做任何一个软件
可以说都要涉及到数据的处理
如何将现实问题当中的数据进行收集、
组织、描述
直至最后的处理呢
这实际上
涉及到数据的抽象思维
通过这门课
我们还要形成基本的算法
分析能力和设计能力
我们要解决现实世界当中的一些问题
必须去设计合适的算法
算法设计出来了之后
是否在性能上满足我们的要求呢
这就需要大家有一定的算法分析能力
另外
在企业面试的时候
经常也会涉及到数据结构相关的内容
大家以后如果要考研
数据结构这门课程也是必考的专业课程之一
我们再来从应用角度看数据结构
这门课程
刚才提到了，几乎开发任何规模的软件
都需要使用到数据结构
原因很简单——
任何软件都需要处理数据
凡是处理到数据
就要思考数据如何抽象、
如何组织、如何存储
当然
除非你开发的是Hello World这样的程序
即使是Hello World，Hello World本身
作为要输出到显示器上的字符串
它本身也是一种数据
另外
编程语言往往内建了数据结构
相关的语法和API
现在主流的编程语言
其实在语言内部，都有一些跟数据结构相关的语法
或者包含了一些数据结构相关的类以及API
比如C语言
大家都知道，C语言有数组和指针。利用数组
实际上就能描述一些顺序存储结构。利用指针
就可以描述一些链式存储结构
C++里面有标准模板库，标准模板库
实际上封装了一些常见的数据结构
还有Java，Java的util(工具)包底下，有几十个跟数据结构相关的接口和实现类
还有，现在比较流行的人工智能、大数据
相关的语言Python，Python这种语言
它在语法层面就提供了一些数据结构相关的机制
比如元组、列表
另外，它也提供了一些API，比如字典、集合
这些都是常见的数据结构
我们现在做Web开发所用到的JavaScript
它里面有一个经常使用到的数据结构，就是JSON
实际上是以字符串描述的
JavaScript对象
它的本质
实际上跟Java里面的Map以及Python里面的字典是类似的。它的本质
就是键值对——
从Key到Value的映射
以上这些语言
它们都提供了与数据结构相关的语法和API，可见数据结构
这门课程是非常重要的
另外我想说的是
既然编程语言提供了如此丰富的数据结构
相关的语法和API
我们为什么还要去学习数据结构
而不是直接用编程语言提供的数据结构
相关的语法和API呢
比如，我们在做软件的时候
经常遇到日期相关的需求
比如，我们要计算两个日期之间相差多少天、
我们要计算用户输入的日期
年月日是否是合法的日期
如果我们自己去编程实现
比如我们判断用户输入的2月29号是否是合法的
我们得先判断它的年份是不是闰年
我们要计算两个日期之间相差多少天
我们当然可以去获得两个日期分别对应的毫秒数
然后相减，再去除以每天对应的毫秒
如果你这样做
虽然能够实现功能，但是
你实现的功能
往往并不是很健壮
你编写的代码，因为没有经过足够多的测试
可能性能方面、健壮性方面都达不到要求
这时候，我们往往是调用编程语言所提供的一些类、API。同样，编程语言提供的数据结构有很多
我们如果对这些数据结构没有很深刻的理解
不知道它们之间的实现差异
那么可能无法针对具体的应用场景，选择合适的数据结构
比如对于Java，Java的
util包底下有一个接口
叫做
Map
刚才我们曾经提到，它的实质就是键到值的映射
它里面描述了若干对的键值对
Map接口有很多的实现类
其中有一个叫HashMap
还有LinkedHashMap
还有一个实现类叫做TreeMap
HashMap
实际上是用数组
加上单链表实现的
这些数据结构
在后续课程中都会讲到
LinkedHashMap
在底层实现上用的是双向链表
而TreeMap
在底层实现上
用的实际上是红黑树
这种数据结构
如果你学习了数据结构这门课程
你去看这些实现类的官方文档
看到官方文档里面描述的数组、
单链表、双向链表、
红黑树等等
你才知道这些实现类各自有什么样的特性
它们之间有什么样的差异
这时候你才能选择适合你的需求
适合你的软件项目的实现类
所以，从这个角度来说
尽管编程语言提供了数据结构、
语法和API，我们依然要去学习数据结构
这门课的主要内容
如下所示
我们在后面会具体讲到
需要特别说明的是
这门课
尽管涉及到一些基础的算法
但这门课并不是专门讲算法的课程
主要还是偏数据结构
如果大家对算法感兴趣
可以专门地学习一些算法相关的课程
另外
我还想强调一下的是
这门课的学习方法
首先是多迭代。有些同学
在学习一个知识点的时候
对这个知识点所要求的一些基础知识可能不太熟悉
比如C语言的结构体、指针
这时候，大家可能需要复习一下C语言相关的东西
如果在学习某个知识点的过程当中，发现有不理解的
这时候可以先暂时停下来
把之前的内容再学习一遍
然后再回来学习。这就是多迭代
实际上
我们在做软件的时候，也并不是线性的
从需求、实现，一直到测试
我们很可能是实现了一个功能
然后再回去迭代，这也是类似的
多做题
在MOOC平台上
有很多的例题、自测、作业以及最后的考试
希望大家能把这些题都完整地做下来
另外要多实践。这里有一句话
实际上是出自
Linux之父
他讲的
如果翻译成中文的话
那就是——高谈阔论
很容易
有本事
写一段代码
所以大家要多写代码
有些同学可能算法的思想、原理、
步骤都知道。给他一道题
也能把结果做出来
但是一到上机环节，把算法写成真正的程序的时候
往往就会遇到一些问题
所以大家在学习的时候要多实践
另外，还要多交流。在MOOC平台上
欢迎大家随时向我们提问
我们会及时地回复
最后一点，就是这门课的编程环境
刚才我们说了
要多实践
那么，我们采用什么样的编程语言呢
采用什么样的IDE呢
从理论上来说
数据结构上机实验所采用的编程语言是没有限定的
你可以用任何你喜欢的编程语言
但这里
我们还是推荐使用强类型的编程语言
那意味着像JavaScript、Python
这样的编程语言，就不推荐
作为数据结构
这门课的上机语言了
你可以用C、C++、C#、Java等等。另外
推荐大家使用面向对象的编程语言
因为我们在抽象数据的过程当中
如果用面向对象的思维来理解这些数据结构、来编写这些数据结构对应的实现代码
会利于你的实现
这里
推荐大家用C++、C#、Java
总之
你擅长、你适合、
你喜欢哪个编程语言
就可以用哪个编程语言
另外
需要大家注意的是
我们不推荐大家使用编程语言内建的数据结构
相关的语法和API
我们现在是学习数据结构
我们要从最基础的语法开始
从零实现这些数据结构
而不是调用编程语言所提供的数据结构
这门课程使用的是C语言
同时为了能够比较方便地修改参数
我们还引入了C++的引用参数
语法
后面会详细提及
IDE方面
有很多同学之前用过VC6.0
实际上在我们这门课当中
放到现在2019年了
我们并不推荐大家用这么古老的东西
毕竟它是在九十年代用的比较多
我们现在写代码
如果用VC6的话
在代码辅助、格式化
这些方面
它的支持力度是比较低的
有些同学呢
可能喜欢用Visual Studio
他会安装Visual Studio 2012、2015，甚至是更新的版本
VS
这个编程环境，当然可以满足数据结构的实验需求
但是它太重了
首先它的安装文件就有几个G，装完之后
可能在你的硬盘上有十几个G
尽管它支持的语言、工程类型非常多
但数据结构这门课程都不会用到
所以也不推荐大家使用
VS
这里我推荐大家使用的是VS Code
VS Code
是微软这几年力推的一个开源、免费项目
首先，它只是一个文本编辑器
并不能称上一个IDE
但是
这个文本编辑器的可扩展性非常的强
我们可以在上面安装各种各样的插件
比如，我们可以安装WinGW
就是Linux底下的C
移植到Windows底下的
我们还可以安装一些其他的插件
让VS Code
支持C、C++的开发
这样就比较轻量级了
大概只有几十兆
可扩展性非常的强
但它的缺点是装完之后需要自己去配置一下
这门课后面会详细给出VS Code
加上各种插件，去搭建一个C、C++开发环境的详细过程
还有一些同学
可能喜欢用Dev-C++、CodeBlocks
这些都可以
我们这里推荐的是
VS Code加上一些插件
这门课的介绍
就到这里，后面
我们将正式进入第一章的学习
同学们，加油！
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
