使用C++进行编程，假设x和y是两个由单链表组成的字符串（其中每个结点只存储一个字符），请编写一个算法，找出x中第一个不在y中出现的字符。 注：在朴素的算法之上，如果使用某些技巧提升算法效率的可以额外得分。 提交的实验报告中请说明所使用的技巧，以及为什么可以有提升。

算法思路：

我们可以分别遍历两个单链表，使用两个哈希表分别记录字符在x和y中出现的次数，然后在哈希表中查找x中第一个不在y中出现的字符。

特别地，对于y中出现的字符，我们可以将其在x的哈希表中次数减一，这样可以避免在两个哈希表中都记录y中的字符。

算法流程：

1. 初始化x和y的单链表，并创建两个哈希表，分别用于记录x和y中字符的出现次数。

2. 遍历y的单链表，将字符在y的哈希表中出现次数加一。

3. 遍历x的单链表，若字符在y的哈希表中出现次数为零，则返回该字符，否则在x的哈希表中将该字符出现次数减一。

4. 若遍历了x的所有字符后仍未找到满足条件的字符，则返回无。

时间复杂度：

该算法需要遍历两个单链表，时间复杂度为O(n)，其中n为两个单链表长度之和，并且在哈希表中查找字符的时间复杂度为O(1)。因此，总时间复杂度为O(n)。

代码实现：

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

#define MAXN 100005

/* 节点结构 */
typedef struct Node {
    char data;          // 数据域
    struct Node *next;  // 指针域
} Node;

/* 单链表结构 */
typedef struct List {
    Node *head;         // 头节点指针
    Node *tail;         // 尾节点指针
} List;

/* 哈希表结构 */
typedef struct HashTable {
    int size;           // 哈希表大小
    int *table;         // 哈希表
} HashTable;

/* 创建空的单链表 */
List* createList() {
    List *list = (List*)malloc(sizeof(List));
    list->head = NULL;
    list->tail = NULL;
    return list;
}

/* 在单链表末尾添加结点 */
void addNode(List *list, char data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    if (list->head == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
}

/* 创建哈希表 */
HashTable* createHashTable(int size) {
    HashTable *ht = (HashTable*)malloc(sizeof(HashTable));
    ht->size = size;
    ht->table = (int*)calloc(size, sizeof(int));
    return ht;
}

/* 向哈希表中添加键值对 */
void put(HashTable *ht, char key, int value) {
    int hash = (int)key % ht->size;
    while (ht->table[hash] != 0 && ht->table[hash] != key) {
        hash = (hash + 1) % ht->size;
    }
    ht->table[hash] = value;
}

/* 在哈希表中查找键对应的值 */
int get(HashTable *ht, char key) {
    int hash = (int)key % ht->size;
    while (ht->table[hash] != 0) {
        if (ht->table[hash] == key) {
            return 1;
        }
        hash = (hash + 1) % ht->size;
    }
    return 0;
}

/* 释放单链表的空间 */
void freeList(List *list) {
    Node *p = list->head;
    while (p != NULL) {
        Node *q = p->next;
        free(p);
        p = q;
    }
    free(list);
}

/* 释放哈希表的空间 */
void freeHashTable(HashTable *ht) {
    free(ht->table);
    free(ht);
}

/* 找出x中第一个不在y中出现的字符 */
char findChar(List *x, List *y) {
    HashTable *hx = createHashTable(MAXN);
    HashTable *hy = createHashTable(MAXN);

    // 将y中字符加入哈希表hy
    Node *p = y->head;
    while (p != NULL) {
        char c = p->data;
        int cnt = hy->table[(int)c % hy->size];
        hy->table[(int)c % hy->size] = cnt + 1;
        p = p->next;
    }

    // 查找x中第一个不在y中出现的字符
    p = x->head;
    char ans;
    while (p != NULL) {
        char c = p->data;
        if (!get(hy, c)) {
            ans = c;
            break;
        }
        int cnt = hx->table[(int)c % hx->size];
        hx->table[(int)c % hx->size] = cnt + 1;
        p = p->next;
    }

    freeHashTable(hx);
    freeHashTable(hy);
    return ans;
}

int main() {
    // 创建x的单链表
    List *x = createList();
    char c;
    printf("Please input string x:\n");
    while ((c = getchar()) != '\n') {
        addNode(x, c);
    }

    // 创建y的单链表
    List *y = createList();
    printf("Please input string y:\n");
    while ((c = getchar()) != '\n') {
        addNode(y, c);
    }

    // 找出x中第一个不在y中出现的字符
    char ans = findChar(x, y);
    if (ans == '\0') {
        printf("No such character.\n");
    } else {
        printf("The first character in x not in y is %c.\n", ans);
    }

    // 释放空间
    freeList(x);
    freeList(y);

    return 0;
}

使用技巧：

1. 使用哈希表记录字符出现次数，可以使查找复杂度从O(n)优化到O(1)，提高算法效率。

2. 哈希表中可以直接存储字符的ASCII码，不必先将字符映射到0~127的整数再存储，这样可以减少一次操作，提高算法效率。