《数据结构与算法》PPT课件.ppt

《《数据结构与算法》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法（Java版）2021年10月4日数据结构是计算机及相关专业中一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。2021年10月4日课程任务在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同

2、存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。学业基础本课程的先修课程为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。2021年10月4日⒈教学内容：(1)数据结构的概念；(2)抽象数据类型；(3)算法和算法分析。⒉教学目的：(1)领会数据、数据元素和数据项的概念及其相互间的关系；(2)清楚数据结构的逻辑结构、存储结构的联系与区别；(3)理解抽象数据类型的概念；(4)掌握进行简单算法分析的方法。第1

3、章数据结构与算法2021年10月4日⒊教学重点：⑴数据、数据项、数据元素、数据结构的概念；⑵逻辑结构和数据结构在概念上的联系与区别；⑶抽象数据类型和数据抽象；⑷评价算法优劣的标准及方法。⒋教学难点：⑴区别算法与程序；⑵逻辑结构、存储结构的联系与区别；⑶抽象数据类型与数据抽象；⑷算法的时间复杂度分析。2021年10月4日1.1.1为什么要学习数据结构在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。由于当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中

4、于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。解决这类问题的关键是要设计出合适的数据结构，才能有效地解决问题。1.1引言2021年10月4日【例1-1】成绩检索系统。要求成绩检索系统提供自动查询的功能，如查找某个学生的单科成绩或平均成绩，查询某门课程的最高分等等。学号姓名考试成绩平均成绩高等数学C语言英语20071801吴承志90958590200

5、71802李淑芳8876918520071803刘丽9278828420071804张会友8178727720071805石宝国7682797920071806何文颖8690918920071807赵胜利7678807820071808崔文靖8293868720071809刘丽80858182………………图1-1学生成绩表【例1-2】棋盘布局问题。要求将4个棋子布在4行4列的棋盘上，使得任两个棋子既不在同一行或同一列，也不在同一对角线上。2021年10月4日【例1-3】教学计划编排问题一个教学计划

6、包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边，则表示课程i必须先于课程j进行。2021年10月4日由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算

7、的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。2021年10月4日1、数据结构课程的发展数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各版本的数据结构著作相继出现。1.1.2数据结构课程的内容2021年10月4日数据结构课程集中讨论软件开发过程中的设计阶段、

8、同时涉及编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”。2、数据结构课程的内容2021年10月4日1.2.1有关概念和术语1、数据数据是信息的载体，是所有能够被计算机识别、存储和加工处理的符号的总称。2、数据项数据项（DataItem）是具有独立含义的标识单位，是数据不可分割的最小单位。3、数据元素数据元素（DataElement）是数据的基本单位。4、数据对象数据对象（Dat