| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6649 人关注过本帖, 1 人收藏
标题:原子【基础版本】(已完成插入、插入整数、查找、判断、插入浮点数)
取消只看楼主 加入收藏
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
结帖率:95.65%
收藏(1)
已结贴  问题点数:100 回复次数:22 
原子【基础版本】(已完成插入、插入整数、查找、判断、插入浮点数)
注意:
    这里说的原子并不是原子操作!!!!
    此处的原子源于LISP。
    原子是一个指针,指向唯一的一个字符序列。
    通过比较两个指针的值,即可判断两者指向的字符串是否相等,原因在于,任一字符序列只会出现一次!!!!


已完成基础的插入,后续还剩下 查找,比较等。

如果代码有任何BUG、或你有任何疑问、或建议,请提出,不胜感激。

冲突一定是会发生的,为了解决冲突,因此结构上使用了链表。

22:43 06/14
            修改了散列函数,冲突明显减少。
00:39 06/15
            修改了数列,虽然并未减少冲突,但是让散列值分布较之前更加均匀。
            经测试读取一个9800个无重复单词的文本文档,发生冲突的几率是22%,链表的节点数均在3左右,最多节点数达到5。
16:24 06/15
            查找、判断函数已完成。
19:05 06/15
            已完成将长整数插入原子表。
20:53 06/16
            已完成将浮点数插入原子表。



程序代码:
/*测试*/

#include <stdio.h>
#include <string.h>
#include "Atom.h"

int
main( void )
{
    char src[ 100 ];
    char *des;

    while( NULL != fgets( src, 100, stdin ) )
    {
        src[ strlen( src ) - 1 ] = '\0';
        des = NewAtom( src );
        printf( "%s\n", des );
    }

    return 0;
}

程序代码:
/*接口*/
#ifndef _ATOM_H
#define _ATOM_H

char *
NewAtom( char *src );
/*将一个字符串添加到原子表中,如果该字符串已经存在,则返回位于原子表中的该字符串,否则添加到原子表并且返回位于原子表中的该字符串。
任何试图修改原子的行为是无法检测的错误。*/

char *
IntAtom( long value );
/*将一个长整数转换为字符串,添加到原子表中,如果该字符串已经存在,则返回位于原子表中的该字符串,否则将该字符串添加到原子表并且返回位于原子表中的该字符串。
任何试图修改原子的行为是无法检测的错误。*/


char *
DoubleAtom( double value, int length );
/*将一个浮点数转换为字符串,添加到原子表中,如果已经存在则返回原子表中的该字符串,否则将该字符串添加到原子表并且返回该字符串。
DoubleAtom()函数的第一个参数为需要添加到原子表中的浮点数,第二个参数为小数点后数字的长度。
length不可以小于0,如果小于0则返回NULL。
*/

char *
FindAtom( char *src );
/*在原子表中查找一个字符串,如果在表中,返回原子表中的该字符串,否则返回NULL
任何试图修改原子的行为是无法见车的错误*/

int
DetermineAtom( char *src, char *dst );
/*判断两个原子指向的字符串是否相等,向该函数传递非源自原子表中的指针是无法检测的错误
相等返回1,否则返回0*/

void
chongtu1( void );/*测试用函数,可删除*/
#endif

