数据结构知识点.doc

第一课第一课 绪论绪论 覆盖的知识点最小集：覆盖的知识点最小集： 1. 数据结构、数据元素、数据项、数据对象、数据的概念 2. 数据的逻辑结构和存储结构的概念 3. 算法设计时的注意事项 4. 时间复杂度的概念及度量方法 5. 空间复杂度的概念及度量方法知识点细化：知识点细化： 1-001 数据结构的基本概念数据结构的基本概念 数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学 科数据结构由数据的逻辑结构、存储结构和对数据的操作三部分组成 数据元素是数据的基本单位数据项是数据的不可分割的最小单位数据对象是性质相同的数据元 素的集合，是数据的子集数据是所有需输入计算机并为程序所处理的对象的总称1-002 数据的逻辑结构和存储结构，对后面的名词要能区分哪些是属于逻辑结构哪些属于物理结构数据的逻辑结构和存储结构，对后面的名词要能区分哪些是属于逻辑结构哪些属于物理结构 数据的逻辑结构指的是数据元素间的逻辑关系，分为集合、线性结构、树形结构和图形结构，或分 为线性结构和非线性结构 数据的物理结构指的是数据元素及其间逻辑关系在计算机中的表示，也称存储结构其中数据元素 间关系的表示有顺序映象（顺序存储结构）和非顺序映象（链式存储结构）两种方式，前者以存储地址 上的联系来体现数据元素之间的逻辑关系，后者则通过指针的指向来体现数据元素之间的逻辑关系。

1-003 算法设计时的注意事项算法设计时的注意事项 算法是对特定问题求解步骤的一种描述，是指令的有限序列算法的特性：有穷性、确定性、可行 性、零或多个输入、一或多个输出算法设计的要求：正确性、可读性、健壮性、高效性1-004 时间复杂度的概念及度量方法时间复杂度的概念及度量方法 算法的时间复杂度是算法执行效率的量度，记作：T(n)=O(f(n))，其中 n 为问题的规模 衡量算法效率时，通常在算法中选择一种不可再分解的基本操作（该操作的重复执行次数应与算法 的执行时间成正比） ，若该操作的执行次数为 f(n)，则记该算法的时间复杂度为 O(f(n)) 若基本操作的执行次数与输入数据有关，则可求算法的平均时间复杂度或最坏时间复杂度一般， 当所有可能的输入数据集及其出现概率均可知时，可求算法的平均时间复杂度，否则求最坏情况下的时 间复杂度1-005 空间复杂度的概念及度量方法空间复杂度的概念及度量方法 算法的空间复杂度是算法执行时所需存储空间的量度，记作：S(n)=O(f(n))，其中 n 为问题的规模 分析算法空间复杂度时，一般只考虑执行算法所需辅助空间，但若输入数据所占空间与算法本身有 关，则也应计算在内。

