數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—家譜系統(tǒng)

1、一.前言1 項(xiàng)目簡(jiǎn)介 家譜（或稱族譜）是一種以表譜形式，記載一個(gè)以血緣關(guān)系為主體的家族世系繁衍和重要人物事跡的特殊圖書體裁。家譜是中國(guó)特有的文化遺產(chǎn)，是中華民族的三大文獻(xiàn)（國(guó)史，地志，族譜）之一，屬珍貴的人文資料，對(duì)于歷史學(xué)、民俗學(xué)、人口學(xué)、社會(huì)學(xué)和經(jīng)濟(jì)學(xué)的深入研究，均有其不可替代的獨(dú)特功能。2系統(tǒng)功能 本項(xiàng)目對(duì)家譜管理進(jìn)行簡(jiǎn)單的模擬，以實(shí)現(xiàn)查看祖先和子孫個(gè)人信息、插入家族成員、刪除家族成員等功能。本項(xiàng)目的實(shí)質(zhì)是完成對(duì)家譜成員信息的建立、查找、插入、修改、刪除等功能，可以首先定義家族成員的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來完成對(duì)數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。一

2、 需求分析1. 系統(tǒng)需求本系統(tǒng)是家譜管理系統(tǒng)，顧名思義，是用來管理家族資料的，要實(shí)現(xiàn)建立新家譜，查找家譜文件，增加家族成員，修改家族成員，刪除家族成員和查找家族成員等基本功能。家譜管理系統(tǒng)是給家族長(zhǎng)輩管理家族資料用的，對(duì)電腦的操作不一定熟悉，所以操作界面一定要友好，一定要方便，dos界面的操作一般比較枯燥，綜合各種原因，要用mfc實(shí)現(xiàn)可視化的界面。2. 環(huán)境需求硬件：acer aspire 4740g i5處理器 2g內(nèi)存 320g硬盤軟件：vs 2008二 總體設(shè)計(jì)3.1 總體設(shè)計(jì)框架刪除結(jié)點(diǎn)修改結(jié)點(diǎn)添加結(jié)點(diǎn)保存家譜讀取文件建立家譜程序入口配偶信息關(guān)系查詢基本查詢輸出家譜 圖1 系統(tǒng)總體設(shè)計(jì)

3、模塊結(jié)構(gòu)圖3.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 關(guān)于樹形的結(jié)構(gòu)：在樹形結(jié)構(gòu)的選擇上，根據(jù)實(shí)際中多子女的現(xiàn)象選擇一般樹，考慮到家譜中成員可能存在的不定成員數(shù)問題，拋棄了以數(shù)組為基礎(chǔ)的一般樹方案，決定用鏈表來實(shí)現(xiàn)。樹形結(jié)構(gòu)的外存保存。為了提高效率，樹形結(jié)構(gòu)在程序初始化時(shí)由外存文件一次讀入內(nèi)存，此后不管插入還是修改，刪除都不再對(duì)外存的樹結(jié)構(gòu)保存文件進(jìn)行操作，只在內(nèi)存中處理，程序退出時(shí)對(duì)外存樹結(jié)構(gòu)文件進(jìn)行一次更新。也就是說，不管在程序運(yùn)行中中對(duì)家譜結(jié)構(gòu)進(jìn)行多少種，多少次的操作，外存的樹結(jié)構(gòu)文件始終只會(huì)被程序訪問兩次。以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)，鏈表中的兩個(gè)鏈域分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)，它通過描述

4、每個(gè)結(jié)點(diǎn)的一個(gè)孩子和兄弟信息來反映結(jié)點(diǎn)之間的層次關(guān)系，其具體的結(jié)點(diǎn)結(jié)構(gòu)為：firstchilddatanextsibling其中，firstchild為指向該結(jié)點(diǎn)第一個(gè)孩子的指針，nextsibling為指向該結(jié)點(diǎn)下一個(gè)兄弟，elem是數(shù)據(jù)元素內(nèi)容，舉例如下：3.3 算法設(shè)計(jì)1、家譜的創(chuàng)建和結(jié)點(diǎn)的添加 家譜采用的樹的結(jié)構(gòu)，通過左孩子，右兄弟的方式變?yōu)槎鏄洌瑒?chuàng)建的過程實(shí)際上就是二叉樹的添加結(jié)點(diǎn)的過程，根據(jù)父親的名字添加在父親結(jié)點(diǎn)的左邊。代碼如下：家譜的創(chuàng)建familytree:familytree() t=null;/開始為空家譜 家譜結(jié)點(diǎn)的添加void familytree:add(pers

5、on parent, person addnode) /將addnode添加到parent作為parent的孩子結(jié)點(diǎn) int n=0; addnode-firstchild=addnode-nextsibling=null; /初始時(shí)firstchild同nextsibling都為空 addnode-parent=parent; if(parent=null) /如果父結(jié)點(diǎn)空 if(t=null) /如果根結(jié)點(diǎn)空 addnode-data.depth=n; t=addnode; /將addnode賦給根結(jié)點(diǎn) return; n=t-data.depth+1;/否則將原來的根結(jié)點(diǎn)成為新根結(jié)點(diǎn)的孩

