用递归的话，每次递归，都需要调用该函数。然而，调用函数，系统需拆盯要把主调函数的状态保存在系统栈里面。旅戚和回到主调函数又要把原来保存的这仔困些状态重新读取，显然增大了很多的 *** 作。
在windows环境下C语言推荐使用编译软件：vc 6.0,Visual Studio ,c-free,turboc等，其中较好编译软件为vc 6.0。厅念携 Microsoft Visual C++ 6.0，简称VC6.0，是微软推出的一款C++编译器，将“高级语言”翻高带译为“机器语言（低级语言）”的程扮伏序。我把网上的程序修改了一下，并整合了，你看看#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define M 50
#define MAX 100000
typedef struct
{
int weight//结点权值
int parent,lchild,rchild
}HTNODE,*HUFFMANTREE
typedef char** HUFFMANCODE//动态分配数组存储哈夫曼编码表
typedef struct
{
int key/*关键字*/
}RecordNode/*排序节点的类型*/
typedef struct
{
RecordNode *record
int n/*排序对象的大小*/
}SortObject//待排序序列
HUFFMANTREE huffmantree(int n,int weight[])//构建哈夫曼树
{
int m1,m2,k
int i,j,x1,x2
HUFFMANTREE ht
ht=(HUFFMANTREE)malloc((2*n)*sizeof(HTNODE))
for(i=1i<(2*n)i++)//初始化哈夫曼树中宴镇各结点的数据，没初始值的赋值为0
{
ht[i].parent=ht[i].lchild=ht[i].rchild=0
if(i<=n)
ht[i].weight=weight[i]
else
ht[i].weight=0
}
for(i=1i<ni++)//每一重循环从森林中选择最小的两棵树组建成一颗新树
{
m1=m2=MAX
x1=x2=0
for(j=1j<(n+i)j++)
{
if((ht[j].weight<m1)&&(ht[j].parent==0))
{
m2=m1
x2=x1
m1=ht[j].weight
x1=j
}
else if((ht[j].weight<m2)&&(ht[j].parent==0))
{
m2=ht[j].weight
x2=j
}
}
k=n+i
ht[x1].parent=ht[x2].parent=k
ht[k].weight=m1+m2
ht[k].lchild=x1
ht[k].rchild=x2
}
return ht
}
void huffmancoding(int n,HUFFMANCODE hc,HUFFMANTREE ht,char str[])
{
int i,start,child,father
char *cd
hc=(HUFFMANCODE)malloc((n+1)*sizeof(char*))//分配n个字符编码的头指针
cd=(char*)malloc(n*sizeof(char))//分配求编码的工作蔽祥顷空间
cd[n-1]='\0'//编码结束符
for(i=1i<=n++i)//逐个字符求哈夫曼编码
{
start=n-1
for(child=i,father=ht[i].parentfather!=0child=father,father=ht[father].parent)/*从叶子结点到根结点求逆向编码*/
if(ht[father].lchild==child)
cd[--start]='0'
else
cd[--start]='1'
hc[i]=(char*)malloc((n-start)*sizeof(char))//为i个字符编码分配空间
strcpy(hc[i],&cd[start])//从cd复制哈夫曼编码串到hc
}
free(cd)//释放工作空间
for(i=1i<=n++i)
{
printf("\n%c的编码:",str[i])
printf("%s\n",hc[i])
}
}
void huffman()
{
int i,j,k,m,n
char str[50]
int weight[50]
HUFFMANCODE hc=NULL
HUFFMANTREE ht
fflush(stdin)
printf("\n请宏陆输入字符(一次性连续输入所求的字符):")/*如:abcjhjg不要输成ab cj hig,即字符间不加空格*/
gets(str)
for(j=0j<50j++)
{
if(str[j]=='\0')
break
}
n=j
for(j=nj>0j--)
str[j]=str[j-1]
str[n+1]='\0'
for(k=0k<nk++)
{
printf("\n请输入%c的权值:",str[k+1])
scanf("%d",&weight[k])
}
for(k=nk>0k--)
weight[k]=weight[k-1]
weight[0]=0
ht=huffmantree(n,weight)
huffmancoding(n,hc,ht,str)
}
void InsertSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k
RecordNode temp
SortObject *pvector
fflush(stdin)
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!")
getchar()
exit(1)
}
k=pvector->n
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k)
for(i=0i<p->ni++)/* 复制数组*/
pvector->record[i]=p->record[i]
pvector->n=p->n
*compare=0
*exchange=0
for(i=1i<pvector->ni++)
{
temp=pvector->record[i]
(*exchange)++
j=i-1
while((temp.key<pvector->record[j].key)&&(j>=0))
{
(*compare)++
(*exchange)++
pvector->record[j+1]=pvector->record[j]
j--
}
if(j!=(i-1))
{
pvector->record[j+1]=temp
(*exchange)++
}
}
free(pvector)
}
void SelectSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,k
RecordNode temp
SortObject *pvector
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!")
getchar()
exit(1)
}
k=pvector->n
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k)
for(i=0i<p->ni++)/*复制数组*/
pvector->record[i]=p->record[i]
pvector->n=p->n
*compare=0
*exchange=0
for(i=0i<pvector->n-1i++)
{
k=i
for(j=i+1j<pvector->nj++)
{
(*compare)++
if(pvector->record[j].key<pvector->record[k].key)
k=j
}
if(k!=i)
{
temp=pvector->record[i]
pvector->record[i]=pvector->record[k]
pvector->record[k]=temp
( *exchange)+=3
}
}
free(pvector)
}
void BubbleSort(SortObject *p,unsigned long *compare,unsigned long *exchange)
{
int i,j,noswap,k
RecordNode temp
SortObject *pvector
if((pvector=(SortObject *)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!")
getchar()
exit(1)
}
k=pvector->n
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k)
for(i=0i<p->ni++)/* 复制数组*/
pvector->record[i]=p->record[i]
pvector->n=p->n
*compare=0
*exchange=0
for(i=0i<pvector->n-1i++)
{
noswap=1
for(j=0j<pvector->n-i-1j++)
{
(*compare)++
if(pvector->record[j+1].key<pvector->record[j].key)
{
temp=pvector->record[j]
pvector->record[j]=pvector->record[j+1]
pvector->record[j+1]=temp
(*exchange)+=3
noswap=0
}
}
if(noswap) break
}
free(pvector)
}
void ShellSort(SortObject *p,int d,unsigned long *compare,unsigned long *exchange)
{
int i,j,increment,k
RecordNode temp
SortObject *pvector
if((pvector=(SortObject*)malloc(sizeof(SortObject)))==NULL)
{
printf("OverFollow!")
getchar()
exit(1)
}
k=pvector->n
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k)
for(i=0i<p->ni++)/* 复制数组*/
pvector->record[i]=p->record[i]
pvector->n=p->n
*compare=0
*exchange=0
for(increment=dincrement>0increment/=2)
{
for(i=incrementi<pvector->ni++)
{
temp=pvector->record[i]
(*exchange)++
j=i-increment
while(j>=0&&temp.key<pvector->record[j].key)
{
(*compare)++
pvector->record[j+increment]=pvector->record[j]
(*exchange)++
j-=increment
}
pvector->record[j+increment]=temp
(*exchange)++
}
}
free(pvector)
}
void QuickSort(SortObject *pvector,int left,int right,unsigned long *compare,unsigned long *exchange)
{
int i,j
RecordNode temp
if(left>=right)
return
i=left
j=right
temp=pvector->record[i]
(*exchange)++
while(i!=j)
{
while((pvector->record[j].key>=temp.key)&&(j>i))
{
(*compare)++
j--
}
if(i<j)
{
pvector->record[i++]=pvector->record[j]
(*exchange)++
}
while((pvector->record[i].key<=temp.key)&&(j>i))
{
(*compare)++
i++
}
if(i<j)
{
pvector->record[j--]=pvector->record[i]
(*exchange)++
}
}
pvector->record[i]=temp
(*exchange)++
QuickSort(pvector,left,i-1,compare,exchange)
QuickSort(pvector,i+1,right,compare,exchange)
}
void SortMethod(void)
{
int i,j,k,l
unsigned long num[5][10]={0}
unsigned long sum[10]={0}
SortObject *pvector
fflush(stdin)
printf("请输入待排序的随机数个数：\n")
scanf("%d",&k)
pvector=(SortObject *)malloc(sizeof(SortObject))
for(j=0j<5j++)
{
pvector->record=(RecordNode *)malloc(sizeof(RecordNode)*k)
for(i=0i<ki++)
pvector->record[i].key=rand()
pvector->n=k
InsertSort(pvector,&num[j][0],&num[j][1])
SelectSort(pvector,&num[j][2],&num[j][3])
BubbleSort(pvector,&num[j][4],&num[j][5])
ShellSort(pvector,4,&num[j][6],&num[j][7])
QuickSort(pvector,0,k-1,&num[j][8],&num[j][9])
}
printf("\n排序比较如下")
for(j=0j<5j++)
{
printf("\n\n对%d个数进行排序，结果为：\n",k)
printf("1.插入排序：比较-->%-7ld次移动-->%-7ld次\n",num[j][0],num[j][1])
printf("2.选择排序：比较-->%-7ld次移动-->%-7ld次\n",num[j][2],num[j][3])
printf("3.冒泡排序：比较-->%-7ld次移动-->%-7ld次\n",num[j][4],num[j][5])
printf("4.希尔排序：比较-->%-7ld次移动-->%-7ld次\n",num[j][6],num[j][7])
printf("5.快速排序：比较-->%-7ld次移动-->%-7ld次\n",num[j][8],num[j][9])
if(j!=5)
printf("按回车继续\n")
getchar()
}
for(j=0j<5j++)
{
sum[0]=sum[0]+num[j][0]
sum[1]=sum[1]+num[j][1]
sum[2]=sum[2]+num[j][2]
sum[3]=sum[3]+num[j][3]
sum[4]=sum[4]+num[j][4]
sum[5]=sum[5]+num[j][5]
sum[6]=sum[6]+num[j][6]
sum[7]=sum[7]+num[j][7]
sum[8]=sum[8]+num[j][8]
sum[9]=sum[9]+num[j][9]
}
printf("\n\n对%d个随机数进行5次排序，平均比较次数和平均移动次数为：\n",k)
printf("1.插入排序：平均比较-->%-7ld次平均移动-->%-7ld次\n",sum[0]/5,sum[1]/5)
printf("2.选择排序：平均比较-->%-7ld次平均移动-->%-7ld次\n",sum[2]/5,sum[3]/5)
printf("3.冒泡排序：平均比较-->%-7ld次平均移动-->%-7ld次\n",sum[4]/5,sum[5]/5)
printf("4.希尔排序：平均比较-->%-7ld次平均移动-->%-7ld次\n",sum[6]/5,sum[7]/5)
printf("5.快速排序：平均比较-->%-7ld次平均移动-->%-7ld次\n",sum[8]/5,sum[9]/5)
free(pvector)
}
void sort()
{
int i
while(1)
{
SortMethod()
printf("\n是否继续？\n1.继续\n2.返回菜单\n")
scanf("%d",&i)
if(i==2)break
fflush(stdin)
getchar()
}
}
void huff()
{
int i
while(1)
{
huffman()
printf("\n是否继续？\n1.继续\n2.返回菜单\n")
scanf("%d",&i)
if(i==2)break
fflush(stdin)
getchar()
}
}
main()
{
int i,j,k
while(1)
{
printf("请选择要运行的功能：\n")
printf("1.哈夫曼编码译码器\n")
printf("2.内部排序性能分析\n")
printf("3.退出该程序\n\n")
printf("你的选择为：")
scanf("%d",&i)
switch(i)
{
case 1:huff()break
case 2:sort()break
case 3:exit(0)
default:break
}
fflush(stdin)
getchar()
system("cls")
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）