表達(dá)式求值廣義表的運(yùn)算課程設(shè)計(jì)報(bào)告(已修改)
2025-02-02 18:48 本頁面
【正文】 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目: 表達(dá)式求值廣義表的運(yùn)算學(xué) 院 信息工程學(xué)院 __________專 業(yè) ____ 計(jì)算機(jī)科學(xué)與技術(shù)年級(jí)班別 _12級(jí)四班___________學(xué) 號(hào) 2012051419________學(xué)生姓名 張海濤_____指導(dǎo)教師 米文麗___成 績(jī) _2013年12月 題目：廣義表的運(yùn)算。本設(shè)計(jì)要求實(shí)現(xiàn)廣義表的建立、查找、輸出、取表尾、以及求深度、求逆表等。一、問題分析與任務(wù)定義：此程序需要完成以下幾個(gè)任務(wù)：首先要將輸入的用數(shù)組存儲(chǔ)的廣義表轉(zhuǎn)化成以廣義表的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的廣義表，這個(gè)過程也就是生成廣義表；查找廣義表，查找廣義表要返回一個(gè)值flag，當(dāng)flag=1時(shí)，程序查找到待查的元素，當(dāng)flag=0時(shí)，程序沒有找到待查元素；輸出廣義表，遍歷廣義表，輸出廣義表的遍歷結(jié)果；取表頭，返回表頭結(jié)點(diǎn)；取表尾，將廣義表從第二個(gè)元素開始復(fù)制到另一個(gè)廣義表中；求廣義表的深度，遍歷每一層廣義表，將廣義表內(nèi)每層廣義表深度最大的廣義表相加為同一層所求過的子表中深度的最大值，最后返回值加一即為廣義表的深度；求逆表，將廣義表逆向輸出。實(shí)現(xiàn)本程序需要解決以下問題： 如何根據(jù)廣義表的特點(diǎn)建立廣義表。 用什么方法才能查找到廣義表中每一個(gè)元素，如何標(biāo)志是否找到待查元素。 建立廣義表，如何根據(jù)廣義表的存儲(chǔ)結(jié)構(gòu)的特點(diǎn)建立廣義表。 求廣義表的深度的依據(jù)是什么。 運(yùn)用什么方法才能將廣義表逆序。 如何實(shí)現(xiàn)廣義表的遍歷。二、概要設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)選擇：設(shè)計(jì)思想：廣義表是線性表的一種推廣，但它并不是線性表。課本上在介紹廣義表的計(jì)本概念的基礎(chǔ)上，介紹了廣義表的存儲(chǔ)及應(yīng)用。廣義表濃縮了線性表、數(shù)組等常見的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，在有效利用存儲(chǔ)空間方面更勝一籌，目前在文本處理、人工智能、代數(shù)操作和計(jì)算機(jī)圖形方面等各個(gè)領(lǐng)域都具有應(yīng)用價(jià)值。所以在我當(dāng)時(shí)拿到這個(gè)題目的時(shí)候，雖然它只有短短的幾行字，但是我深深的感覺到了它的難度，在后來課程設(shè)計(jì)中，也證實(shí)了我的感覺，每個(gè)功能都實(shí)在是太難實(shí)現(xiàn)了，所以只有各個(gè)擊破了。設(shè)計(jì)程序時(shí)，先起草了流程圖，通過流程圖來看，就使得程序鮮明易懂，接下來先寫好了主函數(shù)，通過主函數(shù)的調(diào)用，實(shí)現(xiàn)題目要求的各個(gè)功能，使得程序模塊化，便于編寫，即使不會(huì)寫的子函數(shù)，也可以先空著，等待以后想到好的方法后再對(duì)其進(jìn)行操作，同時(shí)在程序界面上也做了美化，使人感覺舒暢，另外通過一個(gè)循環(huán)，能讓用戶進(jìn)行循環(huán)操作，不至于每次只能進(jìn)行一項(xiàng)操作,這個(gè)循環(huán)用的和線性表里的循環(huán)有點(diǎn)類似，但其實(shí)現(xiàn)的操作不同，當(dāng)然有了以前實(shí)驗(yàn)的基礎(chǔ)，這次編寫起來，也感覺輕松了不少。廣義表的存儲(chǔ)結(jié)構(gòu)：由于廣義表中的元素本身又可以具有結(jié)構(gòu)，是一種帶有層次的非線性結(jié)構(gòu)，因此難以用順序存儲(chǔ)的結(jié)構(gòu)表示。通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素可用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)結(jié)構(gòu)如圖圖2所示：tag=0atom*tp 圖1原子結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)tag=1*hp*tp 圖2結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)每個(gè)結(jié)點(diǎn)由三個(gè)域構(gòu)成。其中tag是一個(gè)標(biāo)志位，用來區(qū)分當(dāng)前結(jié)點(diǎn)是原子結(jié)點(diǎn)還是子表。當(dāng)tag為1時(shí)，該結(jié)點(diǎn)是子表，第二個(gè)域?yàn)閔p，用以存放子表的地址；當(dāng)tag為0時(shí)，該結(jié)點(diǎn)是原子結(jié)點(diǎn)，第二個(gè)域?yàn)閍tom，用以存放元素值。tp域是用來存放與本元素同一層的下一個(gè)元素對(duì)應(yīng)結(jié)點(diǎn)的地址，當(dāng)該元素是所在層的最后一個(gè)元素時(shí)，tp的值為NULL。廣義表及結(jié)點(diǎn)類型描述如下：typedef char ElemType。typedef struct GLode//廣義表結(jié)構(gòu)體的定義{ int tag。 /*結(jié)點(diǎn)類型標(biāo)識(shí)*/ union { ElemType atom。 /*原子值*/ struct GLode *hp。 /*指向子表的指針*/ } val。 struct GLode *tp。 /*指向下一個(gè)元素*/} GList。例如：建立廣義表：（a，b（c，d），e） ，如圖3 1^ 0a0b1^ 0c0d1^0e1^^ 圖3 廣義表的存儲(chǔ)圖示求廣義表的逆表需要用堆棧存儲(chǔ)廣義表的元素，棧的數(shù)據(jù)類型如下：typedef char ElemType。typedef struct { ElemType data[maxlen] 。 int top。}SeqStack。程序流程圖如圖。main()建立一個(gè)用字符數(shù)組存儲(chǔ)的廣義表，用字符指針s指向它輸入廣義表生成數(shù)組廣義表結(jié)構(gòu)遍歷廣義表建立堆棧查找待查元素，flag=1，找到待查元素，反之，沒有查到。求廣義表的深度，并輸出。求廣義表的表尾，并輸出。求廣義表的表頭，并輸出。輸出結(jié)果再見 歡迎使用輸出退出運(yùn)算，并輸出再見。求廣義表的逆表，并輸出。 三、詳細(xì)設(shè)計(jì)與編碼建立廣義表CreateGL(char *amp。s)。在生成廣義表之前，用一個(gè)數(shù)組存儲(chǔ)廣義表，并用指針s指向數(shù)組，通過數(shù)組中的元素生成廣義表?；舅枷胧牵涸趶V義表表達(dá)式中，遇到左括號(hào)”(”時(shí)遞歸
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1