886-数据结构（C语言版）.pptVIP

数据结构(C语言版) 第1章 绪论 1-1 什么是数据结构 1-1 什么是数据结构 例1-1．学生入学情况登记问题 例1-2．井字棋对奕问题 例1-3．教学计划编排问题 由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。 数据的逻辑结构 逻辑结构的描述 例1-4．数据结构Line=（D，R) 1-2 基本概念和术语 例1-5．数据结构Tree =（D，R) 例1-6．数据结构graph =（D，R) 数据的存储结构 1-3 抽象数据类型的表示与实现 1-4 算法和算法分析 算法特性 算法要求 算法描述 算法性能分析与度量 时间复杂度（Time complexity） 空间复杂度（Space complexity） 小 结 数据结构就是研究数据的逻辑结构、存储结构和运算方法的学科。 数据的逻辑结构包括：集合、线性结构、树形结构、图形结构四种类型。 数据的存储结构包括：顺序存储、链式存储、索引存储、散列存储四种。 算法的特性及评价算法的好坏标准 时间复杂度与空间复杂度 第2章 线性表 2-1 线性表的类型定义 2-1 线性表的类型定义 基本概念 基本运算 2-2 线性表的顺序表示与实现 线性表的顺序存储 结构 基本运算在线性表上的实现 构造一个空线性表算法 线性表的插入算法 线性表的删除算法 插入算法性能分析 删除算法性能分析 2-3 线性表的链式表示与实现 线性链表基本概念 单链表基本运算 单链表的插入算法 单链表的插入算法 单链表的插入算法 单链表的删除算法 单链表的删除算法 单链表的删除算法 循环链表 双向链表 双向链表的结点结构 双向链表的前插入操作 双向链表的删除操作 小 结 线性表是一种最简单的数据结构，数据元素之间存在着一对一的关系。其存储方法通常采用顺序存储和链式存储。 顺序存储的最大优点是可以随机存取，且存储空间比较节约，而缺点是表的扩充困难，插入、删除要做大量的元素移动。 线性表的链式存储是通过结点之间的链接而得到的。根据链接方式又可以分为：单链表、双链表和循环链表等。 第3章 栈和队列 3-1 栈 3-1 栈 栈的定义及相关概念 栈的基本运算 栈的表示与实现 栈的表示与实现 栈的操作示意图 3-2 栈的应用举例 例3-1 将十进制138转换为二进制 例3-2 3 + 4 /（25–（6 + 15））* 8 例3-3 迷宫求解 例3-3 迷宫求解 3-3 队列 队列的定义及相关概念 队列的实例 队列的基本运算 链队列—队列的链式表示与实现 队列运算指针变化状况 链队的描述 链队列的入队运算 链队列的出队运算 链队列的队队头元素 顺序队列—队列的顺序表示与实现 顺序队列的假溢出 循环队列 循环队列的变化 循环队列的基本运算 小 结 栈只允许在栈顶进行插入和删除等操作;队列只允许在队尾进行插入操作，在队头进行删除操作。 栈主要特点是“后进先出”。队列的主要特点是“先进先出”。 栈的主要操作：进栈、出栈、读栈顶元素、判栈空和判栈满。 队列的主要操作:进队、出队、判队空、判队满、求队列长度和读队头元素等。 能灵活应用栈和队列的基本原理解决一些综合性的应用问题。 第4章 串 4-1 串类型的定义 4-1 串类型的定义 串的定义及相关概念 串的基本运算 4-2 串的表示与实现 顺序串 静态存储的顺序串 静态存储的顺序串 动态存储的顺序串 串的链式存储 链串的结点大小 4-3 串的模式匹配 模式匹配的基本思想 模式匹配的例子 小 结 串是一种特殊的线性表，规定每个数据元素仅由一个字符组成。 串的顺序存储有非紧凑格式和紧凑格式两种，非紧凑格式存储操作简单，但内存浪费；紧凑格式可以节省内存，但操作却不方便。 串的链式存储结构具有插入、删除方便的优点，但其存储密度很低；若采用紧凑的链式存储（一个结点放多个字符），虽然提高了空间利用率，但其插入、删除方便的优点也随之消失。 串的堆分配存储是一种动态存储结构。 串的基本运算包括串的连接、插入、删除、比较、替换、和模式匹配等 第5章 数组和广义表 5-1 数组的定义 5-1 数组的定义 5-2 数组的顺序存储与实现 例5-1 一个2×3二维数组 5-2 数组的顺序存储与实现 5-3 矩阵的压缩存储 矩阵的二维数组描述 矩阵的压缩存储 特殊矩阵 对称矩阵的特点 对称矩阵的压缩存储 三角矩阵的特点 三角矩阵的压缩存储 对角矩阵的特点 对角矩阵的压缩存储 稀疏矩阵 稀疏矩阵 三元组顺