C 程序步骤中的一些问题

写C 和 C++ 或者 python 还是有很多不同，列举一下常见的基础流程的问题

malloc构建二维数组

以构建一个int dp[n+1][m+1]为例。首先malloc 和 free 要一一对应，第二是 malloc 的大小参数要做数据检查，0字节的长度申请，或者负数长度去申请，负数会被当成一个很大的无符号整数，从而申请内存大小过大导致错误。

#define MAX_M 100
#define MAX_N 500
int **dp = (int**)malloc((MAX_N + 1) * sizeof(int*));

for (int i = 0; i < n + 1; i++) {
    dp[i] = (int*)malloc((MAX_M + 1)*sizeof(int));
}

堆上数组的开辟问题

在很早的C语言版本中 使用变量在堆上初始化数组int [m][n]的写法是不被支持的，需要用malloc进行动态构建开辟。

但是C99或者C11版本中，使用变量在堆上初始化数组在后面的编译器是支持的。

int i = 5;
i++;
char test[i];

int i;
scanf("%d", &i);
char test[i];

int m = 3; int n = 2;
int xoe[m][n];
xoe[2][1] = 3;
printf("%d", xoe[2][1]);

// 需要注意的是使用这种方式进行定义的时候不能直接花括号赋初值
// 下面的写法就不行
int i = 5;
char test[i] = {0, 1, 2, 3, 4};

对数组都赋相同初始值

目前对于全部赋0，-1，或者 MAX 值， C实现比较方便，其他的初始化数值不太方便。

最常见的是都赋0 int arr[10] = {0}; 这个容易实现。

那么要是想要都赋 -1 呢？ int arr[10] = {-1}; 第一个元素将初始化为提供的值,而其他元素将填充零: 只会把 arr[0]变成 -1，arr[1] 的值是0。

除了循环赋值，就只能用memset进行配置。

 int test[10] = {0};
 memset(test, -1, sizeof(test));

或者用 0x3f填满，达到构造类似于INT_MAX的功能。例如使用 0x3f进行赋值，stack里面的每个int数值被 初始化为0x3f3f3f3f，即为1061109567。

常用函数

strcpy_s()

strcpy_s(char* dest, size_t numElems, const char* src)

strncpy_s(char *strDest,size_t numberOfElements,const char *strSource,size_t count)

sprintf_s()

int sprintf_s(char *strDest, size_t destMax, const char *format, ...)

memset()

该库函数属于C库函数 <string.h>。复制字符 c（一个无符号字符）到参数 str 所指向的字符串的前 n 个字符。
void *memset(void *str, int c, size_t n)

虽然本意是用于字符串，但是也支持对int初始数组进行赋初值, 一般赋值全为0， 或者用 0x3f填满，达到构造类似于INT_MAX的功能。例如使用 0x3f进行赋值，stack里面的每个int数值被 初始化为0x3f3f3f3f，即为1061109567。

int stack[10];
memset(stack, 0, sizeof(stack)); // memset(stack, 0x3f, sizeof(stack))
for (int i = 0; i < 10; i++) {
    printf("%d ", stack[i]);
}

如果是直接进行初始值的定义使用花括号。

int arr[2][3] = {{1,2,3}, {4,5,6}}

memcpy_s ()

memcpy_s(dest, destMax, src, srcLen);

接收数组长度变量的destMax 必须设置为 sizeof(dest) 或者 BUFF_SIZE*sizeof(elementType)。只有当元素数组为字节类型(如char，signed char，unsigned char) 时，sizeof(elementType) 为1，此时可以忽略。

qsort()

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

base -- 指向要排序的数组的第一个元素的指针。
nitems -- 由 base 指向的数组中元素的个数。
size -- 数组中每个元素的大小，以字节为单位。
compar -- 用来比较两个元素的函数。

