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

软软件技术术基础础 电子科技大学通信与信息工程学院 软件技术基础课题组 教师:孟中楼 Email： SCIE, University of Electronic Science and Technology of China 2 课课程简简介 n 教材和参考资料 教材：软件技术基础（第3版），黄迪明等 编著，电子科技大学出版社，出版日期2009年 7月 参考资料： 1数据结构清华大学出版社，严蔚敏等 2计算机操作系统西安电子科技大学出版社 ，汤子瀛 SCIE, University of Electronic Science and Technology of China 3 课课程简简介 n 课程安排 讲授学时安排（48学时）： 第一章 数据结构 26学时 第二章 操作系统 22学时 软件技术基础 QQ群554768353 SCIE, University of Electronic Science and Technology of China 4 课课程简简介 n 考核方式 平时考核占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数据结结构中的基本术语术语 元素集合 元素间的关系 运算 计 算 机 系 统 n 元素在计算机系统里的表示 p 字符？字串？整数？ n 元素间的逻辑关系逻辑结 构 n 元素在计算机系统中的存储方式，物 理空间关系存储结构 n 操作指令的集合 算法 SCIE, University of Electronic Science and Technology of China 11 三、数据的逻辑结 构与数据的存储结 构 逻辑结 构：数据元素之间关系的描述 存储结构：数据元素在计算机系统存储器中的存放方式 例：班级里的同学 可能有各种各样的逻辑关系。比如班长、班委、群众等 。形成相应的逻辑结 构。 上课时，大家的座次形成存储结构 座次（存储结构）可能与逻辑关系有关，也可能无关。 1.1数据结结构中的基本术语术语 SCIE, University of Electronic Science and Technology of China 12 逻辑结 构 四、小结： p 数据结构包括数据的逻辑结 构，数据在计算机系 统中的存储结构和数据操作的集合 p 把数据以一定的逻辑结 构组织起来，以适当的方 式存储在计算机系统的存储器里，其最终目的是 为了有效处理数据，提高数据处理运算速度（教 材P3) 存储结构算法 1.1数据结结构中的基本术语术语 要素目标 三个要素都与我们所要实现 的目标相关 有效处理数据提高数据处理运算速度 SCIE, University of Electronic Science and Technology of China 13 数据的逻辑结 构：数据元素之间关系的描述 一、描述法 二元组 p 关系：一般抽象为前驱与后继关系， 即表明结构中，一个元素的前一个元素是谁，它的后 一个元素又是谁 B （ K， R ） K：元素集合 R：元素间关系的集合 1.2数据的逻辑结逻辑结 构 SCIE, University of Electronic Science and Technology of China 14 二、图示法 p 图形要素： 结点和有向线段 p 结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点 p 有向线段：表示元素之间的关系。 箭尾指向的结点是前驱。 箭头指向的结点是后继 K iK hK j Ki的前驱 Ki的后继 1.2数据的逻辑结逻辑结 构 SCIE, University of Electronic Science and Technology of China 15 数据的存储结 构（物理结构） p 是数据元素在计算机系统存储器中的存放方式 p 也可以说，是数据逻辑结 构在存储器中的存放方 式 1.3数据的存储结储结 构 存储储器的特点：由地址连续连续 的单单元构成 SCIE, University of Electronic Science and Technology of China 16 0300 0301 0302 0303 0304 0305 0306 0307 0308 0309 K1K2K3K4 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 K2K3 K4K5K6 K1 K2 K3 K4 K5 K6 1.3数据的存储结储结 构 逻辑结逻辑结 构构物理物理结结构构 SCIE, University of Electronic Science and Technology of China 18 1.3数据的存储结储结 构 n 思考：为什么数据逻辑结 构与物理结构没有 完全统一？ 存储储器的特点：由地址连续连续 的单单元构成。线线性关系 存储单储单 元间间位置上的线线性关系有时时不能 直接反映复杂杂的逻辑逻辑 关系 SCIE, University of Electronic Science and Technology of China 19 几种物理存储方式 一、顺序存储方法 p 连续顺 序地存放数据元素 p 若数据的逻辑结 构也是顺序（线性）的，则逻 辑结构和物理结构完全统一了 p 连续存放的数据元素可以在内存中容易找到 1.3数据的存储结储结 构 SCIE, University of Electronic Science and Technology of China 20 二、链接存储方法 p 元素在内存中不一定连续存放 p 在元素中附加指针项，通过指针可以找到关系元素 元素指针 结点 元素指针 1.3数据的存储结储结 构 联联想：在一套想：在一套丛书丛书 中每一本中每一本书书中中夹夹一个卡片一个卡片 ，记录记录 下一本下一本书书在在书书架上的位置架上的位置 SCIE, University of Electronic Science and Technology of China 21 0300 0310 0320 0330 0340 0350 0370 0380 K1 K2K3 K4K5K6 K1 K2 K3 K4 K5 K6 通过指针，可以方便地找到关系结点 指向后继结点的指针 1.3数据的存储结储结 构 逻辑结逻辑结 构构 物理物理结结构构 SCIE, University of Electronic Science and Technology of China 22 三、索引存储方 法 p 为放在内存中 的元素建立索 引表 p 元素可以离散 存放 p 通过查索引表 找到需要的元 素 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 例：一个树形关系结构用索引方式存储 K1 K2K3 K4K5K6 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 二、算法与程序 p 相似：都是解决问题的方法和步骤，是指令的集合 p 区别： 算法具有有穷性 描述方法 p 联系：程序用某种程序设计语 言来实现算法 程序使用程序设计语 言 算法可以使用框图及其他语言 1.4算法 类似： While(1) 的语句段，在程序中允许 但在算法中不允许 SCIE, University of Electronic Science and Technology of China 29 三、算法语言 p 算法应有严格的描述语言（确定性） p 一般使用类PASCAL语言 p 在本课程中使用类C语言，即语言风格类似于C 描述一个算法时必须满 足： p 对输入和输出的描述 p 描述语句准确、无二义 p 保证算法的有穷性和有效性 1.4算法 SCIE, University of Electronic Science and Technology of China 30 1.4算法 算法的写作规范 int seq_search( elemtype s ,keytype k, int n)int seq_search( elemtype s ,keytype k, int n) int low, high, mid;int low, high, mid; sn.key = k;sn.key = k; i = 0;i = 0; while(s i .key != k)while(s i .key != k) i+; i+; if(i n)if(i n) return i; return i; elseelse return -1; return -1; 名称名称输输入参数入参数 输输出出 类类型型使用的使用的变变量量说说明明 初始化初始化 算法主体部分算法主体部分 SCIE, University of Electronic Science and Technology of China 31 四、在数据结构中常见的问题 p 创建、插入、删除、更新、检索、排序 p 注意：每个问题都有一种或多种算法 找到效率最高的 以最容易理解的方式设计 设计的算法不容易出错或出错情况较少 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 Scienc