第四章软件技术基础1.ppt

第四章 软件技术基础;第一步把8转成二进制: 10110000 11110100 ;程序为：;3. 高级语言;int s; s=8+4;;语言简洁、紧凑、使用方便、灵活;面向对象的C++语言。它是在C语言的基础上增加了面向对象的内容。C++的学习比C语言更为困难。从目前的发展看，C++的应用更为普及。;4 FORTRAN 语言;5 VISUAL BASIC;8 程序设计的基本过程;4.1 算法语言简介;例2 求1+2+3+4+5……n表达式的值(假设n=100) ;(4)输出：要求算法有一个或多个输出;例 下列对算法特性描述正错误的是(2005年9月);(4)效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间,即:要有较优时间效与空间效率。;3. 算法效率的度量;例1 将两个变量x=3,y=5的值交换;（2）用流程图形来表示算法;起止框;算法的控制结构可分为顺序、选择、循环三种基本结构。;例 结构化程序设计的3种基本结构是(2005年4月考题) A）顺序、选择、重复 B）递归、嵌套、调用 C）过程、子过程、主程序 D）顺序、转移、调用;例3 输入两个数x,y;输出最大的数 ;例5 求1x2x3x4x5……n表达式的值(假设n=100) ;计算机解题的过程实际上是实施某种算法，称计算机算法。 （1）列举法 列举法是指根据提出的问题，列举所有可能的情况进行处理。 （2）归纳法 通过列举少量的特殊情况，经过分析，找出一般关系 （3）递推 从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果 （4）递归 将一个复杂的问题归结为若干个较简单的问题,直到最简单问题解决 （5）减半递推技术 就是对问题分而治之。 ;数据结构是一门研究非数值计算的程序设计问 题中计算机的操作对象以及它们之间的关系和 操作等等的学科。;4.4.2 基本概念和术语;数据结构是反映数据元素间关系的集合的表示;(1)集合—数据元素间除“同属于一个集合”外,无其它关系;(2)线性结构—该结构的数据元素之间存在着一个对一的关系,如线性表。;几种常用特殊的线性表;top=0;A)在栈中只能插入元素而不能删除元素 B)在栈中只能删除元素而不能插入元素 C)栈是特殊的线性表,只能在一端插入或删除元素 D)栈是特殊的线性表,只能在一端插入元素,而在另一端 删除元素;②对列:是指允许在一端进行插入、而在另一端进行删除的线性表。;队空;例1 栈和队列的共同点是（ ） A）都是先进先出 B）都是后进先出 C）只允许在端点处插入和删除元素 D）没有共同点;(3)树形结构(层次结构)——一个对多个;A;一、树基本术语;A;A;一、树基本术语;A;　二叉树;R;三、满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。 ;五、二叉树的遍历 遍历是指不重复地访问二叉树中所有结点。;ACBDFEHGP;3. 后中序遍历 首先后序遍历左子树，再右子树，最后访问根结点，并且在访问左子树和右子树时,仍然是先访问左子树，再访问右子树，最后是根。;(4)图状结构——多个对多个，如图;4.3.2 数据的存储结构;(1)顺序存储方法;顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充;线性表的插入是指在第i（1?i ? n+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表;删除元素;(2)链式存储方法;在链式存储方式中,要求每个结点由两部组成：一部分用于存放数据元素值称为数据区；另一部分用于存放指针称为指针域。;(1)在逻辑上相邻的元素在物理可以不相邻 (2)存储时不用事先准备,用时申请,这样会节约存储空间 (3)对增加,删除接点操作简单,不必移动结点,只要改结点中指针值 ; 105; 105;3.索引存储方法;A)一个逻辑数据结构只能有一种存储结构 B)数据的逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理的效率;1、顺序查找 ;4.3：查找技术;假设有5个数：９，８，６，４，３要排序。; 8 6 4 3 9;(2)快速排序方法