数据结构实验题参考答案

while(have==2 && temp.arrive<=finish){

/*下一位客户的到达时间在当前客户处理结束之前*/

EnQueue(&front,&rear,temp);/* 暂存变量中的客户信息进队*/ have=fscanf(fp, \ }

clock=finish; /* 时钟推进到当前客户办理结束时间*/ }while(have==2 || front!=NULL);

printf(\结果：业务员等待时间%d\\n客户平均等待时间%f\\n\ (double)wait/count);

printf(\模拟总时间：%d，\\n客户人数：%d,\\n总等待时间：%d\\n\count,wait); getch(); }/*main_end*/’ 【测试数据】

设数据装在一个数据文件data.dat中，内容为：10 6 13 8 显示结果为：enter file name:data.dat enter file name:data.dat

结果：业务员等待时间10 客户平均等待时间25.500000 模拟总时间：72， 客户人数：2, 总等待时间：51 【说明】

在计算程序中，程序按模拟环境中的事件出同顺序逐一处理事件：当一个事件结束时，下一个事件隔一段时间才发生，则程序逻辑的模拟时钟立即推进到下一事件的发生时间；如一个事件还未处理结束之前，另有其他事件等待处理，则这些事件就应依次排队等候处理。

3． 二叉树的的应用：设计一个表示家谱的二叉树

要求：采用一棵二叉树表示一逐步形成家谱关系，对于给定的父亲显示所有的儿子。

由于家谱为树形，但不是一棵二叉树，所以在存储时要转换成二叉树的形式。规定：一个父亲结点的左子树表示母亲结点，母亲结点的右子树表示他们的所有儿子，例如，图1是一个用二叉树表示的家谱图，与之对应的传统树形图家谱图如图2所示。这样就将家谱树转换成二叉树了，而二叉树的操作是容易实现的。 张德、陈氏 张德 陈氏

张文 张文、刘氏 张武、王氏

刘氏 张武

张兵 王氏

张兵、李氏 张强 张华

李氏 张强 张华 图2 一个家谱树 图1 二叉树表示的家谱图 ［Ｃ源程序］

#include #include

#include #define MaxWidth 40 #define MaxSize 30

typedef struct treenode {

char name[10];

struct treenode *left,*right; } *BTree;

BTree findfather(BTree p,char xm[]) {

BTree bt;

if(p==NULL) return(NULL); else {

if(strcmp(p->name,xm)==0) return(p); else {

bt=findfather(p->left,xm); if(bt!=NULL) return(bt);

else return(findfather(p->right,xm)); } } }

BTree creatree() {

int n,m,i,contin=1,first=1; char xm[10];

BTree btree,s,t,p;

printf(\建立一个家谱二叉树（以空格结尾)：\\n\ while(contin) {

if(first==1) {

btree=(BTree)malloc(sizeof(struct treenode)); printf(\姓名：\ gets(btree->name); btree->right=NULL;

s=(BTree)malloc(sizeof(struct treenode)); printf(\妻子：\ gets(s->name);

s->left=s->right=NULL; btree->left=s; first=0; } else {

printf(\父亲：\ gets(xm);

if(strcmp(xm,\ contin=0; else {

p=findfather(btree,xm); if(p!=NULL) {

p=p->left;

if(p==NULL) /*没有妻子*/

printf(\没有儿子（因为没有妻子）\\n\ else {

while(p->right!=NULL) p=p->right;

s=(BTree)malloc(sizeof(struct treenode)); s->right=NULL; p->right=s;

printf(\儿子：\ gets(s->name);

printf(\儿妻：\ gets(xm);

if(strcmp(xm,\ {

t=(BTree)malloc(sizeof(struct treenode)); strcpy(t->name,xm); t->left=t->right=NULL; s->left=t; }

else s->left=NULL; } }

else printf(\不存在这样的父结点！\\n\ } } }

return(btree); }

void disptree(BTree BT) {

BTree stack[MaxSize],p;

int level[MaxSize][2],top,n,i,width=4; if(BT!=NULL) {

printf(\家谱凹入表示法:\\n\ top=1;

stack[top]=BT; /*根结点入栈*/ level[top][0]=width; while (top>0) {

p=stack[top]; /*退栈并凹入显示该结点值*/

n=level[top][0];

for (i=1;i<=n;i++) /*其中n为显示场宽,字符以右对齐显示*/ printf(\

printf(\

for(i=n+1;i<=MaxWidth-6;i+=2) printf(\━\ printf(\ top--;

if(p->right!=NULL)

{ /*将右子树根结点入栈*/ top++;

stack[top]=p->right;

level[top][0]=n+width; /*显示场宽增width*/ level[top][1]=2; }

if (p->left!=NULL)

{ /*将左子树根结点入栈*/ top++;

stack[top]=p->left;

level[top][0]=n+width; /*显示场宽增width*/ level[top][1]=1; } } } }

void findson(BTree bt) {

char xm[10]; BTree p;

printf(\查找指定父亲的所有儿子\\n\ printf(\父亲：\ gets(xm);

p=findfather(bt,xm); if(p==NULL)

printf(\不存在%s的父亲！\\n\ else {

p=p->left; p=p->right; if(p==NULL)

printf(\没有儿子!\\n\ else {

printf(\有以下儿子!\\n\\t\ while(p!=NULL) {

printf(\ p=p->right; }