数据结构与算法-东北林业大学 第一章演示文稿绪论new2009.ppt

《数据结构与算法-东北林业大学 第一章演示文稿绪论new2009.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG主讲：王阿川教授数据结构目录第一章绪论第二章线性表第三章栈与队列第四章串第五章数组和广义表第六章树第七章图第八章查找第九章排序第十章文件小结习题练习1.4算法的描述和算法分析简介1.3抽象数据类型的表示和实现1.1数据结构讨论的范畴1.2基本概念和术语第一章绪论数据结构是计算机专业的专业基础课程之一，是十分重要的核心课程。计算机的所有系统软件和应用软件都要用到各种类型的数据结构。要想更好地运用计算机来解决实际问题，仅仅学习计算机语言而缺乏数据结构知识是远远不够的，而打好“数据结构”这门课程的扎实基础，对于

2、学习计算机机专业的其他课程都是十分重要的。例如：操作系统、数据库原理、计算机网络、编译方法等课程。数据结构课程的重要性程序＝算法＋数据结构Algorithm+DataStructures=Programs程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型由此可以得出：数据结构描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中的表示和实现NiklausWirth数据结构课程的重要性基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确切含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时

3、间和空间角度分析算法的方法。第一章绪论数据结构中常用的基本概念和术语算法描述和分析方法难点算法复杂性的分析方法要求了解数据的逻辑结构和物理结构，算法的基本概念，它们对于程序设计的重要性以及相互关系掌握算法复杂性的概念及分析方法知识点熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。了解抽象数据类型的定义、表示和实现方法。熟悉类C语言的书写规范，特别是要注意值调用和引用调用的区别，输入输出方式以及错误处理方式。；理解算法五个要素的确切含义：1、动态有穷性（能执行结束）；2、确定性（对于相同的输入执行相同的路径）；

4、3、有输入；4、有输出；5、可行性（用于描述算法的操作都是足够基本的）。掌握计算语句频度和估算算法时间复杂度的方法。学习要点：数据结构讨论什麽？简单回答数据结构是一门和程序设计密切相关的课程。NiklausWirth教授（美国计算机专家）写一本书，书名叫：Algorithm+DataStructures=Programs成为名言。说明算法和数据结构是进行程序设计的两大要素。1.1数据结构讨论的范畴什麽是程序设计:为计算机处理问题编制一组指令集。程序设计任务就是为计算机解题来编制一组织指令集。算法:处理问题的策略数据结构:问题的数学模型任何程序设计问题都包含着两个方面。包括大家已经熟悉的数

5、值计算问题：例1、数值计算的程序设计问题。结构静力分析计算首先利用有限元分析，得到一个线性方程组，这个方程组就是进行结构静力学的数学模型。例2、利用计算机来进行全球气象预报需要求解一组球面坐标系下的一般环流模式方程。这个环流模式方程就是全球气象预报的数学模型。这两个例子中计算机主要进行大量的算术运算，属于侧重数值计算的程序设计问题。那末相对应的，如今计算机处理的大量非数值计算问题，那末这些非数值计算问题中他的算法和数学模型是什麽呢？例1：求一组（n个）整数中的最大值。算法：基本操作是“比较两个数的大小”只要进行n-1次相邻比较就可以求出最大的值。那末，这个问题的数学模型是什莫？数学模型：

6、因为没告诉n的大小。由于受计算机字长的限制，计算机所能表示的整数是一个有限值，比如16位。就是长整形还达不到32位，那末若讨论的整数的绝对值为232，那末就存在怎末表示这个整数的问题。例2人机对奕问题树……..……..…...…...…...…...算法：对弈的规则和策略模型：棋盘棋子怎末表示。例3、足协的数据库管理算法：需要管理的项目？如何管理？用户界面？他的条件，他的规则以及其它接口需求。数学模型：就是各种各样的表格和数据库。例4多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图交叉路口的图示模型（冲突图）有些通行方向不能同时行驶，在这样的结点间画

7、一条连线。综合各种程序设计问题，抽取他具体的物理意义，就可以得到几类数学模型。比如，和数值计算相关的数学模型就有线性代数方程、非线性代数方程、常微分方程等。他们的数值解问题，也就是计算机求解的问题，就是数学所要研究的问题。类似的非数值计算问题，他的数学模型的表示和求解方法，就是数据结构所要研究的内容，所以概括的说：数据结构描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中的表示和实现“课程”表格数据结构定义:是一门研究非