大学计算机基础算法与数据结构基础.ppt

算法与数据结构基础算法n 算法是解题方案的准确而完整的描述。具有可行性，确定性，有穷性，有足够的情报输入与输出。n 算法要素：数据的运算和操作+控制结构；n 运算与操作：算术，逻辑，关系，数据传输（赋值，输入，输出等）；n 控制结构：顺序，选择，循环；n 算法的常见描述方法:n 自然语言方式 n 伪代码方式 n 程序流程图方式 n N/S盒图方式算法描述-伪代码n 介于自然语言和程序语言之间的一种描述方法，与具体编程语言无关。Keep track of current number of resources in use If another resource is available Allocate a dialog box structure If a dialog box structure could be allocated Note that one more resource is in use Initialize the resource Store the resource number at the location provided by the caller Endif Endif Return TRUE if a new resource was created;else return FALSE算法描述-程序流程图n 算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。n 流程图的常用结点及控制结构描述如下：端点符 处理 判断 预定义功能 连接符条件处理1 处理2选择结构循环结构或是条件否处理当型条件处理否是直到型处理1处理2顺序结构算法描述-N/S盒图方式开始读n个数到数组anfor i=1 to n-1 step 1k=ifor j=i+1 to n step 1 查找第 i 个数据后面的最小元素aj ak否是 k=ji!=k否是交换两个元素x=aj aj=ak ak=x结束算法设计基本方法n 列举法n 归纳法n 递推法n 递归法n 回溯法列举法n 设每只母鸡值3元，每只公鸡值2元，每只小鸡值0.5元。现要用100元钱买100只鸡，设计买鸡方案。递推法n 假定一对刚出生的小兔子，一个月后就能长成大兔子，再过一个月后就开始生小兔子，并且也正好生一对兔子。问在没有兔子死亡的情况下，一对初生的兔子一年后可繁殖成多少对兔子。算法的复杂度n 空间复杂度：占用的存储空间大小n 时间复杂度：编译时间+运行时间(1)a=b;/O(1)-时间复杂度为常数值(2)for(int i=0;in;i+)a=b;/O(n)-时间复杂度为一阶值(3)for(int i=0;in;i+)for(int j=0;jn;j+)a=b;/O(n2)-时间复杂度为二阶值 数据结构的基本概念n 数据：数据是信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。n 数据元素：数据处理中具有独立意义的个体。元素可能是数也有可能是记录。n 数据结构：数据结构是指组成数据的元素之间的结构关系（线性结构，树形结构）。n 逻辑结构：数据的逻辑结构（如线性结构和非线性，如树形结构）。n 物理结构：数据的存储结构（线性存贮，链式存贮）。逻辑结构线性结构（线性表）n 一个线性表是n个数据元素的有限序列。n 其存储空间是连续的，各个数据元素在存储空间是按逻辑顺序依次存放的。只有一个跟结点，每个结点只有一个前后件。n 限定性的线性表结构：n 栈：后进先出（进入和删除都在一端）n 队列：先进先出（进入在尾部和删除在头部）线性和链式存贮结构n 线性存储结构具有简单、操作方便、占用空间少的优点，但做插入和删除时需要移动大量的元素，并且需要足够大的成块的内存。n 链式存储结构：每个存储节点由两部分构成，一部分用于存放数据，一部分用于存放指针（记录前一个或后一个节点的地址）。用一个专门的指针（称为头指针）指向第一个数据节点。1)单向链结构 2)双向链结构 3)多向链结构 非线性结构树与二叉树n 数据元素具有层次关系，并以分支关系定义了层次结构。n 父结点（结点的前驱结点），子结点（结点的后继结点），根结点（无前驱结点的结点），叶子结点（无后继结点的结点）。n 结点所拥有的子树的棵树被称为度。二叉树基本性质n 二叉树：只有一个跟结点，每个结点度最大为2n 性质1 二叉树第i层上的结点数目最多为2i-1(i1)。n 性质2 深度为m的二叉树至多有2m-1个结点(k1)。证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：20+21+2k-1=2k-1 故命题正确。n 性质3 在任意-棵二叉树中，若度为零的结点为n0，度为2的结点数为n2，则no=n2+1。特殊形态二叉树n 满二叉树：深度为m且有2m-1个结点的二叉树。即每一层的所有结点数都达到最大值。n 完全二叉树：除最后一层外，每一层结点数都达到最大值；在最后一层只缺少右边的若干结点。二叉树的遍历n 首先访问根结点为前序，先左再根再右为中序，先左再右再根为后序n 前序：A B D C E Fn 中序：D B A E C Fn 后序：D B E F C A查找技术n 顺序查找：无序表，采用链式存储结构的有序线性表。n 折半查找：有序表（需要排序）。n 最坏情况下顺序查找需要比较m次，折半查找需要log2m次。1.5 程序设计基础程序设计的重要性n 程序是计算机的一组指令，是程序设计的最终结果。n 程序经过编译和执行才能最终完成程序的功能。n 高级程序设计语言的出现使得程序设计不仅是计算机专业人员必备知识，也是各行各业专业技术人员必须掌握的技术。程序设计方法与风格n 程序设计应该简单清晰，为了测试和维护应该遵循“清晰第一，效率第二”的风格。n 注意以下因素：n 源程序文档化（符号命名规律，程序注释，视觉组织）n 数据说明便于理解和维护（次序规范便于查找）n 语句结构简单直接（一行一句，避免使用零时变量，模块功能应单一，不用无条件转移，不良程序应重新编写）n 输入输出方便并能进行合理性检查（输入输出数据合法性，合理检查，输入数据应尽可能少，人机会话界面）两种程序设计方法n 结构化程序设计n 程序=数据结构+算法n 面向对象程序设计n 程序=对象+消息1、结构化程序设计n 结构化程序设计：Structured Programmingn 基本原则：n 采用自顶向下，逐步求精的方法：先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标，逐步使得问题具体化。n 模块化：每一个小问题构成一个模块，模块只有一个入口和出口，一个功能。n 禁用无条件转移（GOTO）n 好结构的程序具有结构清晰，容易阅读，容易理解，容易验证，容易维护的特点。n 可以证明采用三种结构可以表达出各种其它复杂形式的程序结构。n 三种结构：顺序，选择，循环端点符 处理 判断 预定义功能 连接符条件处理1 处理2选择结构循环结构或是条件否处理当型条件处理否是直到型处理1处理2顺序结构2、面向对象的程序设计n 面向对象：Object Orientedn 对象即客观世界中的实体，客观世界中的实体都具有静态的属性和动态的行为。n 程序设计中的对象：在编程中将实体表示成一组表示其静态特征的“属性”（property）和它可执行的一组操作组成即“方法”（method）。n 属性即对象所包含的信息，用来描述对象的状态。n 操作（方法）描述了对象的行为，操作的过程对外界来说是不可见的，是封装到对象中的，用户只能看到结果，或者调用这个操作。n 对象实际是对数据和专属操作的封装，是更高级的封装形式。n 对象的基本特点：标识唯一性，分类性（抽象成类），多态性，封装性。n 类是对象的抽象，是具有共同属性、共同方法的对象的集合。描述了对象类中所有对象的性质和行为。对象则是对应类中的实例。类（class）和实例（Instance）类和实例（Class，Instance）二维图形直线 圆形 方形 三角形R=3cm 4cm 5cmColor=red blue green 实例消息（Message）n 消息是一个实例与另一个实例之间传递的信息。n 封装的对象通过“消息”完成合作与信息传递。“消息”是面向对象世界的协作机制。n 消息的传递：“消息”包括接收消息的实例，操作名和参数表（数据流和控制流），接收“消息”的实例会因此产生一系列的操作。n 特点：发送者只提要求，接收者完全独立的处理。传输消息可以1对多也可以多对1。继承（Inheritance）n 继承是使用已定义的类作为基础建立新类（派生类）的定义技术。n 面向对象软件技术的优点在于可以把类组成一个层次结构系统，子类继承了父类的数据和操作。n 采用继承可以节省大量的重复工作，提高软件可重用性，便于维护和管理。二维图形CGdiObjectCPen CCircle CRect CTri r=3cm 4cm 5cm 实例 CPen笔，画线 CBrush刷子，填充 CFont字体，控制文字输出的字体 CBitmap位图 CPalette调色板 CRgn区域，指定一块区域可以用于做特殊处理。CFile文件。最重要的不外是Open（打开）,Read（读入）,Write（写）CString字符串。封装了C中的字符数组，非常实用。CPoint点，就是（x,y）对 CRect矩形，就是（left,top,right,bottom）多态性（Polymorphism）n 多态性是指用一个名字定义不同的函数，这函数执行不同但又类似的操作，从而实现“一个接口，多种方法”。n 通过在基类中定义虚方法(virtual)，在子类中，可以通过override进行派生重写。n 这样增加了面向对象编程的灵活性（有继承有变革）。面向对象方法的特点n 与人类思维方法一致n 稳定性好n 可重用性好n 易于开发大型软件n 可维护性好MFC(Microsoft Foundation Classes)n MFC是对WindowsAPI的封装，大大简化了我们的工作；学VC主要就是要学MFC.n MFC大约有100多个类，但常用的也就二三十个。n CWnd：窗口，它是大多数“看得见的东西”的父类n CDocument文档，负责内存数据与磁盘的交互n CView视图，负责内存数据与用户的交互。包括数据的显示、用户操作的响应（如菜单的选取、鼠标的响应）n CWinApp应用程序类。似于C中的main函数，是程序执行的入口和管理者，负责程序建立、消灭，主窗口和文档模板的建立软件工程基础软件开发的演化过程个人编程时代（46年50年代末）软件开发是科学家们根据各自的应用需要写出的能够解决预定问题的运行程序。程序生产的效率极低，可靠性难以保证，且仅限于处理比较简单的数值计算问题 软件作坊时代(60年代初一60年代未)软件作坊的开发方法是个体的或小组的思维行为，使得软件任务延误、质量不可靠、甚至无法维护，极大地制约了计算机以后)的功能发挥和实际应用。软件工程时代(70年代-)在世界范围内出现了许多组织严密、管理科学、手段先进、工具齐全的软件开发公司，为计算机软件市场提供了大量成功的软件产品。80年代，明确提出了“软件工程支撑环境”的思想，使程序设计可以直接从支撑环境中调用所需的各个“组件”。软件工程基本概念n 计算机软件的数量迅速增加，软件规模不断增加，投入的人力资金十分巨大，成本不断上升。如何保证软件开发的速度和质量成为一个十分严重的问题，必须采用软件工程的思想和方法解决。n 对软件开发成本和进度的估算很不准确n 质量很不可靠n 没有适当的文档n 软件成本比重上升n 速度慢：软件开发生产率跟不上计算机应用迅速深入的趋势 硬件软件100%0%1955 19701985硬件/软件成本变化趋势n 原因n 客观：软件本身特点n 逻辑部件n 规模庞大n 主观：不正确的开发方法n 忽视需求分析n 错误认为：软件开发=程序编写n 轻视软件维护n 软件定义：软件=程序+数据+文档n 程序：按事先设计的功能和性能需求执行的指令序列n 数据：是程序能正常操纵信息的数据结构n 文档：与程序开发、维护和使用有关的图文材料软件工程n 软件工程:借鉴从事工程项目所积累的原理、概念、技术和方法来开发和维护软件，把正确的管理和科学的技术结合起来，这就是软件工程。n 软件工程=开发技术+工程管理n 软件开发技术n 软件开发方法学，软件开发工具，软件开发环境n 软件工程管理n 软件管理学n 软件经济学n 软件心理学软件生存周期模型 软件产品从形成概念开始，经过开发、使用和不断增补修正，直到最后被淘汰的整个过程。按照软件工程的思想，这个过程又可划分成若干个互相区别而又有联系的阶段。软件生命周期瀑布式生存周期模型（1）可行性研究与计划阶段 明确“要做什么”及“是否能做”（2）需求分析阶段 弄清“必须做什么”（3）设计阶段“如何做”和“如何具体做”（4）实现阶段 源程序的编码、编译及程序单元测试。（5）测试阶段 总装测试和确认测试（6）运行与维护阶段 根据新提出需求，扩充和修改软件两类软件工程方法n 传统软件工程：n 软件分析 总体设计 详细设计 面向过程的编码 测试 n 面向对象软件工程n 软件分析对象抽取 对象详细设计 面向对象的编码 测试 软件测试n 软件测试是在软件投入生产性运行之前，对软件需求分析、设计规格说明和编码的最终复审，是软件质量保证的关键步骤。n 软件测试是为了发现错误而执行程序的过程。测试方法一、静态测试与动态测试（一）静态测试方法 静态测试一般指人工评审软件文档或程序，以便发现错误。静态测试包括：代码检查、静态结构分析、代码质量度量等。（二）动态测试方法 动态测试是在样板测试数据上执行程序并分析输出以发现错误的过程。所以动态测试包括三部分：生成测试数据、执行程序与验证的输出结果。二、白盒测试与黑盒测试任何工程产品都可以使用以下两种方法之一进行测试：（1）已知产品的功能设计规格，可以进行测试证明每个实现了的功能是否符合要求。（2）已知产品的内部工作过程，可以通过测试证明每种内部操作是否符合设计规格要求，所有内部成分是否已经过检查。前者是黑盒测试，后者是白盒测试。程序调试程序调试的基本步骤(1)错误定位从错误的外部表现形式入手，研究有关部分的程序，确定错误位置找出错误的内在原因。(2)修改设计和代码，以排除错误排错是软件开发过程中一项艰苦的工作，这也决定了调试工作是一个具有很强技术性和技巧性的工作。(3)进行回归测试，防止引进新的错误