【導(dǎo)讀】程當(dāng)中起著承上啟下的作用，其重要性不言而喻。但是，目前許多銀行在具體的。下，而且無法達到理想的效果。本文針對上述問題，采用軟件工程的開發(fā)原理，軟件應(yīng)用、軟件維護等過程開發(fā)了一個銀行帳目管理系統(tǒng)。口令表、銀行系統(tǒng)的用戶信息表等數(shù)據(jù)表。解決了銀行系統(tǒng)中存在的數(shù)據(jù)安全性。、數(shù)據(jù)一致性以及系統(tǒng)運行速度等問題。取款機信息管理模塊：管理員管理查詢和維護、客戶查詢和取款等?？偭肯M統(tǒng)計、工作量負荷統(tǒng)計等功能。理的任務(wù)，提高賬目管理效率，使銀行的賬目管理工作系統(tǒng)化、規(guī)范化、自動化。各階段分工明確。經(jīng)過實踐證明，該劃分是合理的，極大得提高了本系統(tǒng)的實現(xiàn)?，F(xiàn)今，人們的金融意識、科技意識己經(jīng)有了很大的提高，

　　

【正文】 系統(tǒng)功能分析在系統(tǒng)開發(fā)的總體任務(wù)的基礎(chǔ)上完成。本系統(tǒng)實現(xiàn)的主要功能模塊如下 : （ 1） 帳戶管理 本模塊的功能在于管理員通過簡單的操作，可以實現(xiàn)銀行對賬戶管理一般功能。如：存款、取款、開戶、銷戶、修改信息、辦卡和掛失卡等等，內(nèi)容豐富 . （ 2） 取款機管理 本模塊的功能就是模擬 ATM 取款機的取款過程。具體實現(xiàn)的功能為：用戶輸 入取款機號、卡號、密碼，通過驗證后進入交易，用戶可以查看余額，取出現(xiàn)金。系統(tǒng)自動更新用戶賬號及卡號中的存款余額，并在用戶存取款信息中作記錄，在 ATM 機的存取款信息中作記錄。 （ 3） 用戶查詢 本模塊的功能就是使用戶查詢自己帳戶的信息。在用戶查詢之前，處于安全的考慮，要進行相應(yīng)的驗證，以用戶輸入的密碼和數(shù)據(jù)庫中的原始設(shè)置的密碼相匹配，能夠匹配一致的即可進入數(shù)據(jù)庫中查詢相應(yīng)的信息；匹配不成功的即會退出此模塊而進入主模塊界面，以防止使用者對數(shù)據(jù)庫的非法修改。 （ 4） 查詢統(tǒng)計 本模塊主要實現(xiàn)以下五項功能： ① 金牌用戶統(tǒng)計： 統(tǒng)計持卡消費頻率達到某一標(biāo)準(zhǔn)的用戶，如日平均消費次數(shù)超過一次的。 ② ATM 業(yè)務(wù)量統(tǒng)計： 統(tǒng)計每臺 ATM 機的刷卡次數(shù)，根據(jù)次數(shù)可以讓銀行根據(jù) ATM 地點的分布考慮如何合理安排。 ③ 異動查詢： 統(tǒng)計在短期內(nèi)某帳戶大進大出的情況，發(fā)現(xiàn)異常，則提供帳戶的監(jiān)管。 ④ 持卡總量消費統(tǒng)計： 統(tǒng)計某時段內(nèi)持卡消費的總次數(shù)的變化情況，可以畫出條形圖、餅形圖，提供宏觀的分析。 ⑤ 提供操作員的工作負荷統(tǒng)計，每個操作員的日工作量，以次確定操作員的 業(yè)績，進行考核。 算法及數(shù)據(jù)結(jié)構(gòu) 哈希查找 本文主要采用了 DES 加密算法和哈希算法， DES算法我們已經(jīng)在第二章作過詳細介紹，就不再贅述，我們在此只對哈希查找作詳細的介紹。 什么是哈希表 較主要的查找方法有順序、折半、二叉樹查找等，但是，這一類查找方法建立在“比較”的基礎(chǔ)上。在順序查找時，比較的結(jié)果為“ =”與“≠”兩種可能；在折半查找、二叉排序樹查找和 B樹查找時，比較的結(jié)果為“＜”、“ =”、“＞”三種可能。查找的效率依賴于查找過程中 所進行的比較次數(shù)。 理想的情況是希望不經(jīng)過任何比較，一次存取便能得到所查記錄，那就必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系 f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。因而在查找時，只要根據(jù)這個對應(yīng) f找到給定值 K 的像 f（ K）。若結(jié)構(gòu)中存在關(guān)鍵字和 K相等的記錄，則必定在 f（ K）的存儲位置上，由此，不需要進行比較便可直接取得所查記錄。我們稱這個對應(yīng)關(guān)系 f為哈希（ Hash）函數(shù)，按這個思想建立的表為哈希表。 （ 1） 哈希函數(shù)是一個映象，因此哈希函數(shù)的設(shè)定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值 都落在表長允許的范圍之內(nèi)即可。 （ 2） 對不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突。在一般情況下，沖突只能盡可能地少，而不能完全避免。因為，哈希函數(shù)是從關(guān)鍵字集合到地址集合的映象。通常，關(guān)鍵字集合比較大，它的元素包括所有可能的關(guān)鍵字，而地址集合的元素僅為哈希表中的地址值。因此，在一般情況下，哈希函數(shù)是一個壓縮映象，這就不可避免產(chǎn)生沖突。因此，在建造哈希表時不僅要設(shè)定一個“好”的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。 綜上所述，可如下描述哈希表：根據(jù)設(shè)定的哈希函數(shù) H（ key）和處理沖突的方法將一組關(guān)鍵字映 象到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲位置，這種表便稱為哈希表，這一映象過程稱為哈希造表或散列，所得存儲位置稱哈希地址或散列地址。 哈希函數(shù)的構(gòu)造方法 若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)哈希函數(shù)映象到地址集合中任何一個地址的概率是相等的，則成此類哈希函數(shù)為均勻的哈希函數(shù)。換句話說，就是使關(guān)鍵字經(jīng)過哈希函數(shù)得到一個“隨即的地址”，以便使一組關(guān)鍵字的哈希地址均勻分布在整個地址區(qū)間中，從而減少沖突。 常用的構(gòu)造哈希函數(shù)的方法有： （ 1） 直接定址法 取關(guān) 鍵字或關(guān)鍵字的某個線性函數(shù)值為哈希地址。即： H（ key） =key 或 H（ key） =a*key＋ b 其中， a和 b為常數(shù)（這種哈希函數(shù)叫做自身函數(shù)）。 由于直接定址所得地址集合和關(guān)鍵字集合的大小相同，因此，對于不同的關(guān)鍵字不會發(fā)生沖突。但實際中能使用這種哈希函數(shù)的情況很少。 （ 2） 數(shù)字分析法 假設(shè)關(guān)鍵字是以 r為基的數(shù)（如：以 10為基的十進制數(shù)），并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。 例如，有 80個記錄，其關(guān)鍵字為 8位十進制數(shù)。假設(shè)哈希表的表長為10010，則可取兩位十 進制數(shù)組成哈希地址。取哪兩位？原則是使得到的哈希地址盡量避免產(chǎn)生沖突，則需從分析這 80 個關(guān)鍵字著手。假設(shè)這 80個關(guān)鍵字中的一部分如下所列： ?? 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 5 4 1 5 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ?? ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 對關(guān)鍵字全體的分析中我們發(fā)現(xiàn)：第①②位都是“ 8 1”，第③位只可能取 3 或 4，第⑧位只可能取 5 或 7，因此這四位都不可取。由于中間的四位可看成是近乎隨機的，因此可取其中任意兩位，或取其中兩位與另外兩位的疊加求和后舍去進位作為哈希地址。 （ 3） 平方取中法 取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時不一定能知道關(guān)鍵字的全部情 況，取其中哪幾位也不一定合適，而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都有關(guān)，由此使隨機分布的關(guān)鍵字得到的哈希地址也是隨機的。取的位數(shù)由表長決定。 （ 4） 折疊法 將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進位）作為哈希地址，這種方法稱為折疊法。 （ 5） 除留余數(shù)法 取關(guān)鍵字被某個不大于哈希表長 m的數(shù) p 除后所得余數(shù)為哈希地址。即 H（ key） =key MOD p P≤ m 這是一種最簡單，也最常用的構(gòu)造哈希函數(shù)的方法。它不僅可以對關(guān)鍵字直接取模（ MOD），也可在折疊、平方取中等運算之后取模。 （ 6） 隨機數(shù)法 選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的哈希地址，即 H（ key）=random(key)，其中 random 為隨機函數(shù)。通常，當(dāng)關(guān)鍵字長度不等時采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。 實際工作中需視不同的情況采用不同的哈希函數(shù)。通常，考慮的因素有： （ 1） 計算哈希函數(shù)所需時間（包括硬件指令的因素）； （ 2） 關(guān)鍵字的長度； （ 3） 哈希表的大??； （ 4） 關(guān)鍵字的分布情況； （ 5） 記錄的查找頻率。 處理沖突的方法 “處理沖突”就是為該關(guān)鍵字的記錄找到另一個“空”的哈 希地址。通常用的處理沖突的方法有： （ 1） 開放定址法 Hi=（ H（ key）＋ di） MOD m i=1， 2，?， k （ k≤ m－ 1） 其中， H（ key）為哈希函數(shù)； m為表長； di為增量序列，可有下列三種取法： di=1， 2， 3，?， m－ 1，稱線性探測再散列； di=12，－ 12， 22，－ 22， 32，?，177。 k2，（ k≤ m/2），稱二次探測再散列； di=偽隨機序列，稱偽隨機探測再散列。 （ 2） 再哈希法 Hi=RHi（ key） i=1， 2，?， k RHi均是不的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時計算另一個 哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。這種方法不易產(chǎn)生“聚集”但增加了計算的時間。 （ 3） 鏈地址法 將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間 [0， m－ 1]上，則設(shè)立一個指針型向量 chainhash:ARRAY[0..m－ 1] OF pointer； 其每個分量的初始狀態(tài)都是空指針。凡哈希地址為 i 的記錄都插入到頭指針為 chainhash[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。 （ 4） 建立一個公共溢出區(qū) 這也是處 理沖突的一種方法。假設(shè)哈希函數(shù)的值域為 [0， m－ 1]，設(shè)向量hashtable（ 0: m－ 1）為基本表，每個分量存放一個記錄，另設(shè)立向量overtable[0:v]為溢出表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。 哈希表的查找及其分析 在哈希表上進行查找的過程和哈希造表的過程基本一致。給定 K值，根據(jù)造表時設(shè)定的哈希函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關(guān)鍵字，若和給定值相等，則查找成功；否則根據(jù)造表 時設(shè)定的處理沖突的方法找“下一地址”，直至哈希表中某個位置為“空”或者表中所填記錄的關(guān)鍵字等于給定值為止。 算法 為以開放定址等（除鏈地址法外）方法處理沖突的哈希表的查找過程（不考慮插入和刪除）。 例 已知上例中所示的一組關(guān)鍵字按哈希函數(shù) H（ key） =key MOD 13 和線性探測處理沖突構(gòu)造所的哈希表 a(0..15) 如圖 所示。 給定值 K=84 的查找過程為：首先求得哈希地址 H（ 84） =6，因 ??6a 不空且? ? 846 ??keya ,則 找第一次沖突處理后的地址 716)16(1 ??? M ODH ，而 ? ?7a 不空且 ? ? ?keya ，則找第二次沖突處理后的地址 816)26(2 ??? M ODH ， ??8a 不空且 ? ? ?keya ，則查找成功，返回記錄在表中序號 8。 給定值 K=38 的查找過程為：先求哈希地址 H（ 38） =12， ? ?12a 不空且? ? ?keya ，則找下一地址 1316)112(1 ??? M O DH ，由于 ??13a 是空記錄，則表明表中不存在關(guān)鍵字等于 38的記錄。 從哈希表的查找過程可見 ： 1）雖然哈希表在關(guān)鍵字與記錄的存儲位置之間建立了直接映象，但由于“沖突”的產(chǎn)生，使得哈希表的查找過程仍然是一個給定值和關(guān)鍵字進行比較的過程。因此，仍需以平均查找長度作為衡量哈希表的查找效率的量度。 2）查找過程中需和給定值進行比較的關(guān)鍵字的個數(shù)取決于下列三個因素：哈希函數(shù)，處理沖突的方法和哈息表 的裝填因子。 哈希函數(shù)的“好壞”首先影響出現(xiàn)沖突的頻繁程度。但是，對于“均勻的”哈希函數(shù)可以假定：不同的哈希函數(shù)對同一組隨機的關(guān)鍵字，產(chǎn)生沖突的可能性相同，因為一般情況下設(shè)定的哈希函數(shù)是均勻的，則可不考慮它對平均查找長度的影響。 對同樣一組關(guān)鍵字，設(shè)定相同的哈希函數(shù)，則不同的處理沖突的方法得到的哈希表不同，它們的平均查找長度也不同。如例 93和 94中的兩個哈希表，在記錄的查找概率相等的前提下，前者（鏈地址法）的平均查找長度為 )434261(121)12( ???????A SL 后者（線性探測再散列）的平均查找 長度為 )9433261(121)12( ????????A SL 容易看出，線性探測再散列在處理沖突的過程中易產(chǎn)生記錄的二次聚集，如即使得哈希地址不相同的記錄又產(chǎn)生了新的沖突；而鏈地址發(fā)處理沖突不會發(fā)生類似情況，因為哈希地址不同的記錄在不同的鏈表中。 在一般情況下，處理沖突方法相同的哈希表，起平均查找長度依賴于哈希表的裝填因子。 哈希表的裝填因子定義為 ? = 哈希表的長度表中填入的記錄數(shù) 標(biāo)志哈希表的裝滿程度。直觀地看， ? 越小，發(fā)生沖突的可能性就越小；反之， ? 越大，表中已添入的記錄越多，再記錄時，發(fā)生沖突的可能性就越大，則查找時，給定值需與之進行比較的關(guān)鍵字的個數(shù)也就越多。 可以證明： 線形探測再散列的哈希表查找成功的平均查找長度為 Snl ? 21 ( ???111 ) 隨機探測再散列，二次探測再散列和哈希表查找成功時的查找平均長度為 Snr ? ?1ln(1? ) 鏈地址法處理沖突的哈希表查找成功時的平均查找長度為 Snc ? 1 + 2? 由于哈希表在查找 不成功時所用比較次數(shù)也和給定值有關(guān)，則可以類似的定義哈希表查找不成功時的平均查找長度為：查找不成功時需和給定值進行比較的關(guān)鍵字個數(shù)的期望值。同樣可證明，不同的處理沖突方法構(gòu)成的哈希表查找不成功時的查找長度分別為： Unl ? 21