常用数据结构的声明，定义和初始化

数组

数组申请

1. 示例

// 一维数组
int* num = (int*)malloc(sizeof(int) * 10);

// 二维数组
   int** num = (int**)malloc(sizeof(int*) * 10); // 为第一行（维）申请空间
   for (int i = 0; i < 10; i++) {
       num[i] = (int*)malloc(sizeof(int) * 10);  // 为第二行（维）申请空间
   }

数组赋值

1. 循环进行赋值
2. memset 赋值

// 对动态申请（堆）的一维数组进行赋值
int* num = (int*)malloc(sizeof(int) * 10);
memset(num, 0, sizeof(int) * 10);

// 对栈的一维数组进行赋值
int num[10];
memset(num, 0, sizeof(num));

指针

指针常量和常量指针

1. 常量指针：const int* ptr，指向常量的指针，指针所指内容不可以改变，但指针本身可以改变
2. 指针常量：int* const ptr，指针类型的常量，指针本身不可改变（不能改变地址），指针所指内容可以改变
3. 常量指针常量：const int* const ptr，指针本身和指针所指内容都不可以改变
4. 怎么记忆：按顺序读const *的结构读作常量指针，* const的结构读作指针常量

指针数组与数组指针

1. 数组指针：int (*p)[n]，指向数组的指针
2. 指针数组：int *p[n]，数组里面放指针
3. 怎么记忆：对于数组指针,它落脚点是指针二字，由于 () 和 [] 的优先级位于同一层级（最高级），而结合方向是从左向右，所以 (*p) 被视为一个整体优先计算，所以 (*p) 是一个指针指向数组 [n]
   

指针指向二维数组

1. 示例

int arr[2][3] = {0};
int (*ptr)[3] = arr;

字符串与字符数组

初始化

1. 示例

    char* str = "hello";
    char* str1 = {"hello"};  // str与str1等价
    char str2[] = {"hello"}; // str2与str3,str5,str7等价
    char str3[] = "hello";
    char str4[] = {'h', 'e', 'l', 'l', 'o'};
    char str5[] = {'h', 'e', 'l', 'l', 'o', '\0'};
    char str6[5] = {"hello"};
    char str7[6] = {"hello"};

    printf("str: %s sizeof:%d strlen:%d\n", str,     sizeof(str),  strlen(str));  // str: hello sizeof:8 strlen:5
    printf("str1:%s sizeof:%d strlen:%d\n", str1,    sizeof(str1), strlen(str1)); // str1:hello sizeof:8 strlen:5
    printf("str2:%s sizeof:%d strlen:%d\n", str2,    sizeof(str2), strlen(str2)); // str2:hello sizeof:6 strlen:5
    printf("str3:%s sizeof:%d strlen:%d\n", str3,    sizeof(str3), strlen(str3)); // str3:hello sizeof:6 strlen:5
    // 末尾未包含空字符，可能导致未定义行为
    printf("str4:%s sizeof:%d strlen:%d\n", str4,    sizeof(str4), strlen(str4)); // str4:hellohello sizeof:5 strlen:10
    printf("str5:%s sizeof:%d strlen:%d\n", str5,    sizeof(str5), strlen(str5)); // str5:hello sizeof:6 strlen:5
    // 末尾未包含空字符，可能导致未定义行为
    printf("str6:%s sizeof:%d strlen:%d\n", str6,    sizeof(str6), strlen(str6)); // str6:hellohello sizeof:5 strlen:10
    printf("str7:%s sizeof:%d strlen:%d\n", str7,    sizeof(str7), strlen(str7)); // str7:hello sizeof:6 strlen:5

常用库包含函数

1. <stdio.h>
   1. 字符串拼接：sprintf
2. <string.h>
   1. 字符串长度：strlen
   2. 字符串拷贝：strcpy 系列
   3. 字符串分割：strtok 系列
   4. 字符串追加：strcat
   5. 字符串比较：strcmp 系列
   6. 字符串子串相关：strchr，strstr
   7. 字符串转数值型：strtol 系列
   8. 内存拷贝：memcpy，memmove
   9. 内存设置：memset
