数据结构与算法课程设计报告

1、这一页是封面.请自行设计目录1 课程设计一:约瑟夫环 1 1.1问题描述 1 1.2 基本要求 1 1.3 算法思想 1 1.4 模块划分 1 1.5 数据结构 4 1.6 源程序 4 1.7 测试数据 11 1.8 测试情况 11 2 课程设计二:哈弗曼编/译码系统 14 2.1问题描述 14 2.2 基本要求 14 2.3 算法思想 15 2.4 模块划分 15 2.5 数据结构 18 2.6 源程序 20 2.7 测试数据 40 2.8 测试情况 413 课程设计三:推销员问题求解 48 3.1问题描述 48 3.2 基本要求 48 3.3 算法思想 48 3.4 模块划分 48 3.5

2、 数据结构 50 3.6 源程序 50 3.7 测试数据 60 3.8 测试情况 61 1 课程设计一:约瑟夫环1.1 问题描述约瑟夫（Joeph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）.一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.试设计一个程序求出出列顺序.1.2 基本要求程序要求用户输入编号最大值n,要求输入初始的报数上限m,然后要求输入每个人持有的密码,然后根据以上

3、数据构建一个单向循环链表存储结构模拟所有人的出列顺序,并按照出列的顺序印出各人的编号.如果用户输入的n,m,以及密码因子是非法输入(即输入非正整数),程序能够识别,并提示用户,然后程序终止.1.3 算法思想首先根据用户的输入构建好整个循环链表,用一个first指针指向最先进入链表的元素(即编号为1的元素),还要用一个size变量记录当前循环链表中有多少个元素.根据m和size,计算m%size的值(即m和size取余),这个值确定first指针从自身开始顺时针移动多少个节点,到达待出列的节点(该节点即将被删除).将first移动到上面计算出的节点,取出该节点的密码值,更新m.更新size,使s

4、ize减少1.输出该节点的编号,然后从链表中删除该节点(删除后,first的应该指向被删除节点的下一个位置).重复上述-步,直到所有链表为空(即size=0).则完成了工作1.4 模块划分总体预览:下面是struct node中的变量解释:int bianhao;这是一个整型变量,记录节点的编号值.int mima;这是一个整形变量,记录节点的密码值.node *next_node;这是一个node*类型的指针变量,该指针指向下一个节点.下面是class jeoph中的函数和变量和解释:int size;jepho类的私有变量,记录当前链表中已经存在多少个元素.node *first; jep

5、ho类的私有指针变量,指向首先进入链表的元素,即编号为1的元素.node *end; jepho类的私有指针变量,指向最后一个进入链表的元素,即编号为n的元素.node *current; jepho类的的私有指针变量,这个指针用途较多,在不同成员函数中用途不一样,将在1.6源程序中具体解释起用途.jeoph( int n_size); jepho类的默认构造函数,接收大小参数,初始化链表,使链表包含n_size个元素,并且有正确的编号,每个节点的默认密码=编号.void modify_mima( int mima);当jeoph类的对象初始化后,可以调用这个函数修改current指向的节点的

6、密码值.传入参数是希望修改的密码值.在构造函数调用后,current的值等于first,每调用一次该函数,current自动指向下一个节点,所以只需要连续调用这个函数,就可以更改每个节点.void bianli( int m);这个函数遍历已经建立好的循环链表,m是初始的报数上限值.调用该函数后,就可以将链表中的所有元素按照约瑟夫环的规则出列,已出列的元素会从链表中删除.node* gofront( int x, node *&ptr);这个函数将ptr按顺时针顺序前移x个节点,并返回移动结束后的节点指针.注意是按引用调用,本函数本身会更改传入的ptr.jeoph();这个是析构函数.下面是m

