Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb28d37d

Browse files
committed
Add basic hash table implementation for person structs
Introduces a hash table in C for storing and managing person_t structs, including creation, insertion, lookup, deletion, and printing functions. Adds cperson.c/h for person struct management and hash_table.c/h for hash table logic using open addressing.
1 parent1ada915 commitb28d37d

File tree

4 files changed

+177
-0
lines changed

4 files changed

+177
-0
lines changed

‎HashTable/cperson.c‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/**
2+
* @file cperson.c
3+
* @author Xuhua Huang
4+
* @brief Implementation of functions for the CPerson struct.
5+
* @version 0.1
6+
* @date 2025-06-25
7+
*
8+
* @copyright Copyright (c) 2025
9+
*
10+
*/
11+
12+
#include"cperson.h"
13+
#include<stdlib.h>
14+
#include<string.h>
15+
16+
person_t*DELETED_NODE= (person_t*)(0xFFFFFFFF);// Unsafe, but illustrative
17+
18+
person_t*create_person(constchar*name,intage) {
19+
person_t*new_person= (person_t*)malloc(sizeof(person_t));
20+
if (new_person) {
21+
strncpy(new_person->name,name,sizeof(new_person->name)-1);
22+
new_person->name[sizeof(new_person->name)-1]='\0';
23+
new_person->age=age;
24+
}
25+
returnnew_person;
26+
}
27+
28+
voiddelete_person(person_t*person) {
29+
if (person) {
30+
free(person);
31+
}
32+
}

‎HashTable/cperson.h‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
/**
2+
* @file cperson.h
3+
* @author Xuhua Huang
4+
* @brief Define a C-style struct for a person.
5+
* @version 0.1
6+
* @date 2025-06-25
7+
*
8+
* @copyright Copyright (c) 2025
9+
*
10+
*/
11+
12+
#ifndefCPERSON_H
13+
#defineCPERSON_H
14+
15+
typedefstructCPerson {
16+
charname[100];
17+
intage;
18+
}person_t;
19+
20+
externperson_t*DELETED_NODE;// Pointer to a deleted node, used in hash table operations
21+
22+
#endif// !CPERSON_H

‎HashTable/hash_table.c‎

Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
/**
2+
* @file hash_table.c
3+
* @author Xuhua Huang
4+
* @brief
5+
* @version 0.1
6+
* @date 2025-06-25
7+
*
8+
* @copyright Copyright (c) 2025
9+
*
10+
*/
11+
12+
#include"hash_table.h"
13+
14+
#include<stdio.h>
15+
#include<string.h>
16+
17+
staticperson_t*hash_table[HASH_TABLE_SIZE];
18+
19+
unsignedinthash(constchar*constname) {
20+
intlength=strnlen(name,MAX_NAME_LENGTH);
21+
unsignedinthash_value=0;
22+
for (inti=0;i<length;++i) {
23+
hash_value+=name[i];
24+
hash_value= (hash_value*name[i]) %HASH_TABLE_SIZE;
25+
}
26+
returnhash_value;
27+
}
28+
29+
voidinit_hash_table() {
30+
for (inti=0;i<HASH_TABLE_SIZE;++i) {
31+
hash_table[i]=NULL;
32+
}
33+
}
34+
35+
boolinsert_to_table(constperson_t*constptr) {
36+
if (!ptr)return false;
37+
intindex=hash(ptr->name);
38+
for (inti=0;i<HASH_TABLE_SIZE;++i) {
39+
inttry_index= (i+index) %HASH_TABLE_SIZE;
40+
if (hash_table[try_index]==NULL) {
41+
hash_table[try_index]= (person_t*)ptr;
42+
return true;
43+
}
44+
}
45+
return false;
46+
}
47+
48+
person_t*hash_table_lookup(constchar*constname) {
49+
intindex=hash(name);
50+
for (inti=0;i<HASH_TABLE_SIZE;++i) {
51+
inttry_index= (i+index) %HASH_TABLE_SIZE;
52+
if (hash_table[try_index]==NULL)returnNULL;
53+
if (hash_table[try_index]==DELETED_NODE)continue;
54+
if (strncmp(hash_table[try_index]->name,name,MAX_NAME_LENGTH)==0) {
55+
returnhash_table[try_index];
56+
}
57+
}
58+
returnNULL;
59+
}
60+
61+
person_t*del_from_table(constchar*constname) {
62+
intindex=hash(name);
63+
for (inti=0;i<HASH_TABLE_SIZE;++i) {
64+
inttry_index= (i+index) %HASH_TABLE_SIZE;
65+
if (hash_table[try_index]==NULL)returnNULL;
66+
if (hash_table[try_index]==DELETED_NODE)continue;
67+
if (strncmp(hash_table[try_index]->name,name,MAX_NAME_LENGTH)==0) {
68+
person_t*temp=hash_table[try_index];
69+
hash_table[try_index]=DELETED_NODE;
70+
returntemp;
71+
}
72+
}
73+
returnNULL;
74+
}
75+
76+
voidprint_table() {
77+
printf("\nStart %s\n",__FUNCTION__);
78+
for (inti=0;i<HASH_TABLE_SIZE;++i) {
79+
if (hash_table[i]==NULL) {
80+
printf("\t%i\t---\n",i);
81+
}elseif (hash_table[i]==DELETED_NODE) {
82+
printf("\t%i\t---<deleted>\n",i);
83+
}else {
84+
printf("\t%i\t%s\n",i,hash_table[i]->name);
85+
}
86+
}
87+
printf("End %s\n",__FUNCTION__);
88+
}

‎HashTable/hash_table.h‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/**
2+
* @file hash_table.h
3+
* @author Xuhua Huang
4+
* @brief Practice of hash table in C++23 after lecture of Data Structures and Algorithms.
5+
* Constant operation time of O(1) with Open Addressing and External Chamber.
6+
*
7+
* @version 0.1
8+
* @date 2025-06-25
9+
*
10+
* @copyright Copyright (c) 2025
11+
*
12+
*/
13+
14+
#ifndefHASH_TABLE_H
15+
#defineHASH_TABLE_H
16+
17+
#include"cperson.h"
18+
#include<stdbool.h>
19+
20+
#defineHASH_TABLE_SIZE 10
21+
#defineMAX_NAME_LENGTH 100
22+
23+
typedefstructHashTableEntry {
24+
person_tperson;
25+
boolisOccupied;// Flag to check if the entry is occupied
26+
}hash_table_entry_t;
27+
28+
unsignedinthash(constchar*constname);
29+
voidinit_hash_table();
30+
boolinsert_to_table(constperson_t*constptr);
31+
person_t*hash_table_lookup(constchar*constname);
32+
person_t*del_from_table(constchar*constname);
33+
voidprint_table();
34+
35+
#endif// !HASH_TABLE_H

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp