第一篇：哈夫曼樹及應(yīng)用
常熟理工學(xué)院微課教學(xué)比賽教學(xué)設(shè)計(jì)
1、課程基本信息
課程名稱：哈夫曼樹及應(yīng)用
所屬課程：數(shù)據(jù)結(jié)構(gòu)與算法 課程所屬專業(yè)：軟件工程
適用專業(yè)：計(jì)算機(jī)類 選用教材：嚴(yán)蔚敏，吳偉明編著《數(shù)據(jù)結(jié)構(gòu)（C語言版）》北京：清華大學(xué)出版社，2007 主講人：周思林
時(shí)長：15分鐘 所屬學(xué)校：常熟理工學(xué)院
所屬院系：計(jì)算機(jī)科學(xué)與工程學(xué)院
2.教學(xué)背景
《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計(jì)算機(jī)類專業(yè)的學(xué)科基礎(chǔ)課程，本節(jié)微課“哈夫曼樹及應(yīng)用”屬于數(shù)據(jù)結(jié)構(gòu)課程中的“樹與二叉樹”章節(jié)中的重點(diǎn)及難點(diǎn)。2.1《數(shù)據(jù)結(jié)構(gòu)與算法》課程簡介及特點(diǎn)
《數(shù)據(jù)結(jié)構(gòu)與算法》課程是計(jì)算機(jī)類專業(yè)的學(xué)科基礎(chǔ)課程，同時(shí)也是計(jì)算機(jī)類專業(yè)的核心課程。課程的主要目標(biāo)是使學(xué)生理解和掌握基本數(shù)據(jù)結(jié)構(gòu)的概念、經(jīng)典算法的思想及實(shí)現(xiàn)方法，具備為應(yīng)用所涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的操作算法的能力。數(shù)據(jù)結(jié)構(gòu)與算法課程的學(xué)習(xí)也是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程，通過算法設(shè)計(jì)和實(shí)踐，培養(yǎng)學(xué)生的數(shù)據(jù)抽象和復(fù)雜程序設(shè)計(jì)能力。
《數(shù)據(jù)結(jié)構(gòu)與算法》課程由線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)和查找、排序算法為主體，結(jié)合應(yīng)用型本科院校特點(diǎn)，通過實(shí)踐理解和掌握基本數(shù)據(jù)結(jié)構(gòu)與算法，在實(shí)踐中提高學(xué)生的專業(yè)素養(yǎng)和專業(yè)技能。2.2本節(jié)微課課程特點(diǎn)
“樹與二叉樹——哈夫曼樹及應(yīng)用”是《數(shù)據(jù)結(jié)構(gòu)與算法》課程中第六章“樹與二叉樹”的核心內(nèi)容之一，同時(shí)也是該章節(jié)的教學(xué)難點(diǎn)。
本節(jié)微課采用案例驅(qū)動法進(jìn)行教學(xué)，調(diào)動學(xué)生的學(xué)習(xí)積極性，引導(dǎo)學(xué)生發(fā)現(xiàn)問題、思考問題、解決問題，利用形象的多媒體動畫展示案例的執(zhí)行過程，將哈夫曼樹及編碼復(fù)雜的程序結(jié)構(gòu)趣味化、形象化。由發(fā)送報(bào)文問題引入課程，循序漸進(jìn)的介紹哈夫曼樹的概念、邏輯特性、存儲結(jié)構(gòu)和算法實(shí)現(xiàn)，使學(xué)生掌握哈夫曼樹及編碼的基本概念和算法，提升學(xué)生的程序設(shè)計(jì)及邏輯思維能力。
3.教學(xué)設(shè)計(jì)
3.1教學(xué)目的
通過本節(jié)微課的學(xué)習(xí)，培養(yǎng)學(xué)生以下幾個(gè)方面的能力：（1）理解哈夫曼樹的應(yīng)用范圍和場景，并能靈活運(yùn)用；
（2）掌握哈夫曼樹及編碼的概念、求解算法基本思想，針對實(shí)例，能構(gòu)造哈夫曼樹，求解哈夫曼編碼；
（3）掌握哈夫曼樹的存儲結(jié)構(gòu)，理解靜態(tài)三叉鏈表結(jié)構(gòu)；
（4）掌握哈夫曼樹及編碼的求解算法，并能在實(shí)驗(yàn)中實(shí)現(xiàn)并驗(yàn)證算法（難點(diǎn)）；
根據(jù)學(xué)生理論基礎(chǔ)及程序編碼能力，本微課教學(xué)目標(biāo)分為三個(gè)水平：合格、中等、優(yōu)秀，具體標(biāo)準(zhǔn)如下：
合格水平：熟練掌握哈夫曼樹及編碼的基本概念，能構(gòu)造哈夫曼樹，求解哈夫曼編碼。中等水平：掌握概念和算法思想的基礎(chǔ)上，能上機(jī)實(shí)現(xiàn)驗(yàn)證哈夫曼樹及編碼的求解過程。優(yōu)秀水平：在上機(jī)實(shí)現(xiàn)算法的基礎(chǔ)上，能理論聯(lián)系實(shí)際，利用算法解決實(shí)際問題。3.2教學(xué)內(nèi)容
樹與二叉樹中哈夫曼樹的構(gòu)造和哈夫曼編碼的求解。（1）問題引入；
（2）哈夫曼樹的定義；（3）哈夫曼樹的構(gòu)造；（4）哈夫曼編碼的定義；（5）算法實(shí)現(xiàn)。3.3教學(xué)重點(diǎn)及難點(diǎn)
教學(xué)重點(diǎn)：哈夫曼樹及編碼求解的算法思想。教學(xué)難點(diǎn)：哈夫曼樹的存儲結(jié)構(gòu)，算法的實(shí)現(xiàn)。3.4教學(xué)方法
本微課內(nèi)容在算法思想上較為容易，但在具體實(shí)現(xiàn)上具有一定難度，因此采用啟發(fā)式教學(xué)和案例驅(qū)動式教學(xué)相結(jié)合的方法，提出問題引入課題，通過實(shí)例求解哈夫曼樹，循序漸進(jìn)求解哈夫曼編碼，通過多次提問的方式充分調(diào)動學(xué)生的學(xué)習(xí)積極性，使用動畫的形式演示實(shí)例的求解過程，增強(qiáng)課堂的形象性及趣味性，增加課堂容量。
課程設(shè)置由問題引入、哈夫曼樹的概念、哈夫曼樹的構(gòu)造、哈夫曼編碼、算法的實(shí)現(xiàn)共同組成，由淺入深，由理論到實(shí)踐，實(shí)現(xiàn)微課課堂的完整性和連貫性。
（1）問題引入
由報(bào)文傳送問題引入，如何來構(gòu)建傳送效率高，即報(bào)文長度最短的二進(jìn)制編碼。哈夫曼編碼也常用在數(shù)據(jù)壓縮中，是一種非常有效的壓縮方法。
問題：如何使報(bào)文長度最短？（2）哈夫曼樹的定義
針對給出的二叉樹實(shí)例T，回顧二叉樹的基本概念，樹的根節(jié)點(diǎn)、葉子結(jié)點(diǎn)，同時(shí)引入新的概念，結(jié)點(diǎn)的權(quán)值、路徑長度、結(jié)點(diǎn)的帶權(quán)路徑長度，樹的帶權(quán)路徑長度WPL。
分析實(shí)例，相同葉子結(jié)點(diǎn)權(quán)值，不同樹的組成形態(tài)，WPL權(quán)值不一定，引出哈夫曼樹的定義：帶權(quán)路徑長度最小的二叉樹。
問題：如何構(gòu)造哈夫曼樹？（3）哈夫曼樹的構(gòu)造
通過二叉樹的實(shí)例引出哈夫曼樹的構(gòu)造原則和哈夫曼樹的構(gòu)造思想。
通過流程圖的方式逐步介紹哈夫曼樹的構(gòu)造方法，利用標(biāo)注給出每步詳細(xì)事項(xiàng)。通過動畫的方式，逐步介紹以7、9、5、6、2為葉子結(jié)點(diǎn)的哈夫曼樹構(gòu)造過程。問題：哈夫曼樹是否唯一？（4）哈夫曼編碼
問題：哈夫曼樹中是否存在度為1的結(jié)點(diǎn)？ 分析二進(jìn)制編碼和哈夫曼樹的特點(diǎn)，講解哈夫曼編碼的求解過程。通過動畫演示哈夫曼樹進(jìn)行“0”“1”編碼的過程從而求解出哈夫曼編碼。問題：n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹總共有多少結(jié)點(diǎn)？引導(dǎo)出哈夫曼樹的存儲結(jié)構(gòu)。
（5）算法實(shí)現(xiàn)
分析：在哈夫曼樹的構(gòu)造過程中，需要用到孩子和雙親的信息，因此存儲結(jié)構(gòu)中需要保存雙親及左右孩子的信息，采用三叉鏈表來表示，同時(shí)在求解編碼過程需要從根到葉子結(jié)點(diǎn)，因此采用靜態(tài)鏈表作為存儲結(jié)構(gòu)。
具體實(shí)現(xiàn)分以下部分進(jìn)行：
a：根據(jù)葉子結(jié)點(diǎn)給靜態(tài)三叉鏈表賦初值；
b：在靜態(tài)三叉鏈表中依次構(gòu)造根權(quán)值為7、13、16、29的節(jié)點(diǎn)，刪除所選兩棵樹的操作為修改該結(jié)點(diǎn)雙親的值；
c：產(chǎn)生哈夫曼編碼，針對靜態(tài)三叉鏈表的存儲結(jié)構(gòu)內(nèi)容，從葉子結(jié)點(diǎn)a開始，依次找到雙親信息，并獲得哈夫曼編碼的逆序序列。
提煉出哈夫曼編碼的產(chǎn)生方法，結(jié)合程序代碼進(jìn)行詳細(xì)講解?？偨Y(jié)本次課程主要內(nèi)容，提出課后思考題。
4、教學(xué)總結(jié)
本次微課由報(bào)文傳送引出主題，由理論到實(shí)現(xiàn)，結(jié)合形象的動畫演示循序漸進(jìn)的描述了哈夫曼樹和編碼的定義與實(shí)現(xiàn)。通過問題導(dǎo)入和案例驅(qū)動式教學(xué)方法的使用，使學(xué)生難以理解的二叉樹結(jié)構(gòu)與算法形象化、趣味化。通過實(shí)例的講解，使學(xué)生快速掌握了哈夫曼樹及哈夫曼編碼的算法思想，再由實(shí)例結(jié)合存儲結(jié)構(gòu)的方式，讓學(xué)生理解哈夫曼樹的相關(guān)程序設(shè)計(jì)，提升學(xué)生的學(xué)習(xí)興趣，增強(qiáng)學(xué)生邏輯結(jié)構(gòu)分析能力和程序設(shè)計(jì)能力。
第二篇：樹和哈夫曼樹實(shí)驗(yàn)報(bào)告
樹和哈夫曼樹實(shí)驗(yàn)報(bào)告
一．實(shí)驗(yàn)?zāi)康?/p>
練習(xí)樹和哈夫曼樹的有關(guān)操作，和各個(gè)算法程序，理解哈夫曼樹的編碼和譯碼 二．實(shí)驗(yàn)環(huán)境
Microsoft visual c++ 三．實(shí)驗(yàn)問題描述
1.問題描述：建立一棵用二叉鏈表方式存儲的二叉樹，并對其進(jìn)行遍歷（先序、中序和后序），打印輸出遍歷結(jié)果。
基本要求：從鍵盤接受輸入先序序列，以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并將此二叉樹按照“樹狀形式”打印輸出，然后對其進(jìn)行遍歷（先序、中序和后序），最后將遍歷結(jié)果打印輸出。在遍歷算法中要求至少有一種遍歷采用非遞歸方法。測試數(shù)據(jù)：
ABC??DE?G??F???（其中?表示空格字符）輸出結(jié)果為： 先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.問題描述：利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接受端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?；疽螅?至少完成功能1-2）一個(gè)完整的系統(tǒng)應(yīng)具有以下功能： I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。基本要求：
E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。
D：譯碼（Decoding)。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。
P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrint中。T：印哈夫曼樹（TreePrinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。測試數(shù)據(jù)：
設(shè)權(quán)值w=（5，29，7，8，14，23，3，11），n=8。
按照字符‘0’或‘1’確定找左孩子或右孩子，則權(quán)值對應(yīng)的編碼為：
5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。四．實(shí)驗(yàn)主要程序流
實(shí)驗(yàn)題目一主要程序：
1．void CreatBiTree(BitTree *bt)//用擴(kuò)展先序遍歷序列創(chuàng)建二叉樹，如果是#當(dāng)前樹根置為空，否則申請一個(gè)新節(jié)點(diǎn)// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} } 2．void Visit(char ch)//訪問根節(jié)點(diǎn) { printf(“%c ”,ch);} 3．
void PreOrder(BitTree root){ if(root!=NULL){ Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } 4． void InOrder(BitTree root){ if(root!=NULL){ InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);} } 5．int PostTreeDepth(BitTree bt)//后序遍歷求二叉樹的高度遞歸算法// { int hl,hr,max;if(bt!=NULL){ hl=PostTreeDepth(bt->LChild);//求左子樹的深度
hr=PostTreeDepth(bt->RChild);//求右子樹的深度
max=hl>hr?hl:hr;//得到左、右子樹深度較大者
return(max+1);//返回樹的深度 } else return(0);//如果是空樹，則返回0 } 6．void PrintTree(BitTree Boot,int nLayer)//按豎向樹狀打印的二叉樹 // { int i;if(Boot==NULL)return;PrintTree(Boot->RChild,nLayer+1);for(i=0;i
// 函數(shù)功能：建立哈夫曼樹（調(diào)用鍵盤建立哈夫曼樹或調(diào)用從文件建立哈夫曼樹的函數(shù)）void HuffmanTree::CreateHuffmanTree(){char Choose;cout<<“你要從文件中讀入哈夫曼樹(按1)，還是從鍵盤輸入哈夫曼樹(按2)？”;cin>>Choose;if(Choose=='2'){ //鍵盤輸入建立哈夫曼樹 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //從哈夫曼樹文件hfmTree.dat中讀入信息并建立哈夫曼樹
CreateHuffmanTreeFromFile();} } 3.// 從鍵盤建立哈夫曼樹函數(shù)
// 函數(shù)功能：從鍵盤建立哈夫曼樹 //函數(shù)參數(shù)：無 //參數(shù)返回值：無
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num;cout<<“n請輸入源碼字符集個(gè)數(shù)：”;cin>>Num;if(Num<=1){ cout<<“無法建立少于2個(gè)葉子結(jié)點(diǎn)的哈夫曼樹。nn”;return;} LeafNum=Num;Node=new HuffmanNode[2*Num-1];for(int i=0;i cout<<“請輸入第”<