數據結構課程設計家族關系

1、課程名稱: 數據結構課程設計課程設計題目: 家族關系查詢系統(tǒng)姓 名: 周楠院系: 計算機學院 專 業(yè): 軟件工程 年 級: 2011 學 號: E01114323指導教師: 王愛平2013 年 9月25日 目 錄 1 課程設計的目的2 需求分析3 課程設計報告內容3.1概要設計3.2詳細設計3.3調試分析3.4用戶手冊3.5測試結果3.6程序清單4 小結 5 參考文獻 1.課程設計的目的(1) 熟練使用 C 語言編寫程序，解決實際問題;(2) 了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能;(4

2、) 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力;2.需求分析隨著社會發(fā)展，人們使用紙質的家譜已經非常不方便而且不利于在家譜里進行添加和修改。而用算法設計一個家族關系查詢系統(tǒng)則可以解決這個問題。數據結構的二叉樹剛好滿足家譜的基本結構。首先建立一個文件作為家譜，然后在文件中輸入字符串，實現(xiàn)了在文件中按照數據的邏輯關系進進輸入便可建立相應的三叉鏈表。然后就是進行數據的存儲、刪除及查找工作。3. 算法分析本次設計研究的是建立家族關系，實現(xiàn)對家族成員關系相關查詢的問題。在設計中使用的數據結構為樹狀結構，樹狀結構采用三叉鏈表實現(xiàn)。我們在建立好家族關系后將其存儲在文件中，在文件中家族關系是以樹

3、的形式存儲，運用樹的操作使家族關系得以準確建立。 家族關系查詢系統(tǒng)可分為六大模塊，分別是創(chuàng)建、修改、查詢、保存、退出等。建立家族關系模塊，建立家族關系并存入文件。建立時首先輸入家族關系的名稱，以此名稱為名建立文本文件。接下來按層輸入成員姓名，輸入一個在文件中寫入一個字符串，以回車鍵結束。打開一個家族關系。在界面輸入選項名，以家族關系名為文件名打開文件，如果家族關系不存在，返回空；如果存在，打開文件，讀取文件。向家族中添加一個新成員，添加的新成員要根據其父親確定其在家族中的位置。首先判斷該父親是否在此家族關系中，若存在，則查找其父親，將新節(jié)點插入其父親的最后一個孩子之后；若沒有孩子，直接作為左孩

4、子插入。以寫入的方式打開文件，更新數組中的信息，然后將數組中的信息寫入文件保存，關閉文件。查找功能模塊，查找一個成員的所有祖先及其兄弟，查找一個成員的所有祖先路徑，需要從它的父親一直向上查找?guī)ЦY點。查找一個成員的兄弟，一個成員的兄弟為其父親除了該結點以外的所有孩子。對于要操作的結點，先判斷它是否是根結點，若是根結點，則無兄弟；若不是根結點，則找到該結點的父親。接著判斷父親的兄弟是否都存在，如果都不存在，則無兄弟；如果都存在，對父親的孩子操作。4. 源程序#include <stdio.h> #include <stdlib.h> #include <string

5、.h> #include<conio.h> typedef char TElemType; typedef int status; typedef struct BiTPNode TElemType data10; struct BiTPNode *parent,*lchild,*rchild; /父親及左右孩子指針BiTPNode,*BiPTree; BiPTree P; BiPTree T; /家譜的創(chuàng)建int Cre() system("cls"); FILE *fp; /聲明指向文件的指針 char filename40,str10; printf

