数据结构和算法库是程序编写最基础的库之一。字符串是人类语言的记录，是计算机处理的主要对象，因此字符串数据和算法是重中之重。

C和C++

由于C语言不提供数据结构和算法库，这里专指C++的STL stand template library。

数据结构

vector 是一个动态数组，随机访问时间O(1)，可以快速地在末尾插入或删除元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6);

    for (int val : vec) {
        std::cout << val << " ";  // 输出：1 2 3 4 5 6
    }
    std::cout << std::endl;

    std::cout << vec[2] << std::endl;  // 访问元素 3
    return 0;
}

list 是双向链表，能高效插入或删除元素，但不提供随机访问接口

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    lst.push_back(6);  // 在末尾插入元素
    lst.push_front(0); // 在头部插入元素

    for (int val : lst) {
        std::cout << val << " ";  // 输出：0 1 2 3 4 5 6
    }
    return 0;
}

deque 是双端队列，头部和尾部可以进行高效的插入和删除操作。deque也提供随机访问接口

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <deque>
#include <iostream>

int main() {
    std::deque<int> deq = {1, 2, 3, 4, 5};
    deq.push_back(6);   // 在尾部添加元素
    deq.push_front(0);  // 在头部添加元素

    for (int val : deq) {
        std::cout << val << " ";  // 输出：0 1 2 3 4 5 6
    }
    return 0;
}

set 是一个集合，自动排序且不允许重复元素。unordered_set 是一个不排序的集合，元素根据哈希值存储，允许快速查找和插入。

map 是一个映射，存储键值对（key-value），并根据键进行排序。unordered_map 是一个无序映射，存储键值对，使用哈希表进行存储。

1
2
3
4
5
6
7
8
9
10
11
#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> um = {{1, "one"}, {2, "two"}, {3, "three"}};

    for (const auto& pair : um) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

迭代器，C++ STL使用迭代器来标识容器中的元素，以及实现容器中元素的访问。迭代器支持*和->运算符来解引用或访问元素成员变量

  1. 随机访问迭代器 (Random Access Iterator)，类似指针，通过加减算数提供随机访问。对应容器std::vector、std::deque、std::array。支持随机访问迭代器作为参数的算法函数，一般也支持指针作为参数。
  2. 双向迭代器(Bidirectional Iterator)，允许在容器中向前和向后移动。对应容器std::list、std::set、std::map。

迭代器是使用继承结构组织的，随机访问迭代器也是一种双向迭代器

算法

std::sort：对容器中的元素进行排序，默认升序。需要传入随机访问迭代器作为参数

std::sort是不稳定的，std::stable_sort提供稳定排序，即保证相同元素的相对顺序

1
2
3
4
5
std::vector<int> vec = {4, 2, 9, 1};
std::sort(vec.begin(), vec.end());  // 升序排序
std::sort(vec.begin(), vec.end(), [](int a, int b) {  // 降序
        return a > b;
    });

std::find：查找容器中的某个元素，返回第一个匹配元素的迭代器。传入双向迭代器即可

1
2
3
4
auto it = std::find(vec.begin(), vec.end(), 2);
if (it != vec.end()) {
    // 找到了元素
}

std::lower_bound，传入排序好的数组，返回第一个大于或等于指定元素的迭代器。
std::upper_bound：返回指向已排序数组中第一个大于指定元素的迭代器。

需要传入随机访问迭代器

1
2
auto it = std::lower_bound(vec.begin(), vec.end(), 3);
auto it = std::upper_bound(vec.begin(), vec.end(), 3);

std::reverse：反转容器中的元素顺序。

1
std::reverse(vec.begin(), vec.end());

std::fill：将容器中的所有元素设置为指定值。

1
std::fill(vec.begin(), vec.end(), 0);

std::transform：对容器中的每个元素应用指定的操作。

1
std::transform(vec.begin(), vec.end(), vec.begin(), [](int x) { return x * 2; });

std::copy：将容器中的元素复制到另一个容器。std::swap：交换两个容器的内容。std::move：移动容器的元素，避免复制。

1
2
3
std::copy(vec, dest);
std::swap(vec, dest);
std::vector<int> new_vec = std::move(vec);

std::count：统计容器中某个元素出现的次数。std::count_if：统计符合特定条件的元素的数量。

