#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函数