第 2 章 栈、队列、链表

第 2 章 栈、队列、链表

第 1 节 解密QQ号——队列

新学期开始了,小哈是小哼的新同桌(小哈是个小美女哦~),小哼向小哈询问QQ号,小哈当然不会直接告诉小哼啦,原因嘛你懂的。所以小哈给了小哼一串加密过的数字,同时小哈也告诉了小哼解密规则。规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,再将第5个数删除……直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一起就是小哈的QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。

OK,现在轮到你动手的时候了。快去找出9张便签或小纸片,将“6 3 1 7 5 8 9 2 4”这9个数分别写在9张便签上,模拟一下解密过程。如果你没有理解错解密规则的话,解密后小哈的QQ号应该是“6 1 5 9 4 7 2 8 3”。

其实解密的过程就像是将这些数“排队”。每次从最前面拿两个,第1个扔掉,第2个放到尾部。具体过程是这样的:刚开始这串数是“6 3 1 7 5 8 9 2 4”,首先删除6并将3放到这串数的末尾,这串数更新为“1 7 5 8 9 2 4 3”。接下来删除1并将7放到末尾,即更新为“5 8 9 2 4 3 7”。再删除5并将8放到末尾即“9 2 4 3 7 8”,删除9并将2放到末尾即“4 3 7 8 2”,删除4并将3放到末尾即“7 8 2 3”,删除7并将8放到末尾即“2 3 8”,删除2并将3放到末尾即“8 3”,删除8并将3放到末尾即“3”,最后删除3。因此被删除的顺序是“6 1 5 9 4 7 2 8 3”,这就是小哈的QQ号码了,你可以加她试试看^_^。

既然现在已经搞清楚了解密法则,不妨自己尝试一下去编程,我相信你一定可以写出来的。

首先需要一个数组来存储这一串数即int q[101],并初始化这个数组即int q[101]= {0,6,3,1,7,5,8,9,2,4};(此处初始化是我多写了一个0,用来填充q[0],因为我比较喜欢从q[1]开始用,对数组初始化不是很理解的同学可以去看一下我的上本书《啊哈C!思考快你一步》)。接下来就是模拟解密的过程了。

解密的第一步是将第一个数删除,你可以想一下如何在数组中删除一个数呢。最简单的方法是将所有后面的数都往前面挪动一位,将前面的数覆盖。就好比我们在排队买票,最前面的人买好离开了,后面所有的人就需要全部向前面走一步,补上之前的空位,但是这样的做法很耗费时间。

{%}

在这里,我将引入两个整型变量head和tail。head用来记录队列的队首(即第一位),tail用来记录队列的队尾(即最后一位)的下一个位置。你可能会问:为什么tail不直接记录队尾,却要记录队尾的下一个位置呢?这是因为当队列中只剩下一个元素时,队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时,队列为空。

现在有9个数,9个数全部放入队列之后head=1,tail=10,此时head和tail之间的数就是目前队列中“有效”的数。如果要删除一个数的话,就将head++就OK了,这样仍然可以保持head和tail之间的数为目前队列中“有效”的数。这样做虽然浪费了一个空间,却节省了大量的时间,这是非常划算的。新增加一个数也很简单,把需要增加的数放到队尾即q[tail]之后再tail++就OK啦。

我们来小结一下,在队首删除一个数的操作是head++;。

{%}

在队尾增加一个数(假设这个数是x)的操作是q[tail]=x;tail++;。

{%}

整个解密过程,请看下面这个霸气外漏的图。

{%}

最后的输出就是6 1 5 9 4 7 2 8 3,代码实现如下。

#include <stdio.h>
int main()
{
    int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail;
    int i;
    //初始化队列
    head=1;
    tail=10; //队列中已经有9个元素了,tail指向队尾的后一个位置
    while(head<tail) //当队列不为空的时候执行循环
    {
        //打印队首并将队首出队
        printf("%d ",q[head]);
        head++;

        //先将新队首的数添加到队尾
        q[tail]=q[head];
        tail++;
        //再将队首出队
        head++;
    }

    getchar();getchar();
    return 0;
}

怎么样,上面的代码运行成功没有?现在我们再来总结一下队列的概念。队列是一种特殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为“出队”,而在队列的尾部(tail)进行插入操作,这称为“入队”。当队列中没有元素时(即head==tail),称为空队列。在我们的日常生活中有很多情况都符合队列的特性。比如我们之前提到过的买票,每个排队买票的窗口就是一个队列。在这个队列当中,新来的人总是站在队列的最后面,来得越早的人越靠前,也就越早能买到票,就是先来的人先服务,我们称为“先进先出”(First In First Out,FIFO)原则。

队列将是我们今后学习广度优先搜索以及队列优化的Bellman-Ford最短路算法的核心数据结构。所以现在将队列的三个基本元素(一个数组,两个变量)封装为一个结构体类型,如下。

struct queue
{
    int data[100];//队列的主体,用来存储内容
    int head;//队首
    int tail;//队尾
};

