已知由单链表表示的线性表中含有三类字符

\xe4\xb8\x89\xe7\xb1\xbb\xe5\xad\x97\xe7\xac\xa6\xe5\x8c\x85\xe5\x8c\x85\xe6\x8b\xac\xe5\x8c\x85\xef\xbc\x8c\xe5\x88\x86\xe5\x88\xab\xe4\xb8\xba\xe5\x8d\x95\xe5\xad\x97\xe7\xac\xa6\xe3\x80\x81\xe5\x8f\x8c\xe5\xad\x97\xe7\xac\xa6\xe5\x92\x8c\xe5\xb8\xb8\xe7\x94\xa8\xe7\x89\xb9\xe6\xae\x8a\xe7\xac\xa6\xe3\x80\x82

相关问题

已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空

间。

算法思路：

1. 定义三个循环链表，分别表示字母、数字和其他字符。

2. 遍历原链表，将每个结点根据其数据元素类型插入到对应的循环链表中。

3. 在原链表的头部插入一个新结点作为头结点，使原链表成为带头结点的单链表。

4. 返回三个循环链表的头结点。

算法实现：

typedef struct node {
    char data;
    struct node *next;
} Node;

Node *createCircularList() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = head;
    return head;
}

void insertNode(Node *head, char data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head->next;
    head->next = newNode;
}

Node *separateList(Node *list) {
    Node *letterList = createCircularList();
    Node *digitList = createCircularList();
    Node *otherList = createCircularList();
    Node *p = list->next;
    while (p != list) {
        if (isalpha(p->data)) {
            insertNode(letterList, p->data);
        } else if (isdigit(p->data)) {
            insertNode(digitList, p->data);
        } else {
            insertNode(otherList, p->data);
        }
        p = p->next;
    }
    list->data = 'H';
    list->next = letterList;
    letterList->data = 'A';
    letterList->next = digitList;
    digitList->data = '';
    digitList->next = otherList;
    otherList->data = '#';
    otherList->next = list;
    return letterList;
}

算法说明：

1. createCircularList() 函数用于创建一个空的循环链表，返回头结点指针。

2. insertNode() 函数用于在循环链表的头部插入一个新结点，数据元素为 data。

3. separateList() 函数用于将原链表中的结点按照数据元素类型分别插入到三个循环链表中，并将原链表转化为带头结点的单链表。

4. 在返回循环链表头结点之前，需要将原链表的头结点指向循环链表的第一个结点，以便于后续操作。

5. 时间复杂度为 O(n)，空间复杂度为 O(1)。