数据结构实验：哈希表

忘是亡心i 2022-07-12 11:43 149阅读 0赞

think:  
1哈希表的建立需要注意映射关系的合理选择，自己开始时候将线性映射关系选择为10000，然后提交就一直超时，而且自己犯得错误很多，题目中说了如果有多个结果，输出数字最小的那个，自己昨晚没有注意，提交wrong answer，今天注意到之后又因为知识掌握不扎实，先是超时错误，又因为盲目修改数组大小，导致数组越界，其实哈希表的建立就像是一种大集合中小集合的模块化，结构体链表数组的很好使用，自己还有就是考虑如果是多组输入，那么如何将结构体数组指针初始化，一直还没想到解决方法，刚刚问了问鑫哥，可以重新用一个for循环将指针数组中的每个指针置空，或者用一个for循环重新为指针数组中的每个指针申请新的空间

数据结构实验：哈希表  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
在n个数中，找出出现次数最多那个数字，并且输出出现的次数。如果有多个结果，输出数字最小的那一个。

Input  
单组数据，第一行数字n（1<=n<=100000)。  
接下来有n个数字，每个数字不超过100000000

Output  
出现次数最多的数字和次数。

Example Input  
3  
1 1 2

Example Output  
1 2

Hint

Author  
cz

以下为accepted代码

#include <stdio.h>
    #include <stdlib.h>
    #define N 100
    long long book[100004];
    struct node
    {
        int Data;
        struct node *next;
    };
    struct node *a[1000004];
    
    void Inserst(long long n)
    {
        long long x = n/N;
        struct node *p = (struct node *)malloc(sizeof(struct node));
        p->Data = n;
        p->next = a[x];
        a[x] = p;
    }
    
    int  Find(long long n)
    {
        int cnt = 0;
        long long x = n/N;
        if(a[x] != NULL)
        {
            struct node *p;
            p = a[x];
            while(p != NULL)
            {
                if(p->Data == n)
                    cnt++;
                p = p->next;
            }
        }
        return cnt;
    }
    
    int main()
    {
        int n, i, x, max = -199859;
        scanf("%d", &n);
        {
            max = -199859;
            for(i = 0; i < n; i++)
            {
                scanf("%lld", &book[i]);
                Inserst(book[i]);
            }
            for(i = 0; i < n; i++)
            {
                if(Find(book[i]) > max || (Find(book[i]) == max && book[i] < x))
                {
                    max = Find(book[i]);
                    x = book[i];
                }
            }
            printf("%d %d\n", x, max);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 64ms
    Take Memory: 9432KB
    Submit time: 2017-02-22 18:51:47
    ****************************************************/

以下为time limit exceeded代码——映射关系过大

#include <stdio.h>
    #include <stdlib.h>
    #define N 100000
    long long book[100004];
    struct node
    {
        int Data;
        struct node *next;
    };
    struct node *a[100004];
    
    void Inserst(long long n)
    {
        long long x = n/N;
        struct node *p = (struct node *)malloc(sizeof(struct node));
        p->Data = n;
        p->next = a[x];
        a[x] = p;
    }
    
    int  Find(long long n)
    {
        int cnt = 0;
        long long x = n/N;
        if(a[x] != NULL)
        {
            struct node *p;
            p = a[x];
            while(p != NULL)
            {
                if(p->Data == n)
                    cnt++;
                p = p->next;
            }
        }
        return cnt;
    }
    
    int main()
    {
        int n, i, x, max = -199859;
        scanf("%d", &n);
        {
            max = -199859;
            for(i = 0; i < n; i++)
            {
                scanf("%lld", &book[i]);
                Inserst(book[i]);
            }
            for(i = 0; i < n; i++)
            {
                if(Find(book[i]) > max || (Find(book[i]) == max && book[i] < x))
                {
                    max = Find(book[i]);
                    x = book[i];
                }
            }
            printf("%d %d\n", x, max);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Time Limit Exceeded
    Take time: 1010ms
    Take Memory: 0KB
    Submit time: 2017-02-22 17:54:30
    ****************************************************/

以下为runtime error代码——输入数据记录数组过小（而且映射关系太大，即使数组不越界，也会超时）

#include <stdio.h>
    #include <stdlib.h>
    #define N 10000
    long long book[10004];
    struct node
    {
        int Data;
        struct node *next;
    };
    struct node *a[10004];
    
    void Inserst(struct node *a[], long long n)
    {
        long long x = n/N;
        struct node *p = (struct node *)malloc(sizeof(struct node));
        p->Data = n;
        p->next = a[x];
        a[x] = p;
    }
    
    int  Find(struct node *a[], long long n)
    {
        int cnt = 0;
        long long x = n/N;
        if(a[x] != NULL)
        {
            struct node *p;
            p = a[x];
            while(p != NULL)
            {
                if(p->Data == n)
                    cnt++;
                p = p->next;
            }
        }
        return cnt;
    }
    
    int main()
    {
        int n, i, x, max = -199859;
        scanf("%d", &n);
        {
            struct node *a[100004];
            max = -199859;
            for(i = 0; i < n; i++)
            {
                scanf("%lld", &book[i]);
                Inserst(a, book[i]);
            }
            for(i = 0; i < n; i++)
            {
                if(Find(a, book[i]) > max || (Find(a, book[i]) == max && book[i] < x))
                {
                    max = Find(a, book[i]);
                    x = book[i];
                }
            }
            printf("%d %d\n", x, max);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Runtime Error
    Take time: 0ms
    Take Memory: 0KB
    Submit time: 2017-02-22 17:52:37
    ****************************************************/