精华内容
下载资源
问答
  • 数据结构 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;
    }
    展开全文
  • 链地址法:将所有关键字为同义词的记录保存在一个线性链表中(拉链)设某哈希函数产生的哈希地址在区间[0,12]上,则创建指针数组add[12],其中每个元素都是一个单项链表的头结点(有值)。由于仅仅是简单的实现。。...

    链地址法:将所有关键字为同义词的记录保存在一个线性链表中(拉链法)

    设某哈希函数产生的哈希地址在区间[0,12]上,则创建指针数组add[12],其中每个元素都是一个单项链表的头结点(有值)。

    由于仅仅是简单的实现。。插入链表时没有做排序的处理。。

    链表节点定义:

    typedef struct node

    {

    int data;

    struct node *next;

    }Elem ,*Link;

    设已知的一组关键字为 19,14,23,1,68,20,84,27,55,11,10,79共12个,按哈希函数H(key)=key MOD  13构造简单哈希表。

            int data[12]={19,14,23,1,68,20,84,27,55,11,10,79},key,i,j;

    Link add[13]={NULL};

    Link p,q;

    for(i=0;i<12;i++)

    {

    key=data[i]%13;

    p=(Link)malloc(sizeof(Elem));

    p->data =data[i];

    p->next =NULL;

    if(!add[key]) add[key] =p;//如果头结点为空,则直接为头结点赋值

    else

    {

    for(q=add[key];q->next ;q=q->next );//q作p前趋

    q->next =p;

    }

    }

    至此这个简易的哈希表已经创建成功,于是乎输出一下看看结果

    for(j=0;j<13;j++)

    {

    if(add[j])

    {

    q=add[j];

    while(q)

    {

    printf("%5d",q->data );

    q=q->next ;

    }

    printf("\n");//每个单链表作为一行

    }

    else

    printf("NULL\n");//若头结点为空,就直接输出一个NULL

    }

    运行结果

    0818b9ca8b590ca3270a3433284dd417.png

    0818b9ca8b590ca3270a3433284dd417.png

    展开全文
  • 哈希链地址法

    千次阅读 2019-03-28 16:37:25
    /*************************************************** 目的:将一堆整数存入hash...散列冲突方法:链地址法 ***************************************************/ #include <stdio.h> #include <stdlib...
    /***************************************************
    目的:将一堆整数存入hash表
    键值:本身
    哈希函数的构造方法:除留余数法
    散列冲突方法:链地址法
    ***************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    
    #define N 13
    
    typedef struct node
    {
        int data;
        struct node *next;
    }listnode, *pLinklist;
    
    int insert(pLinklist h, int key)
    {
        int value = key % N; /*除留余数法*/
        pLinklist p = &h[value]; /*p指向哈希表中应存的位置,相当于指向链表头*/
        pLinklist q = NULL; /*q生成要存的数据*/
    
        q = (pLinklist)malloc(sizeof(listnode));
        q->data = key;
        q->next = NULL;
    	/*若p->next为NULL,链表头指向空,不走while, head-->q-->NULL
    	若p->next不为NULL,如head-->q1-->NULL,若q1>q,不走while,head-->q-->q1-->NULL
    	若p->next不为NULL,如head-->q1-->NULL,若q1<q,走while,head-->q1-->q-->NULL 使链表排列是从小到大的*/
        while (p->next && p->next->data < key)
        {
            p = p->next;
        }
        
        q->next = p->next;
        p->next = q;
        
        return 0;
    }
    
    int contains(pLinklist h, int key)
    {
        int value = key % N;
        pLinklist p = h[value].next;
    
        while (p)
        {
            if (p->data == key)
                return 0;
            p = p->next;
        }
        return -1;
    }
    
    void show(pLinklist p)
    {
        while (p)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
    
    int main()
    {
        /*哈希表 用链地址法处理冲突 故用节点作为数据结构 数组中节点相当于链表头,不存数据*/
        listnode hash[N] = {{0, NULL}};
        /*要存入哈希表的数据*/
        int a[] = {23, 23, 34, 14, 38, 46, 16, 68, 15, 7, 31, 26, 6, 6, 51, 66, 77};
    		int i = 0;
    		
        for (i = 0; i < sizeof(a)/sizeof(int); i++)
            insert(hash, a[i]);
    
        for (i = 0; i < N; i++)
            show(hash[i].next);
    
        printf("** %d\n", contains(hash, 23));
        printf("** %d\n", contains(hash, 99));
    
        return 0;
    }
    

    结果:
    在这里插入图片描述

    展开全文
  • 哈希表-链地址法

    2017-12-20 13:50:39
    哈希

    链地址法其实就是将实现哈希表的底层数组的类型变成链表,每次插入数据插入到链表中即可

    这里写图片描述

    package map;
    
    public class Node
    {
        private int data ;
        public Node next ;
    
        public Node ( int data )
        {
            this.data = data ;
        }
    
        public int getData ()
        {
            return data;
        }
    
        public void setData ( int data )
        {
            this.data = data;
        }
    
    
    }
    ---------------
    package map;
    
    public class LinkList
    {
        private Node first ;//首节点
        private Node current ;//用来记录当前节点
        private Node newNode ;
    
        //插入数据
        public void insert ( int i )
        {
            newNode = new Node ( i ) ;
    
            if ( first == null )
            {
                first = newNode ;
                return ;
            }
    
            newNode.next = first ;
            first = newNode ;
    
        }
    
        public void delete ( int value )
        {
            current = first ;
            Node parent = first ;
            while ( current != null )
            {
                if ( current.getData () == value )
                {
                    parent.next = current.next ;
                    return ;
                }
                parent = current ;
                current = current.next ;
            }
        }
    
        public Node find ( int value )
        {
            current  = first ;
    
            while ( current != null && current.getData () != value )
            {
                current = current.next ;
            }
    
            //跳出循环说明找到或者为空
            if ( current == null )
            {
                System.out.println ( "null" );
                return null ;
            }
            else
            {
                return current ;
            }
        }
    
        public void display ()
        {
            current = first ;
            while ( current != null )
            {
                System.out.print ( current.getData () + " " );
                current = current.next ;
            }
            System.out.println (  );
        }
    }
    -----------------------
    package map;
    
    public class LinkHash
    {
        private LinkList [] arr ;
        private int size  ;
        private Node newNode ;
    
        public LinkHash ( int size )
        {
            this.size = size ;
            arr = new LinkList [size] ;
        }
    
        public int Hash ( int data )
        {
            return data % arr.length ;
        }
    
        //插入
        public void insert ( int data )
        {
            int index = Hash ( data ) ;//计算索引下标
    
            //如果为空,就new一个list进去
            if ( arr [index] == null )
            {
    
                LinkList l = new LinkList () ;
                l.insert ( data );
                arr [index] = l ;
            }
            else
            {//不为空直接入
                arr [index].insert ( data );
            }
        }
    
        public Node find ( int data )
        {
            int index = Hash ( data ) ;
    
            if ( arr [index] == null )
            {
                return null ;
            }
            else 
            {
                Node n = arr [index].find ( data ) ;
    
                if ( n == null )
                {
                    return null ;
                }
                else
                {
                    return n ;
                }
            }
    
        }
    
        public void delete ( int data )
        {
            int index = Hash ( data ) ;
    
            arr [index].delete ( data );
        }
    
        public void display ()
        {
            for ( int i = 0 ; i < arr.length ; ++ i )
            {
                if ( arr [i] != null )
                arr [i].display ();
                else
                    System.out.println ();
            }
            System.out.println ( "-------------" );
        }
    
    }
    
    展开全文
  • 哈希表 用链地址法解决冲突:(哈希函数是按名字第一个大写字母分的) 输入内容:学生的姓名跟成绩 操作:插入、修改、查找、删除学生;以及输出哈希
  • JavaScript——哈希表(链地址法) /*哈希表类(链地址法) 哈希表里每个索引对应的元素为一个桶(bucket),每个桶为一个数组。 桶里的每个元素也是一个数组,称为元组(tuple) 每个元组由key和value组成 哈希表整体结构:[...
  • 哈希链地址法

    千次阅读 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-02-24 16:30:42
    哈希函数: 使用特定的哈希...链地址法: 开放地址法中,通过在哈希表中寻找一个空位解决哈希冲突问题。另一个方法是在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元,而数据项本...
  • 哈希表之链地址法

    2018-05-02 18:42:27
    链地址法比开放地址法要好。哈希化的效率:1,线性探测:成功查找P=(1+1/(1-L))/2;不成功查找为P=(1+1/(1-L)^2)/2;其中P为探测序列,L为装填因子2,二次探测和再哈希法:成功查找P=-log2(1-L)/L;不成功查找P=1/(1...
  • 哈希查找--链地址法

    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
    我前面说过哈希表的开放定址,现在说说链地址法又称开散列,在利用毕散列时我们说到有哈希冲突,而开散列法正好避开了哈希冲突,每个下标所在位置就是桶口,每个桶可以看做是一个链表,我们把哈希冲突的元素放在...
  • 哈希表处理。。。用链地址法处理。。。建立关键字的头指针,然后依次插入。。。
  • while(true) { switch(i) { case 1: printf("模为%d的哈希表为:\n",m); shuchuHash(HT); printf("输入你要进行操作的相应数字:"); cin>>i; break; case 2: printf("请输入要查找的数:...
  • DS哈希查找--链地址法

    2020-12-21 19:32:00
    问题 C: DS哈希查找--链地址法 时间限制: 1 Sec 内存限制: 128 MB 提交: 340 解决: 237 [提交][状态][讨论版] 题目描述 给出一个数据序列,建立哈希表,采用求余法作为哈希函数,模数为11,哈希冲突用链地址法和...
  • 1012: 哈希表(链地址法处理冲突) 题目描述 采用除留余数(H(key)=key %n)建立长度为n的哈希表,处理冲突用链地址法。建立链表的时候采用尾插。 输入 第一行为哈西表的长度m; 第二行为关键字的个数n; 第三...
  • #include #include typedef struct node { int data; struct node *next; }node; init_hash(node **A,int n) { int i; for(i=0;i;i++) { A[i]=(node *)malloc(sizeof(node));...printf("请选择hash表的操作\n1....}
  • 地址法概述 一开始开辟一个M的空间的数组; 将要存储的对象转换成... 数组中的每个索引后都挂有一条链表,这就是所谓的链地址法(Separate Chain); 当链表的长度超过一定程度后,Java会将其转换以红黑树,Jav...
  • 链地址法 设计思路:节点存储和原数值它的下一个节点,将每一个数组存储节点,其下标为其哈希值,节点指向所有和它冲突的值 此代码运算哈希值的运算公式 f(x)=x%14 当然也可以通过别的函数运算其哈希值,由于...
  • 哈希表:线性探测链地址法求查找成功与不成功的平均查找
  • hash表一般都采用取余构造(将一个数对n取余然后根据余数来查找是否存在该数),当两个数的余数相同时仅仅凭借余数作为下标来查找就会发生错误即hash冲突,那么链地址法其实就是将余数相同的数用链表储存起来,那么...
  • 学习力 哈希链地址法 就是玉树相同的在一个链表里 参考网上的 第一次用#include #include #include #define inf 1000007 struct node { __int64 num,count; node *next; }hash[1000010]; __int64 count,n; bool ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,413
精华内容 17,765
关键字:

哈希链地址法