数据结构（第一讲）.ppt

* * * * * * * * * * * * * * * * * * * * * （第一讲） 绍兴文理学院 计算机系计算机应用教研室 TKS * 为什么要学习数据结构? * 起始课 、 第1章 绪论(1) 一、教学目的：明确数据结构课程在自身发展、应用等远景和本专业知识结构中的地位、作用；明确课程的特点、教学要求、学习方法；明确数据结构所研究的问题以及有关基本概念；明确抽象数据类型的概念和描述方法。 二、教学重点：数据结构课程在自身发展、应用等远景和本专业知识结构中的地位、作用；数据结构所研究的问题以及有关基本概念；抽象数据类型。 三、教学难点：理解数据结构所研究的问题；抽象数据类型。 四、教学过程： TKS * 1、应用、科学的思想和方法－自身发展及其远景的需要 (1) “校园卡”买饭菜等 §1.0 为什么要学习数据结构 * 不同的查找 主要用到数据的组织和查找。不同的数据的组织和查找效率是很不一样的，不同的查找方法其效率相差百倍以上乃至千倍。 这是数据的组织和查找问题，在第7章中进行讨论。 (2) 打电话－存在0575和05758的城市电话区号吗？ 若存在，则057588341511是0575对应城市下面是05758对应城市下面的8341511呢？ 程控电话如何处理？ 又：为什么北京的电话区号是010，而绍兴的区号是0575？ 这是利用树结构的编码问题，在第5章中进行讨论。 (3) 高考分数的排名－以便录取 在第8章中进行讨论。 (4) 快递线路、运费最省、最短旅行线路等问题 TKS * * 在计算机系统软件和应用软件中排序的使用频度很高。然而不同的排序方法排序效率是很不一样的。其排序效率相差百倍以上。 不同的排序 这是图结构问题，在第6章中进行讨论。 最短路径 (5) 管线、道路连通的最少代价问题 这是图结构问题，在第6章中进行讨论。 (6) 工程计划问题 这是图结构问题，在第6章中进行讨论。 关键路径 3、是后续课程和软件技术基础的需要 数据结构是操作系统、软件工程、计算机网络、编译原理、数据库等信息技术相关专业主要课程的先修课程； 是掌握一定的算法理论、数据组织和处理技术、提高编程技能和提高实践动手能力需要。 4、是培养科学的思想和方法，整体把握利用计算机解决问题的需要 有人设想将常用的数千个汉字进行全排列，用这些字写出的不朽诗篇，名言佳句将都在其中了。 每年按365天，每天24小时，每小时3600秒，对于每秒能生成108个排列的超高速电子计算机，即使一年到头从不休息地工作也需要：3.04×1064/(365×24×3600×108)≈9.64×1049 (年)。所以有些问题是计算机根本不能解决的。 但就当n=50时，有n!≈3.04? 1064, (7) 问题规模的判断－时间和空间复杂度问题 TKS * * 算法复杂度 2、是考研的需要 (1) 现实世界：现实中的事物和问题。 (2) 信息世界：把现实世界中的事物和问题经过分析、抽象、归纳、整理后得到的逻辑意义上的事物和问题的数据和数据关系。 (3) 机器世界：把信息世界里的数据和数据关系，组织并存储到计算机里，通过计算机来处理事物和解决问题。 6、计算机求解问题的步骤： 实际问题 问题模型 机器模型 求解算法 编制程序 问题实现 分析 抽象 分析 归纳 模型 求解 命令 编程 调试 程序 5、三个世界 TKS * * 数据结构是三个世界的纽带 数据结构的知识和技能对现实世界的分析到信息世界提供直接而重要的帮助，结合编程工具，实现由信息世界到机器世界的转换，是实现用计算机来解决问题强有力的支撑。 §1.1 数据结构的研究内容 数据结构主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型。 例1 书目自动检索系统 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 书目文件 按书名 按作者名 按分类号 索引表 线性表 1、数据结构的研究内容 001 高等数学 樊映川 S01 002 理论力学 罗远祥 L01 003 高等数学 华罗庚 S01 004 线性代数 栾汝书 S02 …… …… …… …… …… …… 004，… 线性代数 002，… 理论力学 001，003，… 高等数学 …… …… 004，… 栾汝书 002，… 华罗庚 001，… 樊映川 …… …… 001，003，… S