第7章 数组 零基础学数据结构.ppt

《第7章 数组 零基础学数据结构.ppt》由会员分享，可在线阅读，更多相关《第7章 数组 零基础学数据结构.ppt（51页珍藏版）》请在金锄头文库上搜索。

1、第7章数组 数组是一种扩展的线性数据结构 线性表 栈 队列 串的数据元素都是不可再分的原子类型 而数组中的数据元素是可以再分的 数组可以分为一维数组和多维数组 一维数组中的元素是由原子构成的 多维数组中的元素又是一个线性表 因此 数组是一种特殊的线性表 7 1数组 数组是一种特殊的线性表 表中的元素可以是原子类型 也可以是一个线性表 本节主要介绍数组的定义和数组的抽象数据类型 7 1 1数组的定义 数组是由n个类型相同的数据元素组成的有限序列 其中 这n个数据元素占用一块地址连续的存储空间 数组中的数据元素可以是原子类型的 如整型 字符型 浮点型等 这种类型的数组称为一维数组 也可以是一个线性

2、表 这种类型的数组称为二维数组 二维数组可以看成是线性表的线性表 7 1 2数组的抽象数据类型 1 数据对象集合2 基本操作集合 7 2数组的顺序表示与实现 一般情况下 不对数组进行插入和删除操作 如果建立了数组 则数组的维数与各维的长度不再改变 因此 数组采用的是顺序存储方式 本节的主要学习内容包括数组的顺序存储结构及顺序存储结构下的操作实现 7 2 1数组的顺序存储结构 在计算机中 存储器的结构是一维 线性 的结构 数组是一个多维的结构 如果要将一个多维的结构存放在一个一维的存储单元里 就必须先将多维的数组转换成一个一维的线性序列 才能将其存放在存储器中 7 2 1数组的顺序存储结构 数组

3、的顺序存储结构类型定义描述如下 defineMaxArraySize3 include 标准头文件 包含va start va arg va end宏定义 typedefstruct DataType base 数组元素的基地址 intdim 数组的维数 int bounds 数组的每一维之间的界限的地址 int constants 数组存储映像常量基地址 Array 7 2 2数组的基本运算 在顺序存储结构中 数组的基本运算实现如下所示 1 数组的初始化操作 va list的用法 1 首先在函数里定义一个va list型的变量 这个变量是指向参数的指针 2 然后用va start初始化变量刚

4、定义的va list变量 该函数的第二个参数是第一个可变参数的前一个参数 它是一个固定的参数 3 然后用va arg返回可变的参数 va arg的第二个参数是要返回的参数的类型 4 最后用va end结束可变参数的获取 7 2 2数组的基本运算 2 销毁数组操作 voidDestroyArray Array A 销毁数组 将动态申请的内存单元释放 if A base free A base if A bounds free A bounds if A constants free A constants A base A bounds A constants NULL 将各个指针指向空 A d

5、im 0 7 2 2数组的基本运算 3 返回数组中指定的元素 intGetValue DataType e ArrayA 返回数组中指定的元素 将指定的数组的下标的元素赋值给e va listap intoffset va start ap A if LocateArray A ap 7 2 2数组的基本运算 4 数组的赋值操作 intAssignValue ArrayA DataTypee 数组的赋值操作 将e的值赋给的指定的数组元素 va listap intoffset va start ap e if LocateArray A ap 7 2 2数组的基本运算 5 数组的定位操作 in

6、tLocateArray ArrayA va listap int offset 根据数组中元素的下标 求出该元素在A中的相对地址offset inti instand offset 0 for i 0 i A bounds i return0 offset A constants i instand return1 7 2 3数组的应用举例 下面通过一个例子来说明数组基本操作的用法 例7 1利用数组的基本操作实现对数组的初始化 赋值 返回数组的值及定位操作 定义一个二维数组B 并将B初始化 然后将数组B的值依次赋值给数组A 并将数组A的元素输出 7 3特殊矩阵的压缩存储 在许多科学与工程计算

