哈工大数据结构课件第二章.pdf

第2章 线性表 数据结构与算法数据结构与算法数据结构与算法数据结构与算法 Data Structures and Alggorithms 张岩 哈工大计算机科学与技术学院 2013/9/22 哈工大计算机科学与技术学院 张岩 Slide 2-1 第第第第2222章章章章 线性表线性表线性表线性表 2013/9/22 Slide 2-2 第2章 线性表 学习目标 学习目标 掌握线性表的逻辑结构，线性表的顺序存储结构和链式存储 结构结构的的描述方法描述方法；熟练掌握线性表在顺序存储结构和链式存熟练掌握线性表在顺序存储结构和链式存 储结构的结构特点以及相关的查找、插入、删除等基本操作 的实现的实现；；并能够从时间和空间复杂性的角度综合并能够从时间和空间复杂性的角度综合比较比较两种存两种存 储结构的不同特点 掌握掌握栈和队列栈和队列的的结构特性和描述方法结构特性和描述方法，，熟练掌握栈和队列的熟练掌握栈和队列的 基本操作的实现，并且能够利用栈和队列解决实际应用问题 掌握掌握串串的结构特性以及串的基本操作的结构特性以及串的基本操作，，掌握针对字符串进行掌握针对字符串进行 操作的常用算法和模式匹配算法 掌握掌握多维数组多维数组的的存储和表示方法存储和表示方法，，掌握对掌握对特殊矩阵进行压缩特殊矩阵进行压缩 存储时的下标变换公式，了解稀疏矩阵的压缩存储表示方法 及适用范围 了解广义表的概念和特征 2013/9/22 哈工大计算机科学与技术学院 张岩 Slide 2-3 第2章 线性表 本章主要内容本章主要内容本章主要内容本章主要内容 2.1 线性表的逻辑结构 2.2 线性表的存储结构 2.3 栈（Stack） 2.4 队列（Queue） 2.52.5 串串 （（StringString ）） 2.6 数组（Array） 2.7 广义表 （Generalized List ） 2.7 广义表 （Generalized List ） 本章小结 2013/9/22 哈工大计算机科学与技术学院 张岩 Slide 2-4 第2章 线性表 本章的知识点结构本章的知识点结构 本章的知识点结构本章的知识点结构 基本的数据结构（ADT ） 线性表线性表、栈栈、队列队列、串串、（多维多维）数组数组、广义表广义表 知识点结构 ADT定义 定义及相关术语 静态的结构 逻辑结构逻辑结构 逻辑结构及其特征逻辑结构及其特征 ADT 基本操作（算法） 动态的操作 基本基本 存储结构存储结构 （（描述描述）） 数据 ADT实现 存储结构特点 静态的结构 结构 存储结构 存