数据结构课程设计（用链表法处理冲突）

用C设计哈希表——数据结构课程设计~

#include
#include
#include
using namespace std;
#define Maxsize 57
struct record
{ char name[20];
char tel[20];
char add[20];
};
typedef record * precord;struct HashTable
{ int elem[Maxsize]; //存放数组a[]的下标
int count;
};
typedef HashTable * pHashTable;
int Number; //统计当前数组a[]中的记录总数
void Getdata(precord a) //从文件telphone.txt中读取数据存放到数组a[]
{ Number=0;
ifstream infile("telphone.txt",ios::in|ios::binary);
if(!infile) {cout<<"文件打开失败!
"; exit(1);}
while(!infile.eof() && infile.get()!=EOF) //文件不为空并且文件指针没有指到结束符
{infile.seekg(Number*sizeof(a[Number]),ios::beg); //定位文件指针 infile.read((char *)&a[Number],sizeof(a[Number])); Number++; }
infile.close();
}
void Add(precord a) //添加记录
{ int i,num;
cout<<"当前文件内已有"<<Number<<"条记录
";
cout<<"请输入添加的个数:";
cin>>num;
ofstream ofile("telphone.txt",ios::app);
if(! ofile) {cout<<"文件打开失败!"; exit(1);}
for(i=0;i<num;i++)
{ cout<<"请输入第"<<Number+1<<"个人的姓名"<<endl;
cin>>a[Number].name;
cout<<"请输入第"<<Number+1<<"个人的电话"<<endl;
cin>>a[Number].tel;
cout<<"请输入第"<<Number+1<<"个人的地址"<<endl;
cin>>a[Number].add;
ofile.seekp(ios::end);
ofile.write((char *)&a[Number],sizeof(a[Number]));
Number++;
}
ofile.close();
}

void Print(precord a) //显示所有记录
{ int i;
for(i=0;i<Number;i++)
{
cout<<"第"<<i+1<<"个人的信息为:
";
cout<<" 姓名:"<<a[i].name<<endl;
cout<<" 电话:"<<a[i].tel<<endl;
cout<<" 地址:"<<a[i].add<<endl;
}
}
int Hash(char str[]) //除留取余
{ long val=0;char p[20],*p1;
strcpy(p,str);
p1=p;
while(*p1!='\0')
val=val+*p1++; //将字符串中的所有字符对应的ASCII值相加
return(val%Maxsize);
} int derter; //线性增量
int Line_Sollution(int address) //采用线性探测解决冲突
{
derter++;
if(derter==Maxsize) return(-1);
else return((address+derter)%Maxsize);
} int n;
int Square_Sollution(int address) //采用平方探测法解决冲突
{ int j;
derter++;
if(derter==Maxsize) return -1;
n=n*(-1);
j=(int(pow(derter,2))*n+address)%Maxsize;
return(j);
} void Init_Hash(pHashTable h) //初始化哈希表
{ int i;
for(i=0;i<Maxsize;i++)
h->elem[i]=-1;
}
int menu;
void Creathash_Name(pHashTable h,precord a)
//以用户名为关键字创建哈希表
{ cout<<"--------------------------------------------------------------------------------
";
cout<<" 1----以线性探测建表
";
cout<<" 2----以平方探测建表
";
cout<<"--------------------------------------------------------------------------------
";
int i,address;
cin>>menu;
Init_Hash(h);
for(i=0;i<Number;i++)
{ derter=0;n=-1;
address=Hash(a[i].name);
while(h->elem[address]!=-1)
{if(menu==1) address=Line_Sollution(address); else address=Square_Sollution(address); if(address==-1) break; } if(address!=-1) { h->elem[address]=i; h->count++;}
}
cout<<"姓名哈希表已成功建立!
";
}
void Search_Name(pHashTable h,precord a) //查找并显示指定姓名的记录
{ cout<<"请输入要查找的姓名:";
char nam[20];int address,i=1;
cin>>nam;
address=Hash(nam);
derter=0;n=-1;
while(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)!=0)
{ if(menu==1) address=Line_Sollution(address);
else address=Square_Sollution(address);
i++;
if(address==-1) break;
}
if(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)==0)
{ cout<<"你要查找的信息为:
";
coutelem[address]].name<<endl;
coutelem[address]].tel<<endl;
coutelem[address]].add<<endl;
cout<<"比较次数为"<<i<<endl;
}
else cout<<"无此姓名,查找失败!";
}
void Creathash_tel(pHashTable h,precord a)
//以电话号为关键字创建哈希表
{ cout<<"--------------------------------------------------------------------------------
";
cout<<" 1----以线性探测建表
";
cout<<" 2----以平方探测建表
";
cout<<"--------------------------------------------------------------------------------
";
int i,address;
cin>>menu;
Init_Hash(h);
for(i=0;i<Number;i++)
{ derter=0;n=-1;
address=Hash(a[i].tel);
while(h->elem[address]!=-1)
{if(menu==1) address=Line_Sollution(address); else address=Square_Sollution(address); if(address==-1) break; } if(address!=-1) { h->elem[address]=i; h->count++;}
}
cout<<"电话号哈希表已成功建立!
";
} void Search_tel(pHashTable h,precord a)
//查找并显示指定电话号的记录
{ cout<<"请输入要查找的电话:";
char telphone[20];int address,i=1; //i统计比较次数
cin>>telphone;
address=Hash(telphone);
derter=0; n=-1; //初始化线性增量
while(h->elem[address]!=-1 && strcmp(telphone,a[h->elem[address]].tel)!=0)
{ if(menu==1) address=Line_Sollution(address);
else address=Square_Sollution(address);
i++;
if(address==-1) break;
}
if(h->elem[address]!=-1 && strcmp(telphone,a[h->elem[address]].tel)==0)
{ cout<<"你要查找的信息为:
";
coutelem[address]].name<<endl;
coutelem[address]].tel<<endl;
coutelem[address]].add<<endl;
cout<<"比较次数为"<<i<<endl;
}
else cout<<"无此电话,查找失败!";
} void Menu() //功能菜单函数
{for(int i=1;i cout cout cout cout cout cout cout cout cout cout cout cout cout cout cout cout} void exit()
{
int i;
for(i=1;i<=4;i++)
cout<<endl;
cout<<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◇◆◇
";
cout<<" ◆ ◆
";
cout<<" ◇ 电 话 号 码 查 询 系 统 ◇
";
cout<<" ◆ ◆
";
cout<<" ◇ 谢 谢 您 的 使 用 ! ◇
";
cout<<" ◆ ◆
";
cout<<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇
";} int main()
{ record a[Maxsize];
pHashTable H=new HashTable;
Getdata(a); //将文件中的数据读入到数组a中
start:
Menu();
int menu1;
cin>>menu1;
switch(menu1)
{ case 0:system("cls");exit();break;
case 1:Add(a);system("pause");system("cls");goto start;break;
case 2:Print(a);system("pause");system("cls");goto start;break;
case 3:Creathash_Name(H,a);system("pause");system("cls");goto start;break;
case 4:Creathash_tel(H,a);system("pause");system("cls");goto start;break;
case 5:Search_Name(H,a);system("pause");system("cls");goto start;break;
case 6:Search_tel(H,a);system("pause");system("cls");goto start;break;
default:cout<<"请输入正确的操作选项!
";system("cls");goto start;break;
}
return 0;
}

简单的链表和结构体定义操作，自己写吧，很容易的，自己不动手始终没长进.” 自己动手，丰衣足食“

数据结构课程设计（用链表法处理冲突）我帮您弄,绝对原创.

---

施甸县15730042258： 用链表法的基本原理如何解决哈希冲突？
迪于加力： 向哈希表中添加一个节点B时,如果哈希表中已经存在一个具有相同哈希值的节点A,则将新节点B添加到以A为头节点的链表中.

施甸县15730042258： 用数据结构链地址法解决冲突,编写插入、删除和查找算法 - ？
迪于加力： 多看看数据结构里的链接地址法的相关知识,像基本的插入删除,查找都有讲的.看一点树,图的知识.很久没看书了,也忘记了,呵呵.书上有目录的都有联接地址发的叙述的.就是一般的数据结构的书都有吧.主要是在讲二叉树和图的那些地方有这些存储方法的数据结构.

施甸县15730042258： 用链表和数组实现HASH表,几种碰撞冲突解决方法 - ？
迪于加力： 1.开放地址法 开放地执法有一个公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k其中,m为哈希表的表长.di 是产生冲突的时候的增量序列.如果di值可能为1,2,3,…m-1,称线性探测再散列.如果di取1,则每次冲突之后,向后移动1个位置.如果di取值...

施甸县15730042258： 数据结构,画图 - ？
迪于加力： /* getline: read a line into s, return length */ int getline(char s[],int lim) { int c, i; for (i=0; is[i] = c; if (c == '\n') { s[i] = c; ++i; } s[i] = '\0'; return i; }

施甸县15730042258： 11、采用拉链法解决冲突,散列函数为 H(k) = k mod 17 .则需要个链表...？
迪于加力： /*10.3.2源程序*/ /******头文件(.h)***********/ #include ＂stdio.h＂ /*I/O函数*/ #include ＂stdlib.h＂ /*标准库函数*/ #include ＂string.h＂/*字符串函数*/ #include ＂ctype.h＂ /*字符操作函数*/ #define M 50 /*定义常数表示记录数*/ typedef struct /*定义...

施甸县15730042258： 关于数据结构的问题?？
迪于加力： 查找长度就是每个元素的查找要经过几次比较,把次数相加,然后除以元素个数就行了.

施甸县15730042258： 急求数据结构的课程设计程序:链表操作!!!？
迪于加力： http://topic.csdn.net/t/20051130/11/4428114.html 看这个吧