4-1设有一个二维数组AⅧm,假设A[OI0]存放位置在64410,4[2[2]存放位置在67610,每个元素 占一个空间,问A[3IB3o存放在什么位置?脚注(0表示用10进制表示 【解答】 设数组元素A[[存放在起始地址为Loc(i,j)的存储单元中 ∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676 ∴n=(676-2-644)/2=15 Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692 4-2设有一个nXn的对称矩阵A,如图(a)所示。为了节约存储,可以只存对角线及对角线以上的元素, 或者只存对角线或对角线以下的元素。前者称为上三角矩阵,后者称为下三角矩阵。我们把它们按行 存放于一个一维数组B中,如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问: (1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素? (2)若在一维数组B中从0号位置开始存放,则如图(a)所示的对称矩阵中的任一元素a在只存上 三角部分的情形下(图(b)应存于一维数组的什么下标位置?给出计算公式 (3)若在一维数组B中从0号位置开始存放,则如图(a所示的对称矩阵中的任一元素a在只存下 三角部分的情形下(图(c)应存于一维数组的什么下标位置?给出计算公式。 【解答】 (1)数组B共有n+(n-1)+……+1=n*(n+1)/2个元素。 011 12:*:: in 21a22: anni Int an2…an (a)对称矩阵 (b)只存上三角部分 (c)只存下三角部分 a1102|…a1na2|…az ang11a21a22…m1n|an1…ann|ann (2)只存上三角部分时,若i≤j,则数组元素A[前面有i-1行(1~i-1,第0行第0列不算), 第1行有n个元素,第2行有n-1个元素,………,第i-1行有n-i+2个元素。在第i行中,从对角线算 起,第j号元素排在第j-i+1个元素位置(从1开始),因此,数组元素A[[在数组B中的存放位置 为 n+(n-1)+(n-2)+…+(n-1+2)+J-+1 =(2n-1)*(i-1)/2+ 若i>j,数组元素A[在数组B中没有存放,可以找它的对称元素A[I[。在 数组B的第(2n-)*-1)/2+i位置中找到
4-1 设有一个二维数组 A[m][n]，假设 A[0][0]存放位置在 644(10)，A[2][2]存放位置在 676(10)，每个元素 占一个空间，问 A[3][3](10)存放在什么位置？脚注(10)表示用 10 进制表示。 【解答】 设数组元素 A[i][j]存放在起始地址为 Loc ( i, j ) 的存储单元中。 ∵ Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n + 2 = 676. ∴ n = ( 676 - 2 - 644 ) / 2 = 15 ∴ Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692. 4-2 设有一个 nn 的对称矩阵 A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素， 或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行 存放于一个一维数组 B 中，如图(b)和图(c)所示。并称之为对称矩阵 A 的压缩存储方式。试问： (1) 存放对称矩阵 A 上三角部分或下三角部分的一维数组 B 有多少元素？ (2) 若在一维数组 B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 aij 在只存上 三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。 (3) 若在一维数组 B 中从 0 号位置开始存放，则如图(a)所示的对称矩阵中的任一元素 aij 在只存下 三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。 【解答】 (1) 数组 B 共有 n + ( n-1 ) + + 1= n * ( n+1 ) / 2 个元素。 (2) 只存上三角部分时，若 i j，则数组元素 A[i][j]前面有 i-1 行（1i-1，第 0 行第 0 列不算)， 第 1 行有 n 个元素，第 2 行有 n-1 个元素，，第 i-1 行有 n-i+2 个元素。在第 i 行中，从对角线算 起，第 j 号元素排在第 j-i+1 个元素位置（从 1 开始），因此，数组元素 A[i][j]在数组 B 中的存放位置 为 n + (n-1) + (n-2) + + (n-i+2) + j-i+1 = (2n-i+2) * (i-1) / 2 + j-i+1 = (2n-i) * (i-1) / 2 + j 若 i > j，数组元素 A[i][j]在数组 B 中没有存放，可以找它的对称元素 A[j][i]。在 数组 B 的第 (2n-j) * (j-1) / 2 + i 位置中找到
如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素A][j在数组B中的存放位 置可以改为 当i≤j时 1)*1/2+j 1)*i/2+ 当i>j时,=(2n-j-1)*j/2+ (3)只存下三角部分时,若i≥j,则数组元素A[前面有i-1行(1~i-1,第0行第0列不算), 第1行有1个元素,第2行有2个元素,……,第i-1行有i-1个元素。在第i行中,第j号元素排在 第j个元素位置,因此,数组元素A[i][]在数组B中的存放位置为 1+2+ +(1-1)+j=(1-1)*i/2+j 若i<j,数组元素A[订[]在数组B中没有存放,可以找它的对称元素A[[。在 数组B的第(j-1)*j/2+i位置中找到 如果第0行第0列也计入,数组B从0号位置开始存放,则数组元素A[[在数组B中的存放位 置可以改为 当i≥j时,=i*(i+1)/2+j 当i<j时,=j*j+1) 4-3设A和B均为下三角矩阵,每一个都有n行。因此在下三角区域中各有m(n+1)2个元素。另设有 个二维数组C,它有n行m+1列。试设计一个方案,将两个矩阵A和B中的下三角区域元素存放于 同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中,B的下三角区域中的元素转 置后存放于C的上三角区域中。并给出计算A的矩阵元素a和B的矩阵元素b在C中的存放位置下 标的公式 【解答】 ,o 6, B 6 b b b b b H-21 b 11 计算公式 B[]= ∫cU/+当≥/时 C[iLj+1]l当i<j时
如果第 0 行第 0 列也计入，数组 B 从 0 号位置开始存放，则数组元素 A[i][j]在数组 B 中的存放位 置可以改为 当 i j 时，= (2n-i+1) * i / 2 + j - i = ( 2n - i - 1 ) * i / 2 + j 当 i > j 时，= (2n - j - 1) * j / 2 + i (3) 只存下三角部分时，若 i j，则数组元素 A[i][j]前面有 i-1 行（1i-1，第 0 行第 0 列不算)， 第 1 行有 1 个元素，第 2 行有 2 个元素，，第 i-1 行有 i-1 个元素。在第 i 行中，第 j 号元素排在 第 j 个元素位置，因此，数组元素 A[i][j]在数组 B 中的存放位置为 1 + 2 + + (i-1) + j = ( i-1)*i / 2 + j 若 i < j，数组元素 A[i][j]在数组 B 中没有存放，可以找它的对称元素 A[j][i]。在 数组 B 的第 (j-1)*j / 2 + i 位置中找到。 如果第 0 行第 0 列也计入，数组 B 从 0 号位置开始存放，则数组元素 A[i][j]在数组 B 中的存放位 置可以改为 当 i j 时，= i*(i+1) / 2 + j 当 i < j 时，= j*(j+1) / 2 + i 4-3 设 A 和 B 均为下三角矩阵，每一个都有 n 行。因此在下三角区域中各有 n(n+1)/2 个元素。另设有 一个二维数组 C，它有 n 行 n+1 列。试设计一个方案，将两个矩阵 A 和 B 中的下三角区域元素存放于 同一个 C 中。要求将 A 的下三角区域中的元素存放于 C 的下三角区域中，B 的下三角区域中的元素转 置后存放于 C 的上三角区域中。并给出计算 A 的矩阵元素 aij 和 B 的矩阵元素 bij 在 C 中的存放位置下 标的公式。 【解答】 计算公式 = −10 −11 −1 −1 10 11 00 an an an n a a a A = −10 −11 −1 −1 10 11 00 bn bn bn n b b b B = − − − − − − − − − − − − − 10 11 12 1 1 1 1 20 21 22 22 12 10 11 11 21 11 00 00 10 20 10 n n n n n n n n n n n n n a a a a b a a a b b a a b b b a b b b b C + + = 当 时 当 时 [ ][ 1], [ ][ 1], [ ][ ] C i j i j C j i i j B i j
作业答案 4-4针对稀疏矩阵的三种表示方法,写出两个矩阵的求和算法。即若A,B,C为三个矩阵,求 AUUJ= CULI 当i≥j时 luJI I< 三元组顺序表 三元组顺序表的C表示如下: #define MAXSIze 12500 typedef struct nt 1, J //非零元的行列下标 ElemType e typedef //三元组表 ta[0]未用 ITSMatrix 算法: 注意:在稀疏矩阵的三元组顺序表表示中,a_Data域中的非零元排列是有序的,即以行序为主序 排列,在一行中,数据元素按列序排列。因此整个算法可以集中到如下问题:在已知A和B阵的某 行的起始位置的情况下,如何得到C的该行的内容 如图 kC KA 其中kA,kB,kC分别为矩阵A,B,C的 a Data域的当前位置。kX到kx’的位置是矩阵X中第 行的非零元元素 两个矩阵的加法运算转化为第i行元素的加法。而第i行中第j元素的加法可以描述为:
作业答案： 4-4 针对稀疏矩阵的三种表示方法，写出两个矩阵的求和算法。即若 A, B, C 为三个矩阵，求 C = A + B. 1． 三元组顺序表 三元组顺序表的 C 表示如下： #define MAXSIZE 12500 typedef struct { int i, j; //非零元的行列下标 ElemType e; }Triple; typedef union { Triple a_Data[MAXSIZE + 1]; //三元组表，a_Data[0]未用 int mu, nu, tu; }TSMatrix; 算法： 注意：在稀疏矩阵的三元组顺序表表示中，a_Data 域中的非零元排列是有序的，即以行序为主序 排列，在一行中，数据元素按列序排列。因此整个算法可以集中到如下问题：在已知 A 和 B 阵的某一 行的起始位置的情况下，如何得到 C 的该行的内容。 如图示： C: kC kC’ A: kA kA’ B: kB kB’ 其中 kA，kB，kC 分别为矩阵 A,B,C 的 a_Data 域的当前位置。kX 到 kX’的位置是矩阵 X 中第 i 行的非零元元素。 两个矩阵的加法运算转化为第 i 行元素的加法。而第 i 行中第 j 元素的加法可以描述为： = 当 时 当 时 [ ][ ], [ ][ ], [ ][ ] C j i i j C i j i j A i j
取A和B的当前元素,若列号相同,则相加,若和非零,把结果放在C中,kA,kB,kC 分别移到下一个位置:若和为零,则kA,kB移到下一个位置 否则,若A的列号小于B,则C的元素等于A的元素,kA,kC分别移到下一个位置 否则,则C的元素等于B的元素,kB,kC分别移到下一个位置 程序: /以知A和B,求矩阵C=A+B,其中矩阵采用三元组顺序表表示 status MatrixAdd TSMatrix( TSMatrix A, TSMatrix B, TSMatrix &C) /若矩阵A和B的行列不同,返回错误! f(A mu B mu A nu =B nu return //矩阵C的行列赋值 /初始化 for 0;i<C.mu;i++)/处理每一行 ∥/每列元素,从kA和kB开始,依次比较A和B中元素 while( A a DatalkAl i&&B. a data[kB].i=i)/在一行内 if(A. a data[kA].j=B.a_Data[kB].j)//A和B元素在同一列 C a Data[kC] e =A. a Data[kA]e+B a Data[kB]e if(C. a Data[kC]!=0)//非零,作为C中的一项存在 C C a Data[kC].j=A. a Data[kA].j: KC++ KA++ B++
1． 取 A 和 B 的当前元素，若列号相同，则相加，若和非零，把结果放在 C 中，kA，kB，kC 分别移到下一个位置；若和为零，则 kA，kB 移到下一个位置； 2． 否则，若 A 的列号小于 B，则 C 的元素等于 A 的元素，kA，kC 分别移到下一个位置； 3． 否则，则 C 的元素等于 B 的元素，kB，kC 分别移到下一个位置； 程序： // 以知 A 和 B，求矩阵 C = A + B，其中矩阵采用三元组顺序表表示 status MatrixAdd_TSMatrix( TSMatrix A, TSMatrix B, TSMatrix &C) { // 若矩阵 A 和 B 的行列不同，返回错误！ if( A.mu != B.mu || A.nu != B.nu ) { return ERROR; } // 矩阵 C 的行列赋值 C.mu = A.mu; C.nu = B.nu; kA = kB = kC = 1; // 初始化 for ( i = 0; i < C.mu; i++) // 处理每一行 { // 每列元素，从 kA 和 kB 开始，依次比较 A 和 B 中元素。 while( A.a_Data[kA].i == i && B.a_Data[kB].i == i ) //在一行内 { if( A.a_Data[kA].j == B.a_Data[kB].j ) //A 和 B 元素在同一列 { C.a_Data[kC].e = A.a_Data[kA].e + B.a_Data[kB].e; if( C.a_Data[kC] != 0) //非零，作为 C 中的一项存在 { C.a_Data[kC].i = i; C.a_Data[kC].j = A.a_Data[kA].j; kC++; } kA++; kB++; }
else if(A.a_ DatalkA].j<B.a_Data[k].j)//A元素所在列小 C a Data[kC].i=i C a Data[kC].j=A. a Data[kA].j C a Data[kC]e =A. a Data[kA]e KA++ KC++ //B元素所在列小,kB指针移动 C a DatalkC C a Data[kC].j=B a Data[kB].j: C a Data lkC] e =B a Data[kB]e KB++ KC++ 1//while //若同一行内A和B元素个数不同,则需要把A或B的剩余元素拷贝到C中 hile (A a DatalkA]i ==i /A元素多 C a Data lkC] C a Data[kC].j= A. a Data[kA]. j: C a Data [kC] e =A. a Data[kA]e kA++ while( B a Data[kB].i = i) ∥/B元素多 C a Data[kC].i=i C a Data[kC].j=B a Data[kb]. j C a Data [kC] e =B a Data[kB]e 1//for
else if ( A.a_Data[kA].j < B.a_Data[kB].j )// A 元素所在列小， { C.a_Data[kC].i = i; C.a_Data[kC].j = A.a_Data[kA].j; C.a_Data[kC].e = A.a_Data[kA].e; kA++; kC++; } else // B 元素所在列小，kB 指针移动 { C.a_Data[kC].i = i; C.a_Data[kC].j = B.a_Data[kB].j; C.a_Data[kC].e = B.a_Data[kB].e; kB++; kC++; } }//while // 若同一行内 A 和 B 元素个数不同，则需要把 A 或 B 的剩余元素拷贝到 C 中。 while ( A.a_Data[kA].i == i ) // A 元素多 { C.a_Data[kC].i = i; C.a_Data[kC].j = A.a_Data[kA].j; C.a_Data[kC].e = A.a_Data[kA].e; kA++; kC++: } while ( B.a_Data[kB].i == i ) // B 元素多 { C.a_Data[kC].i = i; C.a_Data[kC].j = B.a_Data[kB].j; C.a_Data[kC].e = B.a_Data[kB].e; kB++; kC++: } } // for
//kC指向下一个可用位置! return OK 1// MatrixAdd TSMatrix 2.行逻辑联接顺序表 C表示 #define maXsize 12500 #define maxrc 100 typedef struct int 1, J //非零元的行列下标 ElemType e I Triple typedef struct Triple a Data [MAXSIZE +1] int rpos [MAXRC+1 Int mu, nu, tu. FRLSMatrix 算法同1。只是要更新该表示法中的rpos数组 十字链表 typedef struct OLNode int 1, J ElemType e Struct OLNode *pRight, *pDo JOLNode, eli typedef struct 0link* pLEad,* pLEad;//行和列链表头指针向量所在数组的基地址 int mu, nu, t I CrossList
C.tu = kC - 1; //kC 指向下一个可用位置！ return OK; }// MatrixAdd_TSMatrix; 2．行逻辑联接顺序表 C 表示： #define MAXSIZE 12500 #define MAXRC 100 typedef struct { int i, j; //非零元的行列下标 ElemType e; }Triple; typedef struct { Triple a_Data[MAXSIZE + 1]; int rpos[MAXRC + 1]; Int mu, nu, tu; }RLSMatrix; 算法同 1。只是要更新该表示法中的 rpos 数组。 3．十字链表 typedef struct OLNode { int i, j; ElemType e; Struct OLNode *pRight, *pDown; }OLNode, *Olink; typedef struct { Olink *pRHead, *pCHead; //行和列链表头指针向量所在数组的基地址； int mu, nu, tu; }CrossList;
算法:具体的算法可以见课本第105页。在本算法中,首先把A和B按行序处理,在处理完行结 点后,再通过遍历处理列链表 /以知A和B,求矩阵C=A+B,其中矩阵采用十字链表表示 status MatrixAdd CrossList( CrossList A, CrossList B, CrossList C /若矩阵A和B的行列不同,返回错误! B.m‖|A.m!=B.nu) return ERROR //矩阵C的行列赋值 B //设置指针pa,pb和pc,分别指向A,B和C的当前行结点 pa =A. pRHead [i] pb =B. pRHead[i] pC =C. pRHead [i] while(pa&&pb)//矩阵A和B的行链表 if(pa>j=pb->j)//同一列结点 0 //申请一个结点 pc->pRight =(OLink)malloc(sizeof (OLNode)) if(! pc->pRight return ERROR //分配内存失败
算法：具体的算法可以见课本第 105 页。在本算法中，首先把 A 和 B 按行序处理，在处理完行结 点后，再通过遍历处理列链表。 // 以知 A 和 B，求矩阵 C = A + B，其中矩阵采用十字链表表示 status MatrixAdd_CrossList( CrossList A, CrossList B, CrossList C) { // 若矩阵 A 和 B 的行列不同，返回错误！ if( A.mu != B.mu || A.nu != B.nu ) { return ERROR; } // 矩阵 C 的行列赋值 C.mu = A.mu; C.nu = B.nu; C.tu = 0; for(i = 1; i j == pb->j ) // 同一列结点 { if( pa->e + pb->e != 0 ) { // 申请一个结点 pc->pRight = (OLink)malloc(sizeof(OLNode)); if(!pc->pRight) { return ERROR; //分配内存失败 } pc = pc->pRight;
//增加一个结点 pc-> pDown=NUL;//把暂时没有使用的指针设置为NULL pc→> pRight=NULL; >pRig pb pb->pRight else if(pa-jj)/把A矩阵中的元素加入到链表中 //申请一个结点 pc->pRight =(OLink)malloc(sizeof(OLNode)) (l pc->pRight) return ERROR /分配内存失败 pc=pc→> pRight pc->pown=NUL;//把暂时没有使用的指针设置为NUL pc->pRight NULL C tu++ //增加一个结点 >pRight: //把B矩阵中的元素加入到链表中 /申请一个结点 pC->pRight =(OLink)malloc(sizeof (OLNode)) if( pc->pRight) return error /分配内存失败
pc->i = i; pc->j = pa->j; pc->e = pa->e + pb->e; C.tu++; //增加一个结点 pc->pDown = NULL; //把暂时没有使用的指针设置为 NULL pc->pRight = NULL; } pa = pa->pRight; pb = pb->pRight; } else if ( pa->j j) //把 A 矩阵中的元素加入到链表中 { // 申请一个结点 pc->pRight = (OLink)malloc(sizeof(OLNode)); if(!pc->pRight) { return ERROR; //分配内存失败 } pc = pc->pRight; pc->i = i; pc->j = pa->j; pc->e = pa->e; pc->pDown = NULL; //把暂时没有使用的指针设置为 NULL pc->pRight = NULL; C.tu++; //增加一个结点 pa = pa->pRight; } else //把 B 矩阵中的元素加入到链表中 { // 申请一个结点 pc->pRight = (OLink)malloc(sizeof(OLNode)); if(!pc->pRight) { return ERROR; //分配内存失败 }
pc= pc->pRight pc->i =i pc->j= pb->j pc->pown=NUL;//把暂时没有使用的指针设置为NULL pc→> pRight=NULL C tu++ //增加一个结点 pb pb->pRight 1// while /pa非空。把A中的结点加入到C中 /申请一个结点 pC->pRight =(OLink)malloc(sizeof(oLNode)) return ERROR //分配内存失败 pc-> pDown=NULL;//把暂时没有使用的指针设置为NULL pc→> pRight=NULL; C. tu++ //增加一个结点 pa pa->pRight while( pb /申请一个结点 pC->pRight =(OLink)malloc(sizeof (OLNode)) return ErROR //分配内存失败
pc = pc->pRight; pc->i = i; pc->j = pb->j; pc->e = pb->e; pc->pDown = NULL; //把暂时没有使用的指针设置为 NULL pc->pRight = NULL; C.tu++; //增加一个结点 pb = pb->pRight; } }// while while( pa ) // pa 非空。把 A 中的结点加入到 C 中 { // 申请一个结点 pc->pRight = (OLink)malloc(sizeof(OLNode)); if(!pc->pRight) { return ERROR; //分配内存失败 } pc = pc->pRight; pc->i = i; pc->j = pa->j; pc->e = pa->e; pc->pDown = NULL; //把暂时没有使用的指针设置为 NULL pc->pRight = NULL; C.tu++; //增加一个结点 pa = pa->pRight; } while( pb ) { // 申请一个结点 pc->pRight = (OLink)malloc(sizeof(OLNode)); if(!pc->pRight) { return ERROR; //分配内存失败 }
pc pc->pRight pc->i =i c->j=pb-> Down=NULL;//把暂时没有使用的指针设置为NULL C→> pRight=NULL C tu++ //增加一个结点 pb=pb→> pRight 1//for //处理列链表 for(j=1;jjpRight //取下一个结点 1//while if(pa)//pa非空,说明pa-> 即该行中第j列有非零结点 //把该结点加入到列链表中 pc->pDown =pa pc pc->pDown }//if 1//for i 1//for j return OK MatrixAdd CrossList 4-5画出下列广义表的图形表示和它们的存储表示: (1)D(A(c),B(e),C(a,L(b,c,d)) (2)Jl(J2(J1,a,J3(J1),J3(J1) 【解答】(1)D(A(c),B(e),Ca,l(b,c,d) (2)J(J2J1,a,J3(J1),J3(J1)
pc = pc->pRight; pc->i = i; pc->j = pb->j; pc->e = pb->e; pc->pDown = NULL; //把暂时没有使用的指针设置为 NULL pc->pRight = NULL; C.tu++; //增加一个结点 pb = pb->pRight; } }// for //处理列链表 for(j = 1; j j pRight; //取下一个结点 }//while if ( pa ) // pa 非空，说明 pa->j = j，即该行中第 j 列有非零结点 { //把该结点加入到列链表中 pc->pDown = pa; pc = pc->pDown; }//if }// for i }// for j return OK; }MatrixAdd_CrossList 4-5 画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1)) 【解答】(1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1))