青岛大学数据结构与算法——第4章

一 概述

• 串
• 数组
• 广义表

二 串

• 串定义：定义、串名、串值、串长、子串/真子串、字符位置、空格串

• 案例：病毒感染检测

• 串类型定义、存储结构及其运算

  • 定义：ADT String

  • 操作：strAssign、strCompare、strLength、concat、其他

  • 存储结构：顺序串，链串

  • 串的匹配算法：

    • 算法目的：第一次出现位置
    • 应用：拼写检查、翻译、压缩

  • 算法种类：

    • BF算法，穷举
    • KMP算法(速度快)

三 数组

3.1 概念

• 定义
• 声明

3.2 数组的抽象数据类型ADT Array

3.3 基本操作

• initArray
• destoryArray
• ValueA
• Assign

3.4 矩阵的压缩存储

3.5 稀疏矩阵存储

四 广义表

4.1 概念

• 定义：列表Lists,n个元素的有限序列
• 示例：参赛名单

4.2 术语

• 广义表
• 表头
• 表尾

五 图示