《数据结构讲义》ppt课件

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

1、数据结构与算法DataStructureandAlgorithms西安交通大学自动化系杜友田duyt@mail.xjtu.edu.cn2数据结构课程简介【课程内容】数据的各种逻辑结构和物理结构（存储结构），以及它们之间的相应关系并对每种结构定义相适应的各种运算设计出相应的算法分析算法的效率常用数据结构类型：线性表、栈和队列、串、数组和特殊矩阵、树和二叉树、图。3【学习目的】为后续专业课程打下算法与数据结构方面的知识基础；掌握必要的软件设计方面的技能。【学习要求】掌握各类数据结构类型和相应的存储结构提高阅读和

2、编写算法的能力能针对给定问题，选择相适应的数据结构，并能设计和分析算法。数据结构课程简介前期课程数据结构计算机基础C语言离散数学后期课程操作系统编译原理数据库原理软件工程承上启下4【课程体系】数据结构课程简介是计算机专业各类考试中的必考课程C语言数据结构软件工程掌握基本编程方法掌握数据组织和处理的方法掌握软件开发的系统方法基本要求课程关系5数据结构课程简介【课程体系】与先修课—C++语言程序设计的联系和区别C语言侧重于通过编写不太复杂的程序而理解掌握语言的特性和语言的运用。数据结构侧重于给出解决问题的策略和方法，即研究算

3、法；还要求算法的时空效率高，算法结构和可读性好、容易验证等等。对问题的数据表示和求解所采取的观点也有大大的提高，通过定义数据结构及其上的操作以解决问题。解决某个问题的程序，如果是用“就事论事”的策略写成的，在C语言中是合格的，在数据结构中过去的算法可能就不再合格了。数据结构课程简介6数据结构的发展1968年在国外规定为一门独立的课程，美国D.E.Knuth教授的著作《计算机程序设计技巧》第一卷《基本算法》出版，系统阐述数据的逻辑结构和存储结构及其操作；20世纪60年代末70年代初提出“数据结构+算法=程序设计”的思想；20

4、世纪70年代中期到80年代初，各种版本的数据结构著作问世；我国从1978年开设本课程，目前，它不仅是计算机专业教学计划中的核心课程之一，而且是其他非计算机专业的主要选修课程之一；发展方向：面向专门领域中特殊问题的数据结构；从抽象数据类型的观点讨论数据结构。数据结构课程简介7【参考书目】《数据结构》（C语言版）,严蔚敏，吴伟民，清华大学出版社《数据结构题集》,严蔚敏，吴伟民，清华大学出版社T.H.Cormen,etal.IntroductiontoAlgorithms(2ndEdition).MITPress,2002.科曼

5、等著,潘金贵译.算法导论(第2版).北京:机械工业出版社,2006.8数据结构课程简介【教学方式】课堂讲授（48学时）＋上机实验（8学时）数据结构课程简介【考核方式】考勤：10分作业：10分实验：20分考试：60分9【一些期望】大胆提问，积极沟通认真完成作业和实验涉猎相关的书籍教材【联系方式】杜友田，电信学院自动化系系统工程研究所智能网络与网络安全教育部重点实验室办公室：科学馆251Tel：82663467(O),13572275205E-mail:duyt@mail.xjtu.edu.cn10数据结构课程简介第一章

6、绪论1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求111.1什么是数据结构问题机外表示处理要求逻辑结构基本运算数学模型存储结构编程实现实现建模求解计算机求解问题的步骤:分析问题；建立求解问题的数学模型并设计算法—通过算法来表示对象数据及其相互关系；实现：编制程序模拟对象领域中的求解过程。12例1图书馆的书目检索自动化系统登录号：书名：作者名：分类号：：：书目卡片书目文件按书名按作者名按分类

7、号索引表线性表131.1什么是数据结构树……..……..…...…...…...…...141.1什么是数据结构例2计算机和人对奕问题例3田径赛的时间安排问题图姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M1、任一选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色不能相同。15跳高跳远标枪铅球200M100M1.1什么是数据结构跳高跳远铅球标枪100M200M跳高111011跳远110011铅球101101标枪001111100M11011

8、1200M111111用矩阵形式表示的图0：两个项目无冲突；1：两个项目有冲突。161.1什么是数据结构例4铺设煤气管道问题假设要在n个居民区之间铺设煤气管道，设任意两个居民区之间都可以架设管道，但每条管道的费用成本不同，求投资最少管道铺设方案。CBAED325416216945364740CBAED3