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

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

2、 需求分析1. 系統(tǒng)需求本系統(tǒng)是家譜管理系統(tǒng)，顧名思義，是用來管理家族資料的，要實(shí)現(xiàn)建立新家譜，查找家譜文件，增加家族成員，修改家族成員，刪除家族成員和查找家族成員等基本功能。家譜管理系統(tǒng)是給家族長輩管理家族資料用的，對電腦的操作不一定熟悉，所以操作界面一定要友好，一定要方便，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)在程序初始化時由外存文件一次讀入內(nèi)存，此后不管插入還是修改，刪除都不再對外存的樹結(jié)構(gòu)保存文件進(jìn)行操作，只在內(nèi)存中處理，程序退出時對外存樹結(jié)構(gòu)文件進(jìn)行一次更新。也就是說，不管在程序運(yùn)行中中對家譜結(jié)構(gòu)進(jìn)行多少種，多少次的操作，外存的樹結(jié)構(gòu)文件始終只會被程序訪問兩次。以二叉鏈表作為樹的存儲結(jié)構(gòu)，鏈表中的兩個鏈域分別指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)和下一個兄弟結(jié)點(diǎn)，它通過描述

4、每個結(jié)點(diǎn)的一個孩子和兄弟信息來反映結(jié)點(diǎn)之間的層次關(guān)系，其具體的結(jié)點(diǎn)結(jié)構(gòu)為：firstchilddatanextsibling其中，firstchild為指向該結(jié)點(diǎn)第一個孩子的指針，nextsibling為指向該結(jié)點(diǎn)下一個兄弟，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; /初始時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+

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

7、加入其firstchild parent->firstchild=addnode; else insertsibling(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) /修改某個人的信息 strcpy(curnode->,newnode->); strcpy(curnode->data.

8、birthplace,newnode->data.birthplace); strcpy(curnode->data.sex,newnode->data.sex); strcpy(curnode->data.occupation,newnode->data.occupation); strcpy(curnode->cation,newnode->cation); strcpy(curnode->data.top_headship,newnode->data.top_headship); curnode->

9、;data.height=newnode->data.height; curnode->data.birthdate=newnode->data.birthdate; curnode->data.deathdate=newnode->data.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)me

10、ssagebox("請選擇結(jié)點(diǎn)再刪除!");return;if(datatree.havechild(m_curnode)messagebox("該結(jié)點(diǎn)有孩子結(jié)點(diǎn)，不能直接刪除!");return;if(messagebox("確認(rèn)刪除?","警告",mb_iconwarning|mb_okcancel)!=1)return;datatree.deletenode(m_curnode);/刪除datatree中相應(yīng)的數(shù)據(jù)questionm_ptreepage->m_showtree.deleteitem(pn

11、ode);if(m_ptreepage->m_showtree.getcount()=0)/刪除后若樹為空getdlgitem(idc_generation)->setwindowtext("未選結(jié)點(diǎn)");getdlgitem(idc_linealname)->setwindowtext("");getdlgitem(idc_matename)->setwindowtext("");getdlgitem(idc_whosbrief)->setwindowtext("簡介");getdl

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

13、ot;<<endl;/如果不能打開，顯示出錯信息 return;preordertraverse(f,t,savenode);/調(diào)用先序遍歷寫二叉樹信息到文件f.close();/關(guān)閉文件/person& t=familytree:getroot();/ 返回家譜的根結(jié)點(diǎn) /return t;家譜的重建（從文件讀?。﹙oid familytree:createfamilytree() destroyfamilytree();/刪除原來家譜樹結(jié)構(gòu) int n=0;/初始化數(shù)組下標(biāo)，用來看有幾多個數(shù)據(jù) fstream f("1.dat",ios:binary

14、|ios:in);/以二進(jìn)制讀方式打開 if(!f) cerr<<"文件打開失??！"<<endl;/不能打開，顯示出錯信息 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;i<max_char_num;i+)tempi=new csnode; / 初始化一個地址值，且不能為空否則

