【静态链表】

#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; }