哈希表实现电话号码查询系统,求数据结构（用面向对象方法与C++语言描述）第二版 殷人昆主编 课后答案
哈希表实现电话号码查询系统,求数据结构（用面向对象方法与C++语言描述）第二版 殷人昆主编 课后答案详细介绍
本文目录一览： 用Visual c#中的windows应用程序模拟向手机中添加联系人和查询电话号码。。急！急！急！
露骨
设计题目三：创建控制台应用程序，模拟向手机中添加联系人和查询电话号码。
提示：联系人和电话号码是键值对的关系，可以使用哈希表来存储联系人及其电话号码，通过键（联系人的姓名）来查询其电话号码。
1）.添加联系人：
2）.查询联系人电话
static void Main(string[] args)
{
Hashtable ht = new Hashtable();
string choice;
while (true)
{
Console.WriteLine("增加联系人,请输入:new");
Console.WriteLine("查询联系人,请输入:query");
Console.WriteLine("显示所有联系人,请输入:all");
Console.WriteLine("退出,请输入:quit");
Console.WriteLine("删除联系人,请输入:del");
choice = Console.ReadLine().Trim();
if (choice == "new")
{
String newName, newTelephone;
Console.WriteLine("请输入联系人的姓名");
newName = Console.ReadLine();
Console.WriteLine("请输入新联系人的电话号码");
newTelephone = Console.ReadLine();
//将新联系人的姓名,电话号码这一组值添加到Hashtable中;
ht.Add(newName ,newTelephone );
Console.WriteLine("现有联系人{0}位", ht.Count );
Console.WriteLine();
}
if (choice == "query")
{
string findName;
Console.WriteLine("请输入联系人的姓名:");
findName = Console.ReadLine();
object find = ht[findName];
if (find != null)
{
Console.WriteLine("姓名,电话号码");
Console.WriteLine("{0,-10}{1,-10}", findName, ht[findName].ToString());
Console.WriteLine();
}
else
{
Console.WriteLine("此联系人不存在");
}
}
if (choice == "all")
{
Console.WriteLine("现有联系人{0}位", ht.Count);
Console.WriteLine("姓名 电话号码");
foreach (DictionaryEntry ide in ht)
{
Console.WriteLine("{0,-10}{1,-10}", ide.Key, ide.Value );
}
Console.WriteLine();
}
if(choice=="del")
{
}
if (choice == "quit")
{
break;
}
}
}
用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<<"文件打开失败!\n"; 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<<"条记录\n";
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<<"个人的信息为:\n";
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<<"--------------------------------------------------------------------------------\n";
cout<<" 1----以线性探测建表\n";
cout<<" 2----以平方探测建表\n";
cout<<"--------------------------------------------------------------------------------\n";
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<<"姓名哈希表已成功建立!\n";
}
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<<"你要查找的信息为:\n";
cout<<" 姓名:"<
elem[address]].name<
<endl;
cout<<" 电话:"<
elem[address]].tel<
<endl;
cout<<" 地址:"<
elem[address]].add<
<endl;
cout<<"比较次数为"<
<i<<endl;
}
else cout<<"无此姓名,查找失败!";
}
void Creathash_tel(pHashTable h,precord a)
//以电话号为关键字创建哈希表
{ cout<<"--------------------------------------------------------------------------------\n";
cout<<" 1----以线性探测建表\n";
cout<<" 2----以平方探测建表\n";
cout<<"--------------------------------------------------------------------------------\n";
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<<"电话号哈希表已成功建立!\n";
} 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<<"你要查找的信息为:\n";
cout<<" 姓名:"<
elem[address]].name<
<endl;
cout<<" 电话:"<
elem[address]].tel<
<endl;
cout<<" 地址:"<
elem[address]].add<
<endl;
cout<<"比较次数为"<
<i<<endl;
}
else cout<<"无此电话,查找失败!";
} void Menu() //功能菜单函数
{for(int i=1;i<=5;i++)
cout<
<endl;
cout<<" 电话号码查询系统\n";
cout<<'\n';
cout<<" \n";
cout<<" 0-------退出 \n";
cout<<" 1-------添加 \n";
cout<<" 2-------显示所有 \n";
cout<<" 3-------以性命建立哈希表 \n";
cout<<" 4-------以电话建立哈希表 \n";
cout<<" 5-------按用户名查找 \n";
cout<<" 6-------按电话号查找 \n";
cout<<" \n";
cout<<" 使用说明:\n";
cout<<" 1.添加新纪录后,如要进行查找请先进行3或4操作\n";
cout<<" 2.按用户名查找之前,请先进行3操作建立用户名哈希表\n";
cout<<" 3.按用户名查找之前,请先进行4操作建立电话号哈希表\n";
} void exit()
{
int i;
for(i=1;i<=4;i++)
cout<
<endl;
cout<<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◇◆◇\n";
cout<<" ◆ ◆\n";
cout<<" ◇ 电 话 号 码 查 询 系 统 ◇\n";
cout<<" ◆ ◆\n";
cout<<" ◇ 谢 谢 您 的 使 用 ! ◇\n";
cout<<" ◆ ◆\n";
cout<<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇\n";} 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<<"请输入正确的操作选项!\n";system("cls");goto start;break;
}
return 0;
}
</endl;
</endl;
</i<<endl;
</endl;
</endl;
</endl;
</number;i++)
</i<<endl;
</endl;
</endl;
</endl;
</number;i++)
</maxsize;i++)
</a[i].add<<endl;
</a[i].tel<<endl;
</a[i].name<<endl;
</i+1<<"个人的信息为:\n";
</number;i++)
</number+1<<"个人的地址"<<endl;
</number+1<<"个人的电话"<<endl;
</number+1<<"个人的姓名"<<endl;
</num;i++)
</number<<"条记录\n";
求数据结构（用面向对象方法与C++语言描述）第二版 殷人昆主编 课后答案
第一章 习题答案
2、××√
3、（1）包含改变量定义的最小范围
（2）数据抽象、信息隐蔽
（3）数据对象、对象间的关系、一组处理数据的操作
（4）指针类型
（5）集合结构、线性结构、树形结构、图状结构
（6）顺序存储、非顺序存储
（7）一对一、一对多、多对多
（8）一系列的操作
（9）有限性、输入、可行性
4、（1）A（2）C（3）C
5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）
第二章 习题答案
1、（1）一半，插入、删除的位置
（2）顺序和链式，显示，隐式
（3）一定，不一定
（4）头指针，头结点的指针域，其前驱的指针域
2、（1）A（2）A：E、A
B：H、L、I、E、A
C：F、M
D：L、J、A、G或J、A、G
（3）D（4）D（5）C（6）A、C
3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。
头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，
该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。
首元素结点：线性表中的第一个结点成为首元素结点。
4、算法如下：
int Linser(SeqList *L,int X)
{ int i=0,k;
if(L->last>=MAXSIZE-1)
{ printf(“表已满无法插入”)；
return(0);
}
while(i<=L->last&&L->elem[i]
<x)
i++;
for(k=L->last;k>=I;k--)
L->elem[k+1]=L->elem[k];
L->elem[i]=X;
L->last++;
return(1);
}
5、算法如下：
#define OK 1
#define ERROR 0
Int LDel(Seqlist *L,int i,int k)
{ int j;
if(i<1||(i+k)>(L->last+2))
{ printf(“输入的i，k值不合法”);
return ERROR;
}
if((i+k)==(L->last+2))
{ L->last=i-2;
ruturn OK;
}
else
{for(j=i+k-1;j<=L->last;j++)
elem[j-k]=elem[j];
L->last=L->last-k;
return OK;
}
}
6、算法如下：
#define OK 1
#define ERROR 0
Int Delet(LInkList L,int mink,int maxk)
{ Node *p,*q;
p=L;
while(p->next!=NULL)
p=p->next;
if(mink
next->data>=mink)||(p->data<=maxk))
{ printf(“参数不合法”);
return ERROR;
}
else
{ p=L;
while(p->next-data<=mink)
p=p->next;
while(q->data
<maxk)
{ p->next=q->next;
free(q);
q=p->next;
}
return OK;
}
}
9、算法如下：
int Dele(Node *S)
{ Node *p;
P=s->next;
If(p= =s)
{printf(“只有一个结点，不删除”)；
return 0;
}
else
{if((p->next= =s)
{s->next=s;
free(p);
return 1;
}
Else
{ while(p->next->next!=s)
P=p->next;
P->next=s;
Free(p);
return 1;
}
}
}
第三章 习题答案
2、（1）
3、栈有顺序栈和链栈两种存储结构。
在顺序栈中，栈顶指针top=-1时，栈为空；栈顶指针top=Stacksize-1时，栈为满。
在带头结点链栈中，栈顶指针top-〉next=NULL，则代表栈空；只要系统有可用空间，链栈就不会出现溢出，既没有栈满。
5、
#include
#include "stdio.h"
void main( )
{
char ch,temp;
SeqStack s;
InitStack(&s);
scanf("%c",&ch);
while(ch!='@'&&ch!='&')
{
Push(&s,ch);
scanf("%c",&ch);
}
while(ch!='@'&&!IsEmpty(&s))
{
Pop(&s,&temp);
scanf("%c",&ch);
if(ch!=temp)
break;
}
if(!IsEmpty(&s))
printf("no!\n");
else
{
scanf("%c",&ch);
if(ch=='@') printf("yes!\n");
else printf("no!\n");
}
}
12、（1）功能：将栈中元素倒置。
（2）功能：删除栈中的e元素。
（3）功能：将队列中的元素倒置。
第四章习题答案
1、StrLength(s)操作结果为14；SubString(sub1,s,1,7)操作结果为sub1=’I AM A ’；
SubString(sub2,s,7,1)操作结果为sub2=’ ’；StrIndex(s,’A’,4) 操作结果为5；
StrReplace(s,’STUDENT’,q) 操作结果为’I AM A WORKER’；
StrCat(StrCat(sub1,t), StrCat(sub2,q)) 操作结果为’I AM A GOOD WORKER’；
2、
int StrReplace(SString S,Sstring T,SString V)
{
int i=1; //从串S的第一个字符起查找串T
if(StrEmpty(T)) //T是空串
return ERROR;
do
{
i=Index(S,T,i); //结果i为从上一个i之后找到的子串T的位置
if(i) //串S中存在串T
{
StrDelete(S,i,StrLength(T)); //删除该串T
StrInsert(S,i,V); //在原串T的位置插入串V
i+=StrLength(V); //在插入的串V后面继续查找串T
}
}while(i);
return OK;
}
第五章习题答案
1、（1）数组A共占用48*6=288个字节；
（2）数组A的最后一个元素的地址为1282；
（3）按行存储时loc（A36）=1000+[（3-1）*8+6-1]*6=1126
（4）按列存储时loc（A36）=1000+[（6-1）*6+3-1]*6=1192
9、（1）（a，b）（2）（（c，d））（3）（b）（4）b（5）（d）
10、D
第六章 习题答案
1、三个结点的树的形态有两个；三个结点的二叉树的不同形态有5个。
2、略
3、证明：分支数=n1+2n2+…+knk （1）
n= n0+n1+…+nk （2）
∵n=分支数+1 （3）
将（1）（2）代入（3）得
n0= n2+2n3+3n4+…+（k-1）nk+1
4、
注：C结点作为D的右孩子（画图的时候忘记了，不好意思）
5、n0=50，n2=n0-1=49，所以至少有99个结点。
6、（1）前序和后序相同：只有一个结点的二叉树
（2）中序和后序相同：只有左子树的二叉树
（3）前序和中序相同：只有右子树的二叉树
7、证明：∵n个结点的K叉树共有nk个链域，分支数为n-1（即非空域）。
∴空域=nk-（n-1）=nk-n+1
8、对应的树如下：
9、（答案不唯一）
哈夫曼树如下图所示：
哈夫曼编码如下：
频率 编码
0.07 0010
0.19 10
0.02 00000
0.06 0001
0.32 01
0.03 00001
0.21 11
0.10 0011
11、对应的二叉树如下：
12、求下标分别为i和j的两个桔点的最近公共祖先结点的值。
typedef int ElemType;
void Ancestor(ElemType A[],int n,int i,int j)
{while(i!=j)
if(i>j) i=i/2;
else j=j/2;
printf("所查结点的最近公共祖先的下标是%d,值是%d",i,A[i]);
}
15、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。
void Del_Sub(BiTree T)
{ if(T->lchild) Del_Sub(T->lchild);
if(T->rchild) Del_Sub(T->rchild);
free(T);
}
void Del_Sub_x(BiTree T,int x)
{ if(T->data==x) Del_Sub(T);
else
{if(T->lchild) Del_Sub_x(T->lchild,x);
if(T->rchild) Del_Sub_x(T->rchild,x);
}
}
22、
int Width(BiTree bt)
{if (bt==NULL) return (0);
else
{BiTree p,Q[50];
int front=1,rear=1,last=1;
int temp=0, maxw=0;
Q[rear]=bt;
while(front<=last)
{p=Q[front++]; temp++;
if (p->lchild!=NULL) Q[++rear]=p->lchild;
if (p->rchild!=NULL) Q[++rear]=p->rchild;
{last=rear;
if(temp>maxw) maxw=temp;
temp=0;}
}
return (maxw);
}
}
第七章 习题答案
1、（1）顶点1的入度为3，出度为0；
顶点2的入度为2，出度为2；
顶点3的入度为1，出度为2；
顶点4的入度为1，出度为3；
顶点5的入度为2，出度为1；
顶点6的入度为2，出度为3；
（2）邻接矩阵如下：
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
（3）邻接表
（4）逆邻接表
2、答案不唯一
（2）深度优先遍历该图所得顶点序列为：1，2，3，4，5，6
边的序列为：（1，2）（2，3）（3，4）（4，5）（5，6）
（3）广度优先遍历该图所得顶点序列为：1，5，6，3，2，4
边的序列为：（1，5）（1，6）（1，3）（1，2）（5，4）
3、
（1）每个事件的最早发生时间：
ve(0)=0,ve(1)=5,ve(2)=6, ve(3)=12, ve(4)=15, ve(5)=16,
ve(6)=16, ve(7)=19, ve(8)=21, ve(9)=23
每个事件的最晚发生时间:：
vl(9)=23, vl(8)=21, vl(7)=19, vl(6)=19, vl(5)=16, vl(4)=15,
vl(3)=12, vl(2)=6, vl(1)=9, vl(0)=0
（2）每个活动的最早开始时间：
e(0,1)=0, e(0,2)=0, e(1,3)=5, e(2,3)=6, e(2,4)=6, e(3,4)=12, e(3,5)=12,
e(4,5)=15, e(3,6)=12, e(5,8)=16, e(4,7)=15, e(7,8)=19, e(6,9)=16, e(8,9)=21
每个活动的最迟开始时间：
l(0,1)=4, l(0,2)=0, l(1,3)=9, l(2,3)=6, l(2,4)=12, l(3,4)=12, l(3,5)=12, l(4,5)=15, l(3,6)=15, l(5,8)=16, l(4,7)=15, l(7,8)=19, l(6,9)=19, l(8,9)=21
（3）关键路径如下图所示：
4、顶点1到其余顶点的最短路经为：
1-〉3最短路经为1，3；长度为15
1-〉2最短路经为1，3，2；长度为19
1-〉5最短路经为1，3，5；长度为25
1-〉4最短路经为1，3，2，4；长度为29
1-〉6最短路经为1，3，2，4，6；长度为44
13、A(7)B(3)C(2)D(11)E(8)
14、略
15、略
第八章 查找
1、画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：
ASL=(1+2*2+4*3+3*4)/10=2.9
5、
解：（1）插入完成后的二叉排序树如下：
ASL=(1+2*2+3*3+3*4+2*5+1*6)/12=3.5 ？？？？
(2)ASL=(1+2*2+3*4+4*5)=37/12
(3)
12、
解：哈希表构造如下：
0 1 2 3 4 5 6 7 8 9 10
22 41 30 01 53 46 13 67
H(22)=(22*3)%11=0
H(41)=(41*3)%11=2
H(53)=(53*3)%11=5
H(46)=(46*3)%11=6
H(30)=(30*3)%11=2 与(41)冲突
H1(30)=(2+1)%11=3
H(13)=(13*3)%11=6 与46冲突
H1(13)=(6+1)%11=7
H(01)=(01*3)%11=3 与30冲突
H1(01)=(3+1)%11=4
H(67)=(67*3)%11=3 与30冲突
H1(67)=(3+1)%11=4 与01冲突
H2(67)=(3+2)%11=5 与53冲突
H3(67)=(3+3)%11=6 与46冲突
H4(67)=(3+4)%11=7 与13冲突
H5(67)=(3+5)%11=8
ASLsucc=(1*4+2*3+6)/8=2
ASLunsucc=(2+8+7+6+5+4+3+2)/8=37/8
第九章 排序
1、以关键字序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟派结束时的关键字状态。
（1）直接插入排序（2）希尔排序（增量序列为5，3，1）（3）快速排序（4）堆排序（5）归并排序
解：（1）略
（2）增量为5的排序结果：170，087，275，061，426，503，897，512，653，908
增量为3的排序结果：061，087，275，170，426，503，897，512，653，908
增量为1的排序结果：061，087，170，275，426，503，512，653，897，908
（3）一次划分后：{426 087 275 061 170}503{897 908 653 512}
分别进行：{170 087 275 061}426 503 {512 653} 897 {908}
{061 087}170{275}426 503 512 {653} 897 908
061 087 170 275 426 503 512 653 897 908
（4）略
7、已知一组关键字：（40，27，28，12，15，50，7），要求采用快速排序法从小到大排序。请写出每趟排序后的划分结果。
解：初始状态：40 27 28 12 15 50 7
一次划分：{7 27 28 12 15} 40 {50}
依次划分：7 {27 28 12 15} 40 50
7 {15 12} 27 {28} 40 50
7 12 15 27 28 40 50
16、（1）A3 B1 C4 D2 E7
(2)C
(3)C
17、对，错，对
数据结构课程设计指导书
一、设计内容
1.飞机订票系统（限1 人完成）
【问题描述】
设计一个飞机订票系统，可以模拟处理飞机订票过程中的各种操作。
【基本要求】
通过此系统可以实现如下功能：
1)录入
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）。
2)查询
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况。
3)订票（订票情况可以存在一个数据文件中，结构自己设定）
可以订票，如果该航班已经无票，可以提供相关可选择航班。
4)退票
可退票，退票后修改相关数据文件。
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
5)修改航班信息
当航班信息改变可以修改航班数据文件
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。
2.文章编辑（限1 人完成）
【问题描述】
输入一页文字，程序可以统计出文字、数字、空格的个数。
【基本要求】
静态存储一页文章，每行最多不超过80个字符，共N行；
1)分别统计出其中英文字母数和空格数及整篇文章总字数；
2)统计某一字符串在文章中出现的次数，并输出该次数；
3)删除某一子串，并将后面的字符前移；
4)用指定的字符串替换某一子串；
5)存储结构使用线性表，分别用几个子函数实现相应的功能；
6)输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。
7)输出形式：①分行输出用户输入的各行字符；②分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"；③输出删除某一字符串后的文章；④输出替换某一字符串后的文章。
3.宿舍管理查询软件（限1 人完成）
【问题描述】
为宿舍管理人员编写一个宿舍管理查询软件。
【基本要求】
1) 程序设计要求：
①采用交互工作方式
②建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)
2) 查询菜单: (用二分查找实现以下操作)
①按姓名查询
②按学号查询
③按房号查询
3) 输出任一查询结果（可以连续操作）
4.全国交通咨询模拟
【问题描述】
处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。
【设计要求】
1)提供对城市信息进行编辑（如：添加或删除）的功能。
2)提供对列车时刻表进行编辑（增设或删除）的功能。
3) 提供两种最优决策：最快到达和最省钱到达。
4)旅途中耗费的总时间应该包括中转站的等候时间。
5)咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明于何时乘坐哪一趟列车到何地。
测试数据：参考教科书7.6节图7.33的全国交通图，自行设计列车时刻表。
【实现提示】
1) 对全国城市交通图和列车时刻表进行编辑，应该提供文件形式输入和键盘输入两种方式。列车时刻表则需根据交通图给出各个路段的详细信息，例如：基于教科书7.6节图7.33的交通图，对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。
2) 以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。
5.哈夫曼编码/译码器（限1 人完成）
【问题描述】
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
【基本要求】
1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)
2) 分别采用动态和静态存储结构
3) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
4) 编码：利用建好的哈夫曼树生成哈夫曼编码；
5) 输出编码；
6) 设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
【进一步完成内容】
1) 译码功能；
2) 显示哈夫曼树；
3) 界面设计的优化。
6.走迷宫游戏
【问题描述】
以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
【基本要求】
1．首先用二维数组存储迷宫数据，迷宫数据由用户输入。
2．一个以链表作存储结构的栈类型，然后编写一个求解迷宫的递归或非递归程序。求得的通路以三元组（i，j，d）形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东、南、西、北四个方向所用代表数字，自行定义）。
3．可以用多种方法实现，但至少用两种方法，用三种以上可加分。
【实现提示】
1．计算机解迷宫问题通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。
迷宫的入口点的下标为（1，1），出口点的下标为（m，n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫的任一位置，均可约定有东、南、西、北四个方向可通。
2．有一种简单走出迷宫的方法，把手放在右边的墙上开始前进，始终不要把手从墙上移开。如果迷宫向右拐，你也顺着墙向右拐。只要不把手从墙上移开，最终就会到达迷宫的出口。当然这样得到的路径可能不是一个最短的路径，但它可以最终得到结果，换句话说，这种方法走不出迷宫的风险是最小的。
7.作业评分系统
【问题描述】
设计一个可以给小学生出题并且可以给出分数的系统软件。
【基本要求】
利用栈求表达式的值，可供小学生作业，并能给出分数。
1) 建立试题库文件，随机产生n个题目；
2) 题目涉及加减乘除，带括弧的混合运算；
3) 随时可以退出；
4) 给出作业分数。
【进一步完成内容】
1）保留历史分数，能回顾历史，给出与历史分数比较后的评价。
2）界面设计的优化。
8.散列表的设计与实现
【问题描述】
设计散列表实现电话号码查找系统。
【基本要求】
1)设每个记录有下列数据项：电话号码、用户名、地址；
2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
3)采用一定的方法解决冲突；
4)查找并显示给定电话号码的记录；
5)查找并显示给定用户名的记录。
【进一步完成内容】
1) 系统功能的完善；
2) 设计不同的散列函数，比较冲突率；
3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
9.停车场管理
【问题描述】
设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
【基本要求】
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。
【测试数据】
设n=2，输入数据为：(‘A’,1,5),(‘A’,2,10),(‘D’,1,15),(‘A’,3,20),(‘A’,4,25),
(‘A’,5,30),(‘D’,2,35),(‘D’,4,40),(‘E’,0,0)。其中：‘A’表示到达（Arrival）；‘D’表示（Departure）；‘E’表示输入结束（End）。
【实现提示】
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
10.八皇后问题
【问题描述】
求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。
这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线8个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉，也就是下一个皇后不能放的位置。
1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。
【实现提示】
求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。
二、时间安排
2005~2006(一)第19周进行。
第一天： 分析题目，查阅资料；
第二天：算法设计、编码；
第三天：编码、调试运行；
第四天：调试运行，撰写设计报告；；
第五天：答辩。
三、设计工作要求
1．对学生的要求
(1) 要求学生认真阅读设计任务书，了解所做的设计内容及要求，认真主动完成课设的要求。有问题及时主动通过各种方式与教师联系沟通。
(2)学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时向教师汇报。
(3)查阅相关的参考文献；独立完成设计任务。
(4)认真撰写课程设计说明书，要求文字通顺、有逻辑性、真正反映设计的水平，设计要有创新。
(5)设计完成后上交相关内容要求：
①上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。
②课程设计说明书：到教务处网站下载课程设计报告纸及封面。格式及要求见附录。
2．对教师的要求
(1)做好设计题目的选题工作，使题目达到一定的综合性要求，工作量合理；
(2)加强指导，严格考勤、考核；
(3)做好答辩、设计报告的评审以及成绩评定工作。
附录：
课程设计说明书，格式及要求如下：
一、封面；
二、目录；
三、设计任务书；
四、说明书正文，主要内容包括：
1．设计题目；
2．设计目的；
3．算法思想分析；
4．算法描述与实现；
5．结论
</maxk)
</x)
设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。
数据结构部分课程设计题目 题目一：运动会分数据统计问题描述：参加运动会的n个学校编号为1~n，比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m+1~m+w。有些项目取前五名，得分依次为6，4，3，2，1；有些项目取前三名，得分依次为4，2，1。写一程序产生各学校的成绩单（包括各校所取得的每项成绩的项目号、成绩、姓名和得分）和团体总分报表（包括校号、男子团体总分、女子团体总分和团体总分）。基本要求：参阅数据结构题集79页题目二：编写一个文本编辑器(记事本) 问题描述：要有文本编辑器的基本功能，如打开、编辑、保存等。基本要求 ：1．要制作字符形式的菜单．2．不同的功能使用不同的函数实现．3．对程序进行必要的注释．题目三：停车场管理问题问题描述：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停了n辆汽车，则后来的汽车只能在门外的通道上等候，一旦有车开走，收排在通道上的第一辆车即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场，每辆停放在停车场的车在它离开停车场时必须按它停留在停车场内的时间长短交纳停车费。试为停车场编写按上述要求进行管理的模拟程序。基本要求：参阅数据结构题集96页。 题目四： 图书管理 问题描述：图书管理基本业务活动包括对一本书的采编入库、清除库存、借阅和归还等等。将上述业务活动借助于计算机系统完成。基本要求：参阅数据结构题集167页 题目五：关键路径问题问题描述：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。基本要求：1、对一个描述工程的AOE网，应判断其是否能够顺利进行。2、若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。 题目六：任意长的整数加法问题描述：设计一个程序实现两个任意长的整数的求和运算。基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000题目七：哈夫曼编码译码器问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。 题目八：交通咨询模拟问题描述：建立一个模拟的交通网络（用有向网来表示），编程实现从某个城市出发到另一个城市所需的最短的时间及路径。题目九：车厢调度问题描述：假设停在铁路调度站（如数据结构教材图3.1（b）所示）入口处的车厢序列的编号一次为1，2，3，…，n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。题目十：表达式求值问题描述：设计一个程序求任意一个浮点数表达式的计算结果。 题目十一：串的查找和替换问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。 题目十二：约瑟夫环问题描述：编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 基本要求：1、利用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m及各人密码；
3、按照出列顺序输出各人的编号。 题目十三：构造可以使n个城市连接的最小生成树
问题描述：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 题目十四：哈希表的设计与实现 问题描述： 设计哈希表实现电话号码查询系统。
基本要求：1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；
3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。
6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。 题目十五：构造01串
问题描述：给定七个整数N,A,B,L,C,D,M;要求设计一个01串S=S(1)S(2)…S(N)。
基本要求：1、S(i)=0或S(i)=1,1≤i≤N;
2、对于S的任何连续长度为L的子串S(j)S(j+1)…S(j+L-1) ,(1≤j≤N-L+1),0的个数大于等于A且小于等于B;
3、对于S的任何连续长度为M的子串S(j)S(j+1)…S(j+M-1) , (1≤j≤N-M+1),0的个数大于等于C且小于等于D; 列如,N=6,A=1,B=2,L=3,C=1,D=1,M=2,则存在一个满足上述所有条件的01串 S=10101。
设计哈希表实现电话号码查询系统
用map存，用map取，很简单
如何编写C语言程序使得输入编号就可以显示其他的个人信息
首先分析这句话产生的需求，
要解决的问题，通过编号查询信息。
要求使用的工具是C语言。
再看这些需求衍生出来的问题。
1. 编号是什么？身份证、学号、员工编号或者其他
2. 信息又应该涵盖哪些范畴？姓名字号，生辰八字
3. 输入编号的媒介是什么？键盘，语音，图像等等
再者，这些信息怎么来？由谁收集，由谁保存？又显示在哪里？
一个最简单的模型
a 信息都保存在文件里面，可以通过文件导入导出。
b 仅仅也只保存个人的姓名和编号。
c 输入的媒介是键盘，输出的是屏幕
再看使用C语言作为开发工具
解决a 需要用到文件读写。
解决b 需要用到一个简单的结构体 包含姓名和编号两个字符串
解决c 需要标准的输入输出接口
但是除此之外，还有一个问题，怎么查询?
查询的数据是在文件里还是在内存里？
如果为文件里，借用解决a的方式就可以搞定。
如果在内存里，那么批量数据在内存里的存储，最好还是有一个可靠的数据结构来组织起来。这个简单模型里，哈希表就满足了需求。或者简单一点，如果数据量足够小，一个足够大的结构体数组也是可以的。
定义一个结构体 其中编号作为其结构体的一个成员，然后输入编号作为索引，查找到编号相同的那个成员 ，把成员信息打印出来就可以了
定义一个结构体，结构体包括编号，姓名，性别等个人信息， 把结构体编号拿出来与输入编号对比，对比成功之后输出结构体其他信息。
你的结构体里面可以包含编号和其他的信息，用循环遍历结构体数组，用每个元素的编号和你输入的编号比较，若相等，输出该元素的其他信息
数组操作你会吧？ 把所有人的信息都存入一个字符串数组里面，
像这样:char person[num][len]={"name sex class","name2 sex2 class",....};
你要取一个字符串的时候就 puts(a[i]); 就行了。i=0，就取出第一个字符串，即第一个人的信息
1、写一个结构体数组用来记录信息
这里我写了一个可以存储一个人的姓名、电话、邮箱的结构体。
struct note{char name[100];char phone[100];char mail[100];}people[1000];2、用文件储存更加方便
p=fopen("list.txt","r"); if(p==NULL) { fclose(p); p=fopen("list.txt","w"); fclose(p); }3、写一个简单的界面(可以用死循环)
while(1) { n=0; p=fopen("list.txt","r"); while(fscanf(p,"%s%s%s",people[n].name,people[n].phone,people[n].mail)!=EOF) n++; fclose(p); ///--------一次循环更新一次数据4、写一个简单的查找程序
int k; cout<<"输入1读取,输入2输入"<
>k; if(k==1) { cout<<"输入信息"<
>s; bool ok=0; for(i=0;i
='0'&&s[i]<='9') ok=1; //自动识别输入的是姓名还是电话号码 if(ok==0) { //cout<<"通过姓名找到联系人"<
<endl; system("pause"); bool you="1;" for(i="0;i<n;i++)" if(strcmp(s,people[i].name)="=0)" { cout<<"姓名"<<people[i].name<<endl; cout<<"电话号码"<<people[i].phone<<endl; cout<<"邮箱"<<people[i].mail<<endl; } if(you="=0)" cout<<"没有通过姓名找到联系人"<<endl; if(ok="=1)" cout<<"通过电话找联系人"<<endl; if(strcmp(s,people[i].phone)="=0)" cout<<"没有通过电话找到联系人"<<endl; }5、添加信息的代码
if(k==2) { p1=fopen("list.txt","a+"); char ss[1000]; cout<<"请输入姓名"<
>ss; fprintf(p1,"%s\n",ss); cout<<"请输入电话"<
>ss; fprintf(p1,"%s\n",ss); cout<<"请输入邮箱"<
>ss; fprintf(p1,"%s\n",ss); fclose(p1); } }最终的程序
#include
#include
#include
#include
#include
#include
#include
using namespace std;FILE *p,*p1;struct note{char name[100];char phone[100];char mail[100];}people[1000];int main() { int n=0,i,j; p=fopen("list.txt","r"); if(p==NULL) { fclose(p); p=fopen("list.txt","w"); fclose(p); } while(1) { n=0; p=fopen("list.txt","r"); while(fscanf(p,"%s%s%s",people[n].name,people[n].phone,people[n].mail)!=EOF) n++; fclose(p); ///--------------- int k; cout<<"输入1读取,输入2输入"<
>k; if(k==1) { cout<<"输入信息"<
>s; bool ok=0; for(i=0;i
='0'&&s[i]<='9') ok=1; if(ok==0) { //cout<<"通过姓名找到联系人"<
<endl; system("pause"); bool you="1;" for(i="0;i<n;i++)" if(strcmp(s,people[i].name)="=0)" { cout<<"姓名"<<people[i].name<<endl; cout<<"电话号码"<<people[i].phone<<endl; cout<<"邮箱"<<people[i].mail<<endl; } if(you="=0)" cout<<"没有通过姓名找到联系人"<<endl; if(ok="=1)" cout<<"通过电话找联系人"<<endl; if(strcmp(s,people[i].phone)="=0)" cout<<"没有通过电话找到联系人"<<endl; if(k="=2)" p1="fopen("list.txt","a+");" char ss[1000]; cout<<"请输入姓名"<
>ss; fprintf(p1,"%s\n",ss); cout<<"请输入电话"<
>ss; fprintf(p1,"%s\n",ss); cout<<"请输入邮箱"<
>ss; fprintf(p1,"%s\n",ss); fclose(p1); } } return 0; }
VB语言编程问题
简单一点的就是
定义两个数组，一个存姓名name（），一个存号码Number(),姓名和号码一一对应。
然后写个数组的查询函数Query（AName()，QName）as integer
返回名字数组的索引值，无改名字则为-1，假设返回的值为i（i>=0),则对应的号码为Number(i)
查询函数最简单的就是用一个for循环，逐个查询，找到则返回i，exit for。否则返回-1
.。
复杂一些则可以使用哈希表，这样查询速度快，就是要定义好数据结构。
以上方法仅供参考。
用VB链接数据库嘛，方便。
比如说，张三的电话是：1234567，李四的是：1123456,
“画”出三个工具：
Private Sub Command1_Click()
Dim a As String
Select Case t1
Case "张三"
t2 = 123456
Case "李四"
t2 = 112345
End Select
End Sub
哈希查找法中解决冲突问题的常用方法是除留余数法
除留余数法： 若已知整个哈希表的最大长度 m，可以取一个不大于 m 的数 p，然后对该关键字 key 做取余运算，即： H（key）= key % p 。 在此方法中，对于 p 的取值非常重要，由经验得知 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数。
在初中的数学课本中学习过函数的相关知识，给定一个 x，通过一个数学公式，只需要将 x 的值带入公式就可以求出一个新的值 y。
哈希表的建立同函数类似，把函数中的 x 用查找记录时使用的关键字来代替，然后将关键字的值带入一个精心设计的公式中，就可以求出一个值，用这个值来表示记录存储的哈希地址。即：
数据的哈希地址=f（关键字的值）
哈希地址只是表示在查找表中的存储位置，而不是实际的物理存储位置。f（）是一个函数，通过这个函数可以快速求出该关键字对应的的数据的哈希地址，称之为“哈希函数”。
假如想查找李四的电话号码，对于一般的查找方式最先想到的是从头遍历，一一比较。而如果将电话簿构建成一张哈希表，可以直接通过名字“李四”直接找到电话号码在表中的位置。在构建哈希表时，最重要的是哈希函数的设计。例如设计电话簿案例中的哈希函数为：每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。这时会发现，张三和赵六两个关键字的姓的首字母都是 Z ，最终求出的电话号码的存储位置相同，这种现象称为冲突。在设计哈希函数时，要尽量地避免冲突现象的发生。
数据结构哈希表，求大神，急急急
要是有钱就好使了。
#include
#include
#include
#define MAXSIZE 20
#define MAX_SIZE 20 //人名的最大长度
#define HASHSIZE 60 //定义表长
#define SUCCESS 1
#define UNSUCCESS -1
typedef int Status; //为现有类型添加一个同义字
typedef char NA[MAX_SIZE]; // typedef 掩饰数组类型
typedef struct //记录
{
NA name;
NA xuehao; //关键字
NA tel;
}Stu; //查找表中记录类型
typedef struct //建立哈希表
{
Stu *elem[HASHSIZE]; //数据元素存储基址
int cou; //当前数据元素个数
int siz; //当前容量
}HashTable;
Status eq(NA x,NA y)
{
if(strcmp(x,y)==0)
return SUCCESS;
else return UNSUCCESS;
}
Status NUM_BER; //记录的个数 全局变量
Status NUM_BER1;
void Create(Stu* a) //创建新的通讯录
{
system("CLS"); //调用DOS命令CLS能够清屏
int i;
FILE *fp1,*fp2;
if((fp1=fopen("record.txt","r"))!=NULL) //打开文件
{
fclose(fp1); //关闭文件
}
else
{
fp2=fopen("record.txt","w"); //如果不存在,就创建一个record.txt
fclose(fp2);
}
printf("\n输入要添加的个数：\n");
scanf("%d",&NUM_BER);
for(i=0;i
<num_ber;i++)
{
printf("请输入第%d个记录的姓名:\n",i+1);
scanf("%s",a[i].name);
printf("请输入%d个记录的学号:\n",i+1);
scanf("%s",a[i].xuehao);
printf("请输入第%d个记录的电话号码:\n",i+1);
scanf("%s",a[i].tel);
}
getchar();
printf("添加成功!!!\n");
}
void getin(Stu * a) //录入通讯录的内容，传入一个record的指针，然后针对这个指针指向的内存记录进行操作
{int i;
system("cls"); //调用DOS命令CLS能够清屏
printf("输入要添加的个数：\n");
scanf("%d",&NUM_BER);
for(i=0;i
<num_ber;i++)
{
printf("请输入第%d个记录的姓名:\n",i+1);
scanf("%s",a[i].name);
printf("请输入%d个记录的学号:\n",i+1);
scanf("%s",a[i].xuehao);
printf("请输入第%d个记录的电话号码:\n",i+1);
scanf("%s",a[i].tel);
}
}
void output(Stu* a) //显示输入的用户信息
{int i;
system("cls");
printf(" \n姓名\t学号\t\t电话号码");
for( i=0;i
<num_ber;i++)
printf("\n%s\t%s\t\t%s",a[i].name,a[i].xuehao,a[i].tel);
}
int Hash(NA name)
{
int i,m;
i = 1;
m=(int)name[0];//强制转化成数字
while(name[i]!='\0')
{
m+=(int)name[i];
i++;
}
m=m%HASHSIZE;
return m;
}
Status collision(int p,int c) //冲突处理函数，采用二次探测法解决冲突 //二次探测法处理冲突
{
int i,q;
i=c/2+1;
while(i
<hashsize)
{
if(c%2==0)
{
c++;
q=(p+i*i)%HASHSIZE;
if(q>=0) return q;
else i=c/2+1;
}
else
{
q=(p-i*i)%HASHSIZE;
c++;
if(q>=0) return q;
else i=c/2+1;
}
}
return UNSUCCESS;
}
void CreateHash(HashTable* H,Stu* a) //建表，以人的姓名为关键字，建立相应的哈希表
{ int i,p=-1,c,pp;
system("cls");//若哈希地址冲突，进行冲突处理
for(i=0;i
<num_ber+num_ber1;i++)
{
c=0;
p=Hash(a[i].name);
pp=p;
while(H->elem[pp]!=NULL)
{
pp=collision(p,c); //若哈希地址冲突，进行冲突处理
if(pp<0)
{
printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出
continue; //无法解决冲突，跳入下一循环
}
}
H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入
H->cou++;
printf("第%d个记录冲突次数为%d。\n",i+1,c);
}
printf("\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->cou);
}
void SearchHash(HashTable* H,int c) //在通讯录里查找姓名关键字，c用来记录冲突次数，若查找成功，显示信息
{
int p,pp;NA NAME;
system("cls");
printf("\n请输入要查找记录的姓名：\n");
scanf("%s",NAME);
p=Hash(NAME);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(NAME,H->elem[pp]->name)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(NAME,H->elem[pp]->name)==1)
{
printf("\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c);
printf("姓名：%s\n学号：%s\n电话号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
}
else printf("\n此人不存在，查找不成功!\n");
}
void Modify(HashTable* H,int c) //在通讯录里修改某人信息
{
int p,pp;NA NAME;
system("cls");
printf("\n请输入要修改记录的姓名：\n");
scanf("%s",NAME);
p=Hash(NAME);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(NAME,H->elem[pp]->tel)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(NAME,H->elem[pp]->tel)==1)
{
printf("\n以下是您需要修改的信息：");
printf("姓名：%s\n学号：%s\n电话号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
(H->elem)[pp]->tel[0]='\0';
printf("请输入修改后记录的姓名:\n");
scanf("%s",H->elem[pp]->name);
printf("请输入修改后记录的学号:\n");
scanf("%s",H->elem[pp]->xuehao);
printf("请输入修改后记录的电话号码:\n");
scanf("%s",H->elem[pp]->tel);
printf("修改成功!");
}
else
printf("\n此人不存在，修改不成功!\n");
}
void Delete(HashTable* H,int c) //在通讯录里查找姓名关键字，若查找成功，显示信息然后删除
{
int m,p,pp;NA str;
m=0;
system("cls");
printf("\n请输入要删除记录的姓名：\n");
m++;
scanf("%s",str);
p=Hash(str);
pp=p;
while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))
pp=collision(p,c);
if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1)
{
printf("\n以下是您需要要删除的信息：\n\n",c);
printf("姓名：%s\n学号：%s\n电话号码：%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel);
(H->elem)[pp]->name[0]='\0';
printf("删除成功!!!");
}
else
printf("\n此人不存在，删除不成功!\n");
}
void Save(HashTable * H) //将记录保存到指定文件
{
system("CLS");
int i;
FILE* fp;
if((fp=fopen("record.txt","w"))!=NULL)
{
fprintf(fp,"==================== 班级通讯录 ===================\n");
for(i=0;i
<hashsize;i++)
{
if((H->elem)[i]!='\0')
{
fprintf(fp,"学生姓名:%s\n",H->elem[i]->name);
fprintf(fp,"学生学号:%s\n",H->elem[i]->xuehao);
fprintf(fp,"学生电话号码:%s\n",H->elem[i]->tel);
fprintf(fp,"***********************************************\n");
}
}
fclose(fp);
printf("==================== 班级通讯录 ===================\n");
printf("\n\n恭喜你!!成功储存，你能在record.txt找到相应纪录\n");
system("pause");
}
else
{
printf("抱歉，保存记录失败！！");
system("pause");
}
}
int main()
{
Stu a[MAXSIZE];
int c,flag=1,i=0;
HashTable *H;
H=(HashTable*)malloc(sizeof(HashTable));
for(i=0;i
<hashsize;i++)
{
H->elem[i]=NULL;
H->siz=HASHSIZE;
H->cou=0;
}
while (1)
{ int num;
printf("\n");
printf("\n***************************班级通讯录****************************");
printf("\n* 【1】. 创建用户信息 *");
printf("\n* 【2】. 添加用户信息 *");
printf("\n* 【3】. 显示所有用户信息 *");
printf("\n* 【4】. 以姓名建立哈希表（二次探测法解决冲突）*");
printf("\n* 【5】. 查找用户信息 *");
printf("\n* 【6】. 删除用户信息 *");
printf("\n* 【7】. 修改用户信息 *");
printf("\n* 【8】. 保存 *");
printf("\n* 【9】. 退出程序 *");
printf("\n*****************************************************************");
printf("\n");
printf("\n* 温馨提示： *");
printf("\n* 进行4、5、6操作前 请先输出3 *");
printf("\n*****************************************************************");
printf("\n请输入一个任务选项>>>");
printf("\n");
scanf("%d",&num);
switch(num)
{
case 1:Create(a) ;break;
case 2:getin(a); break;
case 3:output(a); break;
case 4:CreateHash(H,a); break;
case 5:c=0;SearchHash(H,c); break;
case 6:c=0;Delete(H,c); break;
case 7:c=0;Modify(H,c); break;
case 8:Save(H); break;
case 9:return 0; break;
default:
printf("输入错误，请重新输入!");
printf("\n");
}
}
system("pause");
return 0;
}
</hashsize;i++)
</hashsize;i++)
</num_ber+num_ber1;i++)
</hashsize)
</num_ber;i++)
</num_ber;i++)
</num_ber;i++)