需求分析
1.1问题描述
随着社会发展，银行作为一个金融机构，在现代人们的生活中扮演着极其重要的角色。为生活节凑飞快的现代人提供快速、便捷、高效的理财服务。伴随着电脑技术的发展，各大银行的储蓄管理系统也随之出现在这一舞台上。人们的生活水平不断提高，会将一定的收入用于活期存储，因其储户开户、销户、存入、支出活动频繁的需求特点，本课程设计使用哈希表进行银行活期储蓄账目管理系统的模拟，实现基本的数据存储和处理 *** 作。活期储蓄帐目管理，活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1)能比较迅速地找到储户的帐户，以实现存款、取款记账；2)能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。
1.2模块组成
伪UI模块：伪界面，为了使界面美观设计的伪UI
主程序模块：初始化工作及功能选择和调用
开户模块：经过人机验证后能新建账户。
销户模块：查找到目的账户，再验证密码后对其销户。
查询模块：能够通过账号查找，迅速的找到要查找的账户，并显示账户余额。
存取模块：在迅速地查找到目的账户后，对账户余额进行修改。
测试模块：超级管理员能够模拟输入数据，并输出全部数据
1.3 功能要求
根据1.2模块组成该系统具有以下五个部分的功能：
开户功能：通过人机验证能够从键盘输入用户账户新建账户，并赋予初始开户金额0元。
销户功能：查找到目的账户，若余额为0则对其销户，否则提示先取钱再销户。
查询功能：能够通过账号查找，迅速的找到要查找的账户，并显示账户余额。
存取功能：迅速地查找到目的账户，验证密码后对账户进行存钱取钱 *** 作。
测试功能：能够通过管理员预设密码进行，模拟输入，全部输出 *** 作，以方便测试。
2 概要设计
2.1 设计思路
每一个用户看作一个基本单位，将系统抽象只包括账号和金额，密码、日期等不做存储和处理。为了便于后期维护与找错，使结构更加明了，采用数据结构型函数与功能实现型函数分离结构，存储数据结构是哈希表。
图1 数据结构型函数和功能实现型函数
2.2 存储结构设计
数据结构存储采用的是哈希表，账号存储为字符串，常用字符串哈希函数有 BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash、ELFHash等，本程序采用 BKDRHash对字符串进行散列，得到一个整数的hash值，根据得到的hash值选择一个槽位置，解决冲突方法为链接法，如图3哈希表插入过程。其中零号元素位用于存储哈希表主槽位容积，非所有元素容积，如图2哈希表存储模型。
图2 哈希表存储模型
图3 哈希表插入过程
2.3 算法设计说明
下面将从函数调用关系和对部分算法设计说明两个方面进行
2.3.1 函数调用关系
图4 函数调用关系
2.3.2 算法设计说明
哈希表初始化算法思想是，为哈希表主槽申请空间并置为0，第0个元素的值域用于存放哈希表主槽长度。
判断哈希值所在哈希表槽位的思想是，将字符串用BKDR算法散列成一个整数哈希值，用该整数哈希值对长度取余加1一定落在哈希表主槽槽位数组内，其中加1是为了防止落在0位，因为0位用于存储长度。
哈希表插入元素的思想是，结合图3，先求插入值的主槽，主槽存在该元素则直接更新值域，如果主槽不是该元素，则冲突处理，本程序用链接法，查看主槽冲突指针域，重复上述过程，即找主槽，然后遍历主槽冲突链，存在就更新，不存在就插入。
哈希表删除元素的思想与插入元素的思想较为类似，将对应插入改成删除。
哈希表搜索的思想是，先求要搜索值的哈希值，再利用判断哈希值所在哈希表槽位的算法找到该槽位，对比该槽位元素查看是否一致，一致则查找成功，不一样则看该槽位是否有冲突元素，有的话则对比该槽位元素是否一致，没有的话则不存在该元素，查找失败。
图5 哈希表查找流程图
返回全部数据元素个数的思想为，遍历主槽，如果主槽后面有冲突链则遍历冲突链。
打印全部元素的思想与返回全部元素思想类似，先主槽，并查看是否有冲突链。
3 详细设计
3.1 结构体定义
根据2.2存储结构设计，哈希表结构体的定义为：
typedef struct _htItem
{
struct _htItem *next;//冲突时下一个
char *key_string;//
uint fid;
int password;//卫星值
} htItem;
3.2 功能型函数
开户、销户等功能型函数较为简单，在此不做特别说明，利用随机数产生加减法进行人机验证，for循环可进行多次开户、销户 *** 作，尽可能体现严谨思维。
int funOpenAccount(htItem **ht)
{
//人机验证
int n,m,num1,num2,x;
long s;
char c;
srand((unsigned) time(NULL));//用时间做种子，每次产生的随机序列不同
num1=rand()%10+1;
num2=rand()%10+1;
x=rand()%3;
switch(x)
{
case 0:c='+';s=num1+num2;break;
case 1:c='-';s=num1-num2;break;
default:c='*';s=num1*num2;
}
printf("tt请先进行人机验ntt%d%c%d=",num1,c,num2);
scanf("%d",&n);
if(n==s)
m=1;
else
m=-1;
//printf("fun 开户 beginn");
while (m==1)
{
int iAccountAdd,iAccountAddSum;
printf("nnt请输入预开户账号总数nt本次开户总数：");
scanf("%d",&iAccountAddSum);
for(iAccountAdd=0; iAccountAdd { printf("ntt请输入预开户%d的8位数账号：n",iAccountAdd+1); char *sp; sp=(char *)malloc(ACCOUNT_NUM*sizeof(char)); int tempmoney=0; int temppassword,temppassword1; printf("tt预开户账号："); scanf("%s",sp); if (htGet(sp, ht)) { //检查账户是否存在 printf("tt该账户已存在!ntt------------------------------"); continue; //break; //return 0; } printf("tt请输入6位数密码："); scanf("%d",&temppassword); printf("tt请再次确认密码："); scanf("%d",&temppassword1); do{ if (temppassword==temppassword1) { htSet(sp, tempmoney, temppassword, ht); printf("tt开户完成!ntt------------------------------"); } else { printf("两次密码不匹配！请重新输入！n"); printf("tt请输入6位数密码："); scanf("%s",&temppassword); printf("请确认密码n"); scanf("%s",&temppassword1); } }while(0); continue; } return 0; } printf("tt验证失败!ntt------------------------------"); // printf("t系统所有开户信息为：n"); // print_hashTable(ht); // printf("fun 开户 endnnn"); return 0; } //销户 int funDelAccount(htItem **ht) { // printf("fun 销户 beginn"); int iAccountDel,iAccountDelSum; printf("nt请输入本次销户账号总数：nt销户总数："); scanf("%d",&iAccountDelSum); printf("nt友情提示，谨慎 *** 作！nn"); for(iAccountDel=0; iAccountDel { printf("ntt请输入预销户%d的账号：n",iAccountDel+1); char *sp; int temppassword; sp=(char *)malloc(ACCOUNT_NUM*sizeof(char)); int tempmoney; printf("tt预销户账号："); scanf("%s",sp); htItem *tmp; if (tmp = htGet(sp, ht)) { printf("tt请输入6位数密码："); scanf("%d",&temppassword); if ( temppassword==tmp->password ) { if(tmp->fid>0) { printf("tt用户 %s 的余额为￥%d ，请取出余额后再进行销户n", tmp->key_string, tmp->fid); continue; } else { htDel(sp, ht); free(sp); printf("tt销户成功！n"); continue; } } else { printf("tt密码不正确，请再次输入！n"); printf("tt请输入6位数密码："); scanf("%d",&temppassword); } if ( temppassword=tmp->password ) { if(tmp->fid>0) printf("tt用户 %s 的余额为￥%d ，请取出余额后再进行销户n", tmp->key_string, tmp->fid); else { htDel(sp, ht); free(sp); printf("tt销户成功！n"); } } else { printf("tt *** 作失败，请重试！n"); continue; } } else printf("tt没有此用户! 请确认信息重新 *** 作n"); printf("tt-----------------------------------------n"); } // printf("t系统所有开户信息为：n"); // print_hashTable(ht); // printf("fun 销户 endnnn"); return 0; } 其中存取函数利用哈希表特性，不是找到该元素直接更改卫星值值域，而是取出值域中的卫星值经过处理后，重新插入该元素，代码如下： scanf("%d",&moneyAD); htItem *tmp = htGet(spAD, ht); moneyAD = moneyAD + (tmp->fid); htSet(spAD, moneyAD, ht); 3.3 数据结构型函数 3.3.1 初始化函数 根据2.3.2哈希表初始化思想，初始化函数如下： //初始化HashTable void htInit(htItem **ht, uint length){ int i; for (i = 0; i { ht[i] = (htItem*)malloc(sizeof(htItem)); memset(ht[i], 0, sizeof(htItem));//用来对一段内存空间全部设置为某个字符 } ht[0]->fid = length;//第一个存长度 } 3.3.2 判断哈希值所在哈希表槽位 根据2.3.2判断哈希值所在哈希表槽位的思想，代码如下： // get the index of hash table 根据得到的hash值选择一个槽位置 uint htIndex(char *key, htItem **ht){ uint hashedKey = bkdrHash(key); uint length = (ht[0]->fid - 1); return (uint)hashedKey % length + 1; //char转整数哈希值再用哈希函数定位槽位 //0号位存长度，对长度取余加1，一定落在槽位内 } 其中bkdrHash(key)函数为： uint bkdrHash(char *key) { uint seed = 131; uint hash = 0; while (*key != 'n' && *key != 0) { //通常使用时，判别条件为*key != 0即可，此处的*key != 'n'是因程序需要 hash = hash * seed + (*key++); } return (hash & 0x7FFFFFFF); } 3.3.3 哈希表插入元素与删除元素 根据2.3.2哈希表插入元素与删除元素算法思想，以插入为例代码如下： uint htSet(char *key, uint fid, int password, htItem **ht){ uint i = htIndex(key, ht); htItem *item = ht[i]; while (item->next) { //已经存在的话则直接更新值 if (strcmp(key, item->next->key_string) == 0){ item->next->fid = fid; item->next->password = password; return 0; }else{ item = item->next; } } //处理冲突元素 item->next = (htItem*)malloc(sizeof(htItem)); item->next->fid = fid; item->next->password = password; item->next->key_string = key; item->next->next = NULL; return 0; } 3.3.4 哈希表查找元素 根据2.3.2哈希表查找元素思想，代码如下： //get hashTable elements 进行对应的hash值的搜索，如果找到则返回该节点 htItem* htGet(char *key, htItem **ht) { uint i = htIndex(key, ht); htItem *item = ht[i]->next; htItem *tmp = (htItem*)malloc(sizeof(htItem)); memset(tmp, 0, sizeof(htItem));// 内存空间初始化 while (item) { if (strcmp(key, item->key_string) == 0){ return item; tmp->fid = item->fid; tmp->key_string = item->key_string; return tmp;// 返回地址 } item = item->next; } return NULL; } 3.3.5 返回所有元素个数与打印全部元素 根据2.3.2哈希表计算所有元素思想和打印所有元素思想，以计算所有元素个数为例，代码如下： // get element number in the hashtable 所有元素总和个数 //遍历所有槽位和对应槽位冲突的元素 uint htLen(htItem **ht) { uint alength = ht[0]->fid; uint i, length = 0; for (i = 1; i < alength; i++) { if (ht[i]->next) length++; } return length; } 4 调试分析 4.1 测试数据 图6 测试 特意输入错误值使得验证失败后正确验证，体现人机验证的作用。依次进行开户销户功能，保留一个账号20191683，密码131452,存取功能存500元，显示余额为500，取款功能取200显，显示余额为300。经查询余额为300与前面相符。 利用测试模块，功能选择输入未在列表中展示的54321，超级管理员密码为54321，自动模拟输入120个数据，其中哈希表主槽位120，一定产生冲突，然后再功能选择输入未在列表中展示的12345，超级管理员密码为12345，展示所有元素，显示数据为120条，结果正确。 4.2 调试与分析 问题1 ：最开始申请内存为sp=(char *)malloc(sizeof(char)); 虽然达到可变空间的目的，但是考虑到不安全，实际申请1个char空间， 其他空间不一定没用，和char *p；直接用赋值是一样的错误，问题1应改为sp=(char *)malloc(ACCOUNT_NUM*sizeof(char));其中ACCOUNT_NUM可用define预设。 问题2：for{ scanf(sp); htSet(sp, tempmoney, item);}未申请空间，无论输入多少都是一个记录，结合问题1，因为没用申请空间，所以所有元素都覆盖在一个未知空间，问题2应在循环中加入申请空间。 问题3：do{scanf("%d", &funChoose); switch(funChoose){}；}while{}输入1个数字非法字符，显示非法输入，正确；输入1个字母，就死循环，通过询问别人，加个getchar();吸收字符，解决；发现输入1个字符串就会空出字符串长度个循环，问题3应为while(getchar() != 'n')。 问题4：uint fid; int password;//卫星值为了使哈希表数据域存储两个数据值密码password和余额fid，起初未声明空间，导致一直报错，最后检查，发现问题所在，修改代码。 时间复杂度为O(1)，其他调试问题因篇幅所限就不在此一一列出，多数错误产生的原因因为对C语言理解不够透彻。通过查阅书籍笔记和讨论都有所解决。 4.3 算法改进 算法中并未加入载荷因子，下一步改进可从数据结构方面，加入载荷因子，实现自动扩容，提高效率。程序用C语言编写，并未涉及对文件的 *** 作，所有存储均在内存进行，仅体现结构思想，下一步从C语言方面，可添加文件映射，提高实用性。 5小结 刚收到这个课题名称及课程要求时，在学过了线性表及后续课程第一想法就是利用线性表来做这个课题。但是考虑到线表在查找及插入删除的矛盾后，我认为这并不是一个非常完美的方案。最终在最后一节课学习哈希表之后，我决定用哈希表进行课题研究。利用BKDRHash对字符串进行散列，得到一个整数的hash值，尽可能的减少了冲突，发生冲突时，利用链表形式，减少了哈希再生，减小了查找时间复杂度。想法是这么个想法，但是实施起来并不是十分的顺利。通过查找资料并未发现利用哈希表进行此课题活期存储账目管理的研究方案，只有类似与此课题的其他方案，没有了先人探路，一切进行的都十分艰难。在现有要求基础上，还增加了类似于人机验证，密码验证等其他功能，一切都需要查找资料，书写代码后与整个程序适配进行调试，才能够顺利使用。可以说整个过程都不是十分的容易。但是通过整个课题的研究，重新学习了许多东西，留意到许多之前并不曾注意的地方。其中最主要的是掌握了数据存储多个记录的方法及声明，为后续学习记录多条记录值打下基础。整个调试过程中，因为头文件未声明数据域的空间及存储类型，导致程序一直大量报错。在修改错误的过程中逐渐了解并掌握各种错误类型。能够识别并修正各种常见错误，为后续代码工作打下基础。也从中体会到程序员书写代码的辛苦，对于某一错误需要修改大量的代码，并且需要足够细心及耐心的进行查错。另外一方面，对于if while ，do while等循环语句有了更深入的了解。之前只是纸上谈兵的讨论，其功能与作用如今实际使用起来与理想中的具有一定偏差，需要不断的尝试才能够掌握起作用。这也告诉我们，在学习数据结构这门课程时，对于各种各样的算法及语句需要实际 *** 作去探寻其真正意义的工作原理和作用。一味的靠他人讲解或电子教案的演示，无法真正的领悟其精髓，后续也就不能够正确的使用。 通过本次课程设计，最主要的是对哈希表有了更进一步的理解，哈希表是一个数据结构，哈希表本质上是个数组，只能说它的底层实现是用到了数组，简单点说，在数组的这个基础上再加工加工，变得更加有特色了，然后就自立门户，叫哈希表。一般来说啊，实现哈希表我们可以采用两种方法：数组+链表、数组+二叉树，无论哪个都是必须有数组啊，都是再数组的基础上取搞其他的，而且比如第一种数组+链表的形式，本质上是出现哈希冲突的一种解决办法，使用链表存放，所以综合起来叫做数组+链表的方式来实现一个哈希表，另外数组中一般就是存放的单一的数据，而哈希表中存放的是一个键值对，这是就是区别！哈希函数的设计很重要，一个好的哈希函数可以极大的提升性能。其中最重要的部分是如何散列，本设计是用已有技术调用BKDRHash字符串散列，采用hash = hash * seed + (*key++);有效地避免了冲突。具有高效性。 参考文献： [1]耿国华，张德同，周明全.数据结构—用C语言描述（第2版）[J].计算机教育,2015（7）. [2]严蔚敏,李冬梅,吴伟民.数据结构(C语言版)[J].计算机教育,2012(12):62. [3]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,殷建平,徐云,王刚,刘晓光,苏明,邹恒明,王宏志.算法导论(原书第3版)[J].计算机教育,2013(10):51. [4] wiki.《Hash table》. https://en.wikipedia.org/wiki/Hash_table.2019年5月20访问 [5]Mr.Wang.《HashMap 在 Java1.7 与 1.8 中的区别》. https://www.cnblogs.com/justlove/p/7624455.html.2019年5月20访问 [6]灵剑.《hash算法的数学原理是什么，如何保证尽可能少的碰撞？》. https://www.zhihu.com/question/20507188.2019年5月20访问 [7] ithuangqing. 《来吧！一文彻底搞定哈希表！》 来吧！一文彻底搞定哈希表！_庆哥Java的CSDN技术博客-CSDN博客. 欢迎分享，转载请注明来源：内存溢出
//———————part1——————————————
#include
微信扫一扫
支付宝扫一扫
评论列表（0条）