用游戏串起程序员的基本功（一）
用游戏串起程序员的基本功（一）
2004-03-23■作者：潇潇■出处： YESKY
其实做一个程序员要学很多专业知识，有些知识既枯燥又繁杂,让人头疼，所以我们就用大家喜爱的小游戏来串起我们的课程。愿你学的愉快。
这一篇我们将用大家熟知的一种游戏——麻将，来给大家示范一下数据结构这门课的用处。由于笔者的水平有限，文章不可能太深入，旨在抛砖引玉。同时有不正确的地方也恳请各位大虾给于指正。
书归正传，我们先来分析一下麻将游戏的整个流程。
首先，当玩家开局时要在内存中分出136个整型数组空间，来存放136张麻将牌。然后，用136个整型数来代表136张牌，并将个张牌随机分配到前面分出的136个整型数组空间。这样，整个麻将牌就洗好了。
接着，我们可以用1到6的随机数代表榖子,并随着数的变化而显示不同点数的图片。以时间或次数来决定停止的时刻，最后得到的数字就是玩家所掷出的点数，之后就可以用这个数来确定发牌的位置。
然后，就是发牌了。在这里我们可以在建立两个长度为13的整型数组空间，以分别存储两个玩家手中的牌。
接下来就是最有意思的地方了，也就是玩牌的过程了。先比较对家打出的牌是否可以吃、碰、杠、胡，都没有，就从剩下的牌中一张张的分到每个该摸牌的玩家手中，并计算是否为胡牌，如果是，就提示玩家并让玩家决定是否胡牌；如果不是，就等玩家出牌后，根据是否是同一种牌并按大小顺序排列好。重复这一过程，直到有人胡牌，游戏结束。
游戏的流程我们分析完了，怎么实现呢？这也是我们这篇教程的重点。一定好打起精神呀！
我们先来看看游戏的第一个流程是怎样实现的。在文章的开始，我谈到了数组（就是具有同一数据类型的，并且位置连续的数据存储空间），用c语言我们可以这样实现。
int pai[136]；// 注意c语言中数组是从0~135
那么怎么洗牌呢？通常的思路是用rand（）来产生1~136之间的整型数，并按顺序放入我们刚才分配的用来存放麻将牌的数组空间中。为了不出现重复的数值，可以用产生的新数和前面已放入数组的数比较，如果重复就在从新分配，不重复就放入数组中。
下面是实现这一过程的代码。
Void xipai()
{
int temp;
temp=(int ) 135*rand()/32565+1;
for （int i=o；i<136;i++）//按顺序比较136个数组空间
{
if(i=o)
pai[i]=temp; //第一个数直接放入数组
else
for(int j=o ;j<i;j++) //和前面放入数组的数比较
{
if( pai[j]==temp) //有重复的
xipai(); //从新取数比较
else
pai[i]=temp; //没重复的,放入数组
}//end for
}//end for
}//end xipai
在上面的代码中,我们使用了递归的方法,可以说它的效率是比较低的。一方面适应为递归本身对空间的要求,另一方面,就在于这个算法中,要进行多次的比较。举个较极端的例子，如果我们每次取得一个随机整型数都是在前面已经存放过的，那么就要一直从新取数并比较。当然这种可能性极少，但当数组存放有一半以上的数后，这种事情发生的可能性就会成指数的增长。
这里我再介绍一种新的方法。前一种算法的弊处在于可能会有重复的数，而进行多次的取数和比较。我们换个思路，就是随机产生0到135的数组位置，按顺序把1~136的数按得到的数存放到相应的数组位置。有人可能会说，难道位置就不会有重复吗？别急，我们继续往下看。
我们知道，c语言中对于一个int（整型）数，默认的初始化值是0，所以，我们只要在按顺序比较0到135个数组空间，那些值为0，就可以将数放入其中。这样就保证了不会出现重复的数，而且效率也比前一种方法要高。（大家可以思考一下为什么？我也会在后面给以解答）
下面是这种算法的源代码：
void xipai（）
{
for (int i=1 ; i<=136; i++) //这是要放入的136个整型数
{
int a= (int)135 * rand()/32767+1; //随机产生位置
if(pai[a]==0) //判断此位置是否为空
{
pai[a]=i; //空，放入其中
}
else //不空
{
for(int j=0;j<=135;j++) //比较所有数组空间
{
if(pai[j]==0) //找到空闲的位置
pai[j]=i; //放入其中
}//end for
}// end if
} //end for
}//end xipai
这种算法之所以比前一种效率高，原因就在于他即使每次得到的位置都不为空，也顶多搜索136遍，而前一种算法是最坏的可能是想不出的糟糕的。
