C语言复习-数据结构和算法

---

1.基础知识

1.1 时间复杂度

判断一个程序的时间复杂度主要涉及对程序结构的分析和对其算法的理解。以下是一些基本的指导原则和步骤：

1. 识别最影响时间的部分
   通常程序中的一小部分代码（如循环或递归调用）会占据大部分运行时间。专注于这些部分。

2. 计算循环次数

• 单层循环：如果有一个基于n的单层循环（n是输入大小），时间复杂度通常是O(n)。
• 嵌套循环：对于嵌套循环，时间复杂度是每层循环复杂度的乘积。例如，两个嵌套的n大小的循环将有O(n²)的时间复杂度。
• 不等循环：如果循环的次数随每次迭代而减少，可能是一个O(n²)的情况。（例如，第一个循环n次，第二个循环n-1次，依此类推）
• 等比循环：如果循环的次数随每次迭代而增加且和2的倍数有关，可能是一个O(log n)的情况。

3. 递归调用
   递归函数的时间复杂度取决于递归调用的次数和每次调用的复杂度。例如，二分查找的递归实现通常有O(log n)的时间复杂度。

4. 顺序执行的多部分
   如果代码有几个部分顺序执行，总的时间复杂度是所有部分中最大的那个。例如，一个O(n)的循环后跟一个O(1)的操作，总的时间复杂度仍然是O(n)。

5. 并行和分支
   如果代码分支不影响操作的总数（如if-else语句），它们通常不影响总体时间复杂度。

6. 数据结构的影响
   考虑数据结构对操作效率的影响。例如，数组和链表的插入、删除、搜索操作具有不同的时间复杂度。

7. 忽略非主导项和常数
   在大致估算时，可以忽略常数因子和非主导项。例如，O(2n)简化为O(n)，O(n² + n)简化为O(n²)。

1.2 正码，反码和补码

• 反码：正数的反码是其本身；负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

• 补码：正数的补码是其本身；负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后+1。

补码的本质：
   补码本质上是为了解决减法运算的问题，在计算机中，所有的运算都是加法运算，减法运算是通过加法运算来实现的。

比如：5和-5在有符号整型中的表示为0101和1011，但是5+（-5）=0010而不是0，这样补码才会出现。-5的补码为1011，5的补码为0101，相加得到0000。（这里的进位1被舍弃了）

补码溢出：
   补码可以解决减法运算的问题，但是也会出现溢出的问题。两个补码相加后，如果最高位的进位不等于进位前的最高位，就会出现溢出。
   如果两个正数相加，结果为负数，就会出现溢出。
   如果两个负数相加，结果为正数，也会出现溢出。

1.3 哈希表

哈希表是一种数据结构，它提供了键（key）和值（value）的映射关系。哈希表的实现是基于数组的，它通过哈希函数将键映射到一个索引，然后将值存储在数组中的该索引位置。哈希表的查找、插入和删除操作的时间复杂度都是O(1)。

哈希表的实现有很多种，其中最常见的是使用数组和链表的组合。数组用于存储值，链表用于解决哈希冲突（即两个不同的键映射到了同一个索引）的问题。

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct node {
    int key;
    int value;
    struct node* next;
} Node;

// 定义哈希表结构体
typedef struct {
    Node** buckets; // 哈希桶数组
    int size;       // 哈希表的大小
} HashTable;

// 创建新节点
Node* createNode(int key, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 创建哈希表
HashTable* createHashTable(int size) {
    HashTable* ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->buckets = (Node**)malloc(sizeof(Node*) * size);
    for (int i = 0; i < size; i++) {
        ht->buckets[i] = NULL;
    }
    return ht;
}

// 哈希函数
int hashFunction(int key, int size) {
    return key % size;
}

// 插入键值对到哈希表
void insert(HashTable* ht, int key, int value) {
    int index = hashFunction(key, ht->size);
    Node* newNode = createNode(key, value);
    // 解决冲突，使用链表头插法
    newNode->next = ht->buckets[index];
    ht->buckets[index] = newNode;
}

// 在哈希表中查找键
Node* search(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);
    Node* temp = ht->buckets[index];
    while (temp) {
        if (temp->key == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

// 测试哈希表
int main() {
    HashTable* ht = createHashTable(10); // 创建大小为10的哈希表
    insert(ht, 1, 100);
    insert(ht, 2, 200);
    insert(ht, 12, 1200); // 将会与键1冲突
    
    Node* result = search(ht, 12);
    if (result != NULL) {
        printf("找到键 %d，值为 %d\n", result->key, result->value);
    } else {
        printf("键不存在\n");
    }
    
    return 0;
}

Donate