2015級(jí)軟件工程專業(yè)數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)題目

1、內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1868: 2015 級(jí)軟件班數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)1 :線性表的應(yīng)用(6學(xué)時(shí))Description輸入一個(gè)字符串，按照字符串的輸入順序創(chuàng)建一個(gè)線性表A。線f表A中包含有三類字符：數(shù)字字符、字母字符、其他字符。試寫一個(gè)函數(shù)實(shí)現(xiàn)對(duì)線性表A的拆分，使得線性表A、B、C分別各自指向同一類字符。 要求如下：(1)在拆分時(shí)，必須使用原表 A的結(jié)點(diǎn)空間，不能額外創(chuàng)建新結(jié)點(diǎn)。(2)拆分后，原表A指向數(shù)字字符，且其內(nèi)容的前后次序與原表中的 前后次序必須一致，新的表 B指向字母字符，新的表 C指向其他字符。 其中要求刪除B中的重復(fù)結(jié)點(diǎn)(如“ abbcdexec

2、，變?yōu)椤?abcdex”)。(3)判斷拆分后的表A是否是中心對(duì)稱的(如123321或12321都是中 心對(duì)稱的)，若是，則輸出1,否則輸出0。Input輸入格式要求：輸入一行字符串，可以帶空格，并以做為輸入結(jié)束標(biāo)志， 中間不能輸入？字符串長度不做限制。如可以輸入：1aabccd2e3fo3c ?第1頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告Output輸出格式要求：前3行分別輸出表A、B、C的內(nèi)容（若某個(gè)表為空表，則相應(yīng)行輸出-1 ）,第4行輸出表A是否為對(duì)稱的標(biāo)志。如輸出：123321 （拆分后表A的內(nèi)容）abcdef g （拆分后表B的內(nèi)容）（!（拆分后表C的內(nèi)容）

3、1（拆分后表A是中心對(duì)稱的）Sampl e Input1aabccd2e3f（!3c?Sampl e Output123321abcdefg（!1HINT為了方便判斷線性表是否為中心對(duì)稱的，可以使用雙向鏈表結(jié)構(gòu)（但不是必須的）。1869: 2015 級(jí)軟件工程專業(yè) 數(shù)據(jù)結(jié)構(gòu)與算法 實(shí)驗(yàn)2:表達(dá)式求值（9學(xué)時(shí)12學(xué)時(shí)）Description表達(dá)式求值是計(jì)算機(jī)實(shí)現(xiàn)程序設(shè)計(jì)語言中的基本問題之一，也是棧應(yīng)用的一個(gè)典型例子，通過本實(shí)驗(yàn)，對(duì)輸入的一個(gè)表達(dá)式進(jìn)行求值。第2頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康?掌握棧的應(yīng)用；掌握算符優(yōu)先表達(dá)式求值的算法；掌握字符串處理和數(shù)

4、值的轉(zhuǎn)換。具體要求如下：(1)表達(dá)式以字符串形式輸入，并以#結(jié)束。如輸入：12* (12.4+20.15) /25#(2)運(yùn)算數(shù)可以是實(shí)數(shù)，運(yùn)算符有+ - * / ,帶括號(hào)，可以輸入以下4個(gè)函數(shù): 平方sqr()、正弦sin()、余弦cos()、四舍五入取整rd()。函數(shù)的優(yōu)先級(jí)要高 于 + - * / 。(3)對(duì)輸入的表達(dá)式進(jìn)行計(jì)算，計(jì)算結(jié)果要求必須保留小數(shù)點(diǎn)后2位。(4)能夠有效判別表達(dá)式的輸入格式是否有誤(如缺失操作數(shù)、括號(hào)不匹配、 函數(shù)名錯(cuò)誤等)，若輸入格式錯(cuò)誤，輸出為“ error !”。Input表達(dá)式以字符串形式輸入，并以#結(jié)束，可輸入的符號(hào)為：數(shù)字、小數(shù)點(diǎn)、“+ - * / ”

