资源描述：
《数据结构严蔚敏 课件第1章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第一章绪论2007年9月5日星期三第页【课前思考】你过去是否听说过"数据结构"？你知道数据结构是一门讨论什么内容的学科吗？同学们见过《算法+数据结构=程序设计》这本书吧，它正好说明数据结构的实质是讨论程序设计的方法。通过这门课的学习，同学们将掌握非数值计算程序设计中用的基本方法和技巧。2007年9月5日星期三第页【学习目标】熟悉各名词、术语的含义，掌握基本概念。理解算法五个要素的确切含义。掌握计算语句频度和估算算法时间复杂度的方法。【重点和难点】本章讨论的都是一些基本概念，因此没有难点，重点在于了解有关数据结构的各个名词和术语的含义，以及语句频度和时间复杂度、空间
2、复杂度的估算。【知识点】数据、数据元素、数据结构、数据类型、抽象数据类型、算法及其设计原则、时间复杂度、空间复杂度。2007年9月5日星期三第页【学习指南】1.熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2.了解抽象数据类型的定义、表示和实现方法。3.熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。4.理解算法五个要素的确切含义和对算法正确性的理解。5.掌握计算语句频度和估算算法时间复杂度的方法。2007年9月5日星期三第页1.1数据结构
3、讨论的范畴1.2基本概念1.3算法和算法的量度2007年9月5日星期三第页1.1数据结构讨论的范畴NiklausWirth：Algorithm+DataStructures=Programs程序设计:算法:数据结构:为计算机处理问题编制一组指令集处理问题的策略问题的数学模型2007年9月5日星期三第页结构静力分析计算例如:数值计算的程序设计问题─━线性代数方程组─━环流模式方程(球面坐标系)全球天气预报2007年9月5日星期三第页非数值计算的程序设计问题例一:求一组(n个)整数中的最大值算法:?模型：？基本操作是“比较两个数的大小”取决于整数值的范围2007年9月
4、5日星期三第页例二：计算机对弈算法：?模型：?对弈的规则和策略棋盘及棋盘的格局2007年9月5日星期三第页例三：足协的数据库管理算法：?模型：?需要管理的项目？如何管理？用户界面？各种表格2007年9月5日星期三第页概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。2007年9月5日星期三第页1.2基本概念一、数据与数据结构二、数据类型三、抽象数据类型2007年9月5日星期三第页一、数据与数据结构所有能被输入到计算机中，且能被计算机处理的符号的集合。数据:是计算机操作的对象的总称。是计算机处理的信息
5、的某种特定的符号表示形式。2007年9月5日星期三第页是数据（集合）中的一个“个体”数据元素:是数据结构中讨论的基本单位数据对象是性质相同的数据元素的集合是数据的子集2007年9月5日星期三第页数据项：是数据结构中讨论的最小单位数据元素可以是数据项的集合例如：描述一个运动员的数据元素可以是称之为组合项2007年9月5日星期三第页数据结构：带结构的数据元素的集合假设用三个4位的十进制数表示一个含12位数的十进制数。3214,6587,9345─a1(3214),a2(6587),a3(9345)则在数据元素a1、a2和a3之间存在着“次序”关系a1,a2、a2
6、,a33214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:2007年9月5日星期三第页又例，在2行3列的二维数组{a1,a2,a3,a4,a5,a6}中六个元素之间存在两个关系:行的次序关系:列的次序关系:row={,,,}col={,,}a1a3a5a2a4a6a1a2a3a4a5a6数据结构：带结构的数据元素的集合2007年9月5日星期三第页再例，在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系
7、:{
8、i=1,2,3,4,5}或者说，数据结构是相互之间存在着某种关系的数据元素的集合。数据结构：带结构的数据元素的集合可见，不同的“关系”构成不同的“结构”2007年9月5日星期三第页数据结构包括以下几个方面：数据元素之间的逻辑关系，即逻辑结构数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构施加在该数据上的操作，即数据的运算2007年9月5日星期三第页数据的逻辑结构可归结为以下四类:线性结构树形结构图状结构集合结构2007年9月5日星期三第页数据结构的形式定义为:数据结构是一个二元组Data_Structures=(D,S)其中:D
9、是数据元素