cmp()会有三种返回值（以qsort为例）:
1、返回一个正数：a排在b之后；
2、返回0：a、b相等；
3、返回一个负数：a排在b之前；

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

int values[] = { 88, 56, 100, 2, 25 };

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int main()
{
   int n;

   printf("排序之前的列表：\n");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", values[n]);
   }

   qsort(values, 5, sizeof(int), cmpfunc);

   printf("\n排序之后的列表：\n");
   for( n = 0 ; n < 5; n++ ) {
      printf("%d ", values[n]);
   }
  
  return(0);
}

解释下比较函数的写法：

在一些函数定义中，const void *a 这类形参，const void *a这是定义了一个指针，a可以指向任意类型的值，但它指向的值必须是常量，在这种情况下，我们不能修改被指向的对象，但可以使指针指向其他对象。void *则为“无类型指针”，void *可以指向任何类型的数据。

后面 *(int*) a 分为两步 (int*) a是把上面的无类型指针转换为 int 型指针， 再前面加上 * 变成 *(int*) a 是进行了一个dereference解引用。

其实传参也可以直接传个 int 类型的指针，不过对于更复杂的情况还是建议 const void*后，在cmp函数内部进行强转。

int cmpfunc(int* a, int* b) {
    return *a - *b;
}

对于double类型的比较需要特别注意, 要用比较符号，不能用减号。

double in[100];
int cmp( const void *a , const void *b)
{
    return *(double *)a > *(double *)b ? 1 : -1;
}
qsort(in,100,sizeof(in[0]),cmp)；

借助 strcmp(str1, str2) 对字符串进行排序

返回值：

• 如果返回值 < 0，则表示 str1 小于 str2。
• 如果返回值 > 0，则表示 str1 大于 str2。
• 如果返回值 = 0，则表示 str1 等于 str2。

struct In
{
int data;
char str[100];
}s[100];
//按照结构体中字符串str的字典顺序排序
int cmp ( const void *a , const void *b)
{
    return strcmp( (*(In *)a).str , (*(In *)b).str);
}
qsort(s,100,sizeof(s[0]),cmp);

除此之外，qsort 也比较适用于对结构体进行排序。

struct In 
{ 
int x; 
int y; 
}s[100]; 

//按照x从小到大排序，当x相等时按照y从大到小排序 

int cmp( const void *a , const void *b ) 
{ 
struct In *c = (In *)a; 
struct In *d = (In *)b; 
if(c->x != d->x) return c->x - d->x; 
else return d->y - c->y; 
} 

qsort(s,100,sizeof(s[0]),cmp); 

针对二维数组，也可以进行排序，值得注意的是cmp的写法，需要在里面强转(int**)后再解引用，不能直接在入参时候(int**),下面例子里的二维数组形式如下：

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

int cmp(const void* _a, const void* _b) {
    int *a = *(int**)_a, *b = *(int**)_b;
    return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}
int** reconstructQueue(int** people, int peopleSize, int* peopleColSize, int* returnSize, int** returnColumnSizes) {
    qsort(people, peopleSize, sizeof(int*), cmp);
    int** ans = malloc(sizeof(int*) * peopleSize);
    *returnSize = peopleSize;
    *returnColumnSizes = malloc(sizeof(int) * peopleSize);
    memset(*returnColumnSizes, 0, sizeof(int) * peopleSize);
    for (int i = 0; i < peopleSize; ++i) {
        int spaces = people[i][1] + 1;
        for (int j = 0; j < peopleSize; ++j) {
            if ((*returnColumnSizes)[j] == 0) {
                spaces--;
                if (!spaces) {
                    (*returnColumnSizes)[j] = 2;
                    ans[j] = malloc(sizeof(int) * 2);
                    ans[j][0] = people[i][0], ans[j][1] = people[i][1];
                    break;
                }
            }
        }
    }
    return ans;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height/solution/gen-ju-shen-gao-zhong-jian-dui-lie-by-leetcode-sol/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

bsearch()

进行二分搜索的函数，使用前对base里面的数组需要进行排序。

void *bsearch(const void *key, const void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *))

