耿国华 - 数据结构 - C语言的描述 - 课后大部分习题答案[1]

C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1;

for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 {

while(A.data[pa].i

while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 {

if(A.data[pa].j==B.data[pb].j) {

ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if

else if(A.data[pa].j>B.data[pb].j) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

}//while

while(A.data[pa]==x) //插入A 中剩余的元素(第x 行) {

C.data[pc].i=x;

C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; }

while(B.data[pb]==x) //插入B 中剩余的元素(第x 行) {

C.data[pc].i=x;

C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc;

}//TSMatrix_Add 实习题

若矩阵A m×n中的某个元素a ij 是第i行中的最小值,同时又是第j列中的最大值,则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵,试编写算法求出矩阵中的所有马鞍点。

void Get_Saddle(int A[m][n])//求矩阵A 中的马鞍点 {

for(i=0;i

for(min=A[i][0],j=0;j

if(A[i][j]

if(A[i][j]==min) //判断这个(些)最小值是否鞍点 {

for(flag=1,k=0;k

printf(\ } }//for

}//Get_Saddle

第 6 章 树和二叉树

6.12 已知二叉树按照二叉链表方式存储,编写算法,计算二叉树中叶子结点的数目。 int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {

if(!T) return 0; //空树没有叶子

else if(!T->lchild&&!T->rchild) return 1; //叶子结点

else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上 右子树的叶子数 }//LeafCount_BiTree

6.13 编写递归算法:对于二叉树中每一个元素值为x的结点,删去以它为根的子树,并释放相应的空间。

void Del_Sub_x(Bitree T,int x)//删除所有以元素x 为根的子树 {

if(T->data==x) Del_Sub(T); //删除该子树 else {

if(T->lchild) Del_Sub_x(T->lchild,x);

if(T->rchild) Del_Sub_x(T->rchild,x); //在左右子树中继续查找 }//else

}//Del_Sub_x

void Del_Sub(Bitree T)//删除子树T {

if(T->lchild) Del_Sub(T->lchild); if(T->rchild) Del_Sub(T->rchild); free(T); }//Del_Sub

6.14 分别写函数完成:在先序线索二叉树T中,查找给定结点*p在先序序列中的后继。在后序线索二叉树T中,查找给定结点*p在后序序列中的前驱。

BTNode *PreOrder_Next(BTNode *p)//在先序后继线索二叉树中查找结点p 的先 序后继,并返回指针 {

if(p->lchild) return p->lchild; else return p->rchild; }//PreOrder_Next

分析:总觉得不会这么简单.是不是哪儿理解错了?

Bitree PostOrder_Next(Bitree p)//在后序后继线索二叉树中查找结点p 的后序后继,并返回指针 {

if(p->rtag) return p->rchild; //p 有后继线索 else if(!p->parent) return NULL; //p 是根结点

else if(p==p->parent->rchild) return p->parent; //p 是右孩子 else if(p==p->parent->lchild&&p->parent->tag) return p->parent; //p 是左孩子且双亲没有右孩子 else //p 是左孩子且双亲有右孩子 {

q=p->parent->rchild; while(!q->ltag||!q->rtag) {

if(!q->ltag) q=q->lchild; else q=q->rchild;

} //从p 的双亲的右孩子向下走到底 return q; }//else

}//PostOrder_Next

6.16 编写算法,对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 int LeafCount_CSTree(CSTree T)//求孩子兄弟链表表示的树T 的叶子数目 {

if(!T->firstchild) return 1; //叶子结点 else {

count=0;

for(child=T->firstchild;child;child=child->nextsib) count+=LeafCount_CSTree(child); return count; //各子树的叶子数之和 }

}//LeafCount_CSTree

6.17 对以孩子-兄弟链表表示的树编写计算树的深度的算法。

int GetDepth_CSTree(CSTree T)//求孩子兄弟链表表示的树T 的深度 {

if(!T) return 0; //空树 else {

for(maxd=0,p=T->firstchild;p;p=p->nextsib)

if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度 return maxd+1; }

}//GetDepth_CSTree

6.18 已知二叉树按照二叉链表方式存储,利用栈的基本操作写出后序遍历非递归的算法。 typedef struct {

BTNode* ptr;

enum {0,1,2} mark;

} PMType; //有mark 域的结点指针类型

void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈 {

PMType a;

InitStack(S); //S 的元素为PMType 类型 Push (S,{T,0}); //根结点入栈 while(!StackEmpty(S)) {

Pop(S,a);

switch(a.mark) {

case 0:

Push(S,{a.ptr,1}); //修改mark 域

if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树 break; case 1:

Push(S,{a.ptr,2}); //修改mark 域

if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树 break; case 2:

visit(a.ptr); //访问结点,返回 }

}//while

}//PostOrder_Stack

分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark 域,mark=0 表示刚刚访问此结点,mark=1 表示左子树处理结束返回,mark=2 表示右子树处理结束返回.每次根据栈顶元素的mark 域值决定做何种动作.

6.21 已知二叉树按照二叉链表方式存储,利用栈的基本操作写出先序遍历非递归形式的算法。

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 {

InitStack(S);

Push(S,T); //根指针进栈 while(!StackEmpty(S)) {

while(Gettop(S,p)&&p) {

visit(p->data); push(S,p->lchild); } // 向左走到尽头 pop(S,p);

if(!StackEmpty(S)) {

pop(S,p);

push(S,p->rchild); // 向右一步 }

}//while

}//PreOrder_Nonrecursive

6.24 二叉树按照二叉链表方式存储,编写算法,将二叉树左右子树进行交换。 void Bitree_Revolute(Bitree T)//交换所有结点的左右子树 {

T->lchild<->T->rchild; //交换左右子树 if(T->lchild) Bitree_Revolute(T->lchild);

if(T->rchild) Bitree_Revolute(T->rchild); //左右子树再分别交换各自的左右子树 }//Bitree_Revolute

第7 章 图

7.5 编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的 信息建立邻接表 {

InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\

if(a<0) return ERROR; //边数不能为负 G.arcnum=a;

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4