数据结构中栈在过河问题中的应用

李橙　李海燕　丁国栋

摘要：栈是数据结构中的一种基本而重要的存储结构。栈是一种限定仅在一段进行插入与删除操作的线性表，插入或删除是限定在表尾进行的，我们通常将表尾称之为栈顶。相反的，将表头端称之为栈底。在栈中，先插入的元素被压在栈底，最后才能出栈，所以栈也被称为后进先出表。因而，实际应用中，凡是符合后进先出的问题，我们都可以用堆栈来处理和实现。栈的典型应用包括：递归函数的调用，进制转换，括号比配问题，背包问题，中缀表达式求值等等。过河问题是一个非常经典的智力问题，很多竞赛中都使用过这个题材，该文中我们将讨论栈对于过河问题的应用。

关键词：栈；数据结构；计算机编程；过河问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）31-7279-03

Abstract： Stack is a basic and important storage of data structure. Stack is a limit for the insert table of linear and delete operations in only one paragraph， insert or delete is defined in the rear， we usually set the table tail call stack top. On the contrary， the header end called the bottom of stack. On the stack， first insert the element is pressed on the bottom of the stack， and finally to the stack， so the stack is also called the LIFO list.Therefore， in practical application， in line with all the LIFO problem， we can be used to deal with the stack and the implementation. Including the typical application stack： a recursive function calls， hexadecimal conversion，parentheses matching problem， knapsack problem， infix expression etc..Crossiong river is a very classic intellectual problem， lots of competition use this subject， in this paper， we will discuss the application stack for acrossing river problem.

Key words： stack；data structure； computer programming；crossing river problem

1 问题描述与分析

问题描述如下：M个坏人，N个好人过河，只有1条船，这条船每次只能至多只能载2个人过河（包括开船的），船开过了河还要有一个人把船开回来。在船的两岸坏人数量不能多于好人，否则坏人会欺负好人。要怎样将3个好人和3个坏人平安送达对岸。

问题分析：在此，我们假定共有3个坏人3个好人（M=3、N=3），原本这6个人在左岸，要到右岸去，对问题进行具体分析。由于船上只能一次载2个人，因而每次过河共有5种方案供选择：1个坏人一个好人；两个坏人；两个好人；一个坏人；一个好人。我们可以使用试探法，用这5种方案轮流进行过河流程，并计算两岸剩下的好人与坏人人数，如果符合规定，就保留这个方案，否则尝试其他方案，直到6个人顺利过河。

2 核心算法思想

在此我们定义结构体包含4个成员：好人个数，坏人个数，船的状态（左岸、右岸），以及已经尝试的乘船方案（共5种方案）。轮流尝试5种过河方案，使用堆栈保存正确的方案步骤，同时计算两岸好人与坏人个数，如果不符合坏人不多于好人的规则，则弹出栈中已经保存的方案步骤，否则如果符合坏人不多于好人的规则，则继续尝试方案寻找下一过河方案。如此反复一直到6个人正确到达右岸。

6 结束语

笔者在《数据结构》的教学过程发现学生在学习了第二章线性表后学习栈和队列结构时常常会将几种表结构混淆，但在学习了几种结构的应用后大大加强了大家对于几种结构的理解和区分。而其中，栈的应用是最丰富最有趣的。从简单的穿衣服脱衣服，到生活中的洗碗操作，再到复杂的迷宫问题，九连环问题无一不论证了栈结构的有趣之处。学生们厌恶枯燥的各种机构定义，但对丰繁的现实应用非常感兴趣，如何引导学生，激发他们的兴趣，从而调动他们的学习积极性，提高他们的主观能动性是我在教授数据结构这门比较复杂而枯燥的专业课时常常思考的问题。

参考文献：

[1] 谭浩强.C语言程序设计教程[M].北京：高等教育出版社，1991.

[2] 张俊妮.数据挖掘与应用[M].北京：北京大学出版社，2009.

[3] 李志刚.数据仓库与数据挖掘的原理及应用[M].北京：高等教育出版社，2008.

[4] 严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2007.

[5] 陈文伟.数据仓库与数据挖掘教程[M].北京：清华大学出版社，2009.

[6] 黄明.21世纪进阶辅导C语言程序设计[M].大连：大连理工大学出版社，2005.

[7] 马靖善.C语言程序设计[M].北京：清华大学出版社，2005.2.

[8] 韩家炜.数据挖掘概念与技术[M].北京：机械工业出版社，2007.3.

[9] 许卓群，唐世渭.数据结构[M].北京：高等教育出版社，1988.1.

[10] 李廉治，姜文清，郭福顺.数据结构[M].大连：大连理工大学出版社，1989.

[11] 晋良颍.数据结构[M].北京：人民邮电出版社，2002.

[12] 魏荣.数据结构[M].北京：机械工业出版社，1996.