識別廣義表頭尾演示數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告.doc

沈陽航空航天大學(xué) 課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告 課程設(shè)計(jì)名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目 識別廣義表頭尾演示識別廣義表頭尾演示 院 系 計(jì)算機(jī)學(xué)院 專 業(yè) 軟件工程 班 級 34010301 學(xué) 號 2013040103030 姓 名 張為 指導(dǎo)教師 丁一軍 說明 結(jié)論 優(yōu)秀 良好 中等 及格 不及格 作為相關(guān)教環(huán)節(jié)考核必要依據(jù) 說明 結(jié)論 優(yōu)秀 良好 中等 及格 不及格 作為相關(guān)教環(huán)節(jié)考核必要依據(jù) 格式不符合要求 數(shù)據(jù)不實(shí) 不予通過 報(bào)告和電子數(shù)據(jù)必須作為實(shí)驗(yàn)現(xiàn)象重復(fù)的格式不符合要求 數(shù)據(jù)不實(shí) 不予通過 報(bào)告和電子數(shù)據(jù)必須作為實(shí)驗(yàn)現(xiàn)象重復(fù)的 關(guān)鍵依據(jù) 關(guān)鍵依據(jù) 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 學(xué)術(shù)誠信聲明 本人聲明本人聲明 所呈交的報(bào)告 含電子版及數(shù)據(jù)文件 是我個(gè)人在導(dǎo)師指 導(dǎo)下獨(dú)立進(jìn)行設(shè)計(jì)工作及取得的研究結(jié)果 盡我所知 除了文中特別 加以標(biāo)注或致謝中所羅列的內(nèi)容以外 報(bào)告中不包含其他人己經(jīng)發(fā)表 或撰寫過的研究結(jié)果 也不包含其它教育機(jī)構(gòu)使用過的材料 與我一 同工作的同學(xué)對本研究所做的任何貢獻(xiàn)均己在報(bào)告中做了明確的說明 并表示了謝意 報(bào)告資料及實(shí)驗(yàn)數(shù)據(jù)若有不實(shí)之處 本人愿意接受本 教學(xué)環(huán)節(jié) 不及格 和 重修或重做 的評分結(jié)論并承擔(dān)相關(guān)一切后 果 本人簽名 日期 年 月 日 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 I 沈陽航空航天大學(xué)沈陽航空航天大學(xué) 課課程程設(shè)設(shè)計(jì)計(jì)任任務(wù)務(wù)書書 課程設(shè)計(jì)名稱 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)課課程程設(shè)設(shè)計(jì)計(jì)專業(yè) 軟軟件件工工程程 學(xué)生姓名張為張為班級 34010301 學(xué)號 2013040103030 題目名稱 識別廣義表頭尾演示識別廣義表頭尾演示 起止日期2014年9月1日起至2015年1月14日止 課設(shè)內(nèi)容和要求 1 寫一個(gè)程序 建立廣義表的存儲結(jié)構(gòu) 演示在此存儲結(jié)構(gòu)上實(shí)現(xiàn)的廣義表 求頭 求尾操作序列的結(jié)果 2 廣義表允許多行輸入 其中可以任意輸入空格符 3 廣義表存儲結(jié)構(gòu)自定 4 對廣義表的操作為一個(gè)由 t 和 h 組成的字符串 參考資料 算法與數(shù)據(jù)結(jié)構(gòu) C 語言程序設(shè)計(jì) 教教研研室室審審核核意意見見 教教研研室室主主任任簽簽字字 指導(dǎo)教師 簽名 指導(dǎo)教師 簽名 年月日 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 II 學(xué)學(xué) 生 簽名 生 簽名 年月日 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 III 目目 錄錄 沈陽航空航天大學(xué)沈陽航空航天大學(xué) I 學(xué)術(shù)誠信聲明學(xué)術(shù)誠信聲明 I 1 題目介紹與功能描述題目介紹與功能描述 1 1 1 題目介紹 1 1 2 具體要求 1 1 3 題目分析 1 2 系統(tǒng)功能模塊結(jié)構(gòu)圖系統(tǒng)功能模塊結(jié)構(gòu)圖 2 2 1 系統(tǒng)功能結(jié)構(gòu)圖 2 2 2 主要模塊功能說明 3 2 2 1 建立廣義表 3 2 2 2 對表進(jìn)行求頭尾操作 3 3 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及用法說明數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及用法說明 4 3 1 存儲結(jié)構(gòu) 4 3 2 用法說明 4 4 主要函數(shù)主要函數(shù) 5 4 1 VOID CREATLIST GLIST 表結(jié)點(diǎn)類型 tag 0 表示原子結(jié)點(diǎn) tag 1 表示表結(jié)點(diǎn) union char data struct struct GLNode hr tr GList 3 2 用法說明用法說明 對廣義表的結(jié)構(gòu)采用鏈表的形式進(jìn)行定義 由于廣義表可以是原子也可以是 表 所以在結(jié)構(gòu)體中還采用了共用體的數(shù)據(jù)結(jié)構(gòu) 讓原子和節(jié)點(diǎn)可以共享存儲單 元 tag 代表節(jié)點(diǎn)的類型 0 為原子 1 為表 hr 代表表的頭指針 tr 代表表的尾指 針 data 為表的內(nèi)容 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 4 4 主要函數(shù) 程序主體由幾個(gè)關(guān)鍵函數(shù)組成 creatlist GList c getchar if c return 1 廣義表第一個(gè)字符必須是 否則終止函數(shù) GList Ls creatlist Ls 在整個(gè)程序中采用 getchar 函數(shù)從鍵盤緩沖區(qū)讀取輸入的廣義表數(shù)據(jù) creatlist 函數(shù)的完全代碼如下 void creatlist GList c getchar 拾取一個(gè)合法字符 if c 空表的情況 Ls NULL c getchar if c return 空表的下一個(gè)合法字符應(yīng)該是 else 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 5 當(dāng)前輸入的廣義表非空 GList p Ls GList malloc sizeof GLNode Ls tag 1 表結(jié)點(diǎn) if c 表頭為單原子 Ls hr GList malloc sizeof GLNode p Ls hr p tag 0 p data c 建立原子結(jié)點(diǎn) else 表頭為廣義表 creatlist Ls hr 對此廣義表遞歸建立存儲結(jié)構(gòu) c getchar if c creatlist Ls tr 當(dāng)前廣義表未結(jié)束 等待輸入下一個(gè)子表 else if c Ls tr NULL 當(dāng)前廣義表輸入結(jié)束 廣義表是采用遞歸的方式定義的 因此 creatlist 中廣義表也是采用遞歸的方式建 立的 由于廣義表的第一個(gè)字符 在 main 函數(shù)中已被讀取 因此 creatlist 中從鍵 盤數(shù)據(jù)緩沖區(qū)讀取的第一個(gè)字符是所輸入的廣義表的第二個(gè)字符 若當(dāng)層廣義表 非空 則應(yīng)建立表結(jié)點(diǎn) 在建立原子結(jié)點(diǎn)時(shí)所用的判斷方法為 if c 是因 為 之后的字符要么是 要么是原子 在經(jīng)過代碼 if c 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 6 creatlist Ls tr 遞歸建立的廣義表的讀取的第一個(gè)字符只能是原子或者 而不可能是 因此建立原子結(jié)點(diǎn)的判斷方法為 if c 當(dāng) getchar 讀取的字符為 時(shí) 表示要進(jìn)入下一層廣義表 故使用語句 creatlist Ls hr 遞歸建立下一層廣義表 當(dāng) getchar 讀取的字符為 時(shí) 表示當(dāng)層廣義表未結(jié)束 還有子表需要建立 故用 creatlist Ls tr 遞歸建立剩余的子表 當(dāng) getchar 讀取的字符為 時(shí) 表示當(dāng)層廣義表已結(jié)束 則表結(jié)點(diǎn)的表尾指針 應(yīng)為空 即 Ls tr NULL 缺點(diǎn) 缺點(diǎn) 函數(shù) creatlist 的糾錯(cuò)能力較差 要求輸入的廣義表應(yīng)為廣義表的標(biāo)準(zhǔn)正確 形式 如 a b a 1 d 3 4 如果輸入的形式錯(cuò)誤 如 s d o 就會(huì)造成整個(gè)程 序無法運(yùn)行下去 4 2 void GL Elem GList p GL Elem 十分簡單 只是一個(gè)將存儲的原子輸出的函數(shù) 代碼如下 void GL Elem GList p 輸出原子 printf c p data 4 3 void printf GL GList Ls int Ls 指向空表 else cout hr if p 空表 printf else if p tag 1 p 指向表結(jié)點(diǎn) printf i printf GL p i else if p tag 0 GL Elem p 若 p 指向原子結(jié)點(diǎn)則輸出原子 GList k Ls tr 表結(jié)點(diǎn)的尾指針 if k printf 尾指針存在表示此表中還有元素 printf GL k i 遍歷下一結(jié)點(diǎn) else if k i 主要思想 主要思想 解決這兩個(gè)問題需要分辨出當(dāng)前指針指向的是第幾層子表 對于 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 8 問題一 假設(shè) Ls 指向的是當(dāng)層子表的一個(gè)表結(jié)點(diǎn) p Ls hr 顯然 p tag 0 表 示 p 指針?biāo)附Y(jié)點(diǎn)與 Ls 所指結(jié)點(diǎn)在同一層 則只需輸出原子即可 p tag 1 表 示 p 指針?biāo)附Y(jié)點(diǎn)為 Ls 所指結(jié)點(diǎn)所在層次的廣義表的子層 則輸出 并遞 歸遍歷 p 所指層次的廣義表 即 printf GL p i 對于問題二 則需要分辨出表結(jié)點(diǎn)的尾指針的指向 k Ls tr 若 k 存在 則說明此層子表中仍有元素 故輸出 若 k 不存在 說明此層子表完結(jié) 輸 出 4 4 void GetHead GList GList p Ls 保存頭指針 p tr NULL 隔離出 Ls 所指廣義表的第一個(gè)元素 int i 0 printf GL p i 主要思想主要思想 輸出廣義表的表頭 可以利用 printf GL 函數(shù)遍歷廣義表的第一個(gè)元 素 具體做法只需將第一個(gè)結(jié)點(diǎn)的尾指針設(shè)為空 則將這一結(jié)點(diǎn)從原廣義表中獨(dú) 立開來 單獨(dú)作為一個(gè) 廣義表 進(jìn)行遍歷 輸出的結(jié)果即為原廣義表的表頭 由于廣義表的表頭為廣義表的第一個(gè)元素 可以不是一個(gè)子表 如廣義表 a 1 2 的表頭為 a 因此將傳遞的參數(shù) i 初始值置為 0 這樣在最上層的 廣義表表結(jié)點(diǎn)尾指針為空 k 時(shí) 由于 i 0 故不需要輸出 4 5 void GetTail GList Ls Ls tr if Ls 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 9 printf Ls 指向空表 else printf 表尾第一個(gè)字符為 int i 1 已有左括號 故 i 1 printf GL Ls i 主要思想主要思想 輸出廣義表的表尾 可將指向廣義表的指針 Ls 指向第一個(gè)結(jié)點(diǎn) 的下一個(gè)結(jié)點(diǎn) Ls Ls tr 這樣就能得到原廣義表中除第一個(gè)元素外其他元素所 組成的新表 即原廣義表的表尾 然后再利用遍歷廣義表的方法對該表尾進(jìn)行遍 歷即可 4 6 void Get HT GList Ls 這是直接求表頭 表尾的函數(shù) 由它接收輸入 此函數(shù)實(shí)現(xiàn)對廣義表求頭尾 操作的函數(shù) 解釋輸入的操作序列命令 由 t h 組成的字符串 并執(zhí)行 代碼如下 void Get HT GList Ls 執(zhí)行求廣義表表頭 尾 的操作函數(shù) char ch getchar while ch GList p Ls 保存表頭指針 if p printf n 當(dāng)前表為空表 不能執(zhí)行求頭尾操作 n break else switch ch case t GetTail Ls break case h GetHead Ls break 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 10 case 空串時(shí)輸出整個(gè)廣義表 printf n 上表為 if Ls printf Ls 指向空表 else printf 廣義表第一個(gè)字符為 int i 1 已有左括號 故 i 1 printf GL Ls i break default return ch getchar 主要思想主要思想 Get HT 函數(shù)中同樣是利用 getchar 函數(shù)讀取輸入的操作命令 根據(jù)讀取到的不同字符 完成不同的操作 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 11 5 主要函數(shù)流程圖 5 1 main 函數(shù)函數(shù) 否 是 是 否 圖圖 5 15 1 mainmain 函數(shù)流程圖函數(shù)流程圖 主函數(shù)較簡潔 操作都放在具體函數(shù)之上 退出 進(jìn)入建表函數(shù) 求頭尾函數(shù) C 是否為 表為空 開始 結(jié)束 輸入頭尾操作序列 輸出 輸出廣義表 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 12 5 2 creatlist 函數(shù)函數(shù) 是 否 是 是 否 輸入為 圖圖 5 25 2 createlistcreatelist 函數(shù)流程圖函數(shù)流程圖 建表函數(shù)主要運(yùn)用遞歸的思想對廣義表進(jìn)行建立 循環(huán)的建立表頭 表尾 直到輸入的為反括號為止結(jié)束 在建表的時(shí)候需要對表進(jìn)行判斷 判斷輸入的是 否為空或字符 表為空 建立空表 退出 建立原子節(jié)點(diǎn) 輸入為 輸入為 結(jié)束 開始 c 是否為空 C 為 C 為 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 13 5 3 printf GL 函數(shù)函數(shù) 是 否 是 否 否 是 否 是 圖圖 5 35 3 printf GLprintf GL 函數(shù)流程圖函數(shù)流程圖 輸出函數(shù)是整個(gè)程序很重要的函數(shù) 取表頭 取表尾的操作都依靠輸出函數(shù) 表頭 表尾函數(shù)與輸出函數(shù)結(jié)合構(gòu)成整個(gè)程序的核心 開始 K 為尾指針 輸出原子 輸出 i tag 1 輸出 P 為空 P 為頭指針 結(jié)束 輸出 i i 0 輸出 K 為空 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 14 6 調(diào)試報(bào)告 6 1 測試用例設(shè)計(jì)測試用例設(shè)計(jì) 1 輸入 a b c d 操作 thth 2 輸入 e a b c d 操作 tth 3 輸入 b c d e 操作 htht 4 輸入 3 4 5 2 d 操作 h tth 注意 注意 和 是不同的 前者括號內(nèi)無空格符 后者有 本程只能識別后 一種 代表空表 測試用例 3 中 操作序列 h tth 是由 5 個(gè)字符 h 空格符 t t h 組 成 其中空格符表示空串 6 2 調(diào)試過程調(diào)試過程 遇到問題 遇到問題 1 當(dāng)求表頭時(shí) 輸出時(shí) 在結(jié)果末尾會(huì)多出現(xiàn)一個(gè)右括號 例 如 對于廣義表 1 2 3 進(jìn)行求表頭操作 得到的結(jié)果為 1 正確的結(jié)果應(yīng)為 1 2 第一次輸入廣義表的數(shù)據(jù)后 無法再輸入求頭尾的操作序列 使 得 程序不能完成應(yīng)有的求頭尾的功能 原因及解決方法 原因及解決方法 1 問題原因 問題原因 問題出在遍歷函數(shù) printf GL 中 在求頭尾的操作中 由 于將第一個(gè)表結(jié)點(diǎn)的尾指針置為空 將其從原廣義表中獨(dú)立出來 使得在 printf GL 中 執(zhí)行了一次 printf 解決方法 解決方法 設(shè)置一個(gè)括號計(jì)數(shù)器 i 當(dāng)輸出一個(gè) 時(shí) i 輸 出一個(gè) 時(shí) i 并利用 i 的值判斷是否應(yīng)當(dāng)輸出 即判斷條 件為 if k語句 2 問題原因問題原因 程序中使用了兩次不同需求的 getchar 函數(shù) 但是當(dāng) 用戶 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 15 鍵入回車之后 getchar 才開始從 stdin 流中每次讀入一個(gè)字符 在第一次輸入過 程中 由于輸入了廣義表之后 鍵入了回車 導(dǎo)致接下來的 getchar 函數(shù)均是從 鍵盤緩沖區(qū)中讀入數(shù)據(jù) 使得用戶無法輸入新數(shù)據(jù) 解決方法 解決方法 通過 fflush stdin 來清空輸入緩沖區(qū) 以確保不影響后面的數(shù) 據(jù)讀取 將此語句放在 main 函數(shù)第一部分的末尾 即在建立好廣義表后清空緩 沖區(qū) 6 3 運(yùn)行結(jié)果運(yùn)行結(jié)果 1 輸入 a b c d 操作 thth 2 輸入 e a b c d 操作 tth 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 16 3 輸入 b c d e 操作 htht 4 輸入 3 4 5 2 d 操作 h tth 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 17 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 18 課程設(shè)計(jì)總結(jié) 課程設(shè)計(jì)總結(jié) 在此次的課程設(shè)計(jì)之前 我對廣義表的內(nèi)容了解的比較模糊 經(jīng)過此次課 程設(shè)計(jì) 對于廣義表的存儲結(jié)構(gòu)以及求頭尾操作 我有了較深的理解 廣義表 的用途十分廣泛 因此要求了廣義表的靈活性 廣義表的存儲結(jié)構(gòu)是鏈?zhǔn)降?且類似于二叉樹 廣義表與二叉樹的表頭結(jié)點(diǎn)均有兩個(gè)指針 但是二叉樹的指 針是自上而下的聯(lián)系 而廣義表中的尾指針是指向同層結(jié)點(diǎn) 因此有橫向的聯(lián) 系 這點(diǎn)上與二叉樹不同 對廣義表的求頭尾操作中要注意 廣義表的表頭是廣義表中的第一個(gè)元素 而廣義表的表尾是除第一個(gè)元素外其他元素組成的表 即廣義表的表尾一定是 廣義表 而表頭是否為廣義表 取決于第一個(gè)元素的類型 由于時(shí)間問題 很多地方我都沒有精雕細(xì)琢 導(dǎo)致本程序的容錯(cuò)能力不是 很好 即健壯性較差 需要改進(jìn)的地方有很多 本程序尤其對輸入的廣義表要 求很高 若輸入的廣義表出錯(cuò) 而用戶沒有發(fā)現(xiàn) 將會(huì)照成程序無法運(yùn)行 軟 件設(shè)計(jì)的健壯與否直接反應(yīng)了分析設(shè)計(jì)和編碼人員的水平 即所謂高手寫的程 序不容易死 因此我還有很多值得學(xué)習(xí)的內(nèi)容 有很多地方需要提高 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 19 參考文獻(xiàn) 1 譚浩強(qiáng) C 程序設(shè)計(jì) 北京 清華大學(xué)出版社 2002 2 嚴(yán)蔚敏 吳偉民 數(shù)據(jù)結(jié)構(gòu) C 語言版 北京 清華大學(xué)出版社 2002 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 20 附錄 源程序清單 include include typedef struct GLNode 廣義表結(jié)點(diǎn)定義 int tag 表結(jié)點(diǎn)類型 tag 0 表示原子結(jié)點(diǎn) tag 1 表示表結(jié)點(diǎn) union char data struct struct GLNode hr tr h 為表頭指針 t 為表尾指針 GList void creatlist GList c getchar 拾取一個(gè)合法字符 if c 空表的情況 Ls NULL c getchar if c return 空表的下一個(gè)合法字符應(yīng)該是 else 當(dāng)前輸入的廣義表非空 GList p 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 21 Ls GList malloc sizeof GLNode Ls tag 1 表結(jié)點(diǎn) if c 表頭為單原子 Ls hr GList malloc sizeof GLNode p Ls hr p tag 0 p data c 建立原子結(jié)點(diǎn) else 表頭為廣義表 creatlist Ls hr 對此廣義表遞歸建立存儲結(jié)構(gòu) c getchar if c creatlist Ls tr 當(dāng)前廣義表未結(jié)束 等待輸入下一個(gè)子表 else if c Ls tr NULL 當(dāng)前廣義表輸入結(jié)束 void GL Elem GList p 輸出原子 printf c p data 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 22 void printf GL GList Ls int if p 空表 printf else if p tag 1 p 指向表結(jié)點(diǎn) printf i printf GL p i else if p tag 0 GL Elem p 若 p 指向原子結(jié)點(diǎn)則輸出原子 GList k Ls tr 表結(jié)點(diǎn)的尾指針 if k printf 尾指針存在表示此表中還有元素 printf GL k i 遍歷下一結(jié)點(diǎn) else if k i void GetHead GList 沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告 23 GList p Ls 保存頭