6、子 t-data.depth=n; /并使原來根結(jié)點(diǎn)的depth值加1 addnode-firstchild=t; t-parent=addnode; t=addnode; return; strcpy(addnode-data.parentname,); n=parent-data.depth+1; addnode-data.depth=n;/將depth值加1 if(parent-firstchild=null) /如果parent無孩子，把a(bǔ)ddnode加入其firstchild parent-firstchild=addnode; else insert

7、sibling(parent-firstchild,addnode); /否則插入到相應(yīng)的兄弟結(jié)點(diǎn)中去 2、 家譜結(jié)點(diǎn)的修改家譜結(jié)點(diǎn)的修改就是將結(jié)點(diǎn)的指針傳入，更新數(shù)據(jù)就可完成，代碼如下：void familytree:modify(person &curnode,person newnode) /修改某個(gè)人的信息 strcpy(,); strcpy(curnode-data.birthplace,newnode-data.birthplace); strcpy(curnode-data.sex,newnode-data.se

8、x); strcpy(curnode-data.occupation,newnode-data.occupation); strcpy(cation,cation); strcpy(curnode-data.top_headship,newnode-data.top_headship); curnode-data.height=newnode-data.height; curnode-data.birthdate=newnode-data.birthdate; curnode-data.deathdate=newnode-data

