资源描述：
《数据结构之1绪论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章绪论§1.1数据结构的概念早期：数值计算——运算对象是简单的整型、实型或布尔类型数据中后期：非数值计算——处理对象是类型复杂的数据，数据元素之间的相互关系一般无法用数学方程式加以描述1例1：“学生”表格2例2：八皇后问题(用四皇后描述)............四皇后问题的状态树3课程编号课程名称先修课程C1计算机导论无C2数据结构C1，C4C3汇编语言C1C4C程序设计语言C1C5计算机图形学C2，C3，C4C6接口技术C3C7数据库原理C2，C9C8编译原理C4C9操作系统C2例3：教学计划编排问题（a）计算机专业的
2、课程设置4C1C2C3C6C4C5C9C7C8（b）表示课程之间优先关系的有向图5例4：城市的煤气管道问题（a）结点间管道的代价（b）最经济的管道铺设6描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。数据结构是一门研究（非数值计算的）程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。7课程学习前掌握的基本概念：数据数据元素（数据成员）数据对象8数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号（数值、字符等）的集合。数据元素（数据成员）:是数据
3、的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。9数据对象：具有相同性质的数据元素（数据成员）的集合。整数数据对象N={0,1,2,…}学生数据对象10数据结构由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。数据结构的形式定义11数据结构涉及三个方面：1.数据的逻辑结构-----从用户视图看，是面向问题的。2.数据的物理结构（存储结构）-----从具体实现视图看，是面向计算机的。3.相关的操作及其实现。E
4、xample:学生表：逻辑结构-----线性表物理结构-----数组,链表操作-----插入,删除,查找12数据结构包括“逻辑结构”和“物理结构”两个方面(层次):逻辑结构是对数据成员之间的逻辑关系的描述，它可以用一个数据成员的集合和定义在此集合上的若干关系来表示;物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。13逻辑结构和物理结构的关系数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；是数据的最终组织
5、形式。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。14根据问题来建立逻辑结构例如：Class=(D,S)数据集合：D={a,b1,…,bn,c1,…cn,d1,…dn}关系集合：S={R1,R2}R1={,,}//班长-组长R2={,,
6、j=2,3,…,n}//组长-组员15ab1c1b2b3bn…c2c3cn…d2d3dn…d1班级Class的逻辑结构的图示16存储结构是逻辑结构在存储器中的映象。数据元素的映象：任何数据元素在计算机中最
7、终都是转化成一个二进制的位串。关系的映象：…17关系的映象方法：（关系对x,y）1.顺序映象（顺序存储方法）：以相对的存储位置表示后继关系例如:令y的存储位置和x的存储位置之间差一个常量C，而C是一个隐含值，整个存储结构中只含数据元素本身的信息xy182.链式映象（链接存储方法）:以附加信息(指针)表示后继关系需要用一个和x在一起的附加信息（指针)指示y的存储位置yx193.索引存储方法4.散列存储方法20线性结构：表、栈、队列非线性结构层次结构：树，二叉树，堆网状结构：图其它：集合数据结构的分类21线性结构bindevetclibuser前驱
8、后继22非线性结构——层次结构树二叉树141312111234567891098745623123堆（特殊的树结构）“最大”堆“最小”堆12354871110291641012115123698724图结构12564312543611331814665161921网络结构非线性结构——群结构25§1.2数据结构的抽象形式C语言中的数据类型charintfloatdoublevoid字符型整型浮点型双精度型无值数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.26不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。
9、例如：整型(int)值的范围是：-32768~32767（16位）操作是：+，-，*，/，%27抽象数据类型(ADTs:A
