请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。
所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。

输入格式:

输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。

输出格式:

在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。

随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。

输入样例：

This is a test.

The word "this" is the word with the highest frequency.

Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee.  But this_8 is different than this, and this, and this...#
this line should be ignored.

输出样例：（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）

23
5:this
4:is

参考代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<stdbool.h>

#define MAXTABLESIZE 110  //允许开辟的最大散列表长度

typedef char elementType[16]; //关键词类型用字符串
typedef struct listNode *list;//单链表
struct listNode{
           //链表结点定义
    elementType data;  //存放单词
    int count;         //单词个数
    list next;         //结点指针
};

typedef struct tableNode *hashTable;//散列表类型
struct tableNode{
        //散列表结点定义
    int tableSize;   //表的最大长度
    list heads;      //指向链表头结点的数组
};

typedef struct{
           //结构数组
    elementType data; //存放单词
    int count;        //单词个数
}wordFre;

/*函数声明*/
int nextPrime(int n);//大于n的最小素数
hashTable createTable(int tableSize);//建立散列表
int hash(const char *key,int tableSize);//散列函数
list find(hashTable H,elementType key); //查找
void insert(hashTable H,elementType key);//插入
void destroyTable(hashTable H); //释放空间
bool isLower(char ch); //是否是小写字母
bool isUpper(char ch); //是否是大写字母
bool isDigit(char ch); //是否是数字
void show(hashTable H);//输出
void swap(wordFre *wf1,wordFre *wf2);//结构体数据交换

int main()
{
    
    hashTable H;
    H=createTable(100);
    char ch,str[16]={
    0};
    int i=0,flag=0;
    while((ch=getchar())!='#') //读到#结束
    {
    
        /*如果是小写字母或者数字或者下划线*/
        if(isLower(ch)||isDigit(ch)||ch=='_')
        {
    
            flag=1;
            if(i<15)
                str[i++]=ch;
        }
        /*如果是大写字母转换成小写*/
        else if(isUpper(ch))
        {
    
            flag=1;
            if(i<15)
                str[i++]=ch+32;
        }
        /*否则是单词分隔符*/
        else
        {
    
            if(flag)
            {
    
                str[i]=0;
                insert(H,str);
                i=flag=0;
            }
        }
    }
    if(flag)//最后一个单词处理
    {
    
        str[i]=0;
        insert(H,str);
    }
    show(H);
    destroyTable(H);
    system("pause");
    return 0;
}

int nextPrime(int n)
{
    
    int i,flag=1,p=(n%2)?n+2:n+1;
    while(p<=MAXTABLESIZE)
    {
    
        for(i=2;i<=sqrt(p);i++)
        {
    
            if(p%2==0)
            {
    
                flag=0;
                break;
            }
        }
        if(flag) break;
        else p+=2;
    }
    return p;
}

hashTable createTable(int tableSize)//建立散列表
{
    
    hashTable H;
    int i;
    H=(hashTable)malloc(sizeof(struct tableNode));
    H->tableSize=nextPrime(tableSize);//保证散列表最大长度是素数
    H->heads=(list)malloc(H->tableSize*sizeof(struct listNode));//分配链表头结点数组
    for(i=0;i<H->tableSize;i++) //初始化表头结点
    {
    
        H->heads[i].data[0]='\0';
        H->heads[i].count=0;
        H->heads[i].next=NULL;
    }
    return H;
}

int hash(const char *key,int tableSize)//散列函数
{
    
    unsigned h=0;  //散列函数值，初始化为0
    while(*key!='\0')//位移映射
    {
    
        h=(h<<5)+*key;
        key++;
    }
    return h%tableSize;
}

list find(hashTable H,elementType key)
{
    
    list p;
    int pos=hash(key,H->tableSize);//初始散列位置
    p=H->heads[pos].next; //从该链表的第1个结点开始
    while(p&&strcmp(p->data,key))//当未到表尾，并且key未找到时
    {
    
        p=p->next;
    }
    return p; //此时p或者指向找到的结点，或者为NULL
}

