C语言知识点

C 中的注意点

• 对于C来讲，最麻烦的是不断的malloc 和 free。特别是对于三阶指针那种情况。建议每次malloc之后对着找有没有对应的free。对于不是很大的内存申请，或者复用程度高的，建议直接栈里面申请。

• 对于free掉之后的空间，注意之前申请的指向的指针得置NULL。

• 对于字符串，每次malloc的时候记得 加 1，为 ‘\0’ 留个位置。

• C语言对所有的数组指针都不知道具体有效值有多长，都需要额外的信息进行记录和操作。
  入参参数里面要注明数据长度，返回参数中要对返回值是一个数组的情况，注明各个维度的具体数值。

  可以参考uthash实例二看看具体的参数控制操作。

  输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
  输出:
  [
    ["ate","eat","tea"],
    ["nat","tan"],
    ["bat"]
  ]
  char *** groupAnagrams(char ** strs, int strsSize, int* returnSize, int** returnColumnSizes)
  

  入参参数的维度都比较好理解，但是出参的话前面会多加一个*使用指针传递方便参数的传回。如returnSize其实就是个标量，表明输出的二维数组里面有几个一维数组，但是前面加了*。同理可以理解一维数组 returnColumnSizes 在参数列表里为什么是两个 *, 其实就是传入了指向指针的指针。

  在函数里为returnColumnSizes开辟空间的时候需要先解引用。

  *returnColumnSizes = (int *)malloc(sizeof(int) * strsSize);

• 确保有符号整数运算操作不出现溢出。

  有符号整数的溢出，算术运算的结果太大超过设定的位宽就会发生溢出，一般会导致符号位发生转变。

  有符号数 a 和 b 的 加法检查。 (b > 0) && (a > INT_MAX - b) 或者 (b < 0) && (a < INT_MIN - b) 。总结下来就是如果 b 为 正，防止 a 和 b 相加大于 INT_MAX 。如果 b 为 负，防止 两个负数加起来能够小于 INT_MIN。

  有符号数 a 和 b 的除法检查。除了除0检查，也要防止整数溢出。同理乘法也要先判断 numA > (INT_MAX / numB) 成立与否，成立的话就有溢出。

  if ((numB == 0) || ((numA == INT_MIN) && (numB == -1))) {
      错误处理
  }
  result = numA / numB;
  

• 无符号操作数的计算倒是不会发生溢出，不过当计算结果太大超出表示范围的时候，就会对结果类型能够表示的最大值加1再进行求模。举个例子：

  UINT8 test_unsigned = 255;
  UINT8 result = test_unsigned + 3;
  printf("%d", result);
  

  输出结果就是 (255 + 3) mod 256 = 2

  这种情况叫做无符号整数运算操作出现反转或者回绕。进行数值加法的时候需要进行是否大于 UINT_MAX的判断。

• 整形转换时候的各类隐藏错误。譬如出现截断错误，整型表达式赋值给较大类型前未转换为较大类型，造成数据溢出。

• C99标准中有明确提到整数提升的概念："如果int能够表示原始类型中的所有数值，那么这个数值就被转成int型，否则，它被转成unsigned int型。这种规则被称为整型提升。所有其它类型都不会被整型提升改变。"
  char/unsigned char,short/unsigned short都可以被int表示。所以当它们做算术运算时，都会被提升成int类型。

• 符号位扩展知识：要扩展量为有符号量，不管最终要扩展成有符号还是无符号，都遵循符号扩展；要扩展量为无符号，不管最终要扩展成有符号还是无符号，都遵循零扩展。

  int main()
  {
      char a = 0xff;         // a为-1，其为有符号量，二进制为11111111
      unsigned short b = a;  //此处a要进行符号扩展，遵循符号扩展,b的二进制为11111111 11111111
      short c = a;           //此处a要进行符号扩展,遵循符号扩展,c的二进制为11111111 11111111
      printf("c = %d\n", a);
      printf("b = %u\n", b);
      printf("c = %d", c);
      return 0;
  }
  

  int main()
  {
      unsigned char a = 0xff;  // a为:255，其为无符号量，二进制为11111111
      unsigned short b = a;    //此处a要进行符号扩展，遵循零扩展,b的二进制为00000000 11111111
      short c = a;             //此处a要进行符号扩展,遵循符号扩展,c的二进制为00000000 11111111
      printf("c = %d\n", a);
      printf("b = %u\n", b);
      printf("c = %d", c);
      return 0;
  }
  

  从上面的结果可以看到符号位的扩展方法只和待扩展变量的符号有关，如果待扩展的变量是无符号变量，则遵循零扩展，否则就是符号位扩展。

• 有符号整数使用位运算操作符时候的错误。特别是左移时候把符号位覆盖的情况。

