实验一-线性表的应用

实验一线性表的应用（一）——体育彩票的模拟生成和兑奖一、实验目的与要求熟悉线性表数据结构的定义及顺序存储，会使用线性表的基本操作解决一些实际问题。二、实验内容用线性表实现体育彩票的模拟生成和兑奖。三、实验指导1．实验描述模拟36选7的中国体育彩票。从1～36这36个数中随机取出7个数作为一张彩票的号码，随机生成若干张彩票，并和指定的中奖号码(设有7个号码)进行比较，判断中奖情况。2．实验分析一张彩票的号码可以用一个线性表表示，因其长度是固定的，故可用顺序表表示，这里我们称其为彩票号码表。随机生成彩票，最直接的方法就是产生l～36间的随机数。若该数不在彩票号码表中，则将其插入到彩票号码表中；否则，舍弃该数。重复产生随机数，直至彩票号码表中的号码个数达到指定的个数7。显然，上面的方法中产生随机数的次数是不确定的，因为可能有重复的数，显然该算法的效率较低。彩票生成的另一种方法是：备选数是一个集合，该集合也可以采用线性表表示，只是元素间的顺序可以随意指定，我们不妨称其为备选数表，备选数表初始状态含有l～36这36个数。根据备选数表的长度产生一个随机数，用该随机数作为位置序号，将备选数表中该位置的数作为彩票的一个号码，将其从备选数表中删除，并插入到彩票号码表中。重复这一操作，每次都能得到一个不同的号码，所以循环指定的次数(一张彩票中号码的个数)即可得到一张彩票。备选数表的初始化，备选数表初始状态含有1～36这36个数，元素间的顺序没有意义。为了提高初始化的效率，不用每次生成彩票前重新初始化备选数表中的各个分量，当选定备选数表中的一个元素作为彩票的一个号码时，将该号码插入到彩票号码表中，并将其从备选数表中删除。删除元素时，不将其后的所有元素依次前移，而只是将被删除元素与备选数表当前的最后一个元素互换，备选数表的长度减1即可。这样，被选数表的删除操作简化了，同时备选数表的初始化操作也简化了。判断中奖情况，就是先初始化猜对号码个数为0，再依次用中奖号码表中的每个号码，在一张彩票号码表中查找，若有，猜对号码个数加1。处理完毕，猜对号码个数即可反映中奖情况。3．解决方案(1)彩票号码表、备选数表的存储结构类型定义#defineMM7/*彩票中号码的个数*/#defineNN36/*选数的个数*/typedefintElemTp;/*元素类型*/typedefstruct{ElemTpelem[MM+1];intlen;/*表长*/}VoteTp;/*彩票号码表的类型*/typedefstruct{ElmTpelem[NN+1];intlen;/*表长*/}sourceTp;/*备选数表的类型*/(2)主要算法彩票的生成方法、判断彩票的中奖情况的N-S图，如图1.1、图1.2所示。图1.1彩票的生成方法图1.2判断彩票的中奖情况票的生成方法、判断彩票的中奖情况的C语言程序如下。VoteTpCreateAVote()/*生成一张彩票vote*/{VoteTpvote;ElemTpk,temp;inti;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.elem[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;}returnvote;}intRightNum(VoteTpvote,VoteTpanswervote)/*判断彩票的中奖情况*/{/*一张彩票vote和中奖号码表answervote相比，求出并返回猜对的号码个数*/inti,k;k=0;for(i=1;i=MM;i++)if(SeqLocate(vote,answervote.elem[i])0)k++;return(k);}(3)程序#includestdio.h#includestdlib.h#includetime.h#includemath.h#define_CRT_RAND_S//为了使用rand()函数#defineMM7#defineNN36typedefintElemTp;typedefstruct{ElemTpelem[MM+1];intlen;}VoteTp;typedefstruct{ElemTpelem[NN+1];intlen;}SourceTp;SourceTpsource;voidInitializeVote(VoteTp*vote);voidInitializeSource(SourceTp*source);voidSeqInsertVote(VoteTp*vote,inti,ElemTpx);intSeqLocate(VoteTpv,ElemTpx);VoteTpCreateAVote();intRightNum(VoteTpvote,VoteTpanswervote);voidmain(){VoteTpvote;VoteTpanswervote;intk,i;InitializeSource(&source);/*初始化备选数表Source：放入36个数，将表长置为36*/answervote=CreateAVote();/*生成一组中奖号码*/printf(\nPressAnyKeytocontinue,0toexit!);printf(\n中奖号码:);for(i=1;i=MM;i++)printf(%3d,answervote.elem[i]);printf(\n你的彩票编码:\n);while(getchar()!='0'){vote=CreateAVote();for(i=1;i=MM;i++)printf(%-2d,vote.elem[i]);k=RightNum(vote,answervote);printf(----%d\n,k);}}voidInitializeVote(VoteTp*vote){vote-len=0;}voidInitializeSource(SourceTp*Source){/*初始化备选数表Source，在表中放入1～36共36个数，将表长置为36*/inti;for(i=1;i=NN;i++)Source-elem[i]=i;Source-len=NN;}intSeqLocate(VoteTpv,ElemTpx){/*在顺序表v中查找值为x的元素，返回该元素的位置序号，没有时返回0*/}voidSeqInsertVote(VoteTp*vote,inti,ElemTpx){/*在顺序表*p的第i个数据元素之前插入数据元素x*/VoteTpv;intj;v=*vote;if((i1)||(iv.len+1))printf(errornumber!);else{}*vote=v;}(4)实验测试数据及运行结果：（请记录）4．结果分析与讨论本案例使用顺序表较好地解决了彩票的随机生成、兑奖等操作。这一类问题在我们的当今生活中很常见，如福利彩票、体育彩票、各种有奖竞猜等。对于处理这些问题，本案例的方法有很好的借鉴价值。当然，没有存储本案例中的彩票，这相当于即开即奖。也可以定义数组或顺序表存储这些彩票，待开奖后再处理每张彩票的中奖情况，并可进行统计分析等。5.思考与练习①若每次根据用户的要求生成指定数目的彩票，如何实现算法和程序?②若中奖号码表已经有序，如何修改判断彩票中奖情况的算法，以提高效率?③若要求彩票号码表有序，如何修改彩票的生成算法?