参数

• key -- 指向要查找的元素的指针，类型转换为 void*。
• base -- 指向进行查找的数组的第一个对象的指针，类型转换为 void*。
• nitems -- base 所指向的数组中元素的个数。
• size -- 数组中每个元素的大小，以字节为单位。
• compar -- 用来比较两个元素的函数。

如果查找成功，该函数返回一个指向数组中匹配元素的指针，否则返回空指针。

以字符串数组为例：

int cmp(cons void *a, const void *b) {
    char *a0 = *(char **)a;
    char *b0 = *(char **)b;
    return strcmp(a0, b0);
}

char *retStr[3] = {"ab", "ac", "cd"};
char *new = "ab";
// 返回的是指向字符串的指针，也就是二维的char指针
char **find = bsearch(&new, retStr, 3, sizeof(char *), cmp); 

strtok_s()

功能类似于python的split()

char *strtok_s( char *strToken, const char *strDelimit, char **buf)

参数

• strToken -- 待分割的字符串。
• strDelimit-- 分割符字符串。
• buf -- 存储剩余的字符串。

每次调用成功则返回指向被分割出片段的指针，若无更多分割的字符串则返回空指针。

在第一次调用时，strtok_s()必需给予参数strToken字符串，往后的调用则将参数strToken设置成NULL。这个函数将剩余的字符串存储在buf变量中，而不是静态变量中，从而保证了安全性。

注意：由于strtok_s函数会对strToken参数的字符串进行修改，所以strToken入参不能为const char* ，否则会导致程序崩溃。

char reviews[] = "java python cpp";
char *nextToken = NULL;
char *token = NULL;
char *seps = " ";
token = strtok_s(reviews, seps, &nextToken);
while (token != NULL) {
    printf("%s\r\n", token);
    token = strtok_s(NULL, seps, &nextToken);
}

技巧

位运算相关

n &= n - 1 位运算结果把 n 的二进制位中的最低位的 1 变为 0 之后的结果。

前缀和

二分搜索框架

C语言的一些算法结构

栈

栈的实现：其实也就是动态调整top指针；

栈的实现

实际算法题里面其实只要开辟一个array空间，加上维护top的数值就可以完成栈的模拟。以力扣上著名的有效括号问题为例，

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) { // 遇到右括号
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else { // 遇到左括号
            stk[top++] = s[i];
        }
    }
    return top == 0;
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

队列

维护首末端一个 front 指针，一个 back 指针。

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

剑指 Offer 59

结构体中维护了一个普通队列来完成pop_front的正常功能，一个单调递减队列来保证max_value。

typedef struct {
    int *queue;
    int front;
    int back;
    int *maxQueue;
    int maxFront;
    int maxBack;
} MaxQueue;

MaxQueue* maxQueueCreate() {
    MaxQueue *Queue;
    Queue = (MaxQueue*)calloc(1, sizeof(MaxQueue));
    Queue->maxQueue = calloc(10000, sizeof(int));
    Queue->queue = calloc(10000, sizeof(int));
    return Queue;
}

int maxQueueMax_value(MaxQueue* obj) {
    if (obj->maxBack != obj->maxFront){
         return obj->maxQueue[obj->maxFront];
    }
    return -1;
}

void maxQueuePush_back(MaxQueue* obj, int value) {
    while (obj->maxBack != obj->maxFront && value > obj->maxQueue[obj->maxBack - 1]) {
        obj->maxBack--;
    }
    obj->queue[obj->back++] = value;
    obj->maxQueue[obj->maxBack++] = value;
}

int maxQueuePop_front(MaxQueue* obj) {
    if (obj->front == obj->back) {
        return -1;
    }
    int val = obj->queue[obj->front++];
    if (val == obj->maxQueue[obj->maxFront]) {
        obj->maxFront++;
    }
    return val;
}

