# algorithm_c_cpp

**Repository Path**: hjunsong/algorithm_c_cpp

## Basic Information

- **Project Name**: algorithm_c_cpp
- **Description**: 一些c/c++实现的算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-03-05
- **Last Updated**: 2025-03-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: Algorithm, Cpp, OpenCV

## README

# algorithm c/c++

一些 c/c++实现的算法。
代码目录说明：

> - `common`: 一些公共的方法封装或者定义
> - `lcs`: 最长公共子串算法，c 语言版
> - `list`: 双向链表，c 语言版
> - `btree`: B 树（B-tree）算法
>   - `btree/draw_btree`: 绘制 B-tree
> - `b+tree`: B+树（B+tree）算法
>   - `b+tree/draw_b+tree`: 绘制 B+tree
> - `multidimensional_array`: 多维数组
> - `01_knapsack`: 01 背包问题
> - `heap`: 堆（heap）, 通用版：任意元素类型的堆(非基础类型时，需使用指针)
>   - `heap/draw_heap`: 绘制堆
>   - `heap/heap_sort`: 堆排序
>   - `heap/int_heap`: 丐版堆实现：仅支持元素类型为`int`的堆
> - `KMP`: KMP 算法(Knuth-Morris-Pratt 算法)，高效的搜索子串(字符串匹配)算法
> - `test`: 测试代码

## 编译

### 编译环境

linux 系统，安装好 gcc、g++、make<br>
推荐 centos 7，任意子版本都行

### 编译命令

1. 进入 test 目录

```bash
cd test
```

2. 编译

```bash
# 首次编译
make -f Makefile

# 重新编译（建议每次都使用这个）
make -f Makefile rebuild
```

编译成功后，会在 test 目录生成可执行文件 hjs_test

## 运行测试

各算法运行测试的命令如下：

1. 最长公共子串(lcs)

```bash
./hjs_test lcs
```

2. 双向链表(dl_list)

```bash
# 插入测试
./hjs_test list insert

# 删除测试
./hjs_test list delete

# 查询测试
./hjs_test list get

# list托管元素的内存
./hjs_test list memory
```

3. B 树(B-tree)

```bash
# 基础测试
./hjs_test btree basic

# 绘制btree测试
./hjs_test btree draw basic/highlight_node/key_diff_color/left_rotate/right_rotate/merge/delete

# 插入测试
./hjs_test btree insert

# 删除测试
./hjs_test btree delete

# 查找key
./hjs_test btree search

# 由btree来管理每个key的内存，用户无需关心每个key内存的释放
./hjs_test btree memory

# 测试遍历
#   1). 顺序遍历
./hjs_test btree traverse sequence

#   2). 逆序遍历
./hjs_test btree traverse reverse

#   3). 搜索遍历
./hjs_test btree traverse search

#   4). 逐层遍历
./hjs_test btree traverse layer
```

4. 多维数组(multidimensional array, mda)

```bash
# 基本测试
./hjs_test mda
```

5. 01 背包问题(01 knapsack problem)

```bash
# 基本测试
./hjs_test 01kp
```

6. 堆(heap)

```bash
# 绘制堆测试(通用堆heap，相对于非通用堆intHeap)
./hjs_test heap draw

# 插入测试(通用堆heap)
./hjs_test heap insert

# 删除测试(通用堆heap)
./hjs_test heap delete

# 遍历堆测试（包括：前序遍历、中序遍历、后续遍历和层序遍历）(通用堆heap)
./hjs_test heap traverse

# 元素为int类型的堆测试（非通用的intHeap）
 ./hjs_test heap int_heap

# 堆排序测试
#   1). 对char类型的数组进行堆排序
./hjs_test heap sort char

#   2). 对int类型的数组进行堆排序
./hjs_test heap sort int

#   3). 通用版对排序（支持任意类型，当非基础类型时需要使用指针）
./hjs_test heap sort common

#   4). 没有使用struct heap的堆排序（直接利用堆的"堆化"和"删除"原理的堆排序）
./hjs_test heap sort direct

```

7. B+树(B+tree)

```bash
# 1) 基础测试
./hjs_test b+tree basic
# 2) 插入测试
./hjs_test b+tree insert
# 3) 遍历测试
./hjs_test b+tree traverse
# 4) 绘制B+tree测试
./hjs_test b+tree draw
# 5) 删除测试
./hjs_test b+tree delete
# 6) 搜索测试
./hjs_test b+tree search
# 7) 与btree比较测试
./hjs_test b+tree compare_btree
# 8) 优化测试
./hjs_test b+tree optimize
# 9) 内存托管测试
./hjs_test b+tree memory
#10) 绘图着色测试
#   10.1 高亮节点
./hjs_test b+tree draw_color highlight_node
#   10.2 高亮key
./hjs_test b+tree draw_color highlight_key
#   10.3 高亮临时状态b+tree中节点和key
./hjs_test b+tree draw_color temporary
#11) blog绘图
#   11.1 分裂操作配图
./hjs_test b+tree blog split
#   11.1 借位(旋转)操作配图
./hjs_test b+tree blog borrow
#   11.1 合并操作配图
./hjs_test b+tree blog merge
#   11.1 搜索操作配图
./hjs_test b+tree blog search
```

8. KMP 算法

```bash
# 基本测试
./hjs_test kmp
```