• 无符号数和有符号数互相计算和比较的时候，有符号数会先变为无符号数再参与计算。所以避免有符号数和无符号数之间的逻辑运算，算术运算的结果倒是还好，因为会根据最后存放结果值的定义类型不同进行转换，不会有太大问题。

  int a=-1;
  unsigned int b=2;
  if(a>b)
  {
    printf("-1>2");
  }
  // 输出 "-1>2"
  int main()
  {
    int a=2147483647;
    unsigned int b=1;
  
    printf("a+b=%d\n",a+b);
    printf("a+b=%u\n",a+b);
    printf("%d\n",2147483648);
    return 0;
  }
  结果：
  a+b=-2147483648
  a+b=2147483648
  -2147483648
  

• 字符类型的数值是由实现定义的，可能为有符号数，也能为无符号数（unsigned char）。字符可以参与数值的加减计算， 例如输出ASCII码的b， printf("%c\n", 'a' + 1);

• 单目运算符的优先级一般大于双目和三目运算符。

• size_t类型是sizeof操作符结果的无符号整数类型，具有size_t类型的变量能够保证具有足够的精度来表示对象的大小。size_t的最大值由SIZE_MAX 宏表示。

C基础知识点

存储区

BSS段：BSS段（bss segment）存放未初始化的全局变量(包括静态全局变量)和初始化为0的全局变量(包括静态全局变量)，属于静态分配内存。BSS段的变量都有默认的初始值0, 而在动态数据区（堆区，栈区）变量的默认值是不确定的。
数据段：数据段（data segment）数据段，用来存放已经初始化且初始化值为非零的全局变量（包括静态变量）。
代码段：代码段（code segment/text segment）通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读, 某些架构也允许代码段为可写，即允许修改程序。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。
堆(heap)：堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）。
栈(stack)：栈又称堆栈，用户存放程序临时创建的局部变量。在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的后进先出特点，所以栈特别方便用来保存/恢复调用现场。

1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放 ， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域(BSS)。 - 程序结束后由系统释放
4、文字常量区 — 常量字符串就是放在这里的。 程序结束后由系统释。放在文字常量区的字符串不可以被修改，而在内存堆空间的字符串可以被修改。

举个例子
char str1[] = "abcdef";
char str2[] = "abcdef";  // 两个字符串定义在栈中，虽然内容一样，但是地址是不一样的

char *str1 = "abcdef"; 
char *str2 = "abcdef"; // 这两个 str1 == str2 就成立，在文字常量区，地址一致。

5、程序代码区— 存放函数体的二进制代码。

int c;
void func(int a){
    static int b;
    int array[5] = {0};
    int *p = (int*)malloc(100);
    b = a;
    c = b + 1;
}

分析一下，a 作为参数，和 在函数体内定义的 array 和 指针 p 都是在栈区。b 作为静态变量，而且没有被初始化，所以在bss 段，同理c是没有初始化的全局变量，也是在bss段。

static的作用

C语言中static关键字的作用
【1】static作用的变量
1.static修饰全局变量：在全局变量前加static，全局变量就被定义成为一个全局静态变量。
特点如下：
1)存储区（内存中的位置）：静态存储区没变（静态存储区在整个程序运行期间都存在）；
2)初始化：未经初始化的全局静态变量会被程序自动初始化为0。（自动对象的值是任意的，除非他被显示初始化）
3)作用域：全局静态变量在声明他的文件之外是不可见的。准确地讲从定义之处开始到文件结尾。非静态全局变量的作用域是整个源程序（多个源文件可以共同使用）； 而静态全局变量则限制了其作用域， 即只在定义该变量的源文件内有效， 在同一源程序的其它源文件中不能使用它。好处：

1)不会被其他文件所访问，修改；
2)其他文件中可以使用相同名字的变量，不会发生冲突。

2.static修饰局部变量：在局部变量之前加上关键字static，局部变量就被定义成为一个局部静态变量。特点如下:

1. 存储区（内存中的位置）：由栈变为静态存储区rodata，生存期为整个源程序，只能在定义该变量的函数内使用。退出该函数后，尽管该变量还继续存在，但不能使用它;
   2)初始化：为静态局部变量赋初值是在编译时进行的，即只赋初值一次，在程序运行时它已有初值。以后每次调用函数时不再重新赋初值而只是保留上次函数调用结束时的值。而为自动变量赋初值，不是在编译时进行的，而是在函数调用时进行，每调用函数重新给一次值，相对于执行一次赋值语句。如果在定义局部变量是不赋初值的话，对静态局部变量来说，编译时自动赋初值0（对数值型变量）或空字符（对字符型变量）。而对自动变量来说，如果不赋初值，则它的值是不确定的值。这是由于每次函数调用结束后存储单元已被释放，下次调用时又重新分配存储单元，而所分配的单元中的值是不确定的。
   3)作用域：作用域仍为局部作用域，当定义它的函数或者语句块结束的时候，作用域随之结束，尽管该变量还继续存在，但不能使用它。

