设有一个二维数组A[m][n].doc

4-1 设有一个二维数组Amn，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(10)表示用10进制表示。【解答】设数组元素Aij存放在起始地址为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，则数组元素Aij前面有i-1行（1i-1，第0行第0列不算)，第1行有n个元素，第2行有n-1个元素，第i-1行有n-i+2个元素。在第i行中，从对角线算起，第j号元素排在第j-i+1个元素位置（从1开始），因此，数组元素Aij在数组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，数组元素Aij在数组B中没有存放，可以找它的对称元素Aji。在数组B的第 (2n-j) * (j-1) / 2 + i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素Aij在数组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，则数组元素Aij前面有i-1行（1i-1，第0行第0列不算)，第1行有1个元素，第2行有2个元素，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素Aij在数组B中的存放位置为1 + 2 + + (i-1) + j = ( i-1)*i / 2 + j若i j，数组元素Aij在数组B中没有存放，可以找它的对称元素Aji。在数组B的第 (j-1)*j / 2 + i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素Aij在数组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中的存放位置下标的公式。【解答】计算公式作业答案：4-4 针对稀疏矩阵的三种表示方法，写出两个矩阵的求和算法。即若A, B, C为三个矩阵，求C = A + B.1 三元组顺序表三元组顺序表的C表示如下：#define MAXSIZE 12500typedef structint i, j;/非零元的行列下标ElemType e;Triple;typedef unionTriple a_DataMAXSIZE + 1;/三元组表，a_Data0未用int mu, nu, tu;TSMatrix;算法：注意：在稀疏矩阵的三元组顺序表表示中，a_Data域中的非零元排列是有序的，即以行序为主序排列，在一行中，数据元素按列序排列。因此整个算法可以集中到如下问题：在已知A和B阵的某一行的起始位置的情况下，如何得到C的该行的内容。如图示：C: kC kCA: kA kAB: kB kB其中kA，kB，kC分别为矩阵A,B,C的a_Data域的当前位置。kX到kX的位置是矩阵X中第i行的非零元元素。两个矩阵的加法运算转化为第i行元素的加法。而第i行中第j元素的加法可以描述为：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_DatakA.i = i & B.a_DatakB.i = i )/在一行内if( A.a_DatakA.j = B.a_DatakB.j )/A和B元素在同一列C.a_DatakC.e = A.a_DatakA.e + B.a_DatakB.e;if( C.a_DatakC != 0)/非零，作为C中的一项存在C.a_DatakC.i = i;C.a_DatakC.j = A.a_DatakA.j;kC+;kA+;kB+;else if ( A.a_DatakA.j B.a_DatakB.j )/ A元素所在列小，C.a_DatakC.i = i;C.a_DatakC.j = A.a_DatakA.j;C.a_DatakC.e = A.a_DatakA.e;kA+;kC+;else/ B元素所在列小，kB指针移动C.a_DatakC.i = i;C.a_DatakC.j = B.a_DatakB.j;C.a_DatakC.e = B.a_DatakB.e;kB+;kC+;/while/ 若同一行内A和B元素个数不同，则需要把A或B的剩余元素拷贝到C中。while ( A.a_DatakA.i = i )/ A元素多C.a_DatakC.i = i;C.a_DatakC.j = A.a_DatakA.j;C.a_DatakC.e = A.a_DatakA.e;kA+;kC+:while ( B.a_DatakB.i = i )/ B元素多C.a_DatakC.i = i;C.a_DatakC.j = B.a_DatakB.j;C.a_DatakC.e = B.a_DatakB.e;kB+;kC+: / forC.tu = kC - 1;/kC指向下一个可用位置！return OK;/ MatrixAdd_TSMatrix;2行逻辑联接顺序表C表示：#define MAXSIZE 12500#define MAXRC 100typedef structint i, j;/非零元的行列下标ElemType e;Triple;typedef structTriple a_DataMAXSIZE + 1;int rposMAXRC + 1;Int mu, nu, tu;RLSMatrix;算法同1。只是要更新该表示法中的rpos数组。3十字链表typedef struct OLNodeint i, j;ElemType e;Struct OLNode *pRight, *pDown;OLNode, *Olink;typedef structOlink *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的行列不同，返回错误！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-i = i;pc-j = pa-j;pc-e = pa-e + pb-e;C.tu+;/增加一个结点pc-pDown = NULL;/把暂时没有使用的指针设置为NULLpc-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;/把暂时没有使用的指针设置为NULLpc-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-e = pb-e;pc-pDown = NULL;/把暂时没有使用的指针设置为NULLpc-pRight = NULL;C.tu+;/增加一个结点pb = pb-pRight;/ whilewhile( 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;/把暂时没有使用的指针设置为NULLpc-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;pc-j = pb-j;pc-e = pb-e;pc-pDown = NULL;/把暂时没有使用的指针设置为NULLpc-pRight = NULL;C.tu+;/增加一个结点pb = pb-pRight;/ for/处理列链表for(j = 1; j = C.nu; j+)/对于每一列pc = C.pCHeadj;/当前列链表的头指针/依次在每一行中，寻找列号为j的结点，若有，加入链表中。for( i = 1; i j pRight;/取下一个结点/whileif ( pa )/ pa非空，说明pa-j = j，即该行中第j列有非零结点/把该结点加入到列链表中pc-pDown = pa;pc = pc-pDown;/if/ for i/ for jreturn OK;MatrixAdd_CrossList4-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)J1J2J3CBADcbaeLadc0 J122J1A0 B B0 A 1 e 2 2 0 D D1 c 2 J21 a20 J220 C 2 1 a C0 J3J320 L 1 d1 c 1 b L4-6 利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：(1) L1(apple, pear, banana, orange)(2) L2(apple, pear), (banana, orange)(3) L3(apple), (pear), (banana), (orange)(4) L4(apple), (pear), (banana), orange)(5) L5(apple), pear), banana), orange)(6) L6(apple, (pear, (banana), orange) 【解答】(1) Head (Tail (Tail (L1) ) )(2) Head (Head (Tail (L2) ) )(3) Head (Head (Tail (Tail (Head (L3) ) ) ) )(4) Head (Head (Tail (Tail (L4) ) ) )(5) Head (Tail (Head(L5) ) )(6) Head (Head (Tail (Head (Tail (L6) ) ) ) ) 4-7 广义表具有可共享性，因此在遍历一个广义表时必需为每一个结点增加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。(1) 试定义该广义表的类结构；(2) 采用递归的算法对一个非递归的广义表进行遍历。(3) 试使用一个栈，实现一个非递归算法，对一个非递归广义表进行遍历。【解答】(1) 定义广义表的类结构为了简化广义表的操作，在广义表中只包含字符型原子结点，并用除大写字母外的字符表示数据，表头结点中存放用大写字母表示的表名。这样，广义表中结点类型三种：表头结点、原子结点和子表结点。class GenList;/GenList类的前视声明class GenListNode /广义表结点类定义friend class Genlist;private:int mark, utype;/ utype 0 / 1 / 2, mark是访问标记, 未访问为0GenListNode* tlink;/指向同一层下一结点的指针union /联合char listname;/ utype = 0, 表头结点情形：存放表名char atom;/ utype = 1, 存放原子结点的数据GenListNode* hlink;/ utype = 2, 存放指向子表的指针 value;public:GenListNode ( int tp, char info ) : mark (0), utype (tp), tlink (NULL) /表头或原子结点构造函数 if ( utype = 0 ) value.listname = info; else value.atom = info; GenListNode (GenListNode* hp ) /子表构造函数: mark (0), utype (2), value.hlink (hp) char Info ( GenListNode* elem ) /返回表元素elem的值 return ( utype = 0 ) ? elem-value.listname : elem-value.atom; ;class GenList /广义表类定义 private:GenListNode *first;/广义表头指针void traverse ( GenListNode * ls );/广义表遍历void Remove ( GenListNode* ls );/将以ls为表头结点的广义表结构释放public:Genlist ( char& value ); /构造函数, value是指定的停止建表标志数据GenList ( );/析构函数 void traverse ( );/遍历广义表(2) 广义表遍历的递归算法void GenList : traverse ( ) /共有函数 traverse ( first ); #include void GenList : traverse ( GenListNode * ls ) /私有函数, 广义表的遍历算法if ( ls != NULL ) ls-mark = 1; if ( ls-utype = 0 ) cout value.listname utype = 1 ) /原子结点cout value.atom;if ( ls-tlink != NULL ) cout utype = 2 ) /子表结点if ( ls-value.hlink-mark = 0 ) traverse( ls-value.hlink );/向表头搜索else cout value.hlink-value.listname;if ( ls-tlink != NULL ) cout tlink );/向表尾搜索 else cout ); 0 0 A0 2 0 2 0 1 a0 0 C0 1 e0 2 0 0 D 0 2 0 1 y0 1 x0 0 E对上图所示的广义表进行遍历，得到的遍历结果为A(C(E(x, y), a), D(E, e) )。(2) 利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。#include #include “stack.h”void GenList : traverse ( GenListNode *ls ) Stack GenListNode * st; while ( ls != NULL ) ls-mark = 1; if ( ls-utype = 2 ) /子表结点 if ( ls-value.hlink-mark = 0 )/该子表未访问过 st.Push ( ls-tlink ); ls = ls-value.hlink; /暂存下一结点地址, 访问子表 else cout value.hlink-value.listname; /该子表已访问过, 仅输出表名 if ( ls-tlink != NULL ) cout tlink; else if ( ls-utype = 0 ) cout value.listname utype = 1 ) /原子结点 cout value.atom; if ( ls-tlink != NULL ) cout tlink = NULL ) /子表访问完, 子表结束处理 cout ); if ( st.IsEmpty( ) = 0 ) /栈不空 ls = st.GetTop ( ); st.Pop ( );/退栈if ( ls != NULL ) cout ,; else cout tlink;/向表尾搜索 (4) 广义表建立操作的实现#include #include #include “stack.h”const int maxSubListNum = 20;/最大子表个数GenList : GenList ( char& value ) Stack st (maxSubListNum); /用于建表时记忆回退地址 SeqList Name (maxSubListNum);/记忆建立过的表名 SeqList Pointr (maxSubListNum);/记忆对应表头指针 GenListNode * p, q, r; Type ch; int m = 0, ad, br;/m为已建表计数, br用于对消括号 cout value; cout ch; first = q = new GenListNode ( 0, ch ); /建立整个表的表头结点 if ( ch != value ) Name.Insert (ch, m); Pointr.Insert (q, m); m+; /记录刚建立