数据结构习题解答：习题4解答

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 设有一个n(n的对称矩阵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行（1(i-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[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行（1(i-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中的存放位置下标的公式。
【解答】
计算公式
作业答案：
4-4 针对稀疏矩阵的三种表示方法，写出两个矩阵的求和算法。即若A,B,C为三个矩阵，求C = A + B.
三元组顺序表三元组顺序表的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元素的加法可以描述为：
取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的行列不同，返回错误！
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_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
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的行列不同，返回错误！
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 <= C.mu,i++) //针对每一行
{
//设置指针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 ) // 同一列结点
{
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; //把暂时没有使用的指针设置为NULL
pc->pRight = NULL;
}
pa = pa->pRight;
pb = pb->pRight;
}
else if ( pa->j < pb->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->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;
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 <= C.nu; j++) //对于每一列
{
pc = C.pCHead[j]; //当前列链表的头指针
//依次在每一行中，寻找列号为j的结点，若有，加入链表中。
for( i = 1; i <= C.mu; i++)
{
pa = C.pRHead[i]; //第i行的头结点
while( pa && pa->j < j )
{
pa = pa->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))
4-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是访问标记,未访问为0
GenListNode* 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 <iostream.h>
void GenList,,traverse ( GenListNode * ls ) { //私有函数,广义表的遍历算法
if ( ls != NULL ) {
ls->mark = 1;
if ( ls->utype == 0 ) cout << ls->value.listname << ‘(’; //表头结点
else if ( ls->utype == 1 ) { //原子结点
cout << ls->value.atom;
if ( ls->tlink != NULL ) cout << ‘,’;
}
else if ( ls->utype == 2 ) { //子表结点
if ( ls->value.hlink->mark == 0 ) traverse( ls->value.hlink ); //向表头搜索
else cout << ls->value.hlink->value.listname;
if ( ls->tlink != NULL ) cout << ‘,’;
}
traverse ( ls->tlink ); //向表尾搜索
}
else cout << ‘)’;
}
对上图所示的广义表进行遍历，得到的遍历结果为A(C(E(x,y),a),D(E,e) )。
利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。
#include <iostream.h>
#include,stack.h”
void GenList,,traverse ( GenListNode *ls ) {
Stack <GenListNode<Type> *> 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 << ls->value.hlink->value.listname; //该子表已访问过,仅输出表名
if ( ls->tlink != NULL ) { cout << ‘,’; ls = ls->tlink; }
}
}
else {
if ( ls->utype == 0 ) cout << ls->value.listname << ‘(’; //表头结点
else if ( ls->utype == 1 ) { //原子结点
cout << ls->value.atom;
if ( ls->tlink != NULL ) cout << ‘,’;
}
if ( ls->tlink == NULL ) { //子表访问完,子表结束处理
cout >> ‘)’;
if ( st.IsEmpty( ) == 0 ) { //栈不空
ls = st.GetTop ( ); st.Pop ( ); //退栈
if ( ls != NULL ) cout << ‘,’;
else cout << ‘)’;
}
}
else ls = ls->tlink; //向表尾搜索
}
}
}
(4) 广义表建立操作的实现
#include <iostream.h>
#include <ctype.h>
#include,stack.h”
const int maxSubListNum = 20; //最大子表个数
GenList,,GenList ( char& value ) {
Stack <GenListNode* > st (maxSubListNum); //用于建表时记忆回退地址
SeqList <char> Name (maxSubListNum); //记忆建立过的表名
SeqList <GenListNode * > Pointr (maxSubListNum); //记忆对应表头指针
GenListNode * p,q,r; Type ch; int m = 0,ad,br; //m为已建表计数,br用于对消括号
cout <<,广义表停止输入标志数据value,,; cin >> value;
cout <<,开始输入广义表数据,如A(C(E( x,y ),a ),D(E(x,y),e) )”
cin >> ch; first = q = new GenListNode ( 0,ch ); //建立整个表的表头结点
if ( ch != value ) { Name.Insert (ch,m); Pointr.Insert (q,m); m++; } //记录刚建立的表头结点
else return 1; //否则建立空表,返回1
cin >> ch; if ( ch == ‘(’ ) st.Push ( q ); //接着应是‘(’,进栈
cin >> ch;
while ( ch != value ) { //逐个结点加入
switch ( ch ) {
case ‘(’, p = new GenListNode <Type> ( q ); //建立子表结点,p->hlink = q
r = st.GetTop( ); st.Pop( ); r->tlink = p; //子表结点插在前一结点r之后
st.Push( p ); st.Push( q ); //子表结点及下一表头结点进栈
break;
case ‘)’, q->tlink = NULL; st.pop( ); //子表建成,封闭链,退到上层
if ( st.IsEmpty ( ) == 0 ) q = st.GetTop( ); //栈不空,取上层链子表结点
else return 0; //栈空,无上层链,算法结束
break;
case ‘,’, break;
default, ad = Name.Find (ch); //查找是否已建立,返回找到位置
if ( ad == -1 ) { //查不到,建新结点
p = q;
if ( isupper (ch) ) { //大写字母,建表头结点
q = new GenListNode ( 0,ch );
Name.Insert (ch,m); Pointr.Insert (q,m); m++;
}
else q = new GenListNode ( 1,ch ); //非大写字母,建原子结点
p->tlink = q; //链接
}
else { //查到,已加入此表
q = Pointr.Get (ad); p = new GenListNode (q); //建立子表结点,p->hlink = q
r = st.GetTop ( ); st.Pop ( ); r->tlink = p; st.Push (p); q = p;
br = 0; //准备对消括号
cin >> ch; if ( ch == ‘(’ ) br++; //若有左括号,br加1
while ( br == 0 ) { //br为0表示括号对消完,出循环
cin >> ch;
if ( ch == ‘(’ ) br++; else if ( ch == ‘)’ ) br--;
}
}
}
cin >> ch;
}
}