5、 4個(gè)運(yùn)算符、括號(hào)、以及指定的4個(gè)函數(shù)名，其他符號(hào)為非法符號(hào)， 如出現(xiàn)則意味著輸入格式錯(cuò)誤。下面是一些輸入示例：12*(12.4+20.15)/25#-格式正確12.001+(2*5/37#-格式錯(cuò)誤12*sin(30)+sqr(2.3)#-格式正確12ab+5#-格式錯(cuò)誤12+5-*2 #-格式錯(cuò)誤sin(20)+cosa(30)#-格式錯(cuò)誤Output若表達(dá)式輸入格式正確，則輸出計(jì)算結(jié)果，結(jié)果要求必須保留2位小數(shù)，如輸入:12*(12.4+20.15)/25#,輸出為：15.62。如輸出為 16 或 15.624,都為錯(cuò)誤。第3頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)

6、報(bào)告若表達(dá)式輸入格式錯(cuò)誤，則輸出為：error !,如輸入：15.4/(2-sin(5.12)*)+21#,輸出為：error !。Sampl e Input12*(12.4+20.15)/25#Sampl e Output15.62HINT.核心算法用棧結(jié)構(gòu)來實(shí)現(xiàn)；.首先需對(duì)輸入的表達(dá)式字符串進(jìn)行解析，分離出操作數(shù)和運(yùn)算符，在分離過 程中，可以對(duì)非法的操作數(shù)和運(yùn)算符進(jìn)行判錯(cuò)。若輸入的操作數(shù)和運(yùn)算符正確， 則分別入棧；.函數(shù)可以看成是單目運(yùn)算符，即只需一個(gè)操作數(shù)；.注意函數(shù)的優(yōu)先級(jí)要高于其他的運(yùn)算符，請(qǐng)正確設(shè)置運(yùn)算符優(yōu)先級(jí)表；.在出棧的過程中，可以判別括號(hào)匹配和操作數(shù)匹配的錯(cuò)誤。第4頁，共16

7、頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告1870: 2015 級(jí)軟件工程專業(yè) 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)3:面向數(shù)字圖像的Huffman編/譯碼器的設(shè)計(jì)與實(shí)現(xiàn)（12學(xué)時(shí)）Description“Huffman-樹”不僅能對(duì)文本數(shù)據(jù)進(jìn)行編碼、譯碼，提高文本數(shù)據(jù)的傳輸效率，同時(shí)它也能 對(duì)多媒體數(shù)據(jù)（如：數(shù)字圖像、視頻等）進(jìn)行編碼、譯碼，從而實(shí)現(xiàn)多媒體數(shù)據(jù)的壓縮存儲(chǔ)。 目前，在 Web互聯(lián)網(wǎng)上廣泛使用的 JPEG圖像格式就采用了 Huffman編碼，與其他圖像格 式（如：BMP、TIF等）相比，同一副圖像采用 JPEG格式時(shí)所需的存儲(chǔ)空間是最少的。在 這個(gè)實(shí)驗(yàn)中，請(qǐng)?jiān)O(shè)計(jì)一個(gè) Huffman

8、編/譯碼器，并模擬數(shù)字圖像的壓縮存儲(chǔ)（編碼）和解碼 顯示（譯碼）的過程。（1）構(gòu)造 “Huffman-樹”：讀入一個(gè)大小為N*M （N為圖像的高度，M為圖像的寬度）的灰度圖像塊，該 圖像中的每個(gè)像素（元素）的取值范圍是0255,取值為0表示該像素是“黑色”， 取值為255表示該像素是“白色”，其他取值表示介于“黑色”和“白色”之間 的灰度值。統(tǒng)計(jì)讀入圖像塊中每種灰度值出現(xiàn)的次數(shù)，并去除出現(xiàn)次數(shù)為零的灰度值，以此作為構(gòu)造“ Huffman-樹”所需的權(quán)值。說明：在構(gòu)造“ Huffman-樹”的過程中，當(dāng)有多個(gè)待合并元素的權(quán)值相同時(shí)， 每次選擇灰度值較小的兩個(gè)元素進(jìn)行合并。Huffman編碼（壓縮

9、存儲(chǔ)）：讀入新的灰度圖像塊，利用已建立好的 “Huffman-樹”對(duì)其進(jìn)行編碼，將圖像的寬度、高度信息和編碼結(jié)果保存到文件 （如：compress_image.txt ）中，同時(shí)計(jì)算Huffman編碼的壓縮比并輸出。壓縮 比的計(jì)算公式如不：壓縮比=原始圖像所需比特?cái)?shù)/壓縮后圖像所需比特?cái)?shù)。Huffman譯碼（解碼顯示）：讀入壓縮存儲(chǔ)的灰度圖像，利用已建立好的 “Huffman-樹”對(duì)其進(jìn)行譯碼，將譯碼結(jié)果按照原有寬度、高度還原圖像，并將還原之后的圖像保存到文件（如：decoding_image.txt ）中。Input該實(shí)驗(yàn)有多組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行包含兩個(gè)以空格間隔的正整數(shù) N和M