7、ain()函数解释:main函数主要是创建jeoph类的对象,并调用相关成员函数,实现约瑟夫环的功能.main函数主要功能是与用户的交互,提示用户输入最大编号n,输入初始报数上限m,以及输入每个节点的密码.在main函数中,还有对每个输入是否合法的判断,若不合法,程序直接提示,并终止.1.5 数据结构程序使用的基本抽象类型仅有int;所定义的问题的数据类型为jeoph(一个解决此问题的循环链表类,后面会给出其定义);新定义了一个结构node,此结构是jeoph类的私有数据成员,它是循环链表的每一个节点的数据结构,下面是定义(具体解释参见1.4 模块划分):struct nodeint bian

8、hao;int mima; node *next_node;新定义了一个抽象数据类jeoph,此类是一个循环链表类,调用他的函数能初始化循环链表,能解决约瑟夫环的出列问题.下面是定义(具体解释参见1.4 模块划分):class jeophpublic:jeoph( int n_size);void modify_mima( int mima);void bianli( int m);node* gofront( int x, node *&ptr);jeoph();private:int size;node *first;node *end;node *current;1.6 源程序joeph

9、.h文件代码如下:#ifndef joeph_h_#define joeph_h_/这是约瑟夫环中循环链表的节点结构struct nodeint bianhao;/表示当前节点的编号int mima;/表示当前节点持有的密码node *next_node;/到下一个节点的指针;class jeophpublic:/默构,接收大小参数,初始化链表,使链表包含size个元素,/并且有正确的编号,默认密码=编号jeoph( int n_size);/初始化后,通过这个函数修改每个节点的密码void modify_mima( int mima);/给定最初的报数上限m,然后遍历链表void bianl

10、i( int m);/这个函数操纵ptr指针,使其在环中顺时针移动x个节点node* gofront( int x, node *&ptr);/析构函数jeoph();private:/表示当前链表中的元素个数int size;/这个first指向首先进入链表的元素,也就是编号为1的元素node *first;/这个end指向最后一个进入链表的元素.node *end;/这个指针有多个用途,在不同函数中用途不一样,在具体函数中解释node *current;#endif / joeph_h_jeoph.cpp文件代码如下:#include joeph.h#include using names

11、pace std;jeoph:jeoph( int n_size) : current(0), first(0) ,size(0), end(0)if ( n_size =0)return ;/个数bianhao = 1; /因为已经有了第一个节点,所以i从2开始for ( int i = 2; i next_node = new node;current = current-next_node;current-bianhao = i;current-mima = i;size+;/下面设置尾部指针指向first,以形成环current-next_node = first;/end记录最后一个

12、进入链表的节点end = current;/把current重新置为first;current = first;void jeoph:modify_mima( int mima)current-mima = mima;/将current移到下一个还没有密码的节点current = current-next_node;/将传入的ptr按顺时针顺序前移x个节点,并返回移动终止/处的节点指针node* jeoph:gofront( int x, node *&ptr)for ( int i = 1; i next_node;return ptr;void jeoph:bianli( int m)/首

13、先判断链表是否为空if ( size = 0)cout=1)/current定位于待删除节点的前一个节点gofront( m % size - 1 ,current);first = current-next_node;/定位first为待删除节点coutbianhao)mima;/更新mcurrent-next_node = first-next_node;/更新链表delete first;/删除节点.jeoph:jeoph()/必须有这个判断,因为bianli()函数也可以执行析构过程/如果在真正析构调用前调用了bianli(),则此析构不准执行,/因为析构不存在的对象会出错.while

14、 ( size =1)current = first;/定位first为待删除节点first = first-next_node;size-;/更新大小delete current;/删除节点.main.cpp文件代码如下:#include joeph.h#include using namespace std;int main()int n(1),m(1);coutn;/下面判断输入的n是否合法,(temp!=n&temp!= )是用来检测输/入数据格式为 正整数x(例如5s),x为任意字符,因为int截断,流只读入/前面的正整数部分,所以流并不错误,所以cin.fail()为0,因此必须另

