〈数据结构〉上机实验指导

《〈数据结构〉上机实验指导》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构》实验指导书数据结构实验指导书编淮阴工学院计算机系二OO五年九月20《数据结构》实验指导书目录实验一线性表及其应用…………………………………2实验二栈和队列及其应用…………………………………5实验三二叉树及其应用……………………………………7实验四图及其应用…………………………………………9实验五查找………………………………………………11实验六排序………………………………………………1320《数据结构》实验指导书实验一线性表及其应用实验目的1.加深对线性表的结构特性的理解;2.熟练掌握线性表的链式存储结构的描述方法及基本操作;3.掌握线性表的

2、链式存储结构的应用方法;4.从时间和空间的角度对操作算法进行分析。5.培养程序的设计能力和调试能力。实验学时：建议2~4学时实验内容内容1：制作体育彩票（10选7）的选号器。【说明】1）体育彩票（10选7）的7个号可以重复；2）建议用首尾相连的链式结构，这样可以更逼真地模拟“摇奖”过程；而每个号的“摇动”次数可用随机数来确定。3）怎样产生随机数？可以利用C++语言中的种子函数srand()和伪随机函数rand()来实现。（include）a)首先，给srand(m)提供一个“种子”m，它的取值范围是从0～65535。b)然后，调用ra

3、nd()，是伪随机数，它会根据提供给srand()的“种子”值返回一个随机数（在0～32767之间）。c)根据需要多次调用rand()，从而不断地得到新的随机数。d)无论何时，你都可以给srand()提供一个新的“种子”，从而进一步“随机化”rand()的输出结果。20《数据结构》实验指导书例如，取m=17，则执行了srand(17)之后，再执行rand()函数，将得到输出值94；第二次调用rand()，会得到26,……反复调用rand()就能产生一系列的随机数。注意：若m不变，则rand()的输出系列也不变，总是94,26,602,…等等。所以，建议摇

4、号的“种子”选当前日期或时间，以保证每天的摇号值都不相同。【选做内容】实现摇奖和对奖操作。内容2：约瑟夫（Joseph）环问题【问题描述】约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从1起报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止。求最后剩下的人的编号。【说明】1）建议用循环链表存储方式。2）问题改进：在人数n、k及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码Ki（整数），留作其出圈后的报到Ki后出圈。密码Ki可用随机数产生。这样事前无法确定谁是最后一人编写的代码：#inc

5、lude#includetypedefstructJoseph{intnum;intkey;structJoseph*next;}Joseph1;Joseph1*CreatList(intn){Joseph1*R,*p,*q;20《数据结构》实验指导书inti,k;R=p=(Joseph1*)malloc(sizeof(Joseph1));p->next=NULL;for(i=0;inum=i+1;scanf("%d",

6、&k);if(k<=0){printf("输入信息有误!");exit(0);}p->key=k;p->next=q;p=q;}q->num=n;scanf("%d",&k);if(k<=0){printf("输入信息有误!");exit(0);}q->key=k;q->next=R;R=q;return(R);}voidDeleList(intn,Joseph1*P,intm){Joseph1*q,*t;q=P;inti,j;for(i=1;inext;t=q->next;q->next=t->

7、next;20《数据结构》实验指导书m=t->key;printf("删除的第%d个数是:",i);printf("%d",t->num);free(t);}printf("删除的最后一个数是:%d",q->num);free(q);}voidmain(){intm,n;Joseph1*P;printf("请输入参加的人数:");scanf("%d",&n);if(n<=0){printf("输入信息有误!");exit(0);}printf("请输入初始密码:");scanf("%d",&m);if(m<=0){printf("输入信息有误!"

8、);exit(0);}printf("请输入每个人的密码:");P=CreatL