C语言算法宝库：从基础数据结构到经典算法实现

#include <stdio.h>
#include "audio/alaw.c"

int main() {
    int16_t pcm[] = {1000, -1000, 1234, 3200};
    uint8_t alaw[4];
    int16_t decoded[4];
    
    // 编码
    encode(alaw, pcm, 4);
    
    // 解码
    decode(decoded, alaw, 4);
    
    return 0;
}

#include <stdio.h>
#include "cipher/affine.c"

int main() {
    char text[] = "Hello World!";
    affine_key_t key = {7, 11};
    
    printf("原始文本: %s\n", text);
    
    // 加密
    affine_encrypt(text, key);
    printf("加密后: %s\n", text);
    
    // 解密
    affine_decrypt(text, key);
    printf("解密后: %s\n", text);
    
    return 0;
}

#include <stdio.h>
#include "data_structures/binary_trees/basic_operations.c"

int main() {
    struct node* root = NULL;
    
    // 插入节点
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    
    // 中序遍历
    printf("中序遍历: ");
    inOrderTraversal(root);
    
    return 0;
}

/**
 * @brief 16bit pcm to 8bit alaw
 * @param out unsigned 8bit alaw array
 * @param in  signed 16bit pcm array
 * @param len length of pcm array
 * @returns void
 */
void encode(uint8_t *out, int16_t *in, size_t len)
{
    uint8_t alaw = 0;
    int16_t pcm = 0;
    int32_t sign = 0;
    int32_t abcd = 0;
    int32_t eee = 0;
    int32_t mask = 0;
    
    for (size_t i = 0; i < len; i++)
    {
        pcm = *in++;
        eee = 7;
        mask = 0x4000;  // 0x4000: '0b0100 0000 0000 0000'
        
        // 获取符号位
        sign = (pcm & 0x8000) >> 8;
        
        // 将负数转换为正数进行处理
        pcm = pcm < 0 ? (~pcm >> 4) : pcm;
        
        // 查找量化级别
        while ((mask & pcm) == 0 && eee > 0)
        {
            mask >>= 1;
            eee--;
        }
        
        // 提取abcd位
        abcd = (pcm >> (eee ? (eee + 3) : 4)) & 0x0f;
        alaw = (uint8_t)(sign | eee << 4 | abcd);
        alaw ^= 0xd5;
        *out++ = alaw;
    }
}

/**
 * @brief finds the value x such that (a * x) % m = 1
 * @param a number we are finding the inverse for
 * @param m the modulus the inversion is based on
 * @returns the modular multiplicative inverse of `a` mod `m`
 */
int modular_multiplicative_inverse(unsigned int a, unsigned int m)
{
    int x[2] = {1, 0};
    div_t div_result;

    if (m == 0) {
        return 0;
    }
    a %= m;
    if (a == 0) {
        return 0;
    }

    div_result.rem = a;

    while (div_result.rem > 0)
    {
        div_result = div(m, a);
        m = a;
        a = div_result.rem;

        // 计算当前迭代的x值
        int next = x[1] - (x[0] * div_result.quot);
        x[1] = x[0];
        x[0] = next;
    }

    return x[1];
}

/**
 * @brief Encrypts character string `s` with key
 * @param s string to be encrypted
 * @param key affine key used for encryption
 * @returns void
 */
void affine_encrypt(char *s, affine_key_t key)
{
    for (int i = 0; s[i] != '\0'; i++)
    {
        int c = (int)s[i] - Z95_CONVERSION_CONSTANT;
        c *= key.a;
        c += key.b;
        c %= ALPHABET_SIZE;
        s[i] = (char)(c + Z95_CONVERSION_CONSTANT);
    }
}

/**
 * @brief Insertion procedure, which inserts the input key in a new node in the tree
 * @param root pointer to parent node
 * @param data value to store in the new node
 * @returns pointer to parent node
 */
node *insert(node *root, int data)
{
    // 如果子树根节点为空，在此处插入键值
    if (root == NULL)
    {
        root = newNode(data);
    }
    else if (data > root->data)
    {
        // 如果不为空且输入键值大于根键值，插入右叶子
        root->right = insert(root->right, data);
    }
    else if (data < root->data)
    {
        // 如果不为空且输入键值小于根键值，插入左叶子
        root->left = insert(root->left, data);
    }
    // 返回修改后的树
    return root;
}

/**
 * Node, the basic data structure in the tree
 */
typedef struct node
{
    struct node *left;  // 左子节点
    struct node *right; // 右子节点
    int data;           // 节点数据
} node;

/**
 * The node constructor
 * @param data data to store in a new node
 * @returns new node with the provided data
 */
node *newNode(int data)
{
    node *tmp = (node *)malloc(sizeof(node));
    tmp->data = data;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}

/**
 * @brief Vector structure definition
 */
typedef struct {
    int len;           // 向量长度
    int current;       // 当前项索引
    int* contents;     // 内部数组指针
} Vector;

/**
 * @brief Initialize vector with size 1
 * @param vec pointer to Vector struct
 * @param val initial value
 */
void init(Vector* vec, int val) {
    vec->contents = (int*)malloc(sizeof(int));
    vec->contents[0] = val;
    vec->current = 0;
    vec->len = 1;
}

/**
 * @brief Push value to end of vector
 * @param vec pointer to Vector struct
 * @param val value to be pushed
 */
void push(Vector* vec, int val) {
    vec->contents = realloc(vec->contents, (sizeof(int) * (vec->len + 1)));
    vec->contents[vec->len] = val;
    vec->len++;
}

/**
 * @brief Get item at specified index
 * @param vec pointer to Vector struct
 * @param index index to get value from
 * @returns value at index or -1 if out of bounds
 */
int get(Vector* vec, int index) {
    if(index < vec->len) {
        return vec->contents[index];
    }
    return -1;
}

/**
 * @brief The main function that finds the shortest path from given source
 * to all other vertices using Dijkstra's Algorithm.
 */
void Dijkstra(struct Graph *graph, int src)
{
    int V = graph->vertexNum;
    int mdist[V];  // 存储到顶点的更新距离
    int vset[V];   // vset[i]为true表示顶点i包含在最短路径树中

    // 初始化mdist和vset，设置源点距离为0
    for (int i = 0; i < V; i++) {
        mdist[i] = INT_MAX;
        vset[i] = 0;
    }

    mdist[src] = 0;

    // 迭代查找最短路径
    for (int count = 0; count < V - 1; count++)
    {
        int u = minDistance(mdist, vset, V);
        vset[u] = 1;

        for (int v = 0; v < V; v++)
        {
            if (!vset[v] && graph->edges[u][v] != INT_MAX &&
                mdist[u] + graph->edges[u][v] < mdist[v])
                mdist[v] = mdist[u] + graph->edges[u][v];
        }
    }

    print(mdist, V);
}