void maxQueueFree(MaxQueue* obj) {
    free(obj->queue);
    free(obj->maxQueue);
    free(obj);
}

/**
 * Your MaxQueue struct will be instantiated and called as such:
 * MaxQueue* obj = maxQueueCreate();
 * int param_1 = maxQueueMax_value(obj);
 
 * maxQueuePush_back(obj, value);
 
 * int param_3 = maxQueuePop_front(obj);
 
 * maxQueueFree(obj);
*/

滑动窗口

和队列差不多，需要维护的是head和tail的两个指针。

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct {
    int head;
    int tail;
    int *val;
    int maxIndex;
}deque;

int findMax(int *input, int head, int tail) {
    int max = 0;
    int index = 0;
    for (int i = head; i <= tail; i++) {
        if (input[i] >= max) {
            max = input[i];
            index = i;
        }
    }
    return index;
}
int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize){
    if (nums == NULL || numsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int *ans = (int*)calloc(numsSize - k + 1, sizeof(int));
    *returnSize = numsSize - k + 1;
    deque *dq = (deque*)calloc(1, sizeof(deque));

    dq->head = 0; dq->tail = k - 1;
    dq->val = (int*)calloc(k, sizeof(int));
    
    for (int i = 0; i < k; i++) {
        dq->val[i] = nums[i];
    }
    
    for (int i = 0; i < numsSize - k + 1; i++) {
        dq->head = i;
        dq->tail = i + k -1;
        if ((i == 0) || (i > 0 && dq->maxIndex == i - 1)) {
            dq->maxIndex = findMax(dq->val, dq->head, dq->tail);
        } else { 
            dq->maxIndex = (dq->val[dq->tail] >= dq->val[dq->maxIndex]) ? dq->tail : dq->maxIndex;
        }
        ans[i] = dq->val[dq->maxIndex];
    }
    return ans;
}

大顶堆

C++ 里面是 直接可以用 priority_queue , C 里面先看看大顶堆的具体实现。包括了如何构建堆，堆的插入和删除，自顶向上和自顶向下两种调整堆的方式。

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

void swap(int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
// 自底向上的调整

void max_heapify_up(int *arr, int i, int size) {
    int p = (i - 1) / 2;
    while (p >= 0) {
        if (arr[p] < arr[i] && i < size) {
            swap(&arr[p], &arr[i]);
            i = p;
            p = (i - 1) / 2;
        } else {
            return;
        }
    }
}
// 自顶向下的调整
void max_heapify(int *arr, int i, int size) {
    int c = 2 * i + 1;
    while (c < size) {
        if (c + 1 < size && arr[c] < arr[c+1]) c++;
        if (arr[i] < arr[c]) {
            swap(&arr[i], &arr[c]);
            i = c;
            c = 2 * i + 1;
        } else {
            return;
        }
    }
}


void build_heap(int *arr, int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        max_heapify(arr, i, size);
    }
}

// 获取顶部的值 又只能从堆中删除堆顶元素。移除堆顶元素之后，用堆的最后一个节点填补取走的堆顶元素，
// 并将堆的实际元素个数减1。但用最后一个元素取代堆顶元素之后有可能破坏堆，因此需要将对自顶向下调整，使其满足最大或最小堆。
int fetch(int *arr, int *size) {
    int x = arr[0];
    arr[0] = arr[--(*size)];
    max_heapify(arr, 0, *size);
    return x;
}

void push(int *arr, int *size, int x) {
    arr[(*size)++] = x;
    max_heapify_up(arr, *size-1, *size);
}


void heap_sort(int *arr, int len) {
    for (int i = len / 2 - 1; i >= 0; i--) {
        max_heapify(arr, i, len - 1);
    }
    for (int i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets UnionFind）的合并及查询问题。常常在使用中以森林来表示。 进行快速规整。主要是用在无向图的连通性的实例场景，例如大部分的岛屿或者部分棋盘问题。

一个很好的判断是否使用并查集的思路是，一、需要划分几个集合 二、如何划分根据各个元素之间的一些链接关系。典型的类比是，利用朋友关系划分出几个朋友圈。

参考1
参考2

在LeetCode上对应的题目有

200.岛屿数量
128.最长连续序列
200.被围绕的区域

1. 初始化一个并查集 initUnionFind
   初始化并查集,一般是将每个元素作为一个单独的集合,对于下面的示例就是对应的元素父节点就是自己
2. 合并两个不相交集合 union
   两个元素,分别找到(find)他们的根节点,然后将其中一个元素的根节点的父亲指向另外的一个元素的根节点
3. 查找某个元素的根节点 find
   查找一个元素的根节点,parent--->parent--->parent.....
   那么问题来了,查找元素根节点途径的元素过多,那么就有一个优化的问题———-路径压缩,直接将该元素的父亲指向根节点或者祖先
4. 判断两个元素是否属于同一个集合 isConnected
   判断两个元素是否属于同一个集合,就是分别找到他们的根节点,然后判断两个根节点是否相等.

下面以岛屿数量例题为例，C语言版本并查集。

#define MAX_LEN 100000
int ancestor[MAX_LEN];
int rank[MAX_LEN]; // 每个集合下面挂载的数量
int unCount = 0; // 集合个数

void initUn(int size) {
    unCount = size;
    for (int i = 0; i < size; i++) {
        ancestor[i] = i;
        rank[i] = 1; 
    }
}

int findAncestor(int index) {
    while (ancestor[index] != index) {
        ancestor[index] = ancestor[ancestor[index]];
        index = ancestor[index];
    }
    return index;
}

void unionF(int index1, int index2) {
    int ant1 = findAncestor(index1);
    int ant2 = findAncestor(index2);
    if (ant1 == ant2) return; 
    if (rank[ant1] < rank[ant2]) {
        ancestor[ant1] = ant2; // 挂载在大的集合下面
        rank[ant2] += rank[ant1]; // 更新集合数目
    } else {
        ancestor[ant2] = ant1; 
        rank[ant1] += rank[ant2]; 
    }
    unCount--;
}

int numIslands(char** grid, int gridSize, int* gridColSize){
    if (grid == NULL || gridSize < 1 || gridColSize == NULL) {
        return 0;
    }
    int nr = gridSize;
    int nc = gridColSize[0];
    int dummy = nr * nc;
    initUn(nr * nc + 1);
    for (int r = 0; r < nr; ++r) {
        for (int c = 0; c < nc; ++c) {
            if (grid[r][c] == '0') {
                unionF(r * nc + c, dummy);
                continue;
            }
            if (grid[r][c] == '1') {
                grid[r][c] = '0';
                if (r - 1 >= 0 && grid[r-1][c] == '1') unionF(r * nc + c, (r-1) * nc + c);
                if (r + 1 < nr && grid[r+1][c] == '1') unionF(r * nc + c, (r+1) * nc + c);
                if (c - 1 >= 0 && grid[r][c-1] == '1') unionF(r * nc + c, r * nc + c - 1);
                if (c + 1 < nc && grid[r][c+1] == '1') unionF(r * nc + c, r * nc + c + 1);
            }
        }
    }
    return unCount - 1;
}

C语言的一些算法模板

DFS

深度优先搜索

还是以上面岛屿数量为例，这题太过经典。

void dfs(char** grid, int r, int c, int nr, int nc) {
    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c, nr, nc);
    if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c, nr, nc);
    if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1, nr, nc);
    if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1, nr, nc);
}
int numIslands(char** grid, int gridSize, int* gridColSize){
    int ans = 0;
    int nr = gridSize;
    int nc = gridColSize[0];
    for (int i = 0; i < nr; i++) {
        for (int j = 0; j < nc; j++) {
            if (grid[i][j] == '1') {
                ans++;
                dfs(grid, i, j, nr, nc);
            }
        }
    }
    return ans;
}

