C语言静态链表和动态链表

C语言中实现链表有两种方式，静态链表和动态链表。下面我们对这两种链表进行详细介绍。

静态链表

静态链表是指使用数组来模拟链表。因为在定义时，数组大小必须确定，所以静态链表的长度是固定的。静态链表需要手动维护指针，即每个元素除了存储自己的值外，还需要记录下一个元素的下标。静态链表使用起来比较繁琐，但是相对于动态链表，它更加节省空间，不需要频繁地进行内存动态分配。下面是一个静态链表的示例代码：

#define MAXSIZE 100
typedef struct {
    int data;
    int next;   // 存储下一个元素的下标
} Node;

Node staticList[MAXSIZE];

// 初始化静态链表，返回头结点的下标
int initStaticList() {
    for (int i = 0; i < MAXSIZE - 1; i++) {
        staticList[i].next = i + 1;
    }
    staticList[MAXSIZE - 1].next = -1;  // 表示链表的结尾
    return 0;   // 返回头结点
}

// 在静态链表的指定位置插入一个元素
void insertStaticList(int pos, int value) {
    int cursor = MAXSIZE - 1;   // 游标从头结点开始
    for (int i = 0; i < pos - 1; i++) {
        cursor = staticList[cursor].next;   // 移动游标
    }
    int new_node = staticList[cursor].next;   // 获取下一个元素的下标
    staticList[new_node].data = value;
    staticList[cursor].next = new_node;   // 修改当前元素的“下一个元素”
}

// 遍历静态链表
void traverseStaticList() {
    int cursor = staticList[0].next;   // 从头结点的下一个元素开始遍历
    while (cursor != -1) {
        printf("%d ", staticList[cursor].data);
        cursor = staticList[cursor].next;   // 移动游标
    }
}

动态链表

动态链表是指使用指针来实现链表，链表的长度不固定，可以根据需要动态分配内存。相对于静态链表，动态链表的使用起来更加方便灵活，但是需要注意内存泄漏问题。下面是一个动态链表的示例代码：

typedef struct Node {
    int data;
    struct Node *next;   // 指向下一个元素的指针
} Node, *LinkList;

// 初始化动态链表，返回头结点的指针
LinkList initLinkList() {
    Node *head = (Node*)malloc(sizeof(Node));   // 创建头结点
    head->next = NULL;
    return head;   // 返回头结点指针
}

// 在动态链表的指定位置插入一个元素
void insertLinkList(LinkList L, int pos, int value) {
    Node *cursor = L;
    for (int i = 0; i < pos - 1; i++) {
        if (cursor->next == NULL) {   // 判断是否到达链表的结尾
            printf("Error: Index out of range\n");
            return;
        }
        cursor = cursor->next;   // 移动游标
    }
    Node *new_node = (Node*)malloc(sizeof(Node));   // 创建新结点
    new_node->data = value;
    new_node->next = cursor->next;   // 修改新结点的“下一个元素”
    cursor->next = new_node;   // 修改当前结点的“下一个元素”
}

// 遍历动态链表
void traverseLinkList(LinkList L) {
    Node *cursor = L->next;   // 从头结点的下一个元素开始遍历
    while (cursor != NULL) {
        printf("%d ", cursor->data);
        cursor = cursor->next;   // 移动游标
    }
}

以上就是静态链表和动态链表的完整攻略，希望能对你有所帮助。

阅读剩余 47%