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

1、软件技术基础软件技术基础电子科技大学通信与信息工程学院软件技术基础课题组教师:孟中楼Email：SCIE, University of Electronic Science and Technology of China2课程简介课程简介n 教材和参考资料教材：软件技术基础（第3版），黄迪明等编著，电子科技大学出版社，出版日期2009年7月参考资料：1数据结构清华大学出版社，严蔚敏等2计算机操作系统西安电子科技大学出版社，汤子瀛SCIE, University of Electronic Science and Technology of China3课程简介课程简介n 课程安排 讲授学时安排

2、（48学时）： 第一章 数据结构 26学时 第二章 操作系统 22学时软件技术基础 QQ群554768353SCIE, University of Electronic Science and Technology of China4课程简介课程简介n 考核方式平时考核占15%，包括课堂出勤，平时作业中期考试占5%，采用开卷考试方式期末考试占80%，采用闭卷考试方式SCIE, University of Electronic Science and Technology of China51、数据结构的基本概念几个基本问题什么是数据结构数据结构研究的主要内容学习数据结构的意义SCIE, Uni

3、versity of Electronic Science and Technology of China61、数据结构的基本概念 本章主要讲述内容1.1 数据结构中的基本术语 1.2 数据的逻辑结构1.3 数据的存储结构1.4 算法 SCIE, University of Electronic Science and Technology of China71.1数据结构中的基本术语数据结构中的基本术语 一、数据及数据元素的概念数据是客观事物在计算机内的抽象描述 数据指一些事实，或一些数，或一些符号集合数据的基本单位：数据元素 组成数据的“事实”、“数值”或“符号”称为数据元素数据元素可由若

4、干个数据项组成三者之间的关系例：班级通讯录 个人记录 姓名、年龄数据 数据元素 数据项SCIE, University of Electronic Science and Technology of China81.1数据结构中的基本术语数据结构中的基本术语 例1、学生花名册数据元素数据学生名字的集合每个学生的名字例2、学生成绩表数据数据元素数据项学生成绩的集合每个学生的成绩名字成绩SCIE, University of Electronic Science and Technology of China91.1数据结构中的基本术语数据结构中的基本术语 二、数据结构的概念结构是指事物间的相互关

5、系和约束。数据结构讨论计算机系统中数据的组织形式及其相互关系 数据结构是相互之间存在一种和多种特定关系的数据元素的集合，表示为：Data_Structure=（D, R）元素有限集关系有限集SCIE, University of Electronic Science and Technology of China101.11.1数据结构中的基本术语数据结构中的基本术语 元素集合元素间的关系运算计算机系统n 元素在计算机系统里的表示p 字符？字串？整数？n 元素间的逻辑关系逻辑结构n 元素在计算机系统中的存储方式，物理空间关系存储结构n 操作指令的集合 算法SCIE, University of

6、 Electronic Science and Technology of China11三、数据的逻辑结构与数据的存储结构 逻辑结构：数据元素之间关系的描述 存储结构：数据元素在计算机系统存储器中的存放方式例：班级里的同学可能有各种各样的逻辑关系。比如班长、班委、群众等。形成相应的逻辑结构。上课时，大家的座次形成存储结构座次（存储结构）可能与逻辑关系有关，也可能无关。1.11.1数据结构中的基本术语数据结构中的基本术语 SCIE, University of Electronic Science and Technology of China12逻辑结构四、小结：p数据结构包括数据的逻辑结构

7、，数据在计算机系统中的存储结构和数据操作的集合p把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度（教材P3)存储结构算法1.11.1数据结构中的基本术语数据结构中的基本术语 要素目标三个要素都与我们所要实现的目标相关有效处理数据提高数据处理运算速度SCIE, University of Electronic Science and Technology of China13数据的逻辑结构：数据元素之间关系的描述一、描述法二元组p关系：一般抽象为前驱与后继关系， 即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁

8、B （ K， R ）K：元素集合R：元素间关系的集合1.2数据的逻辑结构数据的逻辑结构SCIE, University of Electronic Science and Technology of China14二、图示法p图形要素：结点和有向线段p结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点p有向线段：表示元素之间的关系。箭尾指向的结点是前驱。箭头指向的结点是后继K iK hK jKi的前驱Ki的后继1.2数据的逻辑结构数据的逻辑结构SCIE, University of Electronic Science and Technology of China