3. <strlib.h>
   1. bsearch：二分查找
   2. qsort：快排

字符串操作

字符串长度

strlen

1. 描述：计算字符串 str 的长度，直到空结束字符，但不包括空结束字符
2. 原型：size_t strlen(const char *str)
   1. str：被计算字符串
   2. 返回值：字符串长度
3. 头文件 <string.h>
4. 安全版本：-
5. sizeof 和 strlen 的区别：sizeof 可以用于任何类型，它用来计算类型占用的内存字节数（计算字符串的内存字节数时包含 ‘\0’ 的字节数），而 strlen 则是计算字符串的字符个数（不含 ‘\0’）
6. 示例

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

int main() {
    char s1[] = "Hello, world!";
    char s2[] = {'H', 'e', 'l', 'l', 'o'}; // 没有'\0'

    printf("sizeof(s1) = %zu\n", sizeof(s1));   // 14（包括'\0'）
    printf("strlen(s1) = %zu\n", strlen(s1));   // 13（不包括'\0'）

    printf("sizeof(s2) = %zu\n", sizeof(s2));   // 5（数组大小）
    printf("strlen(s2) = %zu\n", strlen(s2));   // 未定义行为！可能越界

    return 0;
}

字符串拷贝

strcpy

1. 描述：从 src 拷贝字符串到 dest
2. 原型：char *strcpy(char *dest, const char *src)
   1. dest：目标数组
   2. src：源数组
   3. 返回值：指向 dest 字符串的指针
3. 头文件 <string.h>
4. 安全版本：strcpy_s

strncpy

1. 描述：从 src 拷贝 n 个字符串到 dest。若 src 长度小于 n，则剩余空间用空字节填充
2. 原型：char *strncpy(char *dest, const char *src, size_t n)
   1. dest：目标数组
   2. src：源数组
   3. n：要拷贝的字符数
   4. 返回值：指向 dest 字符串的指针
3. 头文件 <string.h>
4. 安全版本：strncpy_s

字符串分割

strtok

1. 描述：以 delim 为分割点，分割字符串。该方法需要通过循环的方式来打印所有的分割结果，而不是一次性分割完毕。具体来说 strtok 首先找到 str 中第一次 delim 的位置，并将其置为 ‘\0’，返回指向第一个分割出来的字符子串的首地址（指针），然后通过循环（此时 str 置为 NULL），strtok 从 ‘\0’ 的位置继续向后寻找下一个 delim，以此类推。
2. 原型：char *strtok(char *str, const char *delim)
   1. str：目标字符串
      1. 若 str 不为
   2. delim：分隔符
   3. 返回值：每一次分解出来的子字符串，直到遇到终止符
3. 头文件 <string.h>
4. 安全版本：strtok_s
5. 注意点
   1. strtok 会改变原 str
   2. strtok 无法同时处理两个字符串的分割。例如在一些字符串分割后比较两个子串的大小场景下无法使用该方法
   3. strtok_r 可以解决 2 的问题，但该函数仅在 Linux 下实现
6. 示例

int strtok_test(void)
{
  char string[] = "Day Day up";
  
  char *ret;
   
  ret = strtok(string, " ");
  while(ret != NULL) {
    printf("%s \n", ret);
    ret = strtok(NULL, " ");
  }
  return 0;
}

// 输出
Day
Day
up

字符串追加和拼接

strcat

1. 描述：把 src 所指向的字符串追加到 dest 所指向的字符串的结尾
2. 原型：char *strcat(char *dest, const char *src)
   1. dest：目标数组
   2. src：源数组
   3. 返回值：指向 dest 字符串的指针
3. 头文件 <string.h>
4. 安全版本：strcat_s
5. n 字符版本：strncat，strncat_s
6. 示例
   1. destination 需要有足够的容量来容纳 source
   2. ​源字符串必须以空字符结尾​：src 必须是一个有效的以 ‘\0’ 结尾的字符串

// strcat
#include <stdio.h>
#include <string.h> // 包含 strcat 函数的头文件

int main() {
    char dest[50] = "Hello, ";
    char src[] = "World!";

    // 使用 strcat 将 src 追加到 dest 末尾
    strcat(dest, src);

    printf("拼接后的字符串: %s\n", dest);

    return 0;
}

