Untitled
This snippet defines the MurmurOAAT32 hash function, functions to merge and hash values, and to create a linked list node. It includes a method for converting an unsigned integer to a string.unknown
c_cpp
10 months ago
7.5 kB
3
Indexable
#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; }
Editor is loading...
Leave a Comment