10、,它們的取值范圍都 為1, 100,分別表示圖像的高度和寬度；之后的 N行數(shù)據(jù)是一個(gè)灰度圖像，每 行含有M個(gè)以空格間隔的正整數(shù)P （0 P0 255） , P表示對(duì)應(yīng)像素的灰度值。當(dāng)輸入的N和M都為零時(shí)結(jié)束。第5頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告Output每組測試數(shù)據(jù)的輸出占一行，輸出的內(nèi)容為“ Huffman編碼的壓縮比”Sampl e Input8 8162 162 162 161 162 157 163 161162 162 162 161 162 157 163 161162 162 162 161 162 157 163 161162 162 162

11、 161 162 157 163 161162 162 162 161 162 157 163 161164 164 158 155 161 159 159 160160 160 163 158 160 162 159 156159 159 155 157 158 159 156 1570 0Sampl e OutputHuffman 編碼的壓縮比為2.72:1HINT在oj系統(tǒng)中提交該實(shí)驗(yàn)的代碼時(shí)，請(qǐng)將圖像壓縮存儲(chǔ)結(jié)果保存到文件的代碼和 壓縮圖像解碼結(jié)果保存到文件的代碼都注釋掉，只輸出Huffman樹的壓縮比即可。壓縮結(jié)果和解碼結(jié)果在檢查程序時(shí)查看。1871: 2015 級(jí)軟件工程專業(yè) 算法

12、與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)4:小型文本搜索引擎的實(shí)現(xiàn)（15學(xué)時(shí)）Description隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展，如何從海量數(shù)據(jù)中查找所需內(nèi)容，不僅是科研人員關(guān)注的熱點(diǎn)問題，許多IT公司也先后推出了各自的搜索引擎，如： Google、百度、Bing等。搜索引擎 的核心是如何對(duì) Web網(wǎng)頁構(gòu)建有效的索引，以便能夠快速查找和匹配查詢關(guān)鍵詞，并及時(shí) 地將搜索結(jié)果返回給用戶。第6頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告在這個(gè)實(shí)驗(yàn)中，請(qǐng)實(shí)現(xiàn)一個(gè)英文單詞的二叉查找樹，并可根據(jù)輸入的英文單詞進(jìn)行搜索，同時(shí)可給出單詞出現(xiàn)的次數(shù)。具體要求如下：(1)構(gòu)造二叉查找樹：讀入文本內(nèi)容，過濾掉阿拉伯?dāng)?shù)字和

13、標(biāo)點(diǎn)符號(hào)，并將英文字母的大寫形式全部 轉(zhuǎn)換成小寫形式。按照英文字母表的順序構(gòu)造英文單詞的二叉查找樹。當(dāng)兩個(gè)英文單詞的首字母相同時(shí)，按第二個(gè)字母進(jìn)行排序，依次類推。當(dāng)待插入的單詞已在二叉查找樹中，則將該單詞的出現(xiàn)次數(shù)增1。(2)遍歷二叉查找樹：搜索：輸入一個(gè)待檢索單詞，在二叉查找樹中進(jìn)行查找，如果能找到該單詞，則輸出該單詞及其出現(xiàn)次數(shù)；實(shí)現(xiàn)二叉查找樹的中序遍歷，并將遍歷結(jié)果輸出到屏幕上。(3)刪除結(jié)點(diǎn)：給定一個(gè)停用詞列表(停用詞是指對(duì)搜索沒有作用的詞，如：of, and, a, an, the等等)，將二叉查找樹中的屬于停用詞表中的單詞依次刪除(不僅刪除結(jié)點(diǎn)，還需清空記錄該單詞位置信息的單鏈表)