程序代码:
/*实现*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "Atom.h"
#define EvenKey 101
#define OddKey 211
#define H Hash
typedef struct H *H;
#define K Key

struct K {
    unsigned long int Even;
    unsigned long int Odd;
    int Len;
};

struct H{
    H Link;
    int Len;
    char *Src;
};

static H HashTable[ EvenKey ][ OddKey ];

static struct K
HashFun( char *src );

char *
NewAtom( char *src )
{
    struct K key;
    H this;
    H new;

    if( NULL == src )
        return NULL;

    key = HashFun( src );

    for( this = HashTable[ key.Even ][ key.Odd ]; NULL != this; this = this->Link )
        if( key.Len == this->Len )
            if( 0 == strcmp( src, this->Src ) )
                return this->Src;

    new = ( H )malloc( sizeof( struct H ) );
    if( NULL == new )
    exit( EXIT_FAILURE );
    new->Len = key.Len;
    new->Src = strdup( src );
    new->Link = HashTable[ key.Even ][ key.Odd ];
    HashTable[ key.Even ][ key.Odd ] = new;

    return new->Src;
}

int
DetermineAtom( char *src, char *dst )
{
    return src == dst;
}


char *
FindAtom( char *src )
{
    struct K key;
    H this;

    key = HashFun( src );

    for( this = HashTable[ key.Even ][ key.Odd]; NULL != this; this = this->Link )
        if( key.Len == this->Len )
            if( 0 == strcmp( src, this->Src) )
                return this->Src;

    return NULL;
}


#include <limits.h>
void
ItoS( unsigned long value, char *buffer );

char *
IntAtom( long value )
{
    char buffer[ 100 ];
    unsigned long n;

    if( LONG_MIN == value )
    {
        n = LONG_MAX + 1UL;
        buffer[ 0 ] = '-';
        ItoS( n, buffer + 1 );
    }
    else if( 0 > value )
    {
        n = -value;
        buffer[ 0 ] = '-';
        ItoS( n, buffer + 1 );
    }
    else
        ItoS( value, buffer );;

    return NewAtom( buffer );
}


char *
DoubleAtom( double value , int length )
{
    char buffer[ 100 ];
    char *src;
    unsigned long power;
    double integer;
    double devimal;

    src = buffer;
    power = pow( 10, length );    

    if( 0 > value )
    {
        value *= -1;
        *src++ = '-';
    }

    devimal = modf( value, &integer );
    devimal *= power;
    ItoS( ( unsigned long )value, src );

    if( 0 != ( unsigned long )devimal )
    {
        int length = strlen(src);
        src[ length++ ] = '.';
        src[ length ] = '\0';
        ItoS( ( unsigned long )devimal, &src[ length ]);
    }

    return NewAtom( buffer );    
}


void
ItoS( unsigned long value, char *buffer )
{
    static int ix = 0;

    if( 0 != value / 10 )
        ItoS( value / 10, buffer );
    else
        ix = 0;

    buffer[ ix++ ] = value % 10 + '0';
    buffer[ ix ] = '\0';
}



static unsigned long int scatter[] = 

{763886,98427677,92132,8985211,13039125,24243037,3301847,59153526,33682303,59871667,2427280,63468416,32036220,36579419,54565969,88329145,65162120,80548711,97819618,24188516,90161124,29694574,912717

33,83294586,8342758,6132648,38282737,12987094,97193732,4179587,12266336,3036295,2585741,83131394,21439985,8521426,24979665,81878169,4426519,56103885,8278484,82839570,76081111,59512197,2518751,46884

362,1881190,69327849,4350926,3881300,20162120,25741213,65855507,86483029,51586458,73342808,56754322,40931767,40079146,74331877,49054083,32127559,355490,98962454,3614643,36314919,93276160,10015213,2

808739,387580,7826681,62762801,71611367,27236721,5992993,7143959,43431560,6222210,5467604,35719894,15008883,52829025,73163041,72121897,22794936,3976693,39427257,11816449,93372508,84363894,98438213,

69143257,52249272,83662259,71171005,93724481,2223663,49325772,53039410,93291499,2668699,28877224,38669365,6013633,74264121,89221968,23854237,28506493,44054328,13154706,67653109,19177199,3206486,283

07599,31531019,4206922,67706420,85556941,1271355,7529831,18846373,14516070,37538210,53272913,1327634,39271927,4280435,73248024,38623417,60415090,85059333,2041599,1294746,80323900,48358219,425589,45

59456,84163312,16375,79208671,75848350,57761050,5372448,8754836,67779544,22839116,78482152,6115560,26503349,70711533,20895590,60789818,97641356,977253,721025,57114446,16306660,43275651,6949483,7031

6811,26901210,16285927,26767451,3307438,41737694,20803560,11028044,12054262,32029542,35907903,63191356,52829286,68406538,66281290,5478517,185494,4558551,37349290,61047847,63481161,88952733,18194614

,77244724,8039728,2749281,21824485,3984467,91862302,9173219,3821671,41638702,43176491,20199960,44476653,62493364,85413794,84736745,18631309,9418487,47801626,60753091,4425439,42276238,4247976,705395

7,1113555,60525829,52625011,73234853,64327448,45458665,19279463,2562731,12143942,58894828,39004963,262952,18981190,15215655,325683,2973033,65251844,58104562,96943559,4733669,7473324,29673054,558693

62,94432250,39907562,56881884,66066043,5847501,68945840,81133107,5119999,39524518,16173428,58767743,4218541,2500641,4744839,23396012,90303049,98584351,3896895,51434895,28441306,13578262,53589942,78

687629,18106700,16908972,8034409,64662849,4523895
};

static int chongtu[ EvenKey ][ OddKey ];/*测试用数组,可删除*/