9、.deathdate; 3、 家譜結(jié)點(diǎn)的刪除結(jié)點(diǎn)的刪除，如果該結(jié)點(diǎn)沒有子節(jié)點(diǎn)，則直接刪除該結(jié)點(diǎn)所有信息，如果結(jié)點(diǎn)有子節(jié)點(diǎn)，則不能刪除。void ccmy_dlg:ondelete()htreeitem pnode=m_ptreepage-m_showtree.getselecteditem();if(!pnode)messagebox(請(qǐng)選擇結(jié)點(diǎn)再刪除!);return;if(datatree.havechild(m_curnode)messagebox(該結(jié)點(diǎn)有孩子結(jié)點(diǎn)，不能直接刪除!);return;if(messagebox(確認(rèn)刪除?,警告,mb_iconwarning|mb_okca

10、ncel)!=1)return;datatree.deletenode(m_curnode);/刪除datatree中相應(yīng)的數(shù)據(jù)questionm_ptreepage-m_showtree.deleteitem(pnode);if(m_ptreepage-m_showtree.getcount()=0)/刪除后若樹為空getdlgitem(idc_generation)-setwindowtext(未選結(jié)點(diǎn));getdlgitem(idc_linealname)-setwindowtext();getdlgitem(idc_matename)-setwindowtext();getdlgite

11、m(idc_whosbrief)-setwindowtext(簡(jiǎn)介);getdlgitem(idc_information)-setwindowtext();bismemory=true;4、 家譜的存儲(chǔ)和讀取家譜信息的存儲(chǔ)是按先序遍歷的方式依次存入硬盤的，讀取的時(shí)候，將第一個(gè)結(jié)點(diǎn)的信息對(duì)應(yīng)根結(jié)點(diǎn)，后面依次根據(jù)父親的姓名使用插入函數(shù)完成家譜的重建，代碼如下：家譜的存儲(chǔ)void familytree:savefamilytree() /保存二叉樹到文件 fstream f(1.dat,ios:binary|ios:out);/以二進(jìn)制寫方式打開文件 if(!f) cerr文件打開失??！endl;

12、/如果不能打開，顯示出錯(cuò)信息 return;preordertraverse(f,t,savenode);/調(diào)用先序遍歷寫二叉樹信息到文件f.close();/關(guān)閉文件/person& t=familytree:getroot();/ 返回家譜的根結(jié)點(diǎn) /return t;家譜的重建（從文件讀取）void familytree:createfamilytree() destroyfamilytree();/刪除原來家譜樹結(jié)構(gòu) int n=0;/初始化數(shù)組下標(biāo)，用來看有幾多個(gè)數(shù)據(jù) fstream f(1.dat,ios:binary|ios:in);/以二進(jìn)制讀方式打開 if(!f) cerr文

13、件打開失?。ndl;/不能打開，顯示出錯(cuò)信息 return;f.seekg(0,ios:end);/指針移到文件尾 long posend=f.tellg();f.seekg(0,ios:beg);/指針移到文件頭 person parentt=new csnode;person tempmax_char_num;/ 定義讀取數(shù)據(jù)的數(shù)組 for(int i=0;imax_char_num;i+)tempi=new csnode; / 初始化一個(gè)地址值，且不能為空否則出錯(cuò)= if(posend=f.tellg() /記錄文件尾位置 f.tellg(= )/ cout這是一個(gè)空家譜！data),

14、sizeof(info); n+; newfamilytree(); t=temp0;t-firstchild=t-nextsibling=null;/將第一個(gè)賦給根結(jié)點(diǎn) t-parent = null;for(int j=1;jdata.parentname); if(parentt) tempj-firstchild=tempj-nextsibling=null; tempj-parent=parentt; if(parentt-firstchild) insertsibling(parentt-firstchild,tempj); else parentt-firstchild=temp

15、j; f.close();/關(guān)閉文件流 5、 家譜信息的遍歷主要使用遞歸的方式遍歷家譜樹，代碼入下：先序遍歷：void familytree:preordertraverse(fstream &f,person &t, void (_cdecl *visit)(fstream &f,person &t) /先序遍歷二叉樹，并執(zhí)行visit函數(shù) if(t) (*visit)(f,t); preordertraverse(f,t-firstchild,visit); preordertraverse(f,t-nextsibling,visit); 6、 家族成員的查找查找部分涉及的查找方法多樣，這

16、里用按姓名查找來代表，其他查找使用的算法思想是類似的，使用遞歸的方法，代碼如下：void familytree:findbyname(person& t,person& tname,char* name)/search the name in info from root t /查找姓名name的人，若在家譜中，用tname返回，否則tname為空，tname初始為空 if(t) if(strcmp(t-,name)=0) /用string庫的strcmp（）比較兩個(gè)字符串，若相等，則找到符合條件的 tname=t; else findbyname(t-firstchild,

17、tname,name); /對(duì)t的firstchild遞歸搜索 findbyname(t-nextsibling,tname,name); /對(duì)t的nextsibling遞歸搜索 三 程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)部分是算法設(shè)計(jì)的補(bǔ)充與完善，代碼會(huì)與算法設(shè)計(jì)有不同，而且實(shí)現(xiàn)了mfc界面顯示部分，最終工程的實(shí)現(xiàn)以程序的為主。注：代碼太長(zhǎng)不附在文檔上四 測(cè)試報(bào)告1. 初始化界面： 圖2 系統(tǒng)初始化界面效果圖2文件讀取保存模塊 2.1 新建家譜 新建家譜實(shí)際操作為創(chuàng)建該家譜第一代成員，即該樹的根結(jié)點(diǎn)。默認(rèn)創(chuàng)建男性，默認(rèn)創(chuàng)建當(dāng)前結(jié)點(diǎn)的孩子結(jié)點(diǎn)，第一代不能創(chuàng)建兄弟結(jié)點(diǎn)，按取消操作，退出創(chuàng)建此家譜 圖3 新建家譜界面設(shè)

18、計(jì)效果圖2.2 打開文件（1） 按打開按鍵，彈出文件窗口，默認(rèn)打開txt格式文件圖4 打開載入文件界面設(shè)計(jì)效果圖（2） 打開文件后，操作窗口標(biāo)題欄會(huì)顯示該文件的文件名，并顯示本家譜的信息 圖5 打開文件信息效果圖2.3 保存文件按保存按鍵，直接保存信息到文件，按另存為按鍵，彈出另存為窗口，可以選擇保存路徑保存家譜文件。 圖6 保存文件信息頁面效果圖3. 操作模塊3.1創(chuàng)建新結(jié)點(diǎn) 點(diǎn)擊已經(jīng)存在的一個(gè)結(jié)點(diǎn)，點(diǎn)擊創(chuàng)建新結(jié)點(diǎn)按鈕，表示在當(dāng)前結(jié)點(diǎn)下創(chuàng)建子節(jié)點(diǎn)或者兄弟結(jié)點(diǎn)，左邊顯示編輯框，輸入名字信息和配偶名字信息，可以選擇性別，可以選擇所創(chuàng)建新結(jié)點(diǎn)是當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)或是兄弟結(jié)點(diǎn)。 圖7 創(chuàng)建結(jié)點(diǎn)頁面效果