6、("請輸入家譜名稱:"); getchar(); gets(filename); /輸入家譜名稱 while(filename0=NULL) printf("家譜名不能為空,請重新輸入:"); gets(filename); if(fp=fopen(filename,"w")=NULL) printf("%s家譜創(chuàng)建失敗!n",filename); return 0; printf("請輸入家譜內容:n"); while (strlen(gets(str)>0) fputs(str,fp)

7、; /向文件寫入字符串 putc('n',fp); fclose(fp); /關閉文件 printf("按任一鍵繼續(xù)!"); getch(); return 1; status loc(BiPTree T,BiPTree &P,TElemType name10) if(T)P=T; /字符串的比較 if(!strcmp(name,T->data) return 1; if(loc(T->lchild,P,name) return 1; if(loc(T->rchild,P,name) return 1; else return 0;

8、 /構造二叉樹status inittree(BiPTree &T) T=(BiTPNode *)malloc(sizeof(BiTPNode); if(T) return 0; T->lchild=NULL; T->rchild=NULL; T->parent=NULL; return 1; /載入家譜status Crt(BiPTree &T) FILE *fp; BiPTree Q,R,M,N; char filename40,name10; system("cls"); /清屏 R=(BiTPNode *)malloc(sizeof

9、(BiTPNode); /分配存儲空間 M=(BiTPNode *)malloc(sizeof(BiTPNode); N=(BiTPNode *)malloc(sizeof(BiTPNode); printf("請輸入家譜名:"); getchar(); gets(filename); while(filename0=NULL) printf("家譜名不能為空,請重新輸入:"); gets(filename); if(fp=fopen(filename,"r")=NULL) printf("%s家譜打開失敗!n",

10、filename); return 0; inittree(T); fscanf(fp,"%s",name); /從文件讀入姓名 strcpy(T->data,name); T->lchild=NULL; T->rchild=NULL; T->parent=NULL; fclose(fp); if(fp=fopen(filename,"r")=NULL) printf("%家譜打開失敗!n",filename); return 0; fscanf(fp,"%s",name); while(!

11、feof(fp) if(loc(T,P,name) fscanf(fp,"%s",name); Q=(BiTPNode *)malloc(sizeof(BiTPNode); strcpy(Q->data,name); P->lchild=Q; /構建孩子 Q->parent=P; Q->lchild=NULL; Q->rchild=NULL; N=P; else if(!loc(T,P,name) Q=(BiTPNode *)malloc(sizeof(BiTPNode); R=N; R=R->lchild; while(R) M=R;

12、R=R->rchild; strcpy(Q->data,name); M->rchild=Q; Q->parent=M; Q->lchild=NULL; Q->rchild=NULL; fscanf(fp,"%s",name); printf("信息載入成功,按任一鍵繼續(xù)!"); getch(); return 1; /添加成員status in(BiPTree &T) char father10,name10; BiPTree Q,M; system("cls"); printf(&quo

13、t;請輸入要添加到該家譜中的人的父親姓名:"); getchar(); gets(father); while(!loc(T,P,father) printf("%s不在該家譜中!請重新輸入:",father); gets(father); printf("請輸入要添加到該家譜中的人的姓名:"); gets(name); Q=(BiTPNode *)malloc(sizeof(BiTPNode); M=(BiTPNode *)malloc(sizeof(BiTPNode); strcpy(Q->data,name); Q->lchi

14、ld=NULL; Q->rchild=NULL; if(!P->lchild) P->lchild=Q; Q->parent=P; else P=P->lchild; while(P) M=P; P=P->rchild; M->rchild=Q; Q->parent=M; printf("成員添加成功,按任一鍵繼續(xù)!"); getch(); return 1; /刪除成員status de(BiPTree &T) char name10; system("cls"); printf("請輸

15、入要刪除的人的姓名:"); getchar(); gets(name); while(!loc(T,P,name) printf("%s不在該家譜中!請重新輸入:",name); gets(name); if(!P->rchild) if(P->parent->lchild=P) P->parent->lchild=NULL; else P->parent->rchild=NULL; free(P); else if(P->rchild) if(P->parent->lchild=P) P->par

16、ent->lchild=P->rchild; else P->parent->rchild=P->rchild; free(P); printf("成員刪除成功,按任一鍵繼續(xù)!"); getch(); return 1; status Show(TElemType e10) printf("%s ",e); return 1; /二叉樹的遍歷status pre(BiPTree T,status(*visit)(TElemType10) if(T) if (*visit)(T->data) if (pre(T->

17、lchild,visit) if (pre(T->rchild,visit) return 1; return 0; else return 1; /家族成員查詢status Sea(BiPTree T) char name10; BiPTree N; N=(BiTPNode *)malloc(sizeof(BiTPNode); system("cls"); printf("請輸入要查尋的人的姓名:"); getchar(); gets(name); while(!loc(T,P,name) printf("%s不在該家譜中!請重新輸入:

18、",name); gets(name); N=P; if(P=T) printf("%s的父親在該家譜中沒有記載!n",P->data); else while(N->parent->rchild=N) N=N->parent; printf("%s的父親是:%sn",P->data,N->parent->data); N=P; if(P=T) printf("%s沒有兄弟!n",P->data); else if(!P->rchild&&P->pa

19、rent->rchild!=P) printf("%s沒有兄弟!n",P->data); else printf("%s的兄弟有:n",name); while(N->rchild) printf("%s ",N->rchild->data); N=N->rchild; N=P; while(N->parent->rchild=N) printf("%s ",N->parent->data); N=N->parent; printf("n&

20、quot;); if(P=T) printf("%s的祖先在該家譜中沒有記載!n",name); else printf("%s的祖先是:%sn",name,T->data); N=P; if(!P->lchild) printf("%s沒有孩子!n",name); printf("%s沒有后代n",name); else printf("%s的孩子有:n",name); printf("%s ",P->lchild->data); N=N->l

21、child; while(N->rchild) printf("%s ",N->rchild->data); N=N->rchild; printf("n"); printf("%s的后代有:n",name); pre(P->lchild,Show); printf("n"); printf("按任一鍵繼續(xù)!"); getch(); return 1; /文件的創(chuàng)建status write(BiPTree T,char filename40) FILE *fp; i

22、f(fp=fopen(filename,"a+")=NULL) printf("%s文件創(chuàng)建失敗!n",filename); return 0; fprintf(fp,"%s ",T->data); T=T->lchild; while(T) fprintf(fp,"%s ",T->data); T=T->rchild; fprintf(fp,"n"); /輸出 fclose(fp); return 1; status prewrite(BiPTree T,status(

23、*visit)(BiPTree,char40),char filename40) if(T) if (T->lchild) (*visit)(T,filename); prewrite(T->lchild,visit,filename); prewrite(T->rchild,visit,filename); return 1; else return 1; status wrong() char a; scanf("%c",&a); printf("無此選項,請重新選擇!(按任一鍵繼續(xù)!)"); getch(); return

24、 1; /家譜的存儲status Sav(BiPTree T) FILE *fp; char filename40; system("cls"); printf("請輸入新的文件名:"); getchar(); gets(filename); while(filename0=NULL) printf("家譜名不能為空,請重新輸入:"); gets(filename); prewrite(T,write,filename); printf("%s家譜保存成功,按任一鍵繼續(xù)!",filename); getch(); return 1; /修改家譜status Upd() system("cls"); int xz; while(1) system("cls"); printf("nnnn");printf(" 家族成員的添加與刪除操作 n"); printf(" 請選擇 n");printf(" 1.添加成員. n");