void
chongtu1( void )/*测试用函数,可删除*/
{
    int i,j;
    int count;
    
    for( i = 0, count = 0;EvenKey > i;++i )
        for( j = 0; OddKey > j; ++j )
        {
            if( 1 < chongtu[i][j] )
                printf( "冲突发生在 %d %d, 发生了 %d 次\n", i, j, chongtu[i][j] );
            if( 0 == chongtu[i][j] )
                count++;
        }

    printf( "%d个空间未被散列到\n",count );
        
}


static struct K
HashFun( char *src )
{
    struct K key;
    int ix;

    key.Len = strlen( src );
    key.Even = 0;
    key.Odd = 0;

    for( ix = 0; key.Len > ix; ++ix )
    {
        key.Even = ( key.Even << 1 ) + scatter[ ( unsigned )*( src + ix ) ];
        ++ix;
        if( key.Len > ix )
            key.Odd = ( key.Odd << 1 ) + scatter[ ( unsigned )*( src + ix ) ]; 
    }

    key.Even %= EvenKey;
    key.Odd %= OddKey;

    ++chongtu[ key.Even ][ key.Odd ];/*该语句为测试用,可删除*/

    return key;
}





[此贴子已经被作者于2017-6-16 23:46编辑过]

搜索更多相关主题的帖子: 字符串 不胜感激 
2017-06-14 21:01
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 2楼 九转星河
冲突还是发生的挺频繁的。我读取一个85.3kb的文件,冲突就我肉眼就看到3次。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 21:53
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 4楼 九转星河
用来生成Key的。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 21:56
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 6楼 九转星河
是这样。我用随机函数生成的。

我再一次测试,冲突一定是会发生,但是同一个Key出现的次数并不频繁,所以链表很短,最长的节点为13,但是只出现过一次,其他的也就4左右。(而且字符串比较首先比较长度,只有长度相等才会比较字符串,所以还是很快的。)
但是现在的问题是很多空间没有被散列到,也就是说,很大的空间被浪费了。

PS:我读取了一个85Kb的文件,文件中没有重复的单词。

[此贴子已经被作者于2017-6-14 22:13编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 22:11
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 7楼 九转星河
可以的。将Int行转换为字符串就可以了。但是还是挺麻烦的,慢慢来吧。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 22:12
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 10楼 九转星河
要比速度的话,应该没有哪个好玩的字典树快。

这个表的问题在于,空间浪费,我读取的那个文本中有9682个单词,但是竟然有16883个空间没有被散列到,也就是说,只用到了4428个空间。

散列函数我还得继续修改。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 22:29
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 10楼 九转星河
简单的修改之后,冲突减少了很多,未被散列到的空间也明显减少。

09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 22:43
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 13楼 九转星河
那倒不用,散列函数修改之后,冲突明显减少,节点数平均在2至3,所以寻找目标字符串很快。

发生冲突的可能是 22%,还是太多了。



[此贴子已经被作者于2017-6-14 23:01编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 22:45
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 13楼 九转星河
随机数列也就256个,对比其他的,显得微不足道。

散列表的核心在散列函数,第一是快,第二是生成的Key要尽可能的少冲突。

随机数列可以让散列值分布更平均(经验表明)

[此贴子已经被作者于2017-6-14 23:10编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 23:03
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:不是这样
等 级:贵宾
威 望:33
帖 子:1645
专家分:5297
注 册:2016-12-1
收藏
得分:0 
回复 13楼 九转星河
动态散列表,要实现起来并不困难。
难点在于,如果要扩充的话,那么就需要再散列,这要用很多时间。

[此贴子已经被作者于2017-6-14 23:06编辑过]


09:30 05/21 种下琵琶种子,能种活么?等待中……
21:50 05/27 没有发芽。
20:51 05/28 没有发芽。
23:03 05/29 没有发芽。
23:30 06/09 我有预感,要发芽了。
2017-06-14 23:04
快速回复:原子【基础版本】(已完成插入、插入整数、查找、判断、插入浮点数)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.054790 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved