數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉樹的建立與遍歷

1、課程設(shè)計(jì)指導(dǎo)教師評(píng)定成績(jī)表項(xiàng)目分值優(yōu)秀(100x90)良好(90x80)中等(80x70)及格(70x60)不及格(x60)評(píng)分參考標(biāo)準(zhǔn)參考標(biāo)準(zhǔn)參考標(biāo)準(zhǔn)參考標(biāo)準(zhǔn)參考標(biāo)準(zhǔn)學(xué)習(xí)態(tài)度15學(xué)習(xí)態(tài)度認(rèn)真，科學(xué)作風(fēng)嚴(yán)謹(jǐn)，嚴(yán)格保證設(shè)計(jì)時(shí)間并按任務(wù)書中規(guī)定的進(jìn)度開展各項(xiàng)工作學(xué)習(xí)態(tài)度比較認(rèn)真，科學(xué)作風(fēng)良好，能按期圓滿完成任務(wù)書規(guī)定的任務(wù)學(xué)習(xí)態(tài)度尚好，遵守組織紀(jì)律，基本保證設(shè)計(jì)時(shí)間，按期完成各項(xiàng)工作學(xué)習(xí)態(tài)度尚可，能遵守組織紀(jì)律，能按期完成任務(wù)學(xué)習(xí)馬虎，紀(jì)律渙散，工作作風(fēng)不嚴(yán)謹(jǐn),不能保證設(shè)計(jì)時(shí)間和進(jìn)度技術(shù)水平與實(shí)際能力25設(shè)計(jì)合理、理論分析與計(jì)算正確，實(shí)驗(yàn)數(shù)據(jù)準(zhǔn)確，有很強(qiáng)的實(shí)際動(dòng)手能力、經(jīng)濟(jì)分析能力和計(jì)算機(jī)應(yīng)用能力

2、，文獻(xiàn)查閱能力強(qiáng)、引用合理、調(diào)查調(diào)研非常合理、可信設(shè)計(jì)合理、理論分析與計(jì)算正確，實(shí)驗(yàn)數(shù)據(jù)比較準(zhǔn)確，有較強(qiáng)的實(shí)際動(dòng)手能力、經(jīng)濟(jì)分析能力和計(jì)算機(jī)應(yīng)用能力，文獻(xiàn)引用、調(diào)查調(diào)研比較合理、可信設(shè)計(jì)合理，理論分析與計(jì)算基本正確，實(shí)驗(yàn)數(shù)據(jù)比較準(zhǔn)確，有一定的實(shí)際動(dòng)手能力，主要文獻(xiàn)引用、調(diào)查調(diào)研比較可信設(shè)計(jì)基本合理，理論分析與計(jì)算無大錯(cuò)，實(shí)驗(yàn)數(shù)據(jù)無大錯(cuò)設(shè)計(jì)不合理，理論分析與計(jì)算有原則錯(cuò)誤，實(shí)驗(yàn)數(shù)據(jù)不可靠，實(shí)際動(dòng)手能力差，文獻(xiàn)引用、調(diào)查調(diào)研有較大的問題創(chuàng)新10有重大改進(jìn)或獨(dú)特見解，有一定實(shí)用價(jià)值有較大改進(jìn)或新穎的見解，實(shí)用性尚可有一定改進(jìn)或新的見解有一定見解觀念陳舊論文(計(jì)算書、圖紙)撰寫質(zhì)量50結(jié)構(gòu)嚴(yán)謹(jǐn)，邏輯性

3、強(qiáng)，層次清晰，語言準(zhǔn)確，文字流暢，完全符合規(guī)范化要求，書寫工整或用計(jì)算機(jī)打印成文；圖紙非常工整、清晰結(jié)構(gòu)合理，符合邏輯，文章層次分明，語言準(zhǔn)確，文字流暢，符合規(guī)范化要求，書寫工整或用計(jì)算機(jī)打印成文；圖紙工整、清晰結(jié)構(gòu)合理，層次較為分明，文理通順，基本達(dá)到規(guī)范化要求，書寫比較工整；圖紙比較工整、清晰結(jié)構(gòu)基本合理，邏輯基本清楚，文字尚通順，勉強(qiáng)達(dá)到規(guī)范化要求；圖紙比較工整內(nèi)容空泛，結(jié)構(gòu)混亂，文字表達(dá)不清，錯(cuò)別字較多，達(dá)不到規(guī)范化要求；圖紙不工整或不清晰指導(dǎo)教師評(píng)定成績(jī)：指導(dǎo)教師簽名： 年 月 日重慶大學(xué)本科學(xué)生課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)題目二叉樹的建立與遍歷學(xué)院軟件學(xué)院專業(yè)軟件工程年級(jí)2009級(jí)已知參

