OJ3-2 B. Hash Table

B. Hash Table
运行时间限制: 1000 运行内存限制: 65536
作者: scsxuke 是否specialjudge: False
题目描述
Create a hash table （Open Addressing） from the given sequence and output the Londing Density and Average Search Time (AST). The hash function is H（key）= key % 13 and use linear probing to sovle the collision.
Input a sequence of integer seperated by comma.
Output 2 lines, the first is Loading Density, the second is AST. (Two decimal places are reserved for the result)

输入样例
12,13,14,26,
输出样例
0.31
1.50

#include <stdio.h>
#include <stdlib.h>
#define full 1
#define empty 0
#define delete 2
struct Node;
typedef struct Node *ptrtoNode;struct Node
{
    int x;int kind;
};
int insert(int x, ptrtoNode array[]);
int main()
{
    char ch[200];gets(ch);int nums, num; //nums 为一个数，num为一个数的某一位nums = num = 0;double times = 0;    //times 是查找的次数ptrtoNode array[13]; // 相当于hashtablefor (int i = 0; i < 13; i++){
    array[i] = malloc(sizeof(struct Node));array[i]->kind = empty;}int numbers = 0; //一共有几个数？for (int i = 0; ch[i] != '\0'; i++){
    if (ch[i] != ','){
    num = ch[i] - '0';nums = nums * 10 + num;}else{
    times = insert(nums, array) + times;nums = 0;numbers++;}}double LD = numbers / 13.00;double AST = times / numbers;printf("%.2lf\n", LD);printf("%.2lf\n", AST);return 0;
}
int insert(int x, ptrtoNode array[])
{
    int time = 1;int pos;pos = x % 13;while (array[pos]->kind != empty){
    pos++;pos = pos % 13;time++;}array[pos]->x = x;array[pos]->kind = full;return time;
}