教授论坛讲稿(徐孝凯).ppt

1、关于数据结构课程教学的研究,徐孝凯,主要内容,一、为什么要研究数据结构 二、数据的四种基本结构 三、几种典型的数据结构及其运算,一、为什么要研究数据结构,结构: 计算机系统由硬件和软件组成 硬件：中央处理单元、内外存储器、 输入设备、输出设备、各种接口等 软件：保存、运行和使用的所有程序 和数据 功能：计算机是信息处理机，利用程序处理 数据,程序：能够在计算机系统内运行的所有代码。三个层次：底层、中间层和上层程序。 底层程序：就是计算机操作系统。如Windows 中层程序：开发工具类、专用工具类、各种计算机高级程序设计语言等。如数据库、C+ 上层程序：利用各种中层程序软件开发出来的具有特定功能

2、的应用程序。如人事、财务,一、为什么要研究数据结构,上层程序运行：通常在显示器的屏幕上显示出一个窗口界面，供用户进行交互式操作。用户操作的信息被系统接收后，逐层向下层传递和转换，最终驱动计算机系统中的硬件进行有条不紊地工作。 总之，计算机硬件之上是最底层的程序-操作系统，操作系统之上是中间层程序-各种软件开发平台，开发出最上层的应用程序，实现计算机与用户的交互操作，达到利用计算机为人们服务的目的。,一、为什么要研究数据结构,数据：数据和程序相互依存。总之，数据是所有计算机程序所处理的对象。处理数据是进行计算机程序设计的出发点。数据和程序一样重要，对程序而言，需要研究程序设计语言的语法规则和程序

3、设计的方法，对数据而言，需要研究数据的结构和处理数据的方法。 使用数据的例子：自然数、算式、汉字、单词等；文章、表格、图画、帐簿等。,一、为什么要研究数据结构,研究的问题：如何根据处理它们的需要进行组织，形成一定结构的数据，便于计算机存储和运算，节省存储空间和提高运算速度。 两个知识层面：逻辑层面和机器层面。逻辑层面给出数据的结构和处理数据的思路和方法，机器层面是在计算机上对逻辑层面的设计结果进行的具体实现。,一、为什么要研究数据结构,数据结构课程的教学问题：数据结构课程是计算机专业的核心课程，也是较难学好的一门课程。没有能够联系实际地介绍好据结构的含义，没有能够给学生建立起一个总体的印象。

4、我在这方面的研究：利用实例教学，能够让学生一开始就建立起数据结构的整体概念，能够做到理论和实际相结合，使空洞和枯燥的理论变为有血有肉的、学用结合的有机实体。,一、为什么要研究数据结构,四种基本结构：集合结构、线性结构、树结构、图结构。由它们的组合和嵌套可以构造成各种更为复杂的数据结构。,二、数据的四种基本结构,某单位人事简表,二、数据的四种基本结构,数据表：（01,02,03,04,05,06,07,08,09,10） 1. 集合结构：若我们认为人事简表中的每条记录都是独立的，员工之间不存在任何关系，这时的人事简表就是集合结构。 特点：元素之间无联系。,二、数据的四种基本结构,2. 线性结构：

5、每个人的出生日期不同，若按照出生日期的先后次序排列所有10个职工记录，则05号职工排在第1位；10号职工排在第10位；其他的职工则按顺序排在中间。人事简表就是按照职工年龄从大到小排列的线性结构。 特点：元素之间存在着1对1的联系 。,二、数据的四种基本结构,3. 树结构：若考虑职工之间的领导与被领导的关系，则每个职工只能有一个领导，一个领导可以领导若干个职工，则职工之间是树结构 。 特点：元素之间存在着1对多的联系 。,二、数据的四种基本结构,4. 图结构：如果考虑员工之间的兴趣小组，假定01、02、04、06号，03、05、08号，07、09、10号，则职工之间就形成一种图结构。 特点：元素

6、之间存在着多对多的联系 。,二、数据的四种基本结构,结论：对于同一个数据表，根据处理问题的不同需要，可以构成不同的数据结构，可以有集合结构、线性结构、树结构和图结构，或者是它们之间的任意组合的结构。 虽然数据结构很抽象，但通过实例分析，能够很好地理解数据结构的含义。数据结构并不生疏和神秘，它同日常生活息息相关。,二、数据的四种基本结构,对于集合结构，有插入、删除、查找和排序等运算，有求两个集合的并集、交集、差集等运算。 对于线性结构，同样也有插入、删除、查找、排序等运算。但根据不同的运算限制条件，线性结构又可分为线性表、栈和队列。,三、几种典型的数据结构及其运算,线性表：若允许在线性结构中的任

7、何位置进行插入和删除元素的运算，则称为线性表。如 （20, 35,48,56,72,83），20为第1个元素，83为最后一个元素。如在其中插入一个40元素，变为（20,35,40,48,56,72,83）。 运算时间：与线性表的长度n成正比。,三、几种典型的数据结构及其运算,栈：若只允许在数据表的尾部插入或者删除元素，不允许在其他任何位置进行，则称为栈。如包装和码放物体为栈结构。 又如：若把（20,35,18,56,42,33）看作为一个栈，则表尾33元素为栈顶，向栈中插入元素就是把新元素插入到栈顶之后，从栈中删除元素就是删除栈顶元素33，42成为新的栈顶。,三、几种典型的数据结构及其运算,队

8、列：若只允许在表头删除元素和在表尾插入元素，不允许在其他任何位置插入和删除元素，则称为队列。 如：购物排队。又如：（20,35,18,56,42,33），若只允许从表头20元素的位置删除元素，以及只允许在表尾33元素之后插入元素，则这个数据表就是一个队列。删除队首元素20后，35成为新的队首元素；把新元素50插入后，50元成为新的队尾元素。,三、几种典型的数据结构及其运算,栈和队列的运算时间：对栈和队列的运算，由于只在表头和表尾进行，不需要移动任何元素，操作非常简便，其运算时间只是存取一个元素的时间，所以运算时间是一个常量值，它不随表中元素个数n的变化。 选择： 条件许可时，首选栈，次选队列，

9、后选线性表。,三、几种典型的数据结构及其运算,树结构：也同样有插入、删除、查找、排序等运算。 二叉树：树结构中的一种典型的结构。每个分支结点最多有2个直接后继结点，一个称为左分支结点，另一个称为右分支结点。,三、几种典型的数据结构及其运算,三、几种典型的数据结构及其运算,搜索二叉树：每个分支结点的左分支结点的值小于它的值，而右分支结点的值则大于它的值。,三、几种典型的数据结构及其运算,插入元素：向一棵搜索二叉树中插入一个元素，需要经过从最上面的树根结点到最下面的叶子结点的比较过程。如插入25元素。,三、几种典型的数据结构及其运算,查找元素：也需要经过从最上面的树根结点依次向下层结点的比较过程，直到查找成功或失败为止。如查找63元素。,三、几种典型的数据结构及其运算,运算时间：对搜索二叉树进行插入和查找运算的过程，是从树根结点逐层向下比较，每比较一个结点就下移一层，最多下移到最底层的叶子结点。 因为，搜索二叉树的层数大致为以2的底的n的对数，它比n的值要小得多，所以其运算时间为log2n。,三、几种典型的数据结构及其运算,各种典型数据结构的运算时间比较：线性表的运算速度最慢，运算时间为元素个数n的线性级；搜索二叉树的运算速度快得多，运算时间为n的对数级；栈和队列的运算速度最快，运算时间为常量级。 结论：条件许可时,