15、/外判断下一个字符是否为换行符或空格char temp =cin.get();if ( (temp!=n&temp!= ) | cin.fail() | n 0)cout输入数据非正整数,程序异常退出nn;system(pause);exit(1);coutm;/下面判断输入的m是否合法temp =cin.get();if ( (temp!=n&temp!= ) | cin.fail() | m 0)cout输入数据非正整数,程序异常退出nn;system(pause);exit(1);jeoph my(n);/创建约瑟夫环cout请依次输入编号1-n对应的密码:;for ( int i=1;

16、 iq;/下面判断输入的密码是否合法temp =cin.get();if ( (temp!=n&temp!= ) | cin.fail() | q 0)cout输入数据非正整数,程序异常退出nn;system(pause);exit(1);/更新current节点的密码my.modify_mima(q);cout出列顺序为:;my.bianli(m);/遍历约瑟夫环coutendlendl; system(pause); return 0;1.7 测试数据共有如下8组测试数据,前5组输入都是正确合法的,后三组测试输入非法情况.测试结果见1.8n=7;m=20;密码序列=3,1,7,2,4,8,

17、4n=30;m=15;密码序列=1,2,3,27,28,29,30n=0;m=20;n=1;m=20;密码序列=7n=2;m=10;密码序列=8,10n=非正整数;n=5;m=非正整数n=5;m=7;密码序列任意,但其中至少一个密码非正整数1.8 测试情况n=7;m=20;密码序列=3,1,7,2,4,8,4n=30;m=15;密码序列=1,2,3,27,28,29,30n=0;m=20;n=1;m=20;密码序列=7n=2;m=10;密码序列=8,10n=非正整数;n=5;m=非正整数n=5;m=7;密码序列任意,但其中至少一个密码非正整数2 课程设计二:哈夫曼编/译码系统2.1 问题描述利

18、用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本.但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原).试为这样的信息传输写一个哈夫曼编/译码系统.2.2 基本要求该系统应具有以下功能:(1)I:初始化(Initialization).读入文件ToBeTran.txt,统计该文件中每个字符的权值,并据此建立哈夫曼树,并将它存于文件huffmantree.txt中.(2)E:编码(Encoding).利用已建好的哈夫曼树(如不在内存,则从文件huffmantree.txt中读入),对文件ToBeTran.txt中的正文进行编码

19、,然后将结果存入文件codefile.txt中.(3)D:译码(Decoding).利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码,结果存入文件Textfile.txt中.(4)P:打印代码文件(Print).将文件codefile.txt以紧凑格式显示在终端上,每行50个代码.同时将此字符形式的编码文件写入文件codeprin.txt中.(5)T:打印哈夫曼树(Tree printing).将已在中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint.txt中.(6)用户界面可以设计为”菜单”方式:显示上述功能符号再加

20、上”Q”,表示退出运行Quit.请用户键入一个选择功能符.此功能执行完毕后再显示此菜单,直至某次用户选择了”Q”为止.(7)在程序的一次执行过程中,第一次执行I,D或C命令之后,哈夫曼树已经在内存了,不必再读入.每次执行中不一定执行I命令,因为文件hfmTree可能早已建好.2.3 算法思想哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树即带权路径长度最小的二叉树来编码数据,经常应用于数据压缩.是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码.这种方法是由David.A.Huffman发展起来的.例如,在英文中,e的出现概率很高,而z的出现概率则最低.当利

21、用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去25位.用普通的表示方法时,每个英文字母均占用一个字节（byte）,即8个位.二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多.倘若我们能实现对于英文中,各个字母出现概率的较准确的估算,然后建立哈夫曼树,将每个数据放在叶子节点,则可以得到每个字符的编码.2.4 模块划分总体预览:下面是struct huffman_node中的变量解释:char data;数据域,用来存储当前节点的具体数据.int weight;这个对应数据的权值int paraent;指针域,保存当前节点父节点下标int l_chi

