s->lchild=NULL; s->rchild=NULL;} rear++;
q[rear]=s;
if(rear==1) root=s; else
{if((s!=NULL)&&(q[front]!=NULL)) {if(rear%2==0) q[front]->lchild=s; else q[front]->rchild=s;} if(rear%2==1) front++; }
scanf(\}
return root; }
int BiTreeDepth(BiTree *T) {
int i,j; if(!T) return 0; if(T->lchild)
i=BiTreeDepth(T->lchild); else i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild); else j=0;
return i>j?(i+1):(j+1); }
void inorder(bitree* root) {bitree* p; p=root;
if(p!=NULL)
{inorder(p->lchild); printf(\inorder(p->rchild); }}
int leaf(BiTree *T)
21
{ if(T) {
inorder(T->lchild); visit(T->data ); if(T->rchild==NULL) NUM++;
inorder(T->rchild ,visit); }
return NUM;}
int InOrderTraverse(BiTree *T) { if(T) {
InOrderTraverse(T->lchild, visit); visit(T->data );
if(T->rchild==NULL) NUM++;
InOrderTraverse(T->rchild ,visit); } }
int result(BTNode *b) {
int n1,n2;
if(b->data>='0'&&b->data<='9') return (b->data-'0'); n1=result(b->lchild); n2=result(b->rchild); switch(b->data) {
case'+':
b->data=n1+n2;break; case'-':
b->data=n1-n2;break; case'*':
b->data=n1*n2;break; case'/':
b->data=n1/n2;break; }
return b->data;
22
}
void main()
{bitree *root;int n,m,k; root=create(); n=leaf(root);
printf(\k= BiTreeDepth(root);
printf(\printf(\inorder(root); printf(\
m=InOrderTraverse(root);
printf(\
截图：
八．实验小结
通过这次实验熟悉二叉树的存储结构的特性，以及如何应用树结构解
决具体问题,这次实验关键在于对二叉树的遍历算法的实现，还有对于二叉链表上的二叉树的基本运算，我认为是本次实验中最困难的地方，所以要想做好这个实验，事先一定要熟悉掌握二叉树的各种操作。
23
南昌大学实验报告
---（四）图的应用
学生姓名： 学 号： 专业班级：
实验类型：□ 验证 □ 综合 ■ 设计 □ 创新 实验日期： 2010-5-7 实验成绩：
一、实验目的
图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。
二、问题描述
给出一张某公园的导游图，游客通过终端询问可知： a) 从某一景点到另一个景点的最短路径。
b) 游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回
到出口。
三、实验要求
1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。 2、为游客提供图中任意景点相关信息的查询；
（1）、为游客提供任意两个景点之间的一条最短的简单路径。 （2）、为游客选择最佳游览路径。
四、实验环境
PC微机
DOS操作系统或 Windows 操作系统
Turbo C 程序集成环境或 Visual C++ 程序集成环境
五、程序代码及结果
/* 用邻接表表示图的拓扑排序算法*/ #include
24
#define FALSE 0
typedef struct EdgeNode EdgeNode; typedef struct EdgeNode * PEdgeNode; typedef struct EdgeNode * EdgeList; struct EdgeNode { int endvex;
/* 相邻顶点字段 */
PEdgeNode nextedge; /* 链字段 */ };
typedef struct {
/*VexType vertex;*/ EdgeList edgelist; } VexNode;
typedef struct{ int n;
/* 图的顶点个数 */
/* 顶点信息 */ /* 边表头指针 */
/* 边表中的结点 */
/* 顶点表中的结点 */
VexNode vexs[MAXVEX]; } GraphList;
typedef struct {
int vexsno[MAXVEX];
/* 顶点在顶点表中的下标值 */
/* 顶点信息 */
/*VexType vexs[MAXVEX];*/ } Topo;
/* 求出图中所有顶点的入度 */ /* 方法是搜索整个邻接表 */
void findInDegree(GraphList* g, int *inDegree){ int i; PEdgeNode p; for (i = 0; i < g->n; i++) inDegree[i] = 0; for (i = 0; i < g->n; i++){
25