Huffman编码和解码以及排序

1、一、   课程设计目本课程设计的目的是使学生掌握数据结构的基本概念和算法分析方法，以提高学生的编程能力和解决实际问题的能力。 二、   课程设计内容设计一个程序，该程序具有下面功能：(1)能够选择合适的排序算法，如插入排序、归并排序或快速排序，依据该算法对某一数组进行排序，计算完成该操作所需时间。(2)Huffman编码和解码。程序界面如下：1、主界面-1排序2Huffman编码和解码3退出请选择操作类型(13)：-2、排序界面-1插入排序2归并排序3快速排序4返回5退出请选择操作类型(15)：-是否打印排序前数组(Y/N)：是否打印排序后结果

2、(Y/N)：排序所花时间：(按任意键返回)3、编码解码界面请输入字符串：编码结果为：解码结果为：(按任意键返回)三、   课程设计要求1、课程设计的程序必须用C/C+语言完成。2、关键算法必须画出流程图。3、要求写出软件分析和设计。分析部分包括功能需求和界面需求；设计部分包括算法的详细设计和数据结构（包括内存数据结构和文件结构）。 四、    需求分析和模块设计1、需求分析   程序要完成两大功能：一为内排序，二为Huffman编码与解码。而其中的排序又由三种方法实现，一是插入排序；二是归并排序；三是快速排序。2、

3、模块分解   把程序分成六大模块，分别是主界面，排序界面，插入排序，归并排序，快速排序，Huffman编码与解码。3、详细设计注：这部分对每个函数的功能进行定义，方式如下：函数名称：menu( )编号：001函数功能：实现主界面输入参数：无输出参数：无返回值：无数据流程图-函数名称：sort( )编号：002函数功能：实现排序面输入参数：无输出参数：无返回值：无数据流程图-函数名称：inssort( )编号：003   函数功能：实现插入排序输入参数：要排序数组地址，数组长度输出参数：无返回值：无数据流程图 - 函数名称：msort(

4、 )编号：004    函数功能：实现归并排序输入参数：要排序数组地址，临时数组地址，数组最左边位置，数组最右边位置，输出参数：无返回值：无数据流程图  -函数名称：quicksort( )编号：005      函数功能：实现快速排序输入参数：要排序数组地址，数组最左边位置，数组最右边位置，输出参数：无返回值：无  函数名称：huff( )编号：006函数功能：实现Huffman编码与解码输入参数：建树的字符个数，字符和它的权值输出参数：无返回值：无4、数据结构  插入排序：L

5、60;  i=1   2   3  4   5   6   742 20 17 13 13 13 13 1320 42 20 17 17 14 14 1417 17 42 20 20 17 17 1513 13 13 42 28 20 20 1728 28 28 28 42 28 23 2014 14 14 14 14 42 28 2323 23 23 23 23 23 42 2815 15 15 15 15 15 15 42   快速排序：72 

6、;6 57 88 60 42 83 73 48 85            Pivot=60 48 6 57 426088 83 73 72 85Pivot=6              Pivot=

7、73 642 57 48 727385 88 83Pivot=57             Pivot=88 42 48   57 85 8388Pivot=42              Pivot=85 4248 8385&#

8、160; 6 42 48 57 60 72 73 83 85 88        最终排好序的数组    归并排序：    36 20 17 13 28 14 23 1520 3613 1714 2815 2313 17 20 3

9、614 15 23 2813 14 15 17 20 23 28 36五、计中碰到的问题及解决方法程序的要求是要进行一个操作后要返回原界面或主界面，我用的是switch的结构，和老师给的有所不同，所以在处理这个问题时出了一点问题，但后来一想，也很简单，再调用一次原来的界面函数不就行了吗？ 六、收获和体会通过这次课程实践，我加深了对数据结构这门课程的理解，更好的掌握了各种排序方法和Huffman编码与解码！更巩固了自己的C和C+的知识。 七、程序清单主界面：DS,cpp #in

10、clude "stdafx.h"#include <iostream.h>#include <iomanip.h>void sort();/声明要调用的函数void huff();void menu()       int num;       cout <<endl;       cout <<setw(40) <<"主界面:

11、 " <<endl;       cout <<setw(45) <<"1.排序              " <<endl;       cout <<setw(45) <<"2.Huffman编码与解码 " <<