22、ld;指针域,保存当前节点左儿子下标int r_child;指针域,保存当前节点右儿子下标下面是struct bianma中的变量解释:char data;哈夫曼树的叶子节点的数据值string code;该叶子节点数据的编码,用string来存储下面是class huffman中的函数和变量和解释:vector tree;huffman类的私有数据成员,用来存储具体的哈夫曼树.vector v_code;huffmam类的私有数据成员,用来存储每个叶子节点的二进制编码.int size_of_leaf; huffman类的私有数据成员,用来记录,当前的哈夫曼树有多少个叶子节点.bool in

23、itialization_finished;huffmam类的公有数据成员,用来标识对象所处状态,该状态为真,说明哈夫曼树初始化完成.bool huffman_tree_finished;huffmam类的公有数据成员,该状态为真说明,完整哈夫曼树建造完成.bool bianma_finished;huffmam类的公有数据成员,该状态为真说明,对每个叶子节点的二进制代码编写完成.bool encoding_finished;huffmam类的公有数据成员,该状态为真说明对整个文件的编码完成.void helper_tree_print( int parant, int sp, ostream

24、& fout);huffmam类私有函数,是打印哈夫曼树的辅助函数,parant是父节点指针,sp是缩进的空格数bool fined_action( char x);huffmam类私有函数,在initialization函数中调用的辅助函数.bool initialization( const string &file_name);huffmam类的公有函数,从file_name读入数据,并建造初始化的哈夫曼树(统计每个字符的权值),初始化成功返回1,否则0,若成功则设置initialization_finished为真bool build_up_huffman_tree();huffmam

25、类的公有函数,根据初始哈夫曼树(只有在初始化成功的条件下,改函数才会成功执行)建造完整的哈夫曼树,成功返回1,否则0, 若成功则设置huffman_tree_finished为真.bool bulid_up_bianma();huffmam类的公有函数,用于对哈夫曼树的每个叶子节点(只有在huffman_tree_finished为真的条件下才成功执行),计算出正确的二进制代码,成功返回1,否则0,若成功设置bianma_finished为真.void store_huffman_tree();huffmam类的公有函数,存完整的哈夫曼树,存在huffmantree.txt中.bool rea

26、d_huffman_tree();huffmam类的公有函数,读完整的哈夫曼树,从huffmantree.txt中读,成功返回1,否则0.bool encoding( const string &file_name);huffmam类的公有函数,编码(只有在bianma_finished为真的状态下才能成功执行),把file_name文件编码成二进制代码,存储在codefile.txt中.成功返回1,否则0,若成功设置encoding_finished为真.bool decoding();huffmam类的公有函数,译码,读取codefile.txt并译码,译码后的文件存在Textfile.t

27、xt中.成功返回1,否则0.bool codeprint();huffmam类的公有函数,打印codefile.txt,并把每个字符的二进制代码存入codeprin.txt中.bool tree_print();huffmam类的公有函数,打印哈夫曼树.下面是main()函数解释:main函数的主要是创建huffman类的对象,并调用相关成员函数,实现哈夫曼编译码系统的功能.main函数的主要功能是与用户的交互,提示用户输入相关命令,执行接受命令后,尝试执行命令,若命令执行成功,则明确告知用户成功.若命令执行失败,则提示执行失败,并给出相关失败建议.程序不停的和用户交互,直到用户关闭程序或者键

28、入q(Q).2.5 数据结构程序使用的基本抽象类型有int,sting,char,ifstream,ofstream,bool,vector,stack; 所定义的问题的数据类型为huffman(一个解决哈夫曼编译码系统的类,后面会给出其定义); 新定义了一个结构huffman_node,此结构是huffman类的私有向量的实例化类型,表示哈夫曼树的每一个节点数据结构, 下面是定义(具体解释参见2.4 模块划分):struct huffman_node char data; int weight; int paraent; int l_child; int r_child; huffman_n

