一、需求分析描述
1、針對實現整個過程需要多步，不同步驟中各個事物所處位置不同的情況，可定義乙個結構體來實現對四個物件狼、羊、白菜和農夫的表示。對於起始岸和目的岸，可以用0或者1來表示，以實現在程式設計中的簡便性。
2、題目要求給出四種事物的過河步驟，沒有對先後順序進行約束，這就需要給各個事物依次進行編號，然後依次試探，若試探成功，進行下一步試探。這就需要使用迴圈或者遞迴演算法，避免隨機盲目運算且保證每種情況均試探到。
3、題目要求求出農夫帶乙隻羊，一條狼和一顆白菜過河的辦法，所以依次成功返回運算結果後，需要繼續運算，直至求出結果，即給出農夫的過河方案。
4、輸出介面要求具有每一步中農夫所帶物件及每步之後各岸的物體，需要定義不同的陣列來分別儲存上述內容，並使介面所示方案清晰簡潔。
二、系統架構設計
1．設計中首先涉及的就是資料型別的定義，首先，定義乙個結構體用來存放農夫、狼、羊、白菜的資訊。
具體定義為：struct condition
;定義了乙個結構體陣列condition conditions[100]，定義狀態陣列用來記錄他們過河的狀態0：起始岸；1：目的岸;
程式中定義的char action100陣列用來存放各個物件以及人過河或返回的說明語句。
2．程式中定義的子函式有：
2.1 將狼帶到目的岸以及帶回起始岸的函式takewolfover（）和takewolfback（）；
takewolfover（）函式中將conditions[i+1].wolf=1，白菜、羊的狀態不變，同時要有action[i]=" take wolf over."將狼帶到目的岸語句；
takewolfback（）函式中將conditions[i+1].wolf=0， 白菜、羊的狀態不變，同時要有action[i]=" take wolf back."將狼帶回起始岸語句。
2.2 將羊帶到目的岸以及帶回起始岸的函式takesheepover（）和takesheepback（）；
takesheepover（）函式中將conditions[i+1].sheep=1，白菜、狼的狀態不變，同時要有action[i]=" take sheep over."將羊帶到目的岸語句；
takesheepback（）函式中將conditions[i+1].sheep=0， 白菜、狼的狀態不變，同時要有action[i]=" take sheep back."將羊帶回起始岸語句。
2.3 將白菜帶到目的岸以及帶回起始岸的函式takecabbageover和takecabbageback（）；
takecabbageover（）函式中將conditions[i+1].cabbage=1，羊、狼的狀態不變，同時要有action[i]=" take cabbage over."將白菜帶到目的岸語句。
takecabbageback（）；函式中將conditions[i+1].cabbage=0， 羊、狼的狀態不變，同時要action[i]=" take cabbage back."將白菜帶回起始岸語句。
2.4 getoverbarely（）函式是用來完成乙個人單獨過河的操作，呼叫該函式時action[i]=" get over barely."賦值人單獨回到目的岸，狼、羊、白菜的狀態保持不變。
2.5 getbackbarely（）函式是用來完成乙個人單獨回到起始岸的操作，呼叫該函式時action[i]=" get back barely."賦值人單獨回起始岸，狼、羊、白菜的狀態保持不變。
2.6 輸出過河的每乙個步驟以及完成每一步之後人、狼、羊、白菜的狀態這一動作是由showresult（）函式來完成的，
2.7 tryonestep是本次設計的核心程式，上面提到的所有子程式之間都是相互獨立的，但是在tryonestep函式中都要呼叫上面的子函式。
3．程式流程圖：
3.1 主函式的流程圖如下：
圖1. 主函式的流程
3.2tryonestep函式工作的流程圖如下：
圖函式的流程
三、系統實現過程
編寫好各個子程式後，在main（）函式中首先將人，狼，羊，白菜的初始狀態都置為0，接下來呼叫tryonestep（）函式，同時0作為實參傳給tryonestep（）函式。
1． tryonestep（）函式實現過程如下：
1.1 首先，定義兩個int型變數c，j。
1.2接下來判斷四者的狀態是否都為1，若都為1說明已經過河成功了，之後呼叫showresult（）函式，輸出相關資訊，在由return返回到呼叫處。程式執行結束。
1.3再判斷是否有非法情況出現，即：羊單獨和白菜在一起或狼和羊單獨在一起，具體實現的語句if(conditions[i].
farmer!=conditions[i].wolf&&conditions[i].
wolf==conditions[i].sheep||
conditions[i].farmer!=conditions[i].
sheep&&conditions[i].sheep==conditions[i].cabbage)
如果條件成立的話執行if語句即執行return 返回到呼叫點，否則，向下繼續執行。
1.4 再通過 for(c=0;c 判斷是否有重複狀態
1.5 j=i+1
1.6判斷conditions[i].farmer是否為0，如果不為0，則跳轉到（1.
10）接著執行；若為0，則設定為1，呼叫getoverbarely(i)，接著tryonestep(j)，呼叫tryonestep(j)時就是重複執行整個呼叫過程，直到其中有條件不成立時跳到該呼叫處。
1.7 執行1.6以後跳回到呼叫點後，接著判斷狼是否還未過河。
即conditions[i].wolf==0是否成立，成立則呼叫takewolfover(i)，再執行tryonestep(j)遞迴呼叫自身但實參已發生變化，直到退回到該呼叫處，就繼續向下執行；若狼已經過河就執行1.9。
1.8判斷羊是否還未過河。 即conditions[i].
sheep==0是否成立，若過河，則就執行1.9；未過河，則呼叫takesheepover(i)，再執行tryonestep(j)。
1.9最後判斷白菜是否已經過河，未過河則呼叫takecabbageover(i)，再tryonestep(j)，完成呼叫後回到該呼叫處。
1.10若開始conditions[i].farmer=1，則從1.
10這裡就開始執行，先將conditions[i].farmer設定為0，接著呼叫getbackbarely(i)，後執行tryonestep(j)，遞迴呼叫，直到退回該處，接著向下執行。
1.11順序執行conditions[i].wolf==1若成立就執行 takewolfback(i)後tryonestep(j)，直到退回到該呼叫處，若不成立就直接向下執行。
1.12順序執行conditions[i].sheep==1若成立就執行 takesheepback(i)後tryonestep(j)，直到退回到該呼叫處，若不成立就直接向下執行。
1.13順序執行conditions[i].cabbage==1若成立就執行 takecabbageback(i)後tryonestep(j)，直到退回到該呼叫處，若不成立就直接向下執行。
2. 主函式呼叫關係如下：
圖3.函式呼叫關係
4、總結和體會
1.剛開始在判斷每一種是否安全時走得有點麻煩：開始把每種狀態都列出來逐個判斷，可時間複雜度較大，經過考慮只要判斷兩大類即可，第一種是農夫和羊一塊，然後再分析其他兩種物體的狀態。
第二種是兩者不在一起，然後再分析其他兩種物體的狀態。這樣可以很快找出安全狀態而且降低了時間複雜度。
2.對本次實驗，我得到：以前用c或c++程式設計，只是注重如何編寫函式能夠完成所需要的功能，似乎沒有明確的戰術，只是憑藉單純的意識和簡單的語句來堆砌一段程式。
但現在學了《資料結構》後，變成完全不同啦，在編寫乙個程式之前，自己綜合考慮各種因素，首先選取自己需要的資料結構，然後選一種或幾種儲存結構來具體決定後面的函式主要風格。
3.這次用狀態回溯演算法，其中主要是遞迴，以前都不敢用這個，這次嘗試著，一步一步都克服啦，這都是很大進步。
5、參考文獻
（1）嚴蔚敏吳偉民 ,資料結構（c語言版） 清華大學出版社 2011.7
（2）徐孝凱資料結構使用教程清華大學出版社 1999.12
6、開發環境
vc6.0
7、源**
#include""
int main()
{ cout<<" 資料結構課程設計"< cout<<< cout<<" 農夫過河"< conditions[0].farmer=0;
資料結構課程設計
指導書山東建築大學 電腦科學與技術學院 二 六年十二月 課程設計基本情況 課程名稱 資料結構課程設計 相關課程 c語言程式設計 visual c 程式設計 資料結構 適合專業 電腦科學與技術 網路工程 軟體工程 設計週數 2周 學分 2學分 開課學期 第4學期 開課單位 電腦科學與技術學院 一 課程...
資料結構課程設計
總結報告 專業軟體工程 班級軟體1007 學號 20103540 姓名 日期 2012.9.17 東北大學軟體學院 第一章需求分析 問題定義 實現乙個網上拍賣系統，根據需求描述和附加的框架 完成乙個網上拍賣系統。分析 整個系統執行於windows平台，是基於b s結構的商業應用程式，程式為使用者提供...
資料結構課程設計
環境與測繪學院 1 c 物件導向程式設計基礎 實驗簡介 學會用演算法語言c 描述抽象資料型別。理解資料結構的組成分為兩部分，第一部分是資料集 資料元素 第二部分是在此資料集上的操作。從物件導向的觀點看，這兩部分代表了物件的屬性和方法。掌握用c 描述資料結構的基本方法，即通過建立類來描述抽象資料型別。...