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

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