a174. 上帝玩不玩骰子？(Hash)＠Morris' Blog

2011-07-09 06:07:16| 人氣1,054| 回應0 | 上一篇 | 下一篇

a174. 上帝玩不玩骰子？(Hash)

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

雜湊表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行查詢的資料結構。也就是說，它通過把關鍵碼值映射到表中一個位置來查詢記錄，以加快查找的速度。這個映射函數叫做雜湊函數，存放記錄的數組叫做雜湊表。

以上資料引用自維基百科

現在想請你模擬出一個簡單的 Hash Table

把所有數字經由 mod m 分成 m 個區間

每次給你一個數字 N

有三個操作依下列所示

操作 1: 將數字 N mod m 存入 Hash Table

操作 2: 將數字 N 從 Hash Table 中釋放（刪除）

操作 3: 將整個 Hash Table 輸出

輸入說明：

有多筆測資，每組第一行有兩個數字 k, m (1 ≦ k ≦ 1,0000, 1 ≦ m ≦ 200)

分別代表接下來有 k 筆操作, 模數 m

接下來的每一行

若第一個數字為 1，則接下來會一個數字 N，將這個數字插入 Hash Table

若第一個數字為 2，則接下來會一個數字 N，將這個數字從 Hash Table 刪除

若第一個數字為 3，則輸出整個 Hash Table

0 ≦ N < 2³¹-1

輸出說明：

若有兩個以上的數字在同一個區間內
輸出時請由小到大輸出

其餘輸出格式請參照範例輸出

範例輸入：

範例輸出：

===== s =====
[000]:NULL
[001]:NULL
[002]:17 -> NULL
[003]:8 -> NULL
[004]:NULL
===== e =====
===== s =====
[000]:NULL
[001]:NULL
[002]:17 -> NULL
[003]:8 -> NULL
[004]:NULL
===== e =====
===== s =====
[000]:NULL
[001]:NULL
[002]:17 -> NULL
[003]:8 -> 18 -> NULL
[004]:24 -> NULL
===== e =====
===== s =====
[000]:NULL
[001]:NULL
[002]:17 -> 37 -> NULL
[003]:8 -> 18 -> NULL
[004]:24 -> 64 -> 84 -> NULL
===== e =====
===== s =====
[000]:NULL
[001]:NULL
[002]:17 -> 37 -> NULL
[003]:8 -> NULL
[004]:24 -> 64 -> 84 -> NULL
===== e =====

提示：

背景知識： Hash Table

×　若在存入時，發現數字重複，則不予理會
×　若在刪除時，發現數字不存在，則不予理會
×　模擬即可，循序即可

題目由　example　編輯

出處：

Hash Table (管理：morris1028)

作法 : Hash table (linked list)
模擬 Hash table的處理步驟
有插入刪除打印這三種功能

/**********************************************************************************/
/* Problem: a174 "上帝玩不玩骰子？" from Hash Table                      */
/* Language: C                                                                   */
/* Result: AC (596ms, 476KB) on ZeroJudge                                        */
/* Author: morris1028 at 2011-07-07 22:59:43                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
int Mod;
struct list {
   int tag;
   struct list *next;
}*HASH[200], *curr, *prev, *temp;
void InsHash(int n) {
   int m = n%Mod;
   if(HASH[m] == NULL) {
       curr = (struct list *)malloc(sizeof(struct list));
       curr->tag = n, curr->next = NULL;
       HASH[m] = curr;return;
   }
   temp = HASH[m], prev = NULL;
   while(temp->tag <= n) {
       if(temp->tag == n) return;
       if(temp->next != NULL)
           prev = temp, temp = temp->next;
       else {
           curr = (struct list *)malloc(sizeof(struct list));
           curr->tag = n, curr->next = NULL;
           temp->next = curr; return;
       }
   }
   if(prev != NULL) {
       curr = (struct list *)malloc(sizeof(struct list));
       curr->tag = n;
       prev->next = curr, curr->next = temp;
   }
   else {
       curr = (struct list *)malloc(sizeof(struct list));
       curr->tag = n;
       HASH[m] = curr, curr->next = temp;
   }
   return;
}
void DelHash(int n) {
   int m = n%Mod;
   curr = HASH[m], prev = NULL;
   while(curr != NULL) {
       if(curr->tag < n) prev = curr, curr = curr->next;
       else if(curr->tag == n) {
           if(prev != NULL)   prev->next = curr->next;
           else HASH[m] = curr->next;
           free(curr);
           return;
       }
       else return;
   }
}
void FreeAll() {
   int a;
   for(a = 0; a < Mod; a++) {
       curr = HASH[a], prev = NULL;
       while(curr != NULL) {
           prev = curr, curr = curr->next;
           free(prev);
       }
       HASH[a] = NULL;
   }
}
void PrintHash() {
   puts("===== s =====");
   int a;
   for(a = 0; a < Mod; a++) {
       printf("[%03d]:", a);
       curr = HASH[a];
       while(curr != NULL) {
           printf("%d -> ", curr->tag);
           curr = curr->next;
       }
       puts("NULL");
   }
   puts("===== e =====");
}
main() {
   int a, k, n, op;
   while(scanf("%d %d", &k, &Mod) == 2) {
       FreeAll();
       while(k--) {
           scanf("%d", &op);
           switch(op) {
               case 1:scanf("%d", &n);
                       InsHash(n);break;
               case 2:scanf("%d", &n);
                       DelHash(n);break;
               case 3:PrintHash();break;
           }
       }
   }
   return 0;
}

我要檢舉

#a174#上帝玩不玩骰子#Hash

台長： Morris

您可能對以下文章有興趣

[ZJ][多邊形面積] d546. 3. 剪多邊形（molding）

[ZJ][BIT+掃描線] a457. TOI2010 第五題：餐廳評鑑

[ZJ][LCA][offline] d767. 血緣關係

[ZJ][博弈] d246. Stone Game

人氣(1,054) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:a175. 撒旦玩不玩骰子？ (SplayTree 版本)
此分類上一篇:d920. 智慧盤

回應(0)