swust西南科技大学OJ数据结构80题答案

#include<iostream> #include<cstring> using namespace std; typedef struct//哈夫曼树 { char data; double weight; int parent; int lchild; int rchild; }HTNode; HTNode ht[3000]; char code[1000]; int n; void CreateHT()//构造哈弗曼树 { int i,k,lnode,rnode; double minL,minR; for(i=0;i<2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) { minL=minR=50000; lnode=rnode=-1; for(k=0;k<i;k++) if(ht[k].parent==-1) { if(ht[k].weight<minL) { minR=minL;rnode=lnode; minL=ht[k].weight;lnode=k; } else if(ht[k].weight<minR) { minR=ht[k].weight;rnode=k;} } ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; ht[lnode].parent=ht[rnode].parent=i; } } void ccode()//解码 { int L=strlen(code),i,root=14; for(i=0;i<L;i++) { if(code[i]=='0') root=ht[root].lchild; else if(code[i]=='1') root=ht[root].rchild; if(ht[root].lchild==-1) { cout<<ht[root].data; root=14; } } } int main() { int i; n=8; int weight[]={5,29,7,8,14,23,3,11}; char data[]={'a','b','c','d','e','f','g','h'}; for(i=0;i<n;i++) { ht[i].weight=weight[i]; ht[i].data=data[i]; } CreateHT(); cin>>code; ccode(); return 0; } ******************* #include<stdlib.h> #include<iostream> using namespace std; struct hbtnode { char data; int weight; int parent; int lchild; int rchild; }; void creathbtnode(char data[],int weight[],hbtnode ha[],int n) { int i,j,min1,min2,lmin,rmin; for(i=0;i<n;i++) { ha[i].data=data[i]; ha[i].weight=weight[i]; } for(i=0;i<2*n-1;i++) { ha[i].parent=ha[i].lchild=ha[i].rchild=-1; } for(i=n;i<2*n-1;i++) { min1=min2=23767; lmin=rmin=-1; for(j=0;j<i;j++) { if(ha[j].parent==-1) { if(ha[j].weight<min1) { min2=min1;rmin=lmin; min1=ha[j].weight;lmin=j; } else if(ha[j].weight<min2) { min2=ha[j].weight; rmin=j; } } } ha[i].weight=min1+min2; ha[i].lchild=lmin; ha[i].rchild=rmin; ha[lmin].parent=ha[rmin].parent=i; } } void translation(hbtnode ha[],int n) { char as[1000]; cin>>as; int i=0,j; while(as[i]!='\0') { j=2*n-1-1; while(ha[j].lchild!=-1&&ha[j].rchild!=-1&&as[i]!='\0') { if(as[i]=='0') j=ha[j].lchild; else if(as[i]=='1') j=ha[j].rchild; i++; } if(j<8)cout<<ha[j].data; } } int main() { hbtnode *ha; char data[8]={'a','b','c','d','e','f','g','h'}; int weight[8]={5,29,7,8,14,23,3,11}; ha=(hbtnode *)malloc(16*sizeof(hbtnode)); creathbtnode(data,weight,ha,8); translation(ha,8); return 0; } /***************** #include<iostream> #include<string.h> using namespace std; int main() { char a[100]; int len,i=0; cin>>a; len=strlen(a); while(i<len) { if(a[i]=='0') { i++; if(a[i]=='0') { i++; if(a[i]=='0') { i++; if(a[i]=='0') cout<<"g"; else cout<<"a"; } else cout<<"h"; } else cout<<"f"; } else { i++; if(a[i]=='0') cout<<"b"; else { i++; if(a[i]=='0') cout<<"e"; else { i++; if(a[i]=='0') cout<<"c"; else cout<<"d"; } } } i++; } return 0; } /* 0001 a 10 b 1110 c 1111 d 110 e 01 f 0000 g 001 h */ } /****************** #include<stdio.h> #include<string.h> char a[]="0001"; char b[]="10"; char c[]="1110"; char d[]="1111"; char e[]="110"; char f[]="01"; char g[]="0000"; char h[]="001"; int main() { char str[100]; int k; char *p; scanf("%s",str); p=str; while(p[0]!='\0') { k=0; switch(p[0]){ case '0':switch(p[1]){ case '1':printf("f");k++;break; case '0':switch(p[2]){ case '1':printf("h");k++;break; case '0':switch(p[3]){ case '0':printf("g");k++;break; case '1':printf("a");k++;break; }k++;break; } k++;break; }k++;break; case '1':switch(p[1]){ case '0':printf("b");k++;break; case '1':switch(p[2]){ case '0':printf("e");k++;break; case '1':switch(p[3]){ case '0':printf("c");k++;break; case '1':printf("d");k++;break; }k++;break; }k++;break; }k++;break; } p=p+k; } return 0; } /***************** #include <iostream> #include <stdio.h> #include <string.h> using namespace std; typedef struct node { char data; struct node* lchild; struct node* rchild; }BT; int main() { int T1,T2; int i,j; cin>>T1; char str[100]; BT *root = new BT; root->lchild = root->rchild = NULL; getchar(); for(i=0;i<T1;i++) { char st[100]; cin>>str>>st; BT *p = root; for(j=0;j<strlen(st);j++) { if(st[j]=='0') { if(p->lchild==NULL) { p->lchild = new BT; p->lchild->lchild = p->lchild->rchild = NULL; } p=p->lchild; } else { if(p->rchild==NULL) { p->rchild = new BT; p->rchild->lchild = p->rchild->rchild = NULL; } p=p->rchild; } } p->data = str[0]; //叶结点 } cin>>T2; for(i=0;i<T2;i++) { cin>>str; BT *p = root; for(j=0;j<strlen(str);j++) { if(str[j]=='0') p = p->lchild; else p = p->rchild; if(p->lchild==NULL && p->rchild==NULL) { cout<<p->data; p = root; } } printf("\r\n"); } return 0; }