bool isOdd(int n)
{
	return (n % 2 != 0);
}

bool isOdd(int n)
{
	return (n & 0x1);//奇数的最后一位一定是1，掩码（mask）
}

bool isPowerOf2(int n)
{
	return (n & n-1) == 0;
}

#include "Vector.h" //""：搜索路径：当前目录 -> 系统的头文件包含的目录下
#include <stdio.h>  //<>：搜索路径：系统的头文件包含目录下
#include <stdlib.h>

int main(void)
{
    //创建空的动态数组
    Vector* v = vector_create();

    for(int i=0; i<200; i++)
    {
        push_back(v,i);
    }
    printf("push_finish\n");
    vector_destroy(v);
    printf("destroy_finish\n");
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

//头文件：类型的定义和API声明
#include <stddef.h>
#include <stdlib.h>

typedef int E;

typedef struct
{
    E* elements;
    int capacity;
    int size;
}Vector;

//函数声明
//构造函数
Vector* vector_create(void);

//析构函数
Vector* vector_destroy(Vector* v);

void push_back(Vector* v,E val);

#include "Vector.h"//""：搜索路径：当前目录 -> 系统的头文件包含的目录下

#define DEFAULT_CAPACITY 8
#define PREALLOC_MAX 1024 //提前申请的最大值

//构造函数（创建空的动态数组）
Vector* vector_create(void)
{
    Vector* v = malloc(sizeof(Vector));
    if(v==NULL)
    {
        printf("Error: malloc failed in vector_create!");
        exit(1);
    }
    E* p = malloc(DEFAULT_CAPACITY * sizeof(E));
    if(p == NULL)
    {
        free(v);//要将之前创建的v释放掉
        printf("Error: malloc failed in vector_create!");
        exit(1);
    }
    //设置基本参数
    v->elements = p;
    v->capacity = DEFAULT_CAPACITY;
    v->size = 0;

    return v;
}

//析构函数（释放动态数组）
Vector* vector_destroy(Vector* v)
{
    //从内到外释放（按照申请的相反顺序释放）
    free(v->elements);
    free(v);
}

void grow_capacity(Vector* v)
{
    int new_capacity = v->capacity < PREALLOC_MAX ?
        v->capacity * 2 : v->capacity+PREALLOC_MAX;
    
    //下面代码有问题，realloc失败会返回NULL，原来的内存空间不会被释放，造成内存泄漏
    //v->elements = realloc(v->elements,new_capacity * sizeof(E));
    
    //正确代码写法
    E* p = realloc(v->elements,new_capacity * sizeof(E));
    if(p == NULL)
    {
        printf("Error: realloc failed in grow_capacity!");
        exit(1);
    }

    v->elements = p;
    v->capacity = new_capacity;
}

void push_back(Vector* v,E val)
{
    //判断是否需要扩容
    if(v->size == v->capacity)
    {
        grow_capacity(v);
    }
    //添加元素val
    v->elements[v->size++] = val;
}

#include "hashmap.h"

int main(void)
{
    //创建空的哈希表
    HashMap* map = create_hashmap();

    //向哈希表写入数据
    put(map, "test", "123");
    put(map, "test1", "234");
    put(map, "test2", "345");
    put(map, "test3", "567");
    put(map, "test4", "678");
    put(map, "test5", "789");
    put(map, "test6", "345");
    put(map, "test7", "567");
    put(map, "test8", "678");
    put(map, "test9", "789");

    V val_2 = get(map,"test9");
    puts(val_2);

    put(map, "test2", NULL);
    put(map, "test8", "456");

    V val_1 = get(map,"test8");
    puts(val_1);

    map_remove(map,"test6");

    V val_3 = get(map,"test7");
    puts(val_3);

    if(get(map,"test6")==NULL)
        printf("empty!\n");
    else
        puts(val_3);

    // 销毁哈希表
    destroy_hashmap(map);
    printf("sucess!\n");

    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

#include <stdint.h>
#include <stdbool.h>
#define CAPACITY 10

typedef char* K;
typedef char* V;

// 键值对结点
typedef struct node_s {
  K key;
  V val;
  struct node_s* next;
} KeyValueNode;

typedef struct {
  // 哈希桶
  KeyValueNode** table; // 二级指针
  // 存储的数量
  int size;
  // 容量大小
  int capacity;
  // 哈希函数需要的种子值
  uint32_t hash_seed; 
} HashMap;

// 创建一个固定容量的哈希表
HashMap* create_hashmap(void);
// 销毁一个哈希表
void destroy_hashmap(HashMap* map);

// 插入一个键值对
V put(HashMap* map, K key, V val);
// 查询一个键值对
V get(HashMap* map, K key);
// 删除某个键值对
bool map_remove(HashMap* map, K key);

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "hashmap.h"

#define DEFAULT_CAPACITY 4
#define LOAD_FACTOR 0.75
#define MAX_PREALLOCATE 256

// 创建空的哈希表
HashMap* create_hashmap(void)
{
    HashMap* map = malloc(sizeof(HashMap));
    if(map == NULL)
    {
        printf("ERROR:malloc failed in create_hashmap!");
        exit(1);
    }

    map->size = 0;
    map->capacity = DEFAULT_CAPACITY;
    map->hash_seed = time(NULL);
    map->table = calloc(DEFAULT_CAPACITY,sizeof(KeyValueNode*));
    if(map->table == NULL)
    {
        printf("ERROR:calloc failed in create_hashmap!");
        exit(1);
    }

    return map;
}

// MurmurHash2函数
uint32_t hash(const void* key, int len, uint32_t seed) {
    const uint32_t m = 0x5bd1e995;  // 修正十六进制拼写错误
    const int r = 24;
    uint32_t h = seed ^ len;        // 正确初始化方式

    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;  // 正确运算顺序
        k *= m;

        h *= m;
        h ^= k;        // 异或操作替代原错误乘法

        data += 4;
        len -= 4;
    }

    // 处理剩余字节
    switch (len) {
        case 3: h ^= data[2] << 16;
                // fall through
        case 2: h ^= data[1] << 8;
                // fall through
        case 1: h ^= data[0];
                h *= m;
    }

    // 最终混合
    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

//扩容函数的子函数
void rehash(KeyValueNode* cur,KeyValueNode** new_table,int new_capacity,uint32_t seed)
{
    //计算key的哈希值
    int len = strlen(cur->key);
    int idx = hash(cur->key,len,seed) % new_capacity;
    //头插法
    cur->next = new_table[idx];
    new_table[idx] = cur;
}

//对哈希表进行扩容
void grow_capacity(HashMap* map)
{
    //新的容量
    int new_capacity = (map->capacity <= MAX_PREALLOCATE)?
                    (map->capacity << 1) : (map->capacity + MAX_PREALLOCATE);
    //创建新的哈希数组
    KeyValueNode** new_table = calloc(new_capacity,sizeof(KeyValueNode*));
    if(new_table == NULL)
    {
        printf("ERROR:calloc failed in grow_capacity!");
        exit(1);
    }
    //重新设置哈希种子(更加安全)
    uint32_t new_seed = time(NULL);
    //将旧的哈希表迁移到新的哈希表上
    for(int i=0; i<map->capacity; i++)
    {
        KeyValueNode* cur = map->table[i];
        while(cur != NULL)
        {
            KeyValueNode* next = cur->next;
            //将旧表重映射到新表上
            rehash(cur,new_table,new_capacity,new_seed);
            cur = next;
        }
    }
    //释放旧的表
    free(map->table);

    //更新参数
    map->table = new_table;
    map->capacity = new_capacity;
    map->hash_seed = new_seed;
}


// 往哈希表添加元素
// a.如果key不存在，添加 key-val，并返回NULL
// b.如果key存在，更新key关联的val，返回原来的val
V put(HashMap* map, K key, V val)
{
    int idx = hash(key,strlen(key),map->table) % map->capacity;
    //遍历链表
    KeyValueNode* cur = map->table[idx];
    while(cur != NULL)
    {
        if(strcmp(cur->key,key) == 0)
        {
            //更新key关联的值，并返回原来的值
            V old_val = cur->val;
            cur->val = val;
            return old_val;
        }
        cur = cur->next;
    }
    //cur == NULL
    //a.如果key不存在，添加 key-val，并返回NULL
    KeyValueNode* new_node = malloc(sizeof(KeyValueNode));
    if(new_node == NULL)
    {
        printf("ERROR:malloc failed in put!");
        exit(1);
    }
    new_node->key = key;
    new_node->val = val;

    //判断是否需要扩容
    double table_load = (1.0 * map->size) / map->capacity;
    //如果超过负载因子就需要扩容
    if(table_load >= LOAD_FACTOR)
    {
        grow_capacity(map);
        //计算新的索引
        idx = hash(key,strlen(key),map->hash_seed) % map->capacity;
    }
    //头插法
    new_node->next = map->table[idx];//map->table[idx]哈希桶也存放着结点
    //链接
    map->table[idx] = new_node;
    //更新哈希表信息
    map->size++;

    return NULL;
}

// 根据key值，获取关联的值
// 如果key不存在，返回NULL
V get(HashMap* map, K key)
{
    //对key进行哈希，判断key在哪个哈希桶中
    int idx = hash(key,strlen(key),map->table) % map->capacity;
    //遍历链表
    KeyValueNode* cur = map->table[idx];
    while(cur != NULL)
    {
        if(strcmp(cur->key,key) == 0)
        {
            //找到了
            return cur->val;
        }
        cur = cur->next;
    }
    return NULL;
};

//删除键值对，如果key不存在，什么也不做
bool map_remove(HashMap* map, K key)
{
    int idx = hash(key,strlen(key),map->table) % map->capacity;
    //遍历链表
    KeyValueNode* pre = NULL;
    KeyValueNode* cur = map->table[idx];
    while(cur != NULL)
    {
        if(strcmp(cur->key,key) == 0)
        {
            //删除结点
            if(pre == NULL)
            {
                map->table[idx] = cur->next;
            }
            else
            {
                pre->next = cur->next;
            }
            free(cur);
            map->size--;
            return true;
        }
        pre = cur;
        cur = cur->next;
    }//cur == NULL,什么也不做
    return true;
}

// 销毁一个哈希表
void destroy_hashmap(HashMap* map)
{
    //释放所有结点(遍历哈希表)
    for(int i=0;i<map->capacity;i++)
    {
        KeyValueNode* cur = map->table[i];
        while(cur != NULL)
        {
            KeyValueNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    //释放动态数组
    free(map->table);
    //释放HashMap结构体
    free(map);
}

//添加一个结点
//1、如果key存在则什么也不做
//2、如果key不存在，则添加一个结点
void bst_insert(BST* tree,K key)
{
    TreeNode* parent = NULL;
    TreeNode* cur = tree->root;
    int cmp;//用于比较，只需要比较一次
    while(cur!=NULL)
    {
        //比较
        cmp = key - cur->key;
        if(cmp < 0) //key < cur->key
        {
            parent = cur;
            cur = cur->left;
        }
        else if(cmp > 0) //key > cur->key
        {
            parent = cur;
            cur = cur->right;
        }
        else //key == cur->key，什么也不做
            return;
    }//此时cur == NULL
    //创建树结点
    TreeNode* new_node = calloc(1,sizeof(TreeNode));
    if(new_node == NULL)
    {
        printf("calloc failed in bst_insert!");
        exit(1);
    }
    //初始化树节点
    new_node->key = key;
    //链接到树中
    if(parent == NULL)
        tree->root = new_node;
    else if(cmp < 0) //在左边插入
        parent->left = new_node;
    else //在右边插入
    parent->right = new_node;
}

//查找一个结点
TreeNode* bst_search(BST* tree,K key)
{
    TreeNode* cur = tree->root;
    int cmp;//用于比较，只需要比较一次
    while(cur != NULL)
    {
        //比较
        cmp = key - cur->key;
        if(cmp < 0) //key < cur->key
        {
            cur = cur->left;
        }
        else if(cmp > 0) //key > cur->key
        {
            cur = cur->right;
        }
        else //key == cur->key
            return cur;
    }
    return NULL;
}

//层次遍历BST，广度优先搜索
void bst_levellorder(BST* tree)
{
    LinkedListQueue* q = create_queue(); 
    //将根节点入队列
    enqueue(q,tree->root);
    //判断队列是否为空
    while(!is_empty(q))
    {
        int level_size = q->size;
        for(int i=0;i<level_size;i++)
        {
            //出队列，遍历这个节点
            TreeNode* node = dequeue(q);
            printf("%d ",node->key);
            //判断是否有左孩子
            if(node->left)
            {
                enqueue(q,node->left);
            }
            //判断是否有右孩子
            if(node->right)
            {
                enqueue(q,node->right);
            }
        }
        printf("\n");
    }//队列为空了
    destroy_queue(q);
}

//中序遍历(二叉排序树)
void bst_inorder(TreeNode* root)
{
    //边界条件
    if(root == NULL)
        return;
    //递归公式
    //遍历左子树
    bst_inorder(root->left);
    //遍历根节点
    printf("%d ",root->key);
    //遍历右子树
    bst_inorder(root->right);
}

//先序遍历
void bst_preorder(TreeNode* root)
{
    //边界条件
    if(root == NULL)
        return;
    //递归公式
    //遍历根节点
    printf("%d ",root->key);
    //遍历左子树
    bst_preorder(root->left);
    //遍历右子树
    bst_preorder(root->right);
}

//后序遍历
void bst_backorder(TreeNode* root)
{
    //边界条件
    if(root == NULL)
        return;
    //递归公式
    //遍历左子树
    bst_backorder(root->left);
    //遍历右子树
    bst_backorder(root->right);
    //遍历根节点
    printf("%d ",root->key);
}

//删除节点
void bst_delete(BST* tree,K key)
{
    // 1.找到要删除的节点
    TreeNode* parent = NULL;
    TreeNode* cur = tree->root;
    K cmp;
    while(cur != NULL)
    {
        cmp = key - cur->key;
        if(cmp < 0) //key < cur->key,向左边找
        {
            parent = cur;
            cur = cur->left;
        }
        else if(cmp > 0)
        {
            parent = cur;
            cur = cur->right;
        }
        else
            break;
    }//cur == NULL || cur != NULL
    if(cur == NULL)
        return;
    // 2.删除节点
    if(cur->left && cur->right) // 度为2的情况
    {
        //退化成度为0或度为1的情况
        //先找右子树的最小节点
        TreeNode* pr_min = cur;
        TreeNode* r_min = cur->right;
        while(r_min->left != NULL)
        {
            pr_min = r_min;
            r_min = r_min->left;
        }
        //退化过程
        cur->key = r_min->key;
        cur = r_min;
        parent = pr_min;
    }
    //度为0或1的情况
    //找到唯一的孩子
    TreeNode* child = cur->left ? cur->left : cur->right;
    if(parent == NULL) // 删除的是根节点
    {
        tree->root = child;
    }
    else
    {
        //将child链接到parent正确的位置
        //必须重新比较，因为可能出现了退化
        K cmp = cur->key - parent->key;
        if(cmp<0)
        {
            parent->left = child;
        }
        else if(cmp>0)
        {
            parent->right = child;
        }
        else //注意：特例cmp==0，右子树最小节点就是右子树根节点
        {
            parent->right = child;
        }
    }
    free(cur);
}

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

int main(void)
{
    // 1.打开文件流
    FILE *stream = fopen("a.txt", "w");//可以调整路径和模式
    if (stream == NULL)
    {
        fprintf(stderr, "Open a.txt failed\n");
    }
    // 2.读写文件(统计，转换，加密，解密等业务逻辑)

    // 3.关闭文件流
    fclose(stream);

    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

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

int main(int argc, char *argv[])
{
    // xxx.exe src dst
    //  1.参数校验
    if (argc != 3)
    {
        fprintf(stderr, "Usage: %s src dst\n", argv[0]);
        exit(1);
    }

    // 2.打开文件流
    FILE *src = fopen(argv[1], "r");
    if (src == NULL)
    {
        fprintf(stderr, "Open %s failed\n", argv[1]);
        exit(1);
    }

    FILE *dst = fopen(argv[2], "w");
    if (src == NULL)
    {
        fprintf(stderr, "Open %s failed\n", argv[2]);
        fclose(src);
        exit(1);
    }

    // 3.读写文件
    // a.一个字符一个字符地读写: fgetc, fputc
    // 把大写转换为小写
    int c;
    while ((c = fgetc(src)) != EOF)
    {
        fputc(tolower(c), dst);
    }

    // 4.关闭文件流
    fclose(src);
    fclose(dst);

    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

// b.一行一行地读写字符
    char line[MAXLINE];
    char buffer[MAXLINE];
    int line_num = 1;
    while (fgets(buffer, MAXLINE, src) != NULL)
    {
        sprintf(line, "%d. %s", line_num, buffer);
        fputs(line, dst);
        line_num++;
    }

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

#define BUFSIZE 4096

int main(int argc, char *argv[])
{
    // xxx.exe src dst
    //  1.参数校验
    if (argc != 3)
    {
        fprintf(stderr, "Usage: %s src dst\n", argv[0]);
        exit(1);
    }

    // 2.打开文件流
    FILE *src = fopen(argv[1], "rb");// 读二进制文件模式后面要加b
    if (src == NULL)
    {
        fprintf(stderr, "Open %s failed\n", argv[1]);
        exit(1);
    }

    FILE *dst = fopen(argv[2], "wb");
    if (src == NULL)
    {
        fprintf(stderr, "Open %s failed\n", argv[2]);// 读二进制文件模式后面要加b
        fclose(src);
        exit(1);
    }

    // 3.复制二进制文件
    char buffer[BUFSIZE];
    int bytes_num;
    while ((bytes_num = fread(buffer, 1, BUFSIZE, src)) > 0)
    {
        fwrite(buffer, 1, BUFSIZE, dst);
    }

    // 4.关闭文件流
    fclose(src);
    fclose(dst);

    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

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

char *readFILE(const char *path)
{
    // 2.打开文件流
    FILE *src = fopen(path, "rb"); // 以二进制形式
    if (src == NULL)
    {
        fprintf(stderr, "Open %s failed\n", path);
        exit(1);
    }

    // 3.确定文件大小
    fseek(src, 0, SEEK_END);
    long n = ftell(src);
    char *content = malloc(n + 1); // 1 for '\0'

    // 读文件内容，填充content数组
    rewind(src); // 回到文件开头
    int bytes_num = fread(content, 1, n, src);
    content[bytes_num] = '\0';

    // 4.关闭文件流
    fclose(src);

    return content;
}

int main(int argc, char *argv[])
{
    // xxx.exe src
    //  1.参数校验
    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s filename\n", argv[0]);
        exit(1);
    }

    char *content = readFILE(argv[1]);

    // 输出内容
    puts(content);

    free(content);

    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}