计算机二级公共基础知识69

公共基础知识基本数据结构与算法二级二级ACCESS一数据库基础知识二级二级ACCESS一数据库基础知识本章的重要性•经统计本章在理论考试中占10%左右即4个左右的选择题。•本章在考试中只涉及笔试题目，上机不考。二级二级ACCESS—数据访问页二级二级ACCESS—数据访问页关键考点16」，BdBdBfl•广，Bl**ilJBI，BdBSBIB1»flBS，BdBdBfl•广，■广LB＜，“•:•顺序存储与链式存储的基本概念•:•栈、队列的基本概念与基本操作•:•循环队列元素个数的计算•:•算法时间、空间复杂度的概念•:•几种查找与排序的比较次数•:•二叉树的遍历•:•二叉树结点个数的计算基本数据结构与算法基本数据结构与算法1.1算法1B1BdB4B 1 »SBdBdBd»•**>1B1B1BdBdB4Bd**>fl*B1■」»SBdI•:•算法的基本概念*算法：解题方案的准确而完整的描述。釆算法的基本特征:是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。算法不等于程序，程序不可能优于算法。釆基本特性（P1）■可行性:根据实际问题设计的算法，执行得到满意结果■确定性:每一步骤必须有明确定义，不允许有多义性。■有穷性：算法必须能在有限的时间内做完。■■有穷性：算法必须能在有限的时间内做完。■拥有足够的情报:输入和输出，方可执行。基本数据结构与算法1.1算法1BdBdKdB 4B4»1BdBi»1Bd»4BiB4B1BdBdKdBd*i4B4»1BdBi»1Bd»4BiB4BSB唔算法的复杂度:时间复杂度、空间复杂度•:•算法的时间复杂度.算法时间复杂度是指执行算法所需要的计算工作量。•工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)釆算法空间复杂度-算法空间复杂度是指执行这个算法所需要的内存空间。•存储空间包括:①算法程序所占的空间.②输入数据所占的空间.①算法执行过程中所需要的额外空间。。数据结构研究的主要内容SBdBdB1Bd»a・1BdBSBdBdBJB4»•**>1B1■，BdBdB1Bd»A・1BdBSBdBdBJB•:•数据结构主要研究以下三个隽面南问题縈数据的逻辑结构:数据集合中各元素的信息，及元素之间所固有的逻辑关系（前后件关系）软数据的存储结构:各数据元素在计算机中的存储关系縈对各种数据结构进行的运算主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法1.2数据结构的基本概念数据元素(DataElement)数据元素是数据的基本单位，即数据集合中的个体。有时一个数据元素可由若干数据项(DataItem)组成。数据项是数据的最小单位。书名作者名分类岀版年月数据元素亦称盘或就。

数据结构类型1BdBdft1 BSBIB«B1B1Bd，Bf线性表LA.线性结构J栈,1.数据的逻辑结构V数据结构的三个方面B.非线性结构树形结构图形结构2、数据的存储结构数据结构的三个方面B.非线性结构树形结构图形结构2、数据的存储结构A顺序存储B链式存储I3、数据的运算：检索、排序、插入、删除、修改等。线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构线性结构和非线性结构•线性结构条件"（1）有且只有一个根结点；米（2）每一个结点最多有一个前件，也最多有一个后件。崇（3）首节点无前件，尾节点无后件。•:•非线性结构:不满足线性结构条件的数据结构•:•注意:在一个线性结构中插入或删除任何一个节点后还应是线性结构；否则，不能称为线性结构。J1姓名成绩张卓100刘忠赏95胡孝臣86学生成绩表线性结构和非线性结构线性结构和非线性结构基本数据结构与算法基本数据结构与算法线性结构和非线性结构线性结构和非线性结构基本数据结构与算法基本数据结构与算法•树形结构学校非线性系别数学系计算机系专业计算机应用计算机软件班级991 995991 995991 995学生张力……李扬全校学生档案管理的树形结构的组织方式基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法存储地址存储内容存储地址存储内容顺序存储与链式存储•顺序存储铁常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。•:•三个弱点费插入或删除操作时，需移动大量元数。栄长度变化较大时，需按最大空间分配。亲表的容量难以扩充顺序存储与链式存储•:•链接存储结构1345每个节点都由两部分组成:数据域和指针域。数据域:存放元素本身的数据，1345指针域:存放指针，体现数据元素之间的逻辑联系元素1 1400 —＞元素2 1536 —＞元素3 1346 —＞元素4 [\•:•链接存储结构特点吒匕顺序存储结构的存储密度小（每个节点都由数据域和指针愈组成）。软逻辑上相邻的节点物理上不必相邻。*插入、删除灵活（不必移动节点，仅改变节点中的指针）。

