数据结构导论知识点

数据结构导论知识点数据结构导论知识点 第一章第一章 概论概论 数据结构 是相互之间存在一种或多种关系的数据元素的集合 和该集合中数据元素 之间的关系组成 数据结构包括数据的逻辑结构 数据的存储结构和数据的基本运算 简单地说 数据结构是计算机组织数据和存储数据的方式 更进一步地说 数据结构 是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方 式 以及定义在该组数据上的操作 合理的数据结构可降低程序设计的复杂性 提高程序 执行的效率 1 11 1 引言引言 计算机解决一个具体问题时 一般需要经过以下几个步骤 从具体的问题抽象出一个适当的数学模型 设计一个求解该数学模型的算法 用某种计算机语言编写实现该算法的程序 调试和运行程序直至最终得到问题的解 答 数据的逻辑结构 数据和数据的组织方式称为数据的逻辑结构 为了能用计算机加工 处理 逻辑结构还必须转换为能被计算机存储的存储结构 1976 年瑞士计算机科学家尼克劳斯 维尔特提出公式 算法 数据结构 程序 该公式 简洁的描述了数据结构和程序之间关系 1 21 2 基本概念和术语基本概念和术语 1 2 11 2 1 数据 数据元素和数据项数据 数据元素和数据项 数据 所有被计算机存储 处理的对象 数据元素 简称元素 又称为结点 数据的基本单位 在程序中作为一个整体而加以 考虑和处理 数据元素是运算的基本单位 通常具有完整确定的实际意义 数据元素由数 据项组成 数据项 在数据库中数据项又称为字段或域 是数据的不可分割的最小标识单位 组 成数据元素 关系 数据 数据元素和数据项实际上反映了数据组织的三个层次 数据可由若干个 数据元素组成 而数据元素又可由若干个数据项组成 表格 逻辑结构 行 记录 数据元素 列 数据项 1 2 21 2 2 数据的逻辑结构数据的逻辑结构 数据的逻辑结构 是指数据元素之间的逻辑关系 逻辑关系 是指数据元素之间的关联方式或邻接关系 逻辑结构示意图中的小圆圈称为结点 一个结点代表一个数据元素 记录 根据数据元素之间关系的不同特性 通常有集合 线性结构 树形结构和图结构四类 基本逻辑结构 反映了四类基本的数据组织形式 四类基本逻辑结构 集合 集合中任何两个结点之间都没有邻接关系 组织形式松散 线性结构 线性结构中结点按逻辑关系依次排列形成一条 链 结点之间一个一个 依次相邻接 树形结构 树形结构具有分支 层次特性 其形态有点像自然界中的树 上层的结 点可以和下层多个结点相邻接 但下层结点只能和上层的一个结点相邻接 图结构 图结构最复杂 任何两个结点都可以邻接 数据的逻辑结构与存储无关 独立与计算机 1 2 31 2 3 数据的存储结构数据的存储结构 数据的逻辑结构在计算机中的实现称为数据的存储结构 或物理结构 一个存储结构包括两个部分 存储数据元素 数据元素之间的关联方式 表示数据元素之间的关联方式主要有 顺序存储方式 是指所有存储结点存放在一个连续的存储区里 利用结点在存储器 中的相对位置来表示数据元素之间的逻辑关系 使用数组 内存地址连续 链式存储方式 是指每个存储结点除了含有一个数据元素外 还包含指针 每个指 针指向一个与本结点有逻辑关系的结点 用指针表示数据元素之间的逻辑关系 索引存储方式 散列存储方式 一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系 相应的 存储结构称为给定逻辑结构的存储实现或存储现象 1 2 41 2 4 运算运算 运算是指在某种逻辑结构上施加的操作 即对逻辑结构的加工 在每个逻辑结构上 都定义了一组基本运算 包括 建立 查找 读取 插入和删除 等 线性表 栈和队列中的元素具有相同的逻辑结构 即线性结构 但有不同的运算集 是不同的数据结构 1 31 3 算法及描述算法及描述 运算的实现是指该运算的算法 算法是计算机科学的一个基本概念 也是程序设计的 一个基本概念 一个算法规定了求解给定问题所需的处理步骤及其执行顺序 使给定问题 在有限的时间内被求解 算法可以用某种语言描述 1 41 4 算法分析算法分析 评价算法好坏的因素包括 正确性 能正确的实现预定的功能 满足具体问题的需要 易读性 易于阅读 理解和交流 便于调试 修改和扩充 健壮性 即使输入非法数据 算法也能适当的做出反应或进行处理 不会产生预料 不到的运行结果 时空性 一个算法的时空性是指该算法的时间性能 或时间效率 和空间性能 或 时间效率 前者是算法包含的计算量 后者是算法需要的存储量 1 4 11 4 1 时间复杂度时间复杂度 估算算法的计算量 可将基本操作次数作为该算法的时间度量 执行次数最多的语句 的执行次数 假如问题的输入规模为 n 一般情况下 一个算法的计算量是问题规模 n 的函数 一 个算法的时间复杂度是算法输入规模的函数 常见算法时间复杂度的阶数有常数 O 1 最优的时间复杂度 与输入规模 n 无关 对数阶 O log2n 线性阶 O n 多项式阶 平方阶 O nC 和指数阶 O Cn C 为大于 1 的 正整数 通常认为 时间复杂度具有指数阶的算法是实际不可计算的 而阶数低于平方阶 的算法是高效的 O 1 O log2n O n O nC O Cn 最坏时间复杂度 对相同输入数据量的不同输入数据 算法时间用量的最大值 平均时间复杂度 对所有相同输入数据量的各种不同输入数据 算法事件用量的平均 值 1 4 21 4 2 空间复杂度空间复杂度 一个算法的空间复杂度定义为该算法所耗费的存储空间 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 一个算法在执行期间所需要的存储空间量包括 程序代码所占用的空间 输入数据所占用的空间 辅助变量所占用的空间 在估算法算法空间复杂度时 一般只需要分析辅助变量所占用的空间 第二章第二章 线性表线性表 2 12 1 线性表的基本概念线性表的基本概念 线性表 Linear List 是一种线性结构 是由 n n 0 个数据元素组成的有穷数列 数据元素又称为结点 结点个数 n 称为表长 a1称为起始结点 an称为终端结点 ai称为 ai 1的直接前驱 ai 1称为 ai的直接后继 线性表的基本特征 线性表中结点具有一对一的关系 如果结点数不为零 则除起始 结点没有直接前驱 除终端结点没有直接后继 其他每个结点有且仅有一个直接前驱 一 个直接后继 线性表的基本运算及功能描述 初始化 Initiate L 建立一个空表 L L 不含数据元素 求表长 Length L 返回线性表 L 的长度 读表元素 Get L i 返回线性表第 i 个数据元素 当 i 不满足 1 i Length L 时 返回一特殊值 定位 Locate L x 查找线性表中数据元素值等于 x 的结点序号 若有多个数据元 素值与 x 相等 运算结果为这些结点中序号的最小值 若找不到该结点 则运算结果为 0 插入 Insert L x i 在线性表 L 的第 i 个数据元素之前插入一个值为 x 的新数据 元素 参数 i 的取值范围是 1 i n 1 插入后线性表 L 表长度加 1 删除 Delete L i 删除线性表 L 的第 i 个数据元素 ai i 的有效取值范围是 1 i n 删除后线性表 L 表长度减 1 2 22 2 线性表的顺序存储线性表的顺序存储 顺序表是最简单的一个存储方式 2 2 12 2 1 线性表顺序存储的类型定义线性表顺序存储的类型定义 线性表顺序存储的方法是 将表中的结点依次存放在计算机内存中一组连续的存储单 元中 数据元素在线性表中的邻接关系决定它们在存储空间中的存储位置 即逻辑结构中 相邻的结点其存储位置也相邻 用顺序存储实现的线性表称为顺序表 一般使用数组来表 示顺序表 假定线性表的数据结构的类型是 DataType 顺序表的结构定义 学生档案信息表的顺 序存储实现 const int Maxsize 7 预先定义一个足够大的常量 作为数组的最大长度 typedef struct 定义一个结构体类型 int num 学号 char name 8 姓名 char sex 2 性别 int age 年龄 int score 入学成绩 DataType 定义结点类型 typedef struct DataType data Maxsize 存放数据的数组 int length 顺序表的实际长度 SeqList 顺序表类型名为 SeqList SeqList student 定义 student 为一个顺序表 2 2 22 2 2 线性表的基本运算在顺序表上的实现 插入 删除 定位的最优 最坏 平均时间线性表的基本运算在顺序表上的实现 插入 删除 定位的最优 最坏 平均时间 复杂度都是复杂度都是 O n O n 1 1 插入插入 顺序表的插入运算 InsertSeqlist SeqList L DataType x int i 是指在顺序表的 第 i 1 i n 1 个元素之前 插入一个新元素 x 使长度为 n 的线性表变为 n 1 的线性 表 插入算法的具体步骤 首先将结点 ai an依次向后移动一个元素的位置 空出第 i 个 数据元素的位置 然后将 x 置入该该空位 表长加 1 插入算法描述 void InserSeqlist SeqList L DataType x int i 将元素 x 插入到顺序表 L 的第 i 个数据元素之前 if L length Maxsize exit 表已满 if iL length 1 exit 位置错 检查插入位置是否合法 for j L length j i j 初始 i L length L data j L data j 1 依次后移 L data i 1 x 元素 x 置入到下标为 i 1 的位置 L length 表长度加 1 顺序表中结点的物理顺序和线性表中结点的逻辑顺序保持一致 顺序表插入算法的元素比较和移动的次数是 n i 1 次 平均移动次数是 n 2 时间 复杂度为 O n 2 2 删除删除 删除运算 DeleteSeqlist SeqList L int i 是指将线性表的第 i 1 i n 个数据 元素删去 使长度为 n 的线性表变为 n 1 的线性表 当 i n 时 直接将表长度减 1 即可 删除算法的基本步骤是 结点 ai an依次向左移动一个元素位置 覆盖掉被删结点 ai 表长度减 1 不考虑溢出 只判断参数 i 是否合法 删除算法描述 void DeleteSeqlist SeqList L int i 删除顺序表 L 中的第 i 个数据结点 if iL length 1 exit 非法位置 检查插入位置是否合法 for j i jL length 1 L data i x 在顺序表中查找值为 x 的结点 i if jnext NULL return head 在算法中 变量 head 是链表的头指针 指向新创建的结点 即头结点 一个空单链表 仅有一个头指针 它的指针域为 NULL 求表长求表长 在单链表存储结构中 线性表的表长等于单链表中数据元素的结点个数 即除了头结 点以外的结点的个数 单链表的求表长描述 通过结点的指针域来从头至尾访问每一个结点 int LengthLinklist LinkList head 求单链表表 head 的长度 Node p head p 是工作指针 初始时 p 指向头结点 int cnt 0 计数器置初值 while p next NULL p p next 指针移动到下一个结点 cnt return cnt 返回表长 读表元素读表元素 给定一个序列号 i 查找线性表的第 i 个元素 单链表的读表元素描述 从头指针出发 一直往后移动 直到第 i 个结点 Node GetLinklist LinkList head int i 在单链表 head 中查找第 i 个元素结点 找到返回指向该结点的指针 否则返回 NULL Node p p 是工作指针 p head next 初始时 p 指向首结点 int c 1 while cnext c if i c return p 找到第 i 个结点 else return NULL in i 值不合法 查找失败 注意 p NULL 在这里作为判断是否以遍历整个链表的条件 不可遗漏 定位定位 定位运算又称为安值查找 线性表的定位运算 是对给定表元素的值 找出这个元素 的值 在单链表实现中 则是给定一个结点的值 找出这个结点是单链表的第几个结点 单链表的定位运算描述 从头至尾访问链表 直至找到需要的结点 返回其序列号 若未找到 返回 0 int LocateLinklist LinkList head DataType x 求单链表表 head 中第一个值等于 x 的结点的序号 若不存在这种结点 返回结果 0 Node p head p 是工作指针 p p next 初始时 p 指向头结点 int i 0 i 代表结点的序号 这里置初值为 0 while p NULL p data x 访问链表 i p p next if p NULL return i 1 else return 0 插入插入 单链表的插入运算是将值为 x 的元素插入到链表 head 的第 i 个结点之前 单链表的插入运算描述 先找到链表的第 i 1 个结点 q 生成一个值为 x 的新结点 p p 的指针域指向 q 的直接后继结点 q 的指针域指向 p void InserLinklist LinkList head DataType x int i 在单链表 head 的第 i 个数据元素结点之前插入一个值为 x 的新结点 Node p q if i 1 q head else q GetLinklist head i 1 找第 i 1 个数据元素结点 if q NULL 第 i 1 的结点不存在 exit 找不到插入的位置 else p malloc sizeof Node p data x 生成新结点 p next q next 新结点链域指向 q 的后继结点 q next p 修改 q 的链域 单链表的插入运算操作 p next q next 和 q next p 语句执行顺序不能颠倒 删除删除 单链表的删除运算是给定一个值 i 将链表中第 i 个结点从链表中移除 并修改相关 结点的指针域 以维持剩余结点的链接关系 单链表的删除运算描述 将 ai结点移除后 需要修改该结点的直接前驱结点 ai 1的指 针域 使其指向移除结点 ai的直接后继结点 ai 1 void DeleteLinklist LinkList head int i 在单链表 head 中删除第 i 个数据结点 Node q if i 1 q head else q GetLinklist head i 1 先找待删除结点的直接前驱 if q NULL q next NULL 若直接前驱存在且待删除结点存在 p q next p 指向待删除结点 q next p next 移出待删除结点 free p 释放以移出结点 p 的空间 else exit 找不到要删除的结点 结点不存在 free p 是必不可少的 当一个结点从链表中移出后 若不释放它的空间 它将变成一 个无用的结点 并一直占用着系统内存空间 其他程序将无法使用这块空间 2 42 4 其他运算在单链表上的实现其他运算在单链表上的实现 2 4 12 4 1 建表建表 根据线性表元素的邻接关系 建立该线性表的单链表 建立含头结点的单链表 首先建立带头节点的空表 其次建立一个新结点 然后将新结点链接到头结点之后 这个结点为尾结点 首结 点 最后重复建立新结点和将新结点链接到表尾这两个步骤 直到线性表中所有元素链 接到单链表中 1 1 建立单链表方法一 建立单链表方法一 通过已实现的初始化和插入算法来实现 依次增大插入位置 i 使新的结点链入到链表中 每次插入都从表头开始查找 比较浪费时间 算法 InserLinklist 主要部分是找到第 i 个位置 然后将新结点插入 计算量约等于 i 线性表有 n 个元素 插入位从 1 到 n 方法一算法的计算量约为 n n 1 2 时间复杂 度为 O n2 LinkList CreatLinkList1 通过调用初始化和插入算法实现建表算法 假定 0 是输入结束标志 LinkList head int x i head InitiateLinkList 建立空表 i 1 置插入位置初值 scanf d x 读入第一个数据元素 x 为整型 while x 0 输入的不是结束标志时继续插入 InserLinklist head x i 将输入插入到 head 表尾 i 修改插入位置 scanf d x 读下一个元素 return head 2 2 建立单链表方法二 建立单链表方法二 每次把新结点链接到链尾 用一个指针指向尾结点 为下一个 新结点指明了插入位置 时间与元素个数成正比 时间复杂度为 O n 用方法二建立的链表 数据顺序与输入顺序相同 LinkList CreatLinkList2 q 是一个 LinkList 类型的变量 用来指示链入的位置 LinkList head Node q t int x head malloc sizeof Node 生成头结点 q head 尾指针置初值 scanf d x 读入第一个数据元素 x 为整型 while x 0 输入的不是结束标志时继续链入 t malloc sizeof Node t data x 生成一个新结点 q next t 新结点链入 q t 修改尾指针 q 指向新结点 scanf d x 读下一个元素 q next NULL return head 3 3 建立单链表方法三 建立单链表方法三 将新增加的结点插入到头结点之后 第一个数据结点之前 称 为前插操作 时间复杂度为 O n 用方法三建立的链表 数据顺序与输入顺序相反 LinkList CreatLinkList3 LinkList head Node p int x head malloc sizeof Node 生成头结点 head next NULL scanf d x while x x 0 时结束输入 p malloc sizeof Node p data x p next head next 前插 插入到链表的第一个结点处 head next p scanf d x return head 2 4 22 4 2 删除重复节点删除重复节点 设计算法删除重复结点 只保留结点序号最小的那个结点 用链表作为存储结构 算法描述 void PurgeLinkList LinkList head 删除表 head 中多余的重复结点 Node p q r q head next q 指示当前检查结点的位置 置其初值指向首结点 while q NULL 当前检查结点 q 不是尾结点时 寻找并删除他的重复结点 p q 工作指针 p 指向 q while p next NULL 当 p 的后继结点存在时 将其数据域与 q 数据域比较 if p next data q data 若 p next 是 q 的重复结点 r p next r 指向待删结点 p next r next 移出结点 p next p next 指向原来 p next 的后继结点 free r else p p next 否则 让 p 指向下一个结点 q q next 更新检查结点 为了便于删除操作 P 指针始终指向 当前比较结点 的前驱结点 2 52 5 其他链表其他链表 2 5 12 5 1 循环链表循环链表 在单链表中 如果让最后一个结点的指针域指向第一个结点可以构成循环链表 在循 环链表中 从任一结点出发能够扫描整个链表 常见的循环链表 带头结点的非空循环链表 带头结点的空循环链表 设立尾指针的非空循环链表 设立尾指针的空循环链表 头指针 head 尾指针 rear 首结点表示为 rear next next 2 5 22 5 2 双向循环链表双向循环链表 双向循环链表与单链表类似 用类 C 语言描述如下 struct dbnode Datatype data struct dbnode prior next typedef struct dbnode dbpointer typedef dbpointer DLinkList 在单链表的每个结点中在设置一个指向其直接前驱结点的指针域 prior 这样每个结 点有两个指针 结点结构 prior data next 头结点的 prior 指向最后一个结点 最后一个结点的 next 指向头结点 由这种结点构 成的链表称为双向循环链表 单链表找直接后继结点的时间复杂度是 O 1 双向循环链表是一种对称结构 找前驱 结点和后继结点的时间复杂度均为 O 1 双向循环链表适合应用在需要经常查找结点的前 驱和后继的场合 双向循环链表的对称性可以用下列等式表示 p p prior next p next prior 结点 p 的前驱结点的 next 和后继结点的 prior 都指向结点 p 1 1 删除删除 在双向循环链表中删除结点时 设 p 指向待删结点 删除 p 可以通过下述语句完成 p prior next p next p 前驱结点的后链指向 p 的后继结点 p next prior p prior p 后继结点的前链指向 p 的前驱结点 free p 释放 p 的空间 其中 这两个语句的执行顺序可以颠倒 2 2 插入插入 在双向循环链表中 在 p 所指结点的后面插入一个新结点 t 需要修改四个指针 t prior p t next p next p next prior t p next t 2 62 6 顺序实现与链接实现的比较顺序实现与链接实现的比较 顺序表优点 随机存储数据元素 缺点 需要预先分配存储空间 链表优点 插入 删除方便 不需要预先分配空间 缺点 需要分配存储指针空间 第三章第三章 栈 队列和数组栈 队列和数组 3 13 1 栈栈 3 1 13 1 1 栈的基本概念栈的基本概念 栈是运算受限的线性表 这种线性表上的插入和删除运算限定在表的某一端进行 允 许进行插入和删除的一端称为栈顶 另一端称为栈底 不含任何数据元素的栈称为空栈 处于栈顶位置的数据元素称为栈顶元素 栈的修改原则是后进先出 Last In First Out 栈又称为后进先出线性表 简称后进 先出表 栈的插入和删除运算分别称为进栈和出栈 栈的基本运算 初始化 InitStack S 构造一个空栈 S 判栈空 EmptyStack S 若栈 S 为空栈 则结果为 1 否则结果为 0 进栈 Push S x 将元素 x 插入栈 S 中 使 x 成为栈 S 的栈顶元素 出栈 Pop S 删除栈顶元素 取栈顶 GetTop S 返回栈顶元素 3 1 23 1 2 栈的顺序实现栈的顺序实现 栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个元素 并用始端作为 栈底 栈的顺序实现称为顺序栈 通常用一个一维数组和一个记录栈顶元素位置的变量来 实现栈的顺序存储 在出栈前判断栈是否为空 如果空栈作出栈运算 会产生 下溢 在进栈前判断是否栈满 如果栈满作进栈运算 会产生 上溢 顺序栈用类 C 语言定义如下 const int maxsize 6 顺序栈的容量 typedef struct seqstack DataType data maxsize 存储栈中数据元素的数组 int top 标志栈顶位置的变量 SeqStk 上述定义存放到 Seqstack h 中 下面列出栈的基本运算在顺序栈上的实现算法 初始化 int InitStack SeqStk stk stk top 0 return 1 判栈空 EmptyStack S int EmptyStack SeqStk stk 若栈为空 则返回值 1 否则返回值 0 if stk top 0 return 1 else return 0 进栈 int Push SeqStk stk DataType x 若栈未满 元素 x 进栈 stk 中 否则提示出错信息 if stk top maxsize 1 判断栈是否满 error 栈已满 return 0 else stk top 栈未满 top 值加 1 stk data stk top x 元素 x 进栈 return 1 出栈 int Pop SeqStk stk if EmptyStack stk 判断是否下溢 栈空 error 下溢 return 0 else 未下溢 栈顶元素出栈 stk top top 值减 1 return 1 取栈顶元素 DataType GetTop SeqStk stk 取栈顶数据元素 栈顶数据元素通过参数返回 if EmptyStack stk return NULLData 栈空 返回 NULLData else return stk data stk top 返回栈顶数据元素 在某些应用中 为了节省空间 让两个数据元素类型一致的栈共享一维数组空间 data max 成为双栈 两个栈的栈底分别设在数组两端 让两个栈彼此迎面增长 两个栈 的栈顶变量分别为 top1 top2 仅当两个栈的栈顶位置在中间相遇时 top1 1 top2 才发 生 上溢 双栈的数据结构定义为 const int max 40 栈容量 typedef struct Dbstack DataType data max int top1 top2 DbStk 双栈中判断上溢语句为 top1 1 top2 判栈空时 两个栈不同 当 top1 0 时栈 1 为空 栈 top2 max 1 时栈 2 为空栈 3 1 33 1 3 栈的链接实现栈的链接实现 栈的链接实现称为链栈 链栈可以用带头结点的单链表实现 LS 指向链表的头结点 首结点是栈顶元素 LS next 指向栈顶结点 尾结点为栈底结点 各结点通过链域的链接 组成栈 由于每个结点空间都是动态分配产生 链栈不用预先考虑容量的大小 链栈用类 C 语言定义如下 typedef struct node DataType data struct node next LkStk 将上述定义存放到 Lkstack h 中 栈的基本运算在链栈上的实现算法如下 初始化 void InitStack LkStk LS LS LkStk malloc sizeof LkStk LS next NULL 建立一个空栈 判栈空 int EmptyStack LkStk LS 若栈为空 则返回值 1 否则返回值 0 if LS next NULL return 1 else return 0 进栈 在进栈操作算法中采用前插操作 新增结点始终插入到头结点之后 void Push LkStk LS DataType x LkStk temp temp LkStk malloc sizeof LkStk temp 指向申请的新结点 temp data x 新结点的 data 域赋值为 x temp next LS next temp 的 next 域指向原来的栈顶结点 LS next temp 指向新的栈顶结点 出栈 出栈操作始终是栈顶结点出栈 即删除头结点之后的结点 int Pop LkStk LS 栈顶数据元素通过参数返回 它的直接后继成为新的栈顶 LkStk temp if EmptyStack LS 判断是否为空 temp LS next temp 指向栈顶结点 LS next temp next 原栈顶的下一个结点成为新的栈顶 free temp 释放原栈顶结点空间 return 1 else return 0 取栈顶元素 DataType GetTop LkStk LS 取栈顶元素 if EmptyStack LS return LS next data 若栈非空 返回栈顶数据元素 else return NULLData 否则返回空元素 例子 借助栈将带头结点的单链表逆置 将链表逆置 其实是将链表结点中数据元素倒置 由于不知道链表的长度 可以用链 栈来实现 扫描链表 将链表中数据元素依次进栈 然后 再一次扫描链表 同时依次进 行出栈操作 将出栈的元素依次填到链表中去 算法描述如下 void ReverseList LkStk head LkStk S DataType x InitStack S 初始化链表 p head next while p NULL 扫描链表 Push S p data 元素进栈 p p next p head next while EmptyStack S 栈不为空时 p data Gettop S 元素添入单链表中 Pop S 出栈 p p next 3 1 43 1 4 栈的简单应用和递归栈的简单应用和递归 栈是一种应用范围广泛的数据结构 适用于各种具有 后进先出 特征的问题 递归是一个重要的概念 同时也是一种重要的程序设计方法 简单地说 如果在一个 函数或数据结构的定义中又应用了它自身 作为定义项之一 那么这个函数或数据结构称 为是递归定义的 例如 阶乘函数可递归定义如下 n 1 n 0 n n 1 n 0 递归定义不能是 循环定义 要求任何递归定义必须同时满足两个条件 被定义项在定义中的应用 即作为定义项的出现 具有更小的 规模 被定义项在最小 规模 上的定义是非递归的 这是递归的结束条件 在上述阶乘函数的定义中 定义 n 又用了 n 1 它具有比原来 n 更小的规模 即 n 1 同时 n 在最小规模 0 上的定义是非递归的 由自然数 1 直接定义 即当 n 0 时 n 1 是递归的结束条件 这两个条件构成了递归算法的基本成分 通常将反映条件 的部 分写在递归函数的开头 计算阶乘函数的递归算法描述 include long f int n f 表示求 n 的函数 if n 0 return 1 递归的结束条件 0 1 else return n f n 1 n n 1 递归步骤 main int m n 3 m f n printf d d n n m 3 23 2 队列队列 3 2 13 2 1 队列的基本概念队列的基本概念 队列 Queue 是有限个同类型数据元素的线性序列 是一种先进先出 First In First Out 的线性表 新加入的数据元素插在队列尾端 出队列的数据元素在队列首部被 删除 排队的规则是不允许插队 新加入的成员只能排在队列尾 而且队列中全体成员只能 按入队列的顺序离开队列 即先进先出 在操作系统中 需要一个队列来保持多个进程按某种次序依次执行 就是进程调度中 的就绪队列 队列的基本运算 队列初始化 InitQueue Q 设置一个空队列 Q 判队列空 EmptyQueue Q 若队列 Q 为空 则返回值为 1 否则返回值为 0 入队列 EnQueue Q x 将数据元素 x 从队尾一端插入队列 使其成为队列的新尾元 素 出队列 OutQueue Q 删除队列元素 取队列首元素 GetHead Q 返回队列首元素的值 3 2 23 2 2 队列的顺序实现队列的顺序实现 顺序存储实现的队列称为顺序队列 由一个一维数组 储存队列中元素 及两个分别 指示队列首和队列尾元素的变量组成 两个变量分别称为队列首指针和队列尾指针 用类 C 语言定义顺序队列类型如下 const int maxsize 20 typedef struct seqqueue DataType data maxsize int front rear SeqQue SeqQue SQ 顺序队列结构类型中有三个域 data front 和 rear 其中 data 为一维数组 存储队 列中数据元素 front 和 rear 定义为整形变量 实际取值范围是 0 maxsize 1 为了方 便操作 规定 front 指向队列首的前一个单元 rear 指向实际的队列尾元素单元 入队列操作可用两条赋值语句 SQ rear SQ rear 1 SQ data SQ rear x 完成 出队 列操作可用一条赋值语句 SQ front SQ front 1 完成 但在实际上 用这种方法来实现 队列的操作会出现一些问题 假溢出 在顺序队列中 数据元素占用数组最大下标的单元后 如果还有元素要 入队列 将超出数组的下标范围 使将要入队的新元素无法进入队列 而此时 数组中下 标底端还有空位置 数组的实际空间并没有占满 这种现象称为 假溢出 循环队列可以 解决 假溢出 问题 循环队列的入队列操作语句为 SQ rear SQ rear 1 maxsize SQ data SQ rear x 循环队列的出队列操作对应的赋值语句为 SQ front SQ front 1 maxsize 用类 C 语言定义循环队列类型如下 typedef struct cycqueue DataType data maxsize int front rear CycQue CycQue CQ 将上述定义存放到头文件 Sequeue h 中 循环队列克服了假上溢 而队列为空时 front rear 队列满时亦有 front rear 区 分两种情况 有两种解决方法 为队列另设一个标志 用来区分队列是空还是满 队列少用一个元素空间 当只剩下一个单元时就认为队列满 此时 队列尾指针只 差一步就将追上队列首指针 循环队列队列满条件为 CQ rear 1 maxsize CQ front 成立 循环队列队列空条件为 CQ rear CQ front 成立 循环队列的基本运算如下 队列的初始化 void InitQueue CycQue CQ CQ front 0 CQ rear 0 判队列空 int EmptyQueue CycQue CQ if CQ rear CQ front return 1 队列为空 返回 1 else return 0 队列不为空 返回 0 入队列 int EnQueue CycQue CQ DataType x if CQ rear 1 maxsize CQ front error 队列满 return 0 队列满 入队列失败 else CQ rear CQ rear 1 maxsize CQ data CQ rear x return 1 入队成功 出队列 int OutQueue CycQue CQ if EmptyQueue CQ 判断队列是否为空 error 队列空 return 0 队列为空 出队列失败 else CQ front CQ front 1 maxsize 不为空 出队列 return 1 出队列成功 取队列首元素 DataType GetHead CycQue CQ if EmptyQueue CQ 判断队列是否为空 return NULLData 队列为空 返回空数据标志 else return CQ data CQ front 1 maxsize 3 2 33 2 3 队列的链接实现队列的链接实现 队列的链接实现是使用一个带有头结点的单链表来表示队列 称为链队列 头指针指 向链表的头结点 单链表的头结点的 next 域指向队列首结点 尾指针指向队列尾结点 即 单链表的最后一个结点 链接队列用类 C 语言描述类型定义如下 typedef struct LinkQueueNode DataType data struct LinkQueueNode next LkQueNode typedef struct LkQueue LkQueNode front rear LkQue LkQue LQ 将上述定义存放到头文件 Lkqueue h 中 由于链接实现需要动态申请空间 故联队在一定范围内不会出现队列满的情况 当 LQ front LQ rear 成立时 队列中无数据元素 此时队列为空 链队列的基本运算如下 队列的初始化 void InitQueue LkQue LQ LkQueNode temp temp LkQueNode malloc sizeof LkQueNode 生成队列的头结点 LQ front temp 队列头指针指向队列头结点 LQ rear temp 队列尾指针指向队列尾结点 LQ front next NULL 判队列空 int EmptyQueue LkQue LQ if LQ rear LQ front return 1 队列为空 返回 1 else return 0 队列不为空 返回 0 入队列 void EnQueue LkQue LQ DataType x LkQueNode temp temp LkQueNode malloc sizeof LkQueNode temp data x temp next NULL LQ rear next temp 新结点入队列 LQ rear temp 置新的队列尾结点 出队列 OutQueue LkQue LQ LkQueNode temp if EmptyQueue CQ 判断队列是否为空 error 队列空 return 0 队列为空 出队列失败 else 队列非空 temp LQ front next 使 temp 指向队列的首结点 LQ front next temp next 修改头结点的指针域指向新的首结点 if temp next NULL LQ rear LQ front 无首结点时 front 和 rear 都指向头结 点 free temp return 1 取队列首元素 DataType GetHead LkQue LQ LkQueNode temp if EmptyQueue CQ 判断队列是否为空 return NULLData 队列为空 返回空数据标志 else temp LQ front next return temp data 队列非空 返回队列首结点元素 3 2 43 2 4 队列应用队列应用 在日常生活中 到银行办理业务时 往往需要排队等候 按照先到先服务的原则 3 33 3 数组数组 3 3 13 3 1 数组的逻辑结构和基本运算数组的逻辑结构和基本运算 数组可以看成线性表的一种推广 一维数组又称向量 是由一组具有相同类型的数据 元素组成 并存储在一组连续的存储单元中 若一位数组中的数据元素又是一位数组结构 则称作二维数组 依次类推 若一维数组中元素又是一个二维数组结构 则称做三维数组 一般地 一个 n 维数组可以看成元素为 n 1 维数组的线性表 数组通常只有两种基本运算 读 给定一组下标 返回该位置的元素内容 写 给定一组下标 修改该位置的元素内容 3 3 23 3 2 数组的存储结构数组的存储结构 一维数组元素的内存单元地址是连续的 二维数组可有两种存储方法 一种是以列序 为主序的存储 另一种是以行序为主序的存储 在类 C 语言的编译程序中 数组采用的是 以行序为主序的存储方法 对于二维数组 a m n 如果每个元素占 k 个存储单元 以行为主序 数组元素的存 储位置是下标的线性函数 a i j 的位置为 loc i j loc 0 0 n i j k 3 3 33 3 3 矩阵的压缩存储矩阵的压缩存储 矩阵式很多科学计算问题研究的对象 矩阵可以用二维数组来表示 如果值相同的元素或者零元素在矩阵中的分布有一定规律 成此类矩阵为特殊矩阵 矩阵的非零元素个数很少的矩阵成为稀疏矩阵 下面主要讨论这两种矩阵的压缩存储 1 1 特殊矩阵特殊矩阵 特殊矩阵主要讨论对称矩阵和三角矩阵 对称矩阵 若一个 n 阶方阵 A 中的元素满足下述条件 a i j a j i 0 i j n 1 则 A 称为对称矩阵 对称矩阵有近一半的元素可以通过其对称元素获得 为每一对对称元素只分配一个存 储单元 则可将 n n 个元素压缩存储到含有 n n 1 2 个元素的一维数组中 设矩阵元素 a i j 在数组 M 中的位置为 k i j 和 k 存在一一对应关系 对称矩阵的下三角部分 当 i j k i i 1 2 j 对称矩阵的上三角部分 当 i j k j j 1 2 i 三角矩阵 以主对角线为界的上 下 半部分是一个固定的值 c 或零 这样的矩阵 叫做下 上 三角矩阵 采用数组 M n n 1 2 存储三角矩阵 上三角矩阵中 第 i 行除常数外有 n i 个元素 第 0 行有 n 个元素 M k 和 a i j 的对应关系是 当 i j k i 2n i 1 2 j i 当 i j n n 1 2 上三角矩阵的存储和对称矩阵类似 M k 和 a i j 的对应关系是 当 i j k i i 1 2 j 当 i j k n n 1 2 2 2 稀疏矩阵稀疏矩阵 假设 m 行 n 列的矩阵有 t 个非零元素 当 t 0 时 有且仅有一个称为根的结点 除根结点外 其余结点分为 m m 0 个 互不相交的非空集合 T1 T2 Tm 这些集合中的每一个都是一棵树 称为根的子树 4 1 24 1 2 树的相关术语树的相关术语 结点的度 树上任一节点所拥有的子树的数目称为该结点的度 叶子 度为 0 的结点称为叶子或终端结点 树的度 一棵树中所有结点的度的最大值称为该树的度 一个结点的子树的根称为该结点的孩子 或称子结点 相应的该结点称为孩子的双亲 也称父结点 结点的层次 从根开始算起 根的层次为 1 其余结点的层次为其双亲的层次加 1 树的高度 一棵树中所有结点层次数的最大值称为该树的高度或深度 有序树 若树中各结点的子树从左到右是有次序的 不能互换 称为有序树 有序树 中最左边子树的根成为第 1 个孩子 左边第 i 个子树的根称为第 i 个孩子 无序树 若树中各结点的子树是无次序的 可以互换 则称为无序树 树的基本运算 求根 Root T 求树的根节点 求双亲 Parent T X 求结点 X 在树 T 上的双亲结点 若 X 是树 T 的根或 X 不在 T 上 则结果为一特殊标志 求孩子 Child T X i 求树 T 上结点 X 的第 i 个孩子结点 若 X 不在 T 上或 X 没有 第 i 个孩子 则结果为一特殊标志 建树 Create X T1 Tk k 1 建立一颗以 X 为根 以 T1 Tk 为第 1 k 颗子树的树 剪枝 Delete T X i 删除树 T 上结点 X 的第 i 颗子树 若 T 无第 i 颗子树 则为 空操作 遍历 Traverse T 遍历树 即访问树中每个结点 且每个结点仅被访问一次 4 24 2 二叉树二叉树 4 2 14 2 1 二叉树的基本概念二叉树的基本概念 二叉树 Binary Tree 是 n n 0 个元素的有限集合 该集合或者为空 或者有一个根 及两颗互不相交的左子树和右子树组成 其中左子树和右子树也均为二叉树 二叉树有五种基本形态 空二叉树 左右子树均为空的二叉树 右子树为空的二叉树 左子树为空的二叉树 左右子树都非空的二叉树 二叉树的基本运算 初始化 Initiate BT 建立一颗空二叉树 BT 为空 求