大学软件技术基础复习讲义

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

1、1.1数据结构的基本概念1.1.2数据结构中的基本概念和术语n数据(data)：u数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中、能被计算机程序识别和处理的符号的集合。n数据元素(dataelement)：u是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。n数据项（dataitem）u数据项是具有独立含义的最小标识单位。n数据对象(dataobject)u数据的子集。具有相同性质的数据成员（数据元素）的集合。n数据类型（datatype）：u是一个值的集合以及在这些值上定义的一组操作的总称。n结构（structu

2、re）：u数据元素相互之间的关系称为结构。u四类基本结构：n集合n线性结构n树形结构n图状结构或网状结构n数据结构(datastructure)：u相互之间存在着一种或多种特定关系的数据元素的集合。n数据结构包括以下三方面内容：u逻辑结构u存储结构u对数据的操作n逻辑结构：数据元素之间的逻辑关系u线性结构：有且只有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。有表、栈及队列。u非线性结构：一个数据元素可能有多个直接前趋和直接后继。有树与图。四种基本结构•集合结构数据元素间除“同属于一个集合”外，无其它关系•线性结构一个

3、对一个，如线性表、栈、队列•树形结构一个对多个，如树•图状结构多个对多个，如图n数据存储结构(物理结构)：数据元素在计算机中的存储方法。它是逻辑结构在存储器里的实现。n数据存储结构的四种基本存储方法：u顺序存储结构：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，数据元素间的逻辑关系由存储单元的邻接关系来体现。u链接存储结构：不要求逻辑上相邻的数据元素在物理位置上亦相邻，数据元素间的逻辑关系由附加的指针字段表示。亦称链式存储结构。u索引存储方法u散列存储方法n一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。n对数据的操作

4、即运算，运算涉及算法。n算法的定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。n算法的特性：u输入：有0个或多个输入。u输出：有一个或多个输出。u确定性：每步定义都是确切、无歧义的。u有穷性：算法应在执行有穷步后结束。u可行性：每一步骤都可有效执行，且执行有限步骤后能得到确定的结果。n算法分析：对算法的执行时间和所需内存空间的估算。可以比较不同算法的效率。u时间复杂度：执行一个算法所花费的时间代价。u空间复杂度：执行一个算法所占用的空间代价。n决定算法所花费时间的主要因素有：u问题的规模；所要处理的数据量的大小n。u编译所产生的

5、机器代码质量的优劣；u机器执行一条指令的时间长短；u程序中语句的执行次数。n通常只关注复杂性的数量级，即只要一个估计值。n通常考虑最坏情况下的时间代价，常采用大Ｏ表示法来描述。即用“O（数量级）”来表示，称为“阶”。n由小至大顺序排列的常见时间复杂度u常数阶O(1)、u对数阶O(log2n)、u线性阶O(n)、u线性对数阶O(nlog2n)、u平方阶O(n2)、u立方阶O(n3)、uk次方阶O(nk)、u指数阶O(2n)。l线性结构的基本特点是数据元素有序并且是有限的。l线性结构包括以下几种常见的类型：线性表、堆栈、队列。l线性表的长度：线性表中元素

6、的个数。l线性表的基本操作lInitiate(L){初始化}：设定一个空的线性表。lLength(L){求表长}：返回值为其数据元素的个数。lGet(L,i){取元素}：若数据元素序号i满足1≤i≤length(L)，则返回表L的第i个元素ai，否则返回空元素。lLocate(L，x){定位}：对给定值x，若表L中存在ai等于x，则返回索引号最小的i值，否则返回一个特殊值(比如-1），以说明不存在的位置。lInsert(L，i，x){插入}：对给定的表，若索引号i满足1≤i≤length(L)+1，则在第i个位置上插入一个新的元素x，表长+1，返回t

7、rue，否则返回false。lDelete(L，i){删除}：对给定的线性表，若索引号i满足1≤i≤length(L)，则把第i个元素ai删除，表长-1，返回true，否则返回false。l其他操作如：合并，排序等线性表的顺序存储结构--顺序表(SequentialList)n顺序表：用顺序存储方法存储的线性表。即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。顺序表的实现及基本运算#defineListSize100//表类型定义，空间大小根据实际需要而定,这里假设为100structSeqList{intdata[ListSize];

8、//向量data用于存放表结点intlength;//当前的表长度};//(1)表的初始化voidInitL