顺序存储与链式存储存储地址存储内容指针1345元素114001346元素4A1400元素215361536元素313461.31.3线性表基本数据结构与算法基本数据结构与算法1.31.3线性表基本数据结构与算法基本数据结构与算法1.31.3线性表基本数据结构与算法基本数据结构与算法L。元素L。元素1Lo+m元素2Lo+(i-1)*111 兀素i Lo+(n-l)*n元素n存储地址存储内容Loc(a)=L°+(i-l)*m•:•线性表的基本概念线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。•:•非空线性表的结构特征樂有且只有一个根结点al,它无前件；有且只有一个终端结点an,它无后件；縈除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。•:•在线性表上常用的运算有初始化、求长度、取元素、修改、插入、删除、检索、排序。•:•线性表的插入操作•:•在线性表L中第i个数据元素之前插入数据元素e亲检查插入要求的有关参数的合理性亲把原来第n个数据元素至第i个元素（共n・i+l）依次后移一个数组元素的位置。亲把新数据元素放在第i个位置上亲修正线性表的数据元素个数。亲线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：n/21.31.3线性表基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法13线性表sBdBdBdB B1BdB4B1B4»1•」BSBdBdBdBd*>«**B1・」B1BdB•:•线性表的插入操作(KT商复杂言O(n))插入前后移后插入后a。a。aoaiaiai......■..■..al-lal-l插入X一ai-lXala,'1+1al+lai+iai+2..........■last―►an-llast―kan-llast―kanMaxsize-1——►....Maxsize-1 k...■Maxsize-1——►...■•:•线性表的删除操作(时间复杂度O(n))删除前a。ai...■电1删除一aial+l...■last―kan-l...■maxsize―k删除后ao

a.a】.iai+iai+2last—k an-lmaxsize―►进栈出栈进栈出栈1.4栈和队列IBS1BdBSBa・・**■」BdB1 ■」fedBdBi•，Bl**tJ・・**■」BdB1 B♦•■二,■，.■“*■r，■，,■，,■“.■•,■「•■/ •■二,■，.■“*■r，■，,■，,■“.■•,■「•■/栈和队列是两种运算时要受到某些特殊限制的线性表，故也称为限定性的数据结构。•:•栈：限定只能在表的一端进行插入和删除的特殊的线性表,此种结构称为后进先出。设栈S=(alfa2f…,aif...fan)其中al是栈底元素，an是栈顶元素。栈顶(top):允许插入和删除的一端；栈顶一约定top始终指向新数据元素将存放的位置。栈底(bottom):不允许插入和删除的一端。栈底1.41.4栈和队列1.41.4栈和队列1.41.4栈和队列基本数据结构与算法基本数据结构与算法•队列):限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先岀(FIFO)表。队尾队尾•:•队列的主要运算设置一个空队列;插入一个新的队尾(rear)元素，称为进队；删除队头(front)元素，称为出队；读取队头元素；•:•队列的主要运算奈队空时，令rear=front=0;元素个数=rear-front栄当有新元素入队时，尾指针加1,当有元素岀队时，头指针加1。故在非空队列中，头指针始终指向队头元素前_个位置，而尾指针始终指向队尾元素的位置rear=front=0(队空)(b)el,e2,e3rear=front=0(队空)(b)el,e2,e3入队(c)el,e2出队,e4入队基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法1.4栈和队列广，“B«3BIB1»1Bd，B4BdBf**BIBl■广，BflBdBdB«**BIB1»1Bd，B4BdBf**BI■」»1'•.F.—，•.T・■♦,M♦,.F*.■*•.F•.F.■，♦—**・■,•Mt..F・MF•.T•.「•.T•.T・■♦,M♦,.F*•M.F•.T'<■，,.f,,Mt,.,.MF,.T|•:•循环队列:首尾相接的队列，逻辑上形成一个环状。♦:♦循环队歹！J元素个数=(rear-front+n)modn1.5线性链表•:•线性表顺序存储结构的特点简单，方便，要求数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。♦:♦暴露的问题在做插入或删除元素的操作时，会产生大量的数据元素移动；亲对于长度变化较大的线性表，要_次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；亲线性表的容量难以扩充。1.5线性链表■LI将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。■LI数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。线性链表分为:单链表，双链表，循环链表带头结点的单链表S・IIll1a卷音：Sa基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法1.5线性链表单链表的插入运算:在节点a之后插入一新节点p-QQ—p-nnET1.5线性链表1，BflBd■广■广»1fed，“B4B«**BIBd»!*•d，BflBd■广■:

