#include <stdio.h> #include <stdlib.h> #define DEFAULT_SIZE 5 // 静态链表的容量（包括头结点） /** * 静态链表节点结构 * 使用数组下标代替指针来实现链式存储 */ typedef struct StaticLinkedNode { char data; // 存储的字符数据 int next; // 下一个节点在数组中的下标，-1表示空（类似NULL） } *NodePtr; // NodePtr是指向节点的指针类型 /** * 静态链表结构 * 管理整个静态链表的内存和状态 */ typedef struct StaticLinkedList { NodePtr nodes; // 指向节点数组的指针（动态分配） int* used; // 标记数组，1表示该位置已被使用，0表示空闲 } *ListPtr; // ListPtr是指向链表管理器的指针类型 /** * 初始化静态链表 * @return 返回初始化后的链表管理器指针 */ ListPtr initLinkedList() { // 1. 为链表管理器分配内存 ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticLinkedList)); // 2. 为节点数组分配内存（DEFAULT_SIZE个节点） tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE); // 3. 为used标记数组分配内存 tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE); // 4. 初始化头结点（下标0） tempPtr->nodes[0].data = '\0'; // 头结点不存储有效数据 tempPtr->nodes[0].next = -1; // -1表示空链表 // 5. 初始化used数组 tempPtr->used[0] = 1; // 头结点被占用 for (int i = 1; i < DEFAULT_SIZE; i++) { tempPtr->used[i] = 0; // 其他位置空闲 } return tempPtr; } /** * 释放链表占用的所有内存 * @param paraListPtr 链表管理器指针 */ void freeLinkedList(ListPtr paraListPtr) { if (paraListPtr == NULL) return; // 空指针检查 free(paraListPtr->nodes); // 释放节点数组 free(paraListPtr->used); // 释放标记数组 free(paraListPtr); // 释放管理器本身 } /** * 打印链表中的所有字符 * @param paraListPtr 链表管理器指针 */ void printList(ListPtr paraListPtr) { int p = paraListPtr->nodes[0].next; // 从头结点的下一个节点开始 while (p != -1) { // 遍历直到链表末尾（-1） printf("%c", paraListPtr->nodes[p].data); // 打印当前节点的数据 p = paraListPtr->nodes[p].next; // 移动到下一个节点 } printf("\n"); } /** * 在指定位置插入字符 * @param paraListPtr 链表管理器指针 * @param paraChar 要插入的字符 * @param paraPosition 插入位置（0表示插入到链表头部） */ void insertElement(ListPtr paraListPtr, char paraChar, int paraPosition) { int p, q, i; // 步骤1：找到插入位置的前一个节点（前驱） p = 0; // 从头结点开始 for (i = 0; i < paraPosition; i++) { p = paraListPtr->nodes[p].next; // 向后移动 if (p == -1) { // 如果到达链表末尾，说明位置越界 printf("The position %d is beyond the scope of the list.\n", paraPosition); return; } } // 步骤2：在节点数组中找一个空闲位置（模拟内存分配） for (i = 1; i < DEFAULT_SIZE; i++) { // 从下标1开始，跳过0号头结点 if (paraListPtr->used[i] == 0) { // 找到空闲位置 printf("Space at %d allocated.\n", i); paraListPtr->used[i] = 1; // 标记为已使用 q = i; // 记录新节点的下标 break; } } // 检查是否找到空闲位置 if (i == DEFAULT_SIZE) { printf("No space.\n"); // 静态链表已满 return; } // 步骤3：将数据存入新节点 paraListPtr->nodes[q].data = paraChar; // 步骤4：修改指针，完成插入操作 // 新节点的next指向原前驱的下一个节点 paraListPtr->nodes[q].next = paraListPtr->nodes[p].next; // 前驱节点的next指向新节点 paraListPtr->nodes[p].next = q; } /** * 删除链表中第一个匹配的字符 * @param paraListPtr 链表管理器指针 * @param paraChar 要删除的字符 */ void deleteElement(ListPtr paraListPtr, char paraChar) { int p, q; p = 0; // 从头结点开始 // 步骤1：查找待删除节点的前驱 // 条件1：未到达链表末尾 // 条件2：下一个节点的数据不等于要删除的字符 while ((paraListPtr->nodes[p].next != -1) && (paraListPtr->nodes[paraListPtr->nodes[p].next].data != paraChar)) { p = paraListPtr->nodes[p].next; // 继续向后移动 } // 步骤2：判断是否找到 if (paraListPtr->nodes[p].next == -1) { printf("Cannot delete %c\n", paraChar); // 未找到要删除的字符 return; } // 步骤3：执行删除操作 q = paraListPtr->nodes[p].next; // q为要删除的节点下标 // 前驱节点的next指向被删除节点的下一个节点（跳过被删除节点） paraListPtr->nodes[p].next = paraListPtr->nodes[q].next; // 标记该位置为空闲（模拟内存释放） paraListPtr->used[q] = 0; } /** * 输出内存状态信息（用于调试） * @param paraListPtr 链表管理器指针 */ void outputMemory(ListPtr paraListPtr) { int i; printf("Now output the memory.\n"); // 使用%p格式符输出内存地址，并强制转换为void*类型 printf("The address of the list: %p\n", (void*)paraListPtr); // 链表管理器地址 printf("The address of nodes: %p\n", (void*)paraListPtr->nodes); // 节点数组地址 printf("The address of used: %p\n", (void*)paraListPtr->used); // used数组地址 printf("The contents the memory: [data, next, used]\n"); // 输出每个节点的详细信息 for (i = 0; i < DEFAULT_SIZE; i++) { printf("[%c, %d, %d]\n", paraListPtr->nodes[i].data, // 节点的数据 paraListPtr->nodes[i].next, // 下一个节点的下标 paraListPtr->used[i]); // 是否被使用 } } /** * 单元测试：演示插入、删除操作 */ void appendInsertDeleteTest() { // 1. 初始化链表 ListPtr tempList = initLinkedList(); printList(tempList); // 打印空链表 outputMemory(tempList); // 输出初始内存状态 // 2. 依次插入字符构成"Hello" insertElement(tempList, 'H', 0); insertElement(tempList, 'e', 1); insertElement(tempList, 'l', 2); insertElement(tempList, 'l', 3); insertElement(tempList, 'o', 4); printList(tempList); // 输出: Hello // 3. 测试删除操作 printf("Deleting 'e'.\n"); deleteElement(tempList, 'e'); // 删除'e' printf("Deleting 'a'.\n"); deleteElement(tempList, 'a'); // 尝试删除不存在的'a' printf("Deleting 'o'.\n"); deleteElement(tempList, 'o'); // 删除'o' printList(tempList); // 输出删除后的结果 // 4. 在位置2插入'x' insertElement(tempList, 'x', 2); printList(tempList); // 输出最终结果 // 5. 输出最终内存状态 outputMemory(tempList); // 6. 释放内存 freeLinkedList(tempList); } /** * 主函数：程序入口 */ int main() { appendInsertDeleteTest(); // 运行单元测试 return 0; }
