Huffman编译码
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
typedef struct
{
int weight;
char ch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct
{
char ch;
char *chs;
}HuffmanCode;
typedef struct
{
char ch;
int weight;
}sw;
typedef struct
{
HuffmanTree HT;
HuffmanCode *HC;
}huf;
void select(HTNode * HT,int n,int *n1,int *n2)
{
int i=1;
int n3;
while(HT[i].parent!=0) i++;
*n1=i;
i++;
while(HT[i].parent!=0) i++;
*n2=i;
if(HT[*n1].weight<HT[*n2].weight)
{
n3=*n1;
*n1=*n2;
*n2=n3;
}
for(i++;i<=n;i++)
{
if(HT[i].parent==0)
{
if(HT[i].weight<HT[*n1].weight)
*n1=i;
else if(HT[i].weight<HT[*n2].weight)
*n2=i;
}
}
}
huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
{
int m,i,s1,s2,start,c,f;
HuffmanTree p;
char *cd;
if(n<=1) return 0;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++,w++)
{
p->weight=w->weight;
p->ch=w->ch;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->ch='^';
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++)
{
select(HT,i-1,&s1,&s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode *)malloc((n+1)*sizeof(char));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)cd[--start]='0';
else cd[--start]='1';
HC[i].ch=HT[i].ch;
HC[i].chs=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i].chs,&cd[start]);
printf("%c %-10s\n",HC[i].ch,HC[i].chs);
}
HUF->HT=HT;
HUF->HC=HC;
return HUF;
}
char * convert(char *chars,char *chars1,HuffmanCode *hc,int n)
{
char *p=chars; int i;
strcpy(chars1,"");
while(*p)
{
i=1;
while(hc[i].ch!=*p&&i<=n) i++;
strcat(chars1,hc[i].chs);
p++;
}
printf("the chars translate are:%s\n",chars1);
return chars1;
fflush(stdin);
}
void transcode(HuffmanTree ht,char *chars2,char*chars3)
{
int i=1,p; char *q=chars2;char *r=chars3;
while(ht[i].parent!=0) i++;
p=i;
while(*q)
{
while(ht[p].lchild!=0 && *q)
{
if(*q=='0')
p=ht[p].lchild;
else p=ht[p].rchild;
q++;
}
if(ht[p].lchild==0)
{
*r=ht[p].ch;
r++;
}
p=i;
}
*r='\0';
printf("the chars are:");
puts(chars3);
fflush(stdin);
}
void input(int *n,sw *w)
{
int i;
printf("input the amount of char:"); /*输入字符的数目*/
scanf("%d",n);
for(i=1;i<=*n;i++,w++)
{
printf("input the %dth char and weight:",i); /*输入每个节点的字符和其权值*/
fflush(stdin);
scanf("%c%d",&w->ch,&w->weight);
}
}
void main()
{
char x;
HTNode HT;
HuffmanCode HC,*hc;
HuffmanTree ht;
huf *HUF,huf2;
int n;
sw w[40];
char ch,inchar[500],outchar[1000];
char *abc;
char *p=inchar;
printf("下面开始进行Huffman编译码：\n");
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
printf("input chars to translate and end with '#':");
fflush(stdin);/*清除流,解决输入干扰*/
ch=getchar();
while(ch!='#')
{
*p=ch;
p++;
ch=getchar();
}
*p='\0';
hc=HUF->HC;
ht=HUF->HT;
abc=convert(inchar,outchar,hc,n);
transcode(ht,abc,outchar);
getchar();
fflush(stdin);
printf("Do you want to try again?(y/n)");
x=getchar();
while(x=='y'){
input(&n,w);
HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
printf("input chars to translate and end with '#':");
fflush(stdin);/*清除流,解决输入干扰*/
ch=getchar();
while(ch!='#')
{
*p=ch;
p++;
ch=getchar();
}
*p='\0';
hc=HUF->HC;
ht=HUF->HT;
abc=convert(inchar,outchar,hc,n);
transcode(ht,abc,outchar);
fflush(stdin);
getchar();
fflush(stdin);
printf("Do you want to try again?(y/n)");
x=getchar();
}
while(x=='n') break;
getchar();
}
用栈实现表达式求值
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#include"stdio.h"
#include"stdlib.h"
typedef struct SqStack //栈的顺序存储结构
{
double *base;
double *top;
int stacksize;
}SqStack;
void InitStack (SqStack &S) //构造一个空栈
{
S.base=(double *)malloc(STACK_INIT_SIZE*sizeof(double)); //分配储存空间
if(!S.base) exit (-1); //空间分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE; //空间初始分配
}//InitStack
bool GetTop (SqStack S,double &e)
{ //若栈不空，则用e返回S的栈顶元素，并返回true；否则返回false
if(S.top==S.base)
return false;
e=*(S.top-1);
return true;
}//GetTop
bool Push(SqStack &S,double e)
{ //插入元素为e的新的栈顶元素
if(S.top-S.base>=S.stacksize)
{ //栈满，追加存储空间
S.base=(double*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(double));
if(!S.base)
exit(-1); //存储空间分配失败
S.top=S.base+S.stacksize; //此处内存有可能重新分配,S.base地址有可能会变，此句不能省
S.stacksize+=STACKINCREMENT;
}
*S.top++=e; //top自增
return true;
}// Push
bool Pop(SqStack &S,double &e) //若栈不空，则删除S的栈顶元素，用e返回其值
{
if(S.top==S.base)
return false;
e=*--S.top; //删除一个元素,top减一
return true ;
}// Pop
char Precede(char a1 ,char a2)//判定运算符的优先级。
{
char r;
switch(a2)
{
case'+': //此处由于加减几乎优先级一样，故放在一起
case'-':
if(a1=='('||a1=='#')
r='<';
else
r='>';
break;
case'*': //此处由于乘除优先级一样，故放在一起
case'/':
if(a1=='*'||a1=='/'||a1==')')
r='>';
else
r='<';
break;
case'(':
if(a1==')')
{
printf("括号匹配错误!\n");
exit(-1);
}
else
r='<';
break;
case')':
if(a1=='(')
r='=';
else if(a1=='#')
{
printf("eeror!没有左括号\n");
exit (-1);
}
else
r='>';
break;
case'#':
switch(a1)
{
case'#':
r='=';
break;
case'(':
printf("eeror!没有右括号\n");
exit(-1);
default:
r='>';
}//switch
break;
}//switch
return r;
}//Precede
bool In(char d) //判断c是否为七种运算符之一
{
switch(d)
{
case'+':
case'-':
case'*':
case'/':
case'(':
case')':
case'#':
return true;
default:
return false;
}//switch
}
double Operate( double a, double theta, double b ) //Operate为进行二元运算的a theta b的函数
{
char n=char(theta); //此处把double型强制转换成int型，虽然会造成精度缺失，但本身theta是一个符号，也算是整型
switch(n) //转换后相当于和符号匹配ACSII码
{
case'+':
return a+b;
case'-':
return a-b;
case'*':
return a*b;
default:
if(b!=0)
return a/b;
else
{
printf("error!除数不能为零\n");
exit(-1);
}
}//switch
}
double EvaluateExpression()
{ //算符表达式的优先算法。设OPTR和OPND分别为运算符栈和运算数栈
SqStack OPTR,OPND;
char c;
char Data[11]; //定义此数组为了存放整数或小数
double a,b,d,e;
InitStack(OPTR); //构造一个运算符栈
InitStack(OPND); //构造一个运算数栈
Push(OPTR,'#'); //将#压入栈底
c=getchar();
GetTop(OPTR,e);
while(c!='#'||e!='#') //栈顶不是#号且输入不是#号
{
if(In(c))//是符号则进栈
{
switch(Precede(e,c))
{
case'<': //栈顶元素优先级低
Push(OPTR,c);
c=getchar();
break;
case'=': //脱括号并接受下一字符
Pop(OPTR,e);
c=getchar();
break;
case'>': //退栈并将运算结果入栈
Pop(OPTR,e);
Pop(OPND,b);
Pop(OPND,a);
Push(OPND,Operate(a,e,b));
break;
}//switch
}
else if(c>='0'&&c<='9'||c=='.')
{
int i=0;
while(c>='0'&&c<='9'||c=='.')
{
Data[i]=c;
i++;
c=getchar();
}
Data[i]='\0'; //数字没有存满,输入字符串结束符
d=atof(Data); //此处是把数组里的数字，实际上是按字符串；转换为double类型，然后把浮点型数字入栈
Push(OPND,d); //atof函数的形参是指针类型，故用数组名
}
else
{
printf("error!输入错误!\n");
exit(-1);
}
GetTop(OPTR,e);
}//while
GetTop(OPND,e);
return e;
}//EvaluateExpression
main()
{
char ch;
double result;
printf("请输入表达式，以#号结束\n");
result=EvaluateExpression();
printf("结果为%f:\n",result);
printf("您想再试一次吗？如果想，请输入'Y';否则输入'N'\n");
fflush (stdin);
ch=getchar();
while(ch=='Y'||ch=='y'){
printf("请输入表达式，以#号结束\n");
fflush (stdin);
result=EvaluateExpression();
printf("结果为%f:\n",result);
fflush (stdin);
}
}