网站标题更改电子商务网站开发的总结

当前位置： 首页 > news >正文

网站标题更改,电子商务网站开发的总结,网站建设文献综述范文,线报网站如何做文章目录 本次课程内容第四章 数组、广义表和串第一节 数组及广义表数组的基本操作数组的顺序存储方式-借用矩阵行列式概念二维数组C语言对应的函数-通常行主序方式 矩阵的压缩存储对称矩阵和三角矩阵压缩存储后#xff0c;采用不同的映射函数稀疏矩阵-可以构成三元组线性表三… 文章目录 本次课程内容第四章 数组、广义表和串第一节 数组及广义表数组的基本操作数组的顺序存储方式-借用矩阵行列式概念二维数组C语言对应的函数-通常行主序方式 矩阵的压缩存储对称矩阵和三角矩阵压缩存储后采用不同的映射函数稀疏矩阵-可以构成三元组线性表三元组在C语言中的实现三元组表的转置三元组转置的算法实现 数组的应用-解决迷宫问题广义表广义表示例广义表操作示例 本次课程内容 第四章 数组、广义表和串 第一节 数组及广义表 数组的基本操作 数组是高级程序设计语言中的重要语法成分很多语言都定义了数组类型。例如在C语言中定义了一维数组。数组元素还可以是数组由此得到数组的数组 即多维数组。 一般将n(n2)维数组看作n-1维数组的数组。 从数据结构的角度来理解一维数组可以作为线性表的存储结构数组中保存的各元素可以组成一个线性表。多维数组在系统内部都对应一个隐含的一维数组所 以多维数组也是一种线性表。例如二维数组就是以一维数组为元素的线性表。 数组的每个元素都是形如(indexvalue)的二元对index是数组下标也称为索引value是对应于该下标的数值。任何两个元素的index值都不相同。 从数组的操作可知它没有一般线性表常用的插入和删除操作更多的是根据下标index访问元素。 数组的顺序存储方式-借用矩阵行列式概念 一维数组天然地采用顺序存储方式 多维数组的顺序存储又是什么样的呢? 数组的顺序存储有两种形式。以二维数组为例它的元素可以按行排列也可以按列排列。 这里的“行”和“列”借用数学上矩阵或行列式中的概念。 所谓按行排列就是先排数组的第一行紧随其后排第二行依此类推。 所谓按列排列就是先排数组的第一列紧随其后排第二列依此类推。 最终都是将数组中的全部元素排列成一个序列。 在C语言中可以定义多维数组它的下标采取如下的形式表示: 二维数组C语言对应的函数-通常行主序方式 通常int类型占4字节数组D2Array中含有18个元素共占用18x472字节。如果保存的起始地址是1000则数组将占用从1000到1071的内存空间。注意这里 提到的字节编号并不是内存中真实的编号。将图4-1所示的下标表格按行自上而下、同一行中自左至右的次序进行连续编号从0开始 即可得到图4-2a所示的编号结果 这种按行优先把二维数组中的下标映射到0~n-1之间的某个整数的方式称为按行优先方式也称为行主序方式。 包括C语言在内的大多数程序设计语言均采用行主序的实现模式。 也有一些程序设计语言采用另一种实现模式称为按列优先方式也称为列主序方式。 在列主序方式中按列优先对于下标表格从第一列开始从上到下进行连续编号直到最后一列。这个结果如图4-2b所示。 矩阵的压缩存储 数学中的矩阵可以使用二维数组保存。对于n行m列的矩阵数组元素至少需要分配n x m个。 有些矩阵因其特殊性可以不必保存其中的所有元素因而可以减少为数组分配的空间。 对称矩阵和三角矩阵 如果不考虑矩阵的特殊性按照一般二维数组的顺序存储方式来存储特殊矩阵也是完全可行的。 但是从节省存储空间的角度考虑对称矩阵和上(下)三角矩阵都可以只保存矩阵中约一半的元素从而可以节省差不多一半的存储空间。 这样的存储形式称为压缩存储。 具体来说对干对称矩阵因为对角线以上及以下的元素对称相等所以只需要保存其中的一半及对角线上的元素。 对于上三角矩阵或下三角矩阵仅保存上三角部分或下三角部分的元素另外一半的0元素不再保存。
若矩阵有n行n列则这三种形式下需要保存的元素个数为nx(n1)/2。 在采用压缩存储以后需要寻找与普通二维数组不同的映射函数。 压缩存储后采用不同的映射函数 稀疏矩阵-可以构成三元组线性表 在实际的应用中矩阵中可能会出现大量的0元素而非0元素数量很少这就是所谓的稀疏矩阵。至于非0元素少到什么程度才能称为稀疏矩阵并没有很严格的定义。通常认为矩阵中非0元素的个数与矩阵的阶数相当即可将其看作稀疏矩阵。 如何理解 为了节省空间一般只存储稀疏矩阵中的非0元素。但在稀疏矩阵中非0元素的出现是没有规律的 所以在存储非0元素时必须将它所在的行号和列号一起存储起来。这些信息组成一个三元组(ijv)的形式 其中v表示非0元素的值i表示v所在的行号i表示v所在的列号。 一个稀疏矩阵的所有元素用一个三元组表来表示也就是可以构成一个三元组的线性表。 为了方便后续其他操作的实现三元组表应该是一个有序序列通常按行主序的次序排列即先按行的大小排列同一行的三元组再按列的大小排列。 三元组表的初始值从键盘输入输入时各三元组可以按行主序排列也可以按任意的次序排列但最终都应该按行主序的次序插入到一维数组的合适位置。 当然在有特殊需求的应用中也可以按列主序方式保存。 三元组在C语言中的实现 三元组表的转置 转置是矩阵中常用的一种操作。下面实现采用三元组表表示的稀疏矩阵的转置算法。矩阵转置即行、列互换i行的元素放置到i列这也意味着j列的元素放置在j行。如果矩阵是nxm则转置后得到的矩阵是mxn的。 很容易想到将三元组表中的每个三元组项的i与i互换即可得到转置后矩阵的三元组表。但是这样转换后得到的三元组表不再按行主序排列不便于后续操作的实现。所以要实现矩阵转置程序必须先得到一个按行主序排列的三元组表。 可以像readSparseMatrix函数那样处理读入原矩阵的一个三元组插入到目标矩阵的三元组表中。在插入过程中需要调整部分三元组在三元组表中的次序也就是需要进行元素的移动。从顺序表实现的时间复杂度分析中知道这样的移动会导致转置操作的效率很低。 可以使用一个临时计数数组记录原矩阵的每个三元组在目标矩阵的三元组表中的插入位置以辅助完成转置操作由此避免了三元组的移动可高效率地实现转置操作。 不失一般性设原矩阵A的行数是rows列数是cols则转置后矩阵B的行数是cols列数是rows。元组的个数没有改变。 三元组转置的算法实现 数组的应用-解决迷宫问题 多维数组特别是二维数组在计算机科学中有广泛的应用。 下面以一个有趣的“迷宫”问题为例,介绍数组的应用。 “老鼠走迷宫”是实验心理学中的一个经典问题也是一种智力游戏。 在计算机模拟实现中可以用-个较大的二维数组表示迷宫其中元素0表示走得通元素1表示走不通(受阻)行走路径只考虑水平和垂直方向上的4个方向(上、下、左、右)。图4-9是一个迷宫示意图。 适合解决复杂迷宫问题简单的用算法不至于 广义表 广义表是线性表的推广也称为列表。 它是由n(n≥0)个表元素组成的有限序列记为: 广义表示例 广义表操作示例