【2】static作用的函数
在函数的返回类型前加上关键字static，函数就被定义成为静态函数。
函数的定义和声明默认情况下是extern的，但静态函数只是在声明他的文件当中可见，不能被其他文件所用。只能被本文件中的函数调用，而不能被同一程序其它文件中的函数调用。好处：
1)其他文件中可以定义相同名字的函数，不会发生冲突
2)静态函数不能被其他文件所用。

【3】static在类中的作用 （C++的内容，这边也复习一下）

1、对于static修饰的成员变量，属于整个类不属于单个对象， 即使创建多个对象，也只为这个静态成员变量分配一份内存。当某个对象修改了这个数值，其他对象访问的时候的数值也会改变。

2、 static 成员变量的内存既不是在声明类时候分配（也就是在类内部禁止初始化），也不是在创建对象的时候分配。只有在类外初始化时候才会分配（可以选择赋初值，或者不赋，不赋初始值默认初始化为0），也就是说，没有在类外初始化的static 成员变量不能使用

3、static 修饰的成员函数在对象构建的时候并不会被传入 this 指针，这是最大的区别。换句话说，static修饰的成员函数无法访问类中的其他非静态成员， 因为普通函数其实就是通过this指针进行了对其他函数成员的访问。

给个具体的程序理解下

#include <iostream>

using namespace std;

class Sample
{
    public:
        static void Func(Sample* obj);
        void Func2();
        static int val;
    private:
        int value;
};

void Sample::Func(Sample* obj) {
    //value = 1;
    //这个不注释掉的话，Sample::Func(a); c.Func(a); 两个调用都会出错，原因就在于没有this指针
    if (obj != NULL) {
        obj->value = 1;
        cout<<"yes"<<endl;
    }
    // 但是在这边，对于传入的obj对象，是可以访问value这个数值的
}

void Sample::Func2(){
    value = 1;
}

int Sample::val = 100; // static 成员变量必须类外定义后才能使用

int main() {
    Sample b, c;
    Sample *a;
    a = &b;
    cout<<b.val<<endl;
    cout<<Sample::val<<endl;
    Sample::Func(a);
    c.Func(a);
    a->Func2();
    return 0;
}

/**
输出：
100
100
yes
yes
**/

const 和 restrict

const 在 C语言里面的作用：

1、阻止一个变量被改变 2、申明常量指针和指针常量 3、const修饰形参，表明这个参数作为输入只读。

其余的一些作用是针对类的，和C没啥关系。（对于类的成员函数，被const修饰之后这个函数对成员变量只能读不能改）

首先 Pointer aliasing 是指两个或者以上的指针指向同一数据。restrict 限定符会告诉编译器，对象已经被指针所引用，不能通过除该指针外所有其他直接或间接的方式修改该对象的内容。

值得注意的是，编译器无法再编译期检测两个指针是否alias，是否restrict需要程序员保证。编译器仅是根据这个信息优化机器码。所以基本上只有在非常需要性能和特别明确两个指针在业务逻辑上不会重复才会用这个限定符。

int foo(int *a, int *b) {
    *a = 5;
    *b = 6;
    return *a + *b;
}

在这里面，由于编译器觉得，这两个指针有指向同一块内存的可能，在生成机器码的时候，会害怕*b = 6改变了 a 的数值，所以会在最后求和的时候再读取一次a的数值。

改成

int rfoo(int * restrict a, int * restrict b) {
    *a = 5;
    *b = 6;
    return *a + *b;
}

编译器通过 restrict 额外信息知道两个指针不指向同一数据，在编译期就能算出返回值，并且直接对 a 和 b 的数值进行修改，也就是生成了更优化的机器码。

extern 关键字

如果想声明一个变量而非定义它，就在变量名前添加extern关键字，而且不要显式地初始化变量：

extern int i;  //声明i而非定义
int j;         //声明并定义i

但我们也可以给由extern关键字标记的变量赋一个初始值，但这样就不是一个声明了，而是一个定义：

extern int v = 2; // 所以一般这种情况下没必要前面加extern
int v = 2;     //这两个语句效果完全一样，都是v的定义

默认情况下，一个const对象仅在本文件内有效，如果多个文件中出现了同名的const变量时，其实等同于在不同的文件中分别定义了独立的变量。

某些时候有这样一种const变量，它的初始值不是一个常量表达式，但又确实有必要在文件间共享。这种情况下，我们不希望编译器为每个文件分别生成独立的变量。我们想让这类const对象像其他非常量对象一样工作，也就是说，只在一个文件中定义const，而在其他多个文件中声明并使用它。

方法是对于const变量不管是声明还是定义都添加extern关键字，这样只需要定义一次就可以了：

//file1.cpp定义并初始化和一个常量，该常量能被其他文件访问
extern const int bufferSize = function();
//file1.h头文件
extern const int bufferSize; //与file1.cpp中定义的是同一个

file1.h头文件中的声明也由extern做了限定，其作用是指明bufferSize并非本文件独有，它的定义将出现在别处。

inline 和 宏定义

宏定义可以理解为纯粹和机械的文本替换。

内联函数的调用和宏函数有点类似，他在调用点会将代码展开，而不是开辟函数栈，用看目标代码量的增加换时间。最大的区别是宏定义编译器一定会给你作替换，但是inline函数仅仅是一个对编译器的建议，所以最后能否真正内联，看编译器的意思：它如果认为函数不复杂，能在调用点展开，就会真正内联，并不是说声明了内联就会内联，声明内联只是一个建议而已。所以一般来讲inline函数内部不允许包含复杂的控制结构语句，特别是循环和开关语句。在C语言里面，inline函数一般会放在头文件里面（因为内联函数要在调用点展开，所以编译器必须随处可见内联函数的定义，要不然就成了非内联函数的调用了），并且是static inline，因为如果编译器觉得这个函数太复杂不能内联，就会把这个函数进行编译并留存符号位。static目的是让该关键字标识的函数只在本地文件可见,同一个程序的其它文件是不可见该函数的.换句话说,就算你其它文件里包含了同名同参数表的函数定义的话,也是不会引起函数重复定义的错误的.因为static是仅在当前文件可见.

不同点：

1、 编译器会对内联函数的参数类型做安全检查或自动类型转换，而宏定义则不会，他只是进行单纯的文字替换，不会做任何类型的检查
2、内联函数在运行时可调试，而宏定义不可以。
3、内联函数可以访问类的成员变量，宏定义则不能。

在类中声明同时定义的成员函数，自动转化为内联函数。

关于宏定义的冷僻知识：

宏名在源程序中若用引号括起来，则预处理程序不对其作宏代换。(对 )

#符号是把宏的参数直接替换为字符串，等价于把参数加上双引号

#用在预编译语句里面可以把预编译函数的变量直接格式成字符

而##把两个宏参数贴合在一起

注意：当宏参数是另一个宏的时候，需要注意的是凡宏定义里有用’#’或’##’的地方宏参数是不会再展开.

#define INT_MAX 0x7FFFFFFF
#define A 2
#define STR() #s
#define CONS(a, b) (int)(a##e##b)
int main()
{
    printf("int max: %s\n", STR(INT_MAX));
    printf("%d\n", CONS(A, A));  // compile error --- int(AeA)
    return 0;
}

/**
两句print会被展开为
printf("int max: %s\n","INT_MAX");――打印结果为
printf("%s\n", int(AeA));―――编译错误，找不到ＡｅＡ
由于A和INT_MAX均是宏，且作为宏CONS和STR的参数，并且宏CONS和STR中均含有#或者##符号，所以A和INT_MAX均不能被解引用。导致不符合预期的情况出现。
**/

__attribute__

GNU C 的一大特色就是__attribute__机制。__attribute__ 可以设置函数属性（Function Attribute ）、变量属性（Variable Attribute ）和类型属性（Type Attribute ）。

__attribute__语法格式为：__attribute__ ((attribute-list))

对于函数属性来讲，有 section 这个属性。关键字会将被修饰的变量或函数编译到特定的一块位置，不是物理存储器上的特定位置，而是在可执行文件的特定段内。

指针和函数指针

int (*p[10])(int*)

首先[]的优先级大于*，那么p是一个数组。右边看我们可以知道这是个函数指针，参数是 int*，左边看 开头是 int* 表明了这个函数的返回值是个int指针。所以p是一个函数指针数组，存储着函数地址。

举一反三：

int (*p)[10](int*) : p是一个指向函数数组的指针，函数的返回值类型为int，参数列表里有一个 int* 参数。

int *p[10]： []的优先级高于*，因此p首先和[] 结合，表示p是一个10个元素的数组，int *p[10] 其实等价 int* p[10] （这么看可能就更明显一点，表面p这个数组里的元素类型是int*）。

int (*p)[10]： 这边使用了括号强行改变了运算符优先级，p先与*结合，所以p首先是个指针，然后看p指针的指向，指向的是一个int 类型的10个元素的数组。

int *(*p)[4]: 有了上面的分析，就能得出，p首先与*结合是个指针，指向一个int* 类型且大小为10的数组。

函数类型的指针，可以这么理解，对于函数，描述的要素有:返回值类型 参数个数及其类型

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

typedef int (*milaoshu)(int a, int b);

int func(int a, int b){
    return a+b;
}
int main() {

    int a = 10;
    int b = 20;
    printf("a+b = %d\n", a+b);
    milaoshu p;  //如果不给这个类型起名叫米老鼠,那么在声明变量p的时候应该这样声明 int (*p)(int, int);
    p = func;
    int c = p(a ,b);
    printf("a+b = %d\n", c);
    return 0;
}

C-string

C++里面有string类，C风格字符串其实就是个字符数组，这个数组还需要以 '\0' 作为字符串结束的标记符。

易错点一：

对于字符串指针的操作。正确的初始化方式

char test[10] = {'0'}; 
char test[10] = {'\0'};

错误的方式

char test[10] = {0};
//如果非要用整数0初始化：signed char 和 unsigned char才被视作整数类型
signed char test[10] = {0};

易错点二：

char *test = "abc"; // 会创建一个字符串常量，"abc"在静态存储区，不可更改; test 在栈上
const char *test = "abc"; // 更好的写法是用const额外进行注明。

// 如果希望在堆上分配一个初始化字符串数组
char test[] = "abc"; 
char test[] = {'a', 'b', 'c', '\0'};
test[1] = 'e'; // 这时候这句话不会报错

对于字符串指针的初始化，务必在堆上开辟足够空间，再用strcpy，memcpy 或者其他安全函数进行操作。

char *str;
str = (char *)malloc(sizeof(char) * 5);
strcpy(str, "abcd");
str[2] = 'e';
printf("%s", str);

C里面处理字符串时候比较恶心的问题：

• C里面<string.h>的 strcpy strcat等 函数，一定需要注意开辟足够大的空间拷贝或者扩长字符串(记得是 strlen(str) + 1) 。如果目标数组 dest 不够大，而源字符串的长度又太长，可能会造成缓冲溢出的情况 。

  char *strcpy(char *dst, const char *src); 并没有长度检测

  除了对长度进行检查：

  （1）const 修饰：源字符串参数用const修饰，防止修改源字符串；

  （2）空指针检查：源指针和目的指针都有可能会出现空指针的情况，所以应该对其进行检查；

• strncpy 和 strncat 等字符串操作函数很容易产生结束符丢失的问题。操作完记得补结束符。

• memcpy与 memmove 的目的都是将N个字节的源内存地址的内容拷贝到目标内存地址中，源内存和目标内存如果存在重叠，会引发错误。这时候只有 memmove_s 能正确实施拷贝。

所以一般这类函数都有strcpy_s 等安全版本

malloc和free

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

malloc 开辟二维数组的示例。leetcode 122。

int maxProfit(int* prices, int pricesSize){
    int **dp = (int**)malloc(pricesSize*sizeof(int*));
    for (int i = 0; i < pricesSize; i++) {
        dp[i] = (int*)malloc(2*sizeof(int));
    }

    dp[0][0] = 0; dp[0][1] = -prices[0];
    for (int i = 1; i < pricesSize; i++) {
        dp[i][0] = fmax((dp[i-1][1] + prices[i]), dp[i-1][0]);
        dp[i][1] = fmax((dp[i-1][0] - prices[i]), dp[i-1][1]);
    }
    int ans = fmax(dp[pricesSize - 1][0], dp[pricesSize - 1][1]);
    for (int i = 0; i < pricesSize; i++) {
        free(dp[i]);
    }
    free(dp);
    return ans;
}

C语言的格式化函数

常见的就是scanf 和 printf，针对标准输入输出流进行操作。

其他的包括输入目的地为文件的（fprintf），输入 fp 指定的输出流。printf（）函数可以视为 fprintf（）的特殊版本。

int fprintf(FILE *restrict fp, const char * restrict format...);

输入目的地为字符串的 (sprintf)。将格式化数据写入 buf 指向的 char 数组，并在后面加上一个标志结尾的空字符。（这类涉及到字符数组空间的大多都有问题）

int sprintf(char * restrict buf,
const char * restrict format...);

在上述函数原型中出现的省略号（...），表示还可有更多参数，但这些参数是可选的。还有一些 printf（）函数系列需要一个指针参数，以指向一个参数列表，而不是在函数调用时直接接收数量可变的参数。这些函数的名称都以一个 v 开始，表示“variable argument list”（可变参数列表）的意思， 如果想使用支持可变参数列表的函数，除了头文件 <stdio.h> 以外，还必须包含头文件 <stdarg.h> ：

int vprintf( const char * restrictformat, va_list argptr );
int vfprintf( FILE * restrict fp, const char * restrict format,
              va_list argptr );
int vsprintf( char * restrict buf, const char * restrict format,
              va_list argptr );
int vsnprintf( char * restrict buffer, size_t n,
               const char * restrict format, va_list argptr );          

C11 标准为这些函数都提供了一个新的“安全”的版本。这些对应的新函数均以后缀_s（例如，fprintf_s（））。新函数测试它们接收的所有指针参数是否为空指针。

格式化字符串定义了数据的输出格式，并包含了一些普通字符和转换说明（conversion specification）。每个转换说明都定义了函数该如何将可选参数转换并格式化，以供输出。

转换说明的通用格式如下：

%[标记][字段宽度][.精度][长度修饰符]修饰符

