数据结构实验--哈希表设计

               查找的应用

实验要求

        为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序代码，以便在实验课中完成老师所布置的实验内容。

实验目的

   掌握查找法的工作原理及应用过程，利用其工作原理完成上述实验题目中的内容。

实验设计原理

1.创建名字结构、哈希表。

2.将姓名数组初始化，把字符串中字符的ASCLL码相加，形成每个姓名的关键字。

3.创建哈希表，定义哈希函数，现实哈希列表函数，确定处理冲突方法。

实验内容

      哈希表设计

程序代码及注释

#include

#include

#include

#include

#include

#define MAX_NUM 26  //最大数据笔数

#define PRIME 23  //MAX_NUM的质数

#define NOTEXISTED NULL

/*定义数据结构*/

typedef struct Person 

{

    long id;

    char name[21];

    struct Person *link;

} Student;

/*建立哈希链表*/

Student *Hashtab[MAX_NUM];

/*函数原形声明*/

int Hash(char str[]);  //哈希函数

void insert(); //输入信息函数

Student *search(Student *,Student *);  //查找函数

void query(); //查询节点函数

void show(); //显示信息函数

void menu(); //选择菜单函数

void main()

{

    int i;

    for ( i = 0; i< MAX_NUM; i++)  //初始化哈希链表

        Hashtab[i] = NULL;

    menu();  //调用显示选择菜单函数 

}

void menu() //选择菜单函数

{

   char *menu_prompt =

        "学号查询哈希表\\n"

        "\\n"

        "1.输入信息\\n"

        "2.显示信息\\n"

        "3.查找\\n"

        "4.退出\\n"

        "\\n"

        "选择:";

    printf("%s",menu_prompt);

    switch (getchar())

        {

            case '1' :

                insert();

                break;

            case '2' :

                show();

                break;

            case '3' :

                query();

                break;

            case '4' :

                puts("谢谢使用！ ^_^");

                break;

            default :

                puts("Invalid choice !!");

        }

}

int Hash(char str[]) //哈希函数，除留取余

{ 

  long val=0;

  char p[20],*p1;

  strcpy(p,str);

  p1=p;

  while(*p1!='\\0')

     val=val+*p1++; //将字符串中的所有字符对应的ASCII值相加

  return(val%MAX_NUM);

}

void insert()  //输入信息函数

{

    Student  *newnode;

    int index;

    newnode = ( Student *)malloc(sizeof(Student));    //输入记录

newnode->link = NULL;

    printf("学号: ");

scanf("%ld",&newnode->id);

    printf("名字: ");

scanf("%s",newnode->name);

    index = Hash(newnode->name);    //利用哈希函数求得记录地址

    if ( Hashtab[index] == NULL )  //判断该链表是否为空，若为空则建立链表

    {

        Hashtab[index] = newnode;

        printf("信息录入成功！\\n");

        getchar();getchar();     //接收回车

        system("cls"); 

        menu();

    }

    else

    {

        if ((search(Hashtab[index],newnode)) == NOTEXISTED) //调用search函数

        {

            newnode->link = Hashtab[index];

            Hashtab[index] = newnode;

            printf("信息录入成功！\\n");

            getchar();getchar();

            system("cls"); 

            menu();

        }

        else

            printf("记录已存在！\\n");

            getchar();getchar();

            system("cls"); 

            menu();

    }

}

Student *search(Student *linklist,Student *Node) 

 /*search函数，如找到节点则返回指向该节点的指针*/

{

    Student *ptr = linklist;

while (ptr->name != Node->name && ptr->link != NULL)

        ptr = ptr->link;

    if ( ptr == NULL )

        return NOTEXISTED;

    else

        return ptr;

}

void query() //查询节点函数

{

    Student *query_node;

    long index;

    query_node = (Student *)malloc(sizeof(Student));

    printf("输入所要查找姓名 : ");

scanf("%s",&query_node->name);

index = Hash(query_node->name);

    query_node = search(Hashtab[index],query_node);  //查找节点函数

    if ( query_node == NOTEXISTED )

        printf("记录不存在！\\n");

    else

    {

        printf("学号: %ld  姓名 : %s\\n

        query_node->id,query_node->name);

        getchar();getchar();

        system("cls"); 

        menu();

    }

}

void show() //显示信息函数，从哈希表一一查找是否有节点存在

{

    int i;

    Student *ptr;

    puts("学号      姓名");

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

    {

        if ( Hashtab[i] != NULL )//表不为空，则将整个表显示出来

        {

            ptr = Hashtab[i];

            while (ptr) 

            {

                printf("%-5ld    %15s\\n",ptr->id,ptr->name);

                ptr = ptr->link;

            }

        }

    }

    getchar();getchar();

    system("cls"); 

    menu();

}

运行结果

2.录入信息：02  bb   运行：

3.录入信息：03 cc   运行：

4．再次输入 03 cc：

5.选择2：

6.选择3，输入bb：

问题及解决方法

1.问题：输出信息时，由于姓名的长度不同，造成输出时较乱，不美观

  解决方法：右对齐输出名字

2.问题：各功能显示总是一闪而过，就回到菜单界面

  解决方法：在每个功能实现后，加入“getchar();”，等待回车输入后再调用菜单界面，与平时的习惯相同。