1、數據結構課程設計家譜管理系統設計與實現姓名：學號：年級：專業：學校：1 1. 1..352.2.462.2.562.2.682.2.7102.2.8102.2.9102.2.10112.2.11122.3132.41731718192家譜管理系統設計與實現姓名：學號：班級：計算機科學與技術1問題陳述家譜用于記錄某家族歷代家族成員的情況與關系。現編制一個家譜資料管理軟件，實現對一個家族所有的資料進行收集整理。支持對家譜的存儲、更新、查詢、統計等操作。并用計算機永久儲存家族數據，方便隨時調用。2設計方法闡述2.1 總體規劃在動手編制程序之前，先要做好

2、程序的規劃，包括程序儲存數據所用的結構，數據類型等等， 只有確定了數據類型和數據結構，才能在此基礎上進行各種算法的設計和程序的編寫。首先是考慮數據類型。在家譜中，家族成員是最基本的組成部分，對于家族管理中，已經不能再進行細分了，所以選定家族成員作為數據的基本類型，并在程序中定義COperationFamilytree類。其中COperationFamilytree類的各種屬性可以根據需要進行添加或刪除，從日常生活應用的角度出發，制定了COperationFamilytree類中包含了一下屬性：char nameMAX_CHARNUM;/ 姓名Date birthday;/ 出生日期In tse

3、x; / 性別char addrMAX_CHARNUM;/基本資料int live;/健在否Date deathday;/死亡日期int ChildNums(Person pNode) ;/ 返回 pNode孩子數3intInSiblingPos(Person pNode);/ 返回 pNode在其兄弟中的排行為方便計算機進行比較，在 familytree 類的某些屬性中用數字代替了某些不會改變的字符串，譬如性別（1 代表男， 0 代表女）、判斷是否健在（1 為是， 0 為否）。在設置日期上，為方便以后的計算與比較， 也將日期用整型數字表示19990505 表示 1999 年 5 月 5 日，

4、這種表示方法只需在輸入和輸出上作少許的運算便可方便地與日期進行轉換。在家族關系的表示上，并沒有用相關家屬的姓名作為儲存數據，而僅僅是存儲了各關系親屬的ID ，方便日后作為指針指示調用相對應的家族成員。其中在屬性pNode 上，其表示的是下一個同父母的弟或妹 ID ，也就是說，當某家族成員有若干個子女，其pNode 僅指向第一個孩子，其余的孩子如何表示呢？可以通過第一個孩子的pNode 指示，如此類推，直到孩子的pNode =0 為止。這樣就可以避免需在程序設計時預定父母可以擁有的孩子數，有多少孩子就表示多少，實現了動態的儲存數據。在選擇數據結構方面，從直觀來說，選擇樹型結構通過鏈表來連接數據無

5、疑是最直觀易懂的，我在一開始構思的時候也是從樹型結構去想的，但當構思到如何存儲和提取數據是，便發現了問題。 毫無疑問，用指針來處理數據的確是方便直觀，但當我要儲存數據是，便發現把指針儲存進去是沒有作用的，因為當我們下一次讀取數據的時候，數據內存地址已經不同了， 不在是我們上次存儲數據時的地址，也就是說指針這時已經是沒有作用了。要解決這樣的問題， 我們必須要在存儲數據之前，先家族樹序列化，用數組 （或者其他可以用數字表示關系的方法） 來存儲， 并且， 再下一次讀取數據時，再把數據按照序列號重新組成一個家族樹， 過程比較繁復，而且實現起來也不容易。所以我便考慮直接用數組來存儲數據，即使是在內存中也

6、用數組來處理數據間的聯系。運用順序表這個結構雖然不是那么直觀，但在查找數據時的算法設計比較簡單容易實現，效率高，而且在內存中的數據可以直接讀入到文件中，文件中的數據也可以直接讀入內存，不需要進行轉換。所以在衡量的各個方面之后，我決定用數組來處理數據間的聯系。2.2 功能構想構想好總體規劃之后，便開始設計程序中需要用到的各個功能函數，初步構想是要先實現最基本的幾項功能，其中數據操作的有：增加成員，修改成員資料，刪除成員；數據存取的有：打開家譜，新建家譜，保存家譜，另存家譜；數據查詢的有：查看某代信息，按姓名查找，按生日查找，查看成員關系，按出生日期排序等等。42.2.1 增加成員這項功能做得不夠