15、出錯="" if(posend=f.tellg() /記錄文件尾位置" f.tellg(="" )/ cout<<"這是一個空家譜！"<<endl; /文件頭與文件尾相同，說明文件無數(shù)據(jù)，為空樹 return; while(posend!=f.tellg()/從頭到尾讀取二進(jìn)制數(shù)據(jù) f.read(char*)&(tempn->data),sizeof(info); n+; newfamilytree(); t=temp0;t->firstchild=t->nextsiblin

16、g=null;/將第一個賦給根結(jié)點(diǎn) t->parent = null;for(int j=1;j<n;j+) /其余繼續(xù)用類似add（）函數(shù)來添加進(jìn)樹里findbyname(t,parentt,tempj->data.parentname); if(parentt) tempj->firstchild=tempj->nextsibling=null; tempj->parent=parentt; if(parentt->firstchild) insertsibling(parentt->firstchild,tempj); else paren

17、tt->firstchild=tempj; 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->

18、;nextsibling,visit); 6、 家族成員的查找查找部分涉及的查找方法多樣，這里用按姓名查找來代表，其他查找使用的算法思想是類似的，使用遞歸的方法，代碼如下：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（）比

19、較兩個字符串，若相等，則找到符合條件的 tname=t; else findbyname(t->firstchild,tname,name); /對t的firstchild遞歸搜索 findbyname(t->nextsibling,tname,name); /對t的nextsibling遞歸搜索 三 程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)部分是算法設(shè)計(jì)的補(bǔ)充與完善，代碼會與算法設(shè)計(jì)有不同，而且實(shí)現(xiàn)了mfc界面顯示部分，最終工程的實(shí)現(xiàn)以程序的為主。注：代碼太長不附在文檔上四 測試報告1. 初始化界面： 圖2 系統(tǒng)初始化界面效果圖2文件讀取保存模塊 2.1 新建家譜 新建家譜實(shí)際操作為創(chuàng)建該家譜第一代成員

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

21、邊顯示編輯框，輸入名字信息和配偶名字信息，可以選擇性別，可以選擇所創(chuàng)建新結(jié)點(diǎn)是當(dāng)前結(jié)點(diǎn)的子節(jié)點(diǎn)或是兄弟結(jié)點(diǎn)。 圖7 創(chuàng)建結(jié)點(diǎn)頁面效果圖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é)點(diǎn)，按刪除結(jié)點(diǎn)按鈕，彈出警告窗口，詢問是否確認(rèn)刪除結(jié)點(diǎn)，按確定刪除結(jié)點(diǎn) 圖9 刪除子節(jié)點(diǎn)頁面效果圖（2） 刪除有子節(jié)點(diǎn)的父節(jié)點(diǎn)，會彈出警告窗口，說明有子節(jié)點(diǎn)，不能刪除該結(jié)點(diǎn) 圖10 刪除父節(jié)點(diǎn)頁面效果圖4. 查找4.1按照姓名信息關(guān)鍵字查找（1） 不區(qū)分大小寫 圖11 按照名字信息不分大小寫

22、查找頁面效果圖（2） 區(qū)分大小寫 圖12 按照姓名信息區(qū)分大小寫查找頁面效果圖4.2 按照配偶名字信息關(guān)鍵字查找圖13 按照配偶姓名信息查找頁面效果圖五 目標(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

23、. 完成了家譜樹中結(jié)點(diǎn)的查找功能，可以按照姓名信息區(qū)分大小寫或者不分大小寫查找，也可以按照配偶信息查找六 遇到的問題和解決方案1. 需要設(shè)計(jì)一個簡單易用的系統(tǒng)，方便沒有計(jì)算機(jī)技術(shù)的管理人員使用，普通的dos界面就無法滿足此要求了，所以就要采取編寫可視化的解決方案。2. 沒有學(xué)過可視化編程的相關(guān)技能，要從零開始學(xué)習(xí)此門課程，通過購買相關(guān)書籍和上網(wǎng)查找資料解決編程過程中遇到的問題。3. 測試階段總會出現(xiàn)這樣那樣的問題，這時候就需要很多的耐心，并且要細(xì)心的處理每個錯誤。七 尚未解決的問題和應(yīng)對策略1. 在刪除結(jié)點(diǎn)功能上，只能刪除子結(jié)點(diǎn)，不能刪除擁有子結(jié)點(diǎn)的父結(jié)點(diǎn)，要解決這個尚未解決的問題，需要在程序

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