如何解决我所做的代码中哈希中的冲突？目前无法只搜索NG CHEA YEAT的ID
如何解决我所做的代码中哈希中的冲突？目前无法只搜索NG CHEA YEAT的ID
提问于 2022-04-12 05:32:15
我有以下文本文件
1171203258:HOSSAIN, MARUF
1181202660:KUHAN RAJ A/L TAMIL CHEL WAM
1181203465:PONG KAI SUN
1191102443:FAIZA OSAMA ABDALLA HASHIM
1201302289:LEE JIA WEI
1201302368:SHEIKH, AHNAF AZMAIN
1201100584:HI CHIA LING
1201101509:NG CHEA YEAT
1191103201:PHUAH CHEE HAOU
1201100879:MOSTAFA ARABY MADBOULY AHMED
1191103215:TONG JUN YANG
1191103119:ANG QIZHENG
1171302286:DARWIN KUMAR A/L MUNIAN
1181101192:HAIZUN NAJWA BINTI MOHD RIFIN
1201100926:NG XUE NIE
1191302417:ALMARHOON, ALI HUSSAIN A
1201100225:HEMAN RAO A/L SUBRAMANIAM
1181100823:LIM ZHEN BANG
1161202587:SOHEIL PRAKASAN SUPPAN
1201100603:AVINASH MURALI
1181101858:CHEAH KOK YEW
1191103071:GAN WEI TONG
1201100301:KEVIN THAM ZHENG YIT
1201100648:LIM CHER AIK
1201302222:SHIVAA RUTRAN A/L NAGATHEESAN
1201100779:TAN WEI XIANG
1191100919:WONG HONG WEI我现在拥有的代码工作得很好，但是我认为在哈希中有冲突。
以下是我到目前为止所拥有的：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MDIR 27 //size of list
#define MBUFF 256
#define MHASH 109 //hash function is %109
#define MNAME 40
struct List{
char name[40];
int studID;
};
//function prototype
int comparator(const void* p, const void* q){
return strcmp(((struct List*)p)->name,((struct List*)q)->name);
}
int readData(struct List dir[]);
int hashfunc(char *name);
void hash(struct List dir[], int ndir,
int hashtable[]);
int search(char *key,
struct List s[], int hashtable[]);
//main function
int main(){
int ndir, result, hashtable[MHASH];
int count;
int i;
int j;
struct List s[27];
char temp[27];
char query[40];
FILE *fptr;
fptr = fopen("rec.txt", "r+");
if (fptr != NULL) {
printf("File created successfully!\n");
}
else {
printf("Failed to create the file.\n");
// exit status for OS that an error occurred
return -1;
}
for(count = 0; count < 27; count++){
fscanf(fptr,"%d", &s[count].studID);
fgets(s[count].name,40,fptr);
}Q排序
qsort(s,27,sizeof(struct List),comparator);打印排序后的名称，然后继续散列搜索。
//printing sorted name
printf("Sorted Names\n");
for(i=0;i<27;i++){
printf("%d%s\n", i+1, s[i].name);
}
fclose(fptr);搜索部分的散列
ndir=readData(s);
hash(s,ndir,hashtable);
puts("\nName to search>>");
fgets(query,MNAME-1,stdin);
query[strlen(query)-1]='\0';
result=search(query,s,hashtable);
if(result==-1)
printf("Not Found");
else
printf("%s's ID is %d\n",
s[result].name, s[result].studID);
return 0;
}读取功能
int readData(struct List dir[]){
FILE *fdir=fopen("rec.txt","r");
char buff[MBUFF];
int i=0;
while(i<MDIR && fgets(buff,MBUFF-1,fdir)){
dir[i].studID=atol(strtok(buff,":"));
strcpy(dir[i].name,strtok(NULL, "\n"));
i++;
}
return(i);
}散列函数
int hashfunc(char *name){
long sum=0;
int k=0;
while(name[k]){
sum+=name[k];
k++;
}
return( (int) (sum % MHASH) );
}散列函数
void hash(struct List dir[], int ndir,
int hashtable[]){
int k;
int index;
for(k=0;k<ndir;k++){
index = hashfunc(dir[k].name);
hashtable[index]=k;
}
}搜索功能
int search(char *key, struct List dir[],
int hashtable[]){
int index=hashfunc(key);
int k=hashtable[index];
if(strcmp(key,dir[k].name)==0)
return(k);
else
return(-1);
}我不确定搜索部分会不会散列。
Stack Overflow用户
回答已采纳
发布于 2022-04-12 08:03:08
每当需要将数据行中的字段分开时，通常的方法是将整行数据作为字符串读入缓冲区(字符数组)。然后，使用最适合数据的方法将所需的内容从缓冲区中分离出来。或者使用一对指针对所需的文本进行括号，然后在指针之间复制字符。您可以使用字符串函数(如strchr() )将进程自动化，以在缓冲区中定位':'。您还可以使用字符串函数(如strtok() )将缓冲区拆分为任意给定的分隔符集上的标记。
然而，这里有一个更简单的方法。由于行中有固定的studID和name格式，所以可以简单地使用sscanf()。
#include <stdio.h>
#include <stdlib.h>
#define MXSTUD 30 /* if you need a constant, #define one (or more) */
#define MXNAME 40
typedef struct list { /* adding typedef for convenience */
char name[MXNAME];
unsigned studID;
} list;
...
int main (int argc, char **argv) {
int count = 0; /* count of students */
char buf[MXNAME * 2]; /* temprorary storage for line */
list s[MXSTUD] = {{ .name = "" }}; /* list array initialized all 0 */
/* open filename given as 1st argument or "rec.text" if none given */
FILE *fptr = fopen (argc > 1 ? argv[1] : "rec.text", "r");
if (!fptr) { /* validate file open for reading */
fputs ("error: file open failed\n", stderr);
return 1;
}
while (fgets (buf, sizeof buf, fptr)) { /* read each line into buf */
/* separate studID and name using sscanf() */
if (sscanf (buf, "%u:%39[^\n]", &s[count].studID, s[count].name) == 2) {
count += 1; /* increment count on success */
}
}
...这就是读取每一行数据并将该行分隔到studID和name中所需的全部内容，将每一行存储在结构的list数组中。
使用qsort()对进行排序
无论您是否有包含对象的数组或已分配的内存块，qsort()都提供了一种简单有效的方法来对其进行排序。您需要做的就是编写一个compare()函数，告诉qsort()如何比较这些元素。qsort()比较函数的声明是：
int compare (const void *a, const void *b);`其中a和b是要比较的数组元素的简单指针。因此，在编写函数时，只需将a和b转换为适当的类型，并编写逻辑来比较这两个元素中您喜欢的任何内容。负返回意味着a排序在b之前，而正返回表示b排序在a之前。零返回意味着元素相等。
将a和b转换为const list * (您包括const，因为数据没有被修改，这使得编译器可以自由地进行更充分的优化)，您只需循环遍历每个name比较字符，并在两个字符不同或文件结束时返回。在这里，要按照s[]数组按name排序，可以这样做：
/* qsort compare function lexagraphically sorts words */
int compare (const void *a, const void *b)
{
/* a & b are pointers to adjacent list elements, (pointers to list) */
const list *sa = (const list *)a,
*sb = (const list *)b;
const char *na = sa->name, /* pointers to name in each element */
*nb = sb->name;
/* loop advancing a character in each word per-iteration */
for (;; na++, nb++) {
/* if characters differ or at end of either */
if (*na != *nb || !*na)
break;
}
return (*na > *nb) - (*na < *nb); /* return sort order */
}然后，要用list ( s[]数组)对qsort()数组进行排序，所需要的是：
qsort (s, count, sizeof *s, compare); /* sort array by name */将所有这些放在一个简短的程序中，从作为程序的第一个参数的文件名中读取(如果没有参数，默认情况下从"rec.text"读取)，您可以这样做：
#include <stdio.h>
#include <stdlib.h>
#define MXSTUD 30 /* if you need a constant, #define one (or more) */
#define MXNAME 40
typedef struct list { /* adding typedef for convenience */
char name[MXNAME];
unsigned studID;
} list;
/* qsort compare function lexagraphically sorts words */
int compare (const void *a, const void *b)
{
/* a & b are pointers to adjacent list elements, (pointers to list) */
const list *sa = (const list *)a,
*sb = (const list *)b;
const char *na = sa->name, /* pointers to name in each element */
*nb = sb->name;
/* loop advancing a character in each word per-iteration */
for (;; na++, nb++) {
/* if characters differ or at end of either */
if (*na != *nb || !*na)
break;
}
return (*na > *nb) - (*na < *nb); /* return sort order */
}
int main (int argc, char **argv) {
int count = 0; /* count of students */
char buf[MXNAME * 2]; /* temprorary storage for line */
list s[MXSTUD] = {{ .name = "" }}; /* list array initialized all 0 */
/* open filename given as 1st argument or "rec.text" if none given */
FILE *fptr = fopen (argc > 1 ? argv[1] : "rec.text", "r");
if (!fptr) { /* validate file open for reading */
fputs ("error: file open failed\n", stderr);
return 1;
}
while (fgets (buf, sizeof buf, fptr)) { /* read each line into buf */
/* separate studID and name using sscanf() */
if (sscanf (buf, "%u:%39[^\n]", &s[count].studID, s[count].name) == 2) {
count += 1; /* increment count on success */
}
}
qsort (s, count, sizeof *s, compare); /* sort array by name */
for (int i = 0; i < count; i++) { /* output results */
printf ("%2d %10u %s\n", i + 1, s[i].studID, s[i].name);
}
}(注意：，您只需在读取模式"r"中打开文件)
示例使用/输出
如果您的数据位于一个名为dat/studIDlist.txt的文件中，您将得到数据中的27名学生：
$ ./bin/studIDlist dat/studIDlist.txt
1 1191302417 ALMARHOON, ALI HUSSAIN A
2 1191103119 ANG QIZHENG
3 1201100603 AVINASH MURALI
4 1181101858 CHEAH KOK YEW
5 1171302286 DARWIN KUMAR A/L MUNIAN
6 1191102443 FAIZA OSAMA ABDALLA HASHIM
7 1191103071 GAN WEI TONG
8 1181101192 HAIZUN NAJWA BINTI MOHD RIFIN
9 1201100225 HEMAN RAO A/L SUBRAMANIAM
10 1201100584 HI CHIA LING
11 1171203258 HOSSAIN, MARUF
12 1201100301 KEVIN THAM ZHENG YIT
13 1181202660 KUHAN RAJ A/L TAMIL CHEL WAM
14 1201302289 LEE JIA WEI
15 1201100648 LIM CHER AIK
16 1181100823 LIM ZHEN BANG
17 1201100879 MOSTAFA ARABY MADBOULY AHMED
18 1201101509 NG CHEA YEAT
19 1201100926 NG XUE NIE
20 1191103201 PHUAH CHEE HAOU
21 1181203465 PONG KAI SUN
22 1201302368 SHEIKH, AHNAF AZMAIN
23 1201302222 SHIVAA RUTRAN A/L NAGATHEESAN
24 1161202587 SOHEIL PRAKASAN SUPPAN
25 1201100779 TAN WEI XIANG
26 1191103215 TONG JUN YANG
27 1191100919 WONG HONG WEI页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71837552
复制相关文章
相似问题
腾讯云开发者
