嵌入式八股文面试题（二）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;elsepool->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); //释放内存块2printf("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;
}

打印结果：