数据结构实验指导书编工学院计算机系二 OO 五年九月目 录实验一 线性表与其应用…………………………………2实验二 栈和队列与其应用…………………………………5实验三 二叉树与其应用……………………………………7实验四 图与其应用…………………………………………9实验五 查找………………………………………………11实验六 排序………………………………………………13实验一 线性表与其应用实验目的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()的输出结果。例如，取 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）问题改进：在人数 n、k 与起始报数人确定的情况下，最后剩下的人的编号事前是可以确定的。若每人有一个密码 Ki（整数），留作其出圈后的报到 Ki 后出圈。密码 Ki 可用随机数产生...
