數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)匯總

教學(xué)單位信息工程系學(xué)生學(xué)號0143017541數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)匯總題目課程設(shè)計(jì)匯總學(xué)生姓名專業(yè)名稱軟件工程指導(dǎo)教師葉從歡2016年5月31日目錄數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)匯總 1課程設(shè)計(jì)一、多項(xiàng)式的基本運(yùn)算 3實(shí)驗(yàn)?zāi)康模?3實(shí)驗(yàn)內(nèi)容： 3解題思路： 3實(shí)驗(yàn)小結(jié)： 8課程設(shè)計(jì)二、棧的應(yīng)用—逆波蘭式求值 8實(shí)驗(yàn)?zāi)康模?8實(shí)驗(yàn)內(nèi)容： 9解題思路： 9實(shí)驗(yàn)小結(jié)： 12課程設(shè)計(jì)三、圖的應(yīng)用—簡易的社交網(wǎng)絡(luò)圖 13實(shí)驗(yàn)?zāi)康模?13實(shí)驗(yàn)內(nèi)容： 13解題思路： 14實(shí)驗(yàn)小結(jié)： 22課程設(shè)計(jì)四、哈夫曼編碼 23實(shí)驗(yàn)?zāi)康模?23實(shí)驗(yàn)內(nèi)容： 23解題思路： 23實(shí)驗(yàn)小結(jié)： 28課程設(shè)計(jì)五、哈希表的相關(guān)運(yùn)算 29實(shí)驗(yàn)?zāi)康模?29實(shí)驗(yàn)內(nèi)容： 29解題思路： 29實(shí)驗(yàn)小結(jié)： 33課程設(shè)計(jì)六、廣義表的創(chuàng)建與遍歷 33實(shí)驗(yàn)?zāi)康模?33實(shí)驗(yàn)內(nèi)容： 33思路分析： 34實(shí)驗(yàn)總結(jié)： 40課程設(shè)計(jì)七、排序方法 40實(shí)驗(yàn)?zāi)康模?40實(shí)驗(yàn)內(nèi)容： 40解題思路： 41實(shí)驗(yàn)小結(jié)： 48課程設(shè)計(jì)一、多項(xiàng)式的基本運(yùn)算實(shí)驗(yàn)?zāi)康模赫莆站€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)和線性表的典型應(yīng)用—多項(xiàng)式求和、差運(yùn)算，通過實(shí)驗(yàn)進(jìn)一步加深對線性表的存儲結(jié)構(gòu)的理解與熟悉。實(shí)驗(yàn)內(nèi)容：鏈?zhǔn)酱鎯Y(jié)構(gòu)的實(shí)現(xiàn)：已知：f(x)=100x＾100+5x＾50-30x＾10+10,g(x)=150x＾90-5x＾50+40x＾20+20x＾10+3x,求和與差。解題思路：定義一個(gè)結(jié)構(gòu)體數(shù)組，p存儲系數(shù),q存儲指數(shù)。分別輸出兩次輸入的多項(xiàng)式。將兩次輸入的多項(xiàng)式的指數(shù)按從大到小的順序進(jìn)行排列，同時(shí)相應(yīng)的系數(shù)要進(jìn)行交換。輸出時(shí)如果進(jìn)行如果當(dāng)前該項(xiàng)與下一項(xiàng)的的系數(shù)相同，將兩項(xiàng)系數(shù)相加后輸出，并跳過下一項(xiàng)，如果不相等，直接輸出。輸出時(shí)需注意的問題：當(dāng)系數(shù)為0時(shí)，該項(xiàng)不輸出當(dāng)系數(shù)為負(fù)數(shù)時(shí)，不要再在前面輸出+。程序如下：結(jié)果驗(yàn)證：實(shí)驗(yàn)小結(jié)：課程設(shè)計(jì)二、棧的應(yīng)用—逆波蘭式求值實(shí)驗(yàn)?zāi)康模赫莆諚５奶攸c(diǎn)及其描述方法；掌握棧的各種基本操作；掌握棧的一個(gè)經(jīng)典應(yīng)用-逆波蘭式求值問題。實(shí)驗(yàn)內(nèi)容：從鍵盤敲入一個(gè)整數(shù)表達(dá)式，先將其轉(zhuǎn)化為逆波蘭表達(dá)式，再計(jì)算值。解題思路：逆波蘭式又叫后綴表達(dá)式，規(guī)定把運(yùn)算符號放在兩個(gè)操作數(shù)的后面。在后綴表達(dá)式中，不存在運(yùn)算符的優(yōu)先級問題，也不存在任何括號。后綴表達(dá)式求值的步驟：1.初始化一個(gè)空操作數(shù)棧:2.從前到后讀取后綴表達(dá)式字符。如果是操作數(shù)直接入棧。如果讀到一個(gè)操作符@，彈出棧頂元素a和新的棧頂元素b，執(zhí)行b@a，將結(jié)果壓入棧中；3.最后棧中只剩下一個(gè)元素，即表達(dá)式的值。源代碼如下：實(shí)驗(yàn)結(jié)果驗(yàn)證：實(shí)驗(yàn)小結(jié)：課程設(shè)計(jì)三、圖的應(yīng)用—簡易的社交網(wǎng)絡(luò)圖實(shí)驗(yàn)?zāi)康模赫莆請D的幾種存儲方法（鄰接矩陣、鄰接表等）；掌握圖的連通和圖中各節(jié)點(diǎn)的聯(lián)系。實(shí)驗(yàn)內(nèi)容：給出如圖所示的簡易社交連通圖：AABCDEF要求：輸入A,B,C,D,E,F處的人名，計(jì)算某兩人之間的陌生度（即權(quán)值的大小之和）與連通兩人的通路（權(quán)值在下面的代碼中已給出）。解題思路：直接相連的兩個(gè)節(jié)點(diǎn)間邊的權(quán)值就是兩節(jié)點(diǎn)間的親密度（陌生度），權(quán)值越小，節(jié)點(diǎn)間越親密；通過鄰接矩陣給出的數(shù)值可以求出兩節(jié)點(diǎn)間的親密度；通過迪克斯特卡算法可以求出不相鄰的兩節(jié)點(diǎn)間的權(quán)值之和和經(jīng)過的節(jié)點(diǎn)，從而達(dá)到解決問題的目的。程序代碼如下： 運(yùn)行結(jié)果：實(shí)驗(yàn)小結(jié)：課程設(shè)計(jì)四、哈夫曼編碼實(shí)驗(yàn)?zāi)康模河盟鶎W(xué)的知識構(gòu)造一棵哈夫曼樹并以英文字母出現(xiàn)的次數(shù)做權(quán)值，遍歷哈夫曼樹同時(shí)輸出每個(gè)字母的哈夫曼編碼。實(shí)驗(yàn)內(nèi)容：從txt文件讀入一段英文，統(tǒng)計(jì)其中每個(gè)字母出現(xiàn)的頻率，并輸出其哈夫曼編碼。解題思路：構(gòu)造哈夫曼編碼的方法如下：第一步定義一個(gè)結(jié)點(diǎn)的結(jié)構(gòu)體，包括結(jié)點(diǎn)的權(quán)值，結(jié)點(diǎn)的雙親結(jié)點(diǎn)，左孩子，右孩子。并定義兩個(gè)HTNode,*HuffmanTree為該類型的名字。第二步創(chuàng)建一個(gè)Select函數(shù)用來選擇結(jié)點(diǎn)較小的結(jié)點(diǎn)權(quán)值和下標(biāo)。實(shí)現(xiàn)方法主要利用兩個(gè)for循環(huán)實(shí)現(xiàn)。首先判斷是否是單個(gè)結(jié)點(diǎn)如果是跳出for循環(huán)如果不是定義p和s記錄當(dāng)前結(jié)點(diǎn)的權(quán)值和記錄當(dāng)前結(jié)點(diǎn)的下標(biāo)。接著通過一個(gè)for循環(huán)進(jìn)行選擇把結(jié)點(diǎn)權(quán)值最小的14結(jié)點(diǎn)權(quán)值和下標(biāo)記錄分別記錄在p和s中。第三步構(gòu)造哈夫曼樹和求每個(gè)字符的哈夫曼編碼。先判斷結(jié)點(diǎn)個(gè)數(shù)n是否小于等于1如果是則返回如果大于1則計(jì)算出哈夫曼樹中共有m=2n-1個(gè)結(jié)點(diǎn)。然后創(chuàng)建一個(gè)HTNode類型的數(shù)組HT存儲結(jié)點(diǎn)個(gè)數(shù)（結(jié)點(diǎn)的相關(guān)信息），再定義一個(gè)HuffmanTree類型的指針P用來指向數(shù)組HT。將HT中前n個(gè)單元保存輸入的結(jié)點(diǎn)信息，后m-n個(gè)單元保存為空結(jié)點(diǎn)。接著構(gòu)造哈夫曼樹，其實(shí)現(xiàn)方法為首先利用Select函數(shù)選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)s1和s2再將將s1和s2合并從而得到這兩個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)保存為i，且雙親結(jié)點(diǎn)的權(quán)值為s1,s2權(quán)值之和。接著從葉子到根逆向求每個(gè)字符的哈夫曼編碼。其實(shí)現(xiàn)方法為：首先創(chuàng)建一個(gè)字符指針數(shù)組HC和一個(gè)字符型指針數(shù)組cd用來存儲"0"和"1"。定義c表示結(jié)點(diǎn)序號，f表示c結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號，接著通過一個(gè)for循環(huán)將建立好的哈夫曼樹的左邊賦值為0右邊賦值1，再為每一個(gè)結(jié)點(diǎn)創(chuàng)建一個(gè)長度為n-start的字符數(shù)組用來存儲哈夫曼編碼。最后把從cd地址開始且含有NULL結(jié)束符的字符串賦值到以HC開始的地址空間。第四步main函數(shù)的實(shí)現(xiàn)。首先定義一個(gè)HuffmanTree類型的HT初始化為空。接著輸入哈夫曼權(quán)值的個(gè)數(shù)判斷個(gè)數(shù)是否小于等于1如果小于等于1則輸出"輸入錯(cuò)誤,哈夫曼權(quán)值的個(gè)數(shù)要大于1"。如果大于1則創(chuàng)建一個(gè)w指針數(shù)組用來存儲結(jié)點(diǎn)權(quán)值，最后通過調(diào)用HuffmanCoding函數(shù)輸出每個(gè)結(jié)點(diǎn)的哈夫曼編碼。程序如下：結(jié)果驗(yàn)證：實(shí)驗(yàn)小結(jié)：課程設(shè)計(jì)五、哈希表的相關(guān)運(yùn)算實(shí)驗(yàn)?zāi)康模航⒁粋€(gè)哈希表，完成其插入、刪除、查找等相關(guān)基本運(yùn)算，在實(shí)驗(yàn)的過程中加深對相關(guān)知識點(diǎn)的理解和掌握。實(shí)驗(yàn)內(nèi)容：建立{16,74,60,43,54,90,46,31,29,88,77}哈希表，哈希函數(shù)為：H（k）=key%p，并采用線性探查法解決沖突；在上述哈希表中查找關(guān)鍵字為29的記錄；在上述哈希表中刪除關(guān)鍵字為77的記錄，然后再將其插入。解題思路：根據(jù)關(guān)鍵碼值(Keyvalue)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key)=a·key+b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。若其中H(key）中已經(jīng)有值了，就往下一個(gè)找，直到H(key）中沒有值了，就放進(jìn)去。處理沖突：線性探測法：Hi=(H(key)+di)MO