软件技术基础ppt课件

软件技术基础,制作主讲,段景山,段景山,数据结构的基本概念,2,.,第一篇数据结构第一章数据结构的基本概念,数据结构数据的逻辑结构数据的存储结构算法,3,.,数据结构,1数据结构的概念1.1数据及数据元素的概念数据是客观事物在计算机内的抽象描述数据指一些事实，或一些数，或一些符号集合组成数据的“事实”、“数值”或“符号”称为数据元素数据元素可由若干个数据项组成,4,.,数据及数据元素,例1、学生花名册,数据元素,数据,学生名字的集合,每个学生的名字,例2、学生成绩表,数据,数据元素,数据项,学生成绩的集合,每个学生的成绩,名字,成绩,5,.,数据结构的概念,1.2、数据结构的概念数据结构讨论计算机系统中数据的组织形式及其相互关系是相互之间存在一种和多种特定关系的数据元素的集合,例：大楼中的电梯,电梯在楼层中只能逐层移动,例：公司的组织关系,楼层间的关系是线性的,员工间形成树型关系,涉及,元素的集合,元素间的关系,在关系里的操作,电梯的运动,人员的管理,6,.,例：用数据结构描述整数I*,1、组成整数数据的全部元素的集合II0，1，2，3,2、I中元素的关系集合RE,3、I*的运算集合P，比如算术四则运算,4、P中诸运算的运算规则RU，如乘、除法优先于加、减法等,I*I，RE，P，RU,数据结构的概念,RE-10,01,12,7,.,数据结构的概念,例：用数据结构的思想分析以下实物：一个十字路口的红绿灯管制一个五叉路口的红绿灯管制包含两部电梯的管理系统包含三部电梯的管理系统一条公交路线书图书馆,元素关系运算,8,.,数据结构的概念,元素集合,元素间的关系,运算,计算机系统,元素在计算机系统里的表示字符？字串？整数？元素间的逻辑关系逻辑结构元素在计算机系统中的存储方式，物理空间关系存储结构操作指令的集合算法,9,.,数据的逻辑结构与数据的存储结构,例：班级里的同学,可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。,上课时，大家的座次形成存储结构,座次（存储结构）可能与逻辑关系有关，也可能无关。,数据结构的概念,10,.,逻辑结构,小结：数据结构包括数据的逻辑结构，数据在计算机系统中的存储结构和数据操作的集合把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度（教材P3),存储结构,算法,数据结构的概念,要素,目标,三个要素都与我们所要实现的目标相关,有效处理数据,提高数据处理运算速度,11,.,深入思考,研究数据结构的作用看以下几段话，谈谈感受小李是经理小李提升为经理小李从职员提升为经理小李从职员越过课长直接提升为经理，这不合常规小李从1000多个职员中越过课长直接提升为经理，这是很不合常规的哪句话包含的信息多，多了什么样的信息结合这个例子，思考研究目的、重点、基础,12,.,2、数据的逻辑结构数据元素之间关系的描述2.1、描述法二元组关系：一般抽象为前驱与后继关系，即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁,B（K，R）,K：元素集合,R：元素间关系的集合,数据的逻辑结构,13,.,2.2、图示法图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表不管多么复杂的结点，都看作是一个结点有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继,Ki,Kh,Kj,Ki的前驱,Ki的后继,数据的逻辑结构,14,.,3、数据的存储结构（物理结构）是数据元素在计算机系统存储器中的存放方式也可以说，是数据逻辑结构在存储器中的存放方式,数据的存储结构,存储器的特点：由地址连续的单元构成,15,.,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K1,K2,K3,K4,数据的存储结构,逻辑结构,物理结构,16,.,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,数据的存储结构,逻辑结构,物理结构,17,.,数据的存储结构,思考：为什么数据逻辑结构与物理结构没有完全统一？,存储器的特点：由地址连续的单元构成。线性关系,存储单元间位置上的线性关系有时不能直接反映复杂的逻辑关系,18,.,几种物理存储方式3.1顺序存储方法连续顺序地存放数据元素若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了连续存放的数据元素可以在内存中容易找到,数据的存储结构,19,.,3.2、链接存储方法元素在内存中不一定连续存放在元素中附加指针项，通过指针可以找到关系元素,元素指针,结点,元素,指针,数据的存储结构,联想：在一套丛书中每一本书中夹一个卡片，记录下一本书在书架上的位置,20,.,0300,0310,0320,0330,0340,0350,0370,0380,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,通过指针，可以方便地找到关系结点,指向后继结点的指针,数据的存储结构,逻辑结构,物理结构,21,.,3.3索引存储方法为放在内存中的元素建立索引表元素可以离散存放通过查索引表找到需要的元素,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,1,2,3,4,索引表,索引号,数据的存储结构,联想：图书馆的查书卡,22,.,3.4、散列存储方法结点中设一关键值，利用关键值和相应算式算出结点位置（地址）,例：以用户姓名为关键值,DJS,算式：字母的序号相加,04101933,ZXM,26241363,数据的存储结构,所以，DJS放在33号地址单元ZXM放在63号地址单元,联想：通过书的名字就能确定书的位置,23,.,小结：数据的逻辑结构与物理结构1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位2、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序存储方法3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构4、逻辑结构与存储结构是一个问题的两个方面,数据的逻辑结构和存储结构,24,.,例：班级的逻辑关系与课堂上的座次,例：一个树形关系结构用索引方式存储,1,2,3,4,5,6,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,数据的逻辑结构和存储结构,25,.,4、算法4.1、算法的概念及特点算法是为解决某一特定类型问题规定的运算规则的有穷集合有穷性确定性有效性输入输出,特点,非无限执行，必须在有限步骤内结束,非二义，下一步必须是明确的,每一步是可执行的,外部输入零个或多个,至少一个,算法,26,.,4.2、算法与程序相似：都是解决问题的方法和步骤，是指令的集合区别：有穷性描述方法联系：程序用某种程序设计语言来实现算法,程序使用程序设计语言,算法可以使用框图及其他语言,算法,类似：While(1)的语句段，在程序中允许但在算法中不允许,27,.,4.3、算法语言算法应有严格的描述语言（确定性）一般使用类PASCAL语言在本课程中使用类C语言，即语言风格类似于C要求描述一个算法时必须满足：对输入和输出的描述描述语句准确、无二义保证算法的有穷性和有效性,算法,28,.,算法,算法的写作规范,intseq_search(elemtypes,keytypek,intn),intlow,high,mid;,sn.key=k;i=0;,while(si.key!=k)i+;,if(in)returni;elsereturn-1