4、數(shù)和設(shè)計(jì)要求：?jiǎn)栴}描述建立一棵二叉樹，并對(duì)其進(jìn)行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果。學(xué)生應(yīng)完成的工作：基本要求 從鍵盤接受輸入（先序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法對(duì)其進(jìn)行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。測(cè)試數(shù)據(jù)abcdegf（其中表示空格字符）則輸出結(jié)果為：先序：abcdegf中序：cbegdfa后序：cgbfdba選作內(nèi)容采用非遞歸算法實(shí)現(xiàn)二叉樹遍歷。目前資料收集情況（含指定參考資料）：1. robert l. kruse編. data structures and program design in c+.高等教育出版社，200

5、1.2.數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏編，清華大學(xué)出版社，2000.3.數(shù)據(jù)結(jié)構(gòu)教程李春葆編，清華大學(xué)出版社，2002.課程設(shè)計(jì)的工作計(jì)劃： 14周：小組成員初步討論選題，制定課程設(shè)計(jì)實(shí)施計(jì)劃15周：實(shí)現(xiàn)選題編碼，初步完成主要編程工作 16周：對(duì)已完成題目的編碼進(jìn)行調(diào)試，撰寫課程設(shè)計(jì)報(bào)告任務(wù)下達(dá)日期 2011年 4 月 23 日完成日期 2011 年 6 月 17 日指導(dǎo)教師 （簽名）學(xué) 生 （簽名）說明：1、學(xué)院、專業(yè)、年級(jí)均填全稱，如：光電工程學(xué)院、測(cè)控技術(shù)、2003。2、本表除簽名外均可采用計(jì)算機(jī)打印。本表不夠，可另附頁，但應(yīng)在頁腳添加頁碼。重慶大學(xué)本科學(xué)生課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)題目飛機(jī)場(chǎng)的模擬學(xué)院軟件

6、學(xué)院專業(yè)軟件工程年級(jí)2009級(jí)已知參數(shù)和設(shè)計(jì)要求：?jiǎn)栴}描述 考慮一個(gè)很繁忙的小型飛機(jī)場(chǎng)，這個(gè)飛機(jī)場(chǎng)只有一條飛機(jī)跑道。在每個(gè)單位時(shí)間內(nèi)，只有一架飛機(jī)可以著陸，或者這有一架飛機(jī)可以起飛，但不允許同時(shí)著陸起飛。學(xué)生應(yīng)完成的工作：基本要求 將所有用于飛機(jī)場(chǎng)模擬的函數(shù)和方法組合成一個(gè)完整的程序。用飛機(jī)場(chǎng)模擬程序作若干次試運(yùn)行試驗(yàn)，調(diào)整準(zhǔn)備著陸和起飛的飛機(jī)數(shù)的期望值，并找出在飛機(jī)不會(huì)被拒絕服務(wù)的條件下這些數(shù)字的盡可能大的近似值。測(cè)試數(shù)據(jù) 找出在飛機(jī)不會(huì)被拒絕服務(wù)的條件下這些數(shù)字的盡可能大的近似值。選作內(nèi)容 修改模擬程序，使飛機(jī)場(chǎng)有三條飛機(jī)跑道，其中一條用于著陸，另一條用于起飛。目前資料收集情況（含指定參考

