抄写静态链表基本操作

#include <stdio.h> #include <malloc.h> #define DEFAULT_SIZE 5 // 静态链表默认容量 // 静态链表结点结构体 typedef struct StaticLinkedNode{ char data; // 结点存储的字符数据 int next; // 下一个结点的下标（模拟指针） } *NodePtr; // 静态链表结构体 typedef struct StaticLinkedList{ NodePtr nodes; // 结点数组的基址 int* used; // 标记数组，记录结点是否被使用 } *ListPtr; /** * 初始化带头结点的静态链表 * @return 指向链表头部的指针 */ ListPtr initLinkedList(){ // 分配链表结构体内存 ListPtr tempPtr = (ListPtr)malloc(sizeof(struct StaticLinkedList)); // 分配结点数组空间（DEFAULT_SIZE个结点） tempPtr->nodes = (NodePtr)malloc(sizeof(struct StaticLinkedNode) * DEFAULT_SIZE); // 分配使用标记数组空间 tempPtr->used = (int*)malloc(sizeof(int) * DEFAULT_SIZE); // 第0个结点作为头结点，数据域为空 tempPtr->nodes[0].data = '\0'; tempPtr->nodes[0].next = -1; // -1表示链表结束 // 标记头结点已被使用 tempPtr->used[0] = 1; // 其余结点初始标记为未使用 for (int i = 1; i < DEFAULT_SIZE; i ++){ tempPtr->used[i] = 0; }// 结束for循环 return tempPtr; }// 结束initLinkedList函数 /** * 打印链表中的所有字符数据 * @param paraListPtr 链表指针 */ void printList(ListPtr paraListPtr){ int p = paraListPtr->nodes[0].next; // 从头结点的下一个开始遍历 while (p != -1) { printf("%c", paraListPtr->nodes[p].data); p = paraListPtr->nodes[p].next; }// 结束while循环 printf("\r\n"); }// 结束printList函数 /** * 在指定位置插入字符元素 * @param paraListPtr 链表指针 * @param paraChar 待插入的字符 * @param paraPosition 插入位置（0表示第一个位置） */ void insertElement(ListPtr paraListPtr, char paraChar, int paraPosition){ int p, q, i; // 第一步：移动到待插入位置的前一个结点 p = 0; for (i = 0; i < paraPosition; i ++) { p = paraListPtr->nodes[p].next; if (p == -1) { printf("待插入的位置 %d 超出了链表范围。\r\n", paraPosition); return; }// 结束if判断 } // 结束for循环 // 第二步：从空闲结点中分配一个新结点 for (i = 1; i < DEFAULT_SIZE; i ++){ if (paraListPtr->used[i] == 0){ // 找到空闲结点，相当于malloc分配内存 printf("已分配空间，下标为 %d。\r\n", i); paraListPtr->used[i] = 1; // 标记为已使用 q = i; break; }// 结束if判断 }// 结束for循环 if (i == DEFAULT_SIZE){ printf("静态链表已满，无可用空间。\r\n"); return; }// 结束if判断 // 设置新结点的数据 paraListPtr->nodes[q].data = paraChar; // 第三步：修改指针完成链接 printf("正在进行链接操作。\r\n"); paraListPtr->nodes[q].next = paraListPtr->nodes[p].next; paraListPtr->nodes[p].next = q; }// 结束insertElement函数 /** * 删除链表中第一个匹配到的字符元素 * @param paraListPtr 链表指针 * @param paraChar 待删除的字符 */ void deleteElement(ListPtr paraListPtr, char paraChar){ int p, q; p = 0; // 寻找待删除结点的前驱结点 while ((paraListPtr->nodes[p].next != -1) && (paraListPtr->nodes[paraListPtr->nodes[p].next].data != paraChar)){ p = paraListPtr->nodes[p].next; }// 结束while循环 // 未找到待删除的字符 if (paraListPtr->nodes[p].next == -1) { printf("无法删除字符 %c，链表中不存在该元素。\r\n", paraChar); return; }// 结束if判断 // 执行删除操作 q = paraListPtr->nodes[p].next; // q为待删除结点的下标 paraListPtr->nodes[p].next = paraListPtr->nodes[paraListPtr->nodes[p].next].next; // 释放结点（相当于free(q)），标记为未使用 paraListPtr->used[q] = 0; }// 结束deleteElement函数 /** * 输出静态链表的内存使用情况 * @param paraListPtr 链表指针 */ void outputMemory(ListPtr paraListPtr) { int i; printf("当前输出内存状态：\r\n"); printf("链表结构体地址：%ld\r\n", paraListPtr); printf("结点数组地址：%ld\r\n", paraListPtr->nodes); printf("标记数组地址：%ld\r\n", paraListPtr->used); printf("内存内容格式：[数据， next指针， 是否使用]\r\n"); for (i = 0; i < DEFAULT_SIZE; i ++) { printf("[%c, %d, %d]\r\n", paraListPtr->nodes[i].data, paraListPtr->nodes[i].next, paraListPtr->used[i]); }// 结束for循环 }// 结束outputMemory函数 /** * 单元测试：演示链表的插入和删除操作 */ void appendInsertDeleteTest(){ // 第一步：初始化一个空链表 ListPtr tempList = initLinkedList(); printList(tempList); // 打印空链表 outputMemory(tempList); // 查看初始内存状态 // 第二步：依次插入字符构成"Hello" insertElement(tempList, 'H', 0); outputMemory(tempList); insertElement(tempList, 'e', 1); outputMemory(tempList); insertElement(tempList, 'l', 2); outputMemory(tempList); insertElement(tempList, 'l', 3); outputMemory(tempList); insertElement(tempList, 'o', 4); printList(tempList); // 输出：Hello // 第三步：删除指定字符（仅删除第一个匹配项） printf("正在删除 'e'。\r\n"); deleteElement(tempList, 'e'); outputMemory(tempList); printf("正在删除 'a'（不存在）。\r\n"); deleteElement(tempList, 'a'); printf("正在删除 'o'。\r\n"); deleteElement(tempList, 'o'); printList(tempList); // 输出：Hll // 在位置2插入'x' insertElement(tempList, 'x', 2); printList(tempList); // 输出：Hlxl outputMemory(tempList); // 最终内存状态 }// 结束appendInsertDeleteTest函数 /** * 程序入口：主函数 */ int main(){ appendInsertDeleteTest(); // 运行单元测试 return 0; }// 结束main函数