《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第五章 数组与广义表》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 方风波 王巧莲 主编 黄鹤鸣 副主编 第五章 数组与广义表（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第五章 数组与广义表,第五章 数组与广义表,第五章 数组与线性表,知 识 点 数组的基本特点及寻址方式 线性数据结构的基本特征和基本运算 难 点 利用本章的基本知识设计有效的算法解决与线性相关的应用问题,第五章 数组与广义表,要 求 熟练掌握以下内容： 线性表的基本运算 了解以下内容： 线性表运算时间复杂性分析,第五章 数组与广义表,第二章目录 2.1 数组及其顺序存储结构 2.2 线性表及其运算 2.3 堆栈及其应用 2.4 队列及其应用 2.5 应用实例及分析 小 结 习题与练习,第五章 数组与广义表,5.1.1 数组,数组是由一些单元组成的，每个单元对应着一组下标值和一个数组元
2、素。 n维数组的每个单元对应n个下标值。 数组元素可以是基本数据类型，如整数型、实数型、字符型等，也可以是有多个数据项的一种结构。 同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量的存储单元，才能用下标来唯一的确定数组中的元素。,第五章 数组与广义表,5.1.2 数组的顺序存储结构,在计算机中，表示数组是采用一组连续的存储单元顺序地存储各数组元素。 可以用下标值随机的访问该数组的任意一个元素。 计算数组元素存储地址的公式称为寻址公式。 设数组为A，每个数组元素占s个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。,第五章 数组与广义表,1.
3、一维数组寻址公式,对于一维数组，若其下标的下界为LB，上界为UB，第一元素（其下标为LB）的地址为Loc(LB)，下标为i的数组元素Ai的地址为Loc(i)，则计算Loc(i)的寻址公式为： Loc(i)=Loc(LB)+(i-LB)*s 在C语言中，数组下标的下界为0，则数组中任意一元素Ai的寻址公式为： Loc(i)=Loc(0)+i*s 0in-1,第五章 数组与广义表,2. 二维数组寻址公式,在C语言中，采用矩阵元素以行为主存储，即同一行的元素连续存放，存储完一行再存储下一行。 设二维数组Amn，m、n分别表示数组的行和列，用Loc(i,j)表示数组元素Aij的地址，每个单元占用s个存
4、储单元，则寻址公式为： Loc(i,j)=Loc(0,0)+(i*n+j)*s 0im-1, 0jn-1,第五章 数组与广义表,定义一A23数组，对应的矩阵如下： 数组元素A12，其下标i=1，j=2，故它前面已经有i=1行，每行有3个元素，另外本行有j=2个元素，所以在元素A12之前，本数组已有5个元素。,第五章 数组与广义表,3. 三维数组寻址公式,三维数组Amnp可分解为p个m*n的二维数组。 按行为主存储的数组元素Aijk的寻址公式为： Locijk=Loc000+(i*n*p+j*p+k)*s 0im-1, 0jn-1，0pp-1 对于更多维的数组，数组元素在内存中的存储可以此类推。,返回,第五章 数组与广义表,习题与练习,一、基本知识题 1. 什么是数组？数组的主要特点是什么？ 2. 什么是线性表？线性表的主要运算有哪些？ A8，B47，C586，试计算它们的元素个数是多少？,