7、資料）：1. robert l. kruse編. data structures and program design in c+.高等教育出版社，2001.2.數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏編，清華大學(xué)出版社，2000.3.數(shù)據(jù)結(jié)構(gòu)教程李春葆編，清華大學(xué)出版社，2002.課程設(shè)計(jì)的工作計(jì)劃： 14周：小組成員初步討論選題，制定課程設(shè)計(jì)實(shí)施計(jì)劃15周：實(shí)現(xiàn)選題編碼，初步完成主要編程工作 16周：對(duì)已完成題目的編碼進(jìn)行調(diào)試，撰寫課程設(shè)計(jì)報(bào)告任務(wù)下達(dá)日期 2011 年 4 月 23 日完成日期 2011 年 6 月 17 日指導(dǎo)教師 （簽名）學(xué) 生 （簽名）說明：1、學(xué)院、專業(yè)、年級(jí)均填全稱，如：光電工程學(xué)院、測(cè)

8、控技術(shù)、2003。2、本表除簽名外均可采用計(jì)算機(jī)打印。本表不夠，可另附頁，但應(yīng)在頁腳添加頁碼。重慶大學(xué)本科學(xué)生課程設(shè)計(jì)任務(wù)書課程設(shè)計(jì)題目八皇后問題學(xué)院軟件學(xué)院專業(yè)軟件工程年級(jí)2009級(jí)已知參數(shù)和設(shè)計(jì)要求：?jiǎn)栴}描述八皇后問題是一個(gè)以國(guó)際象棋為背景的問題：如何能夠在 88 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無法直接吃掉其他的皇后學(xué)生應(yīng)完成的工作：基本要求 在 88 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無法直接吃掉其他的皇后。為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。 測(cè)試數(shù)據(jù) 在計(jì)算機(jī)上運(yùn)行八皇后程序，編寫尚缺的queens方法；通過引入一個(gè)計(jì)數(shù)器，在

9、solve_from每次啟動(dòng)的時(shí)候遞增此計(jì)數(shù)器，準(zhǔn)確地找出要探查的棋盤位置數(shù) 選作內(nèi)容 用415范圍內(nèi)的皇后數(shù)運(yùn)行程序，嘗試找出一個(gè)數(shù)學(xué)函數(shù)，它作為皇后數(shù)的函數(shù)、目前資料收集情況（含指定參考資料）：1. robert l. kruse編. data structures and program design in c+.高等教育出版社，2001.2.數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏編，清華大學(xué)出版社，2000.3.數(shù)據(jù)結(jié)構(gòu)教程李春葆編，清華大學(xué)出版社，2002.課程設(shè)計(jì)的工作計(jì)劃： 14周：小組成員初步討論選題，制定課程設(shè)計(jì)實(shí)施計(jì)劃15周：實(shí)現(xiàn)選題編碼，初步完成主要編程工作 16周：對(duì)已完成題目的編碼進(jìn)行調(diào)試，

10、撰寫課程設(shè)計(jì)報(bào)告任務(wù)下達(dá)日期 2011 年 4 月 23 日完成日期 2011 年 6 月 17 日指導(dǎo)教師 （簽名）學(xué) 生 （簽名）說明：1、學(xué)院、專業(yè)、年級(jí)均填全稱，如：光電工程學(xué)院、測(cè)控技術(shù)、2003。2、本表除簽名外均可采用計(jì)算機(jī)打印。本表不夠，可另附頁，但應(yīng)在頁腳添加頁碼。摘要隨著軟件技術(shù)的日益普及,程序的代碼量也不斷增大,這就需要合理的數(shù)據(jù)結(jié)構(gòu)來完善程序的編寫。本論文主要利用數(shù)據(jù)結(jié)構(gòu)的知識(shí)解決飛機(jī)場(chǎng)的模擬、八皇后問題和二叉樹的建立于遍歷。針對(duì)飛機(jī)場(chǎng)的模擬問題，主要利用棧的知識(shí)。其算法思想：對(duì)飛機(jī)場(chǎng)的跑道可以被用作起飛或降落。在每個(gè)單位時(shí)間內(nèi),只有一架飛機(jī)可以著陸,或者只有一架飛機(jī)可

11、以起飛,但不允許同時(shí)著陸和起飛。飛機(jī)的到達(dá)和起飛是隨機(jī)的。在單位時(shí)間里,飛機(jī)的降落比起飛優(yōu)先。針對(duì)八皇后問題，我們采用回溯法實(shí)現(xiàn)，其算法思想：從根結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深 方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。 換句話說，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地 在解空間中搜索，直至找到所要求的