12、endl;       cout <<setw(45) <<"3.退出              " <<endl;       cout <<setw(45) <<"请选择操作类型(1-3):" cin >>num;cout <&

13、lt;endl;             switch(num)/ 通过swich语句进行选择              case 1: sort();break;    case 2: huff();break;    case 3: break;    default: co

14、ut <<"error"       void main()       menu(); 排序界面： #include "stdafx.h"#include <iostream.h>#include <iomanip.h>void inssort();/ /首先要声明各个要调用的函数/void menu();void msort();void qsort();void sort()

15、 / 类似于主界面，也通过switch语句进行选择/       int num1;       cout <<endl;       cout <<setw(40) <<"排序界面:           " <<endl;  &#

16、160;    cout <<setw(45) <<"1.插入排序          " <<endl;       cout <<setw(45) <<"2.归并排序          " <<endl; 

17、      cout <<setw(45) <<"3.快速排序          " <<endl;       cout <<setw(45) <<"4.返回            

18、60; " <<endl;       cout <<setw(45) <<"5.退出              " <<endl;       cout <<setw(45) <<"请选择操作类型(1-5):"cin >

19、>num1;cout <<endl;       switch(num1)              case 1: inssort();break;    case 2: msort();break;    case 3: qsort();break;       case 4:

20、 menu();break;       case 5: break;    default: cout <<"error"        插入排序： #include "stdafx.h"#include <iostream.h>#include "stdio.h"int time1=0;int comp(int a,int b);/比较vo

21、id swap(int a,int x,int y); /交换void sort();/排序界面void inssort1(int A,int n)/进行插入排序       for(int i=0;i<n;i+)              for(int j=i;(j>0)&&(comp(Aj,Aj-1);j-)     

22、60;               swap(A,j,j-1);int comp(int a,int b)       int result;    if(a>b)              result=1;  

23、     else              result=0;       return result;       time1+;void swap(int a,int x,int y)       int temp;  &#

24、160;    temp=ax;       ax=ay;       ay=temp;       time1+;void inssort()       int n;       int A80,B80;    cout <<

25、;"请输入你要输入的元素个数：" <<endl;       cin >>n;       cout <<"请输入要排序的元素:" <<endl;       for(int i=0;i<n;i+)           

26、60;         cin >>Ai;              for(int j=0;j<n;j+)                     Bj=Aj;  

27、60;           cout <<"进行排序后的结果:" <<endl;       inssort1(A,n);/进行插入排序       for(int k=0;k<n;k+)             

28、60;       cout <<Ak <<" "              cout <<endl;       cout <<"时间复杂度为： "       cout <<time1 <&

29、lt;endl;       char answer;       cout <<"是否要打印排序前的数组?(y/n)" <<endl;       cin >>answer;       if(answer='y')      

30、;               for(int ii=0;ii<n;ii+)                     cout <<Bii <<" "      

31、;        cout <<endl;       getchar();       sort(); 归并排序： #include "stdafx.h"#include <iostream.h>#include "stdio.h"void inssort1(int A,int n);int time2=0;/时间复杂度extern

32、 int time1;void sort();void mergesort(int A,int temp,int left,int right)     if(right-left)<=32)                     inssort1(&Aleft,right-left+1);/对于较小的数组，调用内排序   

33、;           return;              int i,j,k,mid=(left+right)/2;       if(left=right) return;       mergesort(A,temp,left,mid); 

34、;      mergesort(A,temp,mid+1,right);       for(i=mid;i>=left;i-)                     tempi=Ai;        

35、0;     time2+;              for(j=1;j<right-mid;j+)                     tempright-j+1=Aj+mid;     

36、;         time2+;              for(i=left,j=right,k=left;k<=right;k+)                     if(tempi<

37、=tempj)                                   Ak=tempi+;              

38、;       time2+;                            else                &#

39、160;                  Ak=tempj-;                     time2+;         &

40、#160;                   void msort()       int n,left,right;       int time;       int A80;       in

41、t B80;       int temp80;    cout <<"请输入元素个数：" <<endl;           cin >>n;       left=0;       right=n-1;  &#

42、160;    cout <<"请输入数组元素:" <<endl;       for(int i=0;i<n;i+)                     cin >>Ai;      

