二,、   課程設(shè)計(jì)內(nèi)容
設(shè)計(jì)一個(gè)程序，該程序具有下面功能：
(1)能夠選擇合適的排序算法,，如插入排序,、歸并排序或快速排序，依據(jù)該算法對(duì)某一數(shù)組進(jìn)行排序,，計(jì)算完成該操作所需時(shí)間,。
(2)Huffman編碼和解碼。
程序界面如下：
1,、主界面
------------------------------------------------------------------------
1．排序
2．Huffman編碼和解碼
3．退出
請(qǐng)選擇操作類(lèi)型(1—3)：
------------------------------------------------------------------------
2,、排序界面
------------------------------------------------------------------------
1．插入排序
2．歸并排序
3．快速排序
4．返回
5．退出
請(qǐng)選擇操作類(lèi)型(1—5)：
------------------------------------------------------------------------
是否打印排序前數(shù)組(Y/N)：
是否打印排序后結(jié)果(Y/N)：
排序所花時(shí)間：(按任意鍵返回)
3、編碼解碼界面
請(qǐng)輸入字符串：
編碼結(jié)果為：
解碼結(jié)果為：(按任意鍵返回)
三,、   課程設(shè)計(jì)要求
1,、課程設(shè)計(jì)的程序必須用C/C++語(yǔ)言完成。
2,、關(guān)鍵算法必須畫(huà)出流程圖,。
3、要求寫(xiě)出軟件分析和設(shè)計(jì),。分析部分包括功能需求和界面需求,；設(shè)計(jì)部分包括算法的詳細(xì)設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)（包括內(nèi)存數(shù)據(jù)結(jié)構(gòu)和文件結(jié)構(gòu)）。
 
四,、    需求分析和模塊設(shè)計(jì)
1,、需求分析
   程序要完成兩大功能：一為內(nèi)排序，二為Huffman編碼與解碼,。而其中的排序又由三種方法實(shí)現(xiàn),，一是插入排序；二是歸并排序,；三是快速排序,。
2、模塊分解
   把程序分成六大模塊,，分別是主界面,，排序界面，插入排序,，歸并排序,，快速排序，Huffman編碼與解碼,。
3,、詳細(xì)設(shè)計(jì)
注：這部分對(duì)每個(gè)函數(shù)的功能進(jìn)行定義，方式如下：
函數(shù)名稱(chēng)：menu( )　　編號(hào)：001
函數(shù)功能：實(shí)現(xiàn)主界面
輸入?yún)?shù)：無(wú)
輸出參數(shù)：無(wú)
返回值：無(wú)
數(shù)據(jù)流程圖
-------------------------------------------------------------------------------------------------------
函數(shù)名稱(chēng)：sort( )　　編號(hào)：002
函數(shù)功能：實(shí)現(xiàn)排序面
輸入?yún)?shù)：無(wú)
輸出參數(shù)：無(wú)
返回值：無(wú)
數(shù)據(jù)流程圖
-------------------------------------------------------------------------------------------------------
函數(shù)名稱(chēng)：inssort( )　　編號(hào)：003   
函數(shù)功能：實(shí)現(xiàn)插入排序
輸入?yún)?shù)：要排序數(shù)組地址，數(shù)組長(zhǎng)度
輸出參數(shù)：無(wú)
返回值：無(wú)
數(shù)據(jù)流程圖
 
-------------------------------------------------------------------------------------------------------
 
函數(shù)名稱(chēng)：msort( )　　編號(hào)：004    
函數(shù)功能：實(shí)現(xiàn)歸并排序
輸入?yún)?shù)：要排序數(shù)組地址,，臨時(shí)數(shù)組地址,，數(shù)組最左邊位置，數(shù)組最右邊位置,，
輸出參數(shù)：無(wú)
返回值：無(wú)
數(shù)據(jù)流程圖
 -------------------------------------------------------------------------------------------------------
函數(shù)名稱(chēng)：quicksort( )　　編號(hào)：005      
函數(shù)功能：實(shí)現(xiàn)快速排序
輸入?yún)?shù)：要排序數(shù)組地址,，數(shù)組最左邊位置，數(shù)組最右邊位置,，
輸出參數(shù)：無(wú)
返回值：無(wú)
 
函數(shù)名稱(chēng)：huff( )　　編號(hào)：006
函數(shù)功能：實(shí)現(xiàn)Huffman編碼與解碼
輸入?yún)?shù)：建樹(shù)的字符個(gè)數(shù),，字符和它的權(quán)值
輸出參數(shù)：無(wú)
返回值：無(wú)
4、數(shù)據(jù)結(jié)構(gòu)
  插入排序：L
   i=1   2   3  4   5   6   7