上面定义了一个结构体类型,我们通常将其放在main函数的外面,请注意结构体的定义末尾有个;号。struct是结构体的关键字,queue是我们为这个结构体起的名字。这个结构体有三个成员分别是:整型数组data、整型head和整型tail。这样我们就可以把这三个部分放在一起作为一个整体来对待。你可以这么理解:我们定义了一个新的数据类型,这个新类型非常强大,用这个新类型定义出的每一个变量可以同时存储一个整型数组和两个整数。

{%}

有了新的结构体类型,如何定义结构体变量呢?很简单,这与我们之前定义变量的方式是一样的,具体做法如下。

struct queue q;

请注意struct queue需要整体使用,不能直接写queue q;。这样我们就定义了一个结构体变量q。这个结构体变量就可以满足队列的所有操作了。那又该如何访问结构体变量的内部成员呢?可以使用.号,它叫做成员运算符或者点号运算符,如下:

q.head=1;
q.tail=1;
scanf("%d",&q.data[q.tail]);

好了,下面这段代码就是使用结构体来实现的队列操作。

#include <stdio.h>
struct queue
{
    int data[100];//队列的主体,用来存储内容
    int head;//队首
    int tail;//队尾
};

int main()
{
    struct queue q;
    int i;
    //初始化队列
    q.head=1;
    q.tail=1;
    for(i=1;i<=9;i++)
    {
        //依次向队列插入9个数
        scanf("%d",&q.data[q.tail]);
        q.tail++;
    }

    while(q.head<q.tail) //当队列不为空的时候执行循环
    {
        //打印队首并将队首出队
        printf("%d ",q.data[q.head]);
        q.head++;

        //先将新队首的数添加到队尾
        q.data[q.tail]=q.data[q.head];
        q.tail++;
        //再将队首出队
        q.head++;
    }

    getchar();getchar();
    return 0;
}

上面的这种写法看起来虽然冗余了一些,但是可以加强你对队列这个算法的理解。C++的STL库已经有队列的实现,有兴趣的同学可以参看相关材料。队列的起源已经无法追溯。在还没有数字计算机之前,数学应用中就已经有对队列的记载了。我们生活中队列的例子也比比皆是,比如排队买票,又或者吃饭时候用来排队等候的叫号机,又或者拨打银行客服选择人工服务时,每次都会被提示“客服人员正忙,请耐心等待”,因为客服人员太少了,拨打电话的客户需要按照打进的时间顺序进行等候等等。这里表扬一下肯德基的宅急送,没有做广告的嫌疑啊,每次一打就通,基本不需要等待。但是我每次打银行的客服(具体是哪家银行就不点名了)基本都要等待很长时间,总是告诉我“正在转接,请稍候”,嘟嘟嘟三声后就变成“客服正忙,请耐心等待!”然后就给我放很难听的曲子。看来钱在谁那里谁就是老大啊……

第 2 节 解密回文——栈

上一节中我们学习了队列,它是一种先进先出的数据结构。还有一种是后进先出的数据结构,它叫做栈。栈限定为只能在一端进行插入和删除操作。比如说有一个小桶,小桶的直径只能放一个小球,我们现在小桶内依次放入2、1、3号小球。假如你现在需要拿出2号小球,那就必须先将3号小球拿出,再拿出1号小球,最后才能将2号小球拿出来。在刚才取小球的过程中,我们最先放进去的小球最后才能拿出来,最后放进去的小球却可以最先拿出来。

生活中也有很多这样的例子,比如我们在吃桶装薯片的时候,要想吃掉最后一片,就必须把前面的全部吃完(貌似现在的桶装薯片为了减少分量,在桶里面增加了一个透明的抽屉);再比如浏览网页的时候需要退回到之前的某个网页,我们需要一步步地点击后退键。还有手枪的弹夹,在装子弹的时候,最后装入的那发子弹,是被第一个打出去的。栈的实现也很简单,只需要一个一维数组和一个指向栈顶的变量top就可以了。我们通过top来对栈进行插入和删除操作。

栈究竟有哪些作用呢?我们来看一个例子。“xyzyx”是一个回文字符串,所谓回文字符串就是指正读反读均相同的字符序列,如“席主席”、“记书记”、“aha”和“ahaha”均是回文,但“ahah”不是回文。通过栈这个数据结构我们将很容易判断一个字符串是否为回文。

首先我们需要读取这行字符串,并求出这个字符串的长度。

char a[101];
int len;
gets(a);
len=strlen(a);

如果一个字符串是回文的话,那么它必须是中间对称的,我们需要求中点,即:

mid=len/2-1;

接下来就轮到栈出场了。

我们先将mid之前的字符全部入栈。因为这里的栈是用来存储字符的,所以这里用来实现栈的数组类型是字符数组即char s[101];,初始化栈很简单,top=0;就可以了。入栈的操作是top++; s[top]=x; (假设需要入栈的字符暂存在字符变量x中),其实可以简写为s[++top]=x;。

现在我们就来将mid之前的字符依次全部入栈。

for(i=0;i<=mid;i++)
{
    s[++top]=a[i];
}