19、圖3.2 修改結(jié)點(diǎn)點(diǎn)擊要修改的結(jié)點(diǎn)，按修改結(jié)點(diǎn)按鈕，左邊顯示編輯框，可以修改名字信息和配偶信息 圖8 修改結(jié)點(diǎn)頁面設(shè)計(jì)效果圖3.3 刪除結(jié)點(diǎn)（1） 刪除子節(jié)點(diǎn)。選擇要?jiǎng)h除的子節(jié)點(diǎn)，按刪除結(jié)點(diǎn)按鈕，彈出警告窗口，詢問是否確認(rèn)刪除結(jié)點(diǎn)，按確定刪除結(jié)點(diǎn) 圖9 刪除子節(jié)點(diǎn)頁面效果圖（2） 刪除有子節(jié)點(diǎn)的父節(jié)點(diǎn)，會(huì)彈出警告窗口，說明有子節(jié)點(diǎn)，不能刪除該結(jié)點(diǎn) 圖10 刪除父節(jié)點(diǎn)頁面效果圖4. 查找4.1按照姓名信息關(guān)鍵字查找（1） 不區(qū)分大小寫 圖11 按照名字信息不分大小寫查找頁面效果圖（2） 區(qū)分大小寫 圖12 按照姓名信息區(qū)分大小寫查找頁面效果圖4.2 按照配偶名字信息關(guān)鍵字查找圖13 按照配偶姓名

20、信息查找頁面效果圖五 目標(biāo)完成總結(jié)1. 完成了新家譜的創(chuàng)建，由根結(jié)點(diǎn)開始創(chuàng)建新的家譜樹2. 完成了家譜文件的讀取，可以打開指定路徑的文件并在系統(tǒng)中顯示該家譜信息3. 完成了家譜文件的保存，可以把新建或者修改的家譜文件保存到指定的路徑4. 完成了家譜樹中新結(jié)點(diǎn)的創(chuàng)建，可以創(chuàng)建原有結(jié)點(diǎn)的兄弟結(jié)點(diǎn)或者子結(jié)點(diǎn)，根節(jié)點(diǎn)只能創(chuàng)建其子結(jié)點(diǎn)5. 完成了家譜樹中任意結(jié)點(diǎn)的修改功能，可以修改結(jié)點(diǎn)的信息和其配偶信息6. 完成了家譜樹中任意子結(jié)點(diǎn)的刪除功能，有子結(jié)點(diǎn)的父節(jié)點(diǎn)無法直接刪除7. 完成了家譜樹中結(jié)點(diǎn)的查找功能，可以按照姓名信息區(qū)分大小寫或者不分大小寫查找，也可以按照配偶信息查找六 遇到的問題和解決方案1.

21、需要設(shè)計(jì)一個(gè)簡(jiǎn)單易用的系統(tǒng)，方便沒有計(jì)算機(jī)技術(shù)的管理人員使用，普通的dos界面就無法滿足此要求了，所以就要采取編寫可視化的解決方案。2. 沒有學(xué)過可視化編程的相關(guān)技能，要從零開始學(xué)習(xí)此門課程，通過購買相關(guān)書籍和上網(wǎng)查找資料解決編程過程中遇到的問題。3. 測(cè)試階段總會(huì)出現(xiàn)這樣那樣的問題，這時(shí)候就需要很多的耐心，并且要細(xì)心的處理每個(gè)錯(cuò)誤。七 尚未解決的問題和應(yīng)對(duì)策略1. 在刪除結(jié)點(diǎn)功能上，只能刪除子結(jié)點(diǎn)，不能刪除擁有子結(jié)點(diǎn)的父結(jié)點(diǎn)，要解決這個(gè)尚未解決的問題，需要在程序上做修改，在樹形結(jié)構(gòu)上做修改。但是由于完成系統(tǒng)之后，還沒寫報(bào)告，由于時(shí)間緊迫，沒有添加此項(xiàng)功能。2. 在刪除結(jié)點(diǎn)功能上，每次只能刪除

22、一個(gè)結(jié)點(diǎn)，在效率上未能體現(xiàn)。這個(gè)問題是比較難解決的問題，以我現(xiàn)在的編程能力暫時(shí)未能想到解決方案，在日后的學(xué)習(xí)中會(huì)慢慢發(fā)掘和探索解決方法。3. 數(shù)據(jù)沒有加密，容易篡改。由于數(shù)據(jù)存放于txt文件里面，修改里面的數(shù)據(jù)較為簡(jiǎn)單，嚴(yán)重影響系統(tǒng)的安全性?？梢远x一種二進(jìn)制文件，只有本系統(tǒng)才能打開，這樣就對(duì)數(shù)據(jù)進(jìn)行了加密。八 收獲和心得這次大作業(yè)的完成時(shí)間是整整一個(gè)暑假，但回想起來，時(shí)間都用在實(shí)習(xí)上，沒有好好利用暑假的兩個(gè)月來做課程設(shè)計(jì)。由于我本身編程能力不強(qiáng)，構(gòu)思，寫代碼，修改，調(diào)試的時(shí)間加起來絕對(duì)是要花上不少時(shí)間的，而且對(duì)于可視化mfc之前從來沒用過，都要自學(xué)，所花的時(shí)間就更多了。就是因?yàn)楦冻龊芏?，所以在前期的設(shè)計(jì)組織中，中期的代