7、理想，在規劃時沒有把成員以配偶的形式增加，而只能以子女的形式增加。對應的函數代碼如下：void COperationFamilytree:Add(Person parent, Person addNode)/本函數把addNode 結點加入到其父結點parent 下addNode-child=addNode-sibling=0;/把欲加入的結點所有指針域置空addNode-parent=parent;/因 addNode 欲加為parent 的孩子，故addNode 結點的父指針域應指向parentif(parent=0)/若 parent 為 0，則表示欲加addNode 為根結點if(T=

8、0)/若本為空家譜T=addNode;/把 addNode 當成根結點return;addNode-child=T;/使原來的根結點成為新根結點的孩子T-parent=addNode;T=addNode;return;if(parent-child=0)/parent 無孩子，把addNode 加入其孩子parent-child=addNode;elseInsertSibling(parent-child,addNode);/把 addNode 加到 parent 孩子的兄弟域中2.2.2 修改成員資料修改成員這項功能實現起來比較簡單，找到要修改成員的名字，再輸入新修改的值，整個函數沒有什么需

9、要運用算法的地方，但如果想真正寫好這個函數，則需要考慮相當多的細節，譬如各個輸入項目的錯誤處理等等，要非常全面地考慮各項細節。函數代碼如下：void CFamilytreeDlg:OnModify()/ TODO: Add your command handler code here if(operFamilytree.GetRoot()=0)return;CModifyInfoDlg dlg;HTREEITEM hItem;hItem=m_peTree.GetSelectedItem();dlg.m_newname=m_peTree.GetItemText(hItem);5Person on

10、eself=0;char oldnameMAX_CHARNUM; strcpy(oldname,dlg.m_newname); operFamilytree.Find(operFamilytree.GetRoot(),oneself,oldname); if(dlg.DoModal()=IDCANCEL)return;UpdateData(FALSE);Person newValue=new PersonNode;strcpy(newV,dlg.m_newname);/ 判斷家譜中是否已有用戶給定的新名字if(strcmp(newV,ol

11、dname)=0) ; / 用戶不修改姓名 elsePerson p=0;operFamilytree.Find(operFamilytree.GetRoot(),p,newV);/ 查 找家譜中有沒有此人if(p!=0)AfxMessageBox( 家譜中已有此人!);delete newValue;return;strcpy(newValue-info.addr,dlg.m_newaddr);newValue-info.marry=dlg.m_marry;newValue-info.live=dlg.m_live;newValue-info.birthday.d

12、ay=dlg.m_birthday_day;newValue-info.birthday.month=dlg.m_birthday_month;newValue-info.birthday.year=dlg.m_birthday_year;if(!newValue-info.live)/ 如若過世,則應有死亡日期newValue-info.deathday.day=dlg.m_deathday_day;newValue-info.deathday.month=dlg.m_deathday_month;newValue-info.deathday.year=dlg.m_deathday_year