void insert(hashTable H,elementType key)
{
    
    list p,newCell;
    int pos;
    p=find(H,key);
    if(!p) //单词未找到，可以插入
    {
    
        newCell=(list)malloc(sizeof(struct listNode));
        strcpy(newCell->data,key);
        newCell->count=1; //第一次插入，设置单词数为1
        pos=hash(key,H->tableSize);
        /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
        newCell->next=H->heads[pos].next;
        H->heads[pos].next=newCell;
    }
    else //单词已存在
    {
    
        p->count++; //单词数加1
    }
}

void destroyTable(hashTable H)
{
    
    int i;
    list p,tmp;
    /* 释放每个链表的结点 */
    for(i=0;i<H->tableSize;i++)
    {
    
        p=H->heads[i].next;
        while(p)
        {
    
            tmp=p->next;
            free(p);
            p=tmp;
        }
    }
    free(H->heads); //释放头结点数组
    free(H);        //释放散列表结点
}

bool isLower(char ch)
{
    
    if(ch>='a'&&ch<='z')
        return true;
    else
        return false;
}

bool isUpper(char ch)
{
    
    if(ch>='A'&&ch<='Z')
        return true;
    else
        return false;
}

bool isDigit(char ch)
{
    
    if(ch>='0'&&ch<='9')
        return true;
    else
        return false;
}

void show(hashTable H)
{
    
    wordFre wf[10000];//定义一个结构数组，用来存储单词和个数
    /*wordCount表示单词总数,outputWordCount表示需要输出的单词个数*/
    int i,j,flag,wordCount=0,outputWordCount;
  //  int t1;
  //  elementType t2;
    list p;
    /*遍历散列表，将单词及个数放入结构数组中，并统计单词总数*/
    for(i=0;i<H->tableSize;i++)
    {
    
        p=H->heads[i].next;
        while(p)
        {
    
            wf[wordCount].count=p->count;
            strcpy(wf[wordCount].data,p->data);
            wordCount++;
            p=p->next;
        }
    }
    outputWordCount=wordCount/10;//求出需要输出的单词个数
    printf("%d\n",wordCount); //输出单词总个数
    /*冒泡排序*/
    for(i=0;i<wordCount-1;i++)
    {
    
        flag=0;
        for(j=wordCount-1;j>i;j--) //一次冒泡
        {
    
            /*词频不同交换*/
            if(wf[j-1].count<wf[j].count)
            {
    
                swap(&wf[j-1],&wf[j]);
                flag=1;
            }
            /*词频相同，字典序不同交换*/
            else if(wf[j-1].count==wf[j].count&&strcmp(wf[j-1].data,wf[j].data)>0)
            {
    
                swap(&wf[j-1],&wf[j]);
                flag=1;
            }
        }
        if(flag==0) break;//全程无交换
    }
    for(i=0;i<outputWordCount;i++)
    {
    
        printf("%d:%s\n",wf[i].count,wf[i].data);
    }
}

void swap(wordFre *wf1,wordFre *wf2)
{
    
    int t1;
    elementType t2;
    t1=wf1->count;
    wf1->count=wf2->count;
    wf2->count=t1;
    strcpy(t2,wf1->data);
    strcpy(wf1->data,wf2->data);
    strcpy(wf2->data,t2);
}

思路：

1. 构造链式散列表；
2. 将单词插入表中（如果单词存在，单词数加1）；
3. 遍历散列表，将链表结点数据复制到结构数组中，并统计单词总数；
4. 对结构数组用冒泡排序，按照词频逆序、字典序顺序排列；
5. 输出词频最大的前10%的单词。
   以上几点是这题我的思路，虽然测试点均通过，但是算法复杂度比较高，排序那里思路感觉不是很好，后面有更好的思路再去做修改。