您所在位置：主题：请教各路高手！急！
lxl615@126.com
[专家分：0] 发布于 2007-08-24 13:16:00
有哪位仁兄知道做其中的一道，请发到我邮箱lxl615@126.com，不胜感激！！！
一、基于哈夫曼编码的数据压缩/解压程序
1. 问题描述：将任意一个指定的文本文件中的字符进行哈夫曼编码，生成一个编码文件（压缩文件）；反过来，可将一个压缩文件解码还原为一个文本文件。
2. 要求：
1）可设计一个菜单：
C----Coding
D----Decoding
L----List Text Document
Q----Quit
2）选择C时：
输入一个待压缩的文本文件名称（可带路径）。
如：D:\lu\lu.txt
统计文本文件中各字符的个数作为权值，生成哈夫曼树；
将文本文件利用哈夫曼树进行编码，生成压缩文件。
压缩文件名称=文本文件名.COD 如：D:\lu\lu.COD
压缩文件内容=哈夫曼树的核心内容+编码序列
3) 选择D时：
输入一个待解压的压缩文件名称（可带路径 ）
如：D:\lu\lu.COD
从文件中读出哈夫曼树，并利用哈夫曼树将编码序列解码；
生成（还原）文本文件。
文件文件名称=压缩文件名+“_new.txt”
如：D:\lu\lu_new.txt
4）选择L时：
输入一个待压缩的文本文件名称（可带路径）。
如：D:\lu\lu_new.txt
显示出该文本文件的内容
3. 功能扩展（自己定制）：
编码使用二进制位，利用位运算进行真正的数据压缩。
可对任何文件进行压缩。
显示出各种重要信息，如压缩率、各字符的哈夫曼编码表
……..
二、文件检索
1. 问题描述 输入关键字，在指定的一个（或多个）文本文件中查找关键字。若文本中有关键字的内容，显示其位置。
2. 要求
1) 可设计菜单：
I----输入关键字
F----指出搜索范围
S----开始搜索
Q----退出
2) 选I：输入要搜索的关键字：
如：输入：computer
3) 选F：指出搜索范围：输入要搜索的文本文件名称（可多个文件名称）。
如：输入：d:\mydoc\abc.txt
d:\work\readme.txt
4) 选S：开始搜索。在指定的文本文件里查找是否有指定的关键字，若有，显示关键字所在行的内容。然后询问是否继续搜索下一个，若是，继续往后搜索关键字。若找不到，则显示“无此关键字”.
可将文件的内容读入成为一个字符串（主串），然后在主串中搜索子串（关键字）。
3. 功能扩展（自己定制）：
1） 关键字可以带“？” 代表任意一个字符 如 com??ter
2) 可以输入多个关键字，关键字之间有 “and”关系。
如 computer
calculator
在文本文件中同时有这两个关键字才是检索成功。
3） 输入搜索范围时，可输入文件夹的名称。则搜索的文件是文件夹中的所有文本文件。
4） 自己进一步扩充……..
三、一元多项式的计算
1. 问题描述 将多个多项式输入并存储在内存中，然后对多项式进行加，减，数乘等运算。
2. 要求：
1） 可设计菜单
I----输入多项式
C----多项式计算
L----显示多项式
Q----退出
2) 选I：输入一个或多个多项式。
如输入：f= 3,0 -7,4 6,5 0,-1 3-7x^4+6x^5
g= 4,1 6,4 -57 0,-1 4x^1+6x^4-5x^7
3) 选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^7
4) 选L：显示内存中现有的多项式。
如： 显示出： f= 3-7x^4+6x^5
g= 4x^1+6x^4-5x^7
h=3+4x^1-1x^4+6x^5-5x^7
5) 每个多项式必须用单链表来存储：
typedef struct node
{ float coef; //系数
int exp; // 指数
struct node *next; // 指向下个结点的指针
} nodetype;
3. 功能扩展（自己定制）：
可增加两个多项式的相乘；如 f*g
可增加1个多项式的求导数；如 f ’
……..
四、正方形破坏者
1. 问题描述 左边的图中是由24根火柴拼成的3×3的网格。每根火柴的长度为1。在这个网格中，可以发现若干个不同大小的正方形—9个边长为1，4个边长为2和1个边长为3的正方形。
如图中所示，网格中的火柴按从上到下从左到右的顺序编号。如果从中拿出若干根火柴，会形成一个不完整的3×3网格，原来网格中的某些正方形就会被破坏。右图是拿出编号为12, 17和23的火柴后形成的不完整网格，原来网格中有5个边长为1，3个边长为2和1个边长为3的正方形被破坏，仅剩4个边长为1和1个边长为2的正方形。
现在的问题是，给定一个完整或不完整的N×N网格（含有不超过2N(N十1)根火柴），如何从中拿出最少根数的火柴，使得其中所有的正方形均被破坏？
2. 要求：
1)【输入数据】
测试数据包括两行：第一行包括一个正整数N(N≤5），表示网格的边长；第二行的第一个整数K表示网格中已经缺失的火柴根数，接下来的K个整数表示缺失火柴的编号。注意，如果K=0，表示输入的网格是一个完整的N×N网格，否则表示是一个从完整的N×N网格中拿出K根火柴后所形成的不完整的N×N网格。
2)【 输出数据】
输出至少需要拿走几根火柴，是哪几根火柴。
3)【样例输入】
网格的边长N：2
网格中已经缺失的火柴根数K：0
网格的边长N： 3
网格中已经缺失的火柴根数K： 3 12 17 23
4) 本题所用数据结构自己设计。
3. 功能扩展（自己定制）：
显示出原来的网格和所有的正方形均被破坏后的网格；
讨论时间复杂度和空间复杂度；
……….
[em4]
一、基于哈夫曼编码的数据压缩/解压程序
1. 问题描述：将任意一个指定的文本文件中的字符进行哈夫曼编码，生成一个编码文件（压缩文件）；反过来，可将一个压缩文件解码还原为一个文本文件。
2. 要求：
1）可设计一个菜单：
C----Coding
D----Decoding
L----List Text Document
Q----Quit
2）选择C时：
输入一个待压缩的文本文件名称（可带路径）。
如：D:\lu\lu.txt
统计文本文件中各字符的个数作为权值，生成哈夫曼树；
将文本文件利用哈夫曼树进行编码，生成压缩文件。
压缩文件名称=文本文件名.COD 如：D:\lu\lu.COD
压缩文件内容=哈夫曼树的核心内容+编码序列
3) 选择D时：
输入一个待解压的压缩文件名称（可带路径 ）
如：D:\lu\lu.COD
从文件中读出哈夫曼树，并利用哈夫曼树将编码序列解码；
生成（还原）文本文件。
文件文件名称=压缩文件名+“_new.txt”
如：D:\lu\lu_new.txt
4）选择L时：
输入一个待压缩的文本文件名称（可带路径）。
如：D:\lu\lu_new.txt
显示出该文本文件的内容
3. 功能扩展（自己定制）：
编码使用二进制位，利用位运算进行真正的数据压缩。
可对任何文件进行压缩。
显示出各种重要信息，如压缩率、各字符的哈夫曼编码表
……..
二、文件检索
1. 问题描述 输入关键字，在指定的一个（或多个）文本文件中查找关键字。若文本中有关键字的内容，显示其位置。
2. 要求
1) 可设计菜单：
I----输入关键字
F----指出搜索范围
S----开始搜索
Q----退出
2) 选I：输入要搜索的关键字：
如：输入：computer
3) 选F：指出搜索范围：输入要搜索的文本文件名称（可多个文件名称）。
如：输入：d:\mydoc\abc.txt
d:\work\readme.txt
4) 选S：开始搜索。在指定的文本文件里查找是否有指定的关键字，若有，显示关键字所在行的内容。然后询问是否继续搜索下一个，若是，继续往后搜索关键字。若找不到，则显示“无此关键字”.
可将文件的内容读入成为一个字符串（主串），然后在主串中搜索子串（关键字）。
3. 功能扩展（自己定制）：
1） 关键字可以带“？” 代表任意一个字符 如 com??ter
2) 可以输入多个关键字，关键字之间有 “and”关系。
如 computer
calculator
在文本文件中同时有这两个关键字才是检索成功。
3） 输入搜索范围时，可输入文件夹的名称。则搜索的文件是文件夹中的所有文本文件。
4） 自己进一步扩充……..
三、一元多项式的计算
1. 问题描述 将多个多项式输入并存储在内存中，然后对多项式进行加，减，数乘等运算。
2. 要求：
1） 可设计菜单
I----输入多项式
C----多项式计算
L----显示多项式
Q----退出
2) 选I：输入一个或多个多项式。
如输入：f= 3,0 -7,4 6,5 0,-1 3-7x^4+6x^5
g= 4,1 6,4 -57 0,-1 4x^1+6x^4-5x^7
3) 选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^7
4) 选L：显示内存中现有的多项式。
如： 显示出： f= 3-7x^4+6x^5
g= 4x^1+6x^4-5x^7
h=3+4x^1-1x^4+6x^5-5x^7
5) 每个多项式必须用单链表来存储：
typedef struct node
{ float coef; //系数
int exp; // 指数
struct node *next; // 指向下个结点的指针
} nodetype;
3. 功能扩展（自己定制）：
可增加两个多项式的相乘；如 f*g
可增加1个多项式的求导数；如 f ’
……..
四、正方形破坏者
1. 问题描述 左边的图中是由24根火柴拼成的3×3的网格。每根火柴的长度为1。在这个网格中，可以发现若干个不同大小的正方形—9个边长为1，4个边长为2和1个边长为3的正方形。
如图中所示，网格中的火柴按从上到下从左到右的顺序编号。如果从中拿出若干根火柴，会形成一个不完整的3×3网格，原来网格中的某些正方形就会被破坏。右图是拿出编号为12, 17和23的火柴后形成的不完整网格，原来网格中有5个边长为1，3个边长为2和1个边长为3的正方形被破坏，仅剩4个边长为1和1个边长为2的正方形。
现在的问题是，给定一个完整或不完整的N×N网格（含有不超过2N(N十1)根火柴），如何从中拿出最少根数的火柴，使得其中所有的正方形均被破坏？
2. 要求：
1)【输入数据】
测试数据包括两行：第一行包括一个正整数N(N≤5），表示网格的边长；第二行的第一个整数K表示网格中已经缺失的火柴根数，接下来的K个整数表示缺失火柴的编号。注意，如果K=0，表示输入的网格是一个完整的N×N网格，否则表示是一个从完整的N×N网格中拿出K根火柴后所形成的不完整的N×N网格。
2)【 输出数据】
输出至少需要拿走几根火柴，是哪几根火柴。
3)【样例输入】
网格的边长N：2
网格中已经缺失的火柴根数K：0
网格的边长N： 3
网格中已经缺失的火柴根数K： 3 12 17 23
4) 本题所用数据结构自己设计。
3. 功能扩展（自己定制）：
显示出原来的网格和所有的正方形均被破坏后的网格；
讨论时间复杂度和空间复杂度；
……….
[em4]
