针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序,并分析平均查找长度(姓名以汉语拼音形式,待填入哈希表的人名不低于30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。)
时间: 2023-06-05 21:47:11 浏览: 654
针对同班同学信息设计一个通讯录,包括学生姓名、学号、电话号码等信息。我们可以以学生姓名为关键字设计哈希表,并使用线性探测再散列法或链地址法处理冲突。具体步骤如下:
1. 设计哈希函数:我们可以将每个学生姓名转换成拼音形式,并计算其哈希值。例如,可以将每个字母的ASCII码相加,再取余数得到哈希值。
2. 建立哈希表:根据哈希函数,将每个学生的信息插入到哈希表中。如果发生冲突,可以使用线性探测再散列法或链地址法解决。
3. 查找操作:当需要查找某个学生的信息时,根据其姓名计算哈希值,并在哈希表中查找对应的记录。如果发生冲突,需要继续查找直到找到对应的记录。
4. 分析平均查找长度:平均查找长度是指在哈希表中查找一个记录时需要比较的次数的平均值。可以通过模拟多次查找操作,统计比较次数并计算平均值来得到。
以上是针对同班同学信息设计通讯录的基本步骤和方法。在实际操作中,还需要考虑数据的存储和管理、用户界面的设计等方面的问题。
相关问题
c语言程序设计针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序,并分析平均查找长度
好的,这是一个经典的哈希表设计问题。首先,我们需要定义一个学生信息的结构体,包括姓名、学号和电话号码等信息:
```c
typedef struct {
char name[30];
char id[20];
char phone[20];
} Student;
```
接下来,我们需要设计哈希函数,以学生姓名为关键字进行哈希。一个简单的哈希函数可以是将姓名转换为一个数字,然后取模得到哈希表的下标:
```c
int hash(char *name, int size) {
int sum = 0;
for (int i = 0; name[i]; i++) {
sum += name[i];
}
return sum % size;
}
```
其中,`size`是哈希表的大小,可以根据数据量进行设置。这里我们可以设置为100。
接下来,我们可以定义哈希表的结构体:
```c
#define SIZE 100
typedef struct {
Student *data[SIZE];
int count;
} HashTable;
```
其中,`data`是一个指针数组,每个指针指向一个学生信息的结构体。`count`表示哈希表中已经存储的学生信息数量。
接下来,我们可以定义哈希表的两个基本操作,即插入和查找。插入操作可以先根据哈希函数得到学生姓名对应的哈希表下标,然后将学生信息插入到指定位置。如果该位置已经被占用,则需要解决冲突。这里我们采用线性探测的方法,即向后依次查找,直到找到一个空闲位置为止。
```c
void insert(HashTable *table, Student *stu) {
int index = hash(stu->name, SIZE);
while (table->data[index]) {
index = (index + 1) % SIZE;
}
table->data[index] = stu;
table->count++;
}
```
查找操作也是先根据哈希函数得到学生姓名对应的哈希表下标,然后依次向后查找,直到找到对应的学生信息或者找到一个空闲位置为止。
```c
Student *find(HashTable *table, char *name) {
int index = hash(name, SIZE);
while (table->data[index]) {
if (strcmp(table->data[index]->name, name) == 0) {
return table->data[index];
}
index = (index + 1) % SIZE;
}
return NULL;
}
```
最后,我们可以编写一个测试程序,随机生成一些学生信息并插入哈希表,然后随机查找一些学生信息并计算平均查找长度:
```c
int main() {
srand(time(NULL));
HashTable table = {0};
for (int i = 0; i < 50; i++) {
Student *stu = malloc(sizeof(Student));
sprintf(stu->name, "student%d", rand() % 1000);
sprintf(stu->id, "id%d", rand() % 1000);
sprintf(stu->phone, "phone%d", rand() % 1000);
insert(&table, stu);
}
int total = 0;
for (int i = 0; i < 50; i++) {
char name[30];
sprintf(name, "student%d", rand() % 1000);
Student *stu = find(&table, name);
if (stu) {
total += 1;
}
}
printf("average search length: %lf\n", (double) table.count / total);
return 0;
}
```
注意,在插入和查找时,我们需要动态分配学生信息的内存,以便于存储。
以上就是一个简单的哈希表设计和实现过程,希望可以帮助到你!
用c语言写一个代码实现针对同班同学信息设计一个通讯录,学生信息有姓名,学号,电话号码等。以学生姓名为关键字设计哈希表,并完成相应的建表和查表程序,并分析平均查找长度(姓名以汉语拼音形式,待填入哈希表的人名不低于30个,自行设计哈希函数,用线性探测再散列法或链地址法处理冲突;在查找的过程中给出比较的次数。完成按姓名查询的操作。)
好的,以下是我给你提供的代码,其中包含了哈希表的建立、查找和哈希函数的设计。在本代码中,我使用的是链地址法处理哈希冲突。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASHSIZE 101 //哈希表长度,选择一个大质数
struct student {
char name[20];
int id;
char phone[12];
struct student *next;
};
struct student *hashtable[HASHSIZE];
int hash(char *name) //哈希函数,将姓名转化为数字
{
unsigned int hashval = 0;
while (*name != '\0')
hashval = *name++ + hashval * 31;
return hashval % HASHSIZE;
}
void insert(struct student *newstu) //向哈希表中插入新学生信息
{
int index = hash(newstu->name);
newstu->next = hashtable[index];
hashtable[index] = newstu;
}
void search(char *name) //按姓名查找学生信息
{
int index = hash(name);
struct student *p = hashtable[index];
int count = 0;
while (p != NULL) {
count++;
if (strcmp(p->name, name) == 0) {
printf("学生姓名:%s 学号:%d 电话号码:%s\n", p->name, p->id, p->phone);
printf("比较次数:%d\n", count);
return;
}
p = p->next;
}
printf("找不到该学生信息!\n");
}
int main()
{
int i;
char name[20], phone[12];
struct student *newstu;
//手动输入学生信息,也可以读取文件或从数据库中获取
for (i = 0; i < 30; i++) {
newstu = (struct student *)malloc(sizeof(struct student));
printf("请输入第%d个学生的姓名、学号和电话号码:", i + 1);
scanf("%s%d%s", newstu->name, &newstu->id, newstu->phone);
insert(newstu);
}
//按姓名查找学生信息
printf("请输入要查找的学生姓名:");
scanf("%s", name);
search(name);
return 0;
}
```
在上面的代码中,我们定义了一个结构体`student`,包含了学生的姓名、学号和电话号码等信息,同时也定义了`hashtable`哈希表数组。在`insert`函数中,我们将新学生信息插入到哈希表中,如果出现哈希冲突,我们使用链地址法将新学生信息挂在冲突的链表后面。在`search`函数中,我们按照哈希函数计算出学生姓名对应的哈希值,然后在哈希表中查找该学生信息,如果找到则输出学生信息和比较次数,否则输出“找不到该学生信息!”。
最后,我们可以在`main`函数中手动输入学生信息,也可以从文件或数据库中读取,然后按照学生姓名查找学生信息。在查找的过程中,我们可以通过输出比较次数来分析平均查找长度。