else
{
OutAtom(A->un.ptr.hp,layer+1,Out2);
OutAtom(A->un.ptr.tp,layer,Out2);
}
}
5.18⑤试设计一个算法，将数组A中的元素
A[0..n-1]循环右移k位，并要求只用一个元素
大小的附加存储，元素移动或交换次数为O(n)。
要求实现以下函数：
n++; p++;
}
}
if(k>A.tu)
while(n<=B.tu)
{
C.data[p].e=B.data[n].e;
C.data[p].i=B.data[n].i;
C.data[p].j=B.data[n].j;
n++;p++;
printf("%d B ",B.data[n].e);
}
else
while(k<=A.tu)
/*求二元组矩阵的元素A[i][j]的值e */
稀疏矩阵的二元组顺序表＋行起始向量的类型T2SMatrix的定义：
typedef struct{
int j;
ElemType e;
}TwoTuples;
typedef struct{
TwoTuples data[MAXSIZE];
int cpot[MAXROW]; //这个向量存储每一行在二元组中的起始位置
int mu,nu,tu;
} T2SMatrix; //二元组矩阵类型
Status GetElem(T2SMatrix M, int i, int j, ElemType &e)
/*求二元组矩阵的元素A[i][j]的值e */
{
int k;
if(i>M.mu||j>M.nu||i<1||j<1)return ERROR;
{
int j=0;
OLink p;
for(j=0;j<=M.mu;j++)
{
if(M.rhead[j])
for(p=M.rhead[j];p;p=p->right)
Out3(p->i,p->j,p->e);
}
}
5.30③试按表头、表尾的分析方法重写求广义表
的深度的递归算法。
要求实现以下函数：
int GListDepth(GList ls);
} ptr;
}un;
} *GList;
void OutAtom(GList A, int layer, void(*Out2)(char, int))
/*递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次*/
{
if(A==NULL)return;
if(A->tag==ATOM)Out2(A->un.atom,layer);
/*用函数Out3,依次以三元组格式输出十字链表表示的矩阵*/
稀疏矩阵的十字链表存储表示:
typedef struct OLNode {
int i,j; //该非零元的行和列下标
ElemType e; //非零元素值
OLNode *right,*down; //该非零元所在行表和列表的后继链域
}OLNode, *OLink;
{
C.data[p].e=A.data[k].e;
C.data[p].i=A.data[k].i;
C.data[p].j=A.data[k].j;
k++;p++;
printf("%d A ",C.data[p].e);
}
C.mu=A.mu;
C.nu=A.nu;
C.tu=p-1;
return TRUE;
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode *hp, *tp;
} ptr;
}un;
} *GList;
Status Equal(GList A, GList B)
} ptr;
}un;
} *GList;
int GListDepth(GList ls)
/* Return the depth of list */
{
int max=0,dep;
GList p;
if(ls==NULL)return 1;
if(ls->tag==ATOM)return 0;
for(p=ls;p;p=p->un.ptr.tp)
void Rotate(Array1D &a, int n, int k);
一维数组类型Array1D的定义：
typedef ElemType Array1D[MAXLEN];
void Rotate(Array1D &a, int n, int k)
/* a[n] contains the elements, */
while(k<=A.tu&&n<=B.tu)
{
if(A.data[k].i==B.data[n].i&&A.data[k].j==B.data[n].j)
{
ce=A.data[k].e+B.data[n].e;
if(ce)
{
C.data[p].i=A.data[k].i;
C.data[p].j=A.data[k].j;
if(Equal(A->un.ptr.hp,B->un.ptr.hp)&&Equal(A->un.ptr.tp,B->un.ptr.tp))
return TRUE;
return FALSE;
}
5.33④试编写递归算法，输出广义表中所有原子项
及其所在层次。
要求实现以下函数：
void OutAtom(GList A, int layer, void(*Out2)(char, int));
for(k=M.cpot[i];k<M.cpot[i+1];k++)
{
if(M.data[k].j==j)
{
e=M.data[k].e;
return OK;
}
}
e=0;
return OK;
}
5.26③试编写一个以三元组形式输出用十字链表
表示的稀疏矩阵中非零元素及其下标的算法。
要求实现以下函数：
void OutCSM(CrossList M, void(*Out3)(int, int, int));
数据结构作业系统_第五章答案
5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。
试写出矩阵相加的算法，另设三元组表C存放结果矩阵。
要求实现以下函数：
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);
/*三元组表示的稀疏矩阵加法: C=A+B */
稀疏矩阵的三元组顺序表类型TSMatrix的定义：
typedef struct {
OLink *rhead,*chead; //行和列链表头指针向量基址
int mu,nu,tu; //稀疏矩阵的行数、列数和非零元个数
}CrossList;
void OutCSM(CrossList M, void(*Out3)(int, int, int))
/*用函数Out3,依次以三元组格式输出十字链表表示的矩阵*/
int mu,nu,tu; //矩阵的行数、列数和非零元个数
}TSMatrix;
Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)
/*三元组表示的稀疏矩阵加法: C=A+B */
{
int k=1,n=1,p=1;
ElemType ce;
if(A.mu!=B.mu||A.nu!=B.nu)return ERROR;
#define MAXSIZE 20 //非零元个数的最大值
typedef struct {
int i,j; //行下标,列下标
ElemType e; //非零元素值
}Triple;
typedef struct {
Triple data[MAXSIZE+1]; //非零元三元组表,data[0]未用
/* Return the depth of list */
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode *hp, *tp;
/* rotate them right circlely by k sits */
{
int i,j,l,p,temp;
for(i=1;i<=k;i++)
if(k%i==0&&n%i==0)p=i;
for(i=0;i<p;i++)
{
j=i;
l=(j+k)%n;
while(l!=i)
{
if(j==i){temp=a[l];a[l]=a[j];a[j]=temp;}