14、。Input輸入有以下四種情況：當(dāng)輸入大寫英文字母T時(shí)，表示下一行是文本內(nèi)容，包含若干英文單詞、標(biāo)點(diǎn) 符號(hào)以及阿拉伯?dāng)?shù)字，用于構(gòu)建二叉查找樹。文本內(nèi)容以字符結(jié)束，文本中的每個(gè)英文單詞的長度不超過 30個(gè)字母。當(dāng)輸入大寫英文字母S時(shí)，表示后面跟著的若干行都是停用詞，每個(gè)停用詞占 一行，當(dāng)某行是字符#時(shí)，表示停用詞輸入完畢。對(duì)每個(gè)停用詞，都需要?jiǎng)h 除二叉查找樹中的相應(yīng)結(jié)點(diǎn)，即：每輸入一個(gè)停用詞，執(zhí)行一次刪除結(jié)點(diǎn)的操作。當(dāng)輸入大寫英文字母V時(shí)，表示中序遍歷二叉查找樹。遍歷結(jié)果中的每個(gè)單詞 占一行，先輸出該單詞，然后輸出一個(gè)空格，再輸出該單詞出現(xiàn)的次數(shù)。當(dāng)輸入大寫英文字母Q時(shí)，表示后面跟著的若干行都是

15、查詢?cè)~，每個(gè)查詢?cè)~占 一行，當(dāng)某行是字符#時(shí)，表示查詢?cè)~輸入完畢。對(duì)每個(gè)查詢?cè)~，都需要在 二叉查找樹中的搜索相應(yīng)結(jié)點(diǎn)，如果找到，則輸出該單詞及其出現(xiàn)次數(shù)，如果未 找到，則輸出-1。每個(gè)查詢?cè)~的查詢結(jié)果占一行，先輸出該單詞，然后輸出一個(gè) 空格，再輸出該單詞出現(xiàn)的次數(shù)。當(dāng)輸入大寫英文字母X時(shí)，表示輸入結(jié)束。第7頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告Output按照輸入的要求輸出相應(yīng)結(jié)果。提示：只有在V或者Q狀態(tài)下，才有內(nèi)容需要 輸出。Sampl e InputAccording to characteristics of Mongolian wordformation,

16、a method for removing inflectionalsuffixesfrom word images of the Mongolian Kanjur is proposed in this paper. VQ#Safter against all almost also although among an and these they this those though three to#Q# S thetherefore第8頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告two#Qthe#VTThis paper presents a new method

17、to recognize machineprinted traditionalMongolian characters by using backpropagation (BP) neural networks. Q the # V Q mongolian ocr #XSampl e Outputa 1 according 1 characteristics 1 for 1 formation 1 from 1 images 1 in 1 inflectional 1 is 1 kanjur 1 method 1 mongolian 2 of 2 paper 1 proposed 1 remo

18、ving 1 suffixes 1 the 1 this 1 to 1 word 2第9頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告the 1 the 1-1 a 1 according 1 characteristics 1 for 1formation 1images 1in 1 inflectional 1 is 1 kanjur 1 method 1 mongolian 2 of 2 paper 1 proposed 1 removing 1 suffixes 1 word 2 -1 a 2according 1characteristics 1 characte

19、rs 1for 1 formation 1 from 1 images 1 in 1 inflectional 1 is 1 kanjur 1 machine 1 method 2 mongolian 3 networks 1 neural 1 new 1第10頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告of 2paper 2 presents 1 printed 1 propagation proposed 1 recognize 1 removing 1 suffixes 1this 1traditional 1using 1word 2 mongolian 3-1H

20、INT提示1: char *到string變量可以直接用=,因?yàn)閟tring類重載了 二操作符，而 且提供了以char *為源的拷貝構(gòu)造函數(shù)。但 string變量到char *就不能用=, 但是string類的c_str（）函數(shù)可以返回它的字符串的首地址，因此可以用如下 方法將string變量賦給char *。（希望這個(gè)提示對(duì)你實(shí)現(xiàn)該實(shí)驗(yàn)有幫助！）提示2：為了保證程序編譯正確，請(qǐng)將以下兩個(gè)頭文件均加入程序開頭處：#include #include 提示3:結(jié)點(diǎn)類的參考定義：class Nodeprivate:char* key; /英文單詞int count; /出現(xiàn)次數(shù)Node* leftChild;Node* rightChild;）；第11頁，共16頁內(nèi)蒙古大學(xué)計(jì)算機(jī)學(xué)院&軟件學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告提示4:二叉查找樹參考定義：class Binaryprivate:Node* root;public:Binary();Binary();bool find(Node* ,const char *,Node*&,Node*&);/ 查找void print(Node*);/中序遍歷bool insert(char *&);/插入一個(gè)元素bool deletel(Node*,const char*);