12、解或解空間中已沒有活結(jié)點(diǎn)時(shí)為止。針對(duì)二叉樹的建立和遍歷問題，我們以二叉鏈表作為其存儲(chǔ)方式，以前序來建立二叉樹并分別使用二叉樹前序、中序和后序遍歷的遞歸算法來遍歷二叉樹。其算法思想：以前序遍歷二叉樹為例，若二叉樹非空，則依次執(zhí)行如下操作：訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹。對(duì)其左右子樹，使用同樣的方法實(shí)現(xiàn)。關(guān)鍵字： 棧 回溯法 深度優(yōu)先 遞歸 二叉鏈表（一）飛機(jī)場(chǎng)模擬（1）問題描述：考慮一個(gè)很繁忙的小型飛機(jī)場(chǎng)，只有一條飛機(jī)跑道。創(chuàng)建模擬程序以對(duì)飛機(jī)的起降進(jìn)行調(diào)度。將所有用于飛機(jī)場(chǎng)模擬的函數(shù)和方法組合唱一個(gè)完整的程序，有飛機(jī)場(chǎng)模擬程序做若干次試運(yùn)行實(shí)驗(yàn)，調(diào)整準(zhǔn)備著陸和起飛的飛機(jī)數(shù)的期望值，并找出在

13、飛機(jī)不會(huì)被拒絕服務(wù)的條件下這些數(shù)字的盡可能大的近似值。（2）基本要求：在每個(gè)單位時(shí)間內(nèi)，只有一架飛機(jī)可以著陸，或者只有一架飛機(jī)可以起飛，不允許同時(shí)著陸起飛。飛機(jī)的到達(dá)和起飛是隨機(jī)的。在任何給定時(shí)刻，飛機(jī)跑道可能空閑，或可能有一架飛機(jī)正著陸或起飛，并且可能有若干架飛機(jī)等待著陸或起飛。（3）算法思想：跑道可以被用作起飛或降落。在每個(gè)單位時(shí)間內(nèi),只有一架飛機(jī)可以著陸,或者只有一架飛機(jī)可以起飛,但不允許同時(shí)著陸和起飛。飛機(jī)的到達(dá)和起飛是隨機(jī)的。在單位時(shí)間里,飛機(jī)的降落比起飛優(yōu)先。正在等待的飛機(jī)都在 landing 和 takeoff的隊(duì)列中, 他們都具有固定的大小。（4）模塊劃分：plane類：其對(duì)象

14、表示單個(gè)飛機(jī)，包括一個(gè)初始化方法和表示起飛和著陸的方法；并維護(hù)特定的plane對(duì)象的數(shù)據(jù)，包括航班號(hào)、到達(dá)機(jī)場(chǎng)系統(tǒng)的時(shí)間、到達(dá)或者離開的plane狀態(tài)。 random類：random類封裝到達(dá)或離開跑道的飛機(jī)的隨機(jī)特征，將模擬期間的時(shí)間分成單元，使得在任一給定的時(shí)間單元內(nèi)僅有一架飛機(jī)能利用飛機(jī)跑道著陸或起飛。 飛機(jī)跑道runway維護(hù)兩個(gè)飛機(jī)隊(duì)列，稱其為landing和takeoff，用于保存正在等待的飛機(jī)。僅當(dāng)沒有飛機(jī)等待著陸時(shí)才允許起飛。（5）數(shù)據(jù)結(jié)構(gòu)：plane：創(chuàng)建飛機(jī)抽象類型（包含plane（），fly（），land（），refuse（），started（），）runway：創(chuàng)建跑道

15、抽象類型（包含runway（），runwayinitialize（），can_land(),:can_depar(),actvility(),）queue：創(chuàng)建隊(duì)列抽象類型(包含queue（），)random:創(chuàng)建隨機(jī)數(shù)抽象類型（包含random（），random_real()，reseed()，possion()，）（6）源程序：plane類：#include plane.h#include queue.h#include random.h#include runway.h#include #include using namespace std;plane :plane(int flt,i

16、nt time,plane_status status)flt_num = flt;clock_start = time;state = status;coutplane numberfltready to;if(status = arriving)coutland.endl;elsecouttake off.endl;plane:plane()flt_num = -1;clock_start = -1;state = null;void plane:refuse()constcoutplane numberflt_num;if(state = arriving)coutdirected to

17、 another airportendl;elsecouttold to try to take off again laterendl;void plane:land(int time) constint wait = time - clock_start;cout time :plane number flt_numlanded afterwaittime unit(wait =1)?:s)in the takeoff queueendl;void plane:fly(int time)constint wait =time - clock_start;cout time :plane n

18、umber flt_numtook off afterwaittime unit(wait =1)?:s)in the takeoff queueendl;int plane:started()constreturn clock_start;void plane:run_idle(int time)couttime:runway is idleendl;random類：#include #include random.h#include #include random:random(bool peseudo)if(peseudo) seed=1;elseseed = time(null)%in

19、t_max;multiplier = 2743;add_on = 5923;int random:reseed()seed = seed*multiplier + add_on;return seed;double random:random_real()double max = int_max + 1.0;double temp = reseed();if (temp limit)count+;product *=random_real();return count;runway類：#include runway.h#include queue.h#include plane.h#inclu

20、de random.h#include #include using namespace std;runway:runway(int limit)queue_limit = limit;num_land_requests = num_takeoff_requests = 0;num_landings = num_takeoffs = 0;num_land_refused = num_takeoff_refused = 0;num_land_accepted = num_takeoff_accepted = 0;land_wait = takeoff_wait = idle_time = 0;v

21、oid runwayinitialize(int &end_time,int &queue_limit,double &arrival_rate,double &departure_rate)cout this program simulates an airport with only one runway. endl one plane can land or depart in each unit of time. endl;cout up to what number of planes can be waiting to land or take off at any time? q

22、ueue_limit;cout how many units of time will the simulation run? end_time;bool acceptable;do cout expected number of arrivals per unit time? arrival_rate;cout expected number of departures per unit time? departure_rate;if (arrival_rate 0.0 | departure_rate 0.0)cerr these rates must be nonnegative. 1.

23、0)cerr safety warning: this airport will become saturated. endl; while (!acceptable);error_code runway:can_land(plane ¤t)/*post: if possible, the plane current is added to thelanding queue; otherwise, an error_code of overflow isreturned. the runway statistics are updated.uses: class extended_

24、queue.*/error_code result;if (landing.size() queue_limit)result = landing.append(current);elseresult = fail;num_land_requests+;if (result != success)num_land_refused+;elsenum_land_accepted+;return result;error_code runway:can_depart(plane ¤t)/*post: if possible, the plane current is added to t

25、hetakeoff queue; otherwise, an error_code of overflow isreturned. the runway statistics are updated.uses: class extended_queue.*/error_code result;if (takeoffing.size() queue_limit)result = takeoffing.append(current);elseresult = fail;num_takeoff_requests+;if (result != success)num_takeoff_refused+;

26、elsenum_takeoff_accepted+;return result;runway_activity runway:activity(int time, plane &moving)/*post: if the landing queue has entries, its frontplane is copied to the parameter movingand a result land is returned. otherwise,if the takeoff queue has entries, its frontplane is copied to the paramet

27、er movingand a result takeoff is returned. otherwise,idle is returned. runway statistics are updated.uses: class extended_queue.*/runway_activity in_progress;if (!landing.empty() landing.retrive(moving);land_wait += time - moving.started();num_landings+;in_progress = land;landing.serve();else if (!t

28、akeoffing.empty() takeoffing.retrive(moving);takeoff_wait += time - moving.started();num_takeoffs+;in_progress = takeoff;takeoffing.serve();else idle_time+;in_progress = idle;return in_progress;void runway:shut_down(int time) const/*post: runway usage statistics are summarized and printed.*/cout sim

29、ulation has concluded after time time units. endl total number of planes processed (num_land_requests + num_takeoff_requests) endl total number of planes asking to land num_land_requests endl total number of planes asking to take off num_takeoff_requests endl total number of planes accepted for land

30、ing num_land_accepted endl total number of planes accepted for takeoff num_takeoff_accepted endl total number of planes refused for landing num_land_refused endl total number of planes refused for takeoff num_takeoff_refused endl total number of planes that landed num_landings endl total number of p

31、lanes that took off num_takeoffs endl total number of planes left in landing queue landing.size() endl total number of planes left in takeoff queue takeoffing.size() endl;cout percentage of time runway idle 100.0 * ( float ) idle_time) / ( float ) time) % endl;cout average wait in landing queue ( fl

32、oat ) land_wait) / ( float ) num_landings) time units;cout endl average wait in takeoff queue ( float ) takeoff_wait) / ( float ) num_takeoffs) time units endl;cout average observed rate of planes wanting to land ( float ) num_land_requests) / ( float ) time) per time unit endl;cout average observed

