一些小的问题2

自己实现strcpy、strcat、strlen和strcmp。

注意，这里的 my_strcpy 和 my_strcat 函数的第一个参数是目标字符串，第二个参数是源字符串。另外，my_strcmp 函数的返回值为0表示两个字符串相等，小于0表示前者小于后者，大于0表示前者大于后者。

// 实现strcpy函数
char *my_strcpy(char *dest, const char* src) {
    char *p = dest;
    while((*p++ = *src++) != '\0');
    return dest;
}

// 实现strcat函数
char *my_strcat(char *dest, const char *src) {
    char *p = dest;
    while(*p != '\0') p++;
    while((*p++ = *src++) != '\0');
    return dest;
}

// 实现strlen函数
size_t my_strlen(const char *s) {
    size_t len = 0;
    while(*s != '\0') {
        len++;
        s++;
    }
    return len;
}

// 实现strcmp函数
int my_strcmp(const char *s1, const char *s2) {
    while(*s1 == *s2 && *s1 != '\0' && *s2 != '\0') {
        s1++;
        s2++;
    }
    return *s1 - *s2;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

哈希冲突

哈希冲突指的是在将不同的键映射到哈希表中同一个槽位时发生的冲突。当两个或多个键被映射到同一槽位时，就会发生哈希冲突。

解决哈希冲突的方法通常有以下几种：

链接法（Separate Chaining）：将哈希表中每个槽位看作是一个桶(bucket)，可以使用链表、数组等数据结构将多个键值对存储在同一个桶中。
优点：实现简单，适用于各种类型的键值对，并且能够有效地避免哈希冲突。
缺点：需要额外的内存空间来存储桶，而且访问某个键值对时需要扫描整个桶，时间复杂度较高。

开放定址法（Open Addressing）：当发生冲突时，通过探测（也称为再散列）在哈希表中寻找下一个可用的槽位。
优点：不需要额外的内存空间，存储更紧密；查找速度快，因为只需要进行少量的计算即可找到数据。
缺点：容易出现聚集，产生连锁反应，导致性能降低。

布隆过滤器（Bloom Filter）：一种空间效率很高的概率型数据结构，能够快速判断某个元素是否在集合中。
优点：存储空间利用率高，适合处理大规模数据；查询速度快，只需要进行少量的计算即可。
缺点：存在误判率，可能会把不属于集合的元素错误地判断为属于集合。

选择解决哈希冲突的方法应根据实际情况来决定。如果内存空间充足、数据量较小且查询频繁，则链表法是一个不错的选择；如果内存空间紧张、数据量较大且查询相对较少，则开放定址法更为适合；如果需要处理海量数据，则布隆过滤器是一个常用的选择。

红黑树

红黑树是一种自平衡二叉查找树，它具有以下几个基本特征：

每个节点要么是红色的，要么是黑色的。

1. 根节点是黑色的。
2. 每个叶子节点（NIL节点，空节点）是黑色的。
3. 如果一个节点是红色的，则它的子节点必须是黑色的（反之不一定成立）。
4. 任意一条从根到叶子节点的路径上不能出现连续两个红色节点，但可以出现连续两个黑色节点。

通过这些规则，红黑树保证了它的高度始终是对数级别的，以保证其在最坏情况下仍能保持较好的时间复杂度。同时，红黑树还具有平衡性、插入和删除操作相对简单等优点，因此在计算机科学领域中得到了广泛的应用。

红黑树的基本特征

红黑树的插入操作可能会破坏原有的平衡，需要进行调整以满足红黑树的五个基本特征。插入过程中需要考虑以下几种情况：

1. 插入节点是根节点：直接将该节点染成黑色即可。
2. 插入节点的父节点是黑色：不用进行任何操作，红黑树仍然保持平衡。
3. 插入节点的父节点和叔叔节点都是红色：
   • 将父节点和叔叔节点染成黑色；
   • 将祖父节点染成红色；
   • 将当前节点指向祖父节点，再从步骤 2 开始重新判断。
4. 插入节点的父节点是红色，叔叔节点是黑色（或者为空）：
   • 如果插入节点是其父节点的左子节点，而父节点又是祖父节点的左子节点，那么只需要对祖父节点进行右旋操作；
   • 如果插入节点是其父节点的右子节点，而父节点又是祖父节点的右子节点，那么只需要对祖父节点进行左旋操作；
   • 如果插入节点是其父节点的右子节点，而父节点是祖父节点的左子节点，那么需要先对父节点进行左旋操作，再对祖父节点进行右旋操作；
   • 如果插入节点是其父节点的左子节点，而父节点是祖父节点的右子节点，那么需要先对父节点进行右旋操作，再对祖父节点进行左旋操作。
5. 插入节点的父节点是红色，叔叔节点为空，但祖父节点不为空：
   • 对于第 4 种情况的四种旋转情况，我们可以将叔叔节点看成黑色的空节点。

插入节点后的旋转操作可能会继续破坏红黑树的平衡，因此需要不断地进行调整，直到满足红黑树的五个基本特征。

红黑树的删除

红黑树的删除操作可能会破坏原有的平衡，需要进行调整以满足红黑树的五个基本特征。删除过程中需要考虑以下几种情况：

1. 删除节点是叶子节点：直接删除即可，不会影响红黑树的平衡。
2. 删除节点只有一个子节点：将子节点替代该节点即可，不会影响红黑树的平衡。
3. 删除节点有两个子节点：
   • 找到删除节点的后继节点（即删除节点右子树中的最小节点）或前驱节点（即删除节点左子树中的最大节点），将其值拷贝到删除节点上，并将删除节点指针指向后继节点或前驱节点；
   • 将后继节点或前驱节点视为要删除的节点，再按照删除节点只有一个子节点或者是叶子节点的情况进行处理。
4. 删除节点是红色的：
   • 直接删除即可，不会影响红黑树的平衡。
5. 删除节点是黑色的：
   • 如果删除节点的兄弟节点是红色的，则可以通过旋转操作将其变成黑色的，然后从步骤 6 开始重新判断；
   • 如果删除节点的兄弟节点是黑色的，并且其两个子节点都是黑色的，则可以将兄弟节点染成红色，然后将指针指向其父节点，并重新从步骤 5 开始判断；
   • 如果删除节点的兄弟节点是黑色的，且左子节点是红色的、右子节点是黑色的，则可以对兄弟节点进行左旋操作，使得其左子节点变成兄弟节点，然后从步骤 6 开始重新判断；
   • 如果删除节点的兄弟节点是黑色的，且右子节点是红色的，则可以对兄弟节点进行右旋操作，使得其右子节点变成兄弟节点，然后从步骤 6 开始重新判断；
   • 如果删除节点的兄弟节点是黑色的，且左子节点是黑色的、右子节点是红色的，则可以将兄弟节点染成与其父节点相同的颜色，然后再将其右子节点染成黑色，最后对兄弟节点进行左旋操作，使得其左子节点变成新的兄弟节点，然后重新从步骤 5 开始判断。

删除节点后的旋转操作可能会继续破坏红黑树的平衡，因此需要不断地进行调整，直到满足红黑树的五个基本特征。

缓冲区的内容会写回磁盘通常有以下几种情况：

• 用户主动调用 fflush 或者 fclose 函数：当我们使用 fwrite 函数向文件中写入数据时，写入的数据实际上是先被存储到缓冲区中，并没有直接写入磁盘。此时如果用户调用 fflush 函数或者 fclose 函数，则会将缓冲区中的数据强制刷新到磁盘上。

• 缓冲区满：当缓冲区的容量达到一定的阈值时，系统会自动将缓冲区中的数据写回磁盘。

• 程序结束或者异常终止：当程序正常结束或者遇到异常终止时，系统会把缓冲区中的所有数据一次性写回磁盘，以保证数据的完整性和可靠性。

需要注意的是，缓冲区中的数据并不是即时写回磁盘的，而是在满足一定条件下才会进行写入操作。因此，在进行文件读写操作时，特别是涉及到重要数据的写入时，建议及时进行缓冲区刷新操作，以保证数据的安全性。