29、ode( char c, int w, int p, int l, int r) :data(c), weight(w), paraent(p), l_child(l), r_child(r)huffman_node(char c) : data(c),weight(1)paraent = l_child = r_child = -1;新定义了一个结构bianma,此结构是huffman类的私有向量的实例化类型,表示哈夫曼树中每个叶子节点的具体二进制编码, 下面是定义(具体解释参见2.4 模块划分):struct bianma bianma( char c, string s) : data(

30、c), code(s)char data;string code;新定义了一个抽象数据类huffman,此类是一个哈夫曼树,调用此类的各个函数,能解决哈夫曼编译码问题.下面是定义(具体解释参见2.4 模块划分):class huffmanpublic:huffman();bool initialization( const string &file_name);bool build_up_huffman_tree();bool bulid_up_bianma();void store_huffman_tree();bool read_huffman_tree();bool encoding(

31、const string &file_name);bool decoding();bool codeprint();bool tree_print();private:vector tree; vector v_code;int size_of_leaf; void helper_tree_print( int parant, int sp, ostream& fout);bool fined_action( char x); public:bool initialization_finished;bool huffman_tree_finished; bool bianma_finished

32、; bool encoding_finished; ;2.6 源程序huffman.h文件代码如下:#ifndef huffman_h_#define huffman_h_#include using namespace std;struct huffman_node/这个结构是哈夫曼树的节点/数据域,用来存储具体数据char data;/这个数据的权值int weight;/指针域,保存父节点下标int paraent;/指针域,保存左儿子下标int l_child;/指针域,保存右儿子下标int r_child;huffman_node( char c, int w, int p, int

33、 l, int r) :data(c), weight(w), paraent(p), l_child(l), r_child(r)/这个是构造函数,初始哈夫曼树时使用huffman_node(char c) : data(c),weight(1)paraent = l_child = r_child = -1;/这个结构 存储哈夫曼树中 具体每一个叶子节点的二进制代码struct bianma/将具体字符编码成二进制代码时,会使用其中的数据bianma( char c, string s) : data(c), code(s)char data;string code;class huffm

34、anpublic:/默构,完成空哈夫曼树的初始工作huffman();/读入数据,并建造初始化的哈夫曼树,若成功返回1,否则0bool initialization( const string &file_name);/根据初始哈夫曼树建造完整的哈夫曼树,成功返回1,否则0bool build_up_huffman_tree();/用于对哈夫曼树的每个叶子节点,计算出正确的二进制代码,成功返回1,否则0bool bulid_up_bianma();/存完整的哈夫曼树,存在huffmantree.txt中void store_huffman_tree();/读完整的哈夫曼树,从huffmantr

35、ee.txt中读,成功返回1,否则0bool read_huffman_tree();/编码,把file_name文件编码成二进制代码,存储在codefile.txt中bool encoding( const string &file_name);/译码,读取codefile.txt并译码,译码后的文件存在Textfile.txt中bool decoding();/打印codefile并把每个字符的二进制代码存入codeprin.txt中bool codeprint();/打印哈夫曼树bool tree_print();private:/用向量表示哈夫曼树vector tree;/这个向量存储

36、的是每个叶子节点的具体二进制代码vector v_code;/这个变量用来记录建立的哈夫曼树中有多少个树叶int size_of_leaf;/打印哈夫曼树的辅助函数,parant是父节点指针,sp是缩进的空格数void helper_tree_print( int parant, int sp, ostream& fout);/在initialization函数中调用的辅助函数bool fined_action( char x);public:/这个变量用来标识 初始化哈夫曼树是否完成bool initialization_finished;/这个变量用来标识 整个哈夫曼树建立完成bool h

37、uffman_tree_finished;/标识 对每个叶子节点的二进制代码编写完成bool bianma_finished;/标识对整个文件的编码完成bool encoding_finished;#endif / huffman_h_huffman.cpp文件代码如下:#include huffman.h#include #include #include #include using namespace std;huffman:huffman():size_of_leaf(0),initialization_finished(0),huffman_tree_finished(0),bian