1
2
int count = std::count(vec.begin(), vec.end(), 2);
int count = std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

std::accumulate：对容器中的元素进行累加。

1
int sum = std::accumulate(vec.begin(), vec.end(), 0);

std::min_element：返回容器中最小元素的迭代器。std::max_element：返回容器中最大元素的迭代器。

1
2
auto min_it = std::min_element(vec.begin(), vec.end());
auto max_it = std::max_element(vec.begin(), vec.end());

字符串处理函数

由于C++兼容C语言，因此支持C风格和C++风格的字符串处理算法。C风格字符串函数参数是指针，C++风格是随机访问迭代器。

C风格的字符串处理函数, 在C++中，执行#include <cstring>，C语言的字符串处理函数作为std namespace的全局函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// strcpy(dest, src), strncpy(dest, src, n), 字符串拷贝
char src[] = "Hello, World!";
char dest[20];
std::strcpy(dest, src);
std::strncpy(dest, src, 5);

// strcat(str1, str2) 将str2拼接到str1
std::strcat(str1, str2); 
std::strncat(str1, str2, 5);

// strlen(str)，返回 C 风格字符串的长度（不包括 \0 终止符）

// strcmp(str1, str2), strncmp(str1, str2, n) 如果str1 > str2, 返回大于0
std::strcmp(str1, str2)

// strchr(str, c)，查找字符c在字符串str中第一次出现的位置。如果找到了，返回指向该字符的指针；如果没找到，返回 nullptr。
char* ptr = std::strchr(str, 'o');

// strstr(str, sub), 查找子字符串sub在字符串str中的第一次出现。如果找到了，返回指向子字符串的指针；如果没找到，返回 nullptr。
const char* str = "Hello, World!";
const char* sub = "World";
char* ptr = std::strstr(str, sub);

// memset(str, c, n) 按字节为单位对内存初始化
char str[20];
std::memset(str, '*', 5);  // 将前 5 个字符设置为 '*'

memcpy(dest, src, n) 从src拷贝n个字节到dest
char src[] = "Hello";
char dest[10];
std::memcpy(dest, src, 6);

C++ string是动态字符串，如果希望字符串不可变，可以使用const修饰。string支持的函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// size() 或 length() 获取字符串长度

// append(string)，将内容追加
std::string str = "Hello";
str.append(", World!"); 

// push_back(c)，添加一个字符
str.push_back('!');

// insert(index, string), 指定位置插入字符串
str.insert(5, ", World");

// erase(index, length), 删除指定位置区间的字符串
str.erase(5, 7);  // 从位置 5 开始删除 7 个字符

// replace(index, length, newstring), 替换字符串中的指定部分。
str.replace(7, 5, "C++");

// resize(size) 改变字符串的大小，如果增加字符则填充，减少字符则截断。
str.resize(5);

// std::find(string) 查找子字符串首次出现的位置。如果找不到返回 std::string::npos。rfind, 从字符串末尾向前查找字符串
size_t pos = str.find("World");

// find_first_of(),find_last_of()
size_t pos = str.find_first_of("o");

// substr(index, length) 提取子字符串
std::string sub = str.substr(7, 5); 

// compare 字符串比较
std::string str1 = "Hello";
std::string str2 = "World";
int result = str1.compare(str2);

// stoi(), stol(), stoll() 字符串转为整型
int num = std::stoi(str);

// to_string()，转为字符串
std::string str = std::to_string(num);

// c_str(), data() 返回 C 风格字符串（const char*）。
const char* cstr = str.c_str();

JAVA

数据结构

ArrayList，等于C++的vector，动态数组。JAVA的List是一个接口，包括动态数组和链表。

1
2
3
4
5
6
7
import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
System.out.println(list);  // 输出: [Apple, Banana, Cherry]

LinkedList，双向链表，相当于C++的list

1
2
3
import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();

HashSet, 基于哈希表实现，不保证元素的顺序。

LinkedHashSet, 基于哈希表和链表实现，能够保证元素的插入顺序。

TreeSet, 基于红黑树实现，元素按自然顺序或自定义顺序排列。

HashMap，基于哈希表实现，允许 null 键和值。

LinkedHashMap，基于哈希表和链表实现，保持插入顺序（或访问顺序）

TreeMap，基于红黑树实现，键按自然顺序或自定义顺序排序。

