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

1、【实验题】1 狐狸逮兔子围绕着山顶有10 个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到1号洞找，第二次隔1个洞(即3号洞)找，第三次隔2个洞(即6 号洞)找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了 1000 次，仍没有找到兔子。问兔子究竟藏在哪个洞里？(提示：这实际上是一个反复查找线性表的过程。 )【数据描述】定义一个顺序表， 用具有 10 个元素顺序表来表示这 10 个洞。 每个元素分别表示围着山顶的一个洞，下标为洞的编号。#define LIST_INIT_SIZE 10 / 线性表存储空间的初始分配量typedef struct E

2、lemType *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

3、OK; /InitList_Sqstatus Rabbit(SqList &L) / 构造狐狸逮兔子函数int current=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/第二次隔1

4、个洞找，第三次隔2个洞找，以后如此类推，经过一千次printf( 兔子可能藏在如下的洞中： )for(i=0;iLIST_INIT_SIZE;i+)if(L.elemi=1)printf( “第dj洞n 尸1);/ 输出未进过的洞号 return OK;/end【 C 源程序】#include #include #define OK 1#define OVERFLOW -2typedef int status;typedef int ElemType;*/#define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量typedef struct ElemType *ele

5、m; /* int length; /* int listsize; /*存储空间基址*/当前长度 */当前分配的存储容量(以sizeof(ElemType) 为单位) */SqList;status InitList_Sq(SqList *L) TOC o 1-5 h z /* 构造一个线性表L */(*L).elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!(*L).elem) return OVERFLOW; /*存储分配失败*/(*L).length=0; /* 空表长度为 0 */(*L).listsize=LI

6、ST_INIT_SIZE; /*初始存储容量*/return OK; /*InitList_Sq */status Rabbit(SqList *L)/* 构造狐狸逮兔子函数 */int i,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=(curren

7、t+i)%LIST_INIT_SIZE;/* 实现顺序表的循环引用 */(*L).elemcurrent=0; /*标记进过的洞为 0 */*第二次隔1个洞找，第三次隔2个洞找，以后如此类推，经过一千次*/printf(n 兔子可能藏在如下的洞中： ) ;for(i=0;iLIST_INIT_SIZE;i+)if(*L).elemi=1)printf( n 此洞是第d号洞,i+1);/* 输出未进过的洞号 */ return OK;void main()SqList *L;InitList_Sq(L);Rabbit(L);getch();【测试数据】最后的输出结果为： 2 4 7 9【说明】1

8、，本算法思路比较简单，采用了顺序表表示围着山顶的 10 个洞，首先对所有洞设置标志为然后通过 1000 次循环，对每次所进之洞修改标志为 0 ，最后输出标志为 1 的洞。2 银行客户 某银行有一个客户办理业务站， 在单位时间内随机地有客户到达， 设每位客户的业务办理时间是某个范围内的随机值。 设只有一个窗口， 一位业务人员， 要求程序模拟统计在设定时间内， 业务人员的总空闲时间和客户的平均等待时间。 假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中。 对应每位客户有两个数据， 到达时间和需要办理业务的时间。复习概念：与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入

9、，而在另一 端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图见图3-2 :出队al a2 , an-1an 进队TO【数据描述】typedef structint arrive;int treat;/ 客户的信息结构QNODEtypedef struct nodeQNODE data;Struct node *next; 队列中的元素信息LNODELNODE *front,*rear;队头指针和队尾指针【算法描述】设置统计初值；设置当前时钟时间为 0;打开数据文件，准备读；读入第一位客户信息于暂存变量中；do /约定每轮循环，处理完一位客户i

10、f（等待队列为空，并且还有客户 ） /等待队列为空时累计业务员总等待时间；时钟推进到暂存变量中的客户的到达时间；暂存变量中的客户信息进队；读取下一位客户信息于暂存变量；累计客户人数；从等待队列出队一位客户；将该客户的等待时间累计到客户的总等待时间；设定当前客户的业务办理结束时间；while（ 下一位客户的到达时间在当前客户处理结束之前）暂存变量中的客户信息进队；读取下一位客户信息于暂存变量；时钟推进到当前客户办理结束时间；while（ 还有未处理的客户）；计算统计结果，并输出；【C源程序】#include#include#define OVERFLOW -2typedef structint

11、arrive;int treat; /* 客户的信息结构*/QNODE;typedef struct nodeQNODE data;struct node *next; /* 队列中的元素信息*/LNODE;LNODE *front,*rear;/* 队头指针和队尾指针 */QNODE curr,temp;char Fname120;FILE *fp;void EnQueue(LNODE *hpt,LNODE *tpt,QNODE e)/* 队列进队 */LNODE *p=(LNODE *)malloc(sizeof(LNODE);if(!p) exit(OVERFLOW); /* 存储分配失

12、败*/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;*hpt=(*hpt)-next;if(*hpt=NULL) *tpt=NULL;free(p);return 0;void main() int dwait=0,clock=0,wait=0,count=0,have

13、=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,&temp.arrive,&temp.treat);if(front=NULL & have=2) /* dwait+=temp.arrive-clock; /* clock=temp.arrive; /*E

14、nQueue(&front,&rear,temp); /*do /* 约定每轮循环，处理一位客户 */等待队列为空，但还有客户 */*/累计业务员总等待时间 */时钟推进到暂存变量中的客户的到达时间暂存变量中的客户信息进队*/have=fscanf(fp, %d%d,&temp.arrive,&temp.treat);count+;/*DeQueue(&front,&rear,&curr);/*wait+=clock-curr.arrive; /*finish=clock+curr.treat;/*累计客户人数 */出队一位客户信息*/累计到客户的总等待时间 */设定业务办理结束时间； */w

