數(shù)據(jù)結(jié)構(gòu)中棧在過河問題中的應(yīng)用

李橙　李海燕　丁國(guó)棟

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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個(gè)壞人，N個(gè)好人過河，只有1條船，這條船每次只能至多只能載2個(gè)人過河（包括開船的），船開過了河還要有一個(gè)人把船開回來。在船的兩岸壞人數(shù)量不能多于好人，否則壞人會(huì)欺負(fù)好人。要怎樣將3個(gè)好人和3個(gè)壞人平安送達(dá)對(duì)岸。

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

2 核心算法思想

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

6 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

[8] 韓家煒.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(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].北京：機(jī)械工業(yè)出版社，1996.