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

《“数据结构”专接本复习纲要(2)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、“数据结构”专接本复习纲要2006.1第二章数组结构一、数组概念1、什么是数组数组是连续的、有限的（数目有限的）、有序的（数目有顺序性）同种元素的集合。2、数组的两个特性（1）数组中元素间的地址是连续的。（请与链表对比）（2）数组中所有元素的数据类型是相同的。（请与结构类型对比）二、数组中元素地址的计算1、一维数组中元素地址的计算假设有如下一维数组A，数组的首地址为a，每个元素占据的空间大小是d。（1）数组元素的下标从0开始d0123……i-1ii+1……a则下标是i的元素的地址是L(A[i])=a+(i-0)*d在A[i]之前有A[0]–A[i-1]共i个元素。“数据结构“专接本复习纲要

2、第2章数组第13页共13页（2）数组元素的下标从1开始d1234……i-1ii+1……a则下标是i的元素的地址是L(A[i])=a+(i-1)*d在A[i]之前有A[1]–A[i-1]共i-1个元素。（3）数组元素的下标从j开始dj+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个

3、字节，数组A的起始地址是50，则A[5]的地址是_____________。2、二维数组中元素地址的计算数组中的元素是存放在一片连续的存储空间中，所以二维数组中的元素也要“依次”放入空间中。二维数组中的元素放入连续存储空间中的“依次次序”有两种：“行优先（以行为主）”和“列优先（以列为主）”。“数据结构“专接本复习纲要第2章数组第13页共13页所谓“行优先”的次序是指按行由小到大的次序先后依次把各行元素放入，同一行中按列由小到大的顺序存放。所谓“列优先”的次序是指按列由小到大的次序先后依次把各列元素放入，同一列中按行由小到大的顺序存放。假设有如下二维数组A，数组的首地址为a，每个元素占据的

4、空间大小为d，二维数组有m行、n列。（1）以“行优先”次序存放，数组元素的下标从0，0开始01j-1jn-10**…**…*1**…**…*……………i-1**…**…*i**…**…*……………m-1**…**…*则计算元素A[i][j]的地址可以考虑如下在A[i][j]之前已存入的整行有第0行到第i-1行共（i-0）行，每行的元素个数是n，则在A[i][j]之前已存入的整行元素个数有(i-0)*n个。在A[i][j]所在的i行中，在A[i][j]之前已存入的元素个数有第0列到第j-1列共(j-0)个。所以，总的说来，按行优先的次序，在A[i][j]之前已存入的元素个数有(i-0)*n+

5、(j-0)个。“数据结构“专接本复习纲要第2章数组第13页共13页而每个元素占d个字节，首地址是a。所以,元素A[i][j]的地址是L(A[i][j])=a+((i-0)*n+(j-0))*d（2）以“行优先”次序存放，数组元素的下标从1，1开始L(A[i][j])=a+((i-1)*n+(j-1))*d请自己推导（3）以“列优先”次序存放，数组元素的下标从0，0开始01j-1jn-10**…**…*1**…**…*………..…i-1**…**…*i**…**…*……………m-1**…**…*L(A[i][j])=a+((j-0)*m+(i-0))*d请自己推导（4）以“列优先”次序存放，

6、数组元素的下标从1，1开始L(A[i][j])=a+((j-1)*m+(i-1))*d请自己推导练习，一个二维数组A[1:3,1:5]，每个数组元素用4个字节,数组的起始地址是1000，若以行优先次序排列，A[3,1]的地址是______；若以列优先存储，A[3,1]的地址是_______；三、下三角矩阵和上三角矩阵1、什么是下三角矩阵和上三角矩阵“数据结构“专接本复习纲要第2章数组第13页共13页下三角矩阵是指对角线上方（行下标小于列下标的元素）的元素都是0的正方矩阵。而上三角矩阵是指对角线下方（行下标大于列下标的元素）的元素都是0的正方矩阵。2、下三角矩阵和上三角矩阵的存储矩阵在计算机

7、中可以用二维数组来表示。因为三角矩阵的对角线上方（下方）的元素为0，所以，在存储时，为了节省空间，0元素就不存了。这也是一种矩阵压缩存储的方式。和前面讨论的一般二维数组一样，存储三角矩阵时，也有“行优先”和“列优先”两种次序之分。3、下三角矩阵的元素地址计算设正方矩阵A的阶数为n。每个元素占d个字节空间。（1）“行优先”存储，元素下标从0，0开始0123j567890*1**i=7j=42***3****4*****5*