2.4 静态链表

#include stdio.h#include malloc.h// 默认链表容量#define DEFAULT_SIZE 5typedef 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));// 为节点数组和状态数组分配内存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;// 初始状态只有头节点被占用tempPtr-used[0] 1;for (int i 1; i DEFAULT_SIZE; i ){tempPtr-used[i] 0;}return tempPtr;}/*** 打印链表中的所有数据* 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;}printf(\r\n);}/*** 在指定位置插入元素* param paraListPtr 链表指针* param paraChar 待插入的字符* param paraPosition 插入位置*/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(插入位置 %d 超出链表范围\r\n, paraPosition);return;}}// 步骤2分配空闲节点模拟动态内存的mallocfor (i 1; i DEFAULT_SIZE; i ){if (paraListPtr-used[i] 0){printf(已分配下标为 %d 的空间\r\n, i);paraListPtr-used[i] 1;q i;break;}}if (i DEFAULT_SIZE){printf(链表空间已满无法插入\r\n);return;}// 为新节点赋值paraListPtr-nodes[q].data paraChar;// 步骤3调整游标连接新节点printf(正在连接节点\r\n);paraListPtr-nodes[q].next paraListPtr-nodes[p].next;paraListPtr-nodes[p].next q;}/*** 删除指定元素首次出现的节点* param paraListPtr 链表指针* param paraChar 待删除的字符*/void deleteElement(ListPtr paraListPtr, char paraChar){int p, q;// p指向待删除节点的前驱节点p 0;while ((paraListPtr-nodes[p].next ! -1) (paraListPtr-nodes[paraListPtr-nodes[p].next].data ! paraChar)){p paraListPtr-nodes[p].next;}// 未找到目标元素if (paraListPtr-nodes[p].next -1) {printf(无法删除字符 %c元素不存在\r\n, paraChar);return;}// 摘下待删除节点q paraListPtr-nodes[p].next;paraListPtr-nodes[p].next paraListPtr-nodes[paraListPtr-nodes[p].next].next;// 释放节点空间模拟动态内存的freeparaListPtr-used[q] 0;}/*** 输出链表的内存与节点状态信息* 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(内存内容格式[数据, 游标, 使用状态]\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]);}}/*** 单元测试测试插入、删除功能*/void appendInsertDeleteTest(){// 步骤1初始化空链表ListPtr tempList initLinkedList();printList(tempList);outputMemory(tempList);// 步骤2依次插入字符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);// 步骤3删除指定字符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);// 再次插入测试insertElement(tempList, x, 2);printList(tempList);// 最终内存状态outputMemory(tempList);}/*** 主函数程序入口*/int main(){appendInsertDeleteTest();return 0;}