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;