计算机软件基础知识讲解

《计算机软件基础知识讲解》由会员分享，可在线阅读，更多相关《计算机软件基础知识讲解（50页珍藏版）》请在金锄头文库上搜索。

1、1 计算机软件基础知识 软件基础 算法 v算法的基本概念 算法：是一组有穷指令集，是解题方案的准 确而完整的描述。通俗地说，算法就是计算机解 题的过程。算法不等于程序，也不等于计算方法 ，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的 规则，每一个规则都是有效的，是明确的，此顺序将在有限 的次数下终止。算法不等于程序，程序不可能优于算法。 基本特性 可行性：根据实际问题设计的算法，执行得 到满意结果 确定性：每一步骤必须有明确定义，不允许 有多义性。 有穷性：算法必须能在有限的时间内做完。 输入和输出：拥有足够的情报，方可执行。 算法的基本要素 1.对数据对象的运

2、算和操作 算术运算：、等 逻辑运算：、=、=、!=等 关系运算：and、or、not等 数据传输：w、r等 2.算法的控制结构 算法中各操作之间的执行顺序 描述算法的工具通常有传统流程图、 N-S结构化流程图、算法描述语言等 算法可以用顺序、选择、循环三种基 本机构组合而成。 算法基本设计方法 （1）列举法：根据问题，列举所有可能的情况 ，并用问题中给定的条件检验哪些是需要的，哪些是 不需要的。 （2）归纳法：通过列举少量的特殊情况，经过 分析，最后找出一般的关系。 （3）递推：是指从已知的初始条件出发，逐次 推出所要求的各中间结果和最后结果。 （4）递归：将问题逐层分解的过程。 （5）减半递

3、推技术： “减半”，是指将问题 规模减半，而问题性质不变； “递推”，是指重复“ 减半”过程。 （6）回溯法：分析问题，找出一个解决总线索 ，然后沿着这个线索逐步试探。 算法效率度量算法的复杂度 v算法的复杂度：时间复杂度、空间复杂度 算法的时间复杂度 算法时间复杂度是指执行算法所需要的计算 工作量。 工作量用算法所执行的基本运算次数来度量 ，而算法所执行的基本运算次数是问题规模的函数，即 算法的工作量=f(n) 算法空间复杂度 算法空间复杂度是指执行这个算法所需要的 内存空间。 存储空间包括：算法程序所占的空间、 输入数据所占的空间、算法执行过程中所需要的额外 空间 数据结构基本概念 能输入

4、到计算机中 并能被计算机程序处理的 符号的集合。 整数(1,2)、实数(1.1,1.2) 字符串(Beijing)、 图形、声音。 数据结构是一门研究数据组织、存储和运 算的一般方法的学科。 数据结构基本概念 计算机管理图书问题计算机管理图书问题 图书馆里有各种卡片：有按书名编排的、有按作 者编排的、有按分类编排。 如何将查询图书的这些信息存入计算机中既要考 虑查询时间短，又要考虑节省空间 数据结构是一门研究数据组织、 存储和运算的一般方法的学科。 数据结构基本概念 最简单的办法之一是建立一张表，每一本书的信 息在表中占一行，如 数据结构是一门研究数据组织、 存储和运算的一般方法的学科。 数据

5、结构基本概念 如何将0,1,2,3,4,5,6,7,8,9这10个数存放在 计算机中能最快地达到你所需要的目的？ 目的不同，最佳的存储方方法就不同。 从大到小排列：9,8,7,6,5,4,3,2,1,0 输出偶数：0,2,4,6,8,1,3,5,7,9 数据元素在 计算机中的表示 数据结构是一门研究数据组织、 存储和运算的一般方法的学科。 数据结构基本概念 对数据结构中的节点进行操作处理 (插入、删除、修改、查找、排序) 数据结构是一门研究数据组织、 存储和运算的一般方法的学科。 数据结构研究的主要内容 v 数据结构主要研究以下三个方面的问题： 数据的逻辑结构：数据集合中各元素的信息 ，及元素

6、之间所固有的逻辑关系（前后件关系） 数据的存储结构：各数据元素在计算机中的 存储关系 对各种数据结构进行的运算 主要目的是为了提高数据的效率。所谓提高数据处理的效 率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在 数据处理过程中所占用的计算机存储空间。 数据结构类型 1数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A线性结构 B非线性结构 A 顺序存储 B 链式存储 线性表 栈 队 树形结构 图形结构 数据结构的三个方 面 线性结构和非线性结构 线性结构条件线性结构条件 n（1）有且只有一个根结点； n（2）每一个结点最多有一个前件，也最多有

7、一个后件。 n（3）首节点无前件，尾节点无后件。 非线性结构：非线性结构：不满足线性结构条件的数据结构 注意：在一个线性结构中插入或删除任何一个节点后还应是线性结构；否 则，不能称为线性结构。 学学 生生 成成 绩绩 表表 86胡孝臣9861103 95刘忠赏9861107 100张卓9861109 成绩姓名学号 树形结构 全校学生档案管理的树形结构的组织方式全校学生档案管理的树形结构的组织方式 非线性 结构 树形结构树形结构 树形结构 A BC D EFGH 树形结构树形结构 结点间具有分层次的连接关系结点间具有分层次的连接关系 H BCD EFG A 图形结构 图形结构：节点间的连接任意图

