软件技术基础复习要点整理

《软件技术基础复习要点整理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件技术基础知识点整理孙浩顾丽萍数据结构概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。数据结构（DataStructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构通常包含以下三个方面的内容：数据的逻辑结构；数据的存储结构。形式定义：S=（D，R）D：一个数据元素的非空有限集合R：定义在D上的关系的有限集数据的运算及实现算法及特征算法的基本概念n数据的运算是通过算法实现的、解决某一特定问题的有限运算序列（解决问题的方法和步骤）。算法的定义和特征n算法的非形式化定义一个算法，就是一

2、个有穷规则的集合，其中的规则规定了一个解决某一特定类型问题的运算序列。n算法的非形式化定义一个算法，就是一个有穷规则的集合，其中的规则规定了一个解决某一特定类型问题的运算序列。算法的重要性质n有穷性（Finiteness）一个算法在执行有穷步之后必须结束。n确定性（Definiteness）算法的每一个步骤必须要有确切的定义。n输入（Input）算法有零个或多个输入。n输出（Output）算法有一个或多个的输出。n有效性（Effectiveness）算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地

3、进行的。在算法的分析中，一般应考虑以下3个问题：n1）算法的时间复杂度；n2）算法的空间复杂度；n3）算法是否便于阅读、修改和测试。线性结构顺序存储结构的特点：线性表中数据元素类型一致，只有数据域，存储空间利用率高。支持随机存取，做插入、删除时需移动大量元素。空间估计不明时，按最大空间分配。链表运算（1）头插法建立单链表从左边插入结点，此链表为不带头结点的单链表。每次生成的新结点，插入到表头。（2）尾插法建立单链表从右边插入结点，此链表为带头结点的单链表。每次生成的新结点，插入到表尾。顺序表和单链表的比较a.若线性表需

4、频繁查找却很少进行插入和删除操作，或其操作和元素在表中的位置密切相关时，宜采用顺序表作为存储结构；b.若线性表需频繁进行插入和删除操作时，则宜采用单链表做存储结构。c.当线性表中元素个数变化较大或者未知时，最好使用单链表实现；d.如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。栈和队列栈的定义栈(stack)是运算受限制的线性表，其元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(top)，另一端为固定的一端，称为栈底(bottom)。不含任何数据元素

5、的栈称为空栈。栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。链栈链栈结构及数据类型栈的链式存贮结构,也称为链栈，它是一种限制运算的链表，即规定链表中的插入和删除运算只能在链表开头进行栈的应用算术表达式的求值要实现表达式求值，必须设置两个栈，一个栈存放运算符，另一个栈存放操作数。编译程序从左到右扫描，先在OS中放入";"1.遇到操作数，一律进操作数栈NS；2.遇到运算符，与运算符栈OS的站顶元素相比较，•若优先级高于栈顶则进栈，•否则，在操作数栈NS中退出两个元素x，y（先退出的y在运算符右

6、，后退出的x在左），然后从OS中退出一个运算符θ，构成一条机器指令xθy，运算的结果存入NS栈中，•遇到"(",进栈;遇到")",一直退栈输出,直到退到"("止。•直到扫描完毕,这时，当前运算符为";",OS栈顶为";",NS中只有一个元素,即为运算结果.队列队列的定义队列也是一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表称为队列(queue)。允许插入的一端称为队尾(rear)，允许删除的一端称为队头（front）。队列是一种先进先出（FirstInFirstOut）的特殊线性表，或称F

7、IFO表。若队列中没有任何元素，则称为空队列，否则称为非空队列。数组下三角矩阵的压缩存储14/14软件技术基础知识点整理孙浩顾丽萍若将其中非0元素按行优先顺序存放，则顺序存储为：求取其中非0元素Aij的地址公式为：LOC(Aij)=LOC(A00)+i(i+1)/2+j(0≤j≤i

8、序存放。矩阵运算稀疏矩阵的转置运算树的逻辑结构特征是：树中任一结点都可以有零个或多个直接后继(孩子)结点，但至多只能有一个直接前趋(双亲)结点。树的基本术语：结点（Node）：树中的元素。结点的度（Degree）：结点拥有的子树数。叶子（Leaf）：度为零的结点，也称端结点。结点的层次：从根结点开始算起，根为第一层。深度（Dept