// strncat
#include <stdio.h>
#include <string.h>

int main() {
    char dest[20] = "Hello";
    char src[] = ", World! This is too long";

    // 在 dest 中追加最多 sizeof(dest) - strlen(dest) - 1 个字符
    strncat(dest, src, sizeof(dest) - strlen(dest) - 1);

    printf("安全拼接后的字符串: %s\n", dest);

    return 0;
}

sprintf

1. 描述：发送格式化输出到 str 所指向的字符串
2. 原型：int sprintf(char *str, const char *format, ...)
   1. str：输出结果到这个字符串
   2. format：格式化字符串内容，及包含占位符的字符串
   3. …：填充占位符的内容
   4. 返回值
      1. 成功，返回写入字符数
      2. 失败，返回负数
3. 头文件 <stdio.h>
4. 安全版本：sprintf_s
5. 示例

int sprintf_s_test( void )
{
   char  buffer[200], s[] = "computer", c = 'l';
   int   i = 35, j;
   float fp = 1.7320534f;

   // Format and print various data:
   j  = sprintf_s( buffer, 200,     "   String:    %s\n", s );
   j += sprintf_s( buffer + j, 200 - j, "   Character: %c\n", c );
   j += sprintf_s( buffer + j, 200 - j, "   Integer:   %d\n", i );
   j += sprintf_s( buffer + j, 200 - j, "   Real:      %f\n", fp );

   printf_s( "Output:\n%s\ncharacter count = %d\n", buffer, j );
}  

字符串比较

strcmp

1. 描述：把 str1 所指向的字符串和 str2 所指向的字符串进行比较。比较原则是按照字符的 ASCII 进行比较，与字符串长度无关
2. 原型：int strcmp(const char *str1, const char *str2)
   1. str1：第一个字符串
   2. str2：第二个字符串
   3. 返回值
      1. 返回值 < 0，则 str1 < str2
      2. 返回值 > 0，则 str1 > str2
      3. 返回值 = 0，则 str1 = str2
3. 头文件 <string.h>
4. 安全版本：strcat_s

strncmp

1. 描述：比较 str1 和 str2 前 n 个字符串的大小
2. 原型：int strncmp(const char *str1, const char *str2, size_t n)
   1. str1：第一个字符串
   2. str2：第二个字符串
   3. n：要比较的字符个数
   4. 返回值
      1. 返回值 < 0，则 str1 < str2
      2. 返回值 > 0，则 str1 > str2
      3. 返回值 = 0，则 str1 = str2
3. 头文件 <string.h>
4. 安全版本：-

字符串子串

strchr

1. 描述：返回第一次在字符串 str 中出现字符 c 的位置
2. 原型：char *strchr(const char *str, int c)
   1. str：被查找字符串
   2. c：要查找字符
   3. 返回值
      1. 若在字符串 str 中找到字符 c，返回指向该字符的指针
      2. 未找到，返回 NULL
3. 头文件 <string.h>
4. 安全版本：-
5. 示例

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

int main ()
{
   char str[] = "Hi, man";
   char ch = 'm';
   char *res;

   res = strchr(str, ch);

    if (res != NULL) {
        printf("char location: %d\n", res - str + 1); // char location: 5
    }

   return 0;
}

strrchr

1. 描述：返回最后一次（反向的第一次）在字符串 str 中出现字符 c 的位置
2. 原型：char *strrchr(const char *str, int c)
   1. str：被查找字符串
   2. c：要查找字符
   3. 返回值
      1. 若在字符串 str 中找到字符 c，返回指向该字符的指针
      2. 未找到，返回 NULL
3. 头文件 <string.h>
4. 安全版本：-

strstr

1. 描述：返回第一次在父串 str_1 中出现子串 str_2 的位置
2. 原型：char *strstr (const char *str_1, const char *str_2)
   1. str_1：父串
   2. str_2：子串
   3. 返回值
      1. 指向第一次出现子串的位置，或者如果没有找到就返回 NULL
      2. 子串为空，返回父串
3. 头文件 <string.h>
4. 安全版本：-