8、形结构：节点间的连接任意 14 23 D= 1 , 2 , 3 , 4 R=(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) 无向图 2 1 3 D= 1 , 2 , 3 R= (1,2) , (2,3) , (3,2) , (1,3) 有向图 顺序存储与链式存储 Lo+（n-1)*m 元素n . 元素i . 元素2 元素1 Lo Lo+m Lo+(i-1)*m 存储地址存储内容 Loc(a)=Lo+（i-1)*m 每个元 素所占 用的存 储单元 个数 顺序存储顺序存储 常用于线性数据结构， 将逻辑上相邻的数据元 素存储在物理上相邻的 存储单元里。 三个弱

9、点三个弱点 插入或删除操作时，需 移动大量元数。 长度变化较大时，需按 最大空间分配。 表的容量难以扩充 顺序存储与链式存储 134 6 元素3 1536 . . . 153 6 元素2 1400 . . . 元素4 1346 140 0 元素1 1345 指 针 存储内 容 存储地 址 15 36 元 素2 14 00 元 素1 13 46 元 素3 元 素4 head 13 45 链式链式 存储存储 的地的地 址映址映 射表射表 栈和队列 栈和队列是两种运算时要受到某些特殊限制的线 性表，故也称为限定性的数据结构。 栈：限定只能在表的一端进行插入和删除的特殊的线性表,此 种结构称为后进先出

10、。 n设栈s=（a1，a2，,ai，an） n其中a1是栈底元素， an是栈顶元素。 n栈顶（top)：允许插入和删除的一端； n约定top始终指向新数据元素将存放的位置。 n栈底（bottom):不允许插入和删除的一端。 a1 a2 . an 进栈出栈 栈顶 栈底 栈和队列 队列的主要运算 n设置一个空队列； n插入一个新的队尾（rear）元素，称为进队 ； n删除队头（front）元素，称为出队； n读取队头元素； a1 , a2 , a3 , a4 , an-1 , an 队头 队尾 队列：限定只能在表的一端进行插入，在表的另一端进行删除的线性表。 此种结构称为先进先出（FIFO）表。

11、栈和队列 3 2 1 0 (a) rear=front=0(队空） e3 e4 (c) (c) e1,e2出队，e4入队 rear =4 front e1 e2 e3 (b) rear front (b)e1,e2,e3入队 队列的主要运算 n队空时，令rear=front=0; 元素个数rear- front n当有新元素入队时，尾指针加1，当有元素出 队时，头指针加1。故在非空队列中，头指针始终指 向队头元素前一个位置，而尾指针始终指向队尾元素 的位置 栈和队列 计算循环队列长度： front=rear，队列长度0； frontrear，队列长度rear+size -front a1 ,

12、a2 , a3 , a4 , an-1 , an 队头 队尾 循环队列：首尾相接的队列，逻辑上形成一个环状。 树与二叉树 树的定义：由一个或多个结点组成的有限集合。仅有一个根 结点，结点间有明显的层次结构关系。 A C G T2 D H I T3 J M B E L K T1 F 现实世界中，能用树的结构表示：学校的行政关 系、书的层次结构、人类的家族血缘关系等。 树与二叉树 树的基本概念：树的基本概念： 结点（Node）：树中的元素 结点的度（Degree）：结点拥有的子树数。 结点的层次：从根结点开始算起，根为第一层。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点

13、子树的根称为该结点的孩子结点。 兄弟（Sibling）：同一双亲的孩子。 双亲（Parent）：孩子结点的上层结点，称为其的双亲。 深度（Depth)： 树中结点的最大层次数。 森林（Forest）：M棵互不相交的树的集合。 A C G T2 D H I T3 J M B E L K T1 F 树与二叉树 二叉树（Binary Tree）的定义 二叉树的五种基本形态 二叉树一种特殊的树型结构，特点是树中每个结点只有两棵 子树，且子树有左右之分，次序不能颠倒。 空二叉树 仅有 根结点 右子树 为空 左子树 为空 左右子树 均非空 因为树的每个结点的度不同，存储困难，使对树的处理算法 很复杂。所以

14、引出二叉树的理论。 满二叉树 4 23 1 6 7 89 101112131415 5 特点：所有分支结点都存在左右子树，且所有叶 子结点都在同一层上。 完全二叉树 4 23 1 67 89 10 1112 5 非完全二叉树 4 23 1 67 89 10 1112 5 完全二叉树 特点：除最后一层外，每一层都取最大结点数， 最后一层结点都集中在该层最左边的若干位置。 二叉树的基本性质 A、二叉树的第i层上至多有2i-1（i 1）个结点。 B、深度为h的二叉树中至多含有2h-1个结点。 C、若在任意一棵二叉树中，有n0个叶子结点（度为0），有 n2个度为2的结点，则：n0=n2+1 D、具有n个结点的完全二叉树的深度为log2n+1，其中 log2n表示log2n 的整数部分。 4 23 1 6 7 89 101112131415 5 第三层 (i=3)，有23-1=4个节点 深度h=4，共有24-1=15个节点 n0=8,n2=7,n0=n2+1 15个节点，深度=log215+1=4 二叉树的遍历 遍历是指按某条搜索路线寻访树中每个结点，且每个 结点只被访问一次。 按先左后右的原则，一般使用三种遍历：按先左后右的原则，一般使用三种遍历： 先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(