42 20 17 13 13 13 13 13
20 42 20 17 17 14 14 14
17 17 42 20 20 17 17 15
13 13 13 42 28 20 20 17
28 28 28 28 42 28 23 20
14 14 14 14 14 42 28 23
23 23 23 23 23 23 42 28
15 15 15 15 15 15 15 42
 
   快速排序：
72 6 57 88 60 42 83 73 48 85

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

Pivot=6              Pivot=73
 
6 42 57 48   72 73 85 88 83

Pivot=57             Pivot=88
 
42 48    57   85 83 88

Pivot=42              Pivot=85
 
42 48   83 85

 
6 42 48 57 60 72 73 83 85 88

        最終排好序的數(shù)組
 
   歸并排序：
    36 20 17 13 28 14 23 15
20 36 13 17 14 28 15 23
13 17 20 36 14 15 23 28
13 14 15 17 20 23 28 36

五,、    計(jì)中碰到的問(wèn)題及解決方法
程序的要求是要進(jìn)行一個(gè)操作后要返回原界面或主界面,，我用的是switch的結(jié)構(gòu)，和老師給的有所不同,，所以在處理這個(gè)問(wèn)題時(shí)出了一點(diǎn)問(wèn)題,，但后來(lái)一想，也很簡(jiǎn)單,，再調(diào)用一次原來(lái)的界面函數(shù)不就行了嗎,？
 
六、   收獲和體會(huì)
           通過(guò)這次課程實(shí)踐,，我加深了對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程的理解,，更好的掌握了各種排序方法和Huffman編碼與解碼！更鞏固了自己的C和C++的知識(shí),。
 
七,、   程序清單
主界面：
DS,cpp
 
#include "stdafx.h"
#include <iostream.h>
#include <iomanip.h>
void sort();//聲明要調(diào)用的函數(shù)
void huff();
void menu()
{
       int num;
       cout <<endl;
       cout <<setw(40) <<"主界面: " <<endl;
       cout <<setw(45) <<"1.排序              " <<endl;
       cout <<setw(45) <<"2.Huffman編碼與解碼 " <<endl;
       cout <<setw(45) <<"3.退出              " <<endl;
       cout <<setw(45) <<"請(qǐng)選擇操作類(lèi)型(1-3):"; cin >>num;cout <<endl;
      
       switch(num)// 通過(guò)swich語(yǔ)句進(jìn)行選擇
       {
       case 1: sort();break;
    case 2: huff();break;
    case 3: break;
    default: cout <<"error";
       }
}
void main()
{
       menu();
}
 
排序界面：
Sort.cpp
 
#include "stdafx.h"
#include <iostream.h>
#include <iomanip.h>
void inssort();/ //首先要聲明各個(gè)要調(diào)用的函數(shù)/
void menu();
void msort();
void qsort();
void sort() / 類(lèi)似于主界面，也通過(guò)switch語(yǔ)句進(jìn)行選擇/
{
       int num1;
       cout <<endl;
       cout <<setw(40) <<"排序界面:           " <<endl;
       cout <<setw(45) <<"1.插入排序          " <<endl;
       cout <<setw(45) <<"2.歸并排序          " <<endl;
       cout <<setw(45) <<"3.快速排序          " <<endl;
       cout <<setw(45) <<"4.返回              " <<endl;
       cout <<setw(45) <<"5.退出              " <<endl;
       cout <<setw(45) <<"請(qǐng)選擇操作類(lèi)型(1-5):";cin >>num1;cout <<endl;
       switch(num1)
       {
       case 1: inssort();break;
    case 2: msort();break;
    case 3: qsort();break;
       case 4: menu();break;
       case 5: break;
    default: cout <<"error";
       }
 
}
 
插入排序：
Inssort.cpp
 