数值字符串转数值型

【注】不建议使用 atoi、atol、atoll、atof，因为出错时，产生未定义行为，且不提供详细的错误描述

strtol

1. 描述：把参数 str 所指向的字符串根据给定的 base 转换为一个长整型（long int），base 必须介于 2 和 36（包含）之间，或者是特殊值 0
2. 原型：long int strtol(const char *str, char **endptr, int base)
   1. str：要转换的字符串
   2. endptr：由 strol 函数使用，指向 str 中数值后第一个非数值（也就是常规字符），当遇到常规字符时，就停止转换。一般该值初始化为 NULL
   3. base：要转换的进制。若 base 为 0，则根据字符串前缀来判断进制，如 ‘0x’ 和 ‘0X’ 表示 16 进制，‘0’ 表示 8 进制
   4. 返回值
      1. 成功，返回长整型
      2. 失败，返回 0，且置 errno 为 ERANGE（errno 位于 <errno.h> 中），errno 用于判断是否有溢出发生。除了溢出外，失败还可能是因为把不能转换的字符串拿来转换成长整型
3. 头文件 <string.h>
4. 安全版本：-

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

int main() {
   const char *str = "96535";
   char *endptr = NULL;
   long int num;
   
   num = strtol(str, &endptr, 10);
   printf("The number is: %ld\n", num);    // 96535
   return 0;
}

strtoll

1. 描述：和 strtol 类似，只不过返回 long long int 类型

strtod

1. 描述：和前述两个函数类型，只不过返回浮点型

减 ‘0’

1. 描述：通过将数值字符 - ‘0’ 获取对应的整型。例如，‘9’ - ‘0’ 得到 9
2. 示例

int stringToInt(void)
{
  int num = 0 ;

  char strInt[] = "123";
  char *strIntPtr = strInt;

  while(*strIntPtr != '\0'){
    num = num * 10 + (*strIntPtr - '0');
    strIntPtr++;
  }

  printf("%d", num); // 123

  return 0;
}

内存处理类

内存拷贝

memcpy

1. 描述：从存储区 str2 复制 n 个字节到存储区 str1
2. 原型：void *memcpy(void *str1, const void *str2, size_t n)
   1. str1：目标内存
   2. str2：源内存
   3. n：要被复制的字节数
   4. 返回值：指向 str1 的指针
3. 头文件 <string.h>
4. 安全版本：memcpy_s

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

int main () {
   char dest[] = "address dest";      // 12 个字符
   const char src[]  = "address src"; // 11 个字符

   printf("before dest = %s, src = %s\n", dest, src); // before dest = address dest, src = address src

   memcpy(dest, src, 11); 							 // 从 src 拷贝 11 个字符到 dest

   printf("after dest = %s, src = %s\n", dest, src); // after dest = address srct, src = address src

   return 0;
}

memmove

1. 描述：从存储区 str2 复制 n 个字节到存储区 str1。比 memcpy 更安全，解决了内存重叠的问题
2. 原型：void *memmove(void *str1, const void *str2, size_t n)
   1. str1：目标内存
   2. str2：源内存
   3. n：要被复制的字节数
   4. 返回值：指向 str1 的指针
3. 头文件 <string.h>
4. 安全版本：memmove_s

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

int main () {
   char dest[] = "address dest";      // 12 个字符
   const char src[]  = "address src"; // 11 个字符

   printf("before dest = %s, src = %s\n", dest, src); // before dest = address dest, src = address src

   memmove(dest, src, 11); 							 // 从 src 拷贝 11 个字符到 dest

   printf("after dest = %s, src = %s\n", dest, src); // after dest = address srct, src = address src

   return 0;
}

内存设置

memset

1. 描述：将内存 str 设置指定的值 c，n 为 c 的字节数
2. 原型：void *memset(void *str, int c, size_t n)
   1. str：目标内存
   2. c：设置的值
   3. n：设置的值的字节数，通常用 sizeof 获取
   4. 返回值：指向 str 的指针
3. 头文件 <string.h>
4. 安全版本：memset_s

常用封装算法

查找

bsearch

