数据结构课程设计约瑟夫环(2)

四、详细设计

#include

#include //time用到的头文件 #include //随机数用到的头文件

#include //toascii()用到的头文件用于将拼音的ASCII码的值作为关键字

#include //字符类的头文件

#define HASH_LEN 30 //哈希表的长度 #define P 27 //小于哈希表长度的P用于做除数 #define NAME_LEN 30 //姓名表的长度 typedef struct //姓名表 {

char *py; //名字的拼音

int m; //拼音所对应的 ASCII总和 }NAME;

NAME NameTable[HASH_LEN]; //全局定义姓名表 typedef struct //哈希表 {

char *py; //名字的拼音

int m; //拼音所对应的ASCII总和 int si; //查找长度 }HASH;

HASH HashTable[HASH_LEN]; //全局定义哈希表 int d[30] ,i,j; //全局定义随机数,循环用的i、j void InitNameTable() //姓名表的初始化 {

printf(\请输入30个同学的姓名\\n\); for (int i = 0; i < 30; i++) {

char name[20];

scanf_s(\, name, 20);

NameTable[i].py = new char[20]; strcpy(NameTable[i].py, name); }

for (int i = 0; i

int s = 0;

char *p = NameTable[i].py;

for (j = 0; *(p + j) != '\\0'; j++)

s += toascii(*(p + j));//将拼音中每个字母的ASCII码相加 NameTable[i].m = s; }

printf(\姓名表生成成功\); system(\); system(\); }

void CreateHashTable() //建立哈希表 {

for (i = 0; i

HashTable[i].py = \; HashTable[i].m = 0; HashTable[i].si = 0; }

for (i = 0; i

int sum = 1, j = 0;

int adr = (NameTable[i].m) % P; //除留余数法 H(key)=key MOD p,p<=m 此时用拼音的ASCII码总值作为关键字

if (HashTable[adr].si == 0) //如果不冲突，将姓名表赋值给哈希表 {

HashTable[adr].m = NameTable[i].m; HashTable[adr].py = NameTable[i].py; HashTable[adr].si = 1; }

else //如果冲突 {

while (HashTable[adr].si != 0) {

adr = (adr + d[j++]) % HASH_LEN; //伪随机探测再散列法处理冲突

sum = sum + 1; //查找次数加1 }

HashTable[adr].m = NameTable[i].m; //将姓名表复制给哈希表对应的位置上

HashTable[adr].py = NameTable[i].py; HashTable[adr].si = sum; } } }

void DisplayNameTable() //显示姓名表 {

printf(\地址 \\t\\t 姓名 \\t\\t 关键字\\n\); for (i = 0; i

printf(\, i, NameTable[i].py, NameTable[i].m); }

void DisplayHashTable() // 显示哈希表 {

float asl = 0.0;

printf(\地址 \\t\\t 姓名 \\t\\t 关键字 \\t 搜索长度\\n\); //显示的格式

for (i = 0; i

printf(\, i, HashTable[i].py, HashTable[i].m, HashTable[i].si); asl += HashTable[i].si; }

asl /= NAME_LEN; //求得ASL

printf(\平均查找长度：ASL(%d)=%f \\n\, NAME_LEN, asl); }

void FindName() //查找 {

char name[20] = { 0 }; int s = 0, sum = 1, adr;

printf(\请输入想要查找的姓名的拼音:\); scanf_s(\, name,20);

for (j = 0; name[j]!=’\\0’; j++) //求出姓名的拼音所对应的ASCII作为关键字

s += toascii(name[j]);

adr = s%P; //除留余数法 j = 0;

if (HashTable[adr].m == s&&!strcmp(HashTable[adr].py, name)) //分3种情况进行判断，并输出超找结果

printf(\姓名:%s 关键字:%d 查找长度为: 1\\n\, HashTable[adr].py, s);

else if (HashTable[adr].m == 0) printf(\没有想要查找的人!\\n\); else {

while (1) {

adr = (adr + d[j++]) % HASH_LEN; //伪随机探测再散列法处理冲突

sum = sum + 1; //查找次数加1 if (HashTable[adr].m == 0) {

printf(\没有想要查找的人!\\n\);

break; }

if (HashTable[adr].m == s&&!strcmp(HashTable[adr].py, name)) {

printf(\姓名:%s 关键字:%d 查找长度为:%d\\n\, HashTable[adr].py, s, sum); break; } } } }

void showtable() {

puts(\*********\);

puts(\*********\);

puts(\哈希表设计-----------------------------*\);

puts(\*********\);

puts(\*********\); }

void show() {

puts(\菜单栏------------------------------*\); puts(\显示姓名表\); puts(\显示哈希表\); puts(\查找\);

puts(\退出 \);

puts(\------*\); }

int main() //主函数 { int a;

srand((int)time(0));//表示以当前时间对应的int值为随机序列起点，这样每次运行程序，由于起点不同才可以得到不同的随机数为位随机数法再排列提供随机数

for (i = 0; i<30; i++)//用随机函数求得伪随机数列d[i]（在1到30之间） d[i] = 1 + (int)(HASH_LEN*rand() / (RAND_MAX + 1.0)); showtable(); InitNameTable();

CreateHashTable(); start: showtable(); show(); restart:

printf(\请选择:\); scanf_s(\, &a);

switch (a) //根据选择进行判断，直到选择退出时才可以退出 {

case 1:

DisplayNameTable(); break; case 2:

DisplayHashTable(); break; case 3:

FindName(); break; case 4:

exit(0); break; default:

printf(\请输入正确的选择!\\n\); goto restart; }

printf(\执行成功\\n\); system(\); system(\); goto start; }

五、测试分析

测试数据：随机输入的30个人的姓名拼音

测试过程：输入30个人的姓名拼音，观察输出结果，并进行查找操作 测试结果：