1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)程序設(shè)計(jì)(大作業(yè))報(bào)告課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目：哈夫曼編碼器 院 系：信息技術(shù)學(xué)院 班 級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)2 班設(shè) 計(jì) 者：郭彩丁 學(xué) 號(hào)：202111010205 指導(dǎo)教師：王亞寧 設(shè)計(jì)時(shí)間：2021.1.9-2021.1.11 昆明學(xué)院昆明學(xué)院課程設(shè)計(jì)（大作業(yè)）任務(wù)書(shū)姓 名：郭彩丁 院 系：信息技術(shù)學(xué)院專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè) 學(xué) 號(hào)：202111010205 任務(wù)起止日期：2021.1.9-2021.1.11 課程設(shè)計(jì)題目：哈夫曼編碼器 課程設(shè)計(jì)要求：（1）初始化：鍵盤(pán)輸入n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)（2）編碼：利用建好的huffman樹(shù)生成huff

2、man編碼（3）輸出編碼（4）字符和頻度如下： 字符：空格 A B C D E F G H I J K L M N O P Q 頻度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 字符：R S T U V W X Y Z 頻度：48 51 80 23 8 18 1 16工作計(jì)劃及安排（1）在上機(jī)之前選題（2）選擇合適的數(shù)據(jù)結(jié)構(gòu)（3）結(jié)點(diǎn)結(jié)構(gòu)的設(shè)計(jì)（4）算法設(shè)計(jì)與分析（5）程序設(shè)計(jì)、實(shí)現(xiàn)、調(diào)試（6）提交課程設(shè)計(jì)報(bào)告指導(dǎo)教師簽字 年 月 日 課程設(shè)計(jì)（大作業(yè)）成績(jī)學(xué)號(hào)：202111010205 姓名：郭彩丁 指導(dǎo)教師：王亞寧 老師課程設(shè)計(jì)

3、題目： 哈夫曼編碼器 總結(jié)： 通過(guò)此次的課程設(shè)計(jì)使我認(rèn)識(shí)了哈夫曼樹(shù)的建立與應(yīng)用，復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中的樹(shù)的存儲(chǔ)結(jié)構(gòu)，怎樣構(gòu)造哈夫曼樹(shù)以及用哈夫曼樹(shù)進(jìn)行編碼。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)能使我們?yōu)槠渌n程打好基礎(chǔ)，而課程設(shè)計(jì)作為數(shù)據(jù)結(jié)構(gòu)中一個(gè)重要環(huán)節(jié)能更好的使我們加深對(duì)它的了解。指導(dǎo)教師評(píng)語(yǔ)：成績(jī)：填表時(shí)間：指導(dǎo)教師簽名： 目錄程序設(shè)計(jì)(大作業(yè))報(bào)告1昆明學(xué)院課程設(shè)計(jì)（大作業(yè)）任務(wù)書(shū)21.問(wèn)題描述52.基本要求53.數(shù)據(jù)結(jié)構(gòu)54.總體設(shè)計(jì)55.詳細(xì)設(shè)計(jì)65.1程序流程圖65.2初始化哈夫曼樹(shù)75.3輸入權(quán)值函數(shù)75.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號(hào)75.5構(gòu)造哈夫曼樹(shù)75.6根據(jù)哈夫曼樹(shù)求哈夫曼編碼76.測(cè)試與

4、調(diào)試76.1程序步驟演示76.1.1輸入各字符的權(quán)值76.1.2輸入字符86.1.3得到哈夫曼編碼86.2程序測(cè)試結(jié)果87.源程序清單108.實(shí)驗(yàn)心得131.問(wèn)題描述 構(gòu)造一棵哈夫曼樹(shù)，根據(jù)所需輸入的字符數(shù)目，分別輸入字符的頻度和字符，得到它們相應(yīng)的編碼，也就是設(shè)計(jì)一個(gè)哈夫曼編碼器。2.基本要求以字符的頻度為權(quán)值，建立哈夫曼樹(shù)，求哈夫曼編碼。根據(jù)字符及權(quán)值得到其相應(yīng)的編碼。3.數(shù)據(jù)結(jié)構(gòu)typedef struct int weight; /*結(jié)點(diǎn)的權(quán)值*/int lchild,rchild,parent; /*左、右孩子及雙親的下標(biāo)*/htnode;typedef htnode huffman

