开始用分离链接法实现的散列表,结果超时,于是改成了开放定址法实现的散列表,还是超时
于是把输入输出改成了c的写法,结果都过了。。。
//分离链接法散列 3485ms #include <iostream> #include <cstdlib> using namespace std; #define TAB_SIZ 14997 #define SIDE 6 struct ListNode { int a[SIDE]; struct ListNode *next; }; struct ListNode *table[TAB_SIZ]; bool isFind( int key, int *b ) { struct ListNode *p, *l; int i, j, k, id; l = table[key]; p = l->next; while( p != NULL ) { for( i = 0; i < SIDE; i++ ) { for( j = i, k = 0; k < SIDE; j++, k++ ) { if( j < SIDE ) id = j; else id = j-SIDE; if( p->a[k] != b[id] ) break; } if( k == SIDE ) return true; for( j = i, k = 0; k < SIDE; j--, k++ ) { if( j < 0 ) id = j+SIDE; else id = j; if( p->a[k] != b[id] ) break; } if( k == SIDE ) return true; } p = p->next; } return false; } void Insert( int key, int *b ) { struct ListNode *l, *NewCell; int i; NewCell = (struct ListNode *)malloc( sizeof(struct ListNode) ); l = table[key]; NewCell->next = l->next; l->next = NewCell; for( i = 0; i < SIDE; i++ ) NewCell->a[i] = b[i]; } int main() { int n, b[SIDE]; int i, j, HashVal,id; bool flag; for( i = 0; i < TAB_SIZ; i++ ) { table[i] = (struct ListNode *)malloc( sizeof(struct ListNode) ); table[i]->next = NULL; } flag = false; scanf("%d", &n); for( i = 0; i < n && !flag; i++ ){ for( j = HashVal = 0; j < SIDE; j++ ){ scanf("%d", &b[j]); HashVal += b[j]; } id = HashVal % TAB_SIZ; if( isFind( id, b ) ) flag = true; else Insert( id, b ); } if( flag ) printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); return 0; }
//开放定址法 平方探测 2188ms #include <iostream> #include <cstdlib> using namespace std; #define TAB_SIZ 200003 #define SIDE 6 struct Cell { int a[SIDE]; bool empty; } table[TAB_SIZ]; int isFind( int pos, int *b ) { int i, j, k; int m, id, curr_pos; curr_pos = pos; m = 0; while( !table[curr_pos].empty ) { for( i = 0; i < SIDE; i++ ) { for( j = i, k = 0; k < SIDE; j++, k++ ) { if( j < SIDE ) id = j; else id = j-SIDE; if( table[curr_pos].a[k] != b[id] ) break; } if( k == SIDE ) return -1; for( j = i, k = 0; k < SIDE; j--, k++ ) { if( j < 0 ) id = j+SIDE; else id = j; if( table[curr_pos].a[k] != b[id] ) break; } if( k == SIDE ) return -1; } curr_pos += 2*(++m)-1 ; if(curr_pos >= TAB_SIZ) curr_pos -= TAB_SIZ; } return curr_pos; } void Insert( int id, int *b ) { int i; for( i = 0 ; i < SIDE; i++ ) table[id].a[i] = b[i]; table[id].empty = false; } int main() { int n, b[SIDE]; int i, j, HashVal,id; bool flag; for( i = 0; i < TAB_SIZ; i++ ) table[i].empty = true; flag = false; scanf("%d", &n); for( i = 0; i < n && !flag; i++ ){ for( j = HashVal = 0; j < SIDE; j++ ){ scanf("%d", &b[j]); HashVal += b[j]; } id = HashVal % TAB_SIZ; int res = isFind( id, b ); if( res < 0 ) flag = true; else Insert( res, b ); } if( flag ) printf("Twin snowflakes found.\n"); else printf("No two snowflakes are alike.\n"); return 0; }