嵌入式八股文面试题（二）C语言算法

相关概念请查看文章：C语言概念。

1. 如何实现一个简单的内存池？

简单实现：

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

//内存块
typedef struct MemoryBlock {
    void *data; // 内存块起始地址
    struct MemoryBlock *next; // 下一个内存块的地址
} MemoryBlock;

//内存池
typedef struct MemoryPool {
    MemoryBlock *freeList; // 空闲内存块链表
    MemoryBlock *usedList; // 占用内存块链表
    int freeCount; // 空闲内存块数量
    int usedCount; // 占用内存块数量
    int blockCount; // 内存块总数量
} MemoryPool;
//初始化内存池
MemoryPool *InitMemoryPool(int blockSize, int blockCount) {
    MemoryPool *pool = (MemoryPool *)malloc(sizeof(MemoryPool)); // 为内存池分配空间
    if (pool == NULL) {
        printf("Failed to allocate memory pool!\n");
        return NULL;
    }
    pool->freeList = NULL;
    pool->usedList = NULL;
    pool->freeCount = 0;
    pool->usedCount = 0;
    pool->blockCount = blockCount;
    for (int i = 0; i < blockCount; i++) {
        // 创建内存块节点，插入到空闲链表
        MemoryBlock *block = (MemoryBlock *)malloc(sizeof(MemoryBlock));
        block->data = malloc(blockSize);
        block->next = pool->freeList;
        pool->freeList = block;
        pool->freeCount++;
    }
    return pool;
}
//分配内存块
void *AllocateBlock(MemoryPool *pool) {
    if (pool->freeList == NULL || pool->freeCount == 0) {
        printf("No free blocks available!\n");
        return NULL;
    }
    MemoryBlock *node = pool->freeList;
    // 将该内存块从空闲链表删除
    pool->freeList = node->next;
    // 将该内存块插入到占用链表
    node->next = pool->usedList;
    pool->usedList = node;
    // 更新空闲和占用状态
    pool->usedCount++;
    pool->freeCount--;
    return node->data;
}
//释放内存块
void FreeBlock(MemoryPool *pool, void *data) {
    MemoryBlock *cur = pool->usedList;
    MemoryBlock *pre = NULL;
    // 寻找该内存块的节点
    while (cur != NULL && cur->data != data) {
        pre = cur;
        cur = cur->next;
    }
    if (cur == NULL) {
        printf("Error: Data not found!\n");
        return;
    }
    // 将该内存块从占用链表删除
    if (pre != NULL)
        pre->next = cur->next;
    else
        pool->usedList = cur->next;
    // 将该内存块插入到空闲链表
    cur->next = pool->freeList;
    pool->freeList = cur;
    pool->freeCount++;
    pool->usedCount--;
}
//销毁内存块
void DestroyMemoryPool(MemoryPool *pool) {
    if (pool == NULL) return;
    MemoryBlock *cur = NULL;
    // 释放所有空闲内存块空间
    while (pool->freeList != NULL) {
        cur = pool->freeList;
        pool->freeList = pool->freeList->next;
        free(cur->data);
        free(cur);
    }
    // 释放所有占用内存块空间
    while (pool->usedList != NULL) {
        cur = pool->usedList;
        pool->usedList = pool->usedList->next;
        free(cur->data);
        free(cur);
    }
    // 释放内存池空间
    free(pool);
}
int main(void) {
    MemoryPool *pool;
    pool = InitMemoryPool(10, 5); // 初始化内存池
    int *str = (int *)AllocateBlock(pool);  //申请内存块1
    *str = 2;
    int *ptr = (int *)AllocateBlock(pool); //申请内存块2
    *ptr = 3;
    printf("free block : %d, used block : %d\n", pool->freeCount, pool->usedCount);
    FreeBlock(pool, ptr); //释放内存块2
    printf("free block : %d, used block : %d\n", pool->freeCount, pool->usedCount);
    DestroyMemoryPool(pool); 
    return 0;
}

打印结果：

2. 实现一个双向链表。

双向链表是一种每个节点都有两个指针，一个指向下一个节点，一个指向前一个节点的数据结构。可以在任意位置进行快速插入和删除。

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

// 双向链表节点
typedef struct Node {
    int data;
    struct Node *prev; //连接前一个节点的指针
    struct Node *next; //连接下一个节点的指针
} Node;

// 创建新节点
Node* createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// 插入节点到链表的尾部
void append(Node **head, int data) {
    Node *newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->prev = temp;
    }
}
//删除一个节点
void delete_node(Node **head, int data) {
    if (*head == NULL){  // 如果链表为空
        printf("链表为空，没有要删除的元素\n");
        return;
    }
    Node *temp = *head;
    
    // 如果删除的是头节点
    if (temp->data == data) {
        *head = temp->next;  // 更新头节点
        if (*head != NULL) {  // 如果不是空链表
            (*head)->prev = NULL;
        }
        free(temp);
        return;
    }
    // 找到要删除的节点
    while (temp != NULL && temp->data != data) {
        temp = temp->next;
    }
    // 如果没有找到该节点
    if (temp == NULL) {
        printf("未找到数据为 %d 的节点\n", data);
        return;
    }
    // 删除的是中间或尾部节点
    if (temp->next != NULL) {
        temp->next->prev = temp->prev;  // 更新下一个节点的prev指针
    }
    if (temp->prev != NULL) {
        temp->prev->next = temp->next;  // 更新前一个节点的next指针
    }
    free(temp);
}
// 打印双向链表
void printList(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node *head = NULL;
    append(&head, 10);
    append(&head, 20);
    append(&head, 30);
    printList(head);
    delete_node(&head, 30);
    printList(head);
    return 0;
}

打印结果：