13、;if(!operFamilytree.IsDateValid(newValue-info.deathday)AfxMessageBox( 此人信息中死亡日期不合實際!);delete newValue;return;if(operFamilytree.CompareDate(newValue-info.deathday,newValue-info.birthday)=-1)AfxMessageBox( 此人死亡日期不可能比其出生日期早!);return;6operFamilytree.Modify(oneself,newValue);RefreshTree();RefreshList();I

14、sFamilytreeModified=true;/ 置家譜修改標記為真delete newValue;2.2.3 刪除成員用數組來儲存數據， ，最麻煩的就是刪除數組元素了，在這個程序中，刪除數組不但意味著要重新排列各成員， 還要重新更新各成員的關系， 所以我個人認為在這個程序中， 刪除成員函數可以說是一個難點。 通過分析， 發現刪除成員的情況就只有兩種， 只要針對這兩種情況處理好刪除，就可以完成成員刪除這個功能。，刪除的成員是出于家族中最底層的，也就是刪除該成員不會牽連其他成員，但這也需要處理好其父母的孩子數。，刪除的成員還有子孫，則需要連帶所有子孫都要刪除出家譜。遇到這種情況， 不但要像上

15、一種情況那樣處理父母和兄弟姐妹的關系，還要記錄牽連刪除的總人數，因為刪除不再是簡單刪除了一個人，而是若干個，通過遞歸調用，可以統計出需要刪除的數目刪除函數的相關代碼如下：void COperationFamilytree:Delete(Person &rootNode)/本函數刪除以rootNode 為根結點的所有結點if(rootNode-parent)/如果 rootNode 有父結點if(rootNode-parent-child=rootNode)/ 如果rootNode 為其父結點的第一個孩子rootNode-parent-child=rootNode-sibling;/ 因要刪掉r

16、ootNode, 故把其父結點的孩子指針指向rootNode 的第一個兄弟else/ 如果rootNode 不是父結點的第一個孩子Person p=rootNode-parent-child;/找到 rootNode 應在兄弟中的位置for(;p-sibling!=rootNode;p=p-sibling);p-sibling=rootNode-sibling;/插入到兄弟中PostOrderTraverse(rootNode-child,DestroyNode);/ 刪除以rootNode-child為根結點的所有結點if(rootNode=T)/刪除 rootNode 結點。如果rootN

17、ode 為根結點，則刪除根結點TDestroyNode(T);7elseDestroyNode(rootNode);2.2.4 打開家譜打開家譜函數的相關代碼如下：int COperationFamilytree:ReadNode(FILE *fp, Person &T,char* parentname)/本函數從文件fp 中讀取信息到結點T 中 ,并讀取結點的父親名字到字符數組parentname 中/分別讀取結點值,為: 姓名 ,出生日期 (年,月 ,日 ),婚否 ,地址 ,健在否 ,(如過世，還有死亡日期)fscanf(fp,%s%d%d%d%d%s%d,T-,&T-i

18、nfo.birthday.year,&T-info.birthday.month,&T-info.birthday.day,&T-info.marry,T-info.addr,&T-info.live);if(T-info.live=0)fscanf(fp,%d%d%d,&T-info.deathday.year,&T-info.deathday.month,&T-info.deathday.day);fscanf(fp,%s,parentname);if(!IsDateValid(T-info.birthday) /出生日期合法性檢查 return FILE_DATA_NOT_PRACTIC

19、AL;if(T-info.live=0)/若過世 ,死亡日期合法性檢查if (CompareDate(T-info.birthday,T-info.deathday)!=-1) return FILE_DATA_NOT_PRACTICAL;if(!IsDateValid(T-info.deathday)returnFILE_DATA_NOT_PRACTICAL;return OK;2.2.5 新建家譜新建家譜函數的相關代碼如下：void COperationFamilytree:NewFamilytree()/本函數新建一空家譜8DestroyFamilytree();/刪除原有家譜T=0;i

20、nt COperationFamilytree:CreateFamilytree(CString filename)/本函數建立一新家譜DestroyFamilytree();/建立一新家譜之前，清空原有家譜FILE* fp;if(fp=fopen(filename,r)=0)/打開文件filenamereturn READ_FILE_ERROR;T=new PersonNode;/ 定義根結點if(!T)return NOT_ENOUGH_MEMORY;T-child=0;T-sibling=0;T-parent=0;Person parentT, temp;/定義兩個臨時結點char pa

21、rentnameMAX_CHARNUM;/ 定義一個臨時字符串數組/讀取根結點值,(姓名 ,出生日期 ( 年 ,月 ,日 ), 婚否 ,地址 ,健在否 ,( 如過世，還有死亡日期)int result;result=ReadNode(fp,T,parentname);if(result=FILE_DATA_NOT_PRACTICAL)delete T;/若不合法，刪除申請的堆空間T=0;return result;if(strcmp(T-,parentname)=0)/根結點名字與其父親名字相同，說明為空樹delete T;T=0;return PEDIGREE_EMPTY;

22、temp=new PersonNode;/申請一結點if(!temp)/ 申請失敗DestroyFamilytree();/ 釋放申請空間return NOT_ENOUGH_MEMORY;result=ReadNode(fp,temp,parentname);while(strcmp(,parentname)&strcmp(,end)/9讀取信息結束的條件是兩個人的名字同為endif(result=FILE_DATA_NOT_PRACTICAL)/ 若數據不合法，釋放已申請空間，然后返回delete temp;DestroyFamilyt

23、ree();return result;parentT=0;Find(T,parentT,parentname);/找到 parentname 所在結點parentTif(parentT)/ 如果 parentT 存在，說明parentname 在家譜中/并且 parentname 為 temp 的父親int cmp;cmp=CompareDate(temp-info.birthday,parentT-info.birthday);if(cmpchild=temp-sibling=0;temp-parent=parentT;/temp 的父指針指向parentT;if(parentT-chil

24、d)/parentname 已經有孩子InsertSibling(parentT-child,temp);/ifelse/parentname 無孩子 ,則 temp 應為parentT-child=temp;/parentname 的第一個孩子/ifelse/parentT 不存在 ,說明家譜中不存在parentname 此人DestroyFamilytree();/ 返回出錯信息return FILE_DATA_ERROR;temp=new PersonNode;/ 申請一結點if(!temp)/申請失敗DestroyFamilytree();/釋放申請空間return NOT_ENOUG

25、H_MEMORY;result=ReadNode(fp,temp,parentname);/ 繼續讀取數據/whileif(temp)delete temp;fclose(fp);return OK;102.2.6 保存家譜保存家譜函數的相關代碼如下：int COperationFamilytree:SaveFamilytree(CString filename)/本函數保存家譜到文件filename 中FILE* fp;if(fp=fopen(filename,w)=0)/打開文件filenamereturn WRITE_FILE_ERROR;PreOrderTraverse(fp,T,Sa

26、veNode);/從根結點開始存儲家譜數據/置家譜數據結束標記(一結點的名字與其父結點的名字同為end)fprintf(fp,%s %d %d %d %d %s %d %s,end,1999,12,2,1,end,1,end);fclose(fp);return OK;voidCOperationFamilytree:PreOrderTraverse(FILE*fp,Person&T,void(_cdecl*Visit)(FILE* fp,Person &)/本函數把所有以T 結點為根結點的結點值存到文件fp 中if(T)(*Visit)(fp,T);PreOrderTraverse(fp,T

27、-child,Visit);PreOrderTraverse(fp,T-sibling,Visit);void SaveNode(FILE *fp, Person &pNode)/本函數向文件fp 中存取一結點pNodechar ch=n;if(pNode)fprintf(fp,%s %d %d %d %d %s %d ,pN,pNode-info.birthday.year,pNode-info.birthday.month,pNode-info.birthday.day,pNode-info.marry, pNode-info.addr,pNode-info.li

28、ve);if(pNode-info.live=0)fprintf(fp, %d %d %d ,pNode-info.deathday.year,pNode-info.deathday.month,pNode-info.deathday.day);if(pNode-parent)fprintf(fp, %s ,pN);else11fprintf(fp, %s,-1);fprintf(fp, %c,ch);2.2.7 查看某代信息查看某代信息函數的相關代碼如下：int COperationFamilytree:InGenerationPos(Person p

29、Node)/本函數返回pNode 結點在第幾代int pos=1;Person p;p=pNode-parent;for(;p!=0;p=p-parent)pos+;return pos;2.2.8 按姓名查找按姓名查找函數的相關代碼如下：void COperationFamilytree:Find(Person& T,Person& Tname,char* name)/本函數以T 為根結點開始 ,搜索結點信息中名字等于name 的結點if(T)/如果 T 存在if(strcmp(T-,name)=0)/T 結點姓名和name 相同，把T 結點指針傳給 TnameTname=

30、T;elseFind(T-sibling,Tname,name);/對 T 的兄弟遞歸搜索Find(T-child,Tname,name);/對 T 的孩子遞歸搜索2.2.9 按生日查找按生日查找函數的相關代碼如下：void COperationFamilytree:Find(Person &T, Person*& Tname,int month, int day)/本函數以T 為根結點開始 ,搜索結點信息中生日等于month,day 的結點 ,/并把所有符合條件的結點指針值存入以Tname 為起始地址的地址數組中if(T)/如果 T 存在if(T-info.birthday.month=mo

31、nth&T-info.birthday.day=day)/T 結點生日與所給相同，把T 結點指針傳給Tname,同時 Tname 指針前12進Person temp;temp=new PersonNode;temp=T;if(temp-info.birthday.month=month&temp-info.birthday.day=day)*Tname=temp;Tname+;temp=NULL;Find(T-child,Tname,month,day); / 對 T 的孩子遞歸搜索Find(T-sibling,Tname,month,day);/對 T 的兄弟遞歸搜索2.2.10 查看成員關

32、系查看成員關系函數的相關代碼如下：void CFamilytreeDlg:OnFamilytreeRelations()/ TODO: Add your command handler code here CRelationsDlg dlg; if(dlg.DoModal()=IDCANCEL)return;UpdateData(FALSE); int pos1,pos2;Person oneself=0;char name1MAX_CHARNUM,name2MAX_CHARNUM; strcpy(name1,dlg.m_firstname); operFamilytree.Find(oper

33、Familytree.GetRoot(),oneself,name1); if(oneself)pos1=operFamilytree.InGenerationPos(oneself);elseAfxMessageBox( 本家譜中找不到+CString(name1)+!);return;Person p,q;CString generation;generation+=;generation+= 在家譜中的位置: ;for(q=oneself,p=q-parent;p!=0;p=p-parent)generation+=;generat

34、ion+= -;q=p;13generation+=;generation+=n;oneself=0;strcpy(name2,dlg.m_secondname);operFamilytree.Find(operFamilytree.GetRoot(),oneself,name2);if(oneself)pos2=operFamilytree.InGenerationPos(oneself);elseAfxMessageBox( 本家譜中找不到+CString(name2)+!);return;generation+=;generatio

35、n+= 在家譜中的位置: ;for(q=oneself,p=q-parent;p!=0;p=p-parent)generation+=;generation+= - ;q=p;generation+=;generation+=nn;CString cmpResult;if(pos1pos2)cmpResult.Format(%s在 第 %d代 ， %s在 第 %d代 ， %s是 %s的 晚輩.,name1,pos1,name2,pos2,name1,name2);else if(pos1pos2)cmpResult.Format(%s在 第 %d代

36、， %s在 第 %d代 ， %s是 %s的 長輩.,name1,pos1,name2,pos2,name1,name2);elsecmpResult.Format(%s 與%s 同在第 %d 代 .,name1,name2,pos2);generation+=cmpResult;AfxMessageBox(generation);2.2.11 按出生日期排序按出生日期排序函數的相關代碼如下：void COperationFamilytree:SortByBirthday(QuickSortNode *order)14/本函數對順序表order 以出生日期的大小排序int totalNums=0

37、;QuickSortNode* startaddr=order;startaddr+;GetPersonNums(T,totalNums);CopyInfoFromBiTreeToArray(T,startaddr);QuickSort(order,1,totalNums);2.3 板塊整合以上的功能設計生成的各種函數文件僅是獨立的各個板塊，要將這些函數有機地聯系起來，才能形成可以應用的程序，首先我用了一個DefineStruct.h 聲明數據類型與各個應用函數，其代碼如下：根據家譜的特點，采用孩子- 兄弟的二叉樹鏈表表示法（鏈表的基本單位為以結構PersomNode表示的結點），各種操作以C

38、OperationFamilytree類來實現。以下是 CoperationFamilytree類包含的數據成員及基本操作class COperationFamilytree/定義家族成員結構public:COperationFamilytree();/ 構造函數virtual COperationFamilytree();/ 析構函數void NewFamilytree();/ 新建一空家譜int CreateFamilytree(CString filename);/ 從輸入文件 filename 中讀取數據建立家譜void DestroyFamilytree();/ 刪除家譜int Sa

39、veFamilytree(CString filename);/ 保存家譜void PreOrderTraverse(FILE* fp,Person& T ,void (*Visit)(FILE* fp,Person& T);15/ 先序遍歷 ( 為保存家譜而做 )void PostOrderTraverse(Person& T,void (*Visit)(Person& T);/ 后序遍歷 ( 為刪除家譜而做 )void Find(Person& T,Person& Tname,char* name);/ 從根結點出發，搜索 name 所在結點 , 如找到，存于 Tname 中，找不到， T

40、name 為 0/ 使用前確保 Tname 指針為 0void Find(Person&T,Person*& Tname,int month,int day);/ 從根結點出發， 搜索家譜中 birthday.month等于 month,birthday.day等于 day 的所有結/ 點 , 如找到， 存于以 Tname 為首地址的指針數組中，找不到， Tname 為 0 使用前確保 Tname/ 指針為 0void Add(Person parent,Person addNode);/ 把 addnode 加為結點 parent的孩子void Delete(Person& rootNode

41、);/ 刪除以 rootNode為根結點的所有結點void Modify(Person& pNode,Person newValue);/ 修改 pNode 結點為新值 newValuevoid SortByBirthday(QuickSortNode* order);/ 對家譜以出生日期排序，并把排序結果放在數組order中void GetPersonNums(Person&T,int& personNums);/ 得到家譜中總人數int InGenerationPos(Person pNode);/ 返回 pNode 在家譜中是第幾代int InSiblingPos(Person pNod

42、e);/ 返回 pNode 在其兄弟中的排行int ChildNums(Person pNode);/ 返回 pNode 孩子數int CompareDate(Date date1,Date date2);/ 比較兩日期的大小bool IsDateValid(Date date);/ 檢驗日期是否合法16Person& GetRoot();/ 得到根結點friend void SaveNode(FILE* fp,Person& pNode);/ 保存結點 pNode 到文件 fp 中friend void DestroyNode(Person& pNode);/ 刪除結點private:Per

43、son T;/ 二叉樹的根結點int ReadNode(FILE* fp,Person&T,char* parentname);/ 從文件 fp中讀取信息到結點T 中，讀取此結點的父親姓名到parentnaem中 ( 供CreateFamilytree函數調用 )void InsertSibling(Person& firstSibling,Person insertSibling);/ 把 insertSibling插入到以 firstSibling為首的兄弟中 ( 供 CreateFamilytree函數調用)void CopyInfoFromBiTreeToArray(Person&T,

44、QuickSortNode*&order);/ 把家譜中以 pNode 結點為根結點的出生日期拷貝到快速排序結構數組order中 ( 供SortByBirthday函數調用 )void QuickSort(QuickSortNode* order,int low,int high);/ 對 orderlow.high中的記錄進行快速排序( 供 SortByBirthday函數調用 )int Partition(QuickSortNode* order,int low,int high);/ 對 orderlow.high中的記錄進行一次排序( 供 QuickSort函數調用 )bool IsL

45、eapYear(int year);/ 判斷是否閏年（供IsDateValid調用，以檢查日期是否合法）根據 MFC 的特點，采用 CfamilytreeDlg類實現用戶窗口界面指令對于家譜的各種操作。class CFamilytreeDlg : public CDialogpublic:void SaveTip();17/ 保存提示void InitListCtrl();/ 初始化列表控件void RefreshTree();/ 刷新樹， ( 即刷新顯示 )void RefreshList();/ 刷新列表void DisplayFamilytree(Person& pNode);/ 顯示樹

46、void DisplayInListCtrl(Person pNode);/ 把 pNode 結點的信息在列表控件中顯示出來void Display(CString temp);/ 在列表控件中顯示其他信息void FindInTree(HTREEITEM& hRootItem,HTREEITEM& hItem,char* name);/ 在樹 hRootItem中查找 name 所在結點，如找到，把其結點句柄存入hItem中 , 找不到，/hItem為0. 注意，使用該函數時，確保hItem初值為 0void BirthdayTip();/ 每次打開一新家譜文件時的生日提示void DisplayGenerationInfo(Person& pNode,bool& flag,int count,int generation);/ 顯示所有第 generation 代人的信息void AddToTree(HTREEITEM hParentItem,Person addnode );/ 把 addnode 加入到樹的 hParentItem結點中去private:char savepathMAX_CHARNUM;/ 家譜第一次被保存時的路徑bool IsFamilytre