前言

https://github.com/guofei9987/c-algorithm

动态数组

• 动态数组-int
• 动态数组-指针（泛型）
• 循环数组

链表

• 链表-int
• 链表-指针（泛型）

Hash

String

tree

关于泛型

C 语言作为静态语言，必须事先确定数据类型。
为了防止链表要分别写 int、float、double 等不同的版本，使用一些编程技巧，达成泛型的目的

宏替换

• #define DATA_TYPE int
• 代码原始、能力有限、每次只能编译1个类型
• 常用于 demo

宏替换升级版

// vector_template.h

typedef struct {
    DATA_TYPE* data;
    int size;
} VECTOR;

void VECTOR_push(VECTOR* v, DATA_TYPE x);


// 然后用宏来生成不同数据结构的版本：
#define DATA_TYPE int
#define VECTOR vector_int
#define VECTOR_push vector_int_push
#include "vector_template.h"

#define DATA_TYPE float
#define VECTOR vector_float
#define VECTOR_push vector_float_push
#include "vector_template.h"

特点：

1. 支持多个类型
2. 编译期展开

方法2: void* data

• 工程级
• 运行时泛型
• 单次实现，支持所有类型

静态数组

int arr[] = {1, 2, 4};

动态数组

动态数组-int

dynamic_array.h

dynamic_array.c

动态数组-泛型

1. 为了实现泛型，使用 void* data 来定义数据类型
2. 这里的底层使用的是数组，因此，使用 void ** 指向这个数组指针
3. 数组指针中的一个元素（指针）指向一个结构体
4. 可以用来做stack

dynamic_array_p.h

dynamic_array_p.c

链表

链表-int

linked_list.h

linked_list.c

说明

• 我试着把新的node定义在栈上，但不成功，因为在循环中重复定义，还是指向同一块内存
• 看 leetcode 上也都是用 malloc 放到堆上的
• C++ 的 new 方法，也是放到堆上的

链表-泛型

侵入式链表

上一种实现的缺点：

1. 每个节点（一个 struct）访问 next 的时候（pCurrent->next），都要做指针偏移
2. 链表很多算法都要频繁做 next，这就有大量的偏移操作（？？？为什么不把next放到第一个个字段）
3. 如果节点拥有的数据类型是有变化的，这个偏移量也是有变化的（？？？导致什么问题呢）

linked_list_new.h

linked_list_new.c

知识点：

1. 先定义一个函数指针，实现中使用这个函数指针。用户时候的时候再定义这个函数指针。
2. 实现一个只有 next 的链表。用户自定义的类把它“包起来”。使用时做指针转换，因为它俩指向同一个内存。

双向链表

循环链表

链表中，初始化的时候把指针指向自己。不多说。

栈

可以用数组来模拟栈，
（后面添加）
关键代码

#define MAX_SIZE 1024

typedef struct SEQSTACK{
	void* data[MAX_SIZE];
	int size;
}SeqStack;

3种方式

• 静态数组
• 动态数组
• 链表。链表的头是栈顶

队列

也是用数组来模拟

出队的时，是做个遍历，把后一个复制到前一个。

（好像用链表效率更高？）

实现方式

• 静态数组做环形

二叉树

typedef struct BINARYNODE{
	char ch;
	struct BINARYNODE* lchild;
	struct BINARYNODE* rchild;
}BinaryNode;

编程技巧

c的一些编程技巧

数值

n&(n-1) 作用是消除数字 n 的二进制表示中的最后一个 1

不用临时变量交换两个数

int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1