43、60;      for(int j=0;j<n;j+)                     Bj=Aj;              mergesort(A,temp,left,right);/进行归并排序  

44、     cout <<"进行排序后的结果:" <<endl;       for(int k=0;k<n;k+)                     cout <<Ak <<" "  

45、60;           cout <<endl;       time=time1+time2;       cout <<"时间复杂度为： "       cout <<time <<endl;     &

46、#160; char answer;       cout <<"是否要打印排序前的数组?(y/n)" <<endl;       cin >>answer;       if(answer='y')             &

47、#160;       for(int ii=0;ii<n;ii+)                     cout <<Bii <<" "             

48、cout <<endl;       getchar();       sort(); 快速排序： #include "stdafx.h"#include <iostream.h>#include <stdio.h>#include <stdlib.h>void sort();int time3=0;int pation(int A,int x,int y);void quicksort(

49、int A, int x, int y)    if(x>=y) return;    int q=pation(A, x, y);    quicksort(A, x, q-1);    quicksort(A, q+1, y); int pation(int A, int x, int y)    int n=Ax, i=x+1, j=y, temp;    while(1)  

50、;          while(Ai<n)                                   +i;     &#

51、160;               time3+;                            while(Aj>n)     &#

52、160;                             -j;                     time3+;&

53、#160;                           if(i>=j) break;        temp=Ai; Ai=Aj; Aj=temp;         

54、0;    time3+;        Ax=Aj;    Aj=n;    return j; void qsort( )    int i, A80,n,B80;       char answer;       cout <<"请输入元素个数:"&#

55、160;      cin >>n;       cout <<"请输入要排序的元素:" <<endl;    for(i=0; i<n; +i)        cin >>Ai;       for(int j=0;j<n;j+) 

56、60;            Bj=Aj;    quicksort(A, 0, n-1);       cout <<"排序后的结果为:" <<endl;    for(i=0; i<n; +i)        cout <<Ai &l

57、t;<" "    cout <<endl;    cout <<"时间复杂度为:" <<time3 <<endl;       cout <<"是否打印排序前的数组?(y/n)"       cin >>answer;     &

58、#160; if(answer='y')                     for(int k=0;k<n;k+)                       &

59、#160;           cout <<Bk <<" "                         cout <<endl;       getchar

60、();       sort();       Huffman编码：#include "stdafx.h"#include <iostream.h>#include "stdio.h"#include "string.h"#define MAX 99char chaMAX;char hcMAX-1MAX;int s1,s2; /设置全局变量，以便在方法(函数)select中返回两个变量void menu(

61、);typedef struct /huffman树存储结构 unsigned int wei; int lch,rch,parent;hufftree;  void select(hufftree tree,int k) /找寻parent为0,权最小的两个节点 int i; for (i=1;i<=k && treei.parent!=0 ;i+); s1=i; for (i=1;i<=k;i+)    if (treei.parent=0 &&

62、treei.wei<trees1.wei) s1=i; for (i=1; i<=k ; i+)    if (treei.parent=0 && i!=s1) break; s2=i; for (i=1;i<=k;i+)    if ( treei.parent=0 && i!=s1 && treei.wei<trees2.wei) s2=i; void huffman(hufftree tree,int *w,int n) /生成

63、huffman树 int m,i;   if (n<=1) return;   m=2*n-1; for (i=1;i<=n;i+)           treei.wei=wi;        treei.parent=0;      treei.lch=0;     

64、60;  treei.rch=0;  for (i=n+1;i<=m;i+)           treei.wei=0;        treei.parent=0;      treei.lch=0;        treei.rch=0;    f

65、or (i=n+1;i<=m;i+)             select(tree, i-1);       trees1.parent=i;       trees2.parent=i;       treei.lch=s1;      

66、treei.rch=s2;           treei.wei=trees1. wei+ trees2.wei;      void huffmancode(hufftree tree,char code,int n) int start,c,i,f; coden-1='0' cout <<"Huffman编码:" <<endl; for(i=1;i&l

67、t;=n;i+)         start=n-1;       for(c=i,f=treei.parent;f!=0;c=f,f=treef.parent)                        if(treef.lch=c) 

68、;                            code-start='0'                   else        &