数学系09级课程设计课件

《数据结构》课程设计布置3个题目，任选两个。设计报告内容：标题（题目）问题描述数据结构描述1）类型描述；2）用图示法举一个例子4.主要算法描述：测试方法描述----如何输入测试数据，会出现的结果。特点（特色、扩展的功能、…..）在两个题目的报告完成后，最后给出本次设计的小结（感想、建议等）附录；源代码，要求程序风格清晰易理解，有充分的注释。一、基于哈夫曼编码的数据压缩/解压程序1.问题描述：将任意一个指定的文本文件中的字符进行哈夫曼编码，生成一个编码文件（压缩文件）和哈夫曼树文件；反过来，可将一个压缩文件解码还原为一个文本文件。2.要求：1）可设计一个菜单：

C----Coding

D----Decoding

L----ListTextDocument

Q----Quit2）选择C时：输入一个待压缩的文本文件名称（可带路径）。如：D:\lu\lu.txt

统计文本文件中各字符的个数作为权值，生成哈夫曼树；将哈夫曼树存入磁盘文件中。将文本文件利用哈夫曼树进行编码，生成压缩文件。压缩文件名称=文本文件名.COD如：D:\lu\lu.COD

哈夫曼树文件名称=文本文件名.hfm如：D:\lu\lu.hfm3)选择D时：输入一个待解压的压缩文件名称（可带路径）如：D:\lu\lu.COD

从对应的哈夫曼文件中读出哈夫曼树。二、求复杂表达式的值（课本343页综合实验题2）问题描述输入一个含有运算符和运算函数的表达式，计算其结果。要求1)以字符串方式输入一个复杂的表达式；表达式中包括：数值（整数、实数）、一般运算符（正号，负号，加、减、乘、除、求模、乘方、括号）；如输入：“123*(45.7/25-20^3+12.4*(123%4))”

2)利用栈，根据各运算符的优先度进行数值计算，显示结果

3)循环回1)，继续下个表达式的输入。功能扩展（自己定制）：

1）表达式中可含有运算函数:abs—绝对值，sqrt—开方

exp---指数函数，ln---对数，sin,cos,tan

如输入：“123.45*sin(abs(-23)*3.14)+exp(3)”

上述函数在C++中有对应的函数调用（fabs,sqrt,exp,log,sin,cos,tan）。2)增加自定义的运算，如阶乘：30！等

3)自己进一步扩充……..

如显示计算过程等三、一元多项式的计算问题描述将多个多项式输入并存储在内存中，然后对多项式进行加，减，数乘等运算。要求：

1）可设计菜单：

I----输入多项式

C----多项式计算

L----显示多项式

Q----退出2)选I：输入一个或多个多项式。如输入：f=3,0-7,46,50,-13-7x^4+6x^5g=4,16,4-570,-14x^1+6x^4-5x^73)选C：输入计算表达式，然后计算结果并显示如输入：h=f+g

显示结果：h=3+4x^1-1x^4+6x^5-5x^7

如输入：k=f-g

显示结果：k=3-4x^1-13x^4+6x^5+5x^74)选L：显示内存中现有的多项式。如：显示出：f=3-7x^4+6x^5g=4x^1+6x^4-5x^7h=3+4x^1-1x^4+6x^5-5x^7说明评分方法：程序50%文档50%是否按要求完成各部分文档的撰写；测试方法和测试数据的设计总结源程序的风格及必要的注释将所有源程序、可执行文件和课程设计报告（若