《数据结构实验题参考答案》由会员分享，可在线阅读，更多相关《数据结构实验题参考答案（15页珍藏版）》请在金锄头文库上搜索。
1、【实验题】1狐狸逮兔子围绕着山顶有 10 个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到号洞找，第二次隔个洞（即 3 号洞）找，第三次隔个洞（即 6 号洞）找，以后如此类推，次数不限。 ”但狐狸从早到晚进进出出了 1000 次，仍没有找到兔子。问兔子究竟藏在哪个洞里？（提示：这实际上是一个反复查找线性表的过程。 ）【数据描述】定义一个顺序表，用具有 10 个元素顺序表来表示这 10 个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。#define LIST_INIT_SIZE 10 /线性表存储空间的初始分配量typedef struct Ele
2、mType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量（以 sizeof(ElemType)为单位）SqList;【算法描述】status InitList_Sq(SqList &L) /构造一个线性表 LL.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem) return OVERFLOW; /存储分配失败L.length=0; /空表长度为 0L.listsize=LIST_INIT_SIZE; /初始存储容量return OK; /Init
3、List_Sqstatus Rabbit(SqList &L) /构造狐狸逮兔子函数int current=0; /定义一个当前洞口号的记数器，初始位置为第一个洞口for(i=0;i#include #define OK 1#define OVERFLOW -2typedef int status;typedef int ElemType;#define LIST_INIT_SIZE 10 /*线性表存储空间的初始分配量 */typedef struct ElemType *elem; /* 存储空间基址 */int length; /* 当前长度 */int listsize; /*当前分配
4、的存储容量（以 sizeof(ElemType)为单位）*/SqList;status InitList_Sq(SqList *L)/*构造一个线性表 L */(*L).elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem) return OVERFLOW; /* 存储分配失败 */(*L).length=0; /*空表长度为 0 */(*L).listsize=LIST_INIT_SIZE; /*初始存储容量 */return OK; /*InitList_Sq */status Rabbit(SqList
5、 *L)/*构造狐狸逮兔子函数 */int i,current=0; /*定义一个当前洞口号的记数器，初始位置为第一个洞口*/for(i=0;i#include#define OVERFLOW -2typedef structint arrive;int treat; /*客户的信息结构*/QNODE;typedef struct nodeQNODE data;struct node *next; /*队列中的元素信息*/LNODE;LNODE *front,*rear;/* 队头指针和队尾指针*/QNODE curr,temp;char Fname120;FILE *fp;void EnQu
6、eue(LNODE *hpt,LNODE *tpt,QNODE e)/*队列进队*/LNODE *p=(LNODE *)malloc(sizeof(LNODE);if(!p) exit(OVERFLOW); /*存储分配失败*/p-data=e;p-next=NULL;if(*hpt=NULL) *tpt=*hpt=p;else *tpt=(*tpt)-next=p;int DeQueue(LNODE *hpt,LNODE *tpt,QNODE *cp)/*链接队列出队*/LNODE *p=*hpt;if(*hpt=NULL) return 1;/*队空*/*cp=(*hpt)-data;*h
7、pt=(*hpt)-next;if(*hpt=NULL) *tpt=NULL;free(p);return 0;void main() int dwait=0,clock=0,wait=0,count=0,have=0,finish;printf(n enter file name:);scanf(%s,Fname);/*输入装客户模拟数据的文件的文件名*/if(fp=fopen(Fname, r)=NULL) /*打开数据文件*/printf(cannot open file %s,Fname);return;front=NULL;rear=NULL;have=fscanf(fp, %d%s
8、,do /*约定每轮循环，处理一位客户*/if(front=NULL & have=2) /*等待队列为空，但还有客户*/dwait+=temp.arrive-clock; /*累计业务员总等待时间*/clock=temp.arrive; /*时钟推进到暂存变量中的客户的到达时间*/EnQueue( /* 暂存变量中的客户信息进队*/have=fscanf(fp, %d%d,count+; /*累计客户人数*/ DeQueue(/*出队一位客户信息*/wait+=clock-curr.arrive; /*累计到客户的总等待时间*/finish=clock+curr.treat;/*设定业务办理
9、结束时间；*/while(have=2 & temp.arrive#include #include #define MaxWidth 40#define MaxSize 30typedef struct treenodechar name10;struct treenode *left,*right; *BTree;BTree findfather(BTree p,char xm)BTree bt;if(p=NULL) return(NULL);elseif(strcmp(p-name,xm)=0)return(p);elsebt=findfather(p-left,xm);if(bt!=N
10、ULL) return(bt);else return(findfather(p-right,xm);BTree creatree()int n,m,i,contin=1,first=1;char xm10;BTree btree,s,t,p;printf(n 建立一个家谱二叉树（以空格结尾)：n);while(contin)if(first=1)btree=(BTree)malloc(sizeof(struct treenode);printf(t 姓名：);gets(btree-name);btree-right=NULL;s=(BTree)malloc(sizeof(struct tre
11、enode);printf(t 妻子：);gets(s-name);s-left=s-right=NULL;btree-left=s;first=0; elseprintf(t 父亲：);gets(xm);if(strcmp(xm, )=0)contin=0;elsep=findfather(btree,xm);if(p!=NULL)p=p-left;if(p=NULL) /*没有妻子*/printf(t 没有儿子（因为没有妻子）n);elsewhile(p-right!=NULL) p=p-right;s=(BTree)malloc(sizeof(struct treenode);s-rig
12、ht=NULL;p-right=s;printf(t 儿子：);gets(s-name);printf(t 儿妻：);gets(xm);if(strcmp(xm,)!=0)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 stackMaxSize,p;int levelMaxSize2,top,n,i,w
13、idth=4;if(BT!=NULL)printf(n 家谱凹入表示法:n);top=1;stacktop=BT; /*根结点入栈*/leveltop0=width;while (top0)p=stacktop; /*退栈并凹入显示该结点值*/n=leveltop0;for (i=1;iname);for(i=n+1;iright!=NULL) /*将右子树根结点入栈*/top+;stacktop=p-right;leveltop0=n+width; /*显示场宽增 width*/leveltop1=2;if (p-left!=NULL) /*将左子树根结点入栈*/top+;stacktop=
14、p-left;leveltop0=n+width; /*显示场宽增 width*/leveltop1=1;void findson(BTree bt)char xm10;BTree p;printf(n 查找指定父亲的所有儿子n);printf(父亲：);gets(xm);p=findfather(bt,xm);if(p=NULL)printf(不存在%s 的父亲！n,xm);elsep=p-left;p=p-right;if(p=NULL)printf(%s 没有儿子!n,xm);elseprintf(%s 有以下儿子!nt);while(p!=NULL)printf(%8s ,p-name
15、);p=p-right;main()BTree bt;bt=creatree();disptree(bt);findson(bt);运行结果建立一个家谱二叉树（以空格结尾)：姓名：张德妻子：陈氏父亲：张德儿子：张文儿妻：刘氏父亲：张德儿子：张武儿妻：王氏父亲：张文儿子：张兵儿妻：李氏父亲：张文儿子：张强儿妻：父亲：张武儿子：张华儿妻：父亲：家谱凹入表示法:张德陈氏张文刘氏张兵李氏张强张武王氏张华查找指定父亲的所有儿子父亲：张德有以下儿子!张文 张武 4最短路径假设有 n 个城市组成一个公路网（有向的），并用代价邻接矩阵表示该网络，编写一个指定城市 v 到其他各城市的最短路径的函数。方法：直接采用
