〈数据结构〉上机实验指导.doc
文本预览下载声明
数据结构实验指导书
编
淮阴工学院计算机系
二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)
{
printf(输入信息有误!);
exit(0);
}
显示全部