插入排序：
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)//进行插入排序
{
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 <<"请输入你要输入的元素个数：" <<endl;
cin >>n;
cout <<"请输入要排序的元素:" <<endl;
for(int i=0;i<n;i++)
{
cin >>A[i];
}
for(int j=0;j<n;j++)
{
B[j]=A[j];
}
cout <<"进行排序后的结果:" <<endl;
inssort1(A,n);//进行插入排序
for(int k=0;k<n;k++)
{
cout <<A[k] <<" ";
}
cout <<endl;
cout <<"时间复杂度为： ";
cout <<time1 <<endl;
char answer;
cout <<"是否要打印排序前的数组?(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;//时间复杂度
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);//对于较小的数组，调用内排序
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 <<"请输入元素个数：" <<endl;
cin >>n;
left=0;
right=n-1;
cout <<"请输入数组元素:" <<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);//进行归并排序
cout <<"进行排序后的结果:" <<endl;
for(int k=0;k<n;k++)
{
cout <<A[k] <<" ";
}
cout <<endl;
time=time1+time2;
cout <<"时间复杂度为： ";
cout <<time <<endl;
char answer;
cout <<"是否要打印排序前的数组?(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 <<"请输入元素个数:";
cin >>n;
cout <<"请输入要排序的元素:" <<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 <<"排序后的结果为:" <<endl;
for(i=0; i<n; ++i)
cout <<A[i] <<" ";
cout <<endl;
cout <<"时间复杂度为:" <<time3 <<endl;
cout <<"是否打印排序前的数组?(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; //设置全局变量，以便在方法(函数)select中返回两个变量
void menu();
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 && 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树
{ 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 <<"请输入一段字符:" <<endl;
cin >>anychar;
cout <<"进行Huffman编码后的结果为:" <<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 <<"请输入你要解码的编码:" <<endl;
cin >>b;
cout <<"解码结果为:" <<endl;
while(b!='#') //遇到回车时，结束
{
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 <<"发生错误!!";
}
void huff()
{
int i=0,n=0;
int *w,wei[MAX];
char code[MAX];
hufftree tree[MAX];
w=wei;
cout <<"请输入n(n为你要建树的字符个数):" <<endl;
cin >>n;
cout <<"请输入字符和它的权值(例如:a20):" <<endl;
for(i=1;i<=n;i++)
{
cin >>cha[i] >>wei[i];
}
huffman(tree,w,n); //生成huffman树
huffmancode(tree,code,n); //编码A
tohuffmancode(n);//编码B
decode(cha,tree,n); //译码
cout <<"按任意键返回";
getchar();
menu();
}上一页 [1] [2]
Huffman编码和解码以及排序 第2页下载如图片无法显示或论文不完整，请联系qq752018766
