论坛: 编程破解 标题: To:TOMY_About_Hash_Tables 复制本贴地址    
作者: NetDemon [netdemon]    ADMIN   登录
LIBRARY
    Standard C Library (libc, -lc)

SYNOPSIS
    #include <search.h>

    int
    hcreate(size_t nel);

    void
    hdestroy(void);

    ENTRY *
    hsearch(ENTRY item, ACTION action);

DESCRIPTION
    The hcreate(), hdestroy(), and hsearch() functions manage hash search
    tables.

    The hcreate() function allocates sufficient space for the table, and the
    application should ensure it is called before hsearch() is used.  The nel
    argument is an estimate of the maximum number of entries that the table
    should contain.  This number may be adjusted upward by the algorithm in
    order to obtain certain mathematically favorable circumstances.

    The hdestroy() function disposes of the search table, and may be followed
    by another call to hcreate().  After the call to hdestroy(), the data can
    no longer be considered accessible.  The hdestroy() function calls
    free(3) for each comparison key in the search table but not the data item
    associated with the key.

    The hsearch() function is a hash-table search routine.  It returns a
    pointer into a hash table indicating the location at which an entry can
    be found.  The item argument is a structure of type ENTRY (defined in the
    <search.h> header) containing two pointers: item.key points to the com-
    parison key (a char *), and item.data (a void *) points to any other data
    to be associated with that key.  The comparison function used by
    hsearch() is strcmp(3).  The action argument is a member of an enumera-
    tion type ACTION indicating the disposition of the entry if it cannot be
    found in the table.  ENTER indicates that the item should be inserted in
    the table at an appropriate point.  FIND indicates that no entry should
    be made.  Unsuccessful resolution is indicated by the return of a NULL
    pointer.

    The comparison key (passed to hsearch() as item.key) must be allocated
    using malloc(3) if action is ENTER and hdestroy() is called.

RETURN VALUES
    The hcreate() function returns 0 if it cannot allocate sufficient space
    for the table; otherwise, it returns non-zero.

    The hdestroy() function does not return a value.

    The hsearch() function returns a NULL pointer if either the action is
    FIND and the item could not be found or the action is ENTER and the table
    is full.

ERRORS
    The hcreate() and hsearch() functions may fail if:

    [ENOMEM]          Insufficient storage space is available.

EXAMPLES
    The following example reads in strings followed by two numbers and stores
    them in a hash table, discarding duplicates.  It then reads in strings
    and finds the matching entry in the hash table and prints it out.

代码:

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

    struct info {                  /* This is the info stored in the table */
            int age, room;          /* other than the key. */
    };

    #define NUM_EMPL        5000    /* # of elements in search table. */

    int
    main(void)
    {
            char str[BUFSIZ]; /* Space to read string */
            struct info info_space[NUM_EMPL]; /* Space to store employee info. */
            struct info *info_ptr = info_space; /* Next space in info_space. */
            ENTRY item;
            ENTRY *found_item; /* Name to look for in table. */
            char name_to_find[30];
            int i = 0;

            /* Create table; no error checking is performed. */
            (void) hcreate(NUM_EMPL);

            while (scanf("%s%d%d", str, &info_ptr->age,
                &info_ptr->room) != EOF && i++ < NUM_EMPL) {
                    /* Put information in structure, and structure in item. */
                    item.key = strdup(str);
                    item.data = info_ptr;
                    info_ptr++;
                    /* Put item into table. */
                    (void) hsearch(item, ENTER);
            }

            /* Access table. */
            item.key = name_to_find;
            while (scanf("%s", item.key) != EOF) {
                    if ((found_item = hsearch(item, FIND)) != NULL) {
                            /* If item is in the table. */
                            (void)printf("found %s, age = %d, room = %d\n",
                                found_item->key,
                                ((struct info *)found_item->data)->age,
                                ((struct info *)found_item->data)->room);
                    } else
                            (void)printf("no such employee %s\n", name_to_find);
            }
            hdestroy();
            return 0;
    }





SEARCH.H

代码:

/*
* Written by J.T. Conklin <jtc@netbsd.org>
* Public domain.
*/

#ifndef _SEARCH_H_
#define _SEARCH_H_

#include <sys/cdefs.h>
#include <machine/ansi.h>

#ifdef _BSD_SIZE_T_
typedef _BSD_SIZE_T_ size_t;
#undef _BSD_SIZE_T_
#endif

typedef struct entry {
char *key;
void *data;
} ENTRY;

typedef enum {
FIND, ENTER
} ACTION;

typedef enum {
preorder,
postorder,
endorder,
leaf
} VISIT;

#ifdef _SEARCH_PRIVATE
typedef struct node {
char        *key;
struct node  *llink, *rlink;
} node_t;
#endif