33、 rate of planes wanting to take off ( float ) num_takeoff_requests) / ( float ) time) per time unit endl; （7）測(cè)試數(shù)據(jù)：this program simulates an airport with only one runway.one plane can land or depart in each unit of time.up to what number of planes can be waiting to land or take off at any time ：5how

34、many units of time will the simulation run ：1000expected number of arrivals per unit time ：48expected number of departures per unit time ：48（8）測(cè)試情況：給出程序的測(cè)試情況，并分析運(yùn)行結(jié)果。（測(cè)試結(jié)果如下圖3.1所示）：圖3.1（二）八皇后問題（1）問題描述：八皇后問題是一個(gè)以國(guó)際象棋為背景的問題：如何能夠在 88 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇后都無法直接吃掉其他的皇后（2）基本要求：在 88 的國(guó)際象棋棋盤上放置八個(gè)皇后，使得任何一個(gè)皇

35、后都無法直接吃掉其他的皇后。為了達(dá)到此目的，任兩個(gè)皇后都不能處于同一條橫行、縱行或斜線上。（3）算法思想：通過回溯法實(shí)現(xiàn)：從根結(jié)點(diǎn)出發(fā)，以深度優(yōu)先的方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深 方向移至一個(gè)新結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為一個(gè)新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。 換句話說，這個(gè)結(jié)點(diǎn)不再是一個(gè)活結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)（回溯）至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘匆赃@種工作方式遞歸地 在解空間中搜索，直至找到所要求的解或解空間中已沒有活

36、結(jié)點(diǎn)時(shí)為止。（4）模塊劃分：主程序：驅(qū)動(dòng)概要的遞歸方法。打印出關(guān)于程序功能的信息，在程序中允許用戶指定所用的皇后數(shù)。queens類：打印一個(gè)配置，在棋盤上某特定位置向配置中增加一個(gè)皇后，移去這個(gè)皇后，測(cè)試某特定格子是否未被配置設(shè)防?；厮莺瘮?shù)：基于上述決定，編寫在棋盤上擺放皇后的遞歸函數(shù)。注意通過引用傳遞函數(shù)參數(shù)是為了節(jié)省用于復(fù)制queens對(duì)象的時(shí)間。 （5）數(shù)據(jù)結(jié)構(gòu)：queen:創(chuàng)建皇后抽象數(shù)據(jù)類型（包含queens(int size);bool is_solved()const;void print()const;bool unguarded(int col) const;void ins

37、ert (int col);void remove(int col);int board_size;）（6）源程序：queensclass.h:#ifndef queens_h#define queens_hconst int max_board = 30;class queenspublic:queens(int size);bool is_solved()const;void print()const;bool unguarded(int col) const;void insert (int col);void remove(int col);int board_size;protect

38、ed:private:int count;bool queen_squaremax_boardmax_board;#endif主函數(shù)：#include queensclass.h#include #include using namespace std;void solve_from(queens &configuration);void start();int main()start();cout00000000000000000xx;void start()int board_size;coutwhat is the size of the board?board_size;if(boar