15、hile(have=2 & temp.arrive=finish) TOC o 1-5 h z /*下一位客户的到达时间在当前客户处理结束之前*/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( 模拟总时间

16、：d, n客户人数：%d,n总等待时间： dn,clock, 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 【说明】在计算程序中，程序按模拟环境中的事件出同顺序逐一处理事件：当一个事件结束时， 下一个事件隔一段时间才发生，则程序逻辑的模拟时钟立即推进到下一事件的发生

17、时间；如一个事件还未处理结束之前，另有其他事件等待处理，则这些事件就应依次排队等候处理。.二叉树的的应用：设计一个表示家谱的二叉树 要求：采用一棵二叉树表示一逐步形成家谱关系，对于给定的父亲显示所有的儿子。 由于家谱为树形，但不是一棵二叉树，所以在存储时要转换成二叉树的形式。规定：一个父 亲结点的左子树表示母亲结点，母亲结点的右子树表示他们的所有儿子，例如，图1是一个用二叉树表示的家谱图，与之对应的传统树形图家谱图如图2所示。这样就将家谱树转换成二叉树了，而二叉树的操作是容易实现的。C源程序#include #include #include #define MaxWidth 40#defin

18、e 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!=NULL) return(bt);else return(findfather(p-right,xm);BTree creatree()int n,m,i

19、,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

20、=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-right=NULL;p-right=s;printf(t儿子：);gets(s-name);printf(t儿妻：);gets(xm);if(

21、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; /* 根结点入栈*/l

22、eveltop0=width;while (top0)p=stacktop; /*退栈并凹入显示该结点值*/n=leveltop0;其中 n 为显示场宽 , 字符以右对齐显示*/for (i=1;iname);for(i=n+1;iright!=NULL) top+;/*将右子树根结点入栈*/stacktop=p-right;/*显示场宽增width*/leveltop0=n+width;leveltop1=2;if (p-left!=NULL)top+;/*将左子树根结点入栈*/stacktop=p-left;/*显示场宽增width*/leveltop0=n+width;leveltop1

23、=1;void findson(BTree bt) char xm10;BTree p;printf(n 查找指定父亲的所有儿子n);printf( 父亲： );gets(xm);p=findfather(bt,xm);if(p=NULL)printf(不存在 $的父亲！ 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);p=p-right;)main()(BTree bt;bt=creatree();dis

24、ptree(bt); findson(bt);)运行结果建立一个家谱二叉机(以空格结尾)：姓名：张德妻子：陈氏 父亲：张德 儿子：张文 儿妻：刘氏 父亲：张德 儿子：张武 儿妻：王氏 父亲：张文 儿子：张兵 儿妻：李氏 父亲：张文 儿子：张强儿妻：父亲：张武 儿子：张华 儿妻：父亲：家谱凹入表示法：张德陈氏张文刘氏张兵李氏一 张强一张武王氏李华一查找指定父亲的所有儿子父亲：张德有以下儿子！张武张文.最短路径 假设有 n 个城市组成一个公路网(有向的)，并用代价邻接矩阵表示该网络，编写一个指定城市 v 到其他各城市的最短路径的函数。方法：直接采用 Dijkstra 算法，略。5排序对于对于输入的

25、数字按从小到大和从大到小两种顺序进行排序，并显示中间排序过程。 提示 可以采用快速排序方法进行数字的两种排序。C源程序#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第 个元素：”,i+1);scanf(%d,&ai);i+;int cmp(int lval,int rval,int order)if(order=1)if(lvalrval) return(1);el

26、se 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( );prin

27、tf( %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

28、=1;printf( 从大到小排序： n);quicksort(a,0,n-1,0);printf( 排序结果： );disparr();建立原始数序元素个数： 10 TOC o 1-5 h z 第 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从小到大排次序：64025387 1 9140253 6 78 90 1 4253 67 890 1 425 367890 13 2 4 5 678901 2 345678901 234

29、567890123 4567890123 45 67 890 1 2 3 4 5 6 7 8 9排序结果： 0 1 2 3 4 5 6 7 8 9从大到小排序： 9123456780912345678 098234567 1098 2345671098 734562109873456 21098764532109876 4532109 8 7 6 5 4 3 2 1 09 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

30、(k)=k MOD 17建立对应的哈希表，采用开放地址法中的二次探测瑞散列解决冲突，并查找值为 70 的 元素位置。C源程序#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;/*

31、hleni 为第 i 个元素的查找长度 */i=0;while(in)printf(第 个元素：,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

32、 %d=%d,keyi,d1,j,j,m,d);odd=0;elsed=(d1-j*j)%m;printf(H(%d)=(%d-%d*%d) MOD %d=%d,keyi,d1,j,j,m,d);odd=1;j+;s+;printf(比较 次坨$);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)

33、;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;elsed=(d1-j*j)%m;odd=1;j+;n);if(had=0) printf(t输入的查找值不正确！else printf(t 查找值： ha%d=%d!n,d,x);main()cre

34、athash();disphash();findhash();=建立散列表=输入元素个数n:14输入哈希表长m:18散列函数 :h(k) MOD p: 17第 1 个元素： 53 TOC o 1-5 h z 第 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哈希表建立如下： TOC o 1-5 h z H(53)=53 MOD 17=2比较1 次H(17)=17 MOD 17=0比较1 次H(12)

35、=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=

36、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 1717 87 53 70 0 0 0 75 25 59 61 63 12 98 14 0 46 671 3 1 2 0 0 0