C讲义第1章绪论ppt课件.ppt

《C讲义第1章绪论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构数据结构是计算机及相关专业中一门重要的专业基础课程。本课程的任务：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。学业基础：本课程的先修课程为离散数学和高级语言程序设计。学习本课程必须具备高级语言程序设计(C语言)的基础知识与基本技能。它的后续课程有操作系统和数据库原理等。⒈教学内容：(1)数据结构的概念(2)抽象数据类型(3)算法和算法分析(4)递归⒉教学目的：(1)领会数据、数据元素和数据项的概念及其相互间关系(2)清楚数据结构的逻辑结构、存储

2、结构的联系与区别(3)理解抽象数据类型的概念(4)掌握进行简单算法分析的方法(5)理解递归的特点，会分析什么样的问题适合用递归解决；领会递归调用的执行过程；了解递归的优缺点第1章数据结构与算法2021年7月31日⒊教学重点：⑴数据、数据项、数据元素、数据结构的概念⑵逻辑结构和数据结构在概念上的联系与区别⑶抽象数据类型和数据抽象⑷评价算法优劣的标准及方法(5)什么样的问题可以用递归解决、递归实现的方法、递归方法的时空效率⒋教学难点：⑴区别算法与程序⑵逻辑结构、存储结构的联系与区别⑶抽象数据类型与数据抽象⑷算法的时间复杂度分析(5)递归的执行过程；递归转换为非递归202

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

4、420071804张会友8178727720071805石宝国7682797920071806何文颖8690918920071807赵胜利7678807820071808崔文靖8293868720071809刘丽80858182………………图1-1学生成绩表2021年7月31日【例1-2】棋盘布局问题。要求将4个棋子布在4行4列的棋盘上，使得任两个棋子既不在同一行或同一列，也不在同一对角线上。【例1-3】教学计划编排问题2021年7月31日1、数据结构课程的发展数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中

5、。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各版本的数据结构著作相继出现。1.1.2数据结构课程的内容2021年7月31日数据结构的内容包括三个层次的五个“要素”。2、数据结构课程的内容2021年7月31日1.2.1有关概念和术语1、数据2、数据项3、数据元素4、数据对象1.2数据结构的概念2021年7月31日（a）集合结构（b）线性结构（c）树结构（d）图结构四类基本结构的示意图5、数据结构⑴集合结构。⑵线性结构。⑶树结构。⑷图结构。2021年7月3

6、1日(1)逻辑层次的数据结构有两个要素。一个是数据元素的集合，另一个是关系的集合。形式上，数据结构可以采用一个二元组来表示：Data_Structure＝（D，R）其中，D是数据元素的有限集，R是D上关系的有限集。(2)应用层次的数据结构包括数据的逻辑结构和数据的物理结构。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它与数据的存储无关。数据结构在计算机中的标识称为数据的物理结构，或称存储结构。2021年7月31日1.2.2抽象数据类型1、数据类型数据类型是一个值的集合和定义在这个值集上的一组操作的总称。2、抽象数据类型抽象数据类型（AbstructData

7、Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。2021年7月31日1.3.1算法及其特性算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：⑴有穷性。⑵确定性。⑶可行性。⑷输入。⑸输出。1.3算法2021年7月31日要设计一个好的算法通常要考虑以下的要求。⑴正确。⑵可读。⑶健壮。⑷高效。2021年7月31日1.