5、treem+1; /* huffmantree是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用，存儲(chǔ)哈夫曼樹(shù) */typedef structchar ch; /*存儲(chǔ)字符*/ char coden+1; /*存放編碼位串*/codenode;typedef codenode huffmancoden+1; /*huffmancode是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用,存儲(chǔ)哈夫曼編碼*/4.總體設(shè)計(jì)功能模塊劃分void main() /主函數(shù)void inithuffmantree(huffmantree ht) /初始化哈夫曼樹(shù)函數(shù)inithuffmantree()void inputweight(huffman

6、tree ht) /輸入權(quán)值函數(shù) void selectmin(huffmantree ht, int i, int *p1, int *p2)void createhuffmantree(huffmantree ht) /構(gòu)造huffman樹(shù)，htm為其根結(jié)void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹(shù)ht求huffman編5.詳細(xì)設(shè)計(jì)5.1程序流程圖開(kāi)始設(shè)置字符數(shù)目n輸入權(quán)值若輸入=n，輸入字符 N Y輸出編碼數(shù)結(jié)束5.2初始化哈夫曼樹(shù) void inithuffmantree(huffmantree ht)5.

7、3輸入權(quán)值函數(shù)void inputweight(huffmantree ht)5.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號(hào)void selectmin(huffmantree ht, int i, int *p1, int *p2)5.5構(gòu)造哈夫曼樹(shù)void createhuffmantree(huffmantree ht)5.6根據(jù)哈夫曼樹(shù)求哈夫曼編碼void huffmancodes(huffmantree ht,huffmancode hcd)6.測(cè)試與調(diào)試 6.1程序步驟演示 6.1.1輸入各字符的權(quán)值6.1.2輸入字符6.1.3得到哈夫曼編碼6.2程序測(cè)試結(jié)果字符：R S T U V W

8、 X Y Z頻度：48 51 80 23 8 18 1 16 10字符: A B C D E F G H I J K L M N O P Q頻度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 17.源程序清單#include<stdio.h>#include<stdlib.h> / 用到系統(tǒng)標(biāo)準(zhǔn)輸出函數(shù)的#include<string.h>#include<conio.h> /用到像getch()這種鍵盤(pán)輸入函數(shù)/* Huffman 樹(shù)的存儲(chǔ)結(jié)構(gòu)*/#define n 9 /*葉子數(shù)目根據(jù)需

9、要設(shè)定*/#define m 2*n-1 /* Huffman 樹(shù)中結(jié)點(diǎn)總數(shù) */* Huffman 樹(shù)的存儲(chǔ)結(jié)構(gòu)*/typedef struct /*結(jié)構(gòu)體定義*/int weight; /*結(jié)點(diǎn)的權(quán)值*/int lchild,rchild,parent; /*左、右孩子及雙親的下標(biāo)*/htnode; /*哈夫曼樹(shù)結(jié)點(diǎn)類(lèi)型*/typedef htnode huffmantreem+1; /* huffmantree是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用，存儲(chǔ)哈夫曼樹(shù) */typedef structchar ch; /*存儲(chǔ)字符*/ char coden+1; /*存放編碼位串*/codenode;

10、 /*編碼結(jié)點(diǎn)類(lèi)型*/typedef codenode huffmancoden+1; /*huffmancode是結(jié)構(gòu)數(shù)組類(lèi)型,其0號(hào)單元不用,存儲(chǔ)哈夫曼編碼*/void inithuffmantree(huffmantree ht) /*初始化哈夫曼樹(shù)函數(shù)inithuffmantree()*/int i; for(i=0;i<=m;i+) hti.weight=0; hti.lchild=hti.rchild=hti.parent=0; void inputweight(huffmantree ht) /*輸入權(quán)值函數(shù) */int i; for(i=1;i<=n;i+) pri

