#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++; }进行时间复杂度分析并写出算法主要思想

该代码实现的是一个简单的哈希表，主要思想是将字符串类型的ID转换为一个整型的哈希值，通过哈希值将记录存储在相应的位置中。具体的时间复杂度分析如下：

1. 哈希函数的复杂度为O(1)，因为只需要对字符串进行一次遍历，所以时间复杂度为O(1)。

2. 插入操作：在哈希表中插入一个记录时，需要先计算出该记录在哈希表中的位置，然后将其插入到该位置的链表中，这个过程需要遍历链表，时间复杂度为O(n)，其中n为该链表长度。因为哈希表的长度为Tablesize，所以插入操作的总时间复杂度为O(n*Tablesize)。

3. 查找操作：查找操作需要先计算出目标记录在哈希表中的位置，然后遍历该位置的链表查找目标记录，时间复杂度为O(n)，其中n为该链表长度。

因此，该算法的时间复杂度为O(n*Tablesize)，其中n为链表长度，Tablesize为哈希表大小。