数据结构 教学课件 作者 方风波 王巧莲 主编 黄鹤鸣 副主编第五章 数组与广义表.ppt

《数据结构 教学课件 作者 方风波 王巧莲 主编 黄鹤鸣 副主编第五章 数组与广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第五章数组与广义表第五章数组与线性表知识点数组的基本特点及寻址方式线性数据结构的基本特征和基本运算难点利用本章的基本知识设计有效的算法解决与线性相关的应用问题第五章数组与广义表要求熟练掌握以下内容：线性表的基本运算了解以下内容：线性表运算时间复杂性分析第五章数组与广义表第二章目录2.1数组及其顺序存储结构2.2线性表及其运算2.3堆栈及其应用2.4队列及其应用2.5应用实例及分析小结习题与练习第五章数组与广义表5.1.1数组数组是由一些单元组成的，每个单元对应着一组下标值和一个数组元素。n维数组的每个单元对应n个下标值。数组元素可以是基本数据类

2、型，如整数型、实数型、字符型等，也可以是有多个数据项的一种结构。同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量的存储单元，才能用下标来唯一的确定数组中的元素。第五章数组与广义表5.1.2数组的顺序存储结构在计算机中，表示数组是采用一组连续的存储单元顺序地存储各数组元素。可以用下标值随机的访问该数组的任意一个元素。计算数组元素存储地址的公式称为寻址公式。设数组为A，每个数组元素占s个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。第五章数组与广义表1.一维数组寻址公式对于一维数组，若其下标的下界为LB

3、，上界为UB，第一元素（其下标为LB）的地址为Loc(LB)，下标为i的数组元素A[i]的地址为Loc(i)，则计算Loc(i)的寻址公式为：Loc(i)=Loc(LB)+(i-LB)*s在C语言中，数组下标的下界为0，则数组中任意一元素A[i]的寻址公式为：Loc(i)=Loc(0)+i*s0≤i≤n-1第五章数组与广义表2.二维数组寻址公式在C语言中，采用矩阵元素以行为主存储，即同一行的元素连续存放，存储完一行再存储下一行。设二维数组A[m][n]，m、n分别表示数组的行和列，用Loc(i,j)表示数组元素A[i][j]的地址，每个单元占用s个存储

4、单元，则寻址公式为：Loc(i,j)=Loc(0,0)+(i*n+j)*s0

5、0