资源描述：
《公共基础知识讲义》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第一章数据结构与算法§1概述一、基本概念数据是对客观事物所进行的描述，这种描述是采用了计算机系统能够识别、存储和处理的形式来进行的。数据元素是数据的基本单位，即数据集合中的个体。（在不同的场合又称结点、记录等）数据项是数据的不可分割的最小单位。在数据结构学科中研究的对象是数据元素，而不讨论数据项间的构成和关系。数据对象是性质相同的数据元素的集合，即数据集合的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。抽象化地描述数据元素之间的相互关系称为数据的逻辑结构，它包含两方面的要素：一是数据元素的集合D，二是在D上的一组运算和相应的运算规则或简称为关系R。数据的逻辑结构在计算机存
2、储空间中的存放形式称为数据的物理结构（也称为存储结构），一般来说，一种数据结构的逻辑结构根据需要可以表示成多种存储结构。常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等形式。数据结构学科主要研究如下三个方面的内容：①数据的逻辑结构；②数据的存储结构；③对各种数据结构进行的运算，即算法的设计。二、算法算法是对特定问题求解步骤的描述，它是指令的有限序列。算法的基本特征：①有穷性；②确定性；③可行性；④0个或多个输入；⑤1个或多个输出。算法的基本要素：①对数据的运算和操作：基本运算和操作包括算术运算、逻辑运算、关系运算和数据传输；②算法的控制结构：基本的控制结构包括：顺序结构、选择结构、循环
3、结构。算法设计的基本方法：①列举法；②归纳法；③递推；④递归；⑤半递推技术；⑥回溯法。算法复杂度（性）主要包括时间复杂度和空间复杂度。所谓时间复杂度是指执行算法所需要的计算工作量。一般选取一个标准操作，找出随着问题规模n的变化，算法所执行标准操作的运算次数与其之间的函数关系f(n)，以f(n)的数量级O(n)来表示时间复杂度T(n)。常见的时间复杂度有：线性级O(n)，平方级O(n2)，对数级O(log2n)和指数级O(2n)等。分析某算法的时间复杂度时，有时还从最好情况、最坏情况、平均情况等方面进行全面比较。所谓空间复杂度是指执行算法所需要的存储空间的大小。一般也是问题规模的一个函数，取其数
4、量级表示为O(n)。通常分析算法所需辅助空间的最大情况。§2线性表一、线性结构与非线性结构线性结构满足：①有且仅有一个根结点；②每一个结点最多有一个直接前趋结点，也最多有一个直接后继结点；③在一个线性结构中插入或删除任何一个结点后，还是线性结构。线性结构元素之间是一对一的联系。典型的线性结构有线性表、栈、队列、字符串等。如果一个数据结构不是线性结构，则称之为非线性结构。典型的非线结构有树（一对多的联系）、图（多对多的联系）等。二、线性表线性表是由n（n>=0）个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个（首元素）外，有且只有一个前趋，除了最后一个（尾元素）外，有且仅有一个后继
5、。即线性表或是一个空表，或可表示为：（a1,a2,……,ai,……,an）其中ai是性质相同的数据元素，也称为线性表中的一个结点。线性表的长度，即表中的元素个数n，当n=0时称为空表。三、线性表的顺序存储结构（顺序表）线性表的顺序存储结构的基本特点：①线性表中所有元素所占的存储空间是连续的（一般用数组实现）；②线性表中每个元素在存储空间中是按逻辑顺序存放的，即用物理上的相邻关系来体现逻辑上的相邻关系。线性表的随机存取地址计算公式为：ADD(ai)=ADD(a1)+(i-1)*k这里ADD(ai)是第i元素的地址，k是每个元素占用空间字节数。线性表上的主要运算：①线性表的插入；②线性表的删除；③
6、线性表的查找；④线性表的排序；⑤线性表的分解；⑥线性表的合并；⑦线性表的复制；⑧线性表的逆转。四、线性表的插入运算在长度为n的线性表(a1,a2,…,ai,…,an)的第i元素ai之前插入一个新元素x后得到的长度为n+1的线性表为(a1,a2,…,x,ai,…,an)。实现方法：要在第i（1<=i<.n）元素之前插入一个新元素x，首先要从最后一个（即第n个）元素开始，直到第i元素之间的n-i+1个元素依次向后移动一个位置，移动结束后，在第i位置写入新元素x。插入结束后，表长度就增加了1。插入操作算法的时间复杂度分析：如果插入的位置在第n个元素之前，则只需将第n元素后移，这是最好情况；如果插入的
7、位置在第1个元素之前，则n个元素都要后移，这是最坏情况；在等概情况下（即在任何位置插入的机率相同）平均移动元素个数为n/2。五、线性表的删除运算在长度为n的线性表(a1,a2,…,ai,…,an)中删除第i元素ai后，变为长度为n-1的线性表(a1,a2,…,ai-1,ai+1…,an)。实现方法：要删除第i（1<=i<.n）元素，首先要从第i+1元素开始，直到最后一个（即第n个）元素之间的n-i