#include "stdafx.h"
#include <iostream.h>
#include "stdio.h"
int time1=0;
int comp(int a,int b);//比較
void swap(int a[],int x,int y); //交換
void sort();//排序界面
void inssort1(int A[],int n)//進(jìn)行插入排序
{
       for(int i=0;i<n;i++)
              for(int j=i;(j>0)&&(comp(A[j],A[j-1]));j--)
                     swap(A,j,j-1);
}
int comp(int a,int b)
{
       int result;
    if(a>b)
              result=1;
       else
              result=0;
       return result;
       time1++;
}
void swap(int a[],int x,int y)
{
       int temp;
       temp=a[x];
       a[x]=a[y];
       a[y]=temp;
       time1++;
}
void inssort()
{
       int n;
       int A[80],B[80];
    cout <<"請(qǐng)輸入你要輸入的元素個(gè)數(shù)：" <<endl;
       cin >>n;
       cout <<"請(qǐng)輸入要排序的元素:" <<endl;
       for(int i=0;i<n;i++)
       {
              cin >>A[i];
       }
       for(int j=0;j<n;j++)
       {
              B[j]=A[j];
       }
       cout <<"進(jìn)行排序后的結(jié)果:" <<endl;
       inssort1(A,n);//進(jìn)行插入排序
       for(int k=0;k<n;k++)
       {
              cout <<A[k] <<" ";
       }
       cout <<endl;
       cout <<"時(shí)間復(fù)雜度為： ";
       cout <<time1 <<endl;
       char answer;
       cout <<"是否要打印排序前的數(shù)組?(y/n)" <<endl;
       cin >>answer;
       if(answer=='y')
       {
              for(int ii=0;ii<n;ii++)
                     cout <<B[ii] <<" ";
       }
       cout <<endl;
       getchar();
       sort();
}
 
歸并排序：
Mergesort.cpp
 
#include "stdafx.h"
#include <iostream.h>
#include "stdio.h"
void inssort1(int A[],int n);
int time2=0;//時(shí)間復(fù)雜度
extern int time1;
void sort();
void mergesort(int A[],int temp[],int left,int right)
{     if((right-left)<=32)
       {
              inssort1(&A[left],right-left+1);//對(duì)于較小的數(shù)組,，調(diào)用內(nèi)排序
              return;
       }
       int i,j,k,mid=(left+right)/2;
       if(left==right) return;
       mergesort(A,temp,left,mid);
       mergesort(A,temp,mid+1,right);
       for(i=mid;i>=left;i--)
       {
              temp[i]=A[i];
              time2++;
       }
       for(j=1;j<right-mid;j++)
       {
              temp[right-j+1]=A[j+mid];
              time2++;
       }
       for(i=left,j=right,k=left;k<=right;k++)
       {
              if(temp[i]<=temp[j])
              {
                     A[k]=temp[i++];
                     time2++;
              }
              else
              {
                     A[k]=temp[j--];
                     time2++;
              }
       }
      
 
}
 
void msort()
{
       int n,left,right;
       int time;
       int A[80];
       int B[80];
       int temp[80];
    cout <<"請(qǐng)輸入元素個(gè)數(shù)：" <<endl;
           cin >>n;
       left=0;
       right=n-1;
       cout <<"請(qǐng)輸入數(shù)組元素:" <<endl;
       for(int i=0;i<n;i++)
       {
              cin >>A[i];
       }
       for(int j=0;j<n;j++)
       {
              B[j]=A[j];
       }
       mergesort(A,temp,left,right);//進(jìn)行歸并排序
       cout <<"進(jìn)行排序后的結(jié)果:" <<endl;
       for(int k=0;k<n;k++)
       {
              cout <<A[k] <<" ";
       }
       cout <<endl;
       time=time1+time2;
       cout <<"時(shí)間復(fù)雜度為： ";
       cout <<time <<endl;
       char answer;
       cout <<"是否要打印排序前的數(shù)組?(y/n)" <<endl;
       cin >>answer;
       if(answer=='y')
       {
              for(int ii=0;ii<n;ii++)
                     cout <<B[ii] <<" ";
       }
       cout <<endl;
       getchar();
       sort();
}
 
快速排序：
Quicksort.cpp
 
#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(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=A[x], i=x+1, j=y, temp;
    while(1)
    {
        while(A[i]<n)
              {
                     ++i;
                     time3++;
              }
              while(A[j]>n)
              {
                     --j;
                     time3++;
              }
              if(i>=j) break;
        temp=A[i]; A[i]=A[j]; A[j]=temp;
              time3++;
    }
    A[x]=A[j];
    A[j]=n;
    return j;
}
 
void qsort( )
{
    int i, A[80],n,B[80];
       char answer;
       cout <<"請(qǐng)輸入元素個(gè)數(shù):";
       cin >>n;
       cout <<"請(qǐng)輸入要排序的元素:" <<endl;
    for(i=0; i<n; ++i)
        cin >>A[i];
       for(int j=0;j<n;j++)
              B[j]=A[j];
    quicksort(A, 0, n-1);
       cout <<"排序后的結(jié)果為:" <<endl;
    for(i=0; i<n; ++i)
        cout <<A[i] <<" ";
    cout <<endl;
    cout <<"時(shí)間復(fù)雜度為:" <<time3 <<endl;
       cout <<"是否打印排序前的數(shù)組?(y/n)";
       cin >>answer;
       if(answer=='y')
       {
              for(int k=0;k<n;k++)
              {
                     cout <<B[k] <<" ";
              }
       }
    cout <<endl;
       getchar();
       sort();
      
}
 
