“数据结构”专接本复习纲要(2).pdf

“数据结构”专接本复习纲要2006.1

第二章数组结构

一、数组概念

1、什么是数组

数组是连续的、有限的（数目有限的）、有序的（数目有

顺序性）同种元素的集合。

2、数组的两个特性

（1）数组中元素间的地址是连续的。（请与链表对比）

（2）数组中所有元素的数据类型是相同的。（请与结构类型对

比）

二、数组中元素地址的计算

1、一维数组中元素地址的计算

假设有如下一维数组A，数组的首地址为a，每个元素占

据的空间大小是d。

（1）数组元素的下标从0开始d

0123……i-1ii+1……

a则下标是i的元素的地址是

L(A[i])=a+(i-0)*d

在A[i]之前有A[0]–A[i-1]共i个元素。

“数据结构“专接本复习纲要第2章数组第1页共13页

（2）数组元素的下标从1开始d

1234……i-1ii+1……

a则下标是i的元素的地址是

L(A[i])=a+(i-1)*d

在A[i]之前有A[1]–A[i-1]共i-1个元素。

（3）数组元素的下标从j开始d

j+0j+1j+2j+3……i-1ii+1……

a则下标是i的元素的地址是

L(A[i])=a+(i-j)*d

在A[i]之前有A[j]–A[i-1]共i-j个元素。

可以这样来理解，从A[0]到A[j-1]有j个元素，而从A[0]

到A[i-1]有i个元素，两者之差就是从A[j]到A[i-1]的元素

个数。

例，用C语言定义一个一维数组intA[10];若每个数组

元素占用2个字节，数组A的起始地址是50，则A[5]的地址

是_____________。

2、二维数组中元素地址的计算

数组中的元素是存放在一片连续的存储空间中，所以二维

数组中的元素也要“依次”放入空间中。

二维数组中的元素放入连续存储空间中的“依次次序”有

两种：“行优先（以行为主）”和“列优先（以列为主）”。

“数据结构“专接本复习纲要第2章数组第2页共13页

所谓“行优先”的次序是指按行由小到大的次序先后依次

把各行元素放入，同一行中按列由小到大的顺序存放。

所谓“列优先”的次序是指按列由小到大的次序先后依次

把各列元素放入，同一列中按行由小到大的顺序存放。

假设有如下二维数组A，数组的首地址为a，每个元素占据的

空间大小为d，二维数组有m行、n列。

（1）以“行优先”次序存放，数组元素的下标从0，0开始

01j-1jn-1

0**…**…*

1**…**…*

……………

i-1**…**…*

i**…*