BFS

一般借助queue的广度优先搜索。岛屿题目， C语言写Pair太烦了，贴个官方的C++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (!nr) return 0;
        int nc = grid[0].size();

        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;
                    neighbors.push({r, c});
                    while (!neighbors.empty()) {
                        auto rc = neighbors.front();
                        neighbors.pop();
                        int row = rc.first, col = rc.second;
                        if (row - 1 >= 0 && grid[row-1][col] == '1') {
                            neighbors.push({row-1, col});
                            grid[row-1][col] = '0';
                        }
                        if (row + 1 < nr && grid[row+1][col] == '1') {
                            neighbors.push({row+1, col});
                            grid[row+1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col-1] == '1') {
                            neighbors.push({row, col-1});
                            grid[row][col-1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1') {
                            neighbors.push({row, col+1});
                            grid[row][col+1] = '0';
                        }
                    }
                }
            }
        }

        return num_islands;
    }
};

uthash

uthash 作为一个头文件。可以通过添加UT_hash_handle把任意一个C结构体中的一个或者多个数值组合起来作为key达到hash的功能。

官方文档

初始化

1、uthash需要自定义数据结构， 一个包含UT_hash_handle hh的结构体。
2、结构体中需要定义key的数据类型和其余作为val的数据类型。

struct my_struct {
    int id;
    char name[10];
    UT_hash_handle hh;
};

