1、哈夫曼码编译码系统递归替换问题跳马问题长整数运算问题数据结构课程设计课程设计 *大学*(*学院 数据结构与算法课程设计题 目：哈夫曼码的编/译码系统; 递归替换问题;跳马问题; 长整数运算问题 专业班级： *姓 名： *学 号： *指导教师： % 成 绩：_摘 要本程序主要解决的是哈夫曼码的编/译码系统，跳马问题，递归替换问题和长整数运算问题。采用哈夫曼算法的设计思想。根据给定的权值构成二叉树森林，在森林中任意选取两棵根结点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。跳马问题是在64个国际象棋格子,任意位置放一个
2、马,如何不重复地把格子走完。递归替换问题，编写程序，扩展C/C+源文件中的#include指令（以递归的方式）。请以文件名的内容替换形如下面的代码行。#include “filename”长整数的四则运算实现两个任意长的整数的加、减、乘运算，由于要实现任意长整数，就需要运用到相应的双向线性链表，以实现整数的任意长的加、减、乘运算。长整数运算实现计算任意长的整数的加、减、乘运算，先输入长整数的最多位数，然后输入要运算的长整数，进行加减运算并显示出这两个数的运算。利用双向循环链表实现长整数的存储，每个结点含一个整形变量。程序使用Visual C+ 6.0工具开发 关键词：哈夫曼码的编/译码系统，排
3、序、递归算法、数组数据结构、链式数据结构、整数运算。 一、哈夫曼码的编/译码系统编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。1、数据结构设计 数据结构可用结构体,节点结构体包括字符的名称、字符权值、左右孩子标志、对应字符的前缀码、左孩子指针、右孩子指针、双亲指针。题目要求全程信息用文件保存，应写入文件中，提供文件的输入输出等操作；在过程中需有字符及权值录入、字符前缀码生成、文段编码、文段译码，故应分别建立功能模块；另外还应提供键盘式选择菜单实现程序运行。2、算法设计 利用树的思想创建最优二叉树然后得到对应字符的前缀码Bnode *cr
4、eat_Btree(int k,Bnode zMAX,int n,Bnode *head20) Bnode *a,*b,*c; int i=0,j; a=b=c=(Bnode *)malloc(sizeof(Bnode); k-; /k相当于循环控制变量，这里-1是循环的需要 while(k1) 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-rchi
5、ld=b; a-flag=0; b-flag=1; c-flag=2; n+; /z中元素个数加一 zn=*c; k-; /根节点个数增减一个（a，b变成孩子节点，c成为新的根节点） if(k=1) for(i=0;i=n;i+) if(zi.flag=2) return (&zi); 3、调试分析1 前缀码图3.12 HAFFMAN编码图3.24、执行结果 图3.35、源程序（带注释）# include # include # include # define MAX 100typedef struct int weight; /节点的权值 char name; /节点的字符 char fl
6、ag; /标志，左孩子0，右孩子1，根2 char encodMAX; /编码存储数组 struct Bnode *lchild; /左孩子 struct Bnode *rchild; /右孩子 struct Bnode *parent; /双亲Bnode;Bnode *creat_Btree(int k,Bnode zMAX,int n,Bnode *head20) Bnode *a,*b,*c; int i=0,j; a=b=c=(Bnode *)malloc(sizeof(Bnode); k-; /k相当于循环控制变量，这里-1是循环的需要 while(k1) a=search_min(
7、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中元素个数加一 zn=*c; k-; /根节点个数增减一个（a，b变成孩子节点，c成为新的根节点） if(k=1) for(i=0;i=n;i+) if(zi.flag=2) return (&zi); 二递归替换问题编写程序，扩展C/C+
8、源文件中的#include指令（以递归的方式）。请以文件名的内容替换形如下面的代码行。 #include “filename” 1.采用类语言定义相关的数据类型typedef struct /创建结构体，让文件的读写方便 char dataMAX; /数据项char1;intprint(char chMAX,int n) /递归函数2.算法设计 FILE *fp,*fp1; char sMAX; /s，存储#后面的include char1 bMAX; /b,文件中内容在内存中的存储位置 int i=0,k,d=0,j,flag; /switch参数，用于确认调用函数的参数 if(fp=fop
9、en(ch,rb+)=NULL) printf(文件打开失败！n); exit(0); while(!feof(fp) fread(&bi,1,sizeof(char1),fp); i+; if(bi-1.data0=) /结构体数组计数器 break; k=i-1; /记录b大小，可以认为是对应文件的行数 fclose(fp);2.算法设计 FILE *fp,*fp1; char sMAX; /s，存储#后面的include char1 bMAX; /b,文件中内容在内存中的存储位置 int i=0,k,d=0,j,flag; /switch参数，用于确认调用函数的参数 if(fp=fope
10、n(ch,rb+)=NULL) printf(文件打开失败！n); exit(0); while(!feof(fp) fread(&bi,1,sizeof(char1),fp); i+; if(bi-1.data0=) /结构体数组计数器 break; k=i-1; /记录b大小，可以认为是对应文件的行数 fclose(fp);3.函数的调用关系图 4.调试分析不调用库函数，实现strcpy函数，要返回char*。5.测试结果 图1.调用测试函数6.源程序（带注释）# include # include # include #define MAX 100typedef struct /创建结构
11、体，让文件的读写方便 char dataMAX; /数据项char1;intprint(char chMAX,int n) /递归函数 FILE *fp,*fp1; char sMAX; /s，存储#后面的include char1 bMAX; /b,文件中内容在内存中的存储位置 int i=0,k,d=0,j,flag; /switch参数，用于确认调用函数的参数 if(fp=fopen(ch,rb+)=NULL) printf(文件打开失败！n); exit(0); while(!feof(fp) fread(&bi,1,sizeof(char1),fp); i+; if(bi-1.dat
12、a0=) /结构体数组计数器 break; k=i-1; /记录b大小，可以认为是对应文件的行数 fclose(fp); if(fp1=fopen(辅助.c,ab+)=NULL) printf(文件打开失败！n); exit(0); d=0; /s数组存取计数器 for(i=0;ik;i+) if(bi.data0=#) /发现include，递归调用print for(j=2;j9;j+) sd=bi.dataj; d+; if(strcmp(s,include)=0) flag=bi.data19-0; switch(flag) /带选择的递归调用 case 1:fp=print(file
13、name1.c,1);break; case 2:fp=print(filename2.c,2);break; case 3:fp=print(filename3.c,3);break; default:break; else /否则的话讲代码存入辅助文件 printf(%sn,bi.data); fwrite(&bi,1,sizeof(char1),fp); fputc(r, fp); fputc(n, fp); else /否则的话讲代码存入辅助文件 printf(%sn,bi.data); fwrite(&bi,1,sizeof(char1),fp1); fputc(r, fp); fp
14、utc(n, fp); close(fp1); return 0;三跳马问题要求在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）为初始结点
15、，对全图进行深度遍历，然后按照遍历的顺序输出结点2.算法设计#define MAXNUM 8 /横纵格数最大值 #define INVALIDDIR - 1 /无路可走的情况 #define MAXLEN 64 /棋盘总格数 #define MAXDIR 8 /下一步可走的方向 typedef struct int x; /表示横坐标 int y; /表示纵坐标 int direction; /表示移动方向 HorsePoint; HorsePoint ChessPathMAXLEN; /模拟路径栈 int count; /入栈结点个数 int ChessBoardMAXNUMMAXNUM;
16、/标志棋盘数组 int x; /表示横坐 int y; /表示纵坐标 int direction; /表示移动方向 HorsePoint; HorsePoint ChessPathMAXLEN; /模拟路径栈 int count; /入栈结点个数 int ChessBoardMAXNUMMAXNUM; /标志棋盘数组3.调试分析1输入起始点的位置，如果可以遍历全部位置，则输出8*8的矩阵图。2输入的起始点的位置不可以遍历全部位置时，则输出错误。4.测试结果起始点位置:2，4 图1. 遍历全部位置 5.源程序（带注释）#include #include #define MAXNUM 8 #def
17、ine INVALIDDIR - 1 #define MAXLEN 64 #define MAXDIR 8 typedef struct int x; int y; int direction; HorsePoint; HorsePoint ChessPathMAXLEN; int count; int ChessBoardMAXNUMMAXNUM; void Initial() int i,j; for(i=0;iMAXNUM;i+) for(j=0;jMAXNUM;j+) ChessBoardij=0; /下一步可走的方向 for(i=0;i=MAXNUM|positon.y=MAXNUM
18、|positon.x0|positon.ydirection=parent-direction+; for(i=parent-direction;ix+tryxi; newpoint.y=parent-y+tryyi; /试探新结点的可走方向if(newpoint.x=0&newpoint.y=0&ChessBoardnewpoint.xnewpoint.y=0) parent-direction=i; /上一结点可走的方向 /标记已走过 ChessBoardnewpoint.xnewpoint.y=1; return newpoint; parent-direction=INVALIDDIR
19、; return newpoint; void CalcPoint(HorsePoint hh ) HorsePoint npositon; HorsePoint *ppositon; Initial(); ppositon=&hh; PushStack(*ppositon); while(!(count=0|count=MAXLEN) ppositon=&ChessPathcount-1; npositon=GetNewPoint(ppositon); if(ppositon-direction!=INVALIDDIR) ChessPathcount-1.direction=ppositon
20、-direction; PushStack(npositon); else PopStack(); void PrintChess() int i,j; int stateMAXNUMMAXNUM; int step=0; HorsePoint positon; count=MAXLEN; if(count=MAXLEN) /当棋盘全部走过时 /行走初始化 stateij为棋盘上（i,j）点被踏过 /以8*8矩阵的形式输出运行结果 for(i=0;iMAXLEN;i+) step+; positon=ChessPathi; statepositon.xpositon.y=step; for(i
21、=0;iMAXNUM;i+) printf(tt); for(j=0;jMAXNUM;j+) if(stateij10) printf( ); printf(%6d,stateij); printf(n); printf(n); else printf(tt此时不能踏遍棋盘上所有点!n); int main(int argc,char *argv) HorsePoint h; h=GetInitPoint(); CalcPoint(h); PrintChess(); return 0; /按顺序输出马踏过四长整数运算问题 长整数运算问题。设计程序，实现两个任意长的整数的加、减、乘运算问题。1.
22、数据结构设计#define NULL 0#include#include#includetypedef struct longnode /*每个节点的结构*/ int num; /*数字*/ struct longnode *low1; /*指向低一位节点*/ struct longnode *high1; /*指向高一位节点*/ longnode;typedef struct xlong /*每个长整数的结构*/ longnode *High; /*每个长整数的最高节点*/ longnode *Low; /*每个长整数的最低节点*/ int digit4; /*每个长整数的总位数(不包括高位
23、的0)/4 */*xlong;程序调用关系： 2.算法设计int add()/*加*/ char *a1,*b1; int digit4,cf=0; xlong a,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
24、,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); int subtract()/*减*/ char *a1,*b1; int digit4,cf=0; xlong a,b,c; do printf(输入长整数的位数：);/* 输入最多位数*/ scanf(%d,&digit4); while(digit4=0); a1=(char*
