2.4 静态链表

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

// 为节点数组和状态数组分配内存
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：分配空闲节点（模拟动态内存的malloc）
for (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;

// 释放节点空间（模拟动态内存的free）
paraListPtr->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;
}