在定义后需要初始化一个空指针指向定义的hash结构。这里的hash表结构类似于一个双向链表，这边设置的这个指针就类似于链表的头结点。

struct my_struct *users = NULL;

之后为hash表结构开辟合适的空间，再进行添加item的操作。

添加

对应不同的key的数据类型，需要使用不同的添加函数。

1. key是int，可以使用 HASH_ADD_INT
2. key是字符串，可以使用 HASH_ADD_STR
3. key是指针,可以使用 HASH_ADD_PTR
4. 其它，可以使用 HASH_ADD，上述实际都是调用这个方法，不过简化了参数

在上面已经使用过HASH_ADD_INT , 第一个参数是之前定义的结构体空指针，第二个参数申明了会使用结构体中的哪部分作为可以hash的键值，第三个参数就是我们上面完成赋值初始化构建出的结构体实例s。

void add_user(int user_id, char *name) {
    struct my_struct *s;
    s = malloc(sizeof(struct my_struct));
    s->id = user_id;
    strcpy(s->name, name);
    HASH_ADD_INT(users, id, s); /* id: name of key field */
}

查找

添加函数一样，不同的key数据类型，有不同的添加函数。如HASH_FIND_INT查询int类型的键值。

struct my_struct *find_user(int user_id) {
    struct my_struct *s;
    HASH_FIND_INT( users, &user_id, s);
    return s;
}

这里第一个参数是对应需要查询的哈希表，第二个参数指向查询的key的地址，最后一个s 用于存储查询结果（结构体指针s提前创建了，如果没有查询到 s 返回是 NULL，否则就返回对应的key和val）。

对于键值，我们在添加的时候需要保证键值不重复添加。所以对上面的版本进行修改。如果 没有找到对应的键值，创建完整的key和val。如果找到了，add变成覆盖原来的val。

void add_user(int user_id, char *name) {
    struct my_struct *s;
    HASH_FIND_INT(users, &user_id, s);
    if (s == NULL) {
        /* 如果 s 为 NULL，需要重新 malloc 
        struct my_struct *s;
        s = malloc(sizeof(struct my_struct));
        */
        s = (struct my_struct *)malloc(sizeof *s);
        s->id = user_id;
        HASH_ADD_INT(users, id, s);
    }
    strcpy(s->name, name);
}

