还剩25页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数组和广义表》ppt课件•数组的定义和性质目•数组的存储结构•广义表的定义和性质录•广义表的存储结构•数组和广义表的应用CATALOGUE01CATALOGUE数组的定义和性质数组的基本概念数组是一种线性表,由有序的元素组成每个元素都有其对应的下标,表示它在数组中的位置数组是一种静态数据结构,其大小在创建时确定,且在程序运行期间不能改变数组的维数和元素数组的维数表示其包数组的元素可以通过含的元素个数下标来访问,下标从0开始计数一维数组包含一个线性序列的元素;二维数组则包含多个一维数组数组的运算数组的运算包括赋值、索引、扩展、连接等赋值运算用于给数组元素赋值;索引运算用于获取或修改数组元素的值;扩展运算用于创建新的数组元素;连接运算用于将两个数组组合成一个新的数组02CATALOGUE数组的存储结构一维数组的存储连续存储一维数组在内存中占据一段连续的地址空间,每个元素占用固定大小的存储单元下标计算数组下标从0开始,第i个元素存储在a[i]的位置,可以通过计算i*元素大小来得到多维数组的存储二维数组可以看作是多个一维数组的集合,每个一维数组称为一个“行”三维及更高维数组可以类比二维数组,通过增加更多的维度来扩展特殊类型的数组010203稀疏矩阵对称矩阵下三角矩阵非零元素较少的矩阵,可主对角线两侧对称的矩阵,对角线以下元素全为零的以采用特殊存储方式以节可以采用压缩存储方式矩阵,可以只存储上三角省空间部分03CATALOGUE广义表的定义和性质广义表的基本概念广义表由n个元素(元素可以是一个数、一个符号或一个广义表)组成的有限序列广义表的长度广义表中元素的个数广义表的深度广义表嵌套的层数广义表的特性广义表中的元素可以是数、符广义表是有限序列,即它包含广义表中的元素可以嵌套,即号或另一个广义表的元素个数是有限的一个元素可以是一个广义表广义表的运算广义表的加法广义表的乘法广义表的子表广义表的转置将一个广义表的每个元将两个广义表对应位置素与另一个广义表的每从广义表中选取若干个将广义表中的行和列互的元素相加,得到一个个元素相乘,得到一个元素组成的新广义表换,得到一个新的矩阵新的广义表新的广义表04CATALOGUE广义表的存储结构静态链式存储结构定义优点缺点静态链式存储结构是指将空间利用率较高,因为所插入和删除操作较复杂,广义表中的元素存储在数有元素都存储在连续的内需要移动大量元素来维护组中,并使用指针来指示存空间中数组的连续性元素之间的关系动态链式存储结构定义优点缺点动态链式存储结构是指使用链表插入和删除操作较简单,只需要空间利用率较低,因为需要额外来存储广义表中的元素,每个元修改指针即可的空间来存储指针素包含数据域和指针域数据域存储元素的值,指针域存储指向下一个元素的指针广义表的遍历算法前序遍历先访问广义表的头部元素,然后遍历子表,最后访问尾部元素广度优先遍历中序遍历使用队列实现广度优先遍历算法,从头部先遍历子表,然后访问头部元素,最后访元素开始遍历子表,直到遍历完整个广义问尾部元素表深度优先遍历后序遍历使用递归或栈实现深度优先遍历算法,从先遍历子表,然后访问尾部元素,最后访头部元素开始遍历子表,直到遍历完整个问头部元素广义表05CATALOGUE数组和广义表的应用在数据结构中的应用数组的应用数组是线性数据结构的一种,可以用来存储有序的元素集合数组常用于实现动态分配的线性表、栈、队列等数据结构在数据结构中的应用•数组的优点是存取速度快,但插入和删除操作效率较低在数据结构中的应用01020304广义表的应用广义表是一种扩展的线性表,广义表的优点是能够表示复杂广义表常用于表示层次结构或可以包含其他广义表作为元素的数据结构,但插入和删除操树形结构的数据作较为复杂在算法设计中的应用排序算法排序算法是算法设计中常见的一类问题,可以使用数组和广义表来实现常见的排序算法有冒泡排序、选择排序、插入排序等在算法设计中的应用•这些算法可以通过对数组或广义表进行操作来达到排序的目的在算法设计中的应用搜索算法搜索算法也是算法设计中常见的一类问题,可以使用数组和广义表来实现常见的搜索算法有顺序搜索、二分搜索等这些算法可以通过对数组或广义表进行操作来找到目标元素在实际问题中的应用数据库索引网络通信协议在数据库中,为了提高查询效率,通在网络通信中,协议是规范数据传输常会使用索引来组织数据和通信方式的规则索引可以使用数组或广义表来表示,网络协议可以使用数组或广义表来表通过特定的算法来加速查询速度示,通过特定的协议规则来实现数据的传输和管理THANKS感谢观看。