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. 编写用“三元组表”存储（参见教科书P98页）稀疏矩阵，进行矩阵处理的程序。
（1）矩阵转置 （2）矩阵加
2. 上机调试上面给出的十字链表的程序，在此基础上增加查找功能：
（1） 给定一个数值 X ，查找确定它的位置（行下标i、列下标j）； （2） 给定一个矩阵元素aij位置(i,j)，求出它的数据值是什么？ 3. 实现迷宫求解程序。
实习六 树与二叉树
一、实习目的
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，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。
下列程序中的统计二叉树结点的函数，是对二叉树遍历方法的应用，请认真理解然后模仿练习。
36
/* 二叉树的建立与遍历 */ 1 # include
3 2 # include
typedef int Etype; 4 6 5 typedef struct BiTNode /* 树结点结构 */ { Etype data; 9 7 8 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()
{ 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;
37
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;
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)
38
{ 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++; } /* 把访问的功能扩大了 */ inorder(p->rch); }
} /* inorder */。 三、实习题
1. 建立一棵二叉树，要求用先序非递归方法遍历二叉树。
2. 建立一棵二叉树，要求用“按层遍历”的方法遍历二叉树”的函数。 3. 给定一组值，建立一棵二叉树，求二叉数的树深。 4. 哈夫曼树问题。
利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）对于双工信道（即可以双向传输的信道），每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。 [基本要求]：
A：从终端读入字符集大小为n，及n个字符和n个权值，建立哈夫曼树，进行编码并且输出。（选做）并将它存于文件hfmtree中。
B：利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。
[测试数据] 用下表中给出的字符集和频度的实际统计数据建立哈夫曼树： B C D E F G H I J K L M N 字符 A 5 32 20 57 频度 64 13 22 32 103 21 15 47 57 1 P Q R S T U V W X Y Z 字符 O 空格 18 1 16 1 168 频度 63 15 1 48 51 80 23 8 并实现以下报文的译码和输出：“THIS PROGRAM IS MY FAVORITE”。
39
实习七 图
一、实习目的
熟悉图的两种常用的存储结构，以及在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。进一步掌握递归算法的设计方法。
关于各种典型著名的复杂算法，在上机实习方面不做基本要求。更适合于安排大型课程设计。 二、实例
1. 图的邻接矩阵存储（数组表示）、简单输出。
本题的目的是给出一个无向图数组表示的简单启示，在此基础上稍加改动可以实现网（边上带权值的图）的邻接矩阵表示。 # include
typedef int VexType;
typedef VexType Mgraph[MAX][MAX]; /* Mgraph是二维数组类型标识符 */ /* 函数原形声明 */
void creat_mg(Mgraph G); void out_mg(Mgraph G);
Mgraph G1; /* G1是邻接矩阵的二维数组名 */ int n,e,v0; /* 主函数 */ main()
{ creat_mg(G1); out_mg(G1); }/* main */
/* 建立邻接矩阵 */ void creat_mg(Mgraph G) { int i,j,k;
printf(“\\n n,e=?”); scanf(“%d%d”, &n,&e); /* 输入顶点数n，边数e */ for(i=1; i<=n;i++)
for(j=1;j<=n;j++) G[i][j]=0;
/* 如果是网，G[i][j]=0该为G[i][j]=32767（无穷）*/ for(k=1;k<=e;k++) /* 组织边数的循环 */ { printf(“\\n vi,vj=?”);
scanf(“%d%d”, &i,&j); /* 输入一条边的两个顶点编号i,j */
G[i][j]=1; G[j][i]=1; /* 无向图的邻接矩阵是对称矩阵 */ /* 如果是网，还要输入边的权值w，再让G[i][j]=w */ }
40