数据结构实验题参考答案[1].doc

【实验题】1狐狸逮兔子围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到号洞找，第二次隔个洞（即3号洞）找，第三次隔个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？ （提示：这实际上是一个反复查找线性表的过程。）【数据描述】定义一个顺序表，用具有10个元素顺序表来表示这10个洞。每个元素分别表示围着山顶的一个洞，下标为洞的编号。#defineLIST_INIT_SIZE10/线性表存储空间的初始分配量typedefstructElemType*elem;/存储空间基址intlength;/当前长度intlistsize;/当前分配的存储容量（以sizeof(ElemType)为单位）SqList;【算法描述】statusInitList_Sq(SqList&L)/构造一个线性表LL.elem=(ElemType)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem)returnOVERFLOW; /存储分配失败L.length=0; /空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量returnOK;/InitList_SqstatusRabbit(SqList&L)/构造狐狸逮兔子函数intcurrent=0; /定义一个当前洞口号的记数器，初始位置为第一个洞口for(i=0;iLIST_INIT_SIZE;i+)L.elemi=1; /给每个洞作标记为1，表示狐狸未进之洞L.elemLIST_INIT_SIZE-1=L.elem0=0;/首先进入第一个洞，标记进过的洞为0。for(i=2;i=1000;i+)current=(current+i)%LIST_INIT_SIZE;/实现顺序表的循环引用L.elemi=0; /标记进过的洞为0/第二次隔个洞找，第三次隔个洞找，以后如此类推,经过一千次printf(兔子可能藏在如下的洞中：)for(i=0;iLIST_INIT_SIZE;i+)if(L.elemi=1)printf(“第%d个洞n”,i+1);/输出未进过的洞号returnOK;/end【C源程序】#include#include#defineOK1#defineOVERFLOW-2typedefintstatus;typedefintElemType;#defineLIST_INIT_SIZE10 /*线性表存储空间的初始分配量*/typedefstructElemType*elem; /*存储空间基址*/intlength; /*当前长度*/intlistsize; /*当前分配的存储容量（以sizeof(ElemType)为单位）*/SqList;statusInitList_Sq(SqList*L)/*构造一个线性表L*/(*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!(*L).elem)returnOVERFLOW;/*存储分配失败*/(*L).length=0; /*空表长度为0*/(*L).listsize=LIST_INIT_SIZE; /*初始存储容量*/returnOK;/*InitList_Sq*/statusRabbit(SqList*L)/*构造狐狸逮兔子函数*/inti,current=0; /*定义一个当前洞口号的记数器，初始位置为第一个洞口*/for(i=0;iLIST_INIT_SIZE;i+)(*L).elemi=1; /*给每个洞作标记为1，表示狐狸未进之洞*/(*L).elemLIST_INIT_SIZE-1=0;(*L).elem0=0; /*第一次进入第一个洞，标记进过的洞为0*/for(i=2;i=1000;i+)current=(current+i)%LIST_INIT_SIZE;/*实现顺序表的循环引用*/(*L).elemcurrent=0; /*标记进过的洞为0*/*第二次隔个洞找，第三次隔个洞找，以后如此类推,经过一千次*/printf(n兔子可能藏在如下的洞中：);for(i=0;iLIST_INIT_SIZE;i+)if(*L).elemi=1)printf(n此洞是第%d号洞,i+1);/*输出未进过的洞号*/returnOK;voidmain()SqList*L;InitList_Sq(L);Rabbit(L);getch();【测试数据】最后的输出结果为：2479【说明】本算法思路比较简单，采用了顺序表表示围着山顶的10个洞，首先对所有洞设置标志为1，然后通过1000次循环，对每次所进之洞修改标志为0，最后输出标志为1的洞。2银行客户某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围内的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中。对应每位客户有两个数据，到达时间和需要办理业务的时间。复习概念：与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图3-2：出队a1a2an-1an进队队头 队尾【数据描述】typedefstructintarrive;inttreat;/客户的信息结构QNODE；typedefstructnodeQNODEdata;Structnode*next;/队列中的元素信息LNODELNODE*front,*rear;/队头指针和队尾指针【算法描述】设置统计初值；设置当前时钟时间为0；打开数据文件，准备读；读入第一位客户信息于暂存变量中；do/约定每轮循环，处理完一位客户if(等待队列为空，并且还有客户)/等待队列为空时累计业务员总等待时间；时钟推进到暂存变量中的客户的到达时间；暂存变量中的客户信息进队；读取下一位客户信息于暂存变量；累计客户人数；从等待队列出队一位客户；将该客户的等待时间累计到客户的总等待时间；设定当前客户的业务办理结束时间；while(下一位客户的到达时间在当前客户处理结束之前)暂存变量中的客户信息进队；读取下一位客户信息于暂存变量；时钟推进到当前客户办理结束时间；while(还有未处理的客户)；计算统计结果，并输出；【C源程序】#include#include#defineOVERFLOW-2typedefstruct intarrive; inttreat;/*客户的信息结构*/QNODE;typedefstructnodeQNODEdata;structnode*next;/*队列中的元素信息*/LNODE;LNODE*front,*rear;/*队头指针和队尾指针*/QNODEcurr,temp;charFname120;FILE*fp;voidEnQueue(LNODE*hpt,LNODE*tpt,QNODEe)/*队列进队*/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;intDeQueue(LNODE*hpt,LNODE*tpt,QNODE*cp)/*链接队列出队*/LNODE*p=*hpt;if(*hpt=NULL)return1;/*队空*/ *cp=(*hpt)-data;*hpt=(*hpt)-next;if(*hpt=NULL)*tpt=NULL;free(p);return0;voidmain() intdwait=0,clock=0,wait=0,count=0,have=0,finish; printf(nenterfilename:); scanf(%s,Fname);/*输入装客户模拟数据的文件的文件名*/ if(fp=fopen(Fname,r)=NULL)/*打开数据文件*/ printf(cannotopenfile%s,Fname); return; front=NULL;rear=NULL; have=fscanf(fp,%d%s,&temp.arrive,&temp.treat); do/*约定每轮循环，处理一位客户*/ if(front=NULL&have=2)/*等待队列为空，但还有客户*/ dwait+=temp.arrive-clock;/*累计业务员总等待时间*/ clock=temp.arrive;/*时钟推进到暂存变量中的客户的到达时间*/ EnQueue(&front,&rear,temp);/*暂存变量中的客户信息进队*/ have=fscanf(fp,%d%d,&temp.arrive,&temp.treat); count+; /*累计客户人数*/ DeQueue(&front,&rear,&curr);/*出队一位客户信息*/ wait+=clock-curr.arrive;/*累计到客户的总等待时间*/ finish=clock+curr.treat;/*设定业务办理结束时间；*/ while(have=2&temp.arrive=finish)/*下一位客户的到达时间在当前客户处理结束之前*/ EnQueue(&front,&rear,temp);/*暂存变量中的客户信息进队*/ have=fscanf(fp,%d%d,&temp.arrive,&temp.treat); clock=finish;/*时钟推进到当前客户办理结束时间*/while(have=2|front!=NULL);printf(结果：业务员等待时间%dn客户平均等待时间%fn,dwait,(double)wait/count);printf(模拟总时间：%d，n客户人数：%d,n总等待时间：%dn,clock,count,wait);getch();/*main_end*/【测试数据】 设数据装在一个数据文件data.dat中，内容为：106138 显示结果为：enterfilename: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 30typedef struct treenode char name10; 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 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 treenode); printf(t妻子：); gets(s-name); s-left=s-right=NULL; btree-left=s; first=0; else printf(t父亲：); gets(xm); if(strcmp(xm, )=0) contin=0; else p=findfather(btree,xm); if(p!=NULL) p=p-left; if(p=NULL) /*没有妻子*/printf(t没有儿子（因为没有妻子）n); else while(p-right!=NULL) p=p-right;s=(BTree)malloc(sizeof(struct treenode); s-right=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,width=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=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);else p=p-left; p=p-right; if(p=NULL) printf(%s没有儿子!n,xm); else printf(%s有以下儿子!nt); while(p!=NULL) printf(%8s ,p-name); p=p-right; main() BTree bt;bt=creatree();disptree(bt);findson(bt); 运行结果建立一个家谱二叉树（以空格结尾)： 姓名：张德 妻子：陈氏 父亲：张德 儿子：张文 儿妻：刘氏 父亲：张德 儿子：张武 儿妻：王氏 父亲：张文 儿子：张兵 儿妻：李氏 父亲：张文 儿子：张强 儿妻： 父亲：张武 儿子：张华 儿妻： 父亲：家谱凹入表示法: 张德 陈氏 张文 刘氏 张兵 李氏 张强 张武 王氏 张华查找指定父亲的所有儿子父亲：张德有以下儿子! 张文 张武 4最短路径假设有n个城市组成一个公路网（有向的），并用代价邻接矩阵表示该网络，编写一个指定城市v到其他各城市的最短路径的函数。方法：直接采用Dijkstra算法，略。5排序对于对于输入的数字按从小到大和从大到小两种顺序进行排序，并显示中间排序过程。提示 可以采用快速排序方法进行数字的两种排序。源程序#include #define MAX 100void disparr();int aMAX,n,m;void creatarr() int i=0; printf(建立原始数序n); printf(t元素个数：); scanf(%d,&n); while(in) printf(t第%d个元素：,i+1);scanf(%d,&ai);i+;int cmp(int lval,int rval,int order) if(order=1) if(lvalrval) return(1); else return(0); void quicksort(int x,int l,int r,int order) /*把xl至xr的元素进行快速排序*/ int i=l,j=r,k,temp; temp=xl; while(ij) while(ij & cmp(temp,xj,order) j-;/*/ if(ij) xi=xj;i+; while(ij & cmp(xi,temp,order) i+;/*/ if(ij) xj=xi;j-; xi=temp;printf(t(%d) ,m+);for(k=0;kn;k+) if(k=l) printf( ); if(k=i) printf( ); printf( %d ,xk); if(k=i) printf( ); if(k=r) printf( );printf(n);if(li) quicksort(x,l,i-1,order);if(ir) quicksort(x,j+1,r,order);void disparr() int i; for(i=0;in;i+)printf(%d ,ai); printf(nn);main()creatarr(a); m=1;printf(n原来的次序：);disparr();printf(从小到大排次序：n);quicksort(a,0,n-1,1);printf(排序结果：);disparr();m=1;printf(从大到小排序：n);quicksort(a,0,n-1,0);printf(排序结果：);disparr();建立原始数序 元素个数：10 第1个元素：9 第2个元素：4 第3个元素：0 第4个元素：2 第5个元素：5 第6个元素：3 第7个元素：8 第8个元素：7 第9个元素：1 第10个元素：6原来的次序：9 4 0 2 5 3 8 7 1 6从小到大排次序： (1) 6 4 0 2 5 3 8 7 1 9 (2) 1 4 0 2 5 3 6 7 8 9 (3) 0 1 4 2 5 3 6 7 8 9 (4) 0 1 4 2 5 3 6 7 8 9 (5) 0 1 3 2 4 5 6 7 8 9 (6) 0 1 2 3 4 5 6 7 8 9 (7) 0 1 2 3 4 5 6 7 8 9 (8) 0 1 2 3 4 5 6 7 8 9 (9) 0 1 2 3 4 5 6 7 8 9 (10) 0 1 2 3 4 5 6 7 8 9排序结果：0 1 2 3 4 5 6 7 8 9从大到小排序： (1) 9 1 2 3 4 5 6 7 8 0 (2) 9 1 2 3 4 5 6 7 8 0 (3) 9 8 2 3 4 5 6 7 1 0 (4) 9 8 2 3 4 5 6 7 1 0 (5) 9 8 7 3 4 5 6 2 1 0 (6) 9 8 7 3 4 5 6 2 1 0 (7) 9 8 7 6 4 5 3 2 1 0 (8) 9 8 7 6 4 5 3 2 1 0 (9) 9 8 7 6 5 4 3 2 1 0 (10) 9 8 7 6 5 4 3 2 1 0排序结果：9 8 7 6 5 4 3 2 1 06哈希函数设数序为53,17,12,61,98,70,87,25,63,46,14,59,67,75,哈希表长M=18,哈希函数为： H(k)=k MOD 17建立对应的哈希表，采用开放地址法中的二次探测瑞散列解决冲突，并查找值为70的元素位置。源程序#include #define MAX 100int haMAX,hlenMAX,n,m,p;void creathash() int i,j,d,d1,odd,s,keyMAX; printf(=建立散列表=n); printf(输入元素个数n:); scanf(%d,&n); printf(输入哈希表长m:); scanf(%d,&m); printf(散列函数:h(k) MOD p: ); scanf(%d,&p); for(i=0;im;i+) hai=hleni=0; /*hleni为第i个元素的查找长度*/ i=0; while(in) printf(第%d个元素：,i+1); scanf(%d,&keyi); odd=1; if(keyi=0) printf(输入错误，重新输入！n); else i+; i=0; printf(哈希表建立如下：n); while(in) odd=1;d=d1=keyi%p;j=s=1; /*记录比较次数*/printf(H(%d)=%d MOD %d=%d,keyi,keyi,p,d);while(had!=0) printf( 冲突n); if(odd) d=(d1+j*j)%m; printf(H(%d)=(%d+%d*%d) MOD %d=%d,keyi,d1,j,j,m,d); odd=0; else d=(d1-j*j)%m;printf(H(%d)=(%d-%d*%d) MOD %d=%d,keyi,d1,j,j,m,d);odd=1;j+;s+; printf( 比较%d次n,s); had=keyi; hlend=s; i+; void disphash() int i,s=0; printf(n散列表H为：n); for(i=0;im;i+) printf(%3d,i); printf(n); for(i=0;im;i+) printf(%3d,hai); printf(n); for(i=0;im;i+)printf(%3d,hleni); printf(n); for(i=0;im;i+) s=s+hleni; printf(tASL(%d)=%6.2fn,n,(1.0*s)/n);void findhash() int x,j,d,d1,odd=1; printf(n输入要查找的值：); scanf(%d,&x); d=d1=x%p; j=1; while(had!=0 & had!=x) if(odd) d=(d1+j*j)%m; odd=0; else d=(d1-j*j)%m; odd=1; j+; if(had=0) printf(t输入的查找值不正确！n);else printf(t查找值：ha%d=%d!n,d,x);main() creathash(); disphash(); findhash(); =建立散列表=输入元素个数n:14输入哈希表长m:18散列函数:h(k) MOD p: 17第1个元素：53第2个元素：17第3个元素：12第4个元素：61第5个元素：98第6个元素：70第7个元素：87第8个元素：25第9个元素：63第10个元素：46第11个元素：59第12个元素：14第13个元素：67第14个元素：75哈希表建立如下：H(53)=53 MOD 17=2 比较1次H(17)=17 MOD 17=0 比较1次H(12)=12 MOD 17=12 比较1次H(61)=61 MOD 17=10 比较1次H(98)=98 MOD 17=13 比较1次H(70)=70 MOD 17=2 冲突H(70)=(2+1*1) MOD 18=3 比较2次H(87)=87 MOD 17=2 冲突H(87)=(2+1*1) MOD 18=3 冲突H(87)=(2-1*1) MOD 18=1 比较3次H(25)=25 MOD 17=8 比较1次H(63)=63 MOD 17=12 冲突H(63)=(12+1*1) MOD 18=13 冲突H(63)=(12-1*1) MOD 18=11 比较3次H(46)=46 MOD 17=12 冲突H(46)=(12+1*1) MOD 18=13 冲突H(46)=(12-1*1) MOD 18=11 冲突H(46)=(12+2*2) MOD 18=16 比较4次H(59)=59 MOD 17=8 冲突H(59)=(8+1*1) MOD 18=9 比较2次H(14)=14 MOD 17=14 比较1次H(67)=67 MOD 17=16 冲突H(67)=(16+1*1) MOD 18=17 比较2次H(75)=75 MOD 17=7 比较1次散列表H为： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 17 87 53 70 0 0 0 75 25 59 61 63 12 98 14 0 46 67