李橙　李海燕　丁國棟

摘要：棧是數(shù)據(jù)結(jié)構(gòu)中的一種基本而重要的存儲結(jié)構(gòu)。棧是一種限定僅在一段進行插入與刪除操作的線性表，插入或刪除是限定在表尾進行的，我們通常將表尾稱之為棧頂。相反的，將表頭端稱之為棧底。在棧中，先插入的元素被壓在棧底，最后才能出棧，所以棧也被稱為后進先出表。因而，實際應(yīng)用中，凡是符合后進先出的問題，我們都可以用堆棧來處理和實現(xiàn)。棧的典型應(yīng)用包括：遞歸函數(shù)的調(diào)用，進制轉(zhuǎn)換，括號比配問題，背包問題，中綴表達式求值等等。過河問題是一個非常經(jīng)典的智力問題，很多競賽中都使用過這個題材，該文中我們將討論棧對于過河問題的應(yīng)用。

關(guān)鍵詞：棧；數(shù)據(jù)結(jié)構(gòu)；計算機編程；過河問題

中圖分類號：TP311 文獻標(biāo)識碼：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個人過河（包括開船的），船開過了河還要有一個人把船開回來。在船的兩岸壞人數(shù)量不能多于好人，否則壞人會欺負好人。要怎樣將3個好人和3個壞人平安送達對岸。

問題分析：在此，我們假定共有3個壞人3個好人（M=3、N=3），原本這6個人在左岸，要到右岸去，對問題進行具體分析。由于船上只能一次載2個人，因而每次過河共有5種方案供選擇：1個壞人一個好人；兩個壞人；兩個好人；一個壞人；一個好人。我們可以使用試探法，用這5種方案輪流進行過河流程，并計算兩岸剩下的好人與壞人人數(shù)，如果符合規(guī)定，就保留這個方案，否則嘗試其他方案，直到6個人順利過河。

2 核心算法思想

在此我們定義結(jié)構(gòu)體包含4個成員：好人個數(shù)，壞人個數(shù)，船的狀態(tài)（左岸、右岸），以及已經(jīng)嘗試的乘船方案（共5種方案）。輪流嘗試5種過河方案，使用堆棧保存正確的方案步驟，同時計算兩岸好人與壞人個數(shù)，如果不符合壞人不多于好人的規(guī)則，則彈出棧中已經(jīng)保存的方案步驟，否則如果符合壞人不多于好人的規(guī)則，則繼續(xù)嘗試方案尋找下一過河方案。如此反復(fù)一直到6個人正確到達右岸。

6 結(jié)束語

筆者在《數(shù)據(jù)結(jié)構(gòu)》的教學(xué)過程發(fā)現(xiàn)學(xué)生在學(xué)習(xí)了第二章線性表后學(xué)習(xí)棧和隊列結(jié)構(gòu)時常常會將幾種表結(jié)構(gòu)混淆，但在學(xué)習(xí)了幾種結(jié)構(gòu)的應(yīng)用后大大加強了大家對于幾種結(jié)構(gòu)的理解和區(qū)分。而其中，棧的應(yīng)用是最豐富最有趣的。從簡單的穿衣服脫衣服，到生活中的洗碗操作，再到復(fù)雜的迷宮問題，九連環(huán)問題無一不論證了棧結(jié)構(gòu)的有趣之處。學(xué)生們厭惡枯燥的各種機構(gòu)定義，但對豐繁的現(xiàn)實應(yīng)用非常感興趣，如何引導(dǎo)學(xué)生，激發(fā)他們的興趣，從而調(diào)動他們的學(xué)習(xí)積極性，提高他們的主觀能動性是我在教授數(shù)據(jù)結(jié)構(gòu)這門比較復(fù)雜而枯燥的專業(yè)課時常常思考的問題。

參考文獻：

[1] 譚浩強.C語言程序設(shè)計教程[M].北京：高等教育出版社，1991.

[2] 張俊妮.數(shù)據(jù)挖掘與應(yīng)用[M].北京：北京大學(xué)出版社，2009.

[3] 李志剛.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘的原理及應(yīng)用[M].北京：高等教育出版社，2008.

[4] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2007.

[5] 陳文偉.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程[M].北京：清華大學(xué)出版社，2009.

[6] 黃明.21世紀(jì)進階輔導(dǎo)C語言程序設(shè)計[M].大連：大連理工大學(xué)出版社，2005.

[7] 馬靖善.C語言程序設(shè)計[M].北京：清華大學(xué)出版社，2005.2.

[8] 韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機械工業(yè)出版社，2007.3.

[9] 許卓群，唐世渭.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，1988.1.

[10] 李廉治，姜文清，郭福順.數(shù)據(jù)結(jié)構(gòu)[M].大連：大連理工大學(xué)出版社，1989.

[11] 晉良潁.數(shù)據(jù)結(jié)構(gòu)[M].北京：人民郵電出版社，2002.

[12] 魏榮.數(shù)據(jù)結(jié)構(gòu)[M].北京：機械工業(yè)出版社，1996.