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

“数据结构”专接本复习纲要 2006.1第二章 数组结构一、数组概念1、什么是数组数组是连续的、有限的（数目有限的）、有序的（数目有顺序性）同种元素的集合。2、数组的两个特性（1）数组中元素间的地址是连续的。（请与链表对比）（2）数组中所有元素的数据类型是相同的。（请与结构类型对比）二、数组中元素地址的计算1、一维数组中元素地址的计算假设有如下一维数组A，数组的首地址为a，每个元素占据的空间大小是d。（1）数组元素的下标从0开始 d0 1 2 3 i-1 i i+1 a 则下标是i的元素的地址是 L(Ai)=a+(i-0)*d 在Ai之前有A0 Ai-1共i个元素。（2）数组元素的下标从1开始 d1 2 3 4 i-1 i i+1 a 则下标是i的元素的地址是 L(Ai)=a+(i-1)*d 在Ai之前有A1 Ai-1共i-1个元素。（3）数组元素的下标从j开始 d j+0j+1j+2 j+3 i-1 i i+1 a 则下标是i的元素的地址是 L(Ai)=a+(i-j)*d 在Ai之前有Aj Ai-1共i-j个元素。可以这样来理解，从A0到Aj-1有j个元素，而从A0到Ai-1有i个元素，两者之差就是从Aj到Ai-1的元素个数。例，用C语言定义一个一维数组int A10; 若每个数组元素占用2个字节，数组A的起始地址是50，则A5的地址是 _ 。2、二维数组中元素地址的计算数组中的元素是存放在一片连续的存储空间中，所以二维数组中的元素也要“依次”放入空间中。二维数组中的元素放入连续存储空间中的“依次次序”有两种：“行优先（以行为主）”和“列优先（以列为主）”。所谓“行优先”的次序是指按行由小到大的次序先后依次把各行元素放入，同一行中按列由小到大的顺序存放。所谓“列优先”的次序是指按列由小到大的次序先后依次把各列元素放入，同一列中按行由小到大的顺序存放。假设有如下二维数组A，数组的首地址为a，每个元素占据的空间大小为d，二维数组有m行、n列。（1）以“行优先”次序存放，数组元素的下标从0，0开始 0 1 j-1 j n-10 * * * * *1 * * * * * i-1 * * * * *i * * * * * m-1 * * * * *则计算元素Aij的地址可以考虑如下在Aij之前已存入的整行有第0行到第i-1行共 （i-0） 行，每行的元素个数是n，则在Aij之前已存入的整行元素个数有(i-0)*n个。在Aij所在的i行中，在Aij之前已存入的元素个数有第0列到第j-1列共 (j-0) 个。所以，总的说来，按行优先的次序，在Aij之前已存入的元素个数有 (i-0)*n+(j-0) 个。而每个元素占d个字节，首地址是a。所以,元素Aij的地址是 L(Aij)=a+(i-0)*n+(j-0)*d（2）以“行优先”次序存放，数组元素的下标从1，1开始 L(Aij)=a+(i-1)*n+(j-1)*d 请自己推导（3）以“列优先”次序存放，数组元素的下标从0，0开始 0 1 j-1 j n-10 * * * * *1 * * * * * . i-1 * * * * *i * * * * * m-1 * * * * * L(Aij)=a+(j-0)*m+(i-0)*d 请自己推导（4）以“列优先”次序存放，数组元素的下标从1，1开始 L(Aij)=a+(j-1)*m+(i-1)*d 请自己推导练习，一个二维数组A1:3,1:5，每个数组元素用4个字节,数组的起始地址是1000，若以行优先次序排列，A3,1的地址是 _ ；若以列优先存储，A3,1的地址是 _ ；三、下三角矩阵和上三角矩阵1、什么是下三角矩阵和上三角矩阵下三角矩阵是指对角线上方（行下标小于列下标的元素）的元素都是0的正方矩阵。而上三角矩阵是指对角线下方（行下标大于列下标的元素）的元素都是0的正方矩阵。2、下三角矩阵和上三角矩阵的存储矩阵在计算机中可以用二维数组来表示。因为三角矩阵的对角线上方（下方）的元素为0，所以，在存储时，为了节省空间，0元素就不存了。这也是一种矩阵压缩存储的方式。和前面讨论的一般二维数组一样，存储三角矩阵时，也有“行优先”和“列优先”两种次序之分。3、下三角矩阵的元素地址计算设正方矩阵A的阶数为n。每个元素占d个字节空间。（1）“行优先”存储，元素下标从0，0开始 0 1 2 3 j 5 6 7 8 9 0 *1 * * i=7 j=42 * * *3 * * * *4 * * * * *5 * * * * * *6 * * * * * * *i * * * * * * * *8 * * * * * * * * *9 * * * * * * * * * *在元素Aij之前已存入的“整行”有从0行到i-1行共(i-0)行。元素个数是 1+2+3+i=i*(i+1)/2个在元素Aij所在之i行，在Aij之前已存入 从0列到j-1列共（j-0）个元素。所以，总的说，在元素Aij之前按“行优先”已存入元素i*(i+1)/2+（j-0）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( i*(i+1)/2+（j-0）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第i*(i+1)/2+（j-0）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是i*(i+1)/2+（j-0）+1-1即存储在一维数组元素Di*(i+1)/2+（j-0）中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是i*(i+1)/2+（j-0）+1即存储在一维数组元素Di*(i+1)/2+（j-0）+1中。（2）“行优先”存储，元素下标从1，1开始 1 2 3 j 5 6 7 8 9 10 1 *2 * * i=7 j=43 * * *4 * * * *5 * * * * *6 * * * * * *i * * * * * * *8 * * * * * * * *9 * * * * * * * * *10 * * * * * * * * * *在元素Aij之前已存入的“整行”有从1行到i-1行共(i-1)行。元素个数是 1+2+3+(i-1)=i*(i-1)/2个在元素Aij所在之i行，在Aij之前已存入 从1列到j-1列共（j-1）个元素。所以，总的说，在元素Aij之前按“行优先”已存入元素i*(i-1)/2+（j-1）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( i*(i-1)/2+（j-1）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第i*(i-1)/2+（j-1）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是i*(i-1)/2+（j-1）+1-1即存储在一维数组元素Di*(i-1)/2+（j-1）中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是i*(i-1)/2+（j-1）+1即存储在一维数组元素Di*(i-1)/2+（j-0）中。练习，设有一个矩阵为5X5的下三角矩阵A，将其压缩存储在一维数组D，该数组的大小为 _ ，a42所对应的DK的K值为 _ 。（3）“列优先”存储，元素下标从0，0开始 0 1 2 3 j 5 6 7 8 9 0 *1 * * i=7 j=42 * * *3 * * * *4 * * * * *5 * * * * * *6 * * * * * * *i * * * * * * * *8 * * * * * * * * *9 * * * * * * * * * *在元素Aij之前已存入的“整列”有从0列到j-1列共(j-0)列。元素个数是 n+(n-1)+(n-2)+(n-(j-1)=j*(2*n-j+1)/2个在元素Aij所在之j列，在Aij之前已存入 从j行到i-1行共（i-j）个元素。所以，总的说，在元素Aij之前按“列优先”已存入元素j*(2*n-j+1)/2+（i-j）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( j*(2*n-j+1)/2+（i-j）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第j*(2*n-j+1)/2+（i-j）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是j*(2*n-j+1)/2+（i-j）+1-1即存储在一维数组元素Dj*(2*n-j+1)/2+（i-j）中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是j*(2*n-j+1)/2+（i-j）+1即存储在一维数组元素Dj*(2*n-j+1)/2+（i-j）+1中。（4）“列优先”存储，元素下标从1，1开始 1 2 3 j 5 6 7 8 9 1 *2 * * i=7 j=43 * * *4 * * * *5 * * * * *6 * * * * * *i * * * * * * *8 * * * * * * * *9 * * * * * * * * *10 * * * * * * * * * *在元素Aij之前已存入的“整列”有从1列到j-1列共(j-1)列。元素个数是 n+(n-1)+(n-2)+(n-(j-1)+1)=(j-1)*(2*n-j+2)/2个在元素Aij所在之j列，在Aij之前已存入 从j行到i-1行共（i-j）个元素。所以，总的说，在元素Aij之前按“列优先”已存入元素(j-1)*(2*n-j+2)/2+（i-j）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( (j-1)*(2*n-j+2)/2+（i-j）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第(j-1)*(2*n-j+2)/2+（i-j）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是(j-1)*(2*n-j+2)/2+1-1即存储在一维数组元素D(j-1)*(2*n-j+2)/2中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是(j-1)*(2*n-j+2)/2+1即存储在一维数组元素D(j-1)*(2*n-j+2)/2+1中。4、上三角矩阵的元素地址计算请自己推导。四、稀疏矩阵1、什么是稀疏矩阵稀疏矩阵是指矩阵中绝大多数元素值为0的那种矩阵。2、稀疏矩阵的存储由于稀疏矩阵中绝大多数元素值为0，所以在存储时，为了节省空间，只存储非0值的元素。这就是稀疏矩阵的压缩存储。用“三元组表”来表示稀疏矩阵是常用的稀疏矩阵压缩存储的方式。矩阵中的非0元素用元素的行号、列号和元素值这三项数据来表示，把这三项数据组成一个结构，而矩阵中诸非0元素用这种结构组成的线性表来表示，三元组表的名称由此而来。例，对于如下稀疏矩阵10 0 0 0 0 0 0 20 0 0 40 0 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 50 0 0 0 0 50 0 0 70在C语言中用三元组表可表示如下 row col valuea0 6 6 7a1 1 1 10a2 2 2 -20a3 2 5 40a4 3 3 30a5 5 4 50a6 6 3 -60a7 6 6 70其中A0.row 是稀疏矩阵的行数 A0.col 是稀疏矩阵的列数 A0.value 是稀疏矩阵中非0元素的个数五、矩阵乘积算法设有矩阵AMK BKN，矩阵A乘以矩阵B的积为矩阵CMN。则Cij的值为A的i行和B的j列对应位置元素积的和。for(Cij=0,t=0; tK; t+) Cij+=Ait*Btj;六、多项式的表示多项式表示的要点是多项式中的一个项可以用该项的系数和该项的幂指数来表示。若多项式中的每一项（包括系数为0的项）都表示，则可以不必使用幂指数。例如，按升幂的次序把各项的系数（包括系数0）线性排列，则某系数的后继系数所表示的项的幂指