字符宽度指定对应的数据项所输出的最少字符数量。默认情况下，字段中的被转换数据为右对齐（right-justified），左边多的位置用空格填补。如果标记包含减号（－），则为左对齐（left-justified），超出的字段宽度采用空格向右填补。

printf("1234567890123456\n");           // 用来观察字符长度
printf( "%-10s %s\n", "Player", "Score" );      // 表头
printf( "%-10s %4d\n", "John", 120 );   // 字段宽度：10；4
printf( "%-10s %4d\n", "Mary", 77 );

//会生成一个简单的表格，120 和 77 占四位，右对齐

1234567890123456
Player     Score
John        120
Mary         77

如果字段是右对齐的，可以采用 0 而非空格填充。要实现这样的效果，在转换说明标记中包括一个 0（指数字零）。下面的例子以 mm-dd-yyyy 的格式输出日期：

int month = 5, day = 1, year = 1987;
printf( "Date of birth: %02d-%02d-%04d\n", month, day, year );

输出：
Date of birth: 05-01-1987

列举下控制输出格式的控制符：

转换修饰符	说明
%d	按十进制整型数据的实际长度输出。
%p	输出地址数据。
%ld	输出长整型数据。
%md	m 为指定的输出字段的宽度。如果数据的位数小于 m，则左端补以空格，若大于 m，则按实际位数输出。
%u	输出无符号整型（unsigned）。输出无符号整型时也可以用 %d，这时是将无符号转换成有符号数，然后输出。但编程的时候最好不要这么写，因为这样要进行一次转换，使 CPU 多做一次无用功。
%c	用来输出一个字符。
%f	用来输出实数，包括单精度和双精度，以小数形式输出。不指定字段宽度，由系统自动指定，整数部分全部输出，小数部分输出 6 位，超过 6 位的四舍五入。
%.mf	输出实数时小数点后保留 m 位，注意 m 前面有个点。
%o	以八进制整数形式输出，相比十六进制和十进制用的很少。
%s	用来输出字符串。用 %s 输出字符串但是此时要先定义字符数组或字符指针存储或指向字符串。
%x（或 %X 或 %#x 或 %#X）	以十六进制形式输出整数，如果是小写的x，输出的字母就是小写的；如果是大写的X，输出的字母就是大写的；如果加一个#，就以标准的十六进制形式输出。

C 不同变量的内存占用

• static变量在静态区，对于包含static变量的实例，sizeof均不纳入计算
• 不同编辑器的默认对齐大小不一样，gcc是4字节对齐
• 编辑器规定n字节对齐的pack指令 #pragma pack(n)
• 在编译阶段处理，sizeof作用范围内的内容不能被编译，所以sizeof()内的运算不被执行
• sizeof(函数)=sizeof(返回值类型)
• sizeof和strlen：sizeof计算字符串容量，算’\0’，strlen计算字符串长度，到’\0’截止
• 对于C++的string类，string的实现在各库中可能有所不同，但是在同一库中相同一点是，无论你的string里放多长的字符串，它的sizeof()都是固定的，字符串所占的空间是从堆中动态分配的，与sizeof()无关。 sizeof(string)=4可能是最典型的实现之一，不过也有sizeof()为12、32字节的库实现。

32/64 位 系统各类型内存大小对照（有无unsigned修饰都一样，大小单位字节byte）：

系统	32位	64位
char	1	1
short	2	2
int	4	4
float	4	4
long	4	8
*(地址)	4	8
double	8	8
long long	8	8

• 对于不同系统，有细致的不一样的地方，32位和64位系统在Windows下基本数据类型的大小都是一样的。只有指针的大小不一样！32位指针大小为4byte，而64位的指针大小为8byte。

• Linux下，long型是64位的，这一点是和Windows不同的地方。（表中是Linux标准的long）

C语言位运算

首先位运算最多的肯定是左移和右移操作。

左移

对于左移，丢弃最高位，低位补0， 左移 n 位， 相当于乘以 。譬如 二进制的 000...001，左移两位 就是 000... 100。

对于有符号数，左移可能会导致符号位变化导致的溢出。

int是有符号的整形数，左端的1位是符号为，即0为正1为负，那么用移位的时候就会出现溢出，如:
int i=0x40000000;//16进制的40000000，为2进制的01000000...0000
i=i<<1;
//那么，i在移动1位之后就会变成0x80000000，也就是2进制的100000...0000，符号位被置1，起位全是0，变成了int类型所能表达的最小值，32为的int这个值是-2147483648，溢出，如果在接着把i左移1位会出现什么情况呢?在c语言都采用了丢弃最高位的处理方法，丢弃了1之后，i的值变成了0

其他的左移特殊情况是，当左移的位数超过该数值类型的最大位数时候，编译器会用左移的位数模类型的最大位数，例如 对于32 位 类型，左移33位，这时候其实就相当于只左移了一位。