9、15数据的存储结构（物理结构）p是数据元素在计算机系统存储器中的存放方式p也可以说，是数据逻辑结构在存储器中的存放方式1.3数据的存储结构数据的存储结构存储器的特点：由地址连续的单元构成存储器的特点：由地址连续的单元构成SCIE, University of Electronic Science and Technology of China160300030103020303030403050306030703080309K1K2K3K4K1K2K3K41.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology

10、 of China170300030103020303030403050306030703080309K1K2K3K4K5K6K1K2K3K4K5K61.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China181.3数据的存储结构数据的存储结构n思考：为什么数据逻辑结构与物理结构没有完全统一？存储器的特点：由地址连续的单元构成。线性关系存储器的特点：由地址连续的单元构成。线性关系存储单元间位置上的线性关系有时不能存储单元间位置上的线性关系有时不能直接反映复杂的逻辑关系直接反映复杂的逻辑关系SC

11、IE, University of Electronic Science and Technology of China19几种物理存储方式一、顺序存储方法p连续顺序地存放数据元素p若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了p连续存放的数据元素可以在内存中容易找到1.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China20二、链接存储方法p元素在内存中不一定连续存放p在元素中附加指针项，通过指针可以找到关系元素元素指针 结点元素指针1.3数据的存储结构数据的存储结构SC

12、IE, University of Electronic Science and Technology of China2103000310032003300340035003700380K1K2K3K4K5K6K1K2K3K4K5K6通过指针，可以方便地找到关系结点指向后继结点的指针1.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China22三、索引存储方法p为放在内存中的元素建立索引表p元素可以离散存放p通过查索引表找到需要的元素030003010302030303040305030603

13、0703080309K1K2K3K412341.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China23四、散列存储方法 结点中设一关键值，利用关键值和相应散列函数算出结点位置（地址）例：以用户姓名为关键值DJS算式：字母的序号相加041019 33ZXM262413 631.3数据的存储结构数据的存储结构 DJS放在33号地址单元 ZXM放在63号地址单元SCIE, University of Electronic Science and Technology of China24小结：数据

14、的逻辑结构与物理结构1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题物理结构着眼于结点在内存中的定位2、简单的逻辑结构可能和物理结构一致例：线性逻辑关系与顺序存储方法3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构4、逻辑结构与存储结构是一个问题的两个方面1.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China25例：一个树形关系结构用索引方式存储K1K

15、2K3K4K5K61234560300030103020303030403050306030703080309K1K2K3K4K5K61.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China261.3数据的存储结构数据的存储结构SCIE, University of Electronic Science and Technology of China27一、算法的概念及特点 算法是为解决某一特定类型问题规定的运算规则的有穷集合有穷性确定性有效性输入输出特点非无限执行，必须在有限步骤内结束非二义

16、，下一步必须是明确的每一步是可执行的外部输入零个或多个至少一个1.4算法算法SCIE, University of Electronic Science and Technology of China28 二、算法与程序p相似：都是解决问题的方法和步骤，是指令的集合p区别：算法具有有穷性描述方法p联系：程序用某种程序设计语言来实现算法程序使用程序设计语言算法可以使用框图及其他语言1.4算法算法类似：While(1) 的语句段，在程序中允许但在算法中不允许SCIE, University of Electronic Science and Technology of China29三、算法语言p

17、算法应有严格的描述语言（确定性）p一般使用类PASCAL语言p在本课程中使用类C语言，即语言风格类似于C描述一个算法时必须满足：p对输入和输出的描述p描述语句准确、无二义p保证算法的有穷性和有效性1.4算法算法SCIE, University of Electronic Science and Technology of China301.4算法算法算法的写作规范SCIE, University of Electronic Science and Technology of China31四、在数据结构中常见的问题p创建、插入、删除、更新、检索、排序p注意：每个问题都有一种或多种算法找到效率最

18、高的以最容易理解的方式设计设计的算法不容易出错或出错情况较少1.4算法算法SCIE, University of Electronic Science and Technology of China32五、算法和数据结构的关系算法是建立在数据结构的基础上的 合理的数据结构常常可以有效的简化算法只有明确了算法，才能较好的设计数据结构 程序=算法+数据结构1.4算法算法SCIE, University of Electronic Science and Technology of China33六、算法的衡量1.4算法算法常用时间复杂度来衡量算法评价有4个指标：运行时间、占用空间、正确性和简单性常用空间复杂度来衡量SCIE, University of Electronic Science and Technology of China34五、算法的衡量1.41.4算法算法注：1） O（）为渐近符号2） 空间复杂度S(n)按数