接下来进入判断回文的关键步骤。将当前栈中的字符依次出栈,看看是否能与mid之后的字符一一匹配,如果都能匹配则说明这个字符串是回文字符串,否则这个字符串就不是回文字符串。

for(i=mid+1;i<=len-1;i++)
{
    if (a[i]!=s[top])
    {
          break;
    }
    top--;
}
if(top==0)
    printf("YES");
else
    printf("NO");

最后如果top的值为0,就说明栈内所有的字符都被一一匹配了,那么这个字符串就是回文字符串。完整的代码如下。

#include <stdio.h>
#include <string.h>
int main()
{
    char a[101],s[101];
    int i,len,mid,next,top;

    gets(a); //读入一行字符串
    len=strlen(a); //求字符串的长度
    mid=len/2-1; //求字符串的中点

    top=0;//栈的初始化
    //将mid前的字符依次入栈
    for(i=0;i<=mid;i++)
        s[++top]=a[i];

    //判断字符串的长度是奇数还是偶数,并找出需要进行字符匹配的起始下标
    if(len%2==0)
        next=mid+1;
    else
        next=mid+2;

    //开始匹配
    for(i=next;i<=len-1;i++)
    {
        if(a[i]!=s[top])
            break;
        top--;
    }

    //如果top的值为0,则说明栈内所有的字符都被一一匹配了
    if(top==0)
        printf("YES");
    else
        printf("NO");

    getchar();getchar();
    return 0;
}

可以输入以下数据进行验证。

ahaha

运行结果是:

YES

栈还可以用来进行验证括号的匹配。比如输入一行只包含“()[]{}”的字符串,请判断形如“([{}()])”或者“{()[]{}}”的是否可以正确匹配。显然上面两个例子都是可以正确匹配的。“([)]”是不能匹配的。有兴趣的同学可以自己动手来试一试。

栈最早由Alan M. Turing(艾伦·图灵)于1946年提出,当时是为了解决子程序的调用和返回。艾伦·图灵这个大帅哥可是个大牛人,图灵奖就是以他的名字命名的。如果你对他感兴趣不妨去读一读《艾伦·图灵传:如谜的解谜者》和《图灵的秘密》。

第 3 节 纸牌游戏——小猫钓鱼

星期天小哼和小哈约在一起玩桌游,他们正在玩一个非常古怪的扑克游戏——“小猫钓鱼”。游戏的规则是这样的:将一副扑克牌平均分成两份,每人拿一份。小哼先拿出手中的第一张扑克牌放在桌上,然后小哈也拿出手中的第一张扑克牌,并放在小哼刚打出的扑克牌的上面,就像这样两人交替出牌。出牌时,如果某人打出的牌与桌上某张牌的牌面相同,即可将两张相同的牌及其中间所夹的牌全部取走,并依次放到自己手中牌的末尾。当任意一人手中的牌全部出完时,游戏结束,对手获胜。

假如游戏开始时,小哼手中有6张牌,顺序为2 4 1 2 5 6,小哈手中也有6张牌,顺序为3 1 3 5 6 4,最终谁会获胜呢?现在你可以拿出纸牌来试一试。接下来请你写一个程序来自动判断谁将获胜。这里我们做一个约定,小哼和小哈手中牌的牌面只有1~9。

我们先来分析一下这个游戏有哪几种操作。小哼有两种操作,分别是出牌和赢牌。这恰好对应队列的两个操作,出牌就是出队,赢牌就是入队。小哈的操作和小哼是一样的。而桌子就是一个栈,每打出一张牌放到桌上就相当于入栈。当有人赢牌的时候,依次将牌从桌上拿走,这就相当于出栈。那如何解决赢牌的问题呢?赢牌的规则是:如果某人打出的牌与桌上的某张牌相同,即可将两张牌以及中间所夹的牌全部取走。那如何知道桌上已经有哪些牌了呢?最简单的方法就是枚举桌上的每一张牌,当然也有更好的办法我们待会再说。OK,小结一下,我们需要两个队列、一个栈来模拟整个游戏。

首先我们先来创建一个结构体用来实现队列,如下。

struct queue
{
    int data[1000];
    int head;
    int tail;
};

上面代码中head用来存储队头,tail用来存储队尾。数组data用来存储队列中的元素,数组data的大小我预设为1000,其实应该设置得更大一些,以防数组越界。当然对于本题的数据来说1000已经足够了。

再创建一个结构体用来实现栈,如下。

struct stack
{
    int data[10];
    int top;
};

其中top用来存储栈顶,数组data用来存储栈中的元素,大小设置为10。因为只有9种不同的牌面,所以桌上最多可能有9张牌,因此数组大小设置为10就够了。提示一下:为什么不设置为9呢?因为C语言数组下标是从0开始的。

接下来我们需要定义两个队列变量q1和q2。q1用来模拟小哼手中的牌,q2用来模拟小哈手中的牌。定义一个栈变量s用来模拟桌上的牌。

struct queue  q1,q2;
struct stack  s;