int i=1,j=0x80000000;//设int为32位
i=i<<33;//33%32=1 左移动1位，i变成2
j=j<<33;//33%32=1 左移动1位，j变成0，最高为被丢弃

右移

对于右移，对符号位的处理和左移不同,对于有符号整数来说,比如int类型,右移会保持符号位不变。

具体操作，符号位向右移动后，本来是正数的会在最前面会补0，本来是负数的会在最前面补1，以此保持符号位的不变。（注意负数右移往往会变得非常小）也就是汇编语言中的算术右移.同样当移动的位数超过类型的长度时,会取余数,然后移动余数个位。

结构体和联合体的内存计算

区别：结构体的各个成员会占用不同的内存块，互相之间没有影响；而联合体的所有成员占用同一段内存块，修改其中一个成员会对整个内存块保存的值产生影响。

约定为32位系统，即char 1字节、short 2字节、int 4字节

每个特定平台上的编译器都有自己的默认“对齐系数”（也叫对齐模数）。gcc中默认#pragma pack(4)，可以通过预编译命令#pragma pack(n)，n = 1,2,4,8,16来改变这一系数。

有效对齐值：是给定值#pragma pack(n)和结构体中最长数据类型长度中较小的那个。有效对齐值也叫对齐单位。

该问题总结为两条规律：

1. 结构体第一个成员的偏移量（offset）为0，以后每个成员相对于结构体首地址的 offset 都是该成员大小与有效对齐值中较小那个的整数倍，如有需要编译器会在成员之间加上填充字节。
2. 结构体的总大小为 有效对齐值 的整数倍，如有需要编译器会在最末一个成员之后加上填充字节。

struct A{
    char a;        //1
    int b;        //空3 + 4 = 7 (规则1)
    short c;    //2+空2=4 (规则2)
};
struct B{
    char a;        //1
    short b;    //空1 + 2 = 3 (规则1)
    int c;        //4
};
struct C{         //在四字节对齐的时候，由于最长就是short int，所以有效对齐值为2
    short int num; // 2
    char sex;     // 1 
    short int data; // 空1 + 2 = 3 （规则1）
    char aa; // 1 + 空1 （规则2）
};

如果指定了对齐值1，那么就是所有的元素加起来的大小。

#pragma pack(1)
struct A{
    char a; //1
    int b;//4
    short c;//2
};
#pragma pack(1)
struct B{
    char a;//1
    short b;//4
    int c;//2
};

这时候结构体A和B的大小都为7

如果结构体里面包含联合体呢。看之前联合体的定义，联合体中的元素公用同一块内存，所以联合体共用一块内存，其内存大小为最大成员的内存大小，所以所有成员的地址都一样；给联合体某个成员赋值时会影响到另外一个成员的数值。

struct LinkNode {
    char ch;
    char *ptr;
    union {
        short a;
        short b;
        unsigned int c : 2;
        unsigned int d : 1;
    }
    struct LinkNode *next;
}

所以上面的计算是 1 + （空3 + 4）+ 4 + 4 = 16

在这个知识点中还会涉及位域的概念。有些信息在存储时，并不需要占用一个完整的字节，而只需占几个或一个二进制位。例如在存放一个开关量时，只有 0 和 1 两种状态，用 1 位二进位即可。区分是位域还是结构体或者联合体就是看里面在规定时候有没有使用 ":" 进行规定元素的大小。

struct 位域结构名 
{
 位域列表
};

struct bs{
    int a:8;
    int b:2;
    int c:6;
}data;
说明 data 为 bs 变量，共占两个字节。其中位域 a 占 8 位，位域 b 占 2 位，位域 c 占 6 位。

点运算符和箭头运算符

这两个都是用于成员变量的获取，只看C的话基本就是对结构体变量或者结构体指针的操作。之前也比较明晰的是点运算符用于结构体对象，箭头运算符对应的是结构体指针。

实际运用中有点小细节。对于我们开辟的一个结构体数组，例如

struct Article arrArticle[10];

arrArticle，是一个指向第一个数组元素的常量指针。所以 arrArticle->number 指向第一个数组元素的成员 number。简单地说，对于任一的索引值 i，下面 3 个表达式是等价的：（注意按照下标访问和数组基指针进行加减访问在成员访问运算符选择上的区别）

arrArticle[i].number
(arrArticle+i)->number
(*(arrArticle+i)).number

C的一些常用标准库函数

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 -- 用来比较两个元素的函数。

#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 类型的指针。

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对字符串进行排序

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); 

fgets()

C 库函数 char *fgets(char *str, int n, FILE *stream)从指定的流 stream 读取一行，并把它存储在 str 所指向的字符串内。当读取 (n-1) 个字符时，或者读取到换行符时，或者到达文件末尾时，它会停止，具体视情况而定。