11、ntf(" 請(qǐng)輸入第%d個(gè)權(quán)值: ",i);scanf("%d",&hti.weight); printf("n"); void selectmin(huffmantree ht, int i, int *p1, int *p2)/* 在ht1.i中選兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，其序號(hào)為*p1和*p2，*p1中放權(quán)值最小的根結(jié)點(diǎn)的序號(hào)，*p2中放權(quán)值次小的根結(jié)點(diǎn)的序號(hào)*/int j,min1,min2; /* min1,min2分別是最小權(quán)值和次小權(quán)值*/ min1=min2=32767; *p1=*p2=0; for(j=1;j&

12、lt;=i;j+) if(htj.parent=0) /* j 為根結(jié)點(diǎn)*/ if(htj.weight<min1|min1=32767) if(min1!=32767) min2=min1; *p2=*p1; min1=htj.weight; *p1=j; else if(htj.weight<min2|min2=32767) min2=htj.weight; *p2=j; void createhuffmantree(huffmantree ht) /*構(gòu)造huffman樹(shù)，htm為其根結(jié)點(diǎn)*/ int i,p1,p2; inithuffmantree(ht); /* 將ht初

13、始化*/ inputweight(ht); /* 輸入葉子權(quán)值至ht 1.n的weight域*/ for(i=n+1;i<=m;i+) /* 共進(jìn)行n-1次合并，新結(jié)點(diǎn)依次存于hti中*/ selectmin(ht,i-1,&p1,&p2); /*在ht 1. i-1中選擇兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，其序號(hào)分別為p1和p2*/ htp1.parent=htp2.parent=i; hti.lchild=p1; /* 最小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子*/ hti.rchild=p2; /* 次小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的右孩子*/ hti.weight=htp1.weight+htp

14、2.weight; void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹(shù)ht求huffman編碼*/int c,p,i; /* c和p分別指示 ht中孩子和雙親的位置 */char cdn+1; /* 臨時(shí)存放編碼*/int start; /* 指示編碼在cd 中的起始位置*/cdn='0' getchar(); /* 編碼結(jié)束符*/printf("2.請(qǐng)依次輸入字符:"); for(i=1;i<=n;i+) /* 依次求葉子ht i的編碼*/ hcdi.ch=getchar();

15、 /* 讀入葉子ht i對(duì)應(yīng)的字符*/ start=n; /* 編碼起始位置的初值*/ c=i; /* 從葉子ht i開(kāi)始上溯*/ while(p=htc.parent)!=0) /* 直至上溯到ht c是樹(shù)根為止*/ cd-start=(htp.lchild=c)?'0':'1' /*若ht c是htp的左孩子，則生成代碼0，否則生成代碼1*/ c=p; /* 繼續(xù)上溯*/ strcpy(hcdi.code,&cdstart); /* 復(fù)制編碼位串*/ printf("n");printf("3.哈夫曼編碼結(jié)果為：n&qu

16、ot;);printf("n");for(i=1;i<=n;i+)printf(" 第%d個(gè)字符%c的編碼為：%sn",i,hcdi.ch,hcdi.code);void main()huffmantree t; huffmancode h; printf("|*#*|n"); printf("|*歡迎使用哈弗曼編碼系統(tǒng)！*|n"); printf("|*#*|n"); printf("n"); printf("1.請(qǐng)輸入%d個(gè)權(quán)值:n",n); p