PriorityQueue，基于堆实现的队列，元素按优先级顺序排列

LinkedList 也可以实现 Queue 接口，支持双端队列操作。

1
2
3
4
5
6
7
8
9
import java.util.LinkedList;
import java.util.Queue;

Queue<String> queue = new LinkedList<>();
queue.add("Apple");
queue.add("Banana");
queue.add("Cherry");
System.out.println(queue.poll());  // 输出: Apple（出队）
System.out.println(queue);  // 输出: [Banana, Cherry]

算法

Arrays.sort() 用于对数组进行排序，数组是基本类型数组int[] arr ，或对象数组new Integer[10]

Collections.sort() 用于对集合（如 List）进行排序

1
2
3
4
5
6
7
8
9
import java.util.*;

public class SortExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 3));
        Collections.sort(list);
        System.out.println(list);  // 输出: [1, 2, 3, 5, 8]
    }
}

Arrays.binarySearch()，数组查找；Collections.binarySearch()在容器查找

1
2
3
4
5
6
7
8
9
import java.util.*;

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 5, 8));
        int index = Collections.binarySearch(list, 5);
        System.out.println(index);  // 输出: 3
    }
}

Arrays.fill(), Collections.fill() 填充

1
2
3
4
5
public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    Collections.fill(list, 10);
    System.out.println(list);  // 输出: [10, 10, 10, 10, 10]
}

Collections.shuffle() 用于随机打乱 List 中元素的顺序

1
2
3
4
5
public static void main(String[] args) {
    List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    Collections.shuffle(list);
    System.out.println(list);  // 输出: 随机打乱后的结果
}

字符串处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 创建
String str1 = "Hello"; // 字符串字面量
String str2 = new String("Hello"); // 使用构造函数

// length() 获得长度
int length = str.length();

s.charAt(0)  // 访问字符

String sub = s.substring(0, 5);  // 切片

String result = s1 + " " + s2;  // 使用 + 拼接

StringBuilder sb = new StringBuilder();  // 利用StringBuilder
sb.append("Hello");
sb.append(" ");

String trimmed = s.trim();  // 去除两端空白字符

String s = "Hello, World!";
int index = s.indexOf("World");  // 查找子字符串的索引位置

String upper = s.toUpperCase();  // 转为大写

String formatted = String.format("My name is %s and I am %d years old.", name, age);  // 字符串格式化

String s = "apple,banana,cherry";
String[] fruits = s.split(",");  // 按逗号分割字符串

JAVA的String是不可变的（String类被声明成final），String 字符串每次拼接都会创建新的对象。

StringBuilder 和 StringBuffer 是用于可变字符串的类。StringBuilder只能用于单线程环境，StringBuffer则是线程安全的。

修改字符串某位置的字符

1
2
3
4
5
6
7
8
9
10
11
// String 字符串不可修改某位置字符，可以利用stringBuilder
StringBuilder sb = new StringBuilder("Hello");
sb.setCharAt(1, 'a');
System.out.println(sb.toString());  // 输出: Hallo

// 字符数组可以修改某位置字符
String str = "Hello";
char[] charArray = str.toCharArray();
charArray[1] = 'a';
String modifiedStr = new String(charArray);
System.out.println(modifiedStr);  // 输出: Hallo

Go

数据结构

golang 用语言关键字提供了容器，不必额外导入包

数组, 固定大小的同一类型的元素。Go 数组的大小在声明时确定并且内容不可更改。

1
2
3
4
var arr [5]int // 定义一个长度为 5 的整型数组
arr[0] = 1
arr[1] = 2
fmt.Println(arr) // 输出: [1 2 0 0 0]

切片slice，动态数组。[]byte表示动态字符串。

1
2
3
4
5
// 创建切片
slice := []int{1, 2, 3, 4, 5}

// 添加元素
slice = append(slice, 6)

map，哈希表实现的容器，允许通过键来快速查找和存储值，无序

1
2
3
4
5
6
myMap := map[string]int{
    "apple":  5,
    "banana": 3,
}
// 插入或更新元素
myMap["orange"] = 7

链表，使用container/list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package main

import (
    "container/list"
    "fmt"
)

func main() {
    l := list.New()
    l.PushBack(1) // 在链表尾部插入
    l.PushFront(0) // 在链表头部插入

    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value) // 输出: 0 1
    }
}

