【数据结构】用Hash方法统计数字出现次数

前端之家收集整理的这篇文章主要介绍了【数据结构】用Hash方法统计数字出现次数前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题源:北航6系数据结构作业


【问题描述】

用HASH方法统计整数出现的次数


【输入形式】

以逗号分隔,#结尾的整数
输出形式】

等式。左侧为排序好的整数,右侧为其出现的次数


【样例输入】

2,6,7,13,18,3,1,7#

【样例输出

1=1

2=1

3=2

6=2

7=2

13=1

18=1



一开始用的是比较简单的Hash函数 hash(k) = k

这样的话存在一个问题就是数组要开很大的,遇到比如{1,1kW, 1E}这样就浪费了很多空间

#include <stdio.h>

int main() {

    int i;
    int d;
    char c;
    int MAX_NUM = 0;
    int a[1000] = {0};

    while (1) {
        scanf("%d%c",&d,&c );

        if ( d > MAX_NUM)
            MAX_NUM = d;
        a[d]++;

        if( c == '#')
            break;
    }

    for ( i = 0; i <= MAX_NUM; i++){
        if( a[i] > 0 )
            printf("%d=%d\n",i,a[i]);
    }

    return 0;
}


然后改用的是链式结构的hash表,这样就极大的节约了空间


用一个链表按序存储输入的数字,这样的时间复杂度是O(n),然后用了一个指针数组来存放每个数字的值和出现的次数

H(k)= k mod 10;


此处有个考虑不周到的地方是忘记释放链表的内存了


#include <stdio.h>
#include <stdlib.h>


typedef struct Node {

    int num;
    int time;
   // int mark;
    struct Node *link;
} HNode,*HLink;

typedef struct Node1 {

    int num;
    struct Node1 *link;
} NumNode,*NumLink;

int main() {

    char c = '0';
    int hNum;
    int i;
    HLink bucket[10],p,q,r;
    NumLink head,s,t,w;

    for( i = 0; i < 10; i++) {
        //bucket[i]->link = NULL;
        p = (HLink)malloc(sizeof(HNode));
        p->link = NULL;
        bucket[i] = p;
        //bucket[i]->mark = 0;
    }

    head = (NumLink)malloc(sizeof(NumNode));
    head->link = NULL;


    do {

        scanf("%d%c",&hNum,&c);

        //printf("%d ",hNum);

        if( head->link == NULL ) {
            s = (NumLink)malloc(sizeof(NumNode));
            s->num = hNum;
            s->link = NULL;
            head->link =s;
        }

        else {

            t = head->link;
            while( t != NULL ) {

                if( t->num == hNum ) {
                    break;
                }

                t = t->link;
            }

            if( t == NULL ) {

                s = (NumLink)malloc(sizeof(NumNode));
                s->num = hNum;
                s->link = NULL;

                t = head->link;
                while( t != NULL ) {

                    if ( t->num > hNum )
                        break;

                    w = t;
                    t = t->link;
                }

                if( t == head->link ) {
                    head->link = s;
                    s->link = t;
                }

                else {
                    w->link = s;
                    s->link = t;
                }

            }

        }


        if ( bucket[hNum%10]->link == NULL ) {
            p = (HLink)malloc(sizeof(HNode));
            p->num = hNum;
            p->time = 1;
           // p->mark = 0;
            p->link = NULL;
            bucket[hNum%10]->link = p;
        }

        else {

            p =  bucket[hNum%10]->link;
            while ( p != NULL ) {

                if( p->num == hNum ) {
                    p->time++;
                    break;
                }

                r = p;
                p = p->link;

            }

            if ( p == NULL ) {

                q = (HLink)malloc(sizeof(HNode));
                q->num = hNum;
                q->time = 1;
                //q->mark = 0;
                q->link = NULL;
                r ->link = q;

            }

        }



        //if( c == '#')
          //  break;

    } while( c != '#');

    t = head->link;




    while( t != NULL ) {
        //printf("%d",t->num);
        p = bucket[(t->num)%10]->link;
        while ( p != NULL ) {

            if ( p->num == t->num ) {
                printf("%d=%d\n",p->num,p->time);
                break;
            }

            p = p->link;

        }

        t = t->link;
    }

    return 0;
}
原文链接:https://www.f2er.com/datastructure/382565.html

猜你在找的数据结构相关文章