数据结构上机作业1-5章(10)

e=A.data[s]; return OK; }

return ERROR; } */

5.26③ 试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。 要求实现以下函数：

void OutCSM(CrossList M);

/* 以三元组格式输出十字链表表示的矩阵 */ 稀疏矩阵的十字链表存储表示: typedef struct OLNode {

int i,j; // 该非零元的行和列下标 ElemType e; // 非零元素值

OLNode *right,*down; // 该非零元所在行表和列表的后继链域 }OLNode, *OLink; typedef struct {

OLink *rhead,*chead; // 行和列链表头指针向量基址 int mu,nu,tu; // 稀疏矩阵的行数、列数和非零元个数 }CrossList;

void OutCSM(CrossList M, void(*Out3)(int, int, int))

/* 用函数Out3,依次以三元组格式输出十字链表表示的矩阵 */ { int i; OLink p;

for(i=0;i<=M.mu;i++) {

if(M.rhead[i])

for(p=M.rhead[i];p;p=p->right) Out3(i,p->j,p->e); } }

5.30③ 试按表头、表尾的分析方法重写求广义表的深度的递归算法。 要求实现以下函数： int GListDepth(GList ls); /* Return the depth of list */ 广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union {

char atom; struct {

GLNode *hp, *tp; } ptr; }un; } *GList;

int GListDepth(GList ls) /* Return the depth of list */ { int m,n;

if(ls==NULL) return 1;

else if(ls->tag==0) return 0;

m=GListDepth(ls->un.ptr.hp)+1; n=GListDepth(ls->un.ptr.tp); if(m>n) return m; else return n; } /*

{ int m,n;

if(ls==NULL) return 1;

else if(ls->tag==0) return 0; m=GListDepth(ls->ptr.hp)+1; n=GListDepth(ls->ptr.tp); return m>n?m:n; } */

5.33④ 试编写递归算法，输出广义表中所有原子项及其所在层次。 广义表类型GList的定义：

typedef enum {ATOM,LIST} ElemTag; typedef struct GLNode{ ElemTag tag; union {

char atom; struct {

GLNode *hp, *tp; } ptr; }un; } *GList;

void OutAtom(GList A, int layer, void(*Out2)(char, int))

/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */ {

if(!A) return ;

if(!A->tag) Out2(A->un.atom,layer); else {

OutAtom(A->un.ptr.hp,layer+1,Out2); OutAtom(A->un.ptr.tp,layer,Out2); } }