题解 第三章排序与查找| #找位置#

法1:

使用了哈希表

参考这一篇文章:https://blog.nowcoder.net/n/9bdf2f93480045b6810453b39196260b

哈希表不一定要是链表形式,也可能是用一个数组结构存放

#include <stdio.h>

//ASCII码一共128位
//0-9是48-57
//A-Z是65-90
//a-z是97-122

typedef struct CharTable
{
    int Num;
    int Place[15];
}CharTable;
//哈希表的结构,其中Place中装入有各个字符的位置

//哈希表也不一定要用链表的形式
//比如此处Table中的每一块内
//只用存放该字母首次出现的位置
int main()
{
    CharTable myCharTable[128];
    
    //定义了这样一个哈希表后,需要将其清零
    //使用memset函数
    //void *memset(void* s,int ch,size);
    //memset(myCharTable,0,128*sizeof(CharTable));
    memset(myCharTable,0,sizeof(myCharTable));
    //使用sizeof可以返回该数组的内存占有长度
    
    
    //将现有数据输入
    char C;
    int order=0,tmp;
    while(scanf("%c",&C)!=EOF)
    {
        tmp=myCharTable[C].Num++;
        myCharTable[C].Place[tmp]=order;
        order++;
    }
    
    //得到输出的顺序,得到有几个数字
    char Rank[order];
    memset(Rank,0,sizeof(Rank));
    for(int i=0;i<128;i++)
    {
        if(myCharTable[i].Num!=0)
            Rank[myCharTable[i].Place[0]]=(char)i;
    }//在Rank中存入了每一个字符的出现先后次序
    //有的多余的地方是存了0,这些都是要舍去的
    
    //按顺序,将hash表中的所有的结果输出
    int presChar;
    for(int i=0;i<sizeof(Rank);i++)
    {
        presChar=Rank[i];
        if(myCharTable[presChar].Num>1)
        {
            for(int j=0;j<myCharTable[presChar].Num-1;j++)
            {
                printf("%c:%d,",(char)presChar,myCharTable[presChar].Place[j]);
            }
            printf("%c:%d\n",(char)presChar,myCharTable[presChar].Place[myCharTable[presChar].Num-1]);
            //这里是防止最后多打了一个逗号
        }
    }
    
    return 0;
}