开学了老师出了一道题目考全年级同学~给出程序过程，要求我们写出注释每一步都是做什么的，过了5天都没有一个同学交卷~这里有高手的请帮帮忙~老师要求星期一交卷5555555555 #include<iostream.h> #include<stdio.h> #include<string.h> #include<stdlib.h> struct Hnode{ Hnode * parent; int weight; int id; Hnode * lchild; Hnode * rchild; char code[10]; char ch;};
struct Ht{ Hnode arr[100]; int leaves; int total; }; Ht* statistic_char(char * text,Ht * t); Ht * create_tree(Ht * t); void code_string(Ht*t);
//------------------------------------------------------ // main program goes here! //
void display(Ht * t,char *text) { char * p=NULL;int len; printf("%s\n",text); len=strlen(text); cout<<len; for (int i=0;i<len;i++) { cout<<text[i];
}
}
int main(int argc, char* argv[]) { char str[20];Ht *t=NULL; printf("please input a string!\n"); scanf("%s",str); printf("%s\n",str); t=statistic_char(str,t); t=create_tree(t); code_string(t); display(t,str); return 0; }
Ht* statistic_char(char * text,Ht * t) { t=(Ht*)malloc(100*sizeof(Hnode)); t->total =0; t->leaves =0; cout<<t->total <<t->leaves <<endl; int len=strlen(text); printf("%s",text); for (int i=0;i<len;i++) { for (int j=0;j<t->leaves;j++) { if (t->arr[j].ch==text[i]) { t->arr[j].weight++; break; } } if (j==t->leaves ) { t->arr[t->leaves].ch =text[i]; t->arr[t->leaves].weight=1; t->leaves ++; } } t->total =2*t->leaves-1; cout<<endl; /* for (int h=0;h<t->leaves;h++) { cout<<t->arr[h].ch;cout<<t->arr[h].weight<<h<<t->total <<t->leaves <<endl;}*/ return t; }
Ht * create_tree(Ht * t) { Hnode * min_1=(Hnode*)malloc(sizeof(Hnode)); Hnode * min_2=(Hnode*)malloc(sizeof(Hnode)); int min1,min2,xb1,xb2;int temp=t->leaves;
for (int i=0;i<t->leaves;i++) { t->arr[i].parent=NULL; t->arr[i].lchild=NULL; t->arr[i].rchild=NULL; t->arr[i].id=0; cout<<t->arr[i].id<<t->arr[i].ch ; }
//cout<<t->leaves<<";"<<t->total<<endl; while (t->leaves<t->total ) { for (int j=0;j<t->leaves ;j++) {if (t->arr[j].id==0) {min1=t->arr[j].weight ;break;}}//初始化min1
for (int m=0;m<t->leaves ;m++) {if (min1>=t->arr[m].weight&&t->arr[m].id==0) {min1=t->arr[m].weight;}}//查小最小min1
for (m=0;m<t->leaves ;m++)//记下最小元素的下标 {if (min1==t->arr[m].weight&&t->arr[m].id==0) xb1=m;} min_1=&t->arr[xb1];//记下该元素地址； t->arr[xb1].id=1;//将该元素的下标置1； //--------------------------------------------------------------- for (int k=0;k<t->leaves ;k++) {if (t->arr[k].id==0) {min2=t->arr[k].weight ;break;}}//初始化min2 cout<<"min1="<<min1<<endl; cout<<"min2="<<min2<<endl;
//----------------------------------- for (int n=0;n<t->leaves ;n++) {if (min2>=t->arr[n].weight&&t->arr[n].id==0) {min2=t->arr[n].weight;}}//最小化min2 for(n=0;n<t->leaves;n++) {if (min2==t->arr[n].weight&&t->arr[n].id==0) xb2=n;}//记下该元素的下标 cout<<"min2IV"<<min2<<endl; min_2=&t->arr[xb2]; t->arr[xb2].id=1; cout<<"min2II"<<min2<<endl; //-------------------------------------
cout<<"min here"; cout<<min1<<";"<<min2;//测试 //------------------------------------------------------------------- min_1->parent=&t->arr[t->leaves]; min_2->parent=&t->arr[t->leaves]; t->arr[t->leaves].lchild=min_1; t->arr[t->leaves].rchild=min_2; t->arr[t->leaves].ch='X'; t->arr[t->leaves].parent=NULL; t->arr[t->leaves].weight=min1+min2; t->arr[t->leaves].id=0; cout<<"iD"<<t->arr[t->leaves].id<<endl; t->leaves++; cout<<"iD"<<t->arr[t->leaves].id<<endl; } cout<<"id"<<t->arr[t->leaves-1].id<<endl;
cout<<endl; for (int k=0;k<t->leaves;k++) { if (t->arr[k].id==0){ cout<<t->arr[k].id<<endl; cout<<t->arr[k].ch<<endl; cout<<t->arr[k].weight<<endl; } } t->leaves=temp; return t; }
void code_string(Ht*t) { int j; char * p; Hnode * parentnode=(Hnode*)malloc(sizeof(Hnode)); Hnode * pa=(Hnode*)malloc(sizeof(Hnode)); cout<<endl<<endl; for (int i=0; i<t->leaves ;i++) { j=0; pa=&t->arr[i]; parentnode=pa->parent; cout<<t->arr[i].ch ; while(parentnode!=NULL) { if(parentnode->lchild==pa) {t->arr[i].code[j++]='0';cout<<t->arr[i].code[j-1];} else {t->arr[i].code[j++]='1';cout<<t->arr[i].code[j-1];} pa=parentnode; parentnode=parentnode->parent; } //t->arr[i].code[j]='0';cout<<t->arr[i].code[j];j++; t->arr[i].code[j]='\0'; cout<<t->arr[i].code[j]; cout<<endl; }
for(int k=0;k<t->total;k++) { cout<<"HRER GOES!"<<endl; cout<<t->arr[k].ch<<"CH "<<t->arr[k].lchild<<"L " <<t->arr[k].rchild<<"R "<<t->arr[k].parent<<"P "<<t->arr[k].weight<<"W " <<&t->arr[k]<<endl; } cout<<"HERE!"<<endl; for (j=0;j<t->leaves;j++) {printf("%s\n",t->arr[j].code); } for(k=0;k<t->leaves;k++) { for(j=0;j<10;j++) { if (t->arr[k].code[j]==NULL) {p=&t->arr[k].code[j]-1; break; } } cout<<t->arr[k].ch<<"的编码是："; do{ cout<<*p;p--; }while( p!=&t->arr[k].code[0]-1); cout<<endl; } }
