07《数据结构》第五章.pdf

数据结构 北京邮电大学 信息安全中心 武 斌 上章内容 上一章 （串）内容： 理解 “串”类型定义中各基本操作的特点 能正确利用这些特点进行串的其它操作 理解串类型的各种存储表示方法 理解串匹配的各种算法 2 本次课程学习目标 学习完本次课程，您应该能够： 理解数组类型的特点及其在高级编程语言中的存 储表示和实现方法 掌握数组在以行为主的存储表示中的地址计算方 法 掌握特殊矩阵的存储压缩表示方法 理解稀疏矩阵的两类存储压缩方法的特点及其适 用范围 掌握广义表的结构特点及其存储表示方法 3 本章课程内容（第五章数组和广义表） 5.1 数组的类型定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 4 第五章数组和广义表  数组是所有高级编程语言中都已实现的固有数据类型，因此 凡学习过高级程序设计语言的读者对数组都不陌生。但它和 其它诸如整数、实数等原子类型不同，它是一种结构类型。 换句话说，数组是一种数据结构。 5 数组的类型定义 5.1 数组的类型定义 5.2 数组的顺序存储表示 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构 6 数组的类型定义 看一个二维数组的简单情况： D = { a i, j | 0≤i≤m-1, 0≤j≤n-1, a i, j ∈ElemType } R = { ROW, COL } 其中： ROW = { a i-1, j , a i, j | i=1,…,m-2, 0≤j≤n-1, a i-1, j , a i, j ∈ElemType} (称作行关系) COL = { a i, j-1, a i, j | j= 1,…,n-2, 0≤i≤m -1, a i, j-1, a i, j ∈ElemType} (称作列关系) 7 数组的类型定义 上述定义的二维数组中共有 m ×n 个元素，每个元素 a i, j 同时处于“行” 和 “列”的两个关系中，它既在 “行关系ROW”中是 ai-1, j (i0)的后继， 又在 “列关系