數(shù)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書(學(xué)生正式2010秋)

1、數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)指導(dǎo)書目 錄實(shí)習(xí)步驟2實(shí)習(xí)報告規(guī)范4實(shí)習(xí)報告樣例1最大公因數(shù)5實(shí)習(xí)報告樣例2 進(jìn)制轉(zhuǎn)換11dev c+ 調(diào)試方法簡介18visual c+6.0調(diào)試方法簡介24實(shí)驗(yàn)用書推薦28預(yù)備實(shí)驗(yàn)1 字符串處理30預(yù)備實(shí)驗(yàn)2 文件讀取31預(yù)備實(shí)驗(yàn)3 隨機(jī)數(shù)生成32預(yù)備實(shí)驗(yàn)4 遞歸函數(shù)33預(yù)備實(shí)驗(yàn)5 字符串?dāng)?shù)組的查找34實(shí)驗(yàn)1約瑟夫環(huán)問題35實(shí)驗(yàn)2 一元多項式的運(yùn)算36實(shí)驗(yàn)3 逆波蘭表達(dá)式求值37實(shí)驗(yàn)4 楊輝三角顯示39實(shí)驗(yàn)5四則運(yùn)算表達(dá)式求值40實(shí)驗(yàn)6 bst41實(shí)驗(yàn)7 優(yōu)先隊列與堆42實(shí)驗(yàn)8 哈夫曼編/譯碼器44實(shí)驗(yàn)9 圖的遍歷問題45實(shí)驗(yàn)10 教學(xué)計劃編制問題47實(shí)驗(yàn)11 最短路徑問題

2、48實(shí)驗(yàn)12 最小生成樹問題50實(shí)驗(yàn)13 快速排序51實(shí)驗(yàn)14 基數(shù)排序53實(shí)驗(yàn)15 散列表54實(shí)驗(yàn)16 自組織線性表56實(shí)習(xí)步驟（一）問題分析和任務(wù)定義在進(jìn)行設(shè)計之前，首先應(yīng)該充分地分析和理解問題，明確問題要求做什么？限制條件是什么。注意：本步驟強(qiáng)調(diào)的是做什么？而不是怎么做。主要完成三個方面的工作：（1） 分析并確定問題要處理的對象（數(shù)據(jù)）是什么。例如：輸入數(shù)據(jù)的類型、值的范圍以及輸入的形式。（2） 分析并確定要實(shí)現(xiàn)的功能是什么。也就是說要對輸入的數(shù)據(jù)進(jìn)行什么樣的處理。注意：對問題中描述的需要實(shí)現(xiàn)的功能，應(yīng)避開算法（具體的實(shí)現(xiàn)方法）和所涉及的數(shù)據(jù)類型，僅需對所需完成的任務(wù)做出明確的定義。（3

3、） 分析并確定處理后的結(jié)果如何顯示。這一步還應(yīng)該為調(diào)試程序準(zhǔn)備好測試數(shù)據(jù)，包括合法的輸入數(shù)據(jù)和非法形式的輸入數(shù)據(jù)；以及相應(yīng)的輸出結(jié)果。（二）數(shù)據(jù)類型和系統(tǒng)設(shè)計當(dāng)需求分析結(jié)束，明確問題要求后，開始為編寫程序設(shè)計合適的數(shù)據(jù)結(jié)構(gòu)和算法。本步驟分概要設(shè)計和詳細(xì)設(shè)計兩步實(shí)現(xiàn)。概要設(shè)計指的是，對問題描述中涉及的操作對象定義相應(yīng)的抽象數(shù)據(jù)類型，并設(shè)計合適的算法；以及定義程序各個功能模塊和模塊之間的關(guān)系。在這個過程中，要根據(jù)問題的功能需求綜合考慮，設(shè)計時空復(fù)雜度最優(yōu)的抽象數(shù)據(jù)結(jié)構(gòu)和算法（注意：實(shí)現(xiàn)提示和給出的部分代碼中以及給出了建議）。抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體，算

4、法思想和過程明確有效，程序結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試。作為概要設(shè)計的結(jié)果，應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的規(guī)格說明），主要模塊的算法思想，并畫出模塊之間的調(diào)用關(guān)系圖。詳細(xì)設(shè)計則定義相應(yīng)的物理存儲結(jié)構(gòu)（抽象數(shù)據(jù)類型的物理實(shí)現(xiàn)）并寫出各基本操作的偽碼算法，以及主要模塊算法的具體步驟。詳細(xì)設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作的規(guī)格說明做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，算法書寫規(guī)范（采用文字性的步驟描述或者算法流程圖的形式都行）。在求精的過程中，應(yīng)盡量避免陷入語言細(xì)節(jié)，不必過早描述輔助數(shù)據(jù)結(jié)構(gòu)和局部變量。（三）編碼實(shí)現(xiàn)和靜態(tài)檢查在實(shí)驗(yàn)過程中，題目中會給出程序