若执行算法所需辅助空间与输入数据有关，则可求最坏情况下的空间复杂度第二课第二课 线性表线性表 覆盖的知识点最小集：覆盖的知识点最小集： 1. 线性表的定义和基本操作 2. 线性表的实现 (1) 顺序存储 (2) 链式存储 (3) 线性表的应用知识点细化：知识点细化： 2-010 线性表基本概念线性表基本概念 线性表线性表是ｎ个数据元素构成的有限序列表长表长指线性表中数据元素的个数，表长≥０空表空表指表长 为０的线性表若线性表非空，则表中第一个元素没有直接前趋直接前趋，有且仅有一个直接后继直接后继；表中最后一 个元素没有直接后继，有且仅有一个直接前趋；其余每个数据元素有且仅有一个直接前趋，有且仅有一 个直接后继2-011 线性表的基本操作线性表的基本操作 (1)取元素 GetElem(L,i, //保存数据元素 int len; //线性表长度 }SqList; //顺序表类型名2-014 以一次性动态分配方法实现顺序表以一次性动态分配方法实现顺序表采用一次性的动态分配方法时，需定义最大可能长度，并需设变量记录线性表长 #define MAXSIZE 1000 //最大可能长度 typedef struct{ ElemType *elem; //保存首地址 int len; //线性表长度 }SqList; //顺序表类型名2-015 以带增量的动态分配方法实现顺序表以带增量的动态分配方法实现顺序表 采用带增量的动态分配方法时，需定义初始分配量和增量，并需分别设变量以记录线性表长及当前 分配总量。

#define LIST_INIT_SIZE 100 //初始分配量，以数据元素个数为单位 #define LISTINCREMENT 10 //增量 typedef struct{ ElemType *elem; //保存首地址 int len; //线性表长度 int listsize; //当前分配量，以数据元素个数为单位 }SqList; //顺序表类型名 在该结构上实现三个基本操作2-016 线性表的链式存储方式线性表的链式存储方式 用一组任意的（可连续可不连续）存储单元存储线性表中数据元素，用指针来表示数据元素间的逻 辑关系根据所用指针的类型、个数、方法等的不同，又可分为：线性链表（单链表） 、循环链表、双向 链表、双向循环链表、静态链表等2-017 线性链表（单链表）及其特点线性链表（单链表）及其特点 每个结点由两个域组成，其中数据域用以保存数据元素的值，指针域用以保存其直接后继结点的绝 对地址表中最后一个结点的指针域值为空指针 NULL在首元结点前还可附设头结点，以方便运算的 实现（无论表空与否，头指针值不变；插入时不必特别判断是否在第一个元素之前插入；删除时不必特 别判断是否删除第一个元素） 。

头结点的数据域一般不使用头结点（若表中不含头结点则为首元结点） 的地址保存在头指针中 typedef struct LNode{ ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 在该结构上实现三个基本操作 在单链表中访问结点时，必须从头指针开始顺序查找该结点，指针的移动是其中的基本操作，查找 第 i 个结点时需移动 i-1 次设查找任一元素的概率相等，则需移动指针的平均次数为(n-1)/2，算法时间 复杂度为 O(n) 在单链表中插入结点时，时间主要用于查找插入位置，即查找第 i-1 个结点上算法的时间复杂度为 O(n) 在单链表中删除结点时，时间主要用于查找待删结点算法的时间复杂度为 O(n)2-018 循环链表及其特点循环链表及其特点 循环链表的结点结构同单链表，但表中最后一个结点的指针域保存头结点（若表中不含头结点则为 首元结点）的绝对地址在循环链表中，从任一结点出发均可访问到表中其余结点 循环链表上基本操作的实现与单链表基本相同，主要区别在于算法中的循环条件2-019 双向链表及其特点双向链表及其特点双向链表中每个结点由一个数据域和两个指针域组成，其中数据域用以保存数据元素的值，一个指 针域用以保存其直接后继结点的绝对地址，另一个指针域用以保存其直接前趋结点的绝对地址。

双向链表上基本操作的实现与单链表基本相同，主要区别在于需同时考虑两个方向上的指针 typedef struct DuLNode{ ElemType data; //数据域 struct DuLNode *prior; //指向直接前驱的指针域 struct DuLNode * next; //指向直接后继的指针域 }DuLNode,*DuLinkList;2-020 双向循环链表及其特点双向循环链表及其特点 双向循环链表的结点结构同双向链表，但表中最后一个结点的 next 指针域保存头结点（若表中不含 头结点则为首元结点）的绝对地址，头结点（若表中不含头结点则为首元结点）的 prior 指针域保存表中 最后一个结点的绝对地址 双向循环链表上基本操作的实现与双向链表基本相同，主要区别在于算法中的循环条件2-021 静态链表及其特点静态链表及其特点 静态链表的结点保存在一段连续的存储空间中，每个结点由两个域组成，其中数据域用以保存数据 元素的值，指针域保存其直接后继结点的相对地址相对地址为０的结点用作头结点，其指针域存放首 元结点的相对地址表中最后一个结点的指针域值为０ #define MAXSIZE 1000 //链表的最大长度 typedef struct { ElemType data; //数据域 int next; //指针域 }SLNode,SLinkList[MAXSIZE];2-022 线性表的顺序存储与链式存储的优缺点比较，及各自适用场合线性表的顺序存储与链式存储的优缺点比较，及各自适用场合 若线性表采用顺序存储，则：可随机存取表中数据元素；存储密度大；但：插入、删除时需大量移 动元素（在最后一个元素的后面插入新元素、删除最后一个元素时不需移动元素） ；需预先估计所需存储 空间，可能使存储空间不能得到充分利用，且表的最大长度受此限。

适用于元素总数有上限、仅在表尾 进行插入删除的应用 若线性表采用链式存储，则：插入、删除时不需移动元素（在第 i 个结点之前插入或删除第 i 个结点 时，均需移动辅助指针，使其指向第 i-1 个结点） ；不需预估预分配存储空间，而是在插入时按需分配， 在删除时及时释放（但这也导致运行效率降低） ；表的最大长度只受内存容量的限制；但：对表中数据元 素的存取为顺序存取；需占用额外的存储空间来保存元素间关系适用于元素总数上限难确定，插入、 删除操作频繁的应用2-023 静态链表与顺序表的相似及不同之处静态链表与顺序表的相似及不同之处 相似：都占用一段连续的存储空间；这段空间的分配可用静态分配方法，也可用动态分配方法建 表时都要要估算最大容量，插入元素前都要先判断是否有空余空间 不同：顺序表通过数据元素物理地址上的相邻来体现元素间的逻辑关系，属于一种顺序存储结构； 静态链表借助指针的指向来体现元素间的逻辑关系，属于一个链式存储结构顺序表中元素是随机存取， 静态链表中元素是顺序存取顺序表中执行插入、删除操作要移动元素，静态链表中不要2-024 线性表的应用线性表的应用 基于线性表的各种存储方式实现指定的操作，尤其是各种链表（带头结点、不带头结点） （仅设头指 针、仅设尾指针、分设头尾指针）上插入插入（当前结点之前，当前结点之后，头结点之后，尾结点之后， 其它位置） ，删除删除（当前结点、前趋结点、后继结点、首元结点、其它结点） ，分解分解（一表到多表） ，归并归并 （多表合一表） ，查找查找（顺序表上的顺序和折半查找，链表上的顺序查找） 、排序排序（各种排序方法的实现）等。

第三课第三课 栈、队列和数组栈、队列和数组 覆盖的知识点最小集：覆盖的知识点最小集： 1. 栈和队列的基本概念 2. 栈和队列的顺序存储结构 3. 栈和队列的链式存储结构 4. 栈和队列的应用 5. 特殊矩阵的压缩存储知识点细化：知识点细化： 3-001 栈的基本概念栈的基本概念 栈栈是限定仅在表尾端进行插入、删除的线性表；表尾端称栈顶栈顶，an称栈顶元素；表头端称栈底栈底，a1称 栈底元素栈的长度长度即栈中元素个数长度为 0 的栈称空栈空栈向栈中插入元素称入栈入栈，从栈中删除元素 称出栈出栈栈的修改是按后进先出的原则进行的3-002 栈的顺序存储方式栈的顺序存储方式 与线性表的顺序存储方式类似：三种分配方法；线性表长度分量→栈顶指针分量（指向栈顶元素的 下一个位置） 以顺序存储方式保存的栈称顺序栈 设采用静态分配实现入栈和出栈操作 #define MAXSIZE 1000 //栈的最大容量 typedef struct{ElemType elem[MAXSIZE]; //保存数据元素，以低地址为栈底int top; //栈顶指针 }SqStack;3-003 栈的链式存储方式栈的链式存储方式 与单链表类似：带/不带头结点；插入、删除操作点（即栈顶端）放在靠近头指针的一端。

以链式存 储方式保存的栈称链栈 实现入栈和出。