*******怎样设计数据结构或算法呢？******
需求大概是这样的.
有10w或更多的电话号码信息，对它进行的操作，比如查找，删除，插入单个号码信息（按号码匹配）？
大概流程就是：单个号码信息过来，查找储存数据结构是否有相应号码，然后根据做相应的修改，删除。如果无的话，可能插入该条记录。
觉得用链表，复杂性O(n),不是很好。
有没其它数据结构或算法能满足？
2叉树的话可能会有最坏的复杂度o（n）？大家多提意见，谢谢！！
[解决办法]
/*
* Copyright (c) 2005 All rights reserved.
* 文件名：HashSearch.c
*
* 文件标识：HashSearch
* 摘要：一个简单的哈希表搜索示例
* 输入：员工的ID
* 输出：根据输入的ID查找员工资料并输出，若没有找到给出相应提示
*
* 当前版本 0.01
* 作者：罗
* 完成日期：2006年3月28日
*/
#include <stdio.h>
#include <stdlib.h>
#define HASHSIZE 11
/* 哈希表元素的结构定义 */
typedef struct
{
int ID;
char *name;
float salary;
} employee;
typedef employee DataType;
/* 定义一个全局的，元素类型为 employee 的哈希表 */
DataType Hash[HASHSIZE];
/*
函数名：Create_Hash
参数：employees为员工资料数组， size为数组大小
功能：将大小为size的员工资料数组按员工ID映射到Hash表
*/
void Create_Hash(DataType *employees, int size);
/*函数名：HashFun
参数：key为员工ID
功能：将员工ID映射为Hash表中的下标地址
返回值：返回给定关键字对应的Hash表下标地址
*/
int HashFun(int key);
/*函数名：HashSearch
参数：key为员工的ID
功能：在Hash表中搜索给定关键字的员工信息
返回值：找到返回1，并输出员工资料， 找不到返回0并提示没有找到
*/
int HashSearch(int key);
/*函数名：OverHandle
参数：address发生冲突Hash表下标地址
功能：
返回值：
*/
int OverHandle(int address);
/*函数名：printemployee
参数：一个员工资料结构的指针
功能：屏幕输出员工资料
返回值：无
*/
void printemployee(DataType *employee)
{
printf( "ID : %d \t Name: %s\t Salary:%f\n ",
employee-> ID, employee-> name, employee-> salary);
}
int main(int argc, char* argv[])
{
int size;
int key1;
static char ch;
/* 员工资料数组 */
DataType employee[] = {
{11, "luojiafeng ", 5000},
{37, "wangqian ", 8000},
{48, "liujie ", 6000},
{97, "gaoxing ", 10000},
{86, "xiaozhen ", 6000},
{26, "chenghu ", 8800}
};
/* 数组元素个数 */
size = sizeof(employee) / sizeof(employee[0]);
/* 将员工资料数组映射到哈希表 */
Create_Hash(employee, size);
/* 输入一个员工的ID，查找并显示相关信息 */
printf( "请输入一位员工的ID：\n ");
scanf( "%d ", &key1);
HashSearch(key1);
}
void Create_Hash(DataType *employees, int size)
{
int i, j;
DataType empty = {0, NULL, 0.0};
for (i = 0; i < HASHSIZE; i++)
{
Hash[i] = empty;
}
for (i = 0; i < size; i++)
{
j = 0;
while (j < HASHSIZE)
{
/* 根据员工ID，将员工资料存放到哈表 */
if (Hash[(employees[i].ID % HASHSIZE) + j].ID == 0)
{
Hash[(employees[i].ID % HASHSIZE) + j] = employees[i];
break;
}
/* j++表示发生了冲突 */
else
j++;
}
}
}
int HashFun(int key)
{
return key % HASHSIZE;
}
DataType HashValue(int key)
{
return Hash[key % HASHSIZE];
}
int HashSearch(int key)
{
DataType temp;
int address, count = 0;
address = HashFun(key);
count++;
temp = HashValue(address);
if (temp.ID == key)
{
printemployee(&temp);
return 1;
}
else if (temp.ID == 0)
{
printf( "没有找到与您输入ID相关的记录!\n ");
return 0;
}
else
{
while (count < HASHSIZE)
{
address = OverHandle(address);
temp = HashValue(address);
if (temp.ID == key)
{
printemployee(&temp);
return 1;
}
count++;
}
}
return 0;
}
int OverHandle(int address)
{
return (address+1) % HASHSIZE;
}
[解决办法]
靠，虫子就素快啊。
果然是哈希啊。
研究研究。
[解决办法]
有10w或更多的电话号码信息
#define HASHSIZE 11
这个应该远远不够哦。
冲突应该很厉害吧。
[解决办法]
用树不是很好吗？查找/删除都只跟号码长度有关
不过要想办法减少存储空间，可以用一个16位的int做标志
[解决办法]
所谓的 "电话号码信息 "是只有电话号码呢还是除了号码之外还有其他诸如姓名,性别,单位等条目呢?
