电子科技大学软件技术基础1孟中楼.ppt

软件技术基础,电子科技大学通信与信息工程学院软件技术基础课题组教师:孟中楼Email：zlmeng,SCIE,UniversityofElectronicScienceandTechnologyofChina,2,课程简介,教材和参考资料教材：软件技术基础（第3版），黄迪明等编著，电子科技大学出版社，出版日期2009年7月参考资料：1数据结构清华大学出版社，严蔚敏等2计算机操作系统西安电子科技大学出版社，汤子瀛,SCIE,UniversityofElectronicScienceandTechnologyofChina,3,课程简介,课程安排讲授学时安排（48学时）：第一章数据结构26学时第二章操作系统22学时软件技术基础QQ群554768353,SCIE,UniversityofElectronicScienceandTechnologyofChina,4,课程简介,考核方式平时考核占15%，包括课堂出勤，平时作业中期考试占5%，采用开卷考试方式期末考试占80%，采用闭卷考试方式,SCIE,UniversityofElectronicScienceandTechnologyofChina,5,1、数据结构的基本概念,几个基本问题什么是数据结构数据结构研究的主要内容学习数据结构的意义,SCIE,UniversityofElectronicScienceandTechnologyofChina,6,1、数据结构的基本概念,本章主要讲述内容1.1数据结构中的基本术语1.2数据的逻辑结构1.3数据的存储结构1.4算法,SCIE,UniversityofElectronicScienceandTechnologyofChina,7,1.1数据结构中的基本术语,一、数据及数据元素的概念数据是客观事物在计算机内的抽象描述数据指一些事实，或一些数，或一些符号集合数据的基本单位：数据元素组成数据的“事实”、“数值”或“符号”称为数据元素数据元素可由若干个数据项组成,三者之间的关系,例：班级通讯录个人记录姓名、年龄,数据数据元素数据项,SCIE,UniversityofElectronicScienceandTechnologyofChina,8,1.1数据结构中的基本术语,例1、学生花名册,数据元素,数据,学生名字的集合,每个学生的名字,例2、学生成绩表,数据,数据元素,数据项,学生成绩的集合,每个学生的成绩,名字,成绩,SCIE,UniversityofElectronicScienceandTechnologyofChina,9,1.1数据结构中的基本术语,二、数据结构的概念结构是指事物间的相互关系和约束。数据结构讨论计算机系统中数据的组织形式及其相互关系数据结构是相互之间存在一种和多种特定关系的数据元素的集合，表示为：,Data_Structure=（D,R）,元素有限集,关系有限集,SCIE,UniversityofElectronicScienceandTechnologyofChina,10,1.1数据结构中的基本术语,元素集合,元素间的关系,运算,计算机系统,元素在计算机系统里的表示字符？字串？整数？元素间的逻辑关系逻辑结构元素在计算机系统中的存储方式，物理空间关系存储结构操作指令的集合算法,SCIE,UniversityofElectronicScienceandTechnologyofChina,11,三、数据的逻辑结构与数据的存储结构逻辑结构：数据元素之间关系的描述存储结构：数据元素在计算机系统存储器中的存放方式,例：班级里的同学,可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。,上课时，大家的座次形成存储结构,座次（存储结构）可能与逻辑关系有关，也可能无关。,1.1数据结构中的基本术语,SCIE,UniversityofElectronicScienceandTechnologyofChina,12,逻辑结构,四、小结：数据结构包括数据的逻辑结构，数据在计算机系统中的存储结构和数据操作的集合把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度（教材P3),存储结构,算法,1.1数据结构中的基本术语,要素,目标,三个要素都与我们所要实现的目标相关,有效处理数据,提高数据处理运算速度,SCIE,UniversityofElectronicScienceandTechnologyofChina,13,数据的逻辑结构：数据元素之间关系的描述一、描述法二元组关系：一般抽象为前驱与后继关系，即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁,B（K，R）,K：元素集合,R：元素间关系的集合,1.2数据的逻辑结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,14,二、图示法图形要素：结点和有向线段结点：表示一个数据元素，一般以方形框代表不管多么复杂的结点，都看作是一个结点有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继,Ki,Kh,Kj,Ki的前驱,Ki的后继,1.2数据的逻辑结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,15,数据的存储结构（物理结构）是数据元素在计算机系统存储器中的存放方式也可以说，是数据逻辑结构在存储器中的存放方式,1.3数据的存储结构,存储器的特点：由地址连续的单元构成,SCIE,UniversityofElectronicScienceandTechnologyofChina,16,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K1,K2,K3,K4,1.3数据的存储结构,逻辑结构,物理结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,17,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,1.3数据的存储结构,逻辑结构,物理结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,18,1.3数据的存储结构,思考：为什么数据逻辑结构与物理结构没有完全统一？,存储器的特点：由地址连续的单元构成。线性关系,存储单元间位置上的线性关系有时不能直接反映复杂的逻辑关系,SCIE,UniversityofElectronicScienceandTechnologyofChina,19,几种物理存储方式一、顺序存储方法连续顺序地存放数据元素若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了连续存放的数据元素可以在内存中容易找到,1.3数据的存储结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,20,二、链接存储方法元素在内存中不一定连续存放在元素中附加指针项，通过指针可以找到关系元素,元素指针,结点,元素,指针,1.3数据的存储结构,联想：在一套丛书中每一本书中夹一个卡片，记录下一本书在书架上的位置,SCIE,UniversityofElectronicScienceandTechnologyofChina,21,0300,0310,0320,0330,0340,0350,0370,0380,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,通过指针，可以方便地找到关系结点,指向后继结点的指针,1.3数据的存储结构,逻辑结构,物理结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,22,三、索引存储方法为放在内存中的元素建立索引表元素可以离散存放通过查索引表找到需要的元素,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,1,2,3,4,索引表,索引号,1.3数据的存储结构,联想：图书馆的查书卡,SCIE,UniversityofElectronicScienceandTechnologyofChina,23,四、散列存储方法结点中设一关键值，利用关键值和相应散列函数算出结点位置（地址）,例：以用户姓名为关键值,DJS,算式：字母的序号相加,04101933,ZXM,26241363,1.3数据的存储结构,DJS放在33号地址单元ZXM放在63号地址单元,联想：通过书的名字就能确定书的位置,SCIE,UniversityofElectronicScienceandTechnologyofChina,24,小结：数据的逻辑结构与物理结构1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位2、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序存储方法3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构4、逻辑结构与存储结构是一个问题的两个方面,1.3数据的存储结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,25,例：一个树形关系结构用索引方式存储,1,2,3,4,5,6,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,1.3数据的存储结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,26,1.3数据的存储结构,SCIE,UniversityofElectronicScienceandTechnologyofChina,27,一、算法的概念及特点算法是为解决某一特定类型问题规定的运算规则的有穷集合有穷性确定性有效性输入输出,特点,非无限执行，必须在有限步骤内结束,非二义，下一步必须是明确的,每一步是可执行的,外部输入零个或多个,至少一个,1.4算法,SCIE,UniversityofElectronicScienceandTechnologyofChina,28,二、算法与程序相似：都是解决问题的方法和步骤，是指令的集合区别：算法具有有穷性描述方法联系：程序用某种程序设计语言来实现算法,程序使用程序设计语言,算法可以使用框图及其他语言,1.4算法,类似：While(1)的语句段，在程序中允许但在算法中不允许,SCIE,UniversityofElectronicScienceandTechnologyofChina,29,三、算法语言算法应有严格的描述语言（确定性）一般使用类PASCAL语言在本课程中使用类C语言，即语言风格类似于C描述一个算法时必须满足：对输入和输出的描述描述语句准确、无二义保证算法的有穷性和有效性,1.4算法,SCIE,UniversityofElectronicScienceandTechnologyofChina,30,1.4算法,算法的写作规范,intseq_search(elemtypes,keytypek,intn),intlow,high,mid;,sn.key=k;i=0;,while(si.key!=k)i+;,if(in)returni;elsereturn-1;,SCIE,UniversityofElectronicScienceandTechnologyofChina,31,四、在数据结构中常见的问题创建、插入、删除、更新、检索、排序注意：每个问题都有一种或多种算法找到效率最高的以最容易理解的方式设计设计的算法不容易出错或出错情况较少,1.4算法,SCIE,UniversityofElectronicScienceandTechnologyofChina,32,五、算法和数据结构的关系算法是建立在数据结构的基础上的合理的数据结构常常可以有效的简化算法只有明确了算法，才能较好的设计数据结构程序=算法+数据结构,1.4算法,SCIE,UniversityofElectronicScienceandTechnologyofChina,33,六、算法的衡量,1.4算法,常用时间复杂度来衡量,算法评价有4个指标：,运行时间、占用空间、正确性和简单性,常用空间复杂度来衡量,SCIE,UniversityofElectronicScienceandTechnologyofChina,34,五、算法的衡量,1.4算法,注：1）O（）为渐近符号2）空间复杂度S(n)按数量级递增顺序也与上表类似。,复杂度高,复杂度低,时间复杂度T(n)按数量级递增顺序为：,SCIE,UniversityofElectronicScienceandTechnologyofChina,35,1.4算法,3n+2=O(n)因为3n+24nforn26*2n+n2=O(2n)因为6*2n+n27*2nforn4,例：,渐进符号