接下来来初始化一下队列和栈。

//初始化队列q1和q2为空,此时两人手中都还没有牌
q1.head=1; q1.tail=1;
q2.head=1; q2.tail=1;
//初始化栈s为空,最开始的时候桌上也没有牌
s.top=0;

接下来需要读入小哼和小哈最初时手中的牌,分两次读入,每次读入6个数,分别插入q1和q2中。

//先读入6张牌,放到小哼手上
for(i=1;i<=6;i++)
{
    scanf("%d",&q1.data[q1.tail]); //读入一个数到队尾
    q1.tail++;//队尾往后挪一位
}
//再读入6张牌,放到小哈手上
for(i=1;i<=6;i++)
{
    scanf("%d",&q2.data[q2.tail]); //读入一个数到队尾
    q2.tail++;//队尾往后挪一位
}

现在准备工作已经基本上做好了,游戏正式开始,小哼先出牌。

t=q1.data[q1.head]; //小哼先亮出一张牌

小哼打出第一张牌,也就是q1的队首,我们将这张牌存放在临时变量t中。接下来我们要判断小哼当前打出的牌是否能赢得桌上的牌。也就是判断桌上的牌与t有没有相同的,如何实现呢?我们需要枚举桌上的每一张牌与t进行比对,具体如下:

flag=0;
for(i=1;i<=s.top;i++)
{
    if(t==s.data[i]) { flag=1; break; }
}

如果flag的值为0就表明小哼没能赢得桌上的牌,将打出的牌留在桌上。

if(flag==0)
{
    //小哼此轮没有赢牌
    q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队
    s.top++;
    s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
}

如果flag的值为1就表明小哼可以赢得桌上的牌,需要将赢得的牌依次放入小哼的手中。

f(flag==1)
{
    //小哼此轮可以赢牌
    q1.head++;//小哼已经打出一张牌,所以要把打出的牌出队
    q1.data[q1.tail]=t; //因为此轮可以赢牌,所以紧接着把刚才打出的牌又放到手中牌的末尾
    q1.tail++;
    while(s.data[s.top]!=t) //把桌上可以赢得的牌(从当前桌面最顶部一张牌开始取,直至取到与打出的牌相同为止)依次放到手中牌的末尾
    {
          q1.data[q1.tail]=s.data[s.top]; //依次放入队尾
          q1.tail++;
          s.top--; //栈中少了一张牌,所以栈顶要减1
    }
}

小哼出牌的所有阶段就模拟完了,小哈出牌和小哼出牌是一样的。接下来我们要判断游戏如何结束。即只要两人中有一个人的牌用完了游戏就结束了。因此需要在模拟两人出牌代码的外面加一个while循环来判断,如下。

while(q1.head<q1.tail && q2.head<q2.tail ) //当队列q1和q2都不为空的时候执行循环

最后一步,输出谁最终赢得了游戏,以及游戏结束后获胜者手中的牌和桌上的牌。如果小哼获胜了那么小哈的手中一定没有牌了(队列q2为空),即q2.head==q2.tail,具体输出如下。

if(q2.head==q2.tail)
{
    printf("小哼win\n");
    printf("小哼当前手中的牌是");
    for(i=q1.head;i<=q1.tail-1;i++)
        printf(" %d",q1.data[i]);
    if(s.top>0) //如果桌上有牌则依次输出桌上的牌
    {
        printf("\n桌上的牌是");
        for(i=1;i<=s.top;i++)
            printf(" %d",s.data[i]);
    }
    else
        printf("\n桌上已经没有牌了");
    }
}

反之,小哈获胜,代码的实现也是差不多的,就不再赘述了。到此,所有的代码实现就都讲完了。

在上面我们讲解的所有实现中,每个人打出一张牌后,判断能否赢牌这一点可以优化。之前我们是通过枚举桌上的每一张牌来实现的,即用了一个for循环来依次判断桌上的每一张牌是否与打出的牌相等。其实有更好的办法来解决这个问题,就是用一个数组来记录桌上有哪些牌。因为牌面只有1~9,因此只需开一个大小为10的数组来记录当前桌上已经有哪些牌面就可以了。

int book[10];

这里我再一次使用了book这个单词,因为这个单词有记录、登记的意思,而且单词拼写简洁。另外很多国外的算法书籍在处理需要标记问题的时候也都使用book这个单词,因此我这里就沿用了。当然你也可以使用mark等你自己觉得好理解的单词啦。下面需要将数组book[1]~book[9]初始化为0,因为刚开始桌面上一张牌也没有。

for(i=1;i<=9;i++)
    book[i]=0;

接下来,如果桌面上增加了一张牌面为2的牌,那就需要将book[2]设置为1,表示牌面为2的牌桌上已经有了。当然如果这张牌面为2的牌被拿走后,需要及时将book[2]重新设置为0,表示桌面上已经没有牌面为2的牌了。这样一来,寻找桌上是否有与打出的牌牌面相同的牌,就不需要再循环枚举桌面上的每一张牌了,而只需用一个if判断即可。这一点是不是有点像第1章第1节的桶排序的方法呢?具体如下。

