面试题：C语言指针的指针在复杂数据结构中的应用

Question

设计一个简单的链表结构，链表的每个节点都包含一个指针数组，指针数组中的每个指针又指向另一个链表（形成一种类似二维链表的结构）。使用指针的指针来实现链表节点的插入、删除操作，并且编写函数来遍历整个复杂链表结构并打印所有节点的数据。假设节点数据为整数类型。

Answer 1

#include <stdio.h>
#include <stdlib.h>

// 定义内部链表节点
typedef struct InnerNode {
    int data;
    struct InnerNode* next;
} InnerNode;

// 定义外部链表节点
typedef struct OuterNode {
    InnerNode** innerList;
    int innerListSize;
    struct OuterNode* next;
} OuterNode;

// 创建一个新的内部链表节点
InnerNode* createInnerNode(int data) {
    InnerNode* newNode = (InnerNode*)malloc(sizeof(InnerNode));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建一个新的外部链表节点
OuterNode* createOuterNode(int innerListSize) {
    OuterNode* newNode = (OuterNode*)malloc(sizeof(OuterNode));
    newNode->innerList = (InnerNode**)malloc(innerListSize * sizeof(InnerNode*));
    newNode->innerListSize = innerListSize;
    for (int i = 0; i < innerListSize; i++) {
        newNode->innerList[i] = NULL;
    }
    newNode->next = NULL;
    return newNode;
}

// 在外部链表中插入一个新节点
void insertOuterNode(OuterNode** head, int innerListSize) {
    OuterNode* newNode = createOuterNode(innerListSize);
    if (*head == NULL) {
        *head = newNode;
    } else {
        OuterNode* current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 在外部链表的某个节点的内部链表中插入一个新节点
void insertInnerNode(OuterNode* outerNode, int index, int data) {
    if (index < 0 || index >= outerNode->innerListSize) {
        printf("Invalid index\n");
        return;
    }
    InnerNode* newNode = createInnerNode(data);
    if (outerNode->innerList[index] == NULL) {
        outerNode->innerList[index] = newNode;
    } else {
        InnerNode* current = outerNode->innerList[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

// 删除外部链表的某个节点
void deleteOuterNode(OuterNode** head, OuterNode* nodeToDelete) {
    if (*head == nodeToDelete) {
        *head = nodeToDelete->next;
        free(nodeToDelete->innerList);
        free(nodeToDelete);
        return;
    }
    OuterNode* current = *head;
    while (current->next != NULL && current->next != nodeToDelete) {
        current = current->next;
    }
    if (current->next != NULL) {
        current->next = nodeToDelete->next;
        free(nodeToDelete->innerList);
        free(nodeToDelete);
    }
}

// 删除外部链表某个节点的内部链表中的某个节点
void deleteInnerNode(OuterNode* outerNode, int index, InnerNode* nodeToDelete) {
    if (index < 0 || index >= outerNode->innerListSize) {
        printf("Invalid index\n");
        return;
    }
    if (outerNode->innerList[index] == nodeToDelete) {
        outerNode->innerList[index] = nodeToDelete->next;
        free(nodeToDelete);
        return;
    }
    InnerNode* current = outerNode->innerList[index];
    while (current->next != NULL && current->next != nodeToDelete) {
        current = current->next;
    }
    if (current->next != NULL) {
        current->next = nodeToDelete->next;
        free(nodeToDelete);
    }
}

// 遍历并打印整个复杂链表结构
void printComplexList(OuterNode* head) {
    OuterNode* currentOuter = head;
    while (currentOuter != NULL) {
        for (int i = 0; i < currentOuter->innerListSize; i++) {
            InnerNode* currentInner = currentOuter->innerList[i];
            while (currentInner != NULL) {
                printf("Outer Node: Inner List %d, Data: %d\n", i, currentInner->data);
                currentInner = currentInner->next;
            }
        }
        currentOuter = currentOuter->next;
    }
}

// 释放整个复杂链表结构的内存
void freeComplexList(OuterNode* head) {
    OuterNode* currentOuter = head;
    OuterNode* nextOuter;
    while (currentOuter != NULL) {
        for (int i = 0; i < currentOuter->innerListSize; i++) {
            InnerNode* currentInner = currentOuter->innerList[i];
            InnerNode* nextInner;
            while (currentInner != NULL) {
                nextInner = currentInner->next;
                free(currentInner);
                currentInner = nextInner;
            }
        }
        free(currentOuter->innerList);
        nextOuter = currentOuter->next;
        free(currentOuter);
        currentOuter = nextOuter;
    }
}

int main() {
    OuterNode* head = NULL;
    insertOuterNode(&head, 2);
    insertInnerNode(head, 0, 1);
    insertInnerNode(head, 1, 2);

    insertOuterNode(&head, 1);
    insertInnerNode(head->next, 0, 3);

    printComplexList(head);

    freeComplexList(head);
    return 0;
}

上述代码实现了一个复杂链表结构，包含以下功能：

1. 链表节点定义：定义了内部链表节点 InnerNode 和外部链表节点 OuterNode，外部链表节点包含一个指针数组，每个指针指向一个内部链表。
2. 节点创建函数：createInnerNode 和 createOuterNode 分别用于创建内部和外部链表节点。
3. 插入函数：insertOuterNode 用于在外部链表中插入新节点，insertInnerNode 用于在外部链表某个节点的内部链表中插入新节点。
4. 删除函数：deleteOuterNode 用于删除外部链表的某个节点，deleteInnerNode 用于删除外部链表某个节点的内部链表中的某个节点。
5. 遍历函数：printComplexList 用于遍历并打印整个复杂链表结构。
6. 内存释放函数：freeComplexList 用于释放整个复杂链表结构占用的内存。

在 main 函数中，展示了如何使用这些函数来操作复杂链表。