,■r.■， ,t＞，,V*,■尸•■•,■， ，■，,■”，・，，■，，■，•■,,■，,■，.■， ,t＞，,V*，■，单链表的删除运算：删除节点为1.5线性链表，ftflBd•广■广d，，BdBIB1 BdftflBd•广■广■」»l^td，，BdB«**»IB1»,Vr•■，,・>，■，,Wr，■，•■，,■,,■，.■，,■“,■，，■，•■尸•■，•■，,Vr。・>，■，,Wr，■，•■，,■,,■，.■，,■“,■，，■，•■尸•■，•■，•:•线性链表的特点*插入、删除节点方便（不必移动节点，仅改变节点中的指针）*只能顺序存取（查找只能从头指针开始）,不能随即存取。*适应于数据的动态变化基本数据结构与算法1.6树与二叉树•:•树的定义:由一个或多个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。基本变ns结构与鼻法1.61.6树与二叉树基本数据结构与算法基本数据结构与算法1.61.6树与二叉树基本数据结构与算法基本数据结构与算法bM互不A:树中的元素reebM互不A:树中的元素ree):【开始树的基本概念:结点(Node)结点的度(De结点的局叶子孩兄基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法1.6树与二叉树flB1Bdft1BdB4BflB1fe1B«B1»dBfBIBIBflBdBdft1BdB4Bfl・JBIfe1B«B1»dBfBIBIB1B,■「•■， ,■、，■，*wy•■••■，,■「•wr■■，,■，,■”,■，・■，,■「.■， ,■、，■，*wy•■••■，,■「•wr■■，,■，,■”,■，・■，,■「♦:♦二叉树(BinaryTree)的定义二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。空二叉树左子树为空左右子树均非空空二叉树左子树为空左右子树均非空二叉树的五种基本形态1.61.6树与二叉树基本数据结构与算法基本数据结构与算法1.61.6树与二叉树基本数据结构与算法基本数据结构与算法满二叉树特点:所有分支结点都存在左右子树，且所有叶子结点都在同一层上。

完全二叉树特点:除最后一层外，每一层都取最大结点数，最后一层结点都集中在该层最左边的若干位置。非完全二叉树1.61.6树与二叉树基本数据结构与算法基本数据结构与算法1.61.6树与二叉树基本数据结构与算法基本数据结构与算法1.61.6树与二叉树二叉树的基本性质二叉树的第k层上至多有2k1（k>l）个结点。B、 深度为h的二叉树中至多含有2丄1个结点。若在任意一棵二叉树中，有n°个叶子结点（度为0）,有n?个度为2的结点，则：n0=n2+lD、 具有n仓结点的完全二叉树的深度为[Iog2n]+1,其中[log2n]表示log2n的整数部分。第三层（i=3）,有23」=4个节宙度h=4,共有24・1=15个节点n0=8fn2=7fn0=n2+l15个节点，深度[log215]+l=4基本数据结构与算法二叉树的遍历遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍历:前序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。遍历算法先序遍历:DLRABDC

中序遍历:LDRBDAC

后序遍历:LRDDBCATiT2T3以先序遍历DLR为例汶示遍历过程基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法1.7査找技术•:•查找:在一个给定的数据结构中，根据给定的条件找到满足条件的结点。不同的数据结构采用不同的查找方法。查找的效率直接影响数据处理的效率。•:•平均查找长度:查找过程中比较的次数•:•查找的结果縈查找成功:找到满足条件的结点縈查找失败：找不到满足条件的结点。1.7査找技术•:•顺序查找(线性查找)对给定的一关键字K,从线性表的一端开始，逐个进行记录的关键字和K的比较，直到找到关键字等于K的记录或到达表的另一端。栄可以采用从前向后查，也可采用从后向前查的方法。栄在平均情况下，大约要与表中一半以上元素进行比较,效率较低。平均查找长度二(n+l)/2。*时间复杂度=O(n)*在下面两种情况下只能采取顺序查找:•线性表为无序表(元素排列是无序的)；，即使是有序线性表，但采用的是链式存储结构。1.7査找技术折半查找（二分法查找）•:•思想:先确定待查找记录所在的范围，然后逐步缩小范围,直到找到或确认找不到该记录为止。•:•前提:必须在具有顺序存储结构的有序表中进行。•:•分三种情况:*若中间I页的值等于x,则说明已査到。*若x小于中间项的值，则在线性表的前半部分査找；*若X大于中间项的值，则在线性表的后半部分査找。•:•特点:比顺序查找方法效率高。最坏的情况下，需要比较log?”次。査找23和79的过程如下图：9元素mid=(low+high)/2不进位取整(08, 14, 23,Imid(08,14,23,37.(08, 14, 23,Imid(08,14,23,37.46,55,68,79,91)1lowIhigh(08,14,23,37,46,55,68,79,91)▲1low|mid[high(08,14,23,37,46,55,68,79,91)low=mid+l46, 55, 68, 79, 91)lowmidhigh(08,14,23,37,46,55,68,79,(08,114,23,37,46,▲55,68,79,1low|mid(08,23,46,55,68,79,high=mid・l191)91)Ihigh91)

1.8排序技术排序的功能：将一个数据元素（或记录）的任意序列，囱排成一个按关键字有序的序列。排序过程的组成步骤首先比较两个关键字的大小；然后将记录从一个位置移动到另一个位置。排序方法V选择排序排序方法V选择排序满入排序交换排序［直接，折半插入排序1希尔排序|简单选择排序I堆排序.起泡排序1快速排序基本数据结构与算法基本数据结构与算法、归并排序基本数据结构与算法基本数据结构与算法基本数据结构与算法基本数据结构与算法1.8.1交换类排序法（P40）交换排序的特点在于交换，有冒泡和快速排序两种。泡排序（起泡排序）泡排序（起泡排序）思想:小的浮起，大的沉底。从左端开始比较。第一趟：第1个与第2个比较，大则交换；第2个与第3个比较,大则交换，关键字最大的记录交换到最后一个位置上；第二趙:对前n・l个记录进行同样的操作，关键字次大的记录交换到第n.l个位置上；依次类推，则完成排序。最好正序：时间复杂度为O（n）最差逆序：时间复杂度为。（俱）排序n个记录的文件最多需要n・l趟冒泡排序。

2525252511111156494911252525495611494136367811564136411165413649第六越排序后65413656第五趟排序后413665第四趟排序后3678第趟排序后第一趟排序后初始关键字第趟排序后%1.8.1交换类排序法一示例1.8.1交换类排序法一示例各种排序法比较樊别排序方法基由思想时间复杂度交换类冒泡排序相邻元素比较，不满足条件时交换n(n-l)/2快速排序迷择基准兀素，逋过交换，划分成两个子序列0(nlog2ii)插入类简单插入排序待排序的兀素看成为J个伯序表和J个无序表，将无序表中元素插入到有序表中n(n-l)/2希尔排序分割成若千个子序列分别进行直接插入排序0(4)选择类简单选择排序扫描整个銭性表，从中选出最小的元素，将它交换到表的最前面"垢1)/2堆排序选建堆，然后将堆顶元素与堆中最后一个元素交换，再调整为堆0(nlog2ii)过关练习【2010.9】(3)一个栈的初始状态为空。首先将元素5,4,321依次入栈，然后退栈一次，再将元素A,B,C,D依次入栈，之后将所有元素全部退栈，则所有元素退栈(包括中间退栈的元素)的顺序为[WCBA2345 ]0[2010.9](4)在长度为n的线性表中，寻找最大项至少需要比较【1 】次。二级ACCESS—查询[2010.9](5)一棵二叉树有10个度为1的结点，7个度为2的结点，则该二义树共有【二级ACCESS—查询

过关练习[2010.3](8)—个队列的初始状态为空。现将元素A,B,C,D,E,F,5,4,3,2,1依次入队，然后再依次退队，则元素退队的顺序为【A,B,C,D,E,F,5,4,3,2,1】。i=.==12010.3](9)设某循环队列的容量为50,如果头指针front=45(指向从头元素的前一位置)，尾指针rear=10(指向队尾元素)，则该循环队列中共有i=.==[2010.3](10)设二叉树如下：对该二叉树进行后序遍15】个元素。历的结果为【EDBGHFCA】15】个元素。二级二级ACCESS—查询二级二级ACCESS—查询过关练习flBd"B4“飞广・厂・4B1Bd虹，B1Bfl•广[JfcjB1_B4心。广7、广Bd^Bd，i>1*>1_Bl^>1 1A_ -7TV*11对下列土叉树进行前序遍历的结果为7TV*11!A)DYBEAFCZXB)YDEBFZXCA叱)ABDYECFXZD)ABCDEFXYZ[2008.9](9)对下列二叉树进行

过关练习[2007.9](13)对下列二叉树进行中序遍历的结果[ACBDFEHGP】公尖戛础列识徨序D2软幷H浸妥础二级二级ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础本章的重要性•据统计，本章在每次理论考试中占10%左右•:.本章在考试中只涉及笔试题上机不考。关键考点•结构化程序设计的基本概念•面向对象程序设计的基本概念•软件的概念和软件的分类软件测试的目的•软件生命周期软件设计划分模块原则软件测试的概念和分类本章主要内容•程序设计方法和风格•结构化程序设计•面向对象程序设计•软件工程基本概念•结构化分析方法•软件测试•程序的调试•过关练习2.1程序设计方法和风格•:•什么是程序嵌指令的集合。（解释指令）柴通过硬件控制系统自动完成某一功能。Subsubone。DimyAsIntegerStaticzAsIntegery=10x=yz=z+1 ,*通过一系列代码实现。•:•程序设计语言亲计算机本身仅能识别二进制代码"0\亲编译程序和解释程序亲编程最直接，最低级的就是机器语言。亲汇编语言。Debug.Print:subone()执行“Debug.Print &xDebug.Print"z二"&zEndSub"1飴丄o*高级语言。如C、PASCALFORTRAN,BASIC,一%—口三L事_二级ACCESS—软件设计及软件工程基础2-1程序设计方法和风格•:•程序设计风格（清晰第一，效率第二）基本概念:编写程序时所表现出来的特点，习惯和逻辑思路。一般从以下四部分加以规范:源程序中的内部文档:选择标示符的名字、注释（序言性和功能性注释）■程序的视觉组织。楽数据说明：显式地说明一切变量，数据说明的次序应该规范化，便于查找变量（按顺序排列）,对复杂数据结构应注释说明*语句的结构:每条语句简单明了、尽量不用或少用GOTO语句、尽量只采用3种基本控制结构编程*输入和输出：对所有输入数据进行校验和合理性检查、输入输出格式保持一致,设计良好的输出报表二级ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础2.2结构化程序设计•:•基本思想对大型的程序设计，使用一些基本的结构来设计程序，无论多复杂的程序，都可以使用这些基本结构按一定的顺序组合起来。这些基本结构的特点都是只有一个入口.一个出口。由这些基本结构组成的程序就避免了任意转移，阅读起来需要来寻找的问题。•:•设计原则自顶向下逐步求精模块化限制使用got。语句

2.3面向对象程序设计SB1BdftSBd**i•**>4Biftd・GfeJ»1*BIB1BJBSB1BdftSBd**i•**>4■」BSftd・GI.....「・.，..，..“ ・.，.....’’..尸•.，..尸 ・.，..「・.，..，..“ ・.，.....’’..‘•:•基本思想客观世界中任何一个事物都可以被看成是一个对象，面向对象方法的本质就是主张从客观世界固有的事物出发来构造系统，系统中的对象及对象之间的关系能够如实地反映问题域中有的事物及其关系。•:•结构化与面向对象方法比较亲结构化的分解突出过程，即如何做(Howtod。)?它强调代码的功能是如何实现的；亲面向对象的分解突出现实世界和抽象的对象，即做什么(Whattodo)?(Whattodo)?2.3面向对象程序设计•:•主要优点*与人类习惯的思维方法一致*稳定性好*可重用性好*易于开发大型软件产品*可维护性好面向对象程序设计主要考虑的是提高软件的可重用性!二级二级ACCESS—软件设计及软件工程基础23面向对象程序设计'JO0O•;?<••:?•；?•；?OO,；?•；•<?<? <；•.；,o.%舟•:•面向对象的基本概念对象(Object)•对象是基本的运行时认得实体，它既包括数据(属性)，也包括作用于数据的操作(行为)。一个对象把属性和行为封装为一个整体一个对象通常可由对象名,属性和操作3部分组成对象的基本特点:标致唯一性、分类性、多态性、封装性面向对象(ObjectOriented,OO)•从该问题所涉及的对象入手来研究问题。(Message)nl对象之间进行通信的一种数据构眞，消息瞩:鶯専遣鼻对緜、nl消息标识符.零个或多个参数三薮accessMM膝竅样工23面向对象程序设计•:•面向对象的基本概念*类(Class)一个类定义了一组大体上相似的对象。一个类所包含的方法和数据描述一组对象的共同行为和属性。•类是在对象之上的抽象，对象是类的具体化，是类的实例奈封装(Encapsulation)•将数据和操作数据的函数衔接在一起，构成一个具有类类型的对象的描述。•对象的内部实现受保护，外界不能访问•封装简化了程序员对对象的使用2.3面向对象程序设计0BJBJB«B1B1，广，■广，,广■广B1>]B1Bd**Bd»d*B4B1Bd，广，B1*1•:•面向对象的基本概念奈继承(Inheritance)•继承是父类和子类之间共享数据的方法的机制•一个子类可以继承它的父类(或祖先类)中的属性和操作•子类中可以定义自己的属性和操作•单重继承,多重继承多态性(Polymorphism)•不同的对象收到同一消息可以产生完全不同的结果，这一现象叫做多态性•多态的实现受到继承的支持二级ACCESS—软件设计及软件工程基础3.1软件工程基本概念•:•软件的定义软件(software)是计算机系统中与硬件(hardware)相互依存的另一部分。软件包括三个部分:程序(program).相关数据(data).说明文档(document)o*软件的特点*软件是話逻辑实体，不是物理实体，具有抽象性。栄软件没有明显的制造过程。栄软件在使用过程中，没有磨损,老化问题TOC\o"1-5"\h\z縈软件依赖与硬件和环境，导致了移植问题 每栄软件是复杂的，而且以后会更复杂 P4栄软件的成本相当昂贵 堀"I*软件工作牵涉到很多社会因素 C3.1软件工程基本概念•:•软件危机早期的软件主要指程序，采用个体工作方式，缺少相关文档,质量低，维护困难，这些问题称为〃软件危机“，软件工程概念的岀现源自于软件危机。•:•软件工程软件工程是指应用计算机科学、数学及管理科学等原理，以工程化的原则和方法来解决软件问题的工程。其目的是提高软件生产率，提高软件质量，降低软件成本。•:•软件工程基本目标在给定成本，进度的前提下，开发出具有有效性，可靠性.可理解性,可维护性,可重用性,可适应性,可移植性,可追踪性和可互操作性且满足用户需求的产品。必珞*8廿功二幾ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础软件工程基本概念•:•软件工程三要素亲方法：完成软件工程项目的技术手段亲工具:支持软件的开发，管理，文档生成亲过程:支持软件开发的各个环节的控制，管理•:•软件工具和软件开发环境软件工具(CASE):用来辅助软件开，运行，维护，管理.支持等过程中的活动的软件软件开发环境：支持软件产品开发的软件系统，它由软件工具集和环境集成机制构成

软件工程基本概念•:•软件生命周期软件产品从提出,实现,使用维护到停止使用退役的过程称为软件生命周期。分为软件定义，软件开发及软件运行维护3个阶段。1）软件定义阶段:1）软件定义阶段:括制定计划和需求分析。■制定计划:确定总目标；可行性研究；探讨解决方案；制定开发计划。,需求分析:对待开发软件提出的需求进行分析并给出详细的定义。*2）软件开发阶段:-软件设计:分为概要设计和详细设计两个部分。软件实现:把软件设计转换成计算机可以接受的程序代码。,软件测试：在设计测试用例的基础上检验软件的各个组成部分。3）软件运行维护阶段（生命周期中花费最多的阶段）:软件投入运行，并在使用中不断地维护，进行必要的扩充和删改。3.2结构化分析方法•:•需求分析用户对目标软件系统在功能，行为，性能，设计约束等方面的期望。需求分析的任务是发现需求.求精.建模和定义需求的过程。需求分析将创建所需的数据模型，功能模型和控制模型。•:•需求分析的四步9需求获取，需求分析，编写需求规格说明书和需求评审•:•需求分析的方法结构化分析方法，面向对象分析方法3-2结构化分析方法结构化分析方法结构化程序设计理论在软件需求分析阶段的运用，其目的是帮助弄清用户对软件的需求。•:•常用工具*数据流图、数据字典、判定树、判定表•:•开发策略采自顶向下，逐层分解3.23.2结构化分析方法二级二级ACCESS—软件设计及软件工程基础3.23.2结构化分析方法二级二级ACCESS—软件设计及软件工程基础•:•数据流圏（DFD）:以图形的方式描绘数据在系统中流动和处理的过程，它反映了系统必须完成的逻辑功能，是结构化分析方法中用于表示系统逻辑模型的一种工具。数据流存储文件源、潭数据流存储文件源、潭縈加工（转换）：输入数据经加工变换产生输出。*数据流:沿箭头方向传送数据的通道，旁边标注数据流名。*存储文件（数据源）:表示处理过程中存放各种数据的文件。栄源.潭：表示系统和环境的接口，属系统之外的实体。•:•数据字典(DD):对所有与系统相关的数据元素的一个有组织的列表，其作用是对数据流图中出现的被命名的图形元素的确切解释。*数据字典常包括5个部分:数据项、数据结构、数据流、数据存储、数据处理。*数据字典是结构化分析方法的核心•:•软件需求规格说明书(SRS):需求分析阶段的最后成果，通过建立完整的信息描述、详细的功能和行为描述、性能需求和设计约束的说明、合适的验收标准，给出对目标软件的各种需求。二级二级ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础结构化设计方法一软件设计的基础•:•从工程角度来看，软件设计分两步完成，即概要设计和详细设计。*概要设计：又称结构设计，将软件需求转化为软件体系结构；确定系统级接口,全局数据结构或数据库模式；编写概要设计文档、概要设计文档评审。*详细设计：确定每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节。3.3结构化设计方法一软件设计的基础1BdB4Bd»IBIBI**!1BdB1B4»flBIB1**B1Bdft4Bd»•**>I■■BI**!1B<**14BdB1BIB1**B•:•软件设计基本原理:抽象：模块化、信息隐蔽和模抽象：抽象是一种思维工具，就是把事物本质的共同特性提取出来而不考虑其他细节。模块化:解决一个复杂问题时自顶向下逐步把软件系统划分成较小的、相对独立但又不相互关联的模块的过程。信息隐蔽:模块的实施细节对于其他模块来说是隐蔽的。模块独立性:软件系统中每个模块只涉及软件要求的具体的子功能，和软件系统中其他模块的接口是简单的。・模块独立性指标:耦合性和内聚性-模块划分原则是：高内聚度，低耦合度数据信息二成靈愚软件设计及软件工程基础数据信息二成靈愚软件设计及软件工程基础33结构化设计方总体设计•:•总体设计（概要设计）基本任务T）设计软件系统结构亲2）数据结构及数据库设计禁3）编写概要设计文档禁4）概要设计文档评审•:•软件结构设计工具一S构圏（程序结构圏）亲程序结构图的基本图符•矩形表示模块，箭头表示模块间的调用关系•用带注释的箭头表示模块调用过程中来回传递的信息•实心圆箭头表示控制信息，空心圆箭头表示数据信息二级二级ACCESS—软件设计及软件工程基础二级二级ACCESS—软件设计及软件工程基础3.3结构化设计方法一详细设计•:•详细设计基本任务媛为软件结构图中的每个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节•:•常用设计工具*图形工具:程序流程图、N-S（方盒图）、PAD（问题分析图）和HIPO（层次图+输入/处理/輸出图）。*表格工具:判定表。縈语言工具:PDL（伪码）3.4软件测试的,意义,人员亲通过合理的设计测试用例以最少的人力和时间发现潜在的各种错误和缺陷楽保证系统质量（满足需求规格）和可靠性亲由开发人员.用户一起完成•测试基本方法*人工测试（静态测试）：评审软件文档或程序，包括代码检查,静态结构分析,代码质量度量。不实际运行软件，主要通过人工进行。*机器测试（动态测试）：通过运行软件，来检验结果的正确性。主要包括白盒测试方法和黑盒测试方法。3.4软件测试一白盒测试1B4B4»«*"• 1BflfedB1Bd**B•**»1B«*•1B4B»«*"••**>1・dBflfedB<*t1■•Vr ,■, ，■尸，■，•■，，■>*Vr♦■，，■，，■，，■,•Wr ,■, ，■尸，■，•■，，■>*Vr♦■，•:•白盒测试（结构测试,逻辑驱动测试）楽将软件看成透明的白盒，根据程序的内部结构和逻辑结构来设计测试例子，对程序的踣径和过程进行测试，检查是否满足设计的要求•:•白盒测试基本原则柴保证所测模块中每一独立路径至少执行一次；楽保证所测模块所有判断的每一分支至少执行一次；栄保证所测模块每一循环都在边界条件和一般条件下至少各执彳亍一次；二是证所有内冒数据结构的有效性。3.4软件测试一白盒测试•:•测试用例根据程序内部逻辑设计，主要用于软件的单元测试。•:•用例主要设计方法有媛逻辑覆盖:指一系列以程序内部的逻辑结构为基础的测试用例设计技术。*基本路径测试：根据软件过程性描述中的控制流程确定程序的环路复杂性度量，用此度量定义基本路径集合，并由此导出一组测试用例，对每一条独立执行路径进行测试。3.4软件测试一黑盒测试•:•黑盒测试（功能测试）栄将软件看成黑盒子，不考虑程序内部细节，结构和实现方式，仅仅测试软件的基本功能是否满足需要。栄黑盒测试主要用于软件的确认测试。根据程序的功能说明来设计测试用例，基本设计方法有■等价类划分法：典型黑盒测试方法，将