t=q1.data[q1.head]; //小哼先亮出一张牌
if(book[t]==0) // 表明桌上没有牌面为t的牌
{
        //小哼此轮没有赢牌
    q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队
    s.top++;
    s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
    book[t]=1; //标记桌上现在已经有牌面为t的牌
}

OK,算法的实现讲完了,下面给出完整的代码,如下:

#include <stdio.h>
struct queue
{
    int data[1000];
    int head;
    int tail;
};

struct stack
{
    int data[10];
    int top;
};

int main()
{
    struct queue q1,q2;
    struct stack s;
    int book[10];
    int i,t;

    //初始化队列
    q1.head=1; q1.tail=1;
    q2.head=1; q2.tail=1;
    //初始化栈
    s.top=0;
    //初始化用来标记的数组,用来标记哪些牌已经在桌上
    for(i=1;i<=9;i++)
        book[i]=0;

    //依次向队列插入6个数
    //小哼手上的6张牌
    for(i=1;i<=6;i++)
    {
        scanf("%d",&q1.data[q1.tail]);
        q1.tail++;
    }
    //小哈手上的6张牌
    for(i=1;i<=6;i++)
    {
        scanf("%d",&q2.data[q2.tail]);
        q2.tail++;
    }
    while(q1.head<q1.tail && q2.head<q2.tail ) //当队列不为空的时候执行循环
    {
        t=q1.data[q1.head];//小哼出一张牌
        //判断小哼当前打出的牌是否能赢牌
        if(book[t]==0) //表明桌上没有牌面为t的牌
        {
            //小哼此轮没有赢牌
            q1.head++; //小哼已经打出一张牌,所以要把打出的牌出队
            s.top++;
            s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
            book[t]=1; //标记桌上现在已经有牌面为t的牌
        }
        else
        {
            //小哼此轮可以赢牌
            q1.head++;//小哼已经打出一张牌,所以要把打出的牌出队
            q1.data[q1.tail]=t;//紧接着把打出的牌放到手中牌的末尾
            q1.tail++;
            while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾
            {
              book[s.data[s.top]]=0;//取消标记
                q1.data[q1.tail]=s.data[s.top];//依次放入队尾
                q1.tail++;
                s.top--; //栈中少了一张牌,所以栈顶要减1
            }
            //收回桌上牌面为t的牌
            book[s.data[s.top]]=0;
            q1.data[q1.tail]=s.data[s.top];
            q1.tail++;
            s.top--;
        }
        if(q1.head==q1.tail) break;//小哼手中的牌如果已经打完,游戏结束

        t=q2.data[q2.head]; //小哈出一张牌
        //判断小哈当前打出的牌是否能赢牌
        if(book[t]==0) //表明桌上没有牌面为t的牌
        {
            //小哈此轮没有赢牌
            q2.head++; //小哈已经打出一张牌,所以要把打出的牌出队
            s.top++;
            s.data[s.top]=t; //再把打出的牌放到桌上,即入栈
            book[t]=1; //标记桌上现在已经有牌面为t的牌
        }
        else
        {
            //小哈此轮可以赢牌
            q2.head++;//小哈已经打出一张牌,所以要把打出的牌出队
            q2.data[q2.tail]=t;//紧接着把打出的牌放到手中牌的末尾
            q2.tail++;
            while(s.data[s.top]!=t) //把桌上可以赢得的牌依次放到手中牌的末尾
            {
                book[s.data[s.top]]=0;//取消标记
                q2.data[q2.tail]=s.data[s.top];//依次放入队尾
                q2.tail++;
                s.top--;
            }
            //收回桌上牌面为t的牌
            book[s.data[s.top]]=0;
            q2.data[q2.tail]=s.data[s.top];
            q2.tail++;
            s.top--;
        }
    }

    if(q2.head==q2.tail)
    {
        printf("小哼win\n");
        printf("小哼当前手中的牌是");
        for(i=q1.head;i<=q1.tail-1;i++)
            printf(" %d",q1.data[i]);
        if(s.top>0) //如果桌上有牌则依次输出桌上的牌
        {
            printf("\n桌上的牌是");
            for(i=1;i<=s.top;i++)
                printf(" %d",s.data[i]);
        }
        else
            printf("\n桌上已经没有牌了");
    }
    else
    {
        printf("小哈win\n");
        printf("小哈当前手中的牌是");
        for(i=q2.head;i<=q2.tail-1;i++)
            printf(" %d",q2.data[i]);
        if(s.top>0) //如果桌上有牌则依次输出桌上的牌
        {
            printf("\n桌上的牌是");
            for(i=1;i<=s.top;i++)
                printf(" %d",s.data[i]);
        }
        else
            printf("\n桌上已经没有牌了");
    }

    getchar();getchar();
    return 0;
}

可以输入以下数据进行验证。

2 4 1 2 5 6
3 1 3 5 6 4

运行结果是:

