哈夫曼码编译码系统递归替换问题跳马问题长整数运算问题数据结构课程设计课程设计.docx
《哈夫曼码编译码系统递归替换问题跳马问题长整数运算问题数据结构课程设计课程设计.docx》由会员分享，可在线阅读，更多相关《哈夫曼码编译码系统递归替换问题跳马问题长整数运算问题数据结构课程设计课程设计.docx（34页珍藏版）》请在冰点文库上搜索。
哈夫曼码编译码系统递归替换问题跳马问题长整数运算问题数据结构课程设计课程设计
*****大学
***（**学院
数据结构与算法课程设计
题目：
哈夫曼码的编/译码系统;递归替换问题;跳马问题;
长整数运算问题
专业班级：
*******
姓名：
***
学号：
***
指导教师：
%%%%
成绩：
_____________
摘要
本程序主要解决的是哈夫曼码的编/译码系统，跳马问题，递归替换问题和长整数运算问题。
采用哈夫曼算法的设计思想。
根据给定的权值构成二叉树森林，在森林中任意选取两棵根结点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。
跳马问题是在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。
递归替换问题，编写程序，扩展C/C++源文件中的#include指令（以递归的方式）。
请以文件名的内容替换形如下面的代码行。
#include“filename”长整数的四则运算实现两个任意长的整数的加、减、乘运算，由于要实现任意长整数，就需要运用到相应的双向线性链表，以实现整数的任意长的加、减、乘运算。
长整数运算实现计算任意长的整数的加、减、乘运算，先输入长整数的最多位数，然后输入要运算的长整数，进行加减运算并显示出这两个数的运算。
利用双向循环链表实现长整数的存储，每个结点含一个整形变量。
程序使用VisualC++6.0工具开发
关键词：
哈夫曼码的编/译码系统，排序、递归算法、数组数据结构、链式数据结构、整数运算。
一、哈夫曼码的编/译码系统
编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。
1、数据结构设计
数据结构可用结构体,节点结构体包括字符的名称、字符权值、左右孩子标志、对应字符的前缀码、左孩子指针、右孩子指针、双亲指针。
题目要求全程信息用文件保存，应写入文件中，提供文件的输入输出等操作；在过程中需有字符及权值录入、字符前缀码生成、文段编码、文段译码，故应分别建立功能模块；另外还应提供键盘式选择菜单实现程序运行。
2、算法设计
利用树的思想创建最优二叉树然后得到对应字符的前缀码
Bnode*
creat_Btree（intk,Bnodez[MAX],intn,Bnode*head[20]）
{
Bnode*a,*b,*c;
inti=0,j;
a=b=c=（Bnode*）malloc（sizeof（Bnode））;
k--;//k相当于循环控制变量，这里-1是循环的需要
while（k>1）
{
a=search_min（z,n,k）;
a->flag='3';//修改标志，说明该节点已被选择
b=search_min（z,n,k）;
c->weight=a->weight+b->weight;
a->parent=c;//指针移动，节点关系确立
b->parent=c;
c->lchild=a;
c->rchild=b;
a->flag='0';
b->flag='1';
c->flag='2';
n++;//z中元素个数加一
z[n]=*c;
k--;//根节点个数增减一个（a，b变成孩子节点，c成为新的根节点）
}
if（k==1）
{
for（i=0;i<=n;i++）
if（z[i].flag=='2'）
return（&z[i]）;
}
}
3、调试分析
1前缀码
图3.1
2HAFFMAN编码
图3.2
4、执行结果
图3.3
5、源程序（带注释）
#include
#include
#include
#defineMAX100
typedefstruct
{
intweight;//节点的权值
charname;//节点的字符
charflag;//标志，左孩子0，右孩子1，根2
charencod[MAX];//编码存储数组
structBnode*lchild;//左孩子
structBnode*rchild;//右孩子
structBnode*parent;//双亲
}Bnode;
Bnode*
creat_Btree（intk,Bnodez[MAX],intn,Bnode*head[20]）
{
Bnode*a,*b,*c;
inti=0,j;
a=b=c=（Bnode*）malloc（sizeof（Bnode））;
k--;//k相当于循环控制变量，这里-1是循环的需要
while（k>1）
{
a=search_min（z,n,k）;
a->flag='3';//修改标志，说明该节点已被选择
b=search_min（z,n,k）;
c->weight=a->weight+b->weight;
a->parent=c;//指针移动，节点关系确立
b->parent=c;
c->lchild=a;
c->rchild=b;
a->flag='0';
b->flag='1';
c->flag='2';
n++;//z中元素个数加一
z[n]=*c;
k--;//根节点个数增减一个（a，b变成孩子节点，c成为新的根节点）
}
if（k==1）
{
for（i=0;i<=n;i++）
if（z[i].flag=='2'）
return（&z[i]）;
}
}
二．递归替换问题
编写程序，扩展C/C++源文件中的#include指令（以递归的方式）。
请以文件名的内容替换形如下面的代码行。
#include“filename”
1.采用类语言定义相关的数据类型
typedefstruct//创建结构体，让文件的读写方便
{
chardata[MAX];//数据项
}char1;
int
print（charch[MAX],intn）//递归函数
2.算法设计
{
FILE*fp,*fp1;
chars[MAX];//s，存储#后面的include
char1b[MAX];//b,文件中内容在内存中的存储位置
inti=0,k,d=0,j,flag;//switch参数，用于确认调用函数的参数
if（（fp=fopen（ch,"rb+"））==NULL）
{
printf（"文件打开失败！
\n"）;
exit（0）;
}
while（!
feof（fp））
{
fread（&b[i],1,sizeof（char1）,fp）;
i++;
if（b[i-1].data[0]=='}'）//结构体数组计数器
break;
}
k=i-1;//记录b大小，可以认为是对应文件的行数
fclose（fp）;
2.算法设计
{
FILE*fp,*fp1;
chars[MAX];//s，存储#后面的include
char1b[MAX];//b,文件中内容在内存中的存储位置
inti=0,k,d=0,j,flag;//switch参数，用于确认调用函数的参数
if（（fp=fopen（ch,"rb+"））==NULL）
{
printf（"文件打开失败！
\n"）;
exit（0）;
}
while（!
feof（fp））
{
fread（&b[i],1,sizeof（char1）,fp）;
i++;
if（b[i-1].data[0]=='}'）//结构体数组计数器
break;
}
k=i-1;//记录b大小，可以认为是对应文件的行数
fclose（fp）;
3.函数的调用关系图
4.调试分析
不调用库函数，实现strcpy函数，要返回char*。
5.测试结果
图1.调用测试函数
6.源程序（带注释）
#include
#include
#include
#defineMAX100
typedefstruct//创建结构体，让文件的读写方便
{
chardata[MAX];//数据项
}char1;
int
print（charch[MAX],intn）//递归函数
{
FILE*fp,*fp1;
chars[MAX];//s，存储#后面的include
char1b[MAX];//b,文件中内容在内存中的存储位置
inti=0,k,d=0,j,flag;//switch参数，用于确认调用函数的参数
if（（fp=fopen（ch,"rb+"））==NULL）
{
printf（"文件打开失败！
\n"）;
exit（0）;
}
while（!
feof（fp））
{
fread（&b[i],1,sizeof（char1）,fp）;
i++;
if（b[i-1].data[0]=='}'）//结构体数组计数器
break;
}
k=i-1;//记录b大小，可以认为是对应文件的行数
fclose（fp）;
if（（fp1=fopen（"辅助.c","ab+"））==NULL）
{
printf（"文件打开失败！
\n"）;
exit（0）;
}
d=0;//s数组存取计数器
for（i=0;i{
if（b[i].data[0]=='#'）//发现include，递归调用print
{
for（j=2;j<9;j++）
{
s[d]=b[i].data[j];
d++;
}
if（（strcmp（s,"include"））==0）
{
flag=b[i].data[19]-'0';
switch（flag）//带选择的递归调用
{
case1:
fp=print（"filename1.c",1）;break;
case2:
fp=print（"filename2.c",2）;break;
case3:
fp=print（"filename3.c",3）;break;
default:
break;
}
}
else//否则的话讲代码存入辅助文件
{
printf（"%s\n",b[i].data）;
fwrite（&b[i],1,sizeof（char1）,fp）;
fputc（'\r',fp）;
fputc（'\n',fp）;
}
}
else//否则的话讲代码存入辅助文件
{
printf（"%s\n",b[i].data）;
fwrite（&b[i],1,sizeof（char1）,fp1）;
fputc（'\r',fp）;
fputc（'\n',fp）;
}
}
close（fp1）;
return0;
}
三．跳马问题
要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。
1.数据结构设计
国际象棋中马采用“日”字走法，对棋盘上任意一个马所在的结点，它所能走的结点在一步之内有八种情况，即假设马所在的坐标为（i，j），那么它能走的八个坐标分别为（i+1，j+2），（i+1，j-2），（i+2,j-1），（i+2,j+1），（i-2,j-1），（i-2,j+1），（i-1,j-2），（i-1,j+2），把这八个点个看做是（i，j）的领接点，以此类推每个结点都有邻结点，所以可采用图的深度遍历，以马所在的结点（i，j）为初始结点，对全图进行深度遍历，然后按照遍历的顺序输出结点
2.算法设计
#defineMAXNUM8//横纵格数最大值
#defineINVALIDDIR-1//无路可走的情况
#defineMAXLEN64//棋盘总格数
#defineMAXDIR8//下一步可走的方向
typedefstruct
{intx;//表示横坐标
inty;//表示纵坐标
intdirection;//表示移动方向
}HorsePoint;
HorsePointChessPath[MAXLEN];//模拟路径栈
intcount;//入栈结点个数
intChessBoard[MAXNUM][MAXNUM];//标志棋盘数组
intx;//表示横坐
inty;//表示纵坐标
intdirection;//表示移动方向
}HorsePoint;
HorsePointChessPath[MAXLEN];//模拟路径栈
intcount;//入栈结点个数
intChessBoard[MAXNUM][MAXNUM];//标志棋盘数组
3.调试分析
1输入起始点的位置，如果可以遍历全部位置，则输出8*8的矩阵图。
2输入的起始点的位置不可以遍历全部位置时，则输出错误。
4.测试结果
起始点位置:
2，4
图1.遍历全部位置
5.源程序（带注释）
#include
#include
#defineMAXNUM8
#defineINVALIDDIR-1
#defineMAXLEN64
#defineMAXDIR8
typedefstruct
{
intx;inty;intdirection;
}
HorsePoint;
HorsePoint
ChessPath[MAXLEN];
intcount;
intChessBoard[MAXNUM][MAXNUM];
voidInitial（）
{
inti,j;
for（i=0;
ifor（j=0;jChessBoard[i][j]=0;
//下一步可走的方向
for（i=0;i{
ChessPath[i].x=0;
ChessPath[j].y=0;
ChessPath[i].direction=INVALIDDIR;
}
count=0;
}
voidPushStack（HorsePointpositon）
{
ChessBoard[positon.x][positon.y]=1;
//把标志设为1，证明已走过
ChessPath[count]=positon;count++;
}HorsePointPopStack（）
{
HorsePointpositon;
count--;
positon=ChessPath[count];
ChessBoard[positon.x][positon.y]=0;
ChessPath[count].direction=INVALIDDIR;
returnpositon;
}
HorsePointGetInitPoint（）
{
HorsePointpositon;
do{
printf（"\n请输入起始点（x,y）:
"）;
scanf（"%d,%d",&positon.x,&positon.y）;
//输入horse的起始坐标
//出栈函数
//入栈函数
printf（"\n\n"）;
}while（positon.x>=MAXNUM||positon.y>=MAXNUM||positon.x<0||positon.y<0）;
//不超过各个边缘
positon.direction=INVALIDDIR;
returnpositon;
}HorsePointGetNewPoint（HorsePoint*parent）
{
inti;HorsePointnewpoint;
inttryx[MAXDIR]={1,2,2,1,-1,-2,-2,-1};
inttryy[MAXDIR]={-2,-1,1,2,2,1,-1,-2};
newpoint.direction=INVALIDDIR;
parent->direction=parent->direction++;
for（i=parent->direction;i{
newpoint.x=parent->x+tryx[i];
newpoint.y=parent->y+tryy[i];
//试探新结点的可走方向
if（newpoint.x=0&&newpoint.y=0&&ChessBoard[newpoint.x][newpoint.y]==0）
{
parent->direction=i;
//上一结点可走的方向
//标记已走过
ChessBoard[newpoint.x][newpoint.y]=1;
returnnewpoint;
}
}
parent->direction=INVALIDDIR;
returnnewpoint;
}
voidCalcPoint（HorsePointhh）
{
HorsePointnpositon;
HorsePoint*ppositon;
Initial（）;ppositon=&hh;
PushStack（*ppositon）;
while（!
（count==0||count==MAXLEN））
{
ppositon=&ChessPath[count-1];
npositon=GetNewPoint（ppositon）;
if（ppositon->direction!
=INVALIDDIR）
{
ChessPath[count-1].direction=ppositon->direction;PushStack（npositon）;
}
elsePopStack（）;
}
}
voidPrintChess（）
{
inti,j;intstate[MAXNUM][MAXNUM];
intstep=0;
HorsePointpositon;
count=MAXLEN;if（count==MAXLEN）
{
//当棋盘全部走过时
//行走初始化state[i][j]为棋盘上（i,j）点被踏过
//以8*8矩阵的形式输出运行结果
for（i=0;i{step++;positon=ChessPath[i];
state[positon.x][positon.y]=step;
}for（i=0;i{printf（"\t\t"）;
for（j=0;j{if（state[i][j]<10）printf（""）;
printf（"%6d",state[i][j]）;
}printf（"\n"）;
}printf（"\n"）;}
elseprintf（"\t\t此时不能踏遍棋盘上所有点!
\n"）;}
intmain（intargc,char*argv[]）
{
HorsePointh;
h=GetInitPoint（）;
CalcPoint（h）;
PrintChess（）;
return0;
//按顺序输出马踏过}
四．长整数运算问题
长整数运算问题。
设计程序，实现两个任意长的整数的加、减、乘运算问题。
1.数据结构设计
#defineNULL0
#include
#include
#include
typedefstructlongnode{/*每个节点的结构*/
intnum;/*数字*/
structlongnode*low1;/*指向低一位节点*/
structlongnode*high1;/*指向高一位节点*/
}longnode;
typedefstructxlong{/*每个长整数的结构*/
longnode*High;/*每个长整数的最高节点*/
longnode*Low;/*每个长整数的最低节点*/
intdigit4;/*每个长整数的总位数（不包括高位的0）/4*/
}*xlong;
程序调用关系：
2.算法设计
intadd（）/*加*/
{char*a1,*b1;
intdigit4,cf=0;
xlonga,b,c;
do
{printf（"输入长整数的位数：
"）;/*输入要计算的长整数的最多位数*/
scanf（"%d",&digit4）;
}while（digit4<=0）;
a1=（char*）malloc（digit4+1）;
b1=（char*）malloc（digit4+1）;
digit4=digit4/4+1;
init（&a,digit4）;
init（&b,digit4）;
init（&c,digit4）;/*初始化a,b,c*/
do
{cf=0;
printf（"输入要运算的两个长整数,按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开:
\n"）;
scanf（"%s",a1）;printf（"+\n"）;
scanf（"%s",b1）;cf|=ston（a1,a）;
cf|=ston（b1,b）;
}while（cf）;/*输入被加数和加数,如果转换出错,则重输*/
pass（a,b,c）;/*进行相加运算*/
printlong（a）;printf（"+"）;/*打印结果*/
printlong（b）;printf（"="）;
printlong（c）;printf（"\n"）;
printf（"\n"）;
}
intsubtract（）/*减*/
{char*a1,*b1;
intdigit4,cf=0;
xlonga,b,c;
do
{printf（"输入长整数的位数：
"）;/*输入最多位数*/
scanf（"%d",&digit4）;
}while（digit4<=0）;
a1=（char*
升级会员 