• str -- 这是指向一个字符数组的指针，该数组存储了要读取的字符串。
• n -- 这是要读取的最大字符数（包括最后的空字符）。通常是使用以 str 传递的数组长度。
• stream -- 这是指向 FILE 对象的指针，该 FILE 对象标识了要从中读取字符的流。

如果成功，该函数返回相同的 str 参数。如果到达文件末尾或者没有读取到任何字符，str 的内容保持不变，并返回一个空指针。如果发生错误，返回一个空指针。

C和C++的一些区别

没有引用的概念，需要二级指针

C里没有引用，C++里才有，也就没有引用传值之类的。所以会涉及一些二级指针的概念。对函数来说，它所传递的任何参数仅仅是原来参数的一个拷贝。C语言里，改变值只能通过指针（地址）方式进行传递，传递数组也可以改变值，但实际上，传递数组就是传递指针，也就是默认传入了数组的头元素指针。

摘引博客给出一个样例

首先给出一个错误代码

#include <stdio.h>
#include <malloc.h>
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;
void InitLinkList(LNode *L)
{
    L=(LNode *)malloc(sizeof(LNode));
    L->data=0;
    L->next=NULL;
}
int main()
{
    LNode *L=NULL;
    InitLinkList(L);
    printf("%p\n",L);
    return 0;
}

错误点一：该InitLinkList并不能真正初始化一个链表头结点，在函数里我们的确是给L分配了内存，初始化了结点，但是主函数里没有把指针L本身的地址传递进去，InitLinkList()里的L并不是main()里的L，虽然名称是一样的，但是InitLinks()的L是局部的(所以，其实你写成a,b,c,d都没关系)，传进来的只是一个LNode*副本，这个副本和外面的L的内容是一样的，但是变量不是同一个，当这个子函数执行完后，main()里的L还是原来的L。
错误点二：没有释放malloc的内存，在InitLinkList函数中通过malloc分配的内存是通过堆来划分的，这意味着函数调用完毕后，内存不能自动释放，将会造成内存泄漏。

第一个修改方案是直接利用return返回值进行对main函数中L的赋值。

#include <stdio.h>
#include <malloc.h>
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;
LNode * InitLinkList(LNode *L)
{
    L=(LNode *)malloc(sizeof(LNode));
    L->data=0;
    L->next=NULL;
    return L;
}
int main()
{
    LNode *L=NULL;
    L=InitLinkList(L);
    printf("%p\n",L);
    return 0;
}

要么就是修正主函数里面没有直接传入L的地址的错误，在功能函数参数中传入一个二级指针。

#include <stdio.h>
#include <malloc.h>
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;
void InitLinkList(LNode **L)
{
    (*L)=(LNode *)malloc(sizeof(LNode));
    (*L)->data=0;
    (*L)->next=NULL;
}
int main()
{
    LNode *L=NULL;
    InitLinkList(&L);
    printf("%p\n",L);
    return 0;
}

理解二级指针的关键在于，在main中L本身就是一个指针，指向某块内存。取L这个变量的地址作为实参内容传递给initLinkList()函数里的形参，形参就得用指针的指针来存储这个地址变量。那么子函数里面的L的内容不就是main()里L地址么，那么，*L不就是main里L的内容么，也就是说，对*L操作就是对main()里的L进行操作。

如果是数组传参，会简单些，我们可以看看传参上的区别。

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

typedef struct{
    int x;
}test_struct;

void init(test_struct* input){
    input->x = 1;
    input[1].x = 2;
    input[2].x = 3;
}

int main() {
    test_struct *slist = (test_struct*)malloc(sizeof(test_struct)*3);
    init(slist);
    for (int i = 0; i < 3; i++) {
        printf("val: %d \n", slist[i].x);
    }
    return 0;
}

复习下之前的内容：对于我们开辟的一个结构体数组，例如

struct Article arrArticle[10];

arrArticle，是一个指向第一个数组元素的常量指针。所以 arrArticle->number 指向第一个数组元素的成员 number。简单地说，对于任一的索引值 i，下面 3 个表达式是等价的：（注意按照下标访问和数组基指针进行加减访问在成员访问运算符选择上的区别）

arrArticle[i].number
(arrArticle+i)->number
(*(arrArticle+i)).number

struct 和 typedef struct

在C++ 中， 虽然结构体用的也不多，结构体的定义模式是这样的：

struct Student{
    int name;
};

于是就定义了结构体类型Student，声明变量时直接Student stu1；

在C里面，定义结构体的写法

typedef struct Student
{
    int name;
}Stu;

于是在声明变量的时候就可：Stu stu1;(如果没有typedef就必须用struct Student stu1;来声明)这里的Stu实际上就是struct Student的别名。

在C++里面也可以附加typedef进行别名的设置。

struct Student
{
    int name;
}stu1; // 这边的stu1是一个变量

typedef struct Student2
{
    int name;
}stu2; // 这边就是一个别名

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（LeetCode387）

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;
}