数据结构课件第1章绪论.ppt
《数据结构课件第1章绪论.ppt》由会员分享,可在线阅读,更多相关《数据结构课件第1章绪论.ppt(84页珍藏版)》请在启牛文库网上搜索。
1、主讲:王敬华,数据结构,华中师范大学计算机学院,数据结构作为一门独立的课程在国外是从1968年才开始设立的。在这之前,它的某些内容曾在其它课程,如表处理语言中有所阐述。1968年在美国一些大学的计算机系的教学计划中,虽然把数据结构规定为一门课程,但对课程的范围没有作明确规定。当时,数据结构几乎和图论,特别是和表、树的理论为同义语。随后,数据结构这个概念被扩充到包括网络、集合代数论、格、关系等方面,从而变成了现在称之为离散数学的内容。然而,由于数据结构在计算机中进行处理,因此,不仅考虑数据本身的数学性质,而且还考虑数据的存储结构,这就进一步扩大了数据结构的内容。近年来,随着数据库系统的不断发展,
2、在数据结构课程中又增加了文件管理(特别是大型文件的组织等)的内容。,课程发展的历史前沿,数据结构是高等学校计算机学科的核心课程,是学习计算机软件应用和开发必备的专业基础。随着计算机的日益普及,它还是“软件资格水平考试”和“考研”的必考科目。同时,数据结构还是一门实践性很强的课程,其与高级程序设计语言有着非常密切的关系,不熟练掌握高级程序设计语言,就不能很好的理解数据结构中有关算法的精髓。,课程性质与地位,本课程介绍如何对各种数据进行组织,并在计算机中对其进行存储、传递和转换。内容包括:数组、链表、栈和队列、递归、树与森林、图、查找、内部排序、外部排序与文件结构等。课程强化数据结构基本知识和程序
3、设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。先修课:C语言程序设计、计算机数学(离散数学),课程主要内容,数据结构的前期课程主要有程序设计语言,学好这门课,可以加深对程序设计的理解,有助于进一步提高程序设计能力,并为计算机专业后续课程,如数据库、操作系统、编译原理、软件工程等课程奠定良好的基础。教材:数据结构及应用算法教程 严蔚敏,陈文博 清华大学出版社,本课程目的,参 考 书,1、数据结构(C语言版)严蔚敏 清华大学出版社2、数据结构 黄国瑜、叶乃菁 清华大学出版社3、数据结构(C语言版)陈峰祺 中国铁道出版社4、数据结构、算法与应用(C+语言描述)汪诗林等译 机械工业
4、出版社5、数据结构算法实现及解析 高一凡 西安电子科技大学出版社6、数据结构学习指导与训练 蒋盛益 中国水利水电出版社7、各类数据结构考研全真试题集与解答,本课程的教学目标,掌握常用的数据的逻辑结构及存储方法,学会编写在常用的存储方式下数据的基本操作的算法。学会分析问题,并能正确的选择合适的数据结构和算法进行程序设计。了解算法时间、空间开销的分析方法。通过基本算法的学习和上机实践,强化程序设计的基本训练,提高编程能力,为进行软件开发打下良好的基础。,内容安排(54授课+36实验),考核形式:平时表现(讨论、回答问题):20%平时作业(基本作业):10%课程设计(实验报告):20%期末考试(闭卷
5、笔试):50%,数 据 结 构,实验上机:在微机上即可。安装C+的编译程序。使用Borland C+或 Visual C+都可以。前者的系统体积小一些。但同一个源程序在这两个编译器上可能会出现不同的编译信息。本着教学相长的精神,希望经常对教学效果作出反馈,以便及时改进教学方法。学好一门课程,教师的引导固然十分重要,但主要靠学生的自身努力。课堂教学可以起到画龙点睛的作用,但只有不断练习,才能巩固、掌握课程的内容。因此,本课程要求同学积极独立完成所布置的习题及实验内容。,数 据 结 构,第一章 绪论,学习要点了解数据结构有关概念的含义,特别数据的逻辑结构,数据的存储结构之间的关系;熟悉类C语言的书
6、写规范,特别要注意值调用和引用调用的区别及出错处理方式;了解计算算法时间复杂度的方法;,第一章 绪论,【学习内容】常用术语集合、线性结构、树和图的表示算法评价时间复杂度、空间复杂度重点:了解数据结构的逻辑结构、存储结构、数 据的运算三方面的概念及相互关系难点:算法复杂度的分析方法掌握:用C+语言描述的方法,能用C+语言编写 程序,一、初步认识数据结构,(1)对所加工的对象进行逻辑组织。(2)把加工对象存储到计算机中去。(3)数据运算。例 电话号码查询系统设有一个电话号码薄,有N个人的姓名和电话号码。假定按如下形式安排:(a1,b1)(a2,b2)(an,bn)其中ai,bi(i=1,2,n)分
7、别表示某人的名字和对应的电话号码,要求设计一个程序,按人名查找号码,若不存在,则给出不存在的信息。,一、数据结构研究什么,算法的设计,依赖于计算机如何存储人的名字和对应的电话号码,或者说依赖于名字和其电话号码的结构。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成:二维数组、表结构、向量。假定名字和其电话号码逻辑上已安排成N元向量的形式,它的每个元素是一个数对(ai,bi),1in 数据的结构,直接影响算法的选择和效率。数据结构还要提供定义在每种结构类型基础之上的各种运算的算法实现。,一、数据结构研究什么,一、数据结构研究什么,例 书目自动检索系统,书目文件,例 人机对奕问题,例:
8、田径赛的时间安排问题,1、任一选手所选中的项目中应该两两有边相连;2、任一两个有边相连的顶点颜色(时间)不能相同。,还有许多需要解决的数据结构问题例 酒店管理系统中的客房分配例 城市煤气管网铺设问题例 排课问题例 旅行商问题,数据结构的诞生与发展,1968年 DEKnuth 发表:“Art of computer programming”IEEE 68 教程 1983 IEEE 83 教程 1991 IEEE 91 教程 2000 IEEE 2000 教程国内在 78 年 开设、相应地有 93 教程等。目前:数据结构已经成为计算机科学与技术、信息管理、机械科学、管理工程等许多学科的必修课,数据
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 绪论