《 数 据 结 构 ( C语 言 版 ) 》 复 习 重 点重点在二、三、六、七、九、十章，考试内容两大类：概念，算法第 1 章、绪论1. 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3. 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。其4类基本结构：集合、线性结构、树形结构、图状结构或网状结构4. 逻辑结构：是数据元素之间的逻辑关系的描述。5. 物理结构（存储结构）：是数据结构在计算机中的表示（又称映像）。其4种存储结构：顺序存数结构、链式存数结构、索引存数结构、散列存数结构6. 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。其5个重要特性：有穷性、确定性、可行性、输入、输出7. 时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作，T(n)=O(f(n)) ；他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度。例如： (a) {++x;s=0;}(b) for(i=1;i<=n;++i){++x;s += x;}(c) for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s += x;}含基本操作“x增1”的语句的频度分别为1、n和n²，则这3个程序段的时间复杂度分别为O(1)、O(n)和O(n²)，分别称为常量阶、线性阶和平方阶。还可呈现对数阶O(log n)、指数阶O(2的n次方)等。8. 空间复杂度：算法所需存储空间的度量记作，S(n)=O(f(n))。第 2 章、线性表1. 线性表：是最常用最简单的一种数据结构，一个线性表是n个数据元素的有限序列。2. 线性表的顺序存储结构 ：是用一组地址连续的存储单元依次存储线性表的数据元素。其特点为逻辑关系上相邻的两个元素在物理位置上也相邻，可以随机存取表中任一元素。存储位置计算：假设线性表的每个元素需占用 L 个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，线性表的第i 个数据元素 ai 的存储位置为LOC(ai)=LOC(a1)+(i-1)*L 式中 LOC(a1)是线性表第一个元素 a1 的存储位置，通常称做线性表的起始位置或基地址。3. 线性表的链式存储结构：是用一组任意的存储单元存储线性表的数据元素 (这组存储单元可以是连续的，也可以是不连续的)。数据元素 ai 的存储映像称为结点，包括 2 个域...