Huffman編碼：
Huff.cpp
#include "stdafx.h"
#include <iostream.h>
#include "stdio.h"
#include "string.h"
#define MAX 99
char cha[MAX];
char hc[MAX-1][MAX];
int s1,s2; //設(shè)置全局變量,，以便在方法(函數(shù))select中返回兩個(gè)變量
void menu();
typedef struct //huffman樹(shù)存儲(chǔ)結(jié)構(gòu)
{
 unsigned int wei;
 int lch,rch,parent;
}hufftree;
 
 
void select(hufftree tree[],int k) //找尋parent為0,權(quán)最小的兩個(gè)節(jié)點(diǎn)
{
 int i;
 for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;
 for (i=1;i<=k;i++)
    if (tree[i].parent==0 && tree[i].wei<tree[s1].wei) s1=i;
 for (i=1; i<=k ; i++)
    if (tree[i].parent==0 && i!=s1) break; s2=i;
 for (i=1;i<=k;i++)
    if ( tree[i].parent==0 && i!=s1 && tree[i].wei<tree[s2].wei) s2=i;
}
 
void huffman(hufftree tree[],int *w,int n) //生成huffman樹(shù)
{ int m,i;
   if (n<=1) return;
   m=2*n-1;
 for (i=1;i<=n;i++)
   {
        tree[i].wei=w[i];
        tree[i].parent=0;
      tree[i].lch=0;
        tree[i].rch=0;
 }
 for (i=n+1;i<=m;i++)
   {
        tree[i].wei=0;
        tree[i].parent=0;
      tree[i].lch=0;
        tree[i].rch=0;
 }
   for (i=n+1;i<=m;i++)
   {
          select(tree, i-1);
       tree[s1].parent=i;
       tree[s2].parent=i;
       tree[i].lch=s1;
       tree[i].rch=s2;    
       tree[i].wei=tree[s1]. wei+ tree[s2].wei;
      }
}
void huffmancode(hufftree tree[],char code[],int n)
{
 int start,c,i,f;
 code[n-1]='\0';
 cout <<"Huffman編碼:" <<endl;
 for(i=1;i<=n;i++)
 {
        start=n-1;
       for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)
       {  
               if(tree[f].lch==c)       
                      code[--start]='0';    
               else            
                      code[--start]='1';
        }
     strcpy(hc[i],&code[start]);
     cout <<cha[i] <<"-->" <<hc[i] <<endl;
 }
}
void tohuffmancode(int n)
{
   int i=0,j;
   char anychar[9999];
   cout <<"請(qǐng)輸入一段字符:" <<endl;
   cin >>anychar;
   cout <<"進(jìn)行Huffman編碼后的結(jié)果為:" <<endl;
   for (;anychar[i]!='\0';i++)
   {
      j=0;
      for(;anychar[i]!=cha[j]&&j<=n;)
               j++;
      if (j<=n)
               cout <<hc[j];
   }
   cout <<endl;
}
 
void decode(char ch[],hufftree tree[],int n)
{
 int i,j,m;
 char b;
 m=2*n-1;
 i=m;
 cout <<"請(qǐng)輸入你要解碼的編碼:" <<endl;
 cin >>b;
 cout <<"解碼結(jié)果為:" <<endl;
 while(b!='#')   //遇到回車(chē)時(shí)，結(jié)束
 {
 
 if(b=='0')
        i=tree[i].lch;
 else
        i=tree[i].rch;
 if(tree[i].lch==0)
 {
        cout <<ch[i];
      j=i,i=m;
 }
 cin >>b;
 }
 if(tree[j].lch!=0)
    cout <<"發(fā)生錯(cuò)誤!!";
}
 
void huff()
{
 int i=0,n=0;
 int *w,wei[MAX];
 char code[MAX];
 hufftree tree[MAX];
 w=wei;
 cout <<"請(qǐng)輸入n(n為你要建樹(shù)的字符個(gè)數(shù)):" <<endl;
 cin >>n;
 cout <<"請(qǐng)輸入字符和它的權(quán)值(例如:a20):" <<endl;
 for(i=1;i<=n;i++)
 {
        cin >>cha[i] >>wei[i];
 }
 huffman(tree,w,n);   //生成huffman樹(shù)
 huffmancode(tree,code,n); //編碼A
 tohuffmancode(n);//編碼B
 decode(cha,tree,n); //譯碼
 cout <<"按任意鍵返回";
 getchar();
 menu();