哈夫曼码的编译码系统;递归替换问题;跳马问题;长整数运算问题;数据结构课程设计,课程设计

*大学*(*学院数据结构与算法课程设计题 目：哈夫曼码的编/译码系统; 递归替换问题;跳马问题; 长整数运算问题 专业班级： *姓 名： *学 号： *指导教师： % 成 绩：_目 录摘 要 .4一哈夫曼码的编/译码系统 .51.采用类语言定义相关的数据类型 .52.算法设计 .53.函数的调用关系图 .84.调试 分析 .85.测试结果 .96.源程序（带注释） .10二递归替换问题 .121.采用类语言定义相关的数据类型 .122.算法设计 .133.函数的调用关系图 .144.调试分析 .145.测试结果 .156.源程序（带注释） .15三跳马问题 .161.采用类语言定义相关的数据类型 .172.算法设计 .183函数的调用关系图 .184.调试分析 .185.测试结果 .196.源程序（带注释） .19四长整数运算问题 .221.采用类语言定义相关的数据类型 .222.算法设计 .243函数的调用关系图 .264.调试分析 .265.测试结果 .276.源程序（带注释） .28总 结 .37参考文献 .37致 谢 .374摘 要本程序主要解决的是哈夫曼码的编/译码系统，跳马问题，递归替换问题和长整数运算问题。采用哈夫曼算法的设计思想。根据给定的权值构成二叉树森林，在森林中任意选取两棵根结点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。跳马问题是在 64 个国际象棋格子,任意位置放一个马 ,如何不重复地把格子走完。递归替换问题，编写程序，扩展 C/C+源文件中的#include 指令（以递归的方式）。请以文件名的内容替换形如下面的代码行。#include “filename”长整数的四则运算实现两个任意长的整数的加、减、乘运算，由于要实现任意长整数，就需要运用到相应的双向线性链表，以实现整数的任意长的加、减、乘运算。长整数运算实现计算任意长的整数的加、减、乘运算，先输入长整数的最多位数，然后输入要运算的长整数，进行加减运算并显示出这两个数的运算。利用双向循环链表实现长整数的存储，每个结点含一个整形变量。程序使用 Visual C+ 6.0 工具开发关键词：哈夫曼码的编/译码系统，排序、递归算法、数组数据结构、链式数据结构、整数运算。 5一、哈夫曼码的编/译码系统编写一个哈夫曼码的编/译码系统，实现对输入的文本信息自动统计并依此为依据建立一个哈夫曼码的编/译码系统。1、数据结构设计数据结构可用结构体,节点结构体包括字符的名称、字符权值、左右孩子标志、对应字符的前缀码、左孩子指针、右孩子指针、双亲指针。题目要求全程信息用文件保存，应写入文件中，提供文件的输入输出等操作；在过程中需有字符及权值录入、字符前缀码生成、文段编码、文段译码，故应分别建立功能模块；另外还应提供键盘式选择菜单实现程序运行。2、算法设计利用树的思想创建最优二叉树然后得到对应字符的前缀码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(z,n,k);a-flag=3; /修改标志，说明该节点已被选择b=search_min(z,n,k);c-weight=a-weight+b-weight;6a-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# include # include # define MAX 100typedef structint weight; /节点的权值char name; /节点的字符char flag; /标志，左孩子 0，右孩子 1，根 2char 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(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 成为新的根节点）9if(k=1)for(i=0;i=n;i+)if(zi.flag=2)return (10二递归替换问题编写程序，扩展 C/C+源文件中的#include 指令（以递归的方式）。请以文件名的内容替换形如下面的代码行。#include “filename” 1.采用类语言定义相关的数据类型typedef struct /创建结构体，让文件的读写方便char dataMAX; /数据项char1;intprint(char chMAX,int n) /递归函数2.算法设计FILE *fp,*fp1;char sMAX; /s，存储#后面的includechar1 bMAX; /b,文件中内容在内存中的存储位置int i=0,k,d=0,j,flag; /switch 参数，用于确认调用函数的参数if(fp=fopen