17、rintf("n"); createhuffmantree(t); /* 構(gòu)造huffman樹(shù)*/ huffmancodes(t,h); /* 構(gòu)造huffman編碼*/8.實(shí)驗(yàn)心得通過(guò)這次課程設(shè)計(jì)，使我獲益匪淺。學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于我們是非常重要的，能使我們?cè)谝院蟮某绦蛟O(shè)計(jì)方面給我們很大的幫助。以此同時(shí)，這門(mén)課程的學(xué)習(xí)也是非常艱辛的，因?yàn)樗容^抽象難懂，這需要我們?cè)趯?shí)踐中不斷的克服。將近一個(gè)多星期的設(shè)計(jì)工作，讓我體會(huì)到作為一個(gè)編程人員是非常辛苦的。一個(gè)程序從算法到實(shí)現(xiàn)，再到應(yīng)用開(kāi)發(fā)是需要走很長(zhǎng)的一段路，不是一朝一夕就能實(shí)現(xiàn)的。編程過(guò)程中的辛苦只有親身體會(huì)才能明白，所以編好一個(gè)

18、程序?qū)τ谖覀兪欠浅２蝗菀椎摹?教師見(jiàn)習(xí)報(bào)告總結(jié)期待已久的見(jiàn)習(xí)已經(jīng)結(jié)束了，在龍巖三中高中部見(jiàn)習(xí)聽(tīng)課，雖然只是短短的兩個(gè)星期，但感觸還是蠻深的，以前作為一名學(xué)生坐在課室聽(tīng)課，和現(xiàn)在作為一名準(zhǔn)教師坐在課室聽(tīng)課是完全不同的感受，感覺(jué)自己學(xué)到了一些在平時(shí)課堂上學(xué)不到的東西。在這里，我獲得的不僅是經(jīng)驗(yàn)上的收獲，更多是教學(xué)管理，課堂教學(xué)等的理念，以及他們帶給我的種種思考。教育見(jiàn)習(xí)實(shí)踐過(guò)程：聽(tīng)課。教育見(jiàn)習(xí)的主要目的是讓學(xué)生在指導(dǎo)教師的引導(dǎo)下，觀摩教師上課方法、技巧等。聽(tīng)課是教育見(jiàn)習(xí)的主要內(nèi)容。我院規(guī)定在一周的見(jiàn)習(xí)中需完成至少6課的見(jiàn)習(xí)任務(wù)。我在教師的安排指導(dǎo)下，分別對(duì)高一、高二物理專(zhuān)業(yè)課型為主，其他課型齊頭的

19、方式，積極主動(dòng)的完成了聽(tīng)課任務(wù)，收到良好的效果。我聽(tīng)的第一節(jié)課是高二（8）班，這是一個(gè)平衡班，水平不如實(shí)驗(yàn)班高。在上課前?？迫卫蠋熞呀?jīng)跟我說(shuō)了這個(gè)班的紀(jì)律是比較差的，而且成績(jī)也不是很好。在我聽(tīng)課期間，確實(shí)有幾個(gè)學(xué)生在課堂上說(shuō)話，但是我發(fā)現(xiàn)了一個(gè)有趣的現(xiàn)象，這個(gè)現(xiàn)象我在往后的幾個(gè)班都發(fā)現(xiàn)了，就是絕大部分的學(xué)生的學(xué)習(xí)熱情都好高漲，積極舉手發(fā)言，積極參與課堂活動(dòng)。我跟老師們提起這個(gè)現(xiàn)象的時(shí)候，科任老師就跟我說(shuō)，一個(gè)班里不可能所有的學(xué)生都能全神貫注地聽(tīng)完一節(jié)課，所以作為一名教師，應(yīng)該想辦法吸引學(xué)生的注意力，調(diào)動(dòng)的積極性，比如可以以小組為單位，以搶答計(jì)分的形式調(diào)動(dòng)學(xué)生的積極性，這樣課堂氣氛就會(huì)活躍起來(lái)了

