数据结构复习教程.doc

第 1 章 绪 论 数据结构基本概念 1. 数据： 在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 2. 数据元素： 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 构成数据元素的不可分割的最小单位称为数据项。 3. 数据对象： 是具有相同性质的数据元素的集合，是数据的子集。 4. 数据结构： 是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。 数据的逻辑结构。 存储结构要存储两方面的内容：⑴ 数据元素；⑵ 数据元素之间的逻辑关系。 根据数据元素之间逻辑关系的不同，数据结构分为四类： ⑴ 集合 ⑵ 线性结构 ⑶ 树结构 ⑷ 图结构 会画四种基本数据结构的逻辑结构图 数据的存储结构又称为物理结构 有两种存储结构 顺序存储结构的基本思想是：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系是由元素的存储位置来表示的。 链接存储结构的基本思想是：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系是用指针来表示的。 算法及算法分析 什么是算法 通俗地讲，算法是解决问题的方法； 严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列。 算法必须满足下列五个重要特性： ⑴ 输入： ⑵ 输出： ⑶ 有穷性： ⑷ 确定性： ⑸ 可行性： 算法的描述方法 常用的描述算法的方法 常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。 算法分析 1．度量算法效率的方法 一种方法是事后统计的方法，先将算法实现，然后输入适当的数据运行，测算其时间和空间开销。其缺点：⑴ 编写程序实现算法将花费较多的时间和精力；⑵ 所得实验结果依赖于计算机的软硬件等环境因素，有时容易掩盖算法本身的优劣。 另一种是事前分析估算的方法——渐进复杂度，它是对算法所消耗资源的一种估算方法。 2．算法的时间复杂度 问题规模 问题规模是指输入量的多少。运行算法所需要的时间T是问题规模n的函数。 基本语句是执行次数与整个算法的执行次数成正比的语句。 ??种衡量效率的方法得出的不是时间量，而是一种增长趋势的度量。即当只考察问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶，称作算法的渐进时间复杂度，简称时间复杂度，通常用大O（读作“大欧”）记号表示。 定义1-1 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))（或称算法在O(f(n))中）。 大O记号的含义: 3．最好、最坏和平均情况 4．算法的空间复杂度 算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量。辅助空间是除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间。通常记作：S(n)=O(f(n))，其中，n为问题规模，分析方法与算法的时间复杂度类似。 5. 算法分析举例 定理1-1 若A(n)=amnm +am-1nm-1 +…+a1n+a0是一个m次多项式，则A(n)=O(n m)。 第 2 章 线 性 表 线性表的定义 线性表的顺序存储结构及实现 设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为： LOC(ai)= LOC(a1)＋(i－1)×c 线性表的顺序存储结构——顺序表 顺序表的实现 建一个空的顺序表 顺序表插入算法。 顺序表删除算法。 顺序表查找算法 ⑴ 按位查找 ⑵ 按值查找 查找算法的时间复杂度。 线性表的链接存储结构及实现 线性表的链接存储结构——单链表 线性表的链接存储结构 单链表的实现 在单链表上按位查找 单链表的插入算法。 插入算法的时间复杂度。 单链表的构造：即生成一个有n个结点的单链表。有两种方法：头插法和尾插法。 ⑴ 头插法算法 ⑵ 尾插法算法 删除算法。 顺序表和单链表的比较 循环链表 双链表 双链表的性质 第 3 章 栈、队列 栈的定义 栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。 栈的顺序存储结构及实现 栈的顺序存储结构——顺序栈 栈的顺序存储结构称为顺序栈。 顺序栈的实现 顺序栈入栈算法Push 顺序栈出栈算法Pop 在栈i中插入元素x的算法 在栈i中删除栈顶元素的算法 栈的链接存储结构及实现 1. 栈的链接存储结构——链栈 链栈的示意图 链栈中是否需要头结点？为什么？ 2. 链栈的实现 链栈的插入算法 链栈的删除算法 顺序栈和链栈的比较 队列的定义， 队列的顺序存储结构及实现 1. 队列的顺序存储结构——循环队列 队列的假溢出及其解决 循环队列 2. 循环队列的实现 循环队列的入队算法， 循环队列的出队算法 队列的链接存储结构及