__BEGIN_DECLS
int hcreate __P((size_t));
void hdestroy __P((void));
ENTRY *hsearch __P((ENTRY, ACTION));
void *tdelete __P((const void *, void **,
      int (*)(const void *, const void *)));
void *tfind __P((const void *, void **,
      int (*)(const void *, const void *)));
void *tsearch __P((const void *, void **,
      int (*)(const void *, const void *)));
void      twalk __P((const void *, void (*)(const void *, VISIT, int)));
__END_DECLS

#endif /* !_SEARCH_H_ */





地主 发表时间: 11/18 17:19

回复: 寒枫 [ceo_8008]   论坛用户   登录
老大发的东东基本上我是看不懂的

所以路过~~~

B1层 发表时间: 11/18 17:59

回复: 子木 [lwei889]   论坛用户   登录
问一下ND,
#include <sys/cdefs.h>
#include <machine/ansi.h>
这两个头文件是标准库函数吗?
我没有见过啊!惭愧!

B2层 发表时间: 11/18 20:16

回复: NetDemon [netdemon]   ADMIN   登录
这是给tomy的,关于哈希表的,他那时候在公司,说带不回家,我就贴这里了。

这是BSD上的代码。
#include <sys/cdefs.h>
#include <machine/ansi.h>
这些是UNIX操作系统带的,主要是一些系统定义如:
typedef __signed char   __int8_t;
typedef unsigned char   __uint8_t;
typedef short   __int16_t;
typedef unsigned short __uint16_t;

和MS的不同,UNIX的标准C库头文件是由操作系统提供的而不是由编译器如TC、VC等带来的。

B3层 发表时间: 11/18 21:11

回复: 寒枫 [ceo_8008]   论坛用户   登录
所以前段日子论坛上出现一个程序好象一个版主说是在UNIX系统下编译的

也是C的,

就是类似这种的吗?

B4层 发表时间: 11/18 21:17

回复: 子木 [lwei889]   论坛用户   登录
那也就是说在windows下tc中不能运行了,可我昨天晚上弄了一个小时,(没有正常运行,有错误提示,我看不懂),我学tc也快一年了,我想知道:是不是在windows下能运行的c程序,都能在unix下运行,那么反过来呢?

B5层 发表时间: 11/19 14:01

回复: 寒枫 [ceo_8008]   论坛用户   登录
问题一:如果是这样的话,那么我想在UNIX下可以运行的C程序在WINDOWS下不一定可以运行

如果库函数在MS里没有的话

倒过来也是一样

对吗?

问题二:那么在UNIX下运行C程序就肯定不是用TC等编译器了,

而是它系统的什么东东,也或者是命令行,因为我没接触过UNIX,所以

不知道,见笑了

简单地总结一下,要在MS里运行C程序就需要TC编译器,因为它是建立在WINDOWS基础上

而在UNIX系统里就不是了是吗?

问题三:那么诸如此类的只能在UNIX下运行的C程序要怎么在WINDOWS下运行呢?

写一个程序也要考虑它运行的环境是吗?

B6层 发表时间: 11/19 15:14

回复: 寒枫 [ceo_8008]   论坛用户   登录
up

顶一下,可能问题很幼稚

谁帮我解释一下好吗?

B7层 发表时间: 11/19 20:21

回复: 286 [unique]   版主   登录
寒枫:
    对于你的问题非常容易回答。
    发明C语言的作者同时也是发明unix的作者。发现C的好处后,自然而然地大家要拿来用,不同的操作系统实现结果差异很大,因而所谓拿来用,只是把他的思想、语法、约定等拿来,人们各自再“创造”一个自身的C。除来“拿来”之外,人们还要根据自已操作系统的特点再加上一些新的东西。
    为了避免这种不兼容的情况,国际上统一了一个标准,这个标准就是ANSI C,并规定,不管是什么样的C。不管你增加什么样的东东,这个ANSI C里面规定的内容所有C必须遵守。
    鉴于以上,只要是ANSI C里的,所有C都可以通用。否则,要看运气了。

:)

B8层 发表时间: 11/20 10:15

回复: 寒枫 [ceo_8008]   论坛用户   登录
谢谢你,286

因为我们计算机组成和结构、操作系统还有网络等等都还没学

所以我什么都不知道

课外有看了一点,还是很肤浅的很

有些东西就是无法融会贯通,象这程序语言和操作系统的背景更是陌生

你这么一说,我理解了~~~

:)



B9层 发表时间: 11/20 16:10

回复: TomyChen [quest]   版主   登录
我回复一下,看时间...

B10层 发表时间: 10-09-01 23:36

论坛: 编程破解

20CN网络安全小组版权所有
Copyright © 2000-2010 20CN Security Group. All Rights Reserved.
论坛程序编写:NetDemon

粤ICP备05087286号