7、中会经常遇到矩阵运算的问题 在高级语言中 通常使用二维数组来存储矩阵 然而 在矩阵的运算中 往往在阶数很高的矩阵中存在许多相同的元素或值为零的元素 为了节省空间 需要将这些矩阵进行压缩存储 7 3 1对称矩阵的压缩存储 如果一个n阶的矩阵A中的元素满足性质aij aji 0 i j n 1 则称这种矩阵为n阶对称矩阵 由于对称矩阵中的元素关于主对角线对称 因此 在对矩阵存储时 可以只存储对称矩阵中的上三角或者下三角的元素 使得对称的元素共享一个存储单元 7 3 1对称矩阵的压缩存储 7 3 2三角矩阵的压缩存储 三角矩阵分为两种 上三角矩阵和下三角矩阵 其中 下三角元素均为常数c或零的n阶矩阵

8、称为上三角矩阵 上三角元素均为常数c或零的n阶矩阵称为下三角矩阵 7 3 2三角矩阵的压缩存储 7 3 3对角矩阵的压缩存储 对角矩阵 也称带状矩阵 是另一类特殊的矩阵 所谓对角矩阵 就是所有的非零元素都集中在以主对角线两侧的带状区域内 对角线的个数为奇数 也就是说除了主对角线和主对角线两边的对角线外 其他元素的值均为0 7 3 3对角矩阵的压缩存储 因此 k Loc 0 0 3 i 1 1 j i 1 Loc 0 0 2 i 1 j 1 则k 2 i 1 j 1 7 4稀疏矩阵的压缩存储 稀疏矩阵中的大多数元素是零 因此也需要进行压缩存储 本节的主要学习内容包括稀疏矩阵的定义 稀疏矩阵的抽象

9、数据类型 稀疏矩阵的三元组表示及算法实现 7 4 1稀疏矩阵的定义 所谓稀疏矩阵 假设在m n矩阵中 有t个元素不为零 令 为矩阵的稀疏因子 如果 则称矩阵为稀疏矩阵 也就是说 矩阵中存在大多数为零的元素 只有很少的非零元素 这样的矩阵是稀疏矩阵 7 4 2稀疏矩阵抽象数据类型 1 数据对象集合2 基本操作集合 7 4 3稀疏矩阵的三元组表示 为了实现压缩存储 可以只存储稀疏矩阵的非零的元素 在存储稀疏矩阵中的非零元素时 还必须存储非零元素对应的行和列的位置 i j 也就是说存储一个非零元素需要存储元素的行号 列号和元素值 即通过存储 i j aij 唯一确定一个非零的元素 0 3 9 1 1

10、 3 2 2 7 2 3 2 3 0 7 3 4 2 4 2 4 4 3 7 5 4 5 7 4 3稀疏矩阵的三元组表示 7 4 3稀疏矩阵的三元组表示 三元组顺序表的类型定义如下 defineMaxSize200typedefstruct 三元组类型定义 inti j DataTypee Triple typedefstruct 矩阵类型定义 Tripledata MaxSize intm n len 矩阵的行数 列数和非零元素的个数 TriSeqMatrix 7 4 4稀疏矩阵的三元组实现 下面给出稀疏矩阵的基本操作的算法实现 算法实现保存在文件 TriSeqMatrix h 中 1 创建

11、稀疏矩阵操作 2 销毁稀疏矩阵操作 voidDestroyMatrix TriSeqMatrix M 销毁稀疏矩阵操作 因为是静态分配 所以只需要将矩阵的行数 列数和个数置为0 M m M n M len 0 7 4 4稀疏矩阵的三元组实现 3 稀疏矩阵的复制操作 voidCopyMatrix TriSeqMatrixM TriSeqMatrix N 由稀疏矩阵M复制得到另一个矩阵N inti N len M len 修改稀疏矩阵N的非零元素的个数 N m M m 修改稀疏矩阵N的行数 N n M n 修改稀疏矩阵N的列数 for i 0 idata i i M data i i N data

12、 i j M data i j N data i e M data i e 7 4 4稀疏矩阵的三元组实现 4 稀疏矩阵的相加操作 5 稀疏矩阵的相减操作 7 4 4稀疏矩阵的三元组实现 6 稀疏矩阵的转置操作 7 4 4稀疏矩阵的三元组实现 7 4 4稀疏矩阵的三元组实现 7 5稀疏矩阵的应用举例 在上一节学习了稀疏矩阵的定义及稀疏矩阵的三元组顺序存储的算法实现 这一节主要通过分析并实现两个矩阵的相乘的算法 来加强对稀疏矩阵知识的学习 7 5 1稀疏矩阵的相乘三元组表示 两个矩阵相乘是矩阵的一种常用的运算 假设矩阵M是m1 n1的矩阵 N是m2 n2的矩阵 如果矩阵M的列数与矩阵N的行数相等

13、 即n1 m2 则两个矩阵M和N是可以相乘的 7 5 1稀疏矩阵的相乘三元组表示 7 5 1稀疏矩阵的相乘三元组表示 7 5 1稀疏矩阵的相乘三元组表示 defineMaxSize200typedefintDataType typedefstruct 三元组类型定义 inti j DataTypee Triple typedefstruct 矩阵类型定义 Tripledata MaxSize intrpos MaxSize 用于存储三元组中的每一行的第一非零元素的位置 intm n len 矩阵的行数 列数和非零元素的个数 TriSeqMatrix 7 5 2稀疏矩阵的相乘三元组实现 1 算法

14、的测试部分2 两个矩阵相乘的算法实现 7 6稀疏矩阵的十字链表表示与实现 采用三元组顺序表在进行两个稀疏矩阵的相加和相乘运算时 需要移动大量的元素 算法的时间复杂度也大大增加 因此 本节来学习稀疏矩阵的另一种存储结构 链式存储 7 6 1稀疏矩阵的十字链表表示 稀疏矩阵的链式存储 就是利用链表来表示稀疏矩阵 链表中的每个结点存储稀疏矩阵中的每个非零元素 每个结点包含5个域 3个数据域和两个指针域 其中3个数据域是i j和e 分别表示非零元素的行号 列号和元素值 2个指针域是right域和down域 right指向同一行中的下一个非零元素 down指向同一列的非零元素 7 6 1稀疏矩阵的十字链

15、表表示 7 6 1稀疏矩阵的十字链表表示 十字链表的类型描述如下 typedefstructOLNode inti j DataTypee structOLNode right down OLNode OLink typedefstruct OLink rowhead colhead intm n len CrossList 7 6 2十字链表的实现 下面给出稀疏矩阵的十字链表的基本操作的算法实现 算法实现保存在文件 CrossList h 中 7 6 2十字链表的实现 1 稀疏矩阵的初始化操作 voidInitMatrix CrossList M 初始化稀疏矩阵 M rowhead M co

16、lhead NULL M m M n M len 0 7 6 2十字链表的实现 2 稀疏矩阵的创建操作 3 稀疏矩阵的插入操作 4 稀疏矩阵的销毁操作 7 7稀疏矩阵的十字链表实现应用举例 十字链表在稀疏矩阵的相加 相减和相乘操作是比较恰当的 本节通过两个稀疏矩阵的相加操作来说明稀疏矩阵的十字链表的使用 7 7稀疏矩阵的十字链表实现应用举例 例7 3例如有两个稀疏矩阵A和B 相加得到C 如图7 21所示 请利用十字链表实现两个稀疏矩阵的相加 并输出结果 7 7稀疏矩阵的十字链表实现应用举例 7 7稀疏矩阵的十字链表实现应用举例 1 十字链表表示的稀疏矩阵相加算法2 测试程序部分 7 8小结 本章主要介绍了一种扩展的线性表 数组 数组是由n个相同数据类型的数据元素 a0 a1 a2 an 1 组成的有限序列 三元组顺序表在实现创建 复制 转置 输出等操作比较方便 但是在进行矩阵的相加和相乘的运算中 时间的复杂度比较高 十字链表在各种操作实现时比较麻烦 但是在进行稀疏矩阵的相加和相乘等操作时 主要是进行插入和删除操作 因此 时间复杂度较低 本章重点介绍了特殊矩阵的压缩存储和稀疏矩阵的压缩存