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

《数据结构》实验指导书 PAGE PAGE 19 数据结构实验指导书 编 淮阴工学院计算机系 二OO五年九月 目 录 实验一 线性表及其应用…………… ……………………2 实验二 栈和队列及其应用…………………………………5 实验三 二叉树及其应用……………………………………7 实验四 图及其应用…………………………………………9 实验五 查找……………… ………………………………11 实验六 排序………………… ……………………………13  实验一 线性表及其应用 实验目的 加深对线性表的结构特性的理解; 熟练掌握线性表的链式存储结构的描述方法及基本操作; 掌握线性表的链式存储结构的应用方法; 从时间和空间的角度对操作算法进行分析。 培养程序的设计能力和调试能力。 实验学时：建议2~4学时 实验内容 内容1：制作体育彩票（10选7）的选号器。 【说明】 体育彩票（10选7）的7个号可以重复； 建议用首尾相连的链式结构，这样可以更逼真地模拟“摇奖”过程；而每个号的“摇动”次数可用随机数来确定。 怎样产生随机数？可以利用C++语言中的种子函数srand( )和伪随机函数rand( )来实现。（includeSTDLIB.H） 首先，给srand(m )提供一个“种子”m，它的取值范围是从0～65535。 然后，调用rand( )，是伪随机数，它会根据提供给srand( )的“种子”值返回一个随机数（在0～32767之间）。 根据需要多次调用rand( )，从而不断地得到新的随机数。 无论何时，你都可以给srand( )提供一个新的“种子”，从而进一步“随机化”rand( )的输出结果。 例如，取m=17，则执行了srand(17)之后，再执行rand( )函数，将得到输出值94；第二次调用rand( )，会得到26,……反复调用rand( )就能产生一系列的随机数。 注意：若m不变，则rand( )的输出系列也不变，总是94,26,602,…等等。所以，建议摇号的“种子”选当前日期或时间，以保证每天的摇号值都不相同。 【选做内容】 实现摇奖和对奖操作。 内容2：约瑟夫（Joseph）环问题 【问题描述】 约瑟夫问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈,从1起报到k则出圈，下一个人再从1报起，如此下去直到圈中只有一人为止。求最后剩下的人的编号。 【说明】 建议用循环链表存储方式。 问题改进：在人数n、k及起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码Ki（整数），留作其出圈后的报到Ki后出圈。密码Ki可用随机数产生。这样事前无法确定谁是最后一人 编写的代码： #includestdio.h #includestdlib.h typedef struct Joseph { int num; int key; struct Joseph *next; } Joseph1; Joseph1 *CreatList(int n) { Joseph1 *R,*p,*q; int i,k; R=p=(Joseph1*)malloc(sizeof(Joseph1)); p-next=NULL; for(i=0;in-1;i++){ q=(Joseph1*)malloc(sizeof(Joseph1)); p-num=i+1; scanf(%d,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); } void DeleList(int n,Joseph1 *P,int m) { Joseph1 *q,*t; q=P; int i,j; for(i=1;in;i++) { for(j=1;jm;j++) q=q-next; t=q-next; q-next=t-next; m=t-key; printf(删除的第%d个数是:,i); printf(%d\n,t-num); free(t); } printf(删除的最后一个数是:%d\n,q-num); free(q); } void main() { int m,n; Joseph1 *P; printf(请输入参加的人数: ); scanf(%d,n); if(n=0) { pri