数据结构实验指导书 陈宏明 张亚红 寇海洲编 淮阴工学院计算机系 二OO五年九月《数据结构》实验指导书 1 目 录 实验一 线性表及其应用…………… ……………………2 实验二 栈和队列及其应用…………………………………5 实验三 二叉树及其应用……………………………………7 实验四 图及其应用…………………………………………9 实验五 查找……………… ………………………………1 1 实验六 排序………………… ……………………………1 3 《数据结构》实验指导书 2 实验一 线性表及其应用 实验目的 1. 加深对线性表的结构特性的理解; 2. 熟练掌握线性表的链式存储结构的描述方法及基本操作; 3. 掌握线性表的链式存储结构的应用方法; 4.从时间和空间的角度对操作算法进行分析。 5.培养程序的设计能力和调试能力。 实验学时：建议2~4 学时 实验内容 内容1：制作体育彩票（10 选7）的选号器。 【说明】 1）体育彩票（10 选7）的7 个号可以重复； 2）建议用首尾相连的链式结构，这样可以更逼真地模拟“摇奖”过程；而每个号的“摇动”次数可用随机数来确定。 3）怎样产生随机数？可以利用C++语言中的种子函数srand( )和伪随机函数rand( )来实现。（include） a) 首先，给 srand(m )提供一个“种子”m，它的取值范围是从0～65535。 b) 然后，调用rand( )，是伪随机数，它会根据提供给 srand( )的“种子”值返回一个随机数（在 0～32767 之间）。 c) 根据需要多次调用rand( )，从而不断地得到新的随机数。 d) 无论何时，你都可以给 srand( )提供一个新的“种子”，从而进一步“随机化”rand( )的输出结果。 《数据结构》实验指导书 3 例如，取m=17，则执行了srand(17)之后，再执行rand( )函数，将得到输出值94；第二次调用rand( )，会得到26,„„反复调用rand( )就能产生一系列的随机数。 注意：若m 不变，则rand( )的输出系列也不变，总是94,26,602,„等等。所以，建议摇号的“种子”选当前日期或时间，以保证每天的摇号值都不相同。 【选做内容】 实现摇奖和对奖操作。 内容 2：约瑟夫（Joseph）环问题 【问题描述】 约瑟夫问题的一种描述是：编号为 1，2，„，n的n个人按顺时针方向围坐一圈,从 1起报到k则出圈，下一个人再从 1报起，如此下去直到圈中只有一人为止。求最后剩下的人的编号。 【说明】 1） 建议用循环链表存储方式。 2） ...
