typedef struct Topt {

	int times;

	char c[MAX];

}Topt, *Topten;

int Traverse_Topten (Node p, char *a, int i, struct  Topt * top) {

	int k, t;

	Node q=p;

	if (p->times!=0) {					//所在单词出现频率不为零则输出该单词

		if (p->times<top[8]->times && p->times>=top[9]->times) {

			top[9]->times=p->times;

			top[9]->c[]={"\0"};

			strncpy(top[9]->c,a,i-1);

		}

		else

			for (k=0;k<9;k++)

				if (p->times>=top[k].times) {

					for (t=8;t>=k;t--) {

						top[t+1]->times=top[t]->times;

						top[t+1]->c[]={"\0"};

						strcpy(top[t+1]->c,top[t]->c);

					}

					top[k]->times=p->times;

					top[k]->c[]={"\0"};

					strncpy(top[k]->c,a,i-1);

				}

		//for (k=0;k<i;k++) fprintf(fq,"%c",a[k]);

		//fprintf(fq,"\n");

	}

	if (p->next[0]=='\0') return 0;		//已到达字典序叶子节点，返回

	else							//未到达字典序叶子节点，继续向下检索

		for (k=0;p->next[k]!='\0';k++) {

				q=p;

				a[i++]=p->next[k]->ch;

				p=p->next[k];

				Traverse_Topten (p,a,i,top);		//递归

				p=q;

		}

	return 0;

}



void PrefixFrequence (Node Root, FILE *fp, FILE *fq) {

	int id=1, i, j, k, t, tag;

	Node p, q;

	char a[MAX] = {'\0'}, b;

	struct Topt * top[10];

	for (k=0;k<10;k++) {			//初始化数组

		top[k]=(Topten)malloc(sizeof(Topt));

		top[k]->times=0;

		top[k]->char[]={"\0"};

	}

	while (1) {

		for (i=0;i<MAX;i++) {		//一次读入文件中给定的前缀

			b = fgetc(fp);

			if (b==10 || b==EOF) break;

			else a[i] = b;

		}

		if (i!=0) fprintf(fq, "CASE %d:\n",id++);	//输出单词的ID号

		j=0; p=Root; tag=1;

		while(j<i) {

			for (k=0;k<MAX;k++) {

				if(p->next[k]=='\0') {tag=0;break;}

				else if (p->next[k]->ch==a[j]) {q=p;p=p->next[k];break;}

				else continue;

			}

			if (tag==0) break;			//没有该前缀的单词

			j++;

		}

		if (tag!=0 && i!=0) {		//在字典中找出优先级最高的十个符合前缀的单词

			Traverse_Topten(p,a,i,top);

			k=0;

			while(top[k]->times!=0) {

				for (t=0;top[k]->c[t]!='\0';t++)	fprintf(fq,"%c",top[k]->c[t]);

				fprintf(fq,"\n");

				k++;

				if (k>9) break;

			}

		}

		if (b == EOF) break;

	}

}