数据结构基本概念.ppt
第一篇数据结构第一章数据结构的基本概念数据结构数据的逻辑结构数据的存储结构算法数据结构的概念1.1数据及数据元素的概念数据是客观事物在计算机内的抽象描述数据指一些事实,或一些数,或一些符号集合组成数据的“事实”、“数值”或“符号”称为数据元素数据元素可由若干个数据项组成数据结构数据及数据元素例1、学生花名册数据元素数据学生名字的集合每个学生的名字例2、学生成绩表数据数据元素数据项学生成绩的集合每个学生的成绩名字成绩数据结构的概念1.2、数据结构的概念数据结构讨论计算机系统中数据的组织形式及其相互关系是相互之间存在一种和多种特定关系的数据元素的集合例:大楼中的电梯电梯在楼层中只能逐层移动例:公司的组织关系楼层间的关系是线性的员工间形成树型关系涉及元素的集合元素间的关系在关系里的操作电梯的运动人员的管理例:用数据结构描述整数I*数据结构的概念组成整数数据的全部元素的集合II={0,±1,±2,±3……}I中元素的关系集合REI*的运算集合P,比如算术四则运算P中诸运算的运算规则RU,如乘、除法优先于加、减法等I*={I,RE,P,RU}RE={……-10,01,12,……}数据结构的概念例:用数据结构的思想分析以下实物:一个十字路口的红绿灯管制一个五叉路口的红绿灯管制包含两部电梯的管理系统包含三部电梯的管理系统一条公交路线书图书馆元素关系运算咨讯:是否了解本次行动的目标和内容拿出纸笔,开始行动决策:选取主题,或自拟题目计划:2~4人自由组合为一组实施:按数据结构中的“元素的集合”、“元素的关系”、“运算”来描述主题,至少三句话评价:相互评价描述内容是否适当。课堂活动主题选择是否适当元素抽象是否适当逻辑结构(关系)与物理结构之间是否有区分度算法是否适当,与两个结构之间的描述是否有区分度汇报讲解是否清楚课堂活动数据结构的概念元素集合元素间的关系运算计算机系统元素在计算机系统里的表示字符?字串?整数?元素间的逻辑关系--逻辑结构元素在计算机系统中的存储方式,物理空间关系--存储结构操作指令的集合--算法数据的逻辑结构与数据的存储结构例:班级里的同学可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。上课时,大家的座次形成存储结构座次(存储结构)可能与逻辑关系有关,也可能无关。数据结构的概念数据结构的概念逻辑结构存储结构算法要素目标数据结构包括数据的逻辑结构,数据在计算机系统中的存储结构和数据操作的集合把数据以一定的逻辑结构组织起来,以适当的方式存储在计算机系统的存储器里,其最终目的是为了有效处理数据,提高数据处理运算速度(教材P3)小结:01有效处理数据提高数据处理运算速度三个要素都与我们所要实现的目标相关02深入思考研究数据结构的作用看以下几段话,谈谈感受小李是经理小李提升为经理小李从职员提升为经理小李从职员越过课长直接提升为经理,这不合常规小李从1000多个职员中越过课长直接提升为经理,这是很不合常规的哪句话包含的信息多,多了什么样的信息结合这个例子,思考研究目的、重点、基础数据的逻辑结构数据的逻辑结构数据元素之间关系的描述2.1、描述法二元组关系:一般抽象为前驱与后继关系,即表明结构中,一个元素的前一个元素是谁,它的后一个元素又是谁B=(K,R)K:元素集合R:元素间关系的集合数据的逻辑结构2.2、图示法图形要素:结点和有向线段结点:表示一个数据元素,一般以方形框代表 不管多么复杂的结点,都看作是一个结点有向线段:表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继KiKhKjKi的前驱Ki的后继是数据元素在计算机系统存储器中的存放方式也可以说,是数据逻辑结构在存储器中的存放方式存储器的特点:由地址连续的单元构成数据的存储结构(物理结构)数据的存储结构K101.K201.K301.K401.K101.K201.K301.K401.逻辑结构01.物理结构01.数据的存储结构K101.K201.K301.K401.K501.K601.K101.K201.K301.K401.K501.K601.逻辑结构01.物理结构01.数据的存储结构思考:为什么数据逻辑结构与物理结构没有完全统一?01存储器的特点:由地址连续的单元构成。--线性关系02存