189 8069 5689
#ifndef H_STUDENT_HH
创新互联自2013年创立以来，先为十堰郧阳等服务建站，十堰郧阳等地企业，进行企业商务咨询服务。为十堰郧阳企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
#define H_STUDENT_HH
#include "stdio.h"
#include "string.h"枣知友
#include "malloc.h"
#define LEN sizeof(struct message_student) /*一个结构体数组元素的长度*/
#define numsubs 5 /*学科数目*/
typedef struct message_student /*结构体定义猛蔽*/
{
char number[6];
char name[20];
char sex[4];
float subject[numsubs];
float score;
float average;
int index;
}student;
extern int numstus; /*学生数目*/
extern student *pointer; /*指向结构体数组*/
extern int lens;
int menu_select(); /*函数声明*/
int openfile(student stu[]);
int findrecord(student stud[]);
int writetotext(student stud[]);
void welcome();
void display1();
void showtable();
void sort(student stu[]);
void deleterecord(student stu[],int i);
void addrecord(student stud[]);
void display(student stud[],int n1,int n2);
void amendrecord(student stud[]);
void count(student stud[]);
void sortnum(student stud[]);
void sortnum2(student stud[]);
void sortname(student stud[]);
void sortname2(student stud[]);
void sortcount(student stud[]);
void sortcount2(student stud[]);
void statistic(student stud[]);
void display1();
#endif
//#include "head.h"
int menu_select()
{
char c;
printf("\n\n");
printf(" | 1. 增加学生记录 5.统计信息 |\n");
printf(" | 2. 查询学生记录 6.打开文件 |\n");
printf(" | 3. 修改学生记录 7.保存文件 |\n");
printf(" | 4. 学生纪录排序 8.显示记录 |\n");
printf(" | 0.退出系统 |\n");
printf("\n\n");
printf("请选择(0-8):");
c=getchar();
getchar();
return (c-'0');
}
//#include "head.h"
int findrecord(student stud[]) /*查找信息*/
{
char str[2];
int i,num;
if(numstus==0)
{
printf("没有可被查找的凳槐记录\n");
return -1;
}
else
{
printf("以何种方式查找？\n1.学号\t2.姓名\t3.名次\n");
gets(str);
if(str[0]=='1') /*按学号查找*/
{
printf("请输入学号:");
gets(str);
for(i=0;i=numstus;i++)
if(strcmp(str,stud[i].number)==0)
{
display(stud,i,i);
break;
}
else continue;
}
else if(str[0]=='2') /*按姓名查找*/
{
printf("请输入姓名:");
gets(str);
for(i=0;i=numstus;i++)
if(strcmp(str,stud[i].name)==0)
{
display(stud,i,i);
break;
}
else continue;
}
else if(str[0]=='3') /*按名次查找*/
{
printf("请输入名次:");
scanf("%d",num);
getchar();
for(i=0;i=numstus;i++)
if(num==stud[i].index)
{
display(stud,i,i);
break;
}
else continue;
}
if(inumstus)
{
printf("没有查找所要的信息。\n");
return -1;
}
return i;
}
}
//#include"head.h"
int openfile(student stu[])
{
int i=0,j;
FILE *fp;
char filename[20],str[2];
if(numstus!=0)
{
printf("已经有记录存在，是否保存?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y')
writetotext(stu);
}
printf("请输入文件名:");
gets(filename);
numstus=0;
if((fp=fopen(filename,"rb+"))==NULL)
{
printf("无法打开该文件\n");
return(-1);
}
fscanf(fp,"%d",numstus);
fgetc(fp);
while(inumstus)
{
fscanf(fp,"%s",stu[i].number);
fscanf(fp,"%s",stu[i].name);
fscanf(fp,"%s",stu[i].sex);
for(j=0;jnumsubs;j++)
fscanf(fp,"%f",stu[i].subject[j]);
fscanf(fp,"%f",stu[i].score);
fscanf(fp,"%f",stu[i].average);
fscanf(fp,"%d",stu[i].index);
i++;
}
fclose(fp);
printf("文件读取成功\n");
printf("是否显示纪录?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y')
display(stu,0,numstus-1);
return(0);
}
//#include "head.h"
void sort(student stud[])
{
int i,j=0;
char str[5];
student *p;
p=stud;
if(numstus==0)
{
printf("没有可供查询的记录!");
}
while(1)
{
for(i=0i++)
{
printf(" 请输入查询方式:");
printf("（直接输入回车则结束查询操作）\n");
printf("1.按照学号\t");
printf("2.按照姓名\t");
printf("3.按照名次\n");
gets(str);
if(strlen(str)==0) break;
if(str[0]=='1')
{
printf("请输入排序次序：\n");
printf("1.升序排列\t");
printf("2.降序排列\n");
gets(str);
if(str[0]=='1')
sortnum2(p);
else
sortnum(p);
display(stud,0,numstus-1);
}
else if(str[0]=='2')
{
printf("请输入排序次序：\n");
printf("1.升序排列\t");
printf("2.降序排列\n");
gets(str);
if(str[0]=='1')
sortname2(p);
else
sortname(p);
display(stud,0,numstus-1);
}
else if(str[0]=='3')
{
printf("请输入排序次序：\n");
printf("1.升序排列\t");
printf("2.降序排列\n");
gets(str);
if(str[0]=='1')
sortcount2(p);
else
sortcount(p);
display(stud,0,numstus-1);
}
else printf("请输入1~3");
printf("是否退出排序?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y') break;
}
return;
}
}
void sortnum(student stud[])
{
int i,j;
student temp;
student *p;
p=stud;
for(i=0;inumstus;i++)
for(j=0;jnumstus-i-1;j++)
{
if(strcmp(stud[j+1].number,stud[j].number)0)
{
temp=*(p+j);
*(p+j)=*(p+j+1);
*(p+j+1)=temp;
}
}
}
void sortnum2(student stud[])
{
int i,j;
student temp;
student *p;
p=stud;
for(i=0;inumstus;i++)
for(j=0;jnumstus-i-1;j++)
{
if(strcmp(stud[j].number,stud[j+1].number)0)
{
temp=*(p+j);
*(p+j)=*(p+j+1);
*(p+j+1)=temp;
}
}
}
void sortname(student stud[])
{
int i,j;
student temp;
student *p;
p=stud;
for(i=0;inumstus;i++)
for(j=0;jnumstus-i-1;j++)
{
if(strcmp(stud[j+1].name,stud[j].name)0)
{
temp=*(p+j);
*(p+j)=*(p+j+1);
*(p+j+1)=temp;
}
}
}
void sortname2(student stud[])
{
int i,j;
student temp;
student *p;
p=stud;
for(i=0;inumstus;i++)
for(j=0;jnumstus-i-1;j++)
{
if(strcmp(stud[j].name,stud[j+1].name)0)
{
temp=*(p+j);
*(p+j)=*(p+j+1);
*(p+j+1)=temp;
}
}
}
void sortcount(student stud[])
{
int i,j;
student temp;
student *p;
p=stud;
for(i=0;inumstus;i++)
for(j=0;jnumstus-i-1;j++)
{
if(stud[j+1].indexstud[j].index)
{
temp=*(p+j);
*(p+j)=*(p+j+1);
*(p+j+1)=temp;
}
}
}
void sortcount2(student stud[])
{
int i,j;
student temp;
student *p;
p=stud;
for(i=0;inumstus;i++)
for(j=0;jnumstus-i-1;j++)
{
if(stud[j].indexstud[j+1].index)
{
temp=*(p+j);
*(p+j)=*(p+j+1);
*(p+j+1)=temp;
}
}
}
//#include"head.h"
void statistic(student stud[]) /*新增功能，输出统计信息*/
{
int i,j=0,k=0;
char c1,str[2];
float average[numsubs],sum=0;
if(numstus==0)
printf("没有可被查找的记录\n");
else
{
while(1)
{
printf("下面将统计考试成绩\n");
printf("请选择你要统计哪科的成绩 1.A\t2.B\t3.C\t4.D\t5.E\n");
c1=getchar();
printf("\t一共有个%d记录\n",numstus); /*总共记录数*/
switch(c1)
{
case '1':
for(i=0;inumstus;i++) /*循环输入判断*/
{
sum+=stud[i].subject[0];
if(stud[k].subject[0]stud[i].subject[0]) k=i;
if(stud[j].subject[0]stud[i].subject[0]) j=i;
}
average[0]=sum/numstus;
printf("\t科目A的最高分:\n"); /*最高分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[j].number,stud[j].name,stud[j].subject[0]);
printf("\t科目A的最低分是:\n"); /*最低分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[k].number,stud[k].name,stud[k].subject[0]);
printf("\t科目A的平均分是 %5.2f\n",average[0]); /*平均分*/
break;
case '2':
for(i=0;inumstus;i++) /*循环输入判断*/
{
sum+=stud[i].subject[1];
if(stud[k].subject[1]stud[i].subject[1]) k=i;
if(stud[j].subject[1]stud[i].subject[1]) j=i;
}
average[1]=sum/numstus;
printf("\t科目B的最高分:\n"); /*最高分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[j].number,stud[j].name,stud[j].subject[1]);
printf("\t科目B的最低分是:\n"); /*最低分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[k].number,stud[k].name,stud[k].subject[1]);
printf("\t科目B的平均分是 %5.2f\n",average[1]); /*平均分*/
break;
case '3':
for(i=0;inumstus;i++) /*循环输入判断*/
{
sum+=stud[i].subject[2];
if(stud[k].subject[2]stud[i].subject[2]) k=i;
if(stud[j].subject[2]stud[i].subject[2]) j=i;
}
average[2]=sum/numstus;
printf("\t科目C的最高分:\n"); /*最高分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[j].number,stud[j].name,stud[j].subject[2]);
printf("\t科目C的最低分是:\n"); /*最低分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[k].number,stud[k].name,stud[k].subject[2]);
printf("\t科目C的平均分是 %5.2f\n",average[2]); /*平均分*/
break;
case '4':
for(i=0;inumstus;i++) /*循环输入判断*/
{
sum+=stud[i].subject[3];
if(stud[k].subject[3]stud[i].subject[3]) k=i;
if(stud[j].subject[3]stud[i].subject[3]) j=i;
}
average[3]=sum/numstus;
printf("\t科目D的最高分:\n"); /*最高分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[j].number,stud[j].name,stud[j].subject[3]);
printf("\t科目D的最低分是:\n"); /*最低分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[k].number,stud[k].name,stud[k].subject[3]);
printf("\t科目D的平均分是 %5.2f\n",average[3]); /*平均分*/
break;
case '5':
for(i=0;inumstus;i++) /*循环输入判断*/
{
sum+=stud[i].subject[4];
if(stud[k].subject[4]stud[i].subject[4]) k=i;
if(stud[j].subject[4]stud[i].subject[4]) j=i;
}
average[4]=sum/numstus;
printf("\t科目E的最高分:\n"); /*最高分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[j].number,stud[j].name,stud[j].subject[4]);
printf("\t科目E的最低分是:\n"); /*最低分*/
printf("\t\t学号:%s 姓名:%s 分数:%.2f\n",stud[k].number,stud[k].name,stud[k].subject[4]);
printf("\t科目E的平均分是 %5.2f\n",average[4]); /*平均分*/
break;
default:printf("输入错误！请输入1~5之间的数\n");
}
sum=0;
getchar();
printf("是否继续进行统计?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y') ;
else break;
}
}
}
int writetotext(student stud[]) /*将所有记录写入文件*/
{
int i=0,j;
FILE *fp;
char filename[20];
printf("输入文件名称:");
gets(filename);
fp=fopen(filename,"w");
fprintf(fp,"%d\n",numstus);
while(inumstus)
{
fprintf(fp,"%s %s %s ",stud[i].number,stud[i].name,stud[i].sex);
for(j=0;jnumsubs;j++)
fprintf(fp,"%f ",stud[i].subject[j]);
fprintf(fp,"%f %f %d ",stud[i].score,stud[i].average,stud[i].index);
i++;
}
fclose(fp);
printf("已成功存储!\n");
display(stud,0,numstus-1);
numstus=0;
return 0;
}
void welcome()
{
printf("\t*************************************************************\n");
printf("\t\t\t\t这是一个学生成绩管理系统\n\t\t\t\t 倾情奉献 欢迎使用!\n");
printf("\t*************************************************************\n");
}
void showtable()
{
printf("---------------------------------------------------------------------------------------\n");
printf("学号\t姓名\t性别\tA\tB\tC\tD\tE\t总分\t平均分\t名次\n");
printf("---------------------------------------------------------------------------------------\n");
}
void display(student stud[],int n1,int n2)
{
int i;
showtable(); /*显示表头*/
for(i=n1;i=n2;i++)
printf("%s\t%s\t%s\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%.2f\t%d\t\n",stud[i].number,stud[i].name,stud[i].sex,stud[i].subject[0],stud[i].subject[1],stud[i].subject[2],stud[i].subject[3],stud[i].subject[4],stud[i].score,stud[i].average,stud[i].index);
/*通过循环输出数据*/
}
void display1()
{
printf("\t\t本系统由计应精英一组亲情制作\n\n");
printf("\t\t制作人员列表: (按比划)\n");
printf("\t\t王庆斌\t\t\t张威\n\t\t李智\t\t\t周在峰\n\t\t杨凯\t\t\t胡杨\n");
printf("\n\n");
getchar();
}
#includestring.h
void amendrecord(student stud[])
{
char str[5]; /*供用户输入*/
int i=-1,j;
if(numstus==0) /*没有记录返回*/
printf("没有可供修改的记录！");
while(i0)
{
i=findrecord(stud);
if(i=0)
{
printf("要删除这个学生的信息吗?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y')
{
deleterecord(stud,i);
count(stud);
}
else
{
printf("确定要修改这个学生的信息吗?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y')
{
printf("下面请重新输入学生的信息:\n");
printf("请输入学号:");
gets(stud[i].number);
printf("请输入姓名:");
gets(stud[i].name);
printf("请输入性别(男/女 1/0):");
gets(str);
if(str[0]=='0')
strcpy(stud[i].sex,"女");
else
strcpy(stud[i].sex,"男");
stud[i].score=0;
printf("请按顺序输入成绩:");
for(j=0;jnumsubs;j++)
{
scanf("%f",stud[i].subject[j]);
stud[i].score+=stud[i].subject[j];
}
getchar();
stud[i].average=stud[i].score/numsubs;
}
count(stud);
}
display(stud,0,numstus-1);
}
printf("是否继续进行其他修改?(y/n)\n");
gets(str);
if(str[0]=='y'||str[0]=='Y')
i=-1;
else i=1;
}
}
void deleterecord(student stu[],int i) /*删除信息*/
{
int j;
while(i=0)
{
for(j=i;jnumstus;j++)
stu[j]=stu[j+1];
numstus--;
printf("删除成功!\n");
}
}
void count(student stud[])
{
int i,j;
for(i=0;inumstus;i++)
{
stud[i].index=1;
for(j=0;jnumstus;j++)
if(stud[j].scorestud[i].score)
stud[i].index++;
}
}
void addrecord(student stud[])
{
int i=0,j,num;
char str[5];
if(numstus!=0)
{
printf("已有记录存在是否覆盖?(y/n)\n");
gets(str);
if(str[0]=='Y'||str[0]=='y')
i=0;
else i=numstus;
}
printf("请输入增加的学生信息条目数:");
scanf("%d",num);
if(i==0)
numstus=num;
else numstus+=num;
if(numstuslens)
{
lens+=50;
pointer=(student *)realloc(pointer,lens*LEN);
}
printf("请输入学生信息:\n");
for(;inumstus;i++)
{
getchar();
printf("请输入学号:");
gets(pointer[i].number);
printf("请输入姓名:");
gets(pointer[i].name);
printf("请输入性别(男/女 1/0):");
gets(pointer[i].sex);
if(pointer[i].sex[0]=='0') strcpy(pointer[i].sex,"女");
else strcpy(pointer[i].sex,"男");
printf("请输入各科成绩:(按ABCDE的顺序):");
stud[i].score=0;
for(j=0;jnumsubs;j++)
{
scanf("%f",stud[i].subject[j]); /*计算总分*/
stud[i].score+=stud[i].subject[j];
}
stud[i].average=stud[i].score/numsubs; /*计算平均分*/
}
count(stud); /*附名次*/
display(stud,0,numstus-1);
getchar();
}
int numstus;
int lens;
student *pointer;
void main()
{
int i=1;
char str[2];
lens=100;
pointer=(student *)malloc(lens*LEN); /*分配内存*/
numstus=0;
welcome(); /*欢迎界面*/
while(i0)
{
i=menu_select(); /*控制菜单*/
switch(i)
{
case 1:addrecord(pointer);break; /*增加学生信息*/
case 2:findrecord(pointer);break; /*查询学生信息*/
case 3:amendrecord(pointer);break; /*修改学生信息*/
case 4:sort(pointer);break; /*学生信息排序*/
case 5:statistic(pointer);break; /*统计信息*/
case 6:openfile(pointer);break; /*打开文件*/
case 7:writetotext(pointer);break; /*保存文件*/
case 8:display(pointer,0,numstus-1);break; /*显示记录*/
case 0:
if(numstus!=0) printf("是否保存当前记录?(y/n)");
gets(str);
if(str[0]=='y'||str[0]=='Y')
writetotext(pointer);
i=-1;break; /*退出系统*/
default:printf("请输入数字0~8:\n");i=1; /*输入错误*/
}
}
printf("\t\t欢迎再次使用本系统。\n\n");
display1();
}
int get_code_len(int index)
{
check();
if (index 0 || index = (int)code_lens.size())
throw new huffman_exception("参数非法歼耐");
return code_lens[index];
}
vectorint get_all_code_lens(void)
{
check();
return code_lens;
}
unsigned long get_code(int index)
{
check();
if (index 0 || index = (int)codes.size())
throw new huffman_exception("参数非法");
return codes[index];
}
vectorunsigned long get_all_codes(void)
{
check();
return codes;
}
string get_code_str(int index)
{
check();
if (index 0 || index = (int)codes.size())
throw new huffman_exception("参数非法");
return long_to_string(codes[index], code_lens[index]);
}
vectorstring get_all_code_strs(void)
{
check();
vectorstring v;
for(int i = 0; i (int)codes.size(); i++)
v.push_back(long_to_string(codes[i], code_lens[i]));
return v;
}
int find(unsigned long code)
{
check();
for(int i = 0; i (int)codes.size(); i++)
if (codes[i] == code)
return i;
return -1;
}
int find(const string code)
{
return find(string_to_long(code.c_str()));
}
inline void check()
{
if (codes.size() 罩改歼= 0)
throw new huffman_exception("尚未调用过generate_codes()");
}
unsigned long string_to_long(const char* code)
{
unsigned long ret = 0;
int len = (int)strlen(code);
for(int i = len - 1; i = 0; i--)
if (code[i] == '1')
ret |= (1ul (len - i - 1));
return ret;
}
string long_to_string(unsigned long code, int code_len)
{
char* buf = new char[code_len + 1];
if (buf == NULL)
throw new huffman_exception("no enough memory.");
memset(buf, 0, code_len + 1);
unsigned long bit = 1 (code_len - 1);
for(int i = 0; i code_len; i++)
{
if (code bit)
buf[i] = '1';
else
buf[i] = '0';
bit = 1;
}
string ret(buf); delete buf;
return ret;
}
void generate_canonical_codes()
{
if (code_lens.size() = 0)
throw new huffman_exception("生成Canonical Huffman编码前，应已知所有元物冲素码长");
int max_code_len = 0;
int min_code_len = 1000;
const int tmp = sizeof(unsigned long) * 8 + 1;
int len_count[tmp];
unsigned long min_code[tmp];
memset(len_count, 0, tmp * sizeof(int));
memset(min_code, 0, tmp * sizeof(unsigned long));
int num = (int)code_lens.size();
// 统计码长信息
for (int i = 0; i num; i++)
{
int codelen = code_lens[i];
// huffman_base用unsigned long存储编码，因此
// 码长要限制在sizeof(unsigned long)*8以内
// 这里对超长的编码都简单忽略掉了
if ((unsigned long)codelen sizeof(unsigned long)*8)
continue;
if (codelen max_code_len)
max_code_len = codelen;
if (codelen min_code_len)
min_code_len = codelen;
len_count[codelen]++;
}
// 计算特定码长的所有元素中最小的编码,这里使用的是
// Canonical Huffman编码规则,请参见相关文献
for (int i = max_code_len - 1; i = 0; i--)
min_code[i] = (min_code[i + 1] + len_count[i + 1]) 1;
// 已知特定码长的所有元素中最小的编码,同样码长的元素,
// 编码逐个加1就可以了
codes.clear();
for (int i = 0; i num; i++)
if (code_lens[i] 0 (unsigned long)code_lens[i] = sizeof(unsigned long)*8)
codes.push_back(min_code[code_lens[i]]++);
else
codes.push_back(0);
}
bool verify()
{
check();
int max = 0;
const int code_len_limit = 100; // 这里能检验的最大码长是100
int len_count[code_len_limit + 1];
memset(len_count, 0, sizeof(int)*(code_len_limit+1));
for(int i = 0; i (int)code_lens.size(); i++)
{
if (code_lens[i] code_len_limit)
return true; // 如果有超长码，就不检验了
len_count[code_lens[i]]++;
if (code_lens[i] max) max = code_lens[i];
}
// 从根开始，算每层分支结点数目，如果最后一层不为0，就表明Huffman树有错误
int nonleaf = 1;
for(int i = 1; i = max; i++)
nonleaf = nonleaf * 2 - len_count[i];
return (nonleaf == 0);
}
//主函数
void generate_codes(int num, const unsigned long* weights)
{
if (num = 1 || weights == NULL)
throw new huffman_exception("参数非法");
int heap_num, i, nonzero_count;
// 分配生成Huffman树时使用的堆结构,其大小是元素数目的2倍
unsigned long* heap = new unsigned long[2*num];
if (heap == NULL) throw new huffman_exception("内存不足");
// 将所有元素权值值(叶子结点)复制到堆的后半部分,堆的前半部分置0
memcpy(heap + num, weights, sizeof(unsigned long)*num);
memset((char *)heap, 0, num * sizeof (*heap));
// 将堆的前半部分视作指针,按顺序指向后半部分的叶子结点
// 同时统计权值非0的叶子结点数目
for (nonzero_count = i = 0; i num; i++)
if (heap[num + i])
heap[nonzero_count++] = num + i;
/* 将堆的前半部分视作指针,按照指针所指的权值大小,把堆的前半部分组织成为
堆排序(Heap Sort)算法中定义的"堆",即:堆对应一棵完全二叉树，且所有非叶
结点的值均不大于其子女的值，根结点的值是最小的.在这里,根结点是heap[0]
参见数据结构或算法书籍中的堆排序(Heap Sort)算法介绍 */
heap_num = nonzero_count;
for (i = heap_num / 2; i 0; i--)
{
register int curr, child;
curr = i;
child = curr * 2;
while (child = heap_num)
{
if (child heap_num heap[heap[child]] heap[heap[child - 1]])
child++;
if (heap[heap[curr - 1]] heap[heap[child - 1]])
{
register unsigned long temp;
temp = heap[child - 1];
heap[child - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = child;
child = 2 * curr;
}
else
break;
}
}
/* 创建Huffman树
这里,创建Huffman树的过程利用了堆排序(Heap Sort)算法的基本原理,即根结点是
最小的元素,树中最后一个元素是最大的元素.选出根结点后,把最后的元素调到根
结点,从树根到树叶,让最后的元素移动到合适的位置,重新建成堆.这样,总是可以
找出2个最小的子树,将这两个子树合并后,再作为新元素放到堆中.所有子树都合并
后,Huffman树就建成了.(参见数据结构或算法书籍中的堆排序算法介绍)
这一段代码的运行结果是整个heap数组成了一棵Huffman树,heap[0]未用,树根是
heap[1],其中保存所有权值值的总和, heap[2]..heap[num-1]对应于所有根以外
的分支结点,其中保存的是双亲结点的索引值, heap[num]..heap[num*2-1]对应于所
有叶子结点(即所有要编码的元素),其中保存的是双亲结点的索引值 */
/* 当用于堆排序的二叉树中还有结点时循环 */
while (heap_num 1)
{
int pos[2];
/* 循环2次,找出2个最小的子树,存入pos中 */
for (i = 0; i 2; i++)
{
register int curr, child;
/* 根结点就是最小的结点 */
pos[i] = heap[0];
/* 将最后的结点移动到根结点处,总结点数目减1 */
heap[0] = heap[--heap_num];
/* 以下是重建堆的过程 */
curr = 1;
child = 2;
while (child = heap_num)
{
if (child heap_num
heap[heap[child]] heap[heap[child - 1]])
child++;
if (heap[heap[curr - 1]] heap[heap[child - 1]])
{
register int temp;
temp = heap[child - 1];
heap[child - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = child;
child = 2 * curr;
}
else
break;
}
}
/* 合并子树,其结果作为新的结点放入堆中(但不在堆排序的二叉树内,实际
上,新加入的结点是和堆的后半段一起构成了Huffman树) */
heap[heap_num + 1] = heap[pos[0]] + heap[pos[1]];
/* 子树的左,右分支都指向子树的根结点 */
heap[pos[0]] = heap[pos[1]] = heap_num + 1;
/* 把子树根结点作为叶子结点，放到堆排序中的二叉树内 */
heap[heap_num] = heap_num + 1;
{
/* 在堆中,让新加入的叶子结点上升到合适的位置,不破坏堆的秩序 */
register int parent, curr;
heap_num++;
curr = heap_num;
parent = curr 1;
while (parent heap[heap[parent - 1]] heap[heap[curr - 1]])
{
register int temp;
temp = heap[parent - 1];
heap[parent - 1] = heap[curr - 1];
heap[curr - 1] = temp;
curr = parent;
parent = curr 1;
}
}
}
// 从根出发，求每个编码的码长
code_lens.clear();
heap[0] = (unsigned long)(-1l); // 双亲结点为0的叶子，可由此算得码长0
heap[1] = 0; // 根结点码长为0
for (i = 2; i 2*num; i++)
heap[i] = heap[heap[i]] + 1; // 结点码长等于双亲结点码长加1
for (i = num; i 2*num; i++)
code_lens.push_back(heap[i]);
// 由码长得到canonical huffman编码
generate_canonical_codes();
delete[] heap;
}
generate_codes()为主函数
还要改改,,,
#includestdio.h
#define L 100
int main(void)
{
char s1[2*L], s2[L], *p;
scanf("%s%s", s1, s2);
int i, j, off;
off=1;
for(i=0; s1[i]!='\0'; i++) {
p=s2;
if(s1[i]==*p)
for(j=i; *p!='\0'; j++) {
前销if(s1[j]!=*p) {
off=EOF;
break;
}
else
off=1;
皮悔棚 p++;
}
else
off=EOF;
if(off!=EOF) {
燃则 off=0;
i++;
printf("%d", i);
break;
}
}
if(off==EOF)
printf("s1中没有找到s2");
return 0;
}