数据结构和软件工程基础课件

1 数据与文件2 算法与数据结构3 软件开发基础 数据结构和软件工程基础知识11 数据与文件数据结构和软件工程基础 知识11.1 1.1 数据组织的层次体系数据组织的层次体系1.2 1.2 基本文件组织方式基本文件组织方式 1 数据与文件21.1 数据组织的层次体系1 数据与文件2 任何系统都有一个数据组织的层次体系。在该层次体系中共分为位、字符、数据元、记录、文件和数据库6层，每一后继层都是其前驱层数据元组合的结果，最终实现一个综合的数据集合。数据组织的层次体系3 任何系统都有一个数据组织的层次体系。在该1.字符 一个字符在计算机中占8位，即一个字节。一个计算机系统可以使用不只一种编码体制。2.数据元 在数据的层次体系中，数据元是最低一层的逻辑单位，为了形成一个逻辑单位,需要将若干位和若干字节组合在一起。3.记录 将逻辑上相关的数据元组合在一起就形成一个记录。例如一个学生记录(学号、姓名、性别、院系、班级)中包含的若干数据元以及作为学生记录的一个值的若干数据项。记录是数据库中存取的最低一层的逻辑单位。4.文件 文件是有名字的存储在某种介质上的一组信息的集合，即文件由信息和介质组成。5.数据库 数据库是一组有序数据的集合。41.字符4 文件是大量性质相同的记录的集合，文件存储在外存储器中，如磁盘、光盘、磁带等。记录是文件中可存取的基本数据单位，它由若干数据项组成，而数据项是文件中最小的数据单位，通常由一个或多个数字位或字符组成，用来表示记录的具体数值。文件在外存储器上组织方式的类型主要有顺序文件、索引文件和直接存取文件。基本文件组织方式5 文件是大量性质相同的记录的集合，文件存储1.顺序文件 顺序文件是按从头到尾的顺序进行存取操作的，文件中的信息就像在一条长长的队列中排列一样。顺序文件是最简单的文件，文件的各个记录按逻辑顺序存放在外存的连续区中，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。如果文件按关键字有序输入，则形成的顺序文件称为顺序有序文件；否则称为顺序无序文件。顺序文件是根据记录的序号或记录的相对位置来进行存取的，其特点是当存取第i个记录时，必须先搜索在它之前的i1个记录；插入新的记录时，只能加在文件的末尾；若要更新文件中的某个记录，则必须将整个文件进行复制。顺序文件的主要优点是存取速度快，因此多用于顺序存取设备(如磁带)。61.顺序文件62.索引文件 索引文件是指在主文件之外再建立一个表示关键字与其物理记录之间对应关系的表，称为索引表。索引表与主文件共同构成索引文件。索引文件的检索分成两步完成，首先将索引表读入内存，再根据索引表所指示的物理地址将记录所在的数据块读人内存进行检索，如图所示。72.索引文件73.直接存取文件直接存取文件又称为哈希(Hash)文件或散列文件，即利用哈希函数及其处理冲突的方法，把文件散列到外存上，通常是磁盘上。对直接存取文件进行查找时，首先根据哈希函数求出哈希地址，再将数据读入内存，然后在内存中进行顺序查找。直接存取文件不能进行顺序查找，但插入数据方便，存取速度快。83.直接存取文件82.1 2.1 算法的基本概念算法的基本概念2.2 2.2 数据结构基础数据结构基础2.3 2.3 栈与队列的基本概念栈与队列的基本概念2.4 2.4 排序与查找基本策略排序与查找基本策略2 算法与数据结构92.1 算法的基本概念2 算法与数据结构91.算法的定义算法是一组明确的可执行步骤的有序集合。算法的概念要求步骤集是有序的，这就要求算法中的各个步骤必须拥有定义完好的顺序执行结构。算法的基本概念101.算法的定义 算法的基本概念10算法的特征：(1)有穷性，一个算法必须保证执行有限步之后结束；(2)确定性，算法的每一步骤必须有确定的定义；(3)输入，一个算法有0个或多个输入，以描述运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；(4)输出，一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；(5)可行性，算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。11算法的特征：11正确性精确简单抽象分级。算法的要素12正确性 算法的要素12一个算法的表示需要使用一些语言形式。传统的算法表示方法为图形法，如流程图和NS图。算法的表示13一个算法的表示需要使用一些语言形式。传统的算法表示方法为图形算法是一组逻辑步骤，计算机程序是使用一些特殊编程语言表达的某些算法。可能几种不同的计算机程序，每一种用不同的编程语言实现，但遵循的逻辑步骤是相同的。它都表达同样的算法，但是它们不是同样的程序。算法与计算机程序14算法是一组逻辑步骤，计算机程序是使用一些特殊编程语言表达的某算法具有5个特性：有穷性、确定性、可行性、输入和输出。评价一个算法一般从正确性、运行时间、占用空间和简单性4个方面进行。算法的评价15算法具有5个特性：有穷性、确定性、可行性、输入和输出。算法1.数据结构的定义 数据结构研究和讨论三个方面的问题：数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；对各种数据结构进行的运算。数据结构指相互有关联的数据元素的集合。比如向量和矩阵。2.数据的逻辑结构：反映数据元素之间逻辑关系的数据结构。数据是指由有限的符号组成的元素的集合，结构则是元素之间的关系(前驱和后继)的集合。用二元组表示：B=(D,R)2.2 数据结构基础161.数据结构的定义2.2 数据结构基础16一年四季的数据结构表示：一年四季的数据结构表示：B=(D,R)B=(D,R)D=D=春，夏，秋，冬春，夏，秋，冬 R=R=（春，夏），（夏，秋），（春，夏），（夏，秋），（秋，冬）（秋，冬）家庭成员的数据结构表示家庭成员的数据结构表示 B=(D,R)B=(D,R)D=D=父亲，儿子，父亲，儿子，女儿女儿 R=R=（父亲，儿子）（父亲，儿子），（父亲，女儿），（父亲，女儿）17一年四季的数据结构表示：17数据结构的图形表示：春夏秋冬父亲女儿儿子18数据结构的图形表示：春夏秋冬父亲女儿儿子18线性结构空的数据结构：线性结构（线性表）：非空数据结构；有且只有一个根结点；每个结点最多一个前件，也最多一个后件；在一个线性结构中插入或删除任何一个结点后还应该是线性结构。非线性结构：19线性结构空的数据结构：193、数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构常用的存储结构有顺序、链接、索引和散列四种结构。顺序存储结构 203、数据的存储结构顺序存储结构 20链接存储结构 21链接存21(2)树形存储结构二叉树，用连续的存储单元保存结构如图：22(2)树形存储结构22(3)图形存储结构23(3)图形存储结构234.数据结构、数据类型和抽象数据类型数据结构是计算机科学与技术领域常用的术语。它用来反映一个数据的内部构成。数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为数据类型。抽象数据类型的含义可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。244.数据结构、数据类型和抽象数据类型24(1)数组结构数组结构中数据元素的个数固定，它们之间的逻辑关系由数据元素的序号(或叫数组的下标)来体现。(2)记录结构记录结构是另一种常用的数据结构。它的特点与数组结构一样，数据元素的个数是固定的。基本数据结构25(1)数组结构 基本数据结构25 l.线性表 线性表是n(n=0)个元素al，a2，an的有限序列，记为(a1，a2，an)。数据元素具有相同的数据类型。若线性表非空，第一个元素无前驱；最后一个元素无后继；其他元素仅有一个直接前驱和一个直接后继。线性表的顺序存储结构：在程序设计时常定义一个一维数组来表示线性表的顺序存储空间2.3 栈与队列的基本概念26 l.线性表2.3 栈与队列的基本概念26线性表在顺序存储结构下，可进行各种处理。主要的运算：插入删除查找排序分解合并复制l逆转27线性表在顺序存储结构下，可进行各种处理。主要的运算：272.栈一种特殊的线性表，插入和删除运算只能在线性表的一端进行，另一端封闭。在顺序存储结构下，对这种类型的线性表的插入和删除运算不需要移动表中其它数据元素。遵循“FILO”282.栈一种特殊的线性表，插入和删除运算只能在线性表的一端进栈的顺序存储及其运算：用一维数组 作为栈的顺序存储空间s(1:m)栈的基本运算：入栈、退栈、读栈顶元素、29栈的顺序存储及其运算：栈的基本运算：入栈、退栈、读栈顶元素、3.队列一种特殊的线性表，在一端进行插入、而在另一端进行删除运算。遵循：FIFO303.队列30队列的顺序实现:用一维数组作为队列的顺序存储空间 循环队列及其运算：入队运算和退队运算31队列的顺序实现:循环队列及其运算：314、线性链表线性表的链式存储结构存储空间中的每一个存储结点分为两部分：数据域和指针域链接存储结构 线性链表的基本运算：插入、删除、合并、分解逆转、复制、排序、查找循环链表及其运算：324、线性链表链接存线性链表的基本运算：插入、删除、合并、分解 5.树非线性结构，所有数据元素之间的关系具有明显的层次特性。根节点、父节点、叶子结点、结点的度、树的度、树的深度：树的最大层次、子树33 5.树33二叉树及其基本性质：非空二叉树只有一个根节点；每个结点最多两个子树，分别是左子树和右子树。满二叉树：除最后一层，其它都有两个子结点完全二叉树：除最后一层，每层上的结点数均达到最大；最后一层上只缺少右边的若干结点。二叉树的存储结构：采用链式存储结构34二叉树及其基本性质：34二叉树的遍历：指不重复的访问二叉树中的所有结点。前序遍历(DLR):FCADBEGHP中序遍历（LDR):ACBDFEHGP后序遍历（LRD):ABDCHPGEFBFCEAHGPD35二叉树的遍历：BFCEAHGPD35(1)插入排序例：设待排序的记录共7个，关键码分别为8，3，2，5，9，l，6。从i=2开始经过6步插入完成全部排序工作。对n个记录的文件进行直接插入排序，所需要的执行时间是O(n2)。2.4 排序与查找基本策略 8 3 2 5 9 1 6 i=2:3 8 2 5 9 1 6 i=3:2 3 8 5 9 1 6 i=4:2 3 5 8 9 1 6 i=5:2 3 5 8 9 1 6 i=6:1 2 3 5 8 96 i=7:1 2 3 5 6 8 9 36(1)插入排序2.4 排序与查找基本策略 (2)选择排序例：将上例中的记录用选择排序法排序，过程：对n个记录的文件进行选择排序，所需要的执行时间是O(n2)。37(2)选择排序对n个记录的文件进行选择排序，所需要的执行(3)冒泡排序例：设待排序文件的关键码为：38 19 65 13 97 49 41 95 1 73。执行冒泡排序的过程：对n个记录的文件进行冒泡排序，所需要的执行时间是O(n2)。38(3)冒泡排序对n个记录的文件进行冒泡排序，所需要的执行时4)查找就是根据给定的值，在一组数据中确定一个其数值等于给定值的数据元素，如果找到则查找成功，否则查找不成功。用平均查找长度来衡量。顺序查找：从第一个元素开始，逐个把元素的关键字与给定值比较。平均查找长度为n/2。二分查找：如果表中的数据元素按数值排序（递增有序），则在查找时不必逐个顺序比较，而采用跳跃的方式：首先与“中间位置”的元素比较，若相等则查找成功；若给定值大于“中间位置”的元素，则在后半部继续进行折半查找；否则在前半部进行折半查找。平均查找长度为log2n。树表查找：当二叉排序树不空时，首先将给定值K与根节点的关键字进行比较，若相等则查找成功；若给定值K小于根节点的关键字，则下一次与左子树的关键字进行比较；若给定的值大于根节点的关键字，则下一次与右子树的关键字进行比较；如此递推下去，只到某一次比较相等，查找成功。否则查找失败。394)查找39例：已知一个已按照字母排列的人员名字列表，用二分查找法，查找John.AnnBlackCarolDavialElaineFredGeogreHanyIrene Irene IreneJohn John JohnKelly Kelly Kelly Lany LanyMany ManyNancy NancyOliver Oliver40例：已知一个已按照字母排列的人员名字列表，用二分查找法，查找3.1 3.1 软件工程概述软件工程概述3.2 3.2 软件开发方法软件开发方法3.3 3.3 软件开发工具软件开发工具3.4 3.4 软件复用技术软件复用技术3 软件开发基础413.1 软件工程概述3 软件开发基础41判断一个软件的好坏的的一些定性的准则：(1)正确性(2)可靠性(3)简明性(4)有效性(5)可维护性(6)适应性 软件工程概述1、软件：是指与计算机系统的操作有关的计算机程序、规程、规则及其文档和数据的统称。包括程序和文档两部分。程序指的指令序列和相关的数据；文档指与软件开发、运行、维护、使用和培训有关的文档。42判断一个软件的好坏的的一些定性的准则：软件工程概述1、软2、软件工程：指为了经济地获得可靠地和能在实际机器上高效运行的软件，而建立和使用的健全的工程原则，是指导计算机软件开发和维护的工程学科。软件工程是为了克服“软件危机”而诞生的。软件危机：在计算机软件的开发和维护过程中所遇到的一系列严重问题。软件生命周期：指软件产品从提出、实现、使用、维护到停止使用的过程。包括可行性研究与需求分析、设计、实现、测试、交付使用及维护等具体环节。3、软件开发：是一个把用户需求转化为软件需求，把软件需求转化为软件设计，用软件代码来实现软件设计，对软件代码进行测试，并签署确认它可以投入运行使用的过程。432、软件工程：434、软件开发过程 从工程学角度出发，软件开发过程包括可行性研究、计划、分析、设计、编码、测试运行和维护等几个阶段。需求分析：回答做什么的问题。方法有结构化分析方法、数据流程图和数据字典等。软件设计：概要设计和详细设计。概要设计的目标是给出软件的模块结构，用软件结构图表示。详细设计的首要任务就是设计。模块的程序流程、算法和数据结构，次要任务是设计数据库。软件测试：目的是以较小的代价发现尽可能多的错误。关键是设计一套出色的测试用例。分为静态测试和动态测试。静态测试：测试程序中的语法错误和结构性错误。动态测试：通过试运行程序来推断产品某个行为特性是否有错误，有白盒测试和黑盒测试两种。444、软件开发过程44白盒测试：测试对象是源程序，依据的是程序内部的逻辑结构来发现软件的编程错误、结构错误和数据错误。黑盒测试：依据的是软件的功能或软件行为描述，发现软件的接口、功能、和结构错误。软件测试包括：单元测试、集成测试、确认测试和系统测试。5、软件开发原理1）抽象2）目标分解3）局部化与信息隐藏4）一致性5）可验证性45白盒测试：测试对象是源程序，依据的是程序内部的逻辑结构来发现6、典型的软件过程模型1）瀑布模型2）原型模型快速原型模型l原型进化模型3）增量模型4）螺旋模型466、典型的软件过程模型46当前主要采用的软件开发方法有结构化方法、面向对象方法和专家系统方法。1、结构化方法：采用结构化分析技术对问题进行分析建模。将问题描述为“数据流图+实体联系图”。数据流图是一种用来表示信息流程和信息交换过程的图解方法，描述问题空间中数据交换处理之间的逻辑关系；实体联系图描述问题空间中数据存储之间的逻辑关系，同时借用数据词典、结构化语言、判定表、判定树等工具对它进行详细说明。软件开发方法47当前主要采用的软件开发方法有结构化方法、面向对象方法和专家系2、面向对象的方法：采用面向对象分析对问题进行分析建模，将问题描述为“对象+关联”的形式。对象描述问题空间中的事物，有客观实体也有抽象概念；关联描述问题空间中事物和事物之间的关系。可借助数据词典、结构化语言、判定表、判定树等工具对它进行详细说明。主要包括对问题空间中对象的确定和对对象之间关联的确定。对对象的确定包括对对象的属性和行为的确定；对关联的确定包括对对象结构关系、实力例关联和消息关联的确定。482、面向对象的方法：483、专家系统方法：目的是为了解决借助人类专家知识和经验以及推理分析手段才能解决的问题。知识库用于存放从人类专家处获取的知识和经验；推理机用于应用知识库中的知识对问题进行推理、分析和求解；数据库用于存放问题的信息、求解的过程、和求解结果；解释器用于对求解过程进行解释。493、专家系统方法：49 1.数据流图数据流图(DFD，Data Flow Diagram)是一种最常用的结构化分析工具，它从数据传递和加工角度，以图形的方式刻画出系统内的数据运动情况。软件开发工具50 1.数据流图 软件开发工具502.实体联系图实体联系图(Entity-Relationship Diagram)是分析和设计软件系统中使用的工具，它是关于系统中的信息项(实体)以及这些信息项之间关系的图示描述。3、面向对象开发工具Microsoft visual studio4、CASE计算机辅助软件工程512.实体联系图51 软件复用是将已有的软件及其有效成分用于构造新的软件或系统。根据面向对象的设计原理，应着眼于以下几个方面：(1)封装性 (2)重载 (3)继承 (4)聚合 (5)多态性 软件复用技术52 软件复用是将已有的软件及其有效成分用于构造新的软件或系统。