5、的部分源代碼，根據(jù)實(shí)習(xí)第二步的設(shè)計結(jié)果以及源代碼的提示，編碼實(shí)現(xiàn)程序的其余部分。編碼是把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。對于編程很熟練的讀者，如果基于詳細(xì)設(shè)計的偽碼算法就能直接在鍵盤上輸入程序的話，則可以不必用筆在紙上寫出編碼，而將這一步的工作放在上機(jī)準(zhǔn)備之后進(jìn)行，即在上機(jī)調(diào)試之前直接用鍵盤輸入。寫出編碼的程序后，在上機(jī)（編譯和調(diào)試）之前，認(rèn)真的靜態(tài)檢查是必不可少的。多數(shù)初學(xué)者在編好程序后處于以下兩種狀態(tài)之一：一種是對自己的“精心作品”的正確性確信不疑；另一種是認(rèn)為糾查錯誤是編譯器的工作。這兩種態(tài)度是極為有害的。事實(shí)上，非訓(xùn)練有素的程序設(shè)計者編寫的程序長度超過50行時，極少不含有除

6、語法錯誤以外的錯誤。上機(jī)動態(tài)調(diào)試決不能代替靜態(tài)檢查，否則調(diào)試效率是極低的。靜態(tài)檢查主要有兩種方法，一是用一組測試數(shù)據(jù)手工執(zhí)行程序（通常應(yīng)先分模塊檢查）；二是通過閱讀或給別人講解自己的程序而深入全面地理解程序邏輯，在這個過程中再加入一些注解和斷言。如果程序中邏輯概念清楚，后者將比前者有效。（四）上機(jī)準(zhǔn)備和上機(jī)調(diào)試上機(jī)準(zhǔn)備包括一下幾個方面：（1） 熟悉機(jī)器的操作系統(tǒng)和語言集成環(huán)境的用戶手冊，尤其是最常用的命令操作，以便順利進(jìn)行上機(jī)的基本活動。（2） 上機(jī)調(diào)試程序時要帶一本高級語言教材或手冊。（3） 掌握調(diào)試工具，考慮調(diào)試方案，設(shè)計測試數(shù)據(jù)并手工得出正確結(jié)果?！澳サ恫徽`砍柴工”。計算機(jī)各專業(yè)的學(xué)生應(yīng)

7、該能夠熟練運(yùn)用高級語言的程序調(diào)試器debug調(diào)試程序。上機(jī)調(diào)試程序時要帶一本高級語言教材或手冊。調(diào)試最好分模塊進(jìn)行，自底向上，即先調(diào)試底層函數(shù)。必要時可以另寫一個調(diào)用驅(qū)動程序。這種表面上的工作實(shí)際上可以大大降低調(diào)試所面臨的復(fù)雜性，提高調(diào)試工作效率。在調(diào)試過程中可以不斷借助debug的各種功能，提高調(diào)試效率。調(diào)試中遇到的各種異?，F(xiàn)象往往是預(yù)料不到的，此時不應(yīng)“冥思苦想”，而應(yīng)動手確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，印出帶有完整注釋的且格式良好的源程序清單和結(jié)果。（五）總結(jié)和整理實(shí)習(xí)報告按照實(shí)習(xí)報告的格式完成整個實(shí)習(xí)報告。同時總結(jié)和思考，回味設(shè)計的過程，體會

8、調(diào)試的過程，總結(jié)編程中的收獲，記錄實(shí)習(xí)過程的體會，交流程序設(shè)計各個步驟的心得?！皩W(xué)而不思則罔，思而不學(xué)則殆?！痹诔绦蛟O(shè)計中，只有做到勤思考、善總結(jié)，才能不斷進(jìn)步。實(shí)習(xí)報告規(guī)范實(shí)習(xí)報告的開頭應(yīng)給出題目、班級、姓名、學(xué)號和完成日期，并包括以下七個內(nèi)容：1 需求分析以無歧義的陳述說明程序設(shè)計的任務(wù)，強(qiáng)調(diào)的是程序要做什么？明確規(guī)定：（1） 輸入的形式和輸入值的范圍；（2） 輸出的形式；（3） 程序所能達(dá)到的功能；（4） 測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。2 概要設(shè)計說明本程序中用到的所有抽象數(shù)據(jù)類型的定義、算法的基本思想、主程序的流程以及各程序模塊之間的層次（調(diào)用）關(guān)系

9、。3 詳細(xì)設(shè)計（1） 實(shí)現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型（物理數(shù)據(jù)結(jié)構(gòu)），對每個操作只需要寫出偽碼算法；（2） 算法的具體步驟；（3） 算法的時空分析和改進(jìn)設(shè)想；（4） 畫出函數(shù)的調(diào)用關(guān)系圖。（5） 輸入和輸出的格式。4 調(diào)試分析調(diào)試過程中遇到的問題，以及如何解決的；5 測試結(jié)果根據(jù)實(shí)驗(yàn)提供的測試數(shù)據(jù)，列出你所編寫的程序的測試結(jié)果。6 用戶使用說明（可選）說明如何使用編寫的程序，詳細(xì)列出每一步的操作步驟。7 實(shí)驗(yàn)心得（可選）對實(shí)驗(yàn)設(shè)計與實(shí)現(xiàn)過程的回顧和分析，以及經(jīng)驗(yàn)和體會。8 附錄（可選）帶注釋的源程序。如果是提交源程序電子版，只需列出程序文件名的清單。實(shí)習(xí)報告樣例1最大公因數(shù)題目部分背景因數(shù)分

10、解，求最大公因數(shù)和公倍數(shù)等問題都是數(shù)學(xué)中古老而又重要德問題，這些問題在代數(shù)學(xué)、密碼學(xué)、計算復(fù)雜性理論和量子計算機(jī)等領(lǐng)域中有重要意義。問題描述兩個整數(shù)的最大公因數(shù)是同時整除二者的最大整數(shù)。試設(shè)計一個計算兩個整數(shù)的最大公因數(shù)的程序?；疽螅?） 用戶輸入兩個正整數(shù)，其取值范圍為（0， 216），（2） 要求采用歐幾里德算法，計算最大公因數(shù)。測試數(shù)據(jù)輸入7591035輸出69實(shí)現(xiàn)提示（1） 注意題目給出的正整數(shù)的取值范圍，定義變量時，選擇合適的數(shù)據(jù)類型。（2） 歐幾里德算法計算最大公因數(shù)，編寫成一個獨(dú)立的函數(shù)，并注意該算法對兩個數(shù)據(jù)的大小關(guān)系有要求，在設(shè)計函數(shù)的輸入?yún)?shù)以及函數(shù)處理代碼時要注意處理

11、。選作內(nèi)容（1） 設(shè)計一個求取n個正整數(shù)的最大公因數(shù)的函數(shù)。（2） 如果用戶輸入的正整數(shù)的取值范圍為（0, 232）、（0, 264），請設(shè)計求取兩個大的正整數(shù)的最大公因數(shù)的函數(shù)。源程序及填空部分#include “stdio.h”typedef long elemtype; /歐幾里德算法計算最大公因數(shù)函數(shù)elemtype gcd (elemtype m, elemtype n)/填空main ()elemtype a, b, g;/輸入printf(“n本程序可以求取兩個正整數(shù)的最大公因數(shù)n”);printf(“n請輸入第一個正整數(shù)（注意輸入的數(shù)要小于2100000000）：”);scan

12、f(“%ld”, &a);printf(“n請輸入第二個正整數(shù)（注意輸入的數(shù)要小于2100000000）：”);scanf(“%ld”, &b);g=gcd(a, b);/輸出printf(“n兩者的最大公因數(shù)是：%ld”, g);實(shí)驗(yàn)報告部分hunan university課程實(shí)習(xí)報告題 目： 最大公因數(shù) 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 完 成 日 期 57 一、需求分析1 本程序要求采用歐幾里德算法，計算并輸出用戶輸入的兩個正整數(shù)的最大公因數(shù)。2 兩個正整數(shù)由用戶通過鍵盤輸入，其取值范圍為（0， 216）。不對非法輸入做處理，即假設(shè)輸入都是合法的。3 在dos界面輸出最大公因數(shù)。4

13、 測試數(shù)據(jù)輸入7591035輸出69二、概要設(shè)計抽象數(shù)據(jù)類型為實(shí)現(xiàn)上述程序的功能，應(yīng)以整數(shù)存儲用戶的輸入，以及計算出的結(jié)果。算法的基本思想根據(jù)題目要求，采用歐幾里德算法計算兩個正整數(shù)的最大公因數(shù)。該算法的基本思想是輾轉(zhuǎn)相除法。設(shè)兩數(shù)為a、b（ba），求它們最大公約數(shù)(a、b)的步驟如下：1. a b，令r為所得余數(shù)（0rb）若 r = 0，算法結(jié)束；b 即為答案。2. 互換：置 ab，br，并返回第一步。程序的流程程序由三個模塊組成：（1） 輸入模塊：完成兩個正整數(shù)的輸入，存入變量a和b中。（2） 計算模塊：設(shè)計一個最大公因數(shù)函數(shù)，elemtype gcd (elemtype m, elemt

14、ype n)，兩個整數(shù)作為函數(shù)參數(shù)，計算結(jié)果通過函數(shù)名返回。（3） 輸出模塊：屏幕上顯示計算的最大公因數(shù)。三、詳細(xì)設(shè)計物理數(shù)據(jù)類型題目要求輸入的正整數(shù)的取值范圍在（0， 216）之間，為了能夠存儲，采用c語言中的長整型定義變量。typedef long elemtype算法的具體步驟歐幾里德算法計算兩個正整數(shù)的最大公因數(shù)的算法流程圖如下算法的時空分析算法的運(yùn)行時間依賴與確定余數(shù)序列有多長?？梢宰C明，在兩次迭代后，余數(shù)最多是原始值的一半。則迭代次數(shù)是2log no(log n)。輸入和輸出的格式輸入本程序可以求取兩個正整數(shù)的最大公因數(shù)/提示請輸入第一個正整數(shù)（注意輸入的數(shù)要小于210000000

15、0）：/提示等待輸入請輸入第二個正整數(shù)（注意輸入的數(shù)要小于2100000000）：/提示等待輸入輸出/提示兩者的最大公因數(shù)是：/輸出結(jié)果的位置四、調(diào)試分析略。五、測試結(jié)果輸入50 15輸出5輸入1989 1590 輸出3六、用戶使用說明（可選）1、本程序的運(yùn)行環(huán)境為dos操作系統(tǒng)，執(zhí)行文件為gcd.exe2、運(yùn)行程序時提示輸入兩個整數(shù)本程序可以求取兩個正整數(shù)的最大公因數(shù)請輸入第一個正整數(shù)（注意輸入的數(shù)要小于2100000000）：請輸入第二個正整數(shù)（注意輸入的數(shù)要小于2100000000）：輸出兩者的最大公因數(shù)是：七、實(shí)驗(yàn)心得（可選）略。七、附錄（可選）gcd.c 主程序?qū)嵙?xí)報告樣例2 進(jìn)制轉(zhuǎn)

16、換題目部分背景機(jī)制轉(zhuǎn)換是計算機(jī)實(shí)現(xiàn)計算的基本問題。問題描述十進(jìn)制數(shù)n和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計算機(jī)實(shí)現(xiàn)計算的基本問題。請編制一個滿足下列要求的進(jìn)制轉(zhuǎn)換程序?；疽螅?） 用戶輸入一個非負(fù)的十進(jìn)制整數(shù)，其取值范圍為（0， 216），（2） 打印輸出與其等值的八進(jìn)制數(shù)。測試數(shù)據(jù)輸入1000輸出1750實(shí)現(xiàn)提示（1） 利用求模取余法，n（n div d） d n mod d公式實(shí)現(xiàn)。（2） 由于上述計算過程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，而打印輸出正好相反，利用堆棧的后進(jìn)先出的特性正好實(shí)現(xiàn)。選作內(nèi)容（1） 設(shè)計一個能處理小數(shù)的進(jìn)制轉(zhuǎn)換程序。（2） 設(shè)計一個能處理負(fù)數(shù)的進(jìn)制轉(zhuǎn)換程序。源程序及

17、填空部分#include #include /*包含動態(tài)內(nèi)存分配函數(shù)的頭文件*/typedef int elemtype;typedef struct nodetype elemtypedata;struct nodetype*next;node;typedef struct node * top;int len;linkstack;void initstack(linkstack *s)/構(gòu)造一個空棧s。s-top=null;s-len=0;int stackempty(linkstack *s)/若棧s為空棧，則返回true，否則返回falseif (s-len = 0)return 1;

18、elsereturn 0;/返回1 表示true，否則返回0表示falseint push(linkstack *s, elemtype e) /新元素e入棧/填空int pop(linkstack *s, elemtype *e) /棧頂元素出棧，并以e返回其值/填空void conversion(linkstack *s, int n) /進(jìn)制轉(zhuǎn)換，保存（入棧）在s中/填空void display(linkstack *s) /輸出，把s中元素出棧，并顯示/填空main()struct linkstack * ls;int n;int d;ls=(linkstack *)malloc(si

19、zeof(linkstack); /關(guān)鍵的初始化scanf(%d, &n);initstack(ls);conversion(ls, n);display(ls);實(shí)驗(yàn)報告部分hunan university課程實(shí)習(xí)報告題 目： 進(jìn)制轉(zhuǎn)換 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 完 成 日 期 一、需求分析1 本程序要求對用戶輸入一個非負(fù)的十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。2 十進(jìn)制整數(shù)由用戶通過鍵盤輸入，其取值范圍為（0， 28）。不對非法輸入做處理，即假設(shè)輸入都是合法的。3 在dos界面輸出其等值的八進(jìn)制數(shù)。4 測試數(shù)據(jù)輸入1348輸出2504二、概要設(shè)計抽象數(shù)據(jù)類型為實(shí)現(xiàn)上述程序的

20、功能，應(yīng)以整數(shù)存儲用戶的輸入。為了實(shí)現(xiàn)求模取余法，利用堆棧保存計算的結(jié)果。堆棧定義如下：adt stack數(shù)據(jù)對象：整數(shù)基本操作：initstack（&s）/構(gòu)造一個空棧s。 stackempty（s）/若棧s為空棧，則返回true，否則返回falsepush（s，&e）/新元素e入棧 pop（&s，&e）/棧頂元素出棧，并以e返回其值算法的基本思想根據(jù)題目要求，用求模取余法，n（n div d） d n mod d公式實(shí)現(xiàn)。由于上述計算過程是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，而打印輸出正好相反，利用堆棧的后進(jìn)先出的特性正好實(shí)現(xiàn)。程序的流程程序由三個模塊組成：（1） 輸入模塊：完成正整數(shù)

21、的輸入，存入變量n中。（2） 轉(zhuǎn)換模塊：實(shí)現(xiàn)求模取余法，余數(shù)依次入堆棧中。（3） 輸出模塊：從堆棧中取數(shù)，并顯示在屏幕上。三、詳細(xì)設(shè)計物理數(shù)據(jù)類型題目要求輸入的正整數(shù)的取值范圍在（0， 28）之間，為了能夠存儲，變量n采用c語言中的int定義變量。因?yàn)槎褩Ｐ璐鎯Φ脑貍€數(shù)和十進(jìn)制數(shù)n的大小直接相關(guān)，其長度變化很大，所以堆棧采用單鏈表來實(shí)現(xiàn)其物理數(shù)據(jù)結(jié)構(gòu)。堆棧的每個元素只需存儲08的字符，所以棧中元素類型定義為字符型。typedef int elemtypetypedef struct nodetype elemtypedata;struct nodetype*next;node;typedef

22、 struct node * top;int len;linkstack;void initstack（linkstack *s）/構(gòu)造一個空棧s。s-top = null;s-len=0;int stackempty（linkstack *s）/若棧s為空棧，則返回true，否則返回false若s-len= = 0 /返回1 表示true，否則返回0表示falseint push（linkstack *s，elemtype e）/新元素e入棧/分配新空間，建立一個新結(jié)點(diǎn)l (node *) malloc (sizeof(node);若l null 返回0表示false；入棧失敗l-data

23、= e; l-next = s-top; /插入s-top = l; s-len+; 返回1 表示true，入棧成功int pop（linkstack &s，elemtype *e）/棧頂元素出棧，并以e返回其值若?？眨祷?表示false；出棧失敗*e = s-top-data; l = s-top;s-top = s-top-next；free（l）；s-len-;返回1 表示true，出棧成功算法的具體步驟求模取余法流程圖如下：函數(shù)名conversion(*s, n)輸出的算法（函數(shù)display (*s)）：棧頂元素出棧，轉(zhuǎn)換為字符的ascii碼，然后用字符格式輸出。算法的時空分析算法

24、的執(zhí)行，主要是每次n除8，以及入棧，出棧顯示，由于采用鏈表實(shí)現(xiàn)，入棧和出棧的時間復(fù)雜度都是o(1)，那么進(jìn)制轉(zhuǎn)換的時間復(fù)雜度，主要由n的大小決定，具體來說是要除8幾次，即8 k = n。由此可知上述設(shè)計的時間復(fù)雜度是o(log8n)。函數(shù)的調(diào)用關(guān)系圖initstack /堆棧初始化輸入十進(jìn)制數(shù)nconversion () /進(jìn)制轉(zhuǎn)換push /入堆棧主程序stackempty / 判定棧空display () /顯示結(jié)果pop /出堆棧輸入和輸出的格式輸入本程序可以把輸入的十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制的數(shù)/提示請輸入十進(jìn)制的正整數(shù)（注意輸入的數(shù)要小于2100000000）：/提示等待輸入輸出/提示八進(jìn)

25、制數(shù)數(shù)是：/輸出結(jié)果的位置四、調(diào)試分析略。五、測試結(jié)果略。六、用戶使用說明（可選）1、本程序的運(yùn)行環(huán)境為dos操作系統(tǒng)，執(zhí)行文件為conversion.exe2、運(yùn)行程序時提示輸入本程序可以把輸入的十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制的數(shù)請輸入十進(jìn)制的正整數(shù)（注意輸入的數(shù)要小于2100000000）：輸出八進(jìn)制數(shù)數(shù)是：七、實(shí)驗(yàn)心得（可選）略。七、附錄（可選）conversion.c 主程序stack.h 堆棧實(shí)現(xiàn)（數(shù)據(jù)結(jié)構(gòu)）dev c+ 調(diào)試方法簡介一、dev c+下的調(diào)試的幾個基本步驟。1. 把“生成調(diào)試信息”設(shè)置為 yes。方法如下：tools（工具） - compiler options（編譯器選項）

26、- settings（設(shè)置）2. 編譯程序。程序“編譯”編譯后會出來這個對話框。點(diǎn)擊“關(guān)閉”，關(guān)閉該按鈕。3. 設(shè)置斷點(diǎn)（break point）把光標(biāo)移動到您想暫停執(zhí)行的那一行，按 ctrl + f5，或者直接用鼠標(biāo)點(diǎn)擊下圖紅線標(biāo)明的區(qū)域。（如下圖）4. 開始調(diào)試（debug）按 f8 開始調(diào)試，或者點(diǎn)擊“調(diào)試”選項（ debug ）后就彈出下拉菜單（如下圖）。如果您沒有把“生成調(diào)試信息”設(shè)置為 yes，dev-c+ 會提示說您的工程中沒有調(diào)試信息。點(diǎn)擊 yes，dev-c+ 會自動把“生成調(diào)試信息”設(shè)置為 yes，并且重新編譯您的工程。程序運(yùn)行到斷點(diǎn)處會暫停；按 f7 執(zhí)行當(dāng)前行，并跳到下

27、一行；ctrl + f7 跳到下一斷點(diǎn)，shift + f4 跳到光標(biāo)所在行，并在該行設(shè)置斷點(diǎn)。注意一點(diǎn)。比如。設(shè)置的“斷點(diǎn)”是printf語句處。那執(zhí)行只執(zhí)行到scanf語句后就不會顯示答案了。如下圖。大家看到那藍(lán)條，這是做什么的呢，這是因?yàn)樵O(shè)置的“斷點(diǎn)”是printf語句后，但又顯示不出答案。如果想得到答案?？梢园醋笙陆堑??！跋乱徊健比缦聢D。5. 查看變量的值開始調(diào)試后，在圖示區(qū)域按右鍵（如果您使用的是左手習(xí)慣，則是左鍵），選擇“添加監(jiān)測（add watch）”；或者直接按 f4。在彈出窗口中輸入您想查看的變量名，然后按確定（ok），就可以看到該變量的值：用鼠標(biāo)選擇源文件中的變量名，然后按

28、 f4 也可以查看變量的值，該變量會出現(xiàn)在左邊的監(jiān)測列表中：如果在環(huán)境選項（environment options）中選擇了“通過鼠標(biāo)監(jiān)測變量（watch variable under mouse）”，用鼠標(biāo)指向您想要查看的變量一段時間，該變量也會被添加到監(jiān)測列表中。重要提示：1) 當(dāng)您想查看指針指向的變量的值的時候，按 f4，然后輸入星號及指針的名字（如 *pointer）。 如果沒加 *，看到的將會是一個地址，也就是指針的值。2) 有時，調(diào)試器（debugger）可能不知道某個指針的類型，從而不能顯示該指針指向的變量的值。此時，我們需要手動輸入該指針的類型。按 f4 后，以 *(type

29、*)pointer 形式輸入。例如，*(int *)pointer。6. 最后點(diǎn)擊“停止執(zhí)行”就退出調(diào)試了。如下圖。二、調(diào)式例子下面這個程序，編譯能正常通過，但是運(yùn)行時計算結(jié)果無法顯示，通過調(diào)式可以找出存在死循環(huán)。#include #include int main(int argc, char *argv) int i=1, sum=0; while(i0)個人按順時針方向圍成一圈首先第1個人從1開始順時針報數(shù)報m的人(m 為正整數(shù))令其出列。然后再從他的下一個人開始，重新從1順時針報數(shù)，報m的人，再令其出列。如此下去，直到圈中所有人出列為止。求出列編號序列。基本要求需要基于線性表的基本操作

30、來實(shí)現(xiàn)約瑟夫問題需要利用數(shù)組來實(shí)現(xiàn)線性表輸入輸出格式輸入格式：n，m輸出格式1：在字符界面上輸出這n個數(shù)的輸出序列輸出格式2：將這n個數(shù)的輸出序列寫入到文件中選做內(nèi)容（1） 使用單鏈表來實(shí)現(xiàn)之（2） 使用循環(huán)鏈表來實(shí)現(xiàn)之測試用例輸入：10，3輸出：3 6 9 2 7 1 8 5 10 4課后習(xí)題請以o（n）的時間復(fù)雜度來實(shí)現(xiàn)約瑟夫問題。實(shí)驗(yàn)2 一元多項式的運(yùn)算背景在數(shù)學(xué)上，一個一元n次多項式pn(x)可按降序?qū)懗桑核怯蒼1個系數(shù)唯一確定。因此，在計算機(jī)里它可以用一個線性表p來表示：p=（pn, pn-1, , p1, po）一元多項式的運(yùn)算包括加法、減法和乘法，而多項式的減法和乘法都可以用加

31、法來實(shí)現(xiàn)。問題描述設(shè)pn(x)和qm(x)分別兩個一元多項式。試編寫程序?qū)崿F(xiàn)一元多項式的加法運(yùn)算?；疽笮枰诰€性表的基本操作來實(shí)現(xiàn)一元多項式的加法運(yùn)算需要利用有序鏈表來實(shí)現(xiàn)線性表。輸入輸出舉例/第一個多項式為9x15+7x8+5x3+3x輸入4 /表示第一個多項式的項數(shù)9， 15（回車） /表示9x157， 8 （回車）5， 3 （回車）3， 1 （回車）輸出9x15+ 7x8+5x3+3x1/第二個多項式為-7x8+6x3+2輸入3 /表示第二個多項式的項數(shù)6， 3（回車） /表示9x15-7， 8（回車）2， 0 （回車）輸出-7x8+ 6x3+2x0求和結(jié)果 9x15+11x3+3

32、x1+ 2x0實(shí)驗(yàn)3 逆波蘭表達(dá)式求值背景表達(dá)式求值是程序設(shè)計語言編譯中的一個最基本的問題因?yàn)槿魏纬绦蛟O(shè)計語言都必須具有表達(dá)式求值的功能，同時表達(dá)式的計算應(yīng)用也相當(dāng)廣泛，比如電力調(diào)度系統(tǒng)中的計算遙測、車站票務(wù)系統(tǒng)中的票價類型計算公式等。通常，我們所說的表達(dá)式是由運(yùn)算符、操作數(shù)、界限符所組成。而算術(shù)表達(dá)式中最常見的表示法形式有中綴、前綴和后綴表示法。中綴表示法是書寫表達(dá)式的常見方式，而前綴和后綴表示法主要用于計算機(jī)科學(xué)領(lǐng)域。1、中綴表達(dá)式將運(yùn)算符放在兩操作數(shù)的中間。在運(yùn)算中存在運(yùn)算符的優(yōu)先權(quán)與結(jié)合性的問題。例如運(yùn)算：a*b+(c-d/e)*f 時，編譯器即自左向右逐一檢查，當(dāng)檢查到第一個運(yùn)算符“

33、*”時還無法知道是否執(zhí)行；待檢查到第二個運(yùn)算符“ + ”時，因?yàn)橹馈?”的優(yōu)先級別高于“ + ”時，才知道執(zhí)行“a*b”；當(dāng)繼續(xù)檢查到“ ( ”時，可知道先執(zhí)行括號以內(nèi)部分等。2、前綴表達(dá)式將運(yùn)算符放在兩操作數(shù)的前面。這種表示法經(jīng)常用于計算機(jī)科學(xué)，特別是編譯器設(shè)計方面。為紀(jì)念其發(fā)明家jan lukasiewicz，這種表示法也稱波蘭表示法。3、后綴表達(dá)式將運(yùn)算符放在兩操作數(shù)的后面。后綴表達(dá)式也稱逆波蘭表達(dá)式，因其使表達(dá)式求值變得輕松，所以被普遍使用。前綴和后綴表示法有三項公共特征：（1） 操作數(shù)的順序與等價的中綴表達(dá)式中操作數(shù)的順序一致（2） 不需要括號（3） 操作符的優(yōu)先級不相關(guān)問題描述讀

34、入一個后綴表達(dá)式，利用堆棧來計算該表達(dá)式的值，同時要效驗(yàn)后綴表達(dá)式是否正確?；疽螅?）從鍵盤中輸入一個后綴表達(dá)式，該表示包括加減乘除等操作符，以及正整數(shù)作為操作數(shù)等。（2）用堆棧來實(shí)現(xiàn)輸入輸出格式輸入：在字符界面上輸入一個后綴表達(dá)式，其中兩相鄰操作數(shù)之間利用空格隔開。以“#”表示結(jié)束。輸出：如果該后綴表達(dá)式正確，那么在字符界面上輸出其結(jié)果，計算結(jié)果小數(shù)點(diǎn)后面保留兩位有效數(shù)字，如果不正確，請在字符界面上輸出表達(dá)式錯誤提示。選作內(nèi)容（1） 在輸入和輸出方式上發(fā)生改變：輸入：將后綴表達(dá)式存于文本文件中，其中后綴表達(dá)式中兩相鄰操作數(shù)之間利用空格隔開，程序從該文本文件中讀出表達(dá)式。輸出：如果該后綴表

35、達(dá)式正確，則計算結(jié)果，計算結(jié)果保留小數(shù)點(diǎn)后面兩位有效數(shù)字，同時將結(jié)果輸出到該文件中原表達(dá)式的后面，結(jié)果與表達(dá)式之間用“=”后相連；如果不正確，請在輸出表達(dá)式錯誤提示到該文件原表達(dá)式的后面，它們之間用“-”相連。（2） 表達(dá)式中操作數(shù)為一實(shí)數(shù)，該實(shí)數(shù)精確到小數(shù)點(diǎn)后面兩位有效數(shù)字。測試用例輸入：2 3 * 1 #輸出：5課后習(xí)題 n個元素1,2,n有n!個不同的排列。將這n！個排列按字典序列排列，并編號為0，1,n!-1.每個排列的編號為其字典序值。例如，當(dāng)n=3時，6個不同排列的字典序值如下：字典序值012345排列123132213231312321請編程實(shí)現(xiàn)之。實(shí)驗(yàn)4 楊輝三角顯示背景中國古

36、代數(shù)學(xué)史曾經(jīng)有代寫論文自己光輝燦爛的篇章，而楊輝三角的發(fā)現(xiàn)就是十分精彩的一頁。楊輝三角是中國古代數(shù)學(xué)家賈憲在公元11世紀(jì)發(fā)現(xiàn)，并被南宋數(shù)學(xué)家楊輝在他的書中所引述，才使我們今天得以了解賈憲在數(shù)學(xué)上的重大貢獻(xiàn)。楊輝三角是一個由數(shù)字排列成的三角形數(shù)表.一般形式如下: 問題描述編寫程序，根據(jù)輸入的行數(shù)，屏幕顯示楊輝三角?；疽?1) 行數(shù)不大于20行。(2) 基于隊列的操作來實(shí)現(xiàn)楊輝三角的不斷生成過程。（注：不要用其它的公式計算的方法或者二維數(shù)組來實(shí)現(xiàn)）(3) 基于數(shù)組實(shí)現(xiàn)隊列的物理數(shù)據(jù)結(jié)構(gòu)。輸入輸出輸入 n 6輸出1 n=01 1 n=11 2 1 n=21 3 3 1 n=31 4 6 4 1

37、n=41 5 10 10 5 1 n=51 6 15 20 15 6 1 n=6實(shí)驗(yàn)5四則運(yùn)算表達(dá)式求值背景在工資管理軟件中，不可避免的要用到公式的定義及求值等問題。對于數(shù)學(xué)表達(dá)式的計算，雖然可以直接對表達(dá)式進(jìn)行掃描并按照優(yōu)先級逐步計算，但也可以將中綴表達(dá)式轉(zhuǎn)換為逆波蘭表達(dá)式，這樣更容易處理。問題描述四則運(yùn)算表達(dá)式求值，將四則運(yùn)算表達(dá)式用中綴表達(dá)式，然后轉(zhuǎn)換為后綴表達(dá)式，并計算結(jié)果?；疽?1) 使用二叉樹來實(shí)現(xiàn)。實(shí)現(xiàn)提示利用二叉樹后序遍歷來實(shí)現(xiàn)表達(dá)式的轉(zhuǎn)換，同時可以使用實(shí)驗(yàn)3的結(jié)果來求解后綴表達(dá)式的值。輸入輸出格式：輸入：在字符界面上輸入一個中綴表達(dá)式，回車表示結(jié)束。輸出：如果該中綴表達(dá)式

38、正確，那么在字符界面上輸出其后綴表達(dá)式，其中后綴表達(dá)式中兩相鄰操作數(shù)之間利用空格隔開；如果不正確，在字符界面上輸出表達(dá)式錯誤提示。選作內(nèi)容（1）在輸入輸出方式上要求使用：輸入：將中綴表達(dá)式存于文本文件中，程序從該文本文件中讀出表達(dá)式。輸出：如果該中綴表達(dá)式正確，則將后綴表達(dá)式輸出到該文件中原表達(dá)式的后面，它們之間用“-”后相連；如果不正確，請在輸出表達(dá)式錯誤提示到該文件原表達(dá)式的后面，它們之間用“-”相連。(2) 利用堆棧來實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。測試用例輸入：21+23*（12-6）輸出：21 23 12 6 -*+課后習(xí)題采用非遞歸的編程方法分別統(tǒng)計二叉樹的節(jié)點(diǎn)個數(shù)度為1和葉子節(jié)點(diǎn)

39、的個數(shù)以及數(shù)據(jù)值的最大值和最小值。實(shí)驗(yàn)6 bst問題描述利用二叉查找樹（bst）實(shí)現(xiàn)一個動態(tài)查找表?；疽?1) 使用二叉樹（bst）來實(shí)現(xiàn)。(2) 二叉樹使用鏈?zhǔn)浇Y(jié)構(gòu)（二叉鏈表）實(shí)現(xiàn)。(3) 實(shí)現(xiàn)bst的構(gòu)建，查找兩個功能。實(shí)現(xiàn)提示輸入：8/bst的節(jié)點(diǎn)個數(shù)34, 76, 45, 18, 26, 54, 92, 65 /8個數(shù)據(jù)45/查找 45輸出：查找成功 3 /返回成功和查找時比較的次數(shù) 34/查找 34輸出：查找成功 1 /返回成功和查找時比較的次數(shù)100/查找 100輸出：查找不成功 3 /返回成功和查找時比較的次數(shù)選作內(nèi)容(1) 實(shí)現(xiàn)二叉樹（bst）的插入和刪除功能。(2) 查找不成功時，被查找的數(shù)據(jù)插入到bst中。課后習(xí)題隨機(jī)產(chǎn)生n個數(shù)據(jù)，構(gòu)建bst。然后隨機(jī)產(chǎn)生m個數(shù)據(jù)（可能由相等的數(shù)據(jù)），對每一個數(shù)據(jù)在bst中進(jìn)行查找，統(tǒng)計比較的次數(shù)，求取查找的平均值。若查找不成功時，被查找的數(shù)據(jù)插入到bst中，統(tǒng)計比較的次數(shù)，求取查找的平均值。實(shí)驗(yàn)7 優(yōu)先隊列與堆背景優(yōu)先級隊列（priority queue）就是遵循兩個排序規(guī)則的集合。首先，具有高優(yōu)先級的項目在先。第二，具有相同優(yōu)先級的項目使用先進(jìn)先出方法來確定其排序。用到優(yōu)先隊列的地方：凡是需要取出集合中最值元素的地方。l 構(gòu)建霍夫曼編碼構(gòu)建霍夫曼編碼需要找到結(jié)點(diǎn)集合中頻率最小的兩個結(jié)點(diǎn)。然后合并結(jié)點(diǎn)插入到集