内容导读
线性结构的特点是数据元素之间是一种线性关系,数据元素“一个接一个地排列”。在线性结构中,有且仅有一个元素被称为“第一个”,除第一个元素之外的其他元素均有唯一一个“前驱”;有且仅有一个元素被称为“最后一个”,除最后一个元素之外的其他元素均有唯一一个“后继”。具有这种结构特征的数据在日常生活中有很多,本章将详细讲述基本线性结构的存储表示及其操作实现,以及字符串、特殊矩阵和广义表等扩展线性结构的存储表示和相关操作的实现。
【主要内容提示】
➢ 线性表的顺序存储与实现
➢ 线性表的链式存储与实现
➢ 具有特殊操作规则的线性结构——堆栈的实现及其应用
➢ 具有特殊操作规则的线性结构——队列的实现及其应用
➢ 字符串的基本概念、运算和存储
➢ 字符串模式匹配算法及其改进
➢ 多维数组与特殊矩阵的存储
➢ 稀疏矩阵的存储与运算实现
➢ 广义表的概念及其存储表示
【学习目标】
➢ 定义线性表的顺序存储并写出其基本操作的实现
➢ 定义线性表的链式存储并写出其基本操作的实现
➢ 定义顺序栈和链式栈并写出其基本操作的实现
➢ 举例说明栈的应用求解过程
➢ 定义循环队列和链式队列并写出其基本操作的实现
➢ 举例说明队列的应用求解过程
➢ 定义字符串的存储并写出其基本操作的实现
➢ 熟练写出字符串模式匹配的BF算法并能进行时空效率分析
➢ 能够描述字符串匹配的KMP算法的改进思路并会求next数组的值
➢ 能够将多维数组和特殊矩阵映射到一维
➢ 定义稀疏矩阵的三元组表存储并实现矩阵运算
➢ 描述广义表的概念并定义广义表的存储