实验一 线性表的应用.doc

实验一 　　线性表的应用（一） ——体育彩票的模拟生成和兑奖 一、实验目的与要求 熟悉线性表数据结构的定义及顺序存储，会使用线性表的基本操作解决一些实际问题。 二、实验内容 用线性表实现体育彩票的模拟生成和兑奖。 三、实验指导 1．实验描述 模拟36选7的中国体育彩票。从1～36这36个数中随机取出7个数作为一张彩票 的号码，随机生成若干张彩票，并和指定的中奖号码(设有7个号码)进行比较，判断中奖情况。 2．实验分析 一张彩票的号码可以用一个线性表表示，因其长度是固定的，故可用顺序表表示，这里我们称其为彩票号码表。 随机生成彩票，最直接的方法就是产生l～36间的随机数。若该数不在彩票号码表 中，则将其插入到彩票号码表中；否则，舍弃该数。重复产生随机数，直至彩票号码表 中的号码个数达到指定的个数7。 显然，上面的方法中产生随机数的次数是不确定的，因为可能有重复的数，显然该算法的效率较低。 彩票生成的另一种方法是：备选数是一个集合，该集合也可以采用线性表表示，只是元素间的顺序可以随意指定，我们不妨称其为备选数表，备选数表初始状态含有l～36这36个数。根据备选数表的长度产生一个随机数，用该随机数作为位置序号，将备选数表中该位置的数作为彩票的一个号码，将其从备选数表中删除，并插入到彩票号码表中。重复这一操作，每次都能得到一个不同的号码，所以循环指定的次数(一张彩票中号码的个数)即可得到一张彩票。 备选数表的初始化，备选数表初始状态含有1～36这36个数，元素间的顺序没有意义。为了提高初始化的效率，不用每次生成彩票前重新初始化备选数表中的各个分量，当选定备选数表中的一个元素作为彩票的一个号码时，将该号码插入到彩票号码表中，并将其从备选数表中删除。删除元素时，不将其后的所有元素依次前移，而只是将被删除元素与备选数表当前的最后一个元素互换，备选数表的长度减1即可。这样，被选数表的删除操作简化了，同时备选数表的初始化操作也简化了。 判断中奖情况，就是先初始化猜对号码个数为0，再依次用中奖号码表中的每个号码，在一张彩票号码表中查找，若有，猜对号码个数加1。处理完毕，猜对号码个数即可反映中奖情况。 3．解决方案 (1)彩票号码表、备选数表的存储结构类型定义 #define MM 7 /*彩票中号码的个数*/ #define NN 36 /*选数的个数*/ typedef int ElemTp; /*元素类型*/ typedef struct { ElemTp elem[MM+1]; int len; /*表长*/ } VoteTp; /*彩票号码表的类型*/ typedef struct { ElmTp elem[NN+1]; int len; /*表长*/ } sourceTp; /*备选数表的类型*/ (2)主要算法 彩票的生成方法、判断彩票的中奖情况的N-S图，如图1.1、图1.2所示。 图1.1 彩票的生成方法 图1.2 判断彩票的中奖情况 票的生成方法、判断彩票的中奖情况的C语言程序如下。 VoteTp CreateAVote() /* 生成一张彩票vote*/ { VoteTp vote; ElemTp k,temp; int i; InitializeVote(vote); source.len=NN; /*初始化备选数表source*/ for(i=1;i=MM;i++) { k= rand() % source.len+1; /* 将source.elem[k]插入到彩票号码表vote中 , 产生一个l到source.len的随机数k */ SeqInsertVote(vote,vote.len+1,source.elem[k]); /*将备选数表source中的第k个元素删掉，Source.el em[k]与source.elem[source.len]交换，将备选数表表长source.1en减l */ temp=source.elem[k]; source.elem[k]=source.elem[source.len]; source.elem[source.len]=temp; source.len=source.len-1; } return vote; } int RightNum(VoteTp vote,VoteTp answervo