39、d_sizemax_board)coutthe number must be between 0 andmax_boardendl;elsequeens configuration(board_size);solve_from(configuration);start();void solve_from(queens &configuration)if(configuration.is_solved()configuration.print();elsefor(int col = 0;colconfiguration.board_size;col+)if(configuration.ungua

40、rded(col)configuration.insert(col);solve_from(configuration);configuration.remove(col); queenscpp.cpp:#include queensclass.h#include #include using namespace std;queens:queens(int size)board_size = size;count = 0;for(int row = 0;rowboard_size;row+)for(int col = 0;colboard_size;col+)queen_squarerowco

41、l=false; bool queens:is_solved()constif(board_size = count)return true;elsereturn false;void queens:print()constfor(int i=0;iboard_size;i+)for(int j=0;jboard_size;j+)cout (int)queen_squareij ;cout endl;cout endl; bool queens:unguarded(int col)constint i;bool ok = true;for(i = 0;ok&i=0&col-i=0;i+)ok=

42、!queen_squarecount-icol-i;/元素上左for(i = 1;ok&count-i=0&col+iboard_size;i+)ok=!queen_squarecount-icol+i;/元素上右return ok;void queens:insert(int col)queen_squarecount+col = true;void queens:remove(int col)queen_squarecount-col=false;queen_squarecountcol=false; （7）測(cè)試數(shù)據(jù)：用戶指定所用的皇后數(shù)（如圖1.1所示）圖1.1（8）測(cè)試情況：給出程序的

43、測(cè)試情況，并分析運(yùn)行結(jié)果八皇后問題共有92種解答：（部分解答情況如圖1.2所示）。圖1.2（三）二叉樹的建立與遍歷（1）問題描述：建立一棵二叉樹，并對(duì)其進(jìn)行遍歷（先序、中序、后序），打印輸出遍歷結(jié)果。（2）基本要求：從鍵盤接受輸入（前序），以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，建立二叉樹（以前序來建立），并采用遞歸算法對(duì)其進(jìn)行遍歷（前序、中序、后序），將遍歷結(jié)果打印輸出。（3）算法思想：從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個(gè)基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個(gè)操作： （1）訪問結(jié)點(diǎn)本身(n) （2）遍歷該結(jié)點(diǎn)的左子樹(l) （3）遍歷該結(jié)點(diǎn)的右子樹(r)

44、以上三種操作有六種執(zhí)行次序： nlr、lnr、lrn、nrl、rnl、rln。 前三種次序與后三種次序?qū)ΨQ，故只討論先左后右的前三種次序。中序遍歷的遞歸算法定義： 若二叉樹非空，則依次執(zhí)行如下操作：遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹。前序遍歷的遞歸算法定義：若二叉樹非空，則依次執(zhí)行如下操作：訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹。后序遍歷的遞歸算法定義：若二叉樹非空，則依次執(zhí)行如下操作：遍歷左子樹、遍歷右子樹、訪問根結(jié)點(diǎn)。（4）模塊劃分：1.建立二叉樹 tree *creatbitree()2.基本運(yùn)算 void push(stack *top,tree *tree) /樹結(jié)點(diǎn)入棧void pop

45、(stack *top,tree *t) /出棧，棧內(nèi)元素賦值void gettop(stack*s,tree *t) /獲取棧頂元素3.遞歸遍歷函數(shù)void preorder(tree *b1) /前序遍歷函數(shù)void midorder(tree *b2) /中序遍歷函數(shù)void lastorder(tree *b3) /后序遍歷函數(shù)（5）數(shù)據(jù)結(jié)構(gòu)：binary_node：創(chuàng)建節(jié)點(diǎn)抽象數(shù)據(jù)類型（binary_node（）entry data; binary_node *left; binary_node *right;/ constructors: binary_node(); binary

46、_node(const entry &x);）binary_tree：創(chuàng)建二叉樹抽象數(shù)據(jù)類型(binary_tree(); bool empty() const; void preorder(void (*visit)(entry &); void inorder(void (*visit)(entry &); void postorder(void (*visit)(entry &); int size() const; void clear(); int height() const; void insert(const entry &); binary_tree (const binar

47、y_tree &original); binary_tree & operator =(const binary_tree &original); binary_tree();)（6）源程序：cpp1.cpptypedef char entry;template struct binary_node / data members: entry data; binary_node *left; binary_node *right;/ constructors: binary_node(); binary_node(const entry &x);template class binary_tree public: binary_tree(); bool empty() const; void preorder(void (*visit)(entry &); void inorder(void (*visit)(entry &); void postorder(void (*visit)(entry &); int size() const; void clear(); int height() const; void insert(const entry &