在上面的例子里面 users 作为一个全局变量，如果要设计成函数传参传递数值呢。

直接把 这个 hash表的 指针加在 add_user 函数里面是不对的。

错误写法

void add_user(struct my_struct *users, int user_id, char *names) {
    ...
    HASH_FIND_INT(users, id, s);
}

需要传入的是指向这个 hash表指针的指针, 可以参考上面的双重指针的说明。因为我们在HASH_ADD函数里，需要的是hash表指针本身的地址，而不是这个指针指向的具体内容。

正确写法

void add_user(struct my_struct **users, int user_id, char *name) { 
    ...
    HASH_ADD_INT(*users, id, s);
}

删除

删除一个的元素的示例代码：

void delete_user(struct my_struct *user) {
    HASH_DEL(users, user); // user: pointer to delete
    free(user); // optional，up to you
}

HASH_DEL只会把一个结构体实例从哈希表里面删除，但是不会 free 掉

如果希望循环删除掉所有的item并且free掉每个对象的空间。

void delete_all() {
    struct my_struct *current_user, *tmp;
    HASH_ITER(hh, users, current_user, tmp) {
        HASH_DEL(users,current_user);  /* delete; users advances to next */
        free(current_user);            /* optional- if you want to free  */
    }
}

如果只是想把哈希表结构删除，但是不用free掉每个元素。

HASH_CLEAR(hh, users);

之后，users 这个指针被设置为NULL。

计数

HASH_COUNT 用于计算hash表中item的总数目

unsigned int num_users;
num_users = HASH_COUNT(users);
printf("there are %u users\n", num_users);

遍历

A hash is also a doubly-linked list.

Iterating backward and forward through the items in the hash is possible because of the hh.prev and hh.next fields. All the items in the hash can be reached by repeatedly following these pointers, thus the hash is also a doubly-linked list.

可以使用 hh.next 指针，指向下一个。

void print_users() {
    struct my_struct *s;
    for(s=users; s != NULL; s=s->hh.next) {
        printf("user id %d: name %s\n", s->id, s->name);
    }
}

还有就是上面删除部分用过的HASH_ITER

排序

对于排序来讲可以根据key或者根据val，或者结合起来

HASH_SORT(users, name_sort);

第二个参数是一个比较函数，返回值是需要为int。

int sort_function(void *a, void *b) {
  /* compare a to b (cast a and b appropriately)
   * return (int) -1 if (a < b)
   * return (int)  0 if (a == b)
   * return (int)  1 if (a > b)
   */
}

使用键值或者数值进行比较的示例。

int name_sort(struct my_struct *a, struct my_struct *b) {
    return strcmp(a->name,b->name);
}

int id_sort(struct my_struct *a, struct my_struct *b) {
    return (a->id - b->id);
}

void sort_by_name() {
    HASH_SORT(users, name_sort);
}

void sort_by_id() {
    HASH_SORT(users, id_sort);
}

When the items in the hash are sorted, the first item may change position. In the example above, users may point to a different structure after calling HASH_SORT.

实例1

387. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：
s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

代码

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};


void char_add(struct hashTable **hashHead, int key, int pos) {
    struct hashTable *tmp;
    HASH_FIND_INT(*hashHead, &key, tmp);
    if (tmp != NULL) {
        tmp->val = -1;
    } else {
        tmp = (struct hashTable*)malloc(sizeof *tmp);
        tmp->key = key;
        tmp->val = pos;
        HASH_ADD_INT(*hashHead, key, tmp);
    }
}

int find_no_duplicate(struct hashTable **hashHead, int length) {
    struct hashTable *tmp;
    int ans = length + 1;
    for (tmp = *hashHead; tmp != NULL; tmp = tmp->hh.next) {
        if (tmp->val != -1) {
            ans = fmin(tmp->val, ans);
        }
    }
    return (ans == length + 1)? -1 : ans;
}

