Untitled

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

// MurmurOAAT32 hash function
unsigned int MurmurOAAT32(char *key) {
    unsigned int h = 3323198485u;
    for (; *key; ++key) {
        h ^= *key;
        h *= 0x5bd1e995;
        h ^= h >> 15;
    }
    return h;
}

// Function to convert unsigned int to string
void unsigned_int_to_string(unsigned int num, char *str) {
    sprintf(str, "%u", num);
}

// Function to merge and hash two values in the binary tree
unsigned int merge_and_hash(unsigned int a, unsigned int b) {
    unsigned int sum = a + b;
    char buffer[11]; // enough to hold a 32-bit unsigned int
    unsigned_int_to_string(sum, buffer);
    return MurmurOAAT32(buffer);
}

// Definition of linked list node
typedef struct ListNode {
    unsigned int data;
    struct ListNode *next;
} ListNode;

// Function to create a new list node
ListNode* create_list_node(unsigned int data) {
    ListNode *new_node = (ListNode *)malloc(sizeof(ListNode));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

// Function to append a node to the end of the linked list
void append_list_node(ListNode **head, unsigned int data) {
    ListNode *new_node = create_list_node(data);
    if (*head == NULL) {
        *head = new_node;
    } else {
        ListNode *current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = new_node;
    }
}

// Recursive function to collect hash values from root to leaves into a linked list
void collect_hashes(unsigned int *hashes, int n, ListNode **head) {
    if (n == 1) {
        append_list_node(head, hashes[0]);
        return;
    }

    int new_n = (n + 1) / 2;
    unsigned int *new_hashes = (unsigned int *)malloc(new_n * sizeof(unsigned int));

    for (int i = 0; i < new_n; i++) {
        if (2 * i + 1 < n) {
            new_hashes[i] = merge_and_hash(hashes[2 * i], hashes[2 * i + 1]);
        } else {
            char buffer[11];
            unsigned_int_to_string(hashes[2 * i] * 2, buffer);
            new_hashes[i] = MurmurOAAT32(buffer);
        }
    }

    collect_hashes(new_hashes, new_n, head);
    for (int i = 0; i < n; i++) {
        append_list_node(head, hashes[i]);
    }

    free(new_hashes);
}

// Function to print the linked list
void print_linked_list(ListNode *head) {
    ListNode *current = head;
    while (current != NULL) {
        printf("%u ", current->data);
        current = current->next;
    }
    printf("\n");
}

// Definition of tree node
typedef struct TreeNode {
    unsigned int value;
    struct TreeNode** children;
    int childCount;
} TreeNode;

// Function to create a new tree node
TreeNode* create_tree_node(unsigned int value, int maxChildren) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (!newNode) {
        printf("Memory allocation failed for new node.\n");
        exit(1);
    }
    newNode->value = value;
    newNode->childCount = 0;
    newNode->children = (TreeNode**)malloc(sizeof(TreeNode*) * maxChildren);
    if (!newNode->children) {
        printf("Memory allocation failed for children array.\n");
        exit(1);
    }
    return newNode;
}

// Function to insert a child node
void insert_child(TreeNode* parent, TreeNode* child) {
    parent->children[parent->childCount++] = child;
}

// Function to print the tree (preorder traversal)
void print_tree(TreeNode* root, int level) {
    if (root == NULL) return;
    for (int i = 0; i < level; i++) printf("  ");
    printf("%u\n", root->value);
    for (int i = 0; i < root->childCount; i++) {
        print_tree(root->children[i], level + 1);
    }
}

// Function to collect tree values into a linked list
void collect_tree_values(TreeNode* root, ListNode **head) {
    if (root == NULL) return;
    append_list_node(head, root->value);
    for (int i = 0; i < root->childCount; i++) {
        collect_tree_values(root->children[i], head);
    }
}

// Function to free the tree nodes
void free_tree(TreeNode* node) {
    if (node == NULL) return;
    for (int i = 0; i < node->childCount; i++) {
        free_tree(node->children[i]);
    }
    free(node->children);
    free(node);
}

// Function to compare two linked lists and print differences
void compare_linked_lists(ListNode *list1, ListNode *list2) {
    ListNode *current1 = list1;
    ListNode *current2 = list2;

    while (current1 != NULL && current2 != NULL) {
        if (current1->data == current2->data) {
            printf("%u == %u\n", current1->data, current2->data);
        } else {
            printf("%u != %u\n", current1->data, current2->data);
        }
        current1 = current1->next;
        current2 = current2->next;
    }

    // Print remaining nodes if any list is longer than the other
    while (current1 != NULL) {
        printf("%u != NULL\n", current1->data);
        current1 = current1->next;
    }
    while (current2 != NULL) {
        printf("NULL != %u\n", current2->data);
        current2 = current2->next;
    }
}

int main() {
    // Part A: Hash collection into linked list
    int n;
    scanf("%d", &n);

    char **strings = (char **)malloc(n * sizeof(char *));
    unsigned int *hashes = (unsigned int *)malloc(n * sizeof(unsigned int));

    for (int i = 0; i < n; i++) {
        strings[i] = (char *)malloc(101 * sizeof(char)); // 100 chars + null terminator
        scanf("%s", strings[i]);
        hashes[i] = MurmurOAAT32(strings[i]);
    }

    ListNode *hash_list_A = NULL;
    collect_hashes(hashes, n, &hash_list_A);

    for (int i = 0; i < n; i++) {
        free(strings[i]);
    }
    free(strings);
    free(hashes);

    // Part B: Tree construction
    int layers;
    scanf("%d", &layers);

    TreeNode* root = NULL;
    TreeNode* currentLevelNodes[1000];
    int currentLevelSize = 0;
    
    for (int i = 0; i < layers; i++) {
        int nodesCount;
        scanf("%d", &nodesCount);
        
        TreeNode* newLevelNodes[1000];
        int newLevelSize = 0;
        
        for (int j = 0; j < nodesCount; j++) {
            unsigned int value;
            scanf("%u", &value);
            TreeNode* newNode = create_tree_node(value, 1000);
            
            if (i == 0 && j == 0) {
                root = newNode;
            } else {
                int parentIndex = j / (nodesCount / currentLevelSize);
                if (parentIndex >= currentLevelSize) {
                    parentIndex = currentLevelSize - 1; // 防止越界
                }
                insert_child(currentLevelNodes[parentIndex], newNode);
            }
            
            newLevelNodes[newLevelSize++] = newNode;
        }
        
        for (int k = 0; k < newLevelSize; k++) {
            currentLevelNodes[k] = newLevelNodes[k];
        }
        currentLevelSize = newLevelSize;
    }

    // Collect tree node values into a linked list
    ListNode *hash_list_B = NULL;
    collect_tree_values(root, &hash_list_B);

    // Compare both linked lists
    compare_linked_lists(hash_list_A, hash_list_B);

    // Free the linked list A
    ListNode *current = hash_list_A;
    while (current != NULL) {
        ListNode *next = current->next;
        free(current);
        current = next;
    }

    // Free the tree nodes and linked list B
    free_tree(root);

    current = hash_list_B;
    while (current != NULL) {
        ListNode *next = current->next;
        free(current);
        current = next;
    }

    return 0;
}