20、。在為期兩周的見(jiàn)習(xí)工作中，我真的有很大的感觸，我第一次感受到自己已經(jīng)從一名學(xué)生向一名教師靠近，走在校園里，每當(dāng)有學(xué)生叫我一聲老師，我在感到無(wú)比自豪的同時(shí)，還感受到了自己的責(zé)任。見(jiàn)習(xí)工作結(jié)束了，我要回到學(xué)校繼續(xù)我的學(xué)習(xí)了，但是我會(huì)好好記住我從*中學(xué)學(xué)到的一切，并應(yīng)用于我的專(zhuān)業(yè)學(xué)習(xí)中去。一、教學(xué)管理理念 在龍巖三中，從領(lǐng)導(dǎo)階層到一位普通的科任老師，都秉承以學(xué)生為主體的宗旨進(jìn)行學(xué)校的管理，進(jìn)行教學(xué)工作的開(kāi)展。作為一個(gè)課程改革的示范學(xué)校，一個(gè)教育實(shí)驗(yàn)基地。這所學(xué)校鼓勵(lì)著老師做各種研究，各種改革。每個(gè)班主任都有著自己的管理經(jīng)驗(yàn)與管理宗旨。有了這種思想的自由，自然這里也就充滿(mǎn)著探索與嘗試，從而有

21、所創(chuàng)造與進(jìn)步。在我見(jiàn)習(xí)的班集體中，班主任對(duì)他的學(xué)生說(shuō)：“我要讓你們成為學(xué)習(xí)型的管理者，也是管理型的學(xué)習(xí)者。”這樣一句簡(jiǎn)單的話，讓我感到這里老師進(jìn)行班級(jí)管理的良苦用心。他們關(guān)心的不只是學(xué)生的學(xué)習(xí)，更多的是從一個(gè)完整的人的概念出發(fā)，去培養(yǎng)學(xué)生多方面的素質(zhì)。二、教學(xué)理念 在見(jiàn)習(xí)期間，借著錄課的機(jī)會(huì)，我聽(tīng)了很多的市級(jí)，校級(jí)的公開(kāi)棵，還有理科實(shí)驗(yàn)班的課。在這些課堂上，讓我看到教學(xué)改革正在悄然進(jìn)行，有意識(shí)的老師正在努力體會(huì)“以學(xué)生為主體”的課堂模式。學(xué)生的創(chuàng)造也逐步成為教師追求的教學(xué)效果。其次，這里的老師也都在適應(yīng)著多媒體教學(xué)，信息化教學(xué)，使得課堂更加生動(dòng)，資源更加豐富，學(xué)生獲取學(xué)習(xí)資源的渠道也

22、就更多。盡管，這種教學(xué)理念、教學(xué)模式的推廣仍然有很長(zhǎng)的路，但似乎也并不遙遠(yuǎn)，相信，這股改革的浪潮會(huì)給教育領(lǐng)域帶來(lái)很大的沖擊。 三、實(shí)際工作經(jīng)驗(yàn) 在上面，是我在這所學(xué)校感受最深刻，也是認(rèn)為最有意義的收獲。實(shí)際工作經(jīng)驗(yàn)上，由于在指導(dǎo)老師的指導(dǎo)下，也獲取了許多。 在班主任工作上，我認(rèn)識(shí)到了一個(gè)老師的表率作用是很大的，學(xué)生時(shí)刻看老師，作為一個(gè)老師，應(yīng)該從自己嚴(yán)格要求，并影響感染學(xué)生。這就要求師生之間的相互交流必須是貼心的，也是帶有希望的。見(jiàn)習(xí)期間，班主任老師教給了我許多的班級(jí)管理經(jīng)驗(yàn)。我想這些經(jīng)驗(yàn)是寶貴的，更為寶貴的是老師的主動(dòng)精神。在他的言談中，看出一個(gè)老師對(duì)于班級(jí)管理的深度認(rèn)識(shí)。所以我想：一個(gè)好的班主任不應(yīng)只是從學(xué)習(xí)上給學(xué)生幫助，而是從一種“管理”的角度上去讓班級(jí)