} }
printf(\
}
printf(“\\n 打回车键，返回。“); ch=getch(); }
void creatMatrix(Crosslist *M) { int m,n,t,row,col,i,j;
Etype va; OLnode *p,*q,*s;
/* 输入矩阵的总行数、总列数、非零元素总个数 */ printf(\ for(i=1; i<=m;i++) M->rh[i]=NULL; for(j=1; j<=n;j++) M->ch[j]=NULL;
M->mu=m; M->nu=n; M->tu=t; /* 建立成空十字链表 */ /* 以下为非零元素的逐一输入和插入 */ for(i=1;i<=M->tu;i++)
{ printf(\ p=(OLnode *)malloc(sizeof(OLnode)); p->i=row; p->j=col; p->e=va; /* 在第row行上链接 */ q=M->rh[row]; s=q;
while(q!=NULL && q->j < col){ s=q; q=q->right;} p->right=q;
if(q==M->rh[row])M->rh[row]=p; else s->right=p; /* 在第col列上链接 */ q=M->ch[col];
while(q && q->i < row){s=q;q=q->down;} p->down=q;
if(q==M->ch[col]) M->ch[col]=p; else s->down=p; } /* for */
}/* creatMatrix */
三、实习题
1. 编写用“三元组表”存储（参见教科书）稀疏矩阵，进行矩阵处理的程序。（1）
矩阵转置 （2）矩阵加
2. 上机调试上面给出的十字链表的程序，在此基础上增加查找功能：
（1） 给定一个数值 X ，查找确定它的位置（行下标i、列下标j）；
36
（2） 给定一个矩阵元素aij位置(i,j)，求出它的数据值是什么？ 3. 实现迷宫求解程序。
37
实习六 树与二叉树
一、实习目的
1. 熟练掌握二叉树在二叉链表存储结构中的常用遍历方法：先序递归遍历、中序递归和非递归遍历、后序递归遍历。了解二叉树的按层遍历、先序非递归遍历及后序递归遍历。
2. 用树解决实际问题，如哈夫曼编码等。
加深对“数据结构+算法=程序”的理解和认识，提高编写较复杂程序的能力。 二、实例
1. 二叉树的建立和遍历。
为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。有一种方法利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：序号 数据元素。结合下图的二叉树数的输入据顺序应该是：1 1，2 2，3 3，4 4，6 5，7 6，11 7，12 8，13 9。 另一种算法是教材P58～P59介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织时先序的顺序，但是另有特点，当某结点的某孩子为空时以数据0来充当，也要输入。结合下图的二叉树数的输入据顺序应该是：
1 2 4 0 0 0 3 5 0 7 0 0 6 8 0 0 9 0 0。
若当前数据不为0，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。
下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用，请认真理解然后模仿练习。
/* 二叉树的建立与遍历 */ # include
typedef int Etype;
typedef struct BiTNode /* 树结点结构 */ { Etype data;
struct BiTNode *lch,*rch; }BiTNode; /* 函数原形声明 */ BiTNode *creat_bt1(); BiTNode *creat_bt2() void inorder(BiTNode *p); void numb(BiTNode *p);
BiTNode *t; int n,n0,n1,n2,; /* 主函数 */ main()
38
1 2 4 5 7 8 3 6 9 { char ch; int k;
do { printf(\
printf(\建立二叉树方法1 \ printf(\建立二叉树方法2\ printf(\中序递归遍历二叉树\
printf(\计算树中结点个数\ printf(\结束程序运行\
printf(\
printf(\请输入您的选择 (1,2,3,4,5,6)\ switch(k)
{ case 1:t=creat_bt1( );break; /* 调用性质5建立二叉树算法 */ case 2:t=creat_bt2( );break; /* 调用递归建立二叉树算法 */ case 3: { inorder(t); /* 调用中序遍历 */
printf(\打回车键，继续。“); ch=getch(); } break; case 4:{ n=0;n0=0 ; n1=0; n2=0; /* 全局变量置0 */ numb(t);
printf(“\\n 二叉树结点总数 n=%d”,n);
printf(“\\n 二叉树叶子结点数 n0=%d”,n0); printf(“\\n 度为1的结点数 n1=%d”,n1); printf(“\\n 度为2的结点数 n2=%d”,n2);
printf(\打回车键，继续。“); ch=getch(); } break; case 5: exit(0);
} /* switch */
printf(\ }while(k>=1 && k<5);
printf(\再见！\
printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */
/* 利用二叉树性质5 ，借助一维数组V 建立二叉树 */ BiTNode *creat_bt1()
{ BiTNode *t,*p,*v[20]; int i; Etype e; /* 输入结点的序号i 、结点的数据e */
printf(\
while(i!=0 && e!=0) /* 当 i ,e都为0时，结束循环 */ { p=(BiTNode *)malloc(sizeof(BiTNode)); p->data=e; p->lch=NULL; p->rch=NULL; v[i]=p;
39
if (i==1) t=p; /* 序号为1的结点是根 */ else{ j=i/2;
if(i%2==0) v[j]->lch=p; /* 序号为偶数，做左孩子*/ else v[j]->rch=p; /* 序号为奇数，做右孩子*/ }
printf(\ }
return(t);
} /* creat_bt1 */
/* 模仿先序递归遍历方法，建立二叉树 */ BiTNode *creat_bt2() { BiTNode *t;
printf(\
if(e==0) t=NULL; /* 对于0值，不分配新结点 */ else { t=(BiTNode *)malloc(sizeof(BiTNode)); t->data=e; t->lch=creat_bt2(); /* 左孩子获得新指针值 */
t->rch=creat_bt2(); /* 右孩子获得新指针值 */ }
return(t);
} /* creat_bt2 */
/* 中序递归遍历二叉树 */ void inorder(BiTNode *p)
{ if (p) { inorder(p->lch); printf(\
inorder(p->rch); }
} /* inorder */
/* 利用中序递归遍历二叉树的方法，计算树中结点个数 */
/* 读者可以试着运用先序或后序递归遍历二叉树方法重新编写这一段函数 */ void inorder(BiTNode *p)
{ if (p) { inorder(p->lch);
{ printf(\ n++; if(p->lch==NULL && p->lch==NULL) n0++; if((p->lch==NULL && p->lch!=NULL)|| (p->lch!=NULL && p->lch==NULL) n1++; if(p->lch!=NULL && p->lch!=NULL) n2++; } /* 把访问的功能扩大了 */
40