精华内容
下载资源
问答
  • 数据结构 C语言 哈希 链地址法

    千次阅读 2017-07-05 11:01:20
    【问题描述】 为了美丽的校园计划,学校决定改进排队制度,比如说给饭卡充钱等…… 给每个人一个RP值,这个RP值决定这个人来了之后要排的位置,如果当前位置已经有人, ...任务要求:用链地址法解决冲突的方式建立

    【问题描述】
    为了美丽的校园计划,学校决定改进排队制度,比如说给饭卡充钱等……
    给每个人一个RP值,这个RP值决定这个人来了之后要排的位置,如果当前位置已经有人,
    那么从这个位置以后的人后移一位,这个人插进去,如果没有人的话就直接排到这个位置上去。
    现在已知按时间从前到后来的人的名字和RP值,求按排队顺序输出排队人的名字。
    【任务要求】
    任务要求:用链地址法解决冲突的方式建立哈希表,将RP值相同的元素利用头插法插入到同一个单链表中,并依次输出哈希表中的每一个链表。如:

    【测试数据】
    输入
    多组测试数据,以文件结束
    每组首先一个n(1<=n<=200000),接着一行是名字和RP值,名字是不超过20的字符串
    RP值不超过int
    输出
    按排队顺序输出排队人的名字
    样例输入:
    4
    Yougth 1
    yuanhang 2
    kaichuang 2
    yaoyao 1
    样例输出
    yaoyao Yougth kaichuang yuanhang

    //代码有点缺陷,稍后修改

    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node{
        char name[20];
        struct node *next;
    }nextNode;
    
    typedef struct {
        nextNode *col;
    }list;
    
    list *createHash()
    {
        list ls[1000];
        int i, n, rp;
        nextNode *s;
        for (i = 0; i < 1000; i++) {
            ls[i].col = (nextNode*)malloc(sizeof(nextNode));
            ls[i].col->next = NULL;
        }
        scanf("%d", &n);
        for (i = 0; i < n; i++) {
            s = (nextNode*)malloc(sizeof(nextNode));
            scanf("%s", s->name);
            scanf("%d", &rp);
            s->next = ls[rp].col->next;
            ls[rp].col->next = s;
        }
        return ls;
    }
    
    int display(list *ls)
    {
        int i;
        nextNode *p;
        for (i = 0; i < 200; i++) {
            p = ls[i].col;
            while (p->next != NULL) {
                p = p->next;
                printf("%s ", p->name);
            }
        }
        return 0;
    }
    
    int main()
    {
        list *ls;
        ls = createHash();
        display(ls);
        printf("\n");
        system("pause");
        return 0;
    }
    展开全文
  • poj2002 哈希链地址法

    2017-04-04 21:44:04
    Squares ...A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles.... as a regular octagon also has this property....用链地址法。 代码:
    Squares
    Time Limit: 3500MS   Memory Limit: 65536K
    Total Submissions: 19983   Accepted: 7691

    Description

    A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property. 

    So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates. 

    Input

    The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.

    Output

    For each test case, print on a line the number of squares one can form from the given stars.

    Sample Input

    4
    1 0
    0 1
    1 1
    0 0
    9
    0 0
    1 0
    2 0
    0 2
    1 2
    2 2
    0 1
    1 1
    2 1
    4
    -2 5
    3 7
    0 0
    5 2
    0
    

    Sample Output

    1
    6
    1
    

    Source


    给你坐标上的一些点,问你最多能构成多少个正方形。
    在坐标上给出两点计算能构成正方形的另外两点的公式:

    已知: (x1,y1)  (x2,y2)

    则:   x3=x1+(y1-y2)   y3= y1-(x1-x2)

    x4=x2+(y1-y2)   y4= y2-(x1-x2)

    x3=x1-(y1-y2)   y3= y1+(x1-x2)

    x4=x2-(y1-y2)   y4= y2+(x1-x2)

    这样的做法会使一个正方形被枚举四次,所以最后输出要除以四。
    用哈希标记每一个点,查询时解决地址冲突的方法
    #include<iostream>
    #include<malloc.h>
    #include<cstring>
    using namespace std;
    const int prime=1999;
    struct Node
    {
        int x,y;
    };
    struct HashTable
    {
        int x,y;
        HashTable *next;
    };
    struct Node pos[1001];
    struct HashTable *hashs[prime];
    
    void insert_vist(int k)
    {
        int key=(pos[k].x*pos[k].x+pos[k].y*pos[k].y)%prime+1;
        if(!hashs[key])
        {
            HashTable *temp=(struct HashTable*)malloc(sizeof(HashTable));
    
            temp->x=pos[k].x;
            temp->y=pos[k].y;
            temp->next=NULL;
            hashs[key]=temp;
        }
        else//hashs[key]地址已存,开放寻址
        {
            HashTable *temp=hashs[key];
            while(temp->next)  //直至temp->next为NULL
                temp=temp->next;
            temp->next=(struct HashTable*)malloc(sizeof(HashTable));
            temp->next->x=pos[k].x;
            temp->next->y=pos[k].y;
            temp->next->next=NULL;
        }
        return;
    }
    
    bool finds(int x,int y)
    {
        int key=(x*x+y*y)%prime+1;
        if(!hashs[key])
            return false;
        else
        {
            HashTable *temp=hashs[key];
            while(temp)
            {
                if(temp->x==x&&temp->y==y)
                    return true;
                temp=temp->next;
            }
        }
        return false;
    }
    
    int main()
    {
        int n;
        while(cin>>n)
        {
            if(n==0)
                break;
            memset(hashs,0,sizeof(hashs));
            for(int k=1;k<=n;k++)
            {
                cin>>pos[k].x>>pos[k].y;
                insert_vist(k);
            }
            int num=0;
            for(int i=1;i<=n-1;i++)
            {
                for(int j=i+1;j<=n;j++)
                {
                    int a=pos[j].x-pos[i].x;
                    int b=pos[j].y-pos[i].y;
                    int x3=pos[i].x+b;
                    int y3=pos[i].y-a;
                    int x4=pos[j].x+b;
                    int y4=pos[j].y-a;
                    if(finds(x3,y3)&&finds(x4,y4))
                        num++;
                    x3=pos[i].x-b;
                    y3=pos[i].y+a;
                    x4=pos[j].x-b;
                    y4=pos[j].y+a;
                    if(finds(x3,y3)&&finds(x4,y4))
                        num++;
    
                }
            }
            cout<<num/4<<endl;
        }
        return 0;
    }
    

    用链地址法。
    代码:
    展开全文
  • 就是不知道哪里出了问题,今早上又改,改来改去才知道原来我new node后边缺了个括号,我很懵懂,我记得不用括号也行啊,而且我看到一个AC的代码就是没用括号,但是不加就不对,终于用了链地址法改对了能运行了,交上...

    http://poj.org/problem?id=3007

    题意 :给你一个字符串,让你无论从什么地方分割,把这个字符串分成两部分s1和s2,然后再求出s3和s4,让你进行组合,看能出来多少种不同的形式。

    思路 :记得以前的时候就听他们讨论这道题,说是用map做会超时,所以我直接就没用map。。。。但是做这道题实在是太波折了,昨天晚上改了一晚上都不对,就是不知道哪里出了问题,今早上又改,改来改去才知道原来我new node后边缺了个括号,我很懵懂,我记得不用括号也行啊,而且我看到一个AC的代码就是没用括号,但是不加就不对,终于用了链地址法改对了能运行了,交上去因为数组开小了就越界了............然后又因为忘了删掉我在代码中加的测试的输出,所以Output Limit Exceeded了一次.............

    这个题主要是处理好冲突就行了。

    #include <stdio.h>
    #include <string.h>
    #include <iostream>
    #include <algorithm>
    #include <stdlib.h>
    #include <string>
    using namespace std ;
    
    struct node
    {
        char ch1[1100] ;
        struct node *next ;
    }*hash[1000000] ;
    
    int cnt ;
    
    void hashh(char *ch,char *sh)
    {
        char str[1200] ;
        strcpy(str,ch) ;
        strcat(str,sh) ;
        int len = strlen(str) ;
        int sum = 0 ;
       for(int i = 0 ; i < len ; i++)
            sum += (str[i]*i)  ;
        if(!hash[sum])
        {
            node *p= new node() ;
            strcpy(p->ch1,str) ;
            hash[sum] = p ;
            cnt++ ;
        }
        else
        {
            node *p = hash[sum] ;
            if(!strcmp(p->ch1,str)) return ;
            else
            {
                while(p->next)
                {
                    if(!strcmp(p->next->ch1,str)) return ;
                    p = p->next ;
                }
                node *q = new node() ;
                strcpy(q->ch1,str) ;
                p->next = q ;
                cnt++ ;
            }
        }
        return ;
    }
    int main()
    {
        int n ;
        scanf("%d",&n) ;
        char str[1100],str1[1010],str2[1100],str3[1010],str4[1010]  ;
        while(n--)
        {
            cnt = 0 ;
            memset(hash,0,sizeof(hash)) ;
            scanf("%s",str) ;
            int len = strlen(str) ;
            for(int i = 1 ; i < len ; i++)
            {
                int j = 0 , k = 0 ;
                for( ; j < i ; j++)
                    str1[j] = str[j] ;
                str1[j] = '\0' ;
                for(j = i ; j < len ; j++)
                    str2[k++] = str[j] ;
                str2[k] = '\0' ;
                strcpy(str3,str1) ;
                strcpy(str4,str2) ;
                reverse(str3,str3+i) ;
                reverse(str4,str4+k) ;
              //  printf("%s %s %s %s\n",str1,str2,str3,str4) ;
                hashh(str1,str2) ;
                hashh(str3,str2) ;
                hashh(str1,str4) ;
                hashh(str3,str4) ;
                hashh(str2,str1) ;
                hashh(str2,str3) ;
                hashh(str4,str1) ;
                hashh(str4,str3) ;
            }
            printf("%d\n",cnt) ;
        }
        return 0 ;
    }
    View Code

     

    转载于:https://www.cnblogs.com/luyingfeng/p/3548969.html

    展开全文
  • 没啥好说的,用哈希表的链地址法。 // // //刚开始直接是面向样例编程没用到哈希表,结果直接超时, // // //后来想到用Hash映射解决可以大幅度降低时间复杂度 // // //取100003为取余数(就是鲁大师说的那个形如4*...

    7-15 航空公司VIP客户查询 (25分)
    不少航空公司都会提供优惠的会员服务,当某顾客飞行里程累积达到一定数量后,可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录,要求实现根据身份证号码快速查询会员里程积分的功能。

    输入格式:
    输入首先给出两个正整数N(≤10^5
    ​​ )和K(≤500)。其中K是最低里程,即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行,每行给出一条飞行记录。飞行记录的输入格式为:18位身份证号码(空格)飞行里程。其中身份证号码由17位数字加最后一位校验码组成,校验码的取值范围为0~9和x共11个符号;飞行里程单位为公里,是(0, 15 000]区间内的整数。然后给出一个正整数M(≤10^5
    ​​ ),随后给出M行查询人的身份证号码。

    输出格式:
    对每个查询人,给出其当前的里程累积值。如果该人不是会员,则输出No Info。每个查询结果占一行。

    输入样例:

    4 500
    330106199010080419 499
    110108198403100012 15000
    120104195510156021 800
    330106199010080419 1
    4
    120104195510156021
    110108198403100012
    330106199010080419
    33010619901008041x
    

    输出样例:

    800
    15000
    1000
    No Info
    

    思路:
    (没用stl,因为老师说期末考试不能用stl,所以平时练习时从’底层写起‘);
    没啥好说的,用哈希表的链地址法。

    // // //刚开始直接是面向样例编程没用到哈希表,结果直接超时,
    // // //后来想到用Hash映射解决可以大幅度降低时间复杂度
    // // //取100003为取余数(就是鲁大师说的那个形如4*i+3的素数,由于n<=10000,所以取100003)
    #include<stdio.h>
    #include<string.h>
    #include<malloc.h>
    #include<stdlib.h>
    typedef struct Node{
        char id[20];
        int len;
        struct Node *next;
    }Node,*LinkList;
    
    LinkList List[100003]={NULL};
    int n,k;
    
    void InsertList(int index,char *id,int length)
    {
        if(List[index%100003]==NULL){
            LinkList ss=(LinkList)malloc(sizeof(Node));
            ss->next=NULL;
            for(int i=0;i<20;i++){
                ss->id[i]=id[i];
            }
            if(length<k){
                ss->len=k;
            }else{
                ss->len=length;
            }
            List[index%100003]=ss;
            return ;
        }else{
            LinkList p=List[index%100003];
            LinkList q=NULL;
            while(p){
                if(strcmp(p->id,id)==0){
                    if(length<k){
                        p->len+=k;
                    }else{
                        p->len+=length;
                    }
                    return ;
                }
                q=p;
                p=p->next;
            }
            LinkList ss=(LinkList)malloc(sizeof(Node));
            ss->next=NULL;
            for(int i=0;i<20;i++){
                ss->id[i]=id[i];
            }
            if(length<k){
                ss->len=k;
            }else{
                ss->len=length;
            }
            q->next=ss;
            return ;
        }
    }
    
    void SearchList(char *id){
    
        int index=(id[13]-'0')*10000+(id[14]-'0')*1000+(id[15]-'0')*100+(id[16]-'0')*10+(id[17]-'0');
        LinkList p=List[index%100003];
        while(p){
            if(strcmp(p->id,id)==0){
                printf("%d\n",p->len);
                return ;
            }
            p=p->next;
        }
        printf("No Info\n");
        return ;
    }
    
    int main()
    {
        scanf("%d %d",&n,&k);
        char id[20];
        int length=0;
        for(int i=0;i<n;i++){
            getchar();
            scanf("%s %d",id,&length);
            int index=(id[13]-'0')*10000+(id[14]-'0')*1000+(id[15]-'0')*100+(id[16]-'0')*10+(id[17]-'0');
            InsertList(index,id,length);
        }
    
        int m;
        scanf("%d",&m);
        getchar();
        char name[20];
        for(int i=0;i<m;i++){
            scanf("%s",name);
            SearchList(name);
        }
        return 0;
    }
    
    展开全文
  • 哈希链地址法

    千次阅读 2019-03-28 16:37:25
    /*************************************************** 目的:将一堆整数存入hash...散列冲突方法:链地址法 ***************************************************/ #include <stdio.h> #include <stdlib...
  • 哈希链地址法

    千次阅读 2018-04-18 21:50:56
    不带头结点的就是这点不好,非要通过改变它的自身值来改变原有地址 { HashLink[k]=s;//易错点 return 1; } while(q&&q->data) { pre=q; q=q->next; } if(!q)//第二种情况,pre为最后一个节点,插在尾部 ...
  • 哈希函数: 使用特定的哈希...链地址法: 开放地址法中,通过在哈希表中寻找一个空位解决哈希冲突问题。另一个方法是在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元,而数据项本...
  • 代码实现: 散列函数采用除留余数法,冲突解决采用链地址法。 #ifndef _HASH_H #define _HASH_H #define HASHSIZE 10 typedef struct Node { int data; Node *next; }Node; class HashTable { private: Node* ...
  • 哈希表之链地址法

    2020-01-30 20:31:21
    一:什么是链地址法哈希表每个单元中设置链表.某个数据项的关键字还是像通常一样映射到哈希表的单元中,而数据项本身插入到单元的链表中 二:代码实现 1.创建链表节点Node public class Node { //数据域 Person ...
  • 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合中是否存在这个值。 remove(value):将给定值从哈希集合中...
  • 哈希查找--链地址法

    2020-12-26 13:41:45
    哈希查找–链地址法 题目描述 给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和表头插入 如果首次查找失败,就把数据插入到相应的位置中 实现哈希查找功能 输入 第一行输入n...
  • 哈希桶(链地址法

    2018-09-05 15:23:38
    哈希表使用链地址法进行数据的存储 哈希桶是在发生冲突时,将数据直接链接在该表位置的后面 当发生冲突时采用链式结构,将相同地址的数链接在后面。适用于经常删除和增加的情况。 当同一地址连接的数据过多时,就...
  • 哈希表(链地址法处理冲突) 1000(ms) 10000(kb) 2681 / 6927 采用除留余数法(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插法。 输入 第一行为哈西表的长度m; 第二行为...
  • 哈希表(链地址法

    千次阅读 2018-10-26 11:31:57
    我前面说过哈希表的开放定址法,现在说说链地址法又称开散列法,在利用毕散列时我们说到有哈希冲突,而开散列法正好避开了哈希冲突,每个下标所在位置就是桶口,每个桶可以看做是一个链表,我们把哈希冲突的元素放在...
  • 哈希表-链地址法

    2017-12-20 13:50:39
    哈希
  • while(true) { switch(i) { case 1: printf("模为%d的哈希表为:\n",m); shuchuHash(HT); printf("输入你要进行操作的相应数字:"); cin>>i; break; case 2: printf("请输入要查找的数:...
  • JavaScript——哈希表(链地址法) /*哈希表类(链地址法) 哈希表里每个索引对应的元素为一个桶(bucket),每个桶为一个数组。 桶里的每个元素也是一个数组,称为元组(tuple) 每个元组由key和value组成 哈希表整体结构:[...
  • DS哈希查找--链地址法

    2020-12-21 19:32:00
    问题 C: DS哈希查找--链地址法 时间限制: 1 Sec 内存限制: 128 MB 提交: 340 解决: 237 [提交][状态][讨论版] 题目描述 给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和...
  • 连地址法概述 一开始开辟一个M的空间的数组; 将要存储的对象转换成... 数组中的每个索引后都挂有一条链表,这就是所谓的链地址法(Separate Chain); 当链表的长度超过一定程度后,Java会将其转换以红黑树,Jav...
  • poj3349(哈希+链地址法)

    2019-10-06 07:50:40
    给出N个六边形的6个边长,问其中是否有完全相同...给每个6边形一个哈希值,方法是对6条边长度的平方和取模 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 899
精华内容 359
关键字:

哈希链地址法