38、ma_finished(0),encoding_finished(0)/这个是默构,初始所有变量为空/从file_name读入数据,并初始化哈夫曼树,成功返回1,/否则返回0bool huffman:initialization( const string &file_name)ifstream fin;fin.open(file_name);if ( fin.fail()return 0;/失败返回0/按每一个字符读取输入文件char temp;/这里提前读取,是为了在终止while循环时,不实际存储最后的eoftemp = fin.get();while ( !fin.eof()/这个函数

39、处理每一个读取的字符,并统计每个字符的权重fined_action( temp);temp = fin.get();/初始化哈夫曼树完成,标记为真initialization_finished = 1;return 1;/成功返回1/建造完整哈夫曼树,成功返回1,否则0bool huffman:build_up_huffman_tree()if ( !initialization_finished)return 0;/失败返回0/这是一个死循环,终止在循环内部/只有在哈夫曼树初始化完成后,才会进行完全哈夫曼树的建立while (initialization_finished)/region f

40、or所标记的区域的作用是,从现有哈夫曼树,找出权重最小,/和次最小的两个叶子(或子树)的下标,用于后面的合并 叶子(子树);/已被合并的叶子(子树),在下次搜寻中,直接略过.看该节点是否 /被合并过,通过查看起父指针就知道,父指针为-1的表示未合并过的.#pragma region forint min_index = -1;int ci_min_index = -1;for ( int i = 0; i treeci_min_index.weight)min_index = ci_min_index;ci_min_index = i;continue;elsemin_index = i;co

41、ntinue;if ( treei.weight treeci_min_index.weight)else if ( treei.weight treemin_index.weight)ci_min_index = min_index;min_index = i;elseci_min_index = i;/for ( int i = 0; i tree.size(); +i)#pragma endregion for/当整棵树构建完毕后,树有一个根节点,只有它的父指针为-1,/那么必然会出现其中一个索引值为-1的情况,出现这种情况/即说明,树构建完毕.终止循环.if ( min_index =

42、 -1 | ci_min_index = -1)break;/下面是正确找到最小节点索引和次最小节点索引,合并,将/产生的新子树加入到哈夫曼树中新子树的权重为两子树/权重之和,并设置新子树的左右儿子tree.push_back( huffman_node(T,treemin_index.weight + treeci_min_index.weight, -1, min_index, ci_min_index) );/设置被合并的子树的父指针treemin_index.paraent = tree.size() - 1;treeci_min_index.paraent = tree.size()

43、 -1;/while(initialization_finished);huffman_tree_finished = 1;/哈夫曼树建造完成,标记为真return 1;/成功返回1/void huffman:build_up_huffman_tree()/根据哈夫曼树对每个字符编码,成功返回1,否则0bool huffman:bulid_up_bianma()if ( !huffman_tree_finished)return 0;/失败返回0/下面从叶子按逆序到根节点,以找出叶子节点的编码for ( int i = 0; i size_of_leaf; +i)stack s;int tem

44、p1 = i;int temp2 = 0;while ( treetemp1.paraent != -1)temp2 = temp1;temp1 = treetemp1.paraent;if ( treetemp1.l_child = temp2)s.push( 0);elses.push( 1);/whilestring add;while ( !s.empty()add += s.top();s.pop();v_code.push_back( bianma( treei.data, add);/forbianma_finished = 1;/设置状态return 1;/成功返回1/把当前哈

45、夫曼树存储在huffmantree.txt中void huffman:store_huffman_tree()ofstream fout(huffmantree.txt);for ( int i=0; itree.size(); +i)fouttreei.data treei.weight treei.paraent treei.l_child treei.r_childwplr;fin.get();tree.push_back( huffman_node( c,w, p, l, r);if( l=-1)size_of_leaf+;/更新叶子节点数huffman_tree_finished = 1;/更新状态return 1;/对file_name进行编码,结果存在codefile.txt,成功返回1,否则返回0bool huffman:encoding( const