void print(struct hashTable **hashHead) {
    struct hashTable *s;
    for(s=*hashHead; s != NULL; s=s->hh.next) {
        printf("key %d: val %d\n", s->key, s->val);
    }
}
int firstUniqChar(char * s){
    struct hashTable *hashHead = NULL;
    int length = strlen(s);
    if (length == 0) return -1;
    for(int i = 0; i < length; i++) {
        char_add(&hashHead, s[i] , i);
    }
    //print(&hashHead);
    return find_no_duplicate(&hashHead, length);
}

实例2

LeetCode 49字母异位词

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

#define STR_SIZE 100

static int compare(const void* x, const void* y){
    return *(char*)x - *(char*)y;
}

typedef struct {
    char key[STR_SIZE];
    int value[STR_SIZE]; // value 是用来存储每个同样的词的下标的，方便结果输出
    int cnt;
    UT_hash_handle hh;
} HashNode;

HashNode *head = NULL;

void add_item(char* s, int i){
    HashNode *tmp;
    
    HASH_FIND_STR(head, s, tmp);
    if (tmp == NULL) {
        tmp = (HashNode*)malloc(sizeof(HashNode));
        strcpy(tmp->key, s);
        tmp->cnt = 1;
        tmp->value[0] = i;
        HASH_ADD_STR(head, key, tmp);
    } else {
        tmp->value[tmp->cnt] = i;
        (tmp->cnt) += 1;
        
    }
    return;
}
char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes){
    // 空输入判断
    if (strs == NULL || strsSize < 1) {
        *returnColumnSizes = (int*)malloc(sizeof(int) * 1);
        (*returnColumnSizes)[0] = 0;
        *returnSize = 0;
        return NULL;
    }
    
    // 出参初始化
    head = NULL;
    *returnSize = 0; // 就是个标量，用指针修饰是为了回传
    *returnColumnSizes = (int *)malloc(sizeof(int) * strsSize); // 一维 array

    for (int i = 0; i < strsSize; i++) {
        char curStr[STR_SIZE] = {0};
        strcpy(curStr, strs[i]);
        int len = strlen(curStr);
        qsort(curStr, len, sizeof(char), compare);
        add_item(curStr, i);
    }
    char*** result;
    result = (char***)malloc(sizeof(char**) * HASH_COUNT(head));
    *returnSize = HASH_COUNT(head);
    *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));

    // 遍历
    HashNode *iter; int index = 0;
    for (iter = head; iter != NULL; iter = iter->hh.next) {
        result[index] = (char**)malloc(sizeof(char*) * (iter->cnt));
        (*returnColumnSizes)[index] = iter->cnt;
        for (int i = 0; i < iter->cnt; i++) {
            result[index][i] = (char*)malloc(sizeof(char) * (strlen(iter->key) + 1));
            strcpy(result[index][i], strs[iter->value[i]]);
        }
        index++;
    }
    return result;
}

动态规划

背包九讲

C代码题总结

算法结构题

某完全二叉树，第七层（根为第一层）有10个叶子节点，问总共有多少节点。

由于没有说明第七层是最外层 （最外层就是 ），还是次外层 (次外层的可能性是1-7层满，那么就有127个节点，第七层非叶子节点个数 64 - 10 = 54， 由于完全二叉树的特性，第八层就有 54 * 2 - 1 = 107 或者 54 * 2 = 108 个节点)。

不同排序的特性

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	O()	O()	O(n)	O(1)	稳定
直接选择排序	O()	O()	O()	O()	不稳定
直接插入排序	O()	O()	O()	O()	稳定
快速排序	O()	O()	O()	O()	不稳定
堆排序	O()	O()	O()	O()	不稳定
希尔排序	O()	O()	O()	O()	不稳定
归并排序	O()	O()	O()	O()	稳定
计数排序	O()	O()	O()	O()	稳定
基数排序	O()	O()	O()	O()	稳定