按文件名存储-哈希表

通过散列函数将数据值和它的存储位置联系起来。即通过精心地向表载入元素实现,从而提高访问速度。本例中采取的解决冲突的办法是建立一个链表,挂在这个位置的后面,所有散列函数值为这个位置的元素都添加到这个链表中,可以从头部插入也可以从尾部追加,甚至可以再这个位置后面再挂一个散列表。代码实现了将文件名按字母a-z分类,不区分大小写。先以数组存储各节点,当发生冲突后即将节点加入链表中。然后遍历显示所有的文件名。

/* a2z.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define HASHSIZE 26
#define FILENAMELENGTH 20
#define TRUE 1
#define FALSE 0

struct file {
        char name[FILENAMELENGTH];
        struct file *next;
};

struct file * files[HASHSIZE];

char case_insensitive(char ch)
{
        if (isupper(ch))
                return ch - 'A' + 'a';
        return ch;
}

void init(void)
{
        int i;
        for (i = 0; i < HASHSIZE; i++)
                files[i] = NULL;
}

int hash(char *s)
{
        return case_insensitive(s[0]) - 'a';
}

int search(char *s)
{
        int num = hash(s);
        if (files[num] != NULL) {
                struct file *p = files[num];
                while (p != NULL) {
                        if (strcmp(p->name, s) == 0)
                                return TRUE;
                        p = p->next;
                }
        }

        return FALSE;
}

void insert(char *s)
{
        if (search(s) == FALSE) {
                int num = hash(s);
                struct file *new_node = malloc(sizeof (struct file));
                strcpy(new_node->name, s);
                if (files[num] == NULL) {
                        files[num] = new_node;
                        files[num]->next = NULL;
                } else {
                        new_node->next = files[num];
                        files[num] = new_node;
                }
        }

        return;
}

void free_node(struct file *p)
{
        free(p);

        return;
}


void del_node(char *s)
{
        if (search(s) == TRUE) {
                struct file *p = files[hash(s)], *q;
                if (strcmp(p->name, s) == 0) {
                        q = p;
                        files[hash(s)] = p->next;
                        free_node(q);
                } else {
                        while (p != NULL) {
                                q = p;
                                p = p->next;
                                if (strcmp(p->name, s) == 0)
                                        free_node(q);
                        }
                }
        }

        return;
}


void del(int num)
{
        struct file *p =files[num], *q;
        while (p != NULL) {
                q = p;
                p = p->next;
                free(q);
        }

        return;
}

void destroy(void)
{
        int i;

        for (i = 0; i < HASHSIZE; i++)
                del(i);

        return;
}

void show(int num)
{
        struct file *p = files[num];
        if (p != NULL) {
                printf("For file begins with '%c': \n", num + 'a');
                while (p != NULL) {
                        printf("%s\n", p->name);
                        p = p->next;
                }
                printf("\n");
        }



}

void show_all(void)
{
        int i;
        for (i = 0; i < HASHSIZE; i++)
                show(i);

        return;
}

int main(void)
{
        char * file_name[] = {
                "apple", "because", "song", "Dan", "discuz", "cartoon",
                "nobody", "android", "information", "love", "like", "No",
                "nothing", "like", "alone", "nothing", "sizeof", "Yes",
        };

        int len = sizeof file_name / sizeof (char *);
        int i;
        for (i = 0; i < len; i++)
                insert(file_name[i]);
        show_all();

        printf("---------------------------------\n");
        del_node("like");
        show_all();
        destroy();

        return 0;
}

来看一下执行结果:

./az
For file begins with 'a':
alone
android
apple

For file begins with 'b':
because

For file begins with 'c':
cartoon

For file begins with 'd':
discuz
Dan

For file begins with 'i':
information

For file begins with 'l':
like
love

For file begins with 'n':
nothing
No
nobody

For file begins with 's':
sizeof
song

For file begins with 'y':
Yes

---------------------------------
For file begins with 'a':
alone
android
apple

For file begins with 'b':
because

For file begins with 'c':
cartoon

For file begins with 'd':
discuz
Dan

For file begins with 'i':
information

For file begins with 'l':
love

For file begins with 'n':
nothing
No
nobody

For file begins with 's':
sizeof
song

For file begins with 'y':
Yes

来源: http://blog.csdn.net/lvsi12/article/details/8266884

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据