小哈win
小哈当前手中的牌是 1 6 5 2 3 4 1
桌上的牌是 3 4 5 6 2

接下来你需要自己设计一些测试数据来检验你的程序。在设计测试数据的时候你要考虑各种情况,包括各种极端情况。通过设计测试数据来检测我们的程序是否“健壮”是非常重要的,如果你的程序可以通过任何一组测试数据,才表示你的程序是完全正确的。

如果你设计一些测试数据来验证的话,会发现我们刚才的代码其实还是有问题的。比如游戏可能无法结束。就是小哼和小哈可以永远玩下去,谁都无法赢得对方所有的牌。请你自己想一想如何解决游戏无法结束的问题。

第 4 节 链表

在存储一大波数的时候,我们通常使用的是数组,但有时候数组显得不够灵活,比如下面这个例子。

有一串已经从小到大排好序的数2 3 5 8 9 10 18 26 32。现需要往这串数中插入6使其得到的新序列仍符合从小到大排列。如我们使用数组来实现这一操作,则需要将8和8后面的数都依次往后挪一位,如下:

{%}

这样操作显然很耽误时间,如果使用链表则会快很多。那什么是链表呢?请看下图。

{%}

此时如果需要在8前面插入一个6,就只需像下图这样更改一下就可以了,而无需再将8及后面的数都依次往后挪一位。是不是很节省时间呢?

{%}

那么如何实现链表呢?在C语言中可以使用指针和动态分配内存函数malloc来实现。指针?天啊!如果你在学习C语言的时候没有搞懂指针,或者还不知道指针是啥,不要紧,我们现在就回顾一下指针。指针其实超级简单。如果你已经对指针和malloc了如指掌则可以跳过下面这一小段,继续往后看。

先看下面两行语句。

int a;
int *p;

第一行我们很熟悉了,就是定义一个整型变量a。第二行你会发现在p前面多了一个*号,这就表示定义了一个整型指针变量p。即定义一个指针,只需在变量前面加一个*号就OK啦。

接下来,指针有什么作用呢?答案是:存储一个地址。确切地说是存储一个内存空间的地址,比如说整型变量a的地址。严格地说这里的指针p也只能存储“一个存放整数的内存空间”的地址,因为在定义的时候我们已经限制了这一点(即定义的时候*p的前面是int)。当然你也可以定义一个只能用来存储“一个存放浮点数的内存空间”的地址,例如:

double *p;

简单地说,指针就是用来存储地址的。你可能要问:不就是存储地址嘛,地址不都一样吗,为什么还要分不同类型的指针呢?不要着急,待会后面再解释。接下来需要解决的一个问题:整型指针p如何才能存储整型变量a的地址呢?很简单,如下:

p=&a;

&这个符号很熟悉吧,就是经常在scanf函数中用到的&。&叫取地址符。这样整型指针p就获得了(存储了)整型变量a的地址,我们可以形象地理解整型指针p指向了整型变量a。p指向了a之后,有什么用呢?用处就是我们可以用指针p来操作变量a了。比如我们可以通过操作指针p来输出变量a的值,如下:

#include <stdio.h>
int main()
{
    int a=10;
    int *p; //定义一个指针p
    p=&a; //指针p获取变量a的地址
    printf("%d",*p); //输出指针p所指向的内存中的值

    getchar();getchar();
    return 0;
}

运行结果是:

10

这里printf语句里面*p中的*号叫做间接访问运算符,作用是取得指针p所指向的内存中的值。在C语言中*号有三个用途,分别是:

  1. 乘号,用做乘法运算,例如5*6。
  2. 声明一个指针,在定义指针变量时使用,例如int *p;。
  3. 间接访问运算符,取得指针所指向的内存中的值,例如printf("%d",*p);。

到目前为止,你可能还是觉得指针没啥子实际作用,好好的变量a想输出是的话直接printf("%d",a); 不完了,没事搞个什么指针啊,多此一举。嗯,到目前为止貌似是这样的 O(∩_∩)O哈哈~~不要着急,真枪实弹地来了。

回想一下,我们想在程序中存储一个整数10,除了使用int a;这种方式在内存中申请一块区域来存储,还有另外一种动态存储方法。

malloc(4);

malloc函数的作用就是从内存中申请分配指定字节大小的内存空间。上面这行代码就申请了4个字节。如果你不知道int类型是4个字节的,还可以使用sizeof(int)获取int类型所占用的字节数,如下:

malloc(sizeof(int));

现在你已经成功地从内存中申请了4个字节的空间来准备存放一个整数,可是如何来对这个空间进行操作呢?这里我们就需要用一个指针来指向这个空间,即存储这个空间的首地址。

int *p;
p=(int *)malloc(sizeof(int));

需要注意,malloc函数的返回类型是 void * 类型。void * 表示未确定类型的指针。在C和C++中,void * 类型可以强制转换为任何其他类型的指针。上面代码中我们将其强制转化为整型指针,以便告诉计算机这里的4个字节作为一个整体用来存放整数。还记得我们之前遗留了一个问题:指针就是用来存储内存地址的,为什么要分不同类型的指针呢?因为指针变量存储的是一个内存空间的首地址(第一个字节的地址),但是这个空间占用了多少个字节,用来存储什么类型的数,则是由指针的类型来标明的。这样系统才知道应该取多少个连续内存作为一个数据。

OK,现在我们可以通过指针p对刚才申请的4个字节的空间进行操作了,例如我们向这个空间中存入整数10,如下:

*p=10;

完整代码如下,注意当在程序中使用malloc函数时需要用到stdlib.h头文件。

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int *p; //定义一个指针p
    p=(int *)malloc(sizeof(int)); //指针p获取动态分配的内存空间地址
    *p=10; //向指针p所指向的内存空间中存入10
    printf("%d",*p); //输出指针p所指向的内存中的值

    getchar();getchar();
    return 0;
}

运行结果是:

10

到这里你可能要问:为什么要用这么复杂的办法来存储数据呢?因为之前的方法,我们必须预先准确地知道所需变量的个数,也就是说我们必须定义出所有的变量。比如我们定义了100个整型变量,那么程序就只能存储100个整数,如果现在的实际情况是需要存储101个,那必须修改程序才可以。如果有一天你写的软件已经发布或者交付使用,却发现要存储1000个数才行,那就不得不再次修改程序,重新编译程序,发布一个新版本来代替原来的。而有了malloc函数我们便可以在程序运行的过程中根据实际情况来申请空间。

啰嗦了半天,总算介绍完了什么是指针以及如何动态申请空间。注意,本节接下来的代码对于还没有理解指针的朋友来说可能不太容易,不要紧,如果你痛恨指针,大可直接跳过下面的内容直接进入下一节。下一节中我将介绍链表的另外一种实现方式——数组模拟链表。

首先我们来看一下,链表中的每一个结点应该如何存储。

{%}

每一个结点都由两个部分组成。左边的部分用来存放具体的数值,那么用一个整型变量就可以;右边的部分需要存储下一个结点的地址,可以用指针来实现(也称为后继指针)。这里我们定义一个结构体类型来存储这个结点,如下。

struct node
{
    int data;
    struct node *next;
};

{%}

上面代码中,我们定义了一个叫做node的结构体类型,这个结构体类型有两个成员。第一个成员是整型data,用来存储具体的数值;第二个成员是一个指针,用来存储下一个结点的地址。因为下一个结点的类型也是struct node,所以这个指针的类型也必须是struct node * 类型的指针。

如何建立链表呢?首先我们需要一个头指针head指向链表的最开始。当链表还没有建立的时候头指针head为空(也可以理解为指向空结点)。

struct node *head;
head = NULL;//头指针初始为空

现在我们来创建第一个结点,并用临时指针p指向这个结点。

struct node *p;
//动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点
p=(struct node *)malloc(sizeof(struct node));

接下来分别设置新创建的这个结点的左半部分和右半部分。

scanf("%d",&a);
p->data=a;//将数据存储到当前结点的data域中
p->next=NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空

{%}

上面的代码中我们发现了一个很奇怪的符号“->” 。->叫做结构体指针运算符,也是用来访问结构体内部成员的。因为此处p是一个指针,所以不能使用.号访问内部成员,而要使用->。

下面来设置头指针并设置新创建结点的*next指向空。头指针的作用是方便以后从头遍历整个链表。

if(head==NULL)
    head=p;//如果这是第一个创建的结点,则将头指针指向这个结点
else
    q->next=p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点

如果这是第一个创建的结点,则将头指针指向这个结点。

{%}

如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点。

{%}

最后要将指针q也指向当前结点,因为待会儿临时指针p将会指向新创建的结点。

q=p;//指针q也指向当前结点

完整代码如下。

#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型
struct node
{
    int data;
    struct node *next;
};

int main()
{
    struct node *head,*p,*q,*t;
    int i,n,a;
    scanf("%d",&n);
    head = NULL;//头指针初始为空
    for(i=1;i<=n;i++)//循环读入n个数
    {
        scanf("%d",&a);
        //动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点
        p=(struct node *)malloc(sizeof(struct node));
        p->data=a;//将数据存储到当前结点的data域中
        p->next=NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空
        if(head==NULL)
            head=p;//如果这是第一个创建的结点,则将头指针指向这个结点
        else
            q->next=p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点

        q=p;//指针q也指向当前结点
    }

    //输出链表中的所有数
    t=head;
    while(t!=NULL)
    {
        printf("%d ",t->data);
        t=t->next;//继续下一个结点
    }

    getchar();getchar();
    return 0;
}

需要说明的一点是:上面这段代码没有释放动态申请的空间,虽然没有错误,但是这样会很不安全,有兴趣的朋友可以去了解一下free命令。

可以输入以下数据进行验证。

9
2 3 5 8 9 10 18 26 32

运行结果是:

2 3 5 8 9 10 18 26 32

接下来需要往链表中插入6,操作如下。

{%}

首先用一个临时指针t从链表的头部开始遍历。

t=head;//从链表头部开始遍历

等到指针t的下一个结点的值比6大的时候,将6插入到中间。即t->next->data大于6时进行插入,代码如下。

scanf("%d",&a);//读入待插入的数
while(t!=NULL)//当没有到达链表尾部的时候循环
{
    if(t->next==NULL || t->next->data > a)
    //如果当前结点是最后一个节点或者下一个结点的值大于待插入数的时候插入
    {
        p=(struct node *)malloc(sizeof(struct node));//动态申请一个空间,用来存放新增结点
        p->data=a;
        p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
        t->next=p;//当前结点的后继指针指向新增结点
        break;//插入完毕退出循环
    }
    t=t->next;//继续下一个结点
}

完整代码如下。

#include <stdio.h>
#include <stdlib.h>

//这里创建一个结构体用来表示链表的结点类型
struct node
{
    int data;
    struct node *next;
};

int main()
{
    struct node *head,*p,*q,*t;
    int i,n,a;
    scanf("%d",&n);
    head = NULL;//头指针初始为空
    for(i=1;i<=n;i++)//循环读入n个数
    {
        scanf("%d",&a);
        //动态申请一个空间,用来存放一个结点,并用临时指针p指向这个结点
        p=(struct node *)malloc(sizeof(struct node));
        p->data=a;//将数据存储到当前结点的data域中
        p->next=NULL;//设置当前结点的后继指针指向空,也就是当前结点的下一个结点为空
        if(head==NULL)
            head=p;//如果这是第一个创建的结点,则将头指针指向这个结点
        else
            q->next=p;//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点
        q=p;//指针q也指向当前结点
    }

    scanf("%d",&a);//读入待插入的数
    t=head;//从链表头部开始遍历
    while(t!=NULL)//当没有到达链表尾部的时候循环
    {
        if(t->next==NULL || t->next->data > a)
        //如果当前结点是最后一个节点或者下一个结点的值大于待插入数的时候插入
        {
            p=(struct node *)malloc(sizeof(struct node));//动态申请一个空间,用来存放新增结点
            p->data=a;
            p->next=t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
            t->next=p;//当前结点的后继指针指向新增结点
            break;//插入完毕退出循环
        }
        t=t->next;//继续下一个结点
    }

    //输出链表中的所有数
    t=head;
    while(t!=NULL)
    {
        printf("%d ",t->data);
        t=t->next;//继续下一个结点
    }

    getchar();getchar();
    return 0;
}

可以输入以下数据进行验证。

9
2 3 5 8 9 10 18 26 32
6

运行结果是:

2 3 5 6 8 9 10 18 26 32

第 5 节 模拟链表

如果你觉得上一节的代码简直是天书,或者你压根就很讨厌指针这些东西,没关系!链表还有另外一种使用数组来实现的方式,叫做模拟链表,我们一起来看看。

链表中的每一个结点只有两个部分。我们可以用一个数组data来存储每序列中的每一个数。那每一个数右边的数是谁,这一点该怎么解决呢?上一节中是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了,具体怎么做呢?

{%}

上图的两个数组中,第一个整型数组data是用来存放序列中具体数字的,另外一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组data中位置的。例如right[1]的值为2,就表示当前序列中1号元素右边的元素存放在data[2]中;如果是0,例如right[9]的值为0,就表示当前序列中9号元素的右边没有元素。

现在需要在8前面插入一个6,只需将6直接存放在数组data的末尾即data[10]=6。接下来只需要将right[3]改为10,表示新序列中3号元素右边的元素存放在data[10]中。再将right[10]改为4,表示新序列中10号元素右边的元素存放在data[4]中。这样我们通过right数组就可以从头到尾遍历整个序列了(序列的每个元素的值存放在对应的数组data中),如下。

{%}

完整的代码实现如下。

#include <stdio.h>
int main()
{
    int data[101],right[101];
    int i,n,t,len;
    //读入已有的数
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&data[i]);
    len=n;
    //初始化数组right
    for(i=1;i<=n;i++)
    {
        if(i!=n)
            right[i]=i+1;
        else
            right[i]=0;
    }
    //直接在数组data的末尾增加一个数
    len++;
    scanf("%d",&data[len]);

    //从链表的头部开始遍历
    t=1;
    while(t!=0)
    {
        if(data[right[t]]>data[len])//如果当前结点下一个结点的值大于待插入数,将数插入到中间
        {
            right[len]=right[t];//新插入数的下一个结点标号等于当前结点的下一个结点编号
            right[t]=len;//当前结点的下一个结点编号就是新插入数的编号
            break;//插入完成跳出循环
        }
        t=right[t];
    }
    //输出链表中所有的数
    t=1;
    while(t!=0)
    {
        printf("%d ",data[t]);
        t=right[t];
    }

    getchar();
    getchar();
    return 0;
}

可以输入以下数据进行验证。

9
2 3 5 8 9 10 18 26 32
6

运行结果是:

2 3 5 6 8 9 10 18 26 32

使用模拟链表也可以实现双向链表和循环链表,大家可以自己来试一试。

目录