[工学]数据结构第1章讲义.ppt

数据结构讲义 授课教师：张小莉 联系电话：5079389 办公室：主楼1208 Email: xlzhang@ 数据是计算机可以直接处理的基本和最重要的对象。 计算机科学是一门研究数据表示和数据处理的科学。 计算机进行科学计算、过程控制、对文件的存储和检索及数据库技术等计算机应用，都是对数据进行加工处理的过程。 ------这个过程是按照程序进行的。 要设计出一个结构好而且效率高的程序，必须研究数据的特性、数据间的相互关系及其对应的存储表示方法，并利用这些特性和关系设计出相应的算法和程序。 数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。 从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。 从70年代中期到80年代，各种版本的数据结构著作相继出现。 目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。 本课程的任务是： 在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。 学业基础：本课程的先修课程为高级语言程序设计。学习本课程必须具备高级语言程序设计(如C 或C++，等等)的基础知识与基本技能。它的后续课程有操作系统和数据库原理、算法分析与设计等。 学时安排：总学时100。其中课堂讲授68学时, 实验教学32学时。 理论学习（4学分）： 平时成绩（30%）： 出勤、课上提问、课后作业、小测、论坛参与等等； 考试成绩（70%）：期末考试卷面分数。 实验（1学分）： 实验课： 每个实验按照要求进行，并提交实验报告。 第1章 绪论 ⒈教学内容：1.1 数据结构的概念； 1.2 抽象数据类型； 1.3 算法和算法分析。 ⒉教学目的： ⑴领会数据、数据元素和数据项的概念及其相互间的关系； ⑵清楚数据结构的逻辑结构、存储结构的联系与区别； ⑶理解抽象数据类型的概念； ⑷掌握进行简单算法分析的方法。 ⒊教学重点： ⑴数据、数据项、数据元素、数据结构的概念； ⑵逻辑结构和数据结构在概念上的联系与区别； ⑶抽象数据类型和数据抽象； ⑷评价算法优劣的标准及方法。 ⒋教学难点：⑴区别算法与程序； ⑵逻辑结构、存储结构的联系与区别； ⑶抽象数据类型与数据抽象； ⑷算法的时间复杂度分析。 ⒌学时安排： 2学时 1.1 数据结构的概念 为什么要学习数据结构 有关概念和术语 数据结构课程的内容 1.1.1 为什么要学习数据结构 现实中有计算机处理的两大类问题： 数值问题和非数值问题 计算机使用初期：主要是处理数值计算问题（归结为解方程、求值）。涉及的运算对象是简单，不重视数据结构。 发展之后：非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了90%以上的机器时间。 数据结构更为复杂； 数据元素之间的相互关系无法用数学方程式加以描述； 要分析所处理的数据必要分析数据间的关系。 例1 学生信息检索系统 例1 学生信息检索系统 学号顺序排列的学生信息表 姓名顺序排列的索引表 专业顺序排列的索引表 年级顺序排列的索引表 例2 八皇后问题 在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。 为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。 每一个状态，也是一个数据，而所有的数据之间是一种树型关系。 例3 教学计划编排问题 一个教学计划包含许多课程。 课程之间，有些必须按规定的先后次序进行，有些则没有次