#include <stdio.h> #include <string.h> #define Tablesize 1000005 int zzt[Tablesize],count; void insert(char *ID, int distance); struct Record { char ID[19]; int distance; int he; }Record; struct Record records[Tablesize]; int hash(char *ID); int find(char *ID); int main() { char ID[19]; for (int i = 0; i < sizeof(zzt) / sizeof(zzt[0]); i++) { zzt[i] = -1;} int n, k,m,distance; scanf("%d %d", &n, &k); for (int i = 0; i < n; i++) { scanf("%s %d", ID, &distance); if (distance < k) distance = k; insert(ID, distance); } scanf("%d", &m); int t = -1; for (int i = 0; i < m; i++) { scanf("%s", ID); t = find(ID); if (t == -1) printf("No Info\n"); else printf("%d\n", records[t].distance); } } int find(char *ID) { int h = hash(ID); for (int i = zzt[h]; i != -1; i = records[i].he) if (!strcmp(records[i].ID, ID)) return i; return -1; } int hash(char *ID) { long int yy = 0; for (int i = 0; i < 17; i++) yy = 10 * yy + (ID[i] - '0'); return yy%Tablesize; } void insert(char *ID, int distance) { int o = hash(ID); for (int i = zzt[o]; i != -1; i = records[i].he) { if (!strcmp(records[i].ID, ID)) { records[i].distance= records[i].distance+distance; return 0; } } records[count].distance = records[count].distance+distance; strncpy(records[count].ID, ID, 18); records[count].he = zzt[o]; zzt[o] = count++; }写出算法的主要思想,数据结构定义与分析,可能存在的问题与解决方法和创新改进的地方
时间: 2024-03-11 07:44:00 浏览: 24
该算法的主要思想是使用哈希表来实现字符串的快速查找和插入。具体来说,将字符串类型的ID转换成一个整型的哈希值,通过哈希值将记录存储在相应的位置中,以实现O(1)时间复杂度的查找和插入。
数据结构定义:
1. zzt数组:用于存储哈希表的头指针,即每个哈希值对应的链表的首个元素的下标。
2. Record结构体:用于存储每个记录的ID和distance信息,其中he表示在哈希表中与该记录哈希值相同的下一个记录的下标。
3. records数组:用于存储所有的记录信息。
算法分析:
1. 哈希函数的复杂度为O(1),因为只需要对字符串进行一次遍历,所以时间复杂度为O(1)。
2. 插入操作:在哈希表中插入一个记录时,需要先计算出该记录在哈希表中的位置,然后将其插入到该位置的链表中。如果该位置已经存在相同ID的记录,则将其distance相加,否则将该记录插入到链表的首部。
3. 查找操作:查找操作需要先计算出目标记录在哈希表中的位置,然后遍历该位置的链表查找目标记录,时间复杂度为O(n),其中n为该链表长度。
可能存在的问题与解决方法:
1. 哈希值冲突:如果两个不同的ID计算出的哈希值相同,就会出现哈希值冲突。这时需要使用链表来解决冲突,将相同哈希值的记录存储在同一个链表中。
2. 重复插入:如果插入一个已经存在的ID,需要将其distance相加,否则会造成重复插入的问题。
创新改进的地方:
1. 可以使用更高效的哈希函数,例如MD5、SHA等。
2. 可以使用开放地址法来解决哈希值冲突,而不是使用链表。开放地址法可以提高查找效率,但需要更多的空间来存储哈希表。
3. 可以使用数据结构优化算法,例如平衡树、跳表等来实现快速的查找和插入。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![image/gif](https://img-home.csdnimg.cn/images/20210720083352.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)