《数据结构》课程教学资源：第四章 数组与十字链表

雾章魏影与线

1

s4.1数组 ·数组是一种十分常用的结构 ·大多数程序设计语言都直接支持数组类型 数组的基本操作主要是元素定位 本节的主要内容是讨论数组的存贮映射方法

2 §4.1 数组 • 数组是一种十分常用的结构 • 大多数程序设计语言都直接支持数组类型 • 数组的基本操作主要是元素定位 • 本节的主要内容是讨论数组的存贮映射方法

§4.1.1数组的定义与运算 ·数组是由一组类型相同的数据元素构成,每个 数据元素称为一个数组元素(简称元素) ·每个元素受n个线性关系约東(n≥1),若它 在第1~第n个线性关系中的序号分别为i、 2……,则称它的下标为i1、i2……n,若该数 组的名为A,则记下标为i1、i2……,的元素为, 称该数组为n维数组

3 §4.1.1 数组的定义与运算 • 数组是由一组类型相同的数据元素构成，每个 数据元素称为一个数组元素（简称元素） • 每个元素受n 个线性关系约束（n≥1），若它 在第1～第n个线性关系中的序号分别为i 1、 i 2……in , 则称它的下标为i 1、i 2……in，若该数 组的名为A，则记下标为i 1、i 2……in ,的元素为， 称该数组为n维数组

§4.1.1数组的定义与运算 数组的另一个定义 数组定义为一个元素可直接按序号寻址的线性表 A=(A1,A2,…,An) 若A1是简单元素(不是数组),则A是一维数组;若A1是 (k-1)维数组,则A是k维数组 数组是从线性表的推广 而来

4 §4.1.1 数组的定义与运算 • 数组的另一个定义 • 数组定义为一个元素可直接按序号寻址的线性表 A=(A1 , A2 , …, Am ) 若Ai是简单元素（不是数组），则A是一维数组；若Ai是 （k-1)维数组，则A是k维数组。 数组是从线性表的推广 而来

§4.1.1数组的定义与运算 l1 13 i2i3-1 h1+12l3 i1+1,3 图一个3维数组的元素关系示意

5 §4.1.1 数组的定义与运算 图 - 一个3维数组的元素关系示意 ai 1 i 2 i 3 +1 1 2 3 ai i +1,i 1 2 3 ai +1,i i 1 2 3 ai i i 1 2 3 ai −1,i i 1 2 3 ai i −1,i ai 1 i 2 i 3 −1

§4.1.1数组的定义与运算 维数组的操作 给定一组下标,读出相应的元素 给定一组下标,修改相应的元素

6 §4.1.1 数组的定义与运算 • 一维数组的操作 – 给定一组下标，读出相应的元素。 – 给定一组下标，修改相应的元素

§4.1.2数组的存储结构与寻址问题 要求元素的存储地址能根据它的下标(即逻辑关系) 计算出来,一般只采用顺序存储结构 偏移地址(相府地址) 选定一个基准(参考)存贮单元,问题中所涉及的地址值均 以此参考单元为基准(为起点) 设i1、i2、…、in为某n维数组中的一个元素的下标,则用 Loc(i1,i2,…,in)表示此元素的相对地址 可以将多维数组影射为一维结构,然后运用顺序存储 方式

7 §4.1.2 数组的存储结构与寻址问题 • 要求元素的存储地址能根据它的下标（即逻辑关系） 计算出来，一般只采用顺序存储结构 • 偏移地址（相对地址） –选定一个基准（参考）存贮单元，问题中所涉及的地址值均 以此参考单元为基准（为起点） –设i1、i2、…、in为某n维数组中的一个元素的下标，则用 Loc(i1 , i2 , …, in )表示此元素的相对地址 • 可以将多维数组影射为一维结构，然后运用顺序存储 方式

§4.1.3一维数组的存贮与寻址 设一维数组为 A=( 0c1……n 则它的元素a的相对地址为 Loc(1)=i·c 若数组下标范围为闭区间[12h1]内的整数,即 A=(a h11+12…h1 则元素a的相对地址为 Loc(1)=(l-41)c

8 §4.1.3 一维数组的存贮与寻址 • 设一维数组为 A=(a0 , a1 , …, an ) 则它的元素ai的相对地址为 Loc(i)=i · c • 若数组下标范围为 闭区间[l 1 ,h1 ]内的整数，即 A=( ) 则元素ai的相对地址为 Loc(i)=(i-l 1 ) · c 1 1 1 , ,..., al al +1 ah

§4.1.4二维数组的存贮 二维数组的阵列形状 n A 1m2 mn 常用的映射方法有两种:按行与按列

9 §4.1.4 二维数组的存贮 • 二维数组的阵列形状 a11 a12 … a1n a21 a22 … a2n A = …… am1 am2 … amn • 常用的映射方法有两种：按行与按列

4.1.4二维数组的存贮 (一)按行存贮 先行后列:先存贮行号较小的元素,行号相同者,先 存贮列号较小者。 In 第1行元素 第2行元素 第m行元素

10 §4.1.4 二维数组的存贮 • (一) 按行存贮 • 先行后列：先存贮行号较小的元素，行号相同者，先 存贮列号较小者。 a11 a12 … a1n a21 a22 … a2n …… am1 am2 … amn ────── ─────── ────── 第1行元素 第2行元素 第m行元素