1. 描述：在有序数组中执行二分查找
2. 原型：void *bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
   1. key：要查找的元素
   2. base：被查找的数组
   3. nmemb：数组中元素的个数
   4. size：每个元素的大小（字节大小）
   5. compar：自定义比较函数
      1. a < b，返回负值
      2. a = b，0
      3. a > b，返回正值
   6. 返回值
      1. 成功，返回 base 中匹配元素的指针
      2. 失败，返回 NULL
3. 头文件：stdlib.h
4. 示例：示例源于菜鸟教程

#include <stdio.h>
#include <stdlib.h>
 
// 比较函数，用于 bsearch 查找
int cmpfunc(const void * a, const void * b) {
    return (*(int*)a - *(int*)b);
}
 
int main() {
    int values[] = { 5, 20, 29, 32, 63 };
    int key = 32;
    int *item;
 
    // 计算数组长度
    size_t array_size = sizeof(values) / sizeof(values[0]);
 
    // 使用 bsearch 在数组中查找值 32
    item = (int*) bsearch(&key, values, array_size, sizeof(int), cmpfunc);
 
    // 检查查找结果并输出
    if (item != NULL) {
        printf("Found item = %d\n", *item);
    } else {
        printf("Item = %d could not be found\n", key);
    }
 
    return 0;
}

排序

qsort

1. 描述：用于对数组进行排序，采用的是快速排序算法
2. 函数原型：void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));
   1. base：指向排序数组的指针
   2. nitems：数组中的元素数量
   3. size：数组中每个元素的大小（以字节为单位）
   4. compar：自定义的比较函数，是一个函数指针，用于比较数组中的两个元素（数值，字符，字符串）。升序比较的规则如下：
      1. 第一个元素 > 第二个元素：返回 >0
      2. 第一个元素 < 第二个元素：返回 <0
      3. 第一个元素 = 第二个元素：返回 =0
3. 返回值：无
4. 头文件：<stdlib.h>
5. 示例一：比较数值

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

int compareNum() {
   int arr[] = {10, 5, 4, 6, 9};
   int n = sizeof(arr) / sizeof(arr[0]);

   qsort(arr, n, sizeof(int), compareNumFunc);

   printf("Following is the sorted array: ");
   
   int i;
   for (i = 0; i < n; ++i) {
      printf("%d ", arr[i]);
   }
   printf("\n"); // 4 5 6 9 10
   return 0;
}

6. 示例二：比较字符

int compareCharFunc(const void *arg1, const void *arg2){
   return (*(char*)arg1 - *(char*)arg2);
}

int compareChar(void){
   char cha[] = {'B', 'D', 'A', 'W', 'Z', 'X', 'M', 'O'};
   int i;
   // Size of the array
   int size = sizeof(cha) / sizeof(cha[0]);

   printf("Original array elements:\n");
   for (i = 0; i < size; i++)
   {
      printf("%c ", cha[i]);
   }

   printf("\n");

   // Use qsort to sort
   qsort(cha, size, sizeof(char), compareCharFunc);
   printf("Following is the sorted array: ");

   for (i = 0; i < size; ++i)
   {
      printf("%c ", cha[i]); // A B D M O W X Z
   }
   return 0;
}

7. 示例三：比较字符串

// 比较字符串
int compareStringFunc(const void *arg1, const void *arg2){
   return strcmp(*(const char **)arg1, *(const char **)arg2);
}

int compareString(void){
   char *strings[] = {"Vivek", "Amanaaa","Aman", "Shriansh", "Tapas"};
   int i;
   // Size of the array
   int size = sizeof(strings) / sizeof(strings[0]);

   printf("Original array elements:\n");
   for (i = 0; i < size; i++)
   {
      printf("%s ", strings[i]);
   }

   printf("\n");

   // Use qsort to sort
   qsort(strings, size, sizeof(char *), compareStringFunc);
   printf("Following is the sorted array: ");

   for (i = 0; i < size; ++i)
   {
      printf("%s ", strings[i]); // Aman Amanaaa Shriansh Tapas Vivek
   }
   return 0;
}

参考

1. 菜鸟教程
2. tutorialspoint
3. geeksforgeeks
4. C语言刷题常用基础知识