channel，channel可认为是一个线程安全的协程间消息/任务队列

算法

排序，import “sort”标准库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main

import (
	"sort"
)

func main() {
	numbers := []int{5, 2, 9, 1, 5, 6}

	sort.Ints(numbers) // 排序，可以选择Ints, Strings, Stable等
}

// 自定义类型排序
type Person struct {
	Name string
	Age  int
}

type ByAge []Person

func (a ByAge) Len() int           { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	people := []Person{
		{"Alice", 25},
		{"Bob", 20},
		{"Charlie", 30},
	}

	sort.Sort(ByAge(people)) // 排序
}

字符串处理函数

Go中，string是不可变的 UTF-8 编码字符串, 无法原地修改字符串（编译失败）。[]byte是字符序列切片，可原地修改字符串。

1
2
3
4
5
s := "Hello, World!"
b := []byte(s) // 将 string 转换为 []byte

b := []byte{72, 101, 108, 108, 111}
s := string(b) // 将 []byte 转换为 string

字符串处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
str := "Hello"
len(str)  // 返回长度
str[1]  // 根据索引查看字符

str1 := "Hello"
str2 := "World"
result := str1 + ", " + str2  // + 拼接字符串

strings.Index(str, "World")  // 查找字符串
strings.Contains(str, "World")

strings.Split(str, ",")  // 字符串分割，返回字符串数组
strings.TrimSpace(str)  // 去掉两侧空白

strings.ToUpper(str)  // 字符串大小写
strings.ToLower(str)

strings.HasPrefix(str, "go")  // 字符串前后缀
strings.HasSuffix(str, ".org")

result := fmt.Sprintf("Name: %s, Age: %d", name, age) // 格式化生成字符串

strconv.Atoi(numStr) // 字符串转整数

Python

数据结构

列表，动态数组。和go一样，python列表支持切片。

1
2
3
my_list = [1, 2, 3, 4, 5]
my_list[0] = 10
my_list.append(6)

元组Tuple，不可变，只可被访问

1
2
my_tuple = (1, 2, 3)
a, b, c = my_tuple

字典dict, 无序（Python 3.7 及以上版本中插入有序）、键值对、键唯一

1
2
my_dict = {"name": "Alice", "age": 25}
my_dict["age"] = 30

集合set，无序、不重复。

1
2
my_set = {1, 2, 3, 4, 5}
my_set.add(6)

有序字典, 保留键值对插入顺序

1
2
3
4
5
from collections import OrderedDict

ordered_dict = OrderedDict()
ordered_dict["a"] = 1
ordered_dict["b"] = 2

算法

排序

sorted(iterable, key=None, reverse=False), 返回一个新的排序列表，不改变原列表。

1
2
3
4
5
6
nums = [5, 2, 9, 1]
print(sorted(nums))  # 升序: [1, 2, 5, 9]
print(sorted(nums, reverse=True))  # 降序: [9, 5, 2, 1]

words = ["apple", "banana", "cherry"]
print(sorted(words, key=len))  # 按字符串长度排序: ['apple', 'cherry', 'banana']

list.sort(), 原地排序，直接修改列表

1
2
nums = [5, 2, 9, 1]
nums.sort()

字典排序

1
2
3
my_dict = {"b": 2, "a": 1, "c": 3}
sorted_keys = sorted(my_dict)  # 按键排序
sorted_items = sorted(my_dict.items(), key=lambda item: item[1])  # 按值排序

字符串处理

1
2
3
4
5
6
7
8
9
10
11
12
13
s = "Hello"
len(s)
s[1]
s[-1]
s[1:3]
s + " "  # 拼接
print(f"My name is {name} and I am {age} years old.")  # 格式化输出, python3支持
s.upper()，s.lower()
s.strip()  # 去除空格
s.find("World")
s.replace("World", "Python")

s.split(",")

对于python2, 还有个编码的问题。处理办法是，对于u开头的字符串或者unicode类型的字符串，都使用encode(“utf-8”) 编码为str类型后，再使用。

1
2
3
4
5
6
7
# coding=utf-8
unicode_str = u"中文"  # Unicode 字符串
byte_str = "byte"  # 字节字符串
print(type(unicode_str))  # <type 'unicode'>
print(type(byte_str))  # <type 'str'>

print(type(unicode_str.encode("utf-8")))  # <type 'str'>