數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)家族關(guān)系

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

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

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

4、子插入。以寫(xiě)入的方式打開(kāi)文件，更新數(shù)組中的信息，然后將數(shù)組中的信息寫(xiě)入文件保存，關(guān)閉文件。查找功能模塊，查找一個(gè)成員的所有祖先及其兄弟，查找一個(gè)成員的所有祖先路徑，需要從它的父親一直向上查找?guī)ЦY(jié)點(diǎn)。查找一個(gè)成員的兄弟，一個(gè)成員的兄弟為其父親除了該結(jié)點(diǎn)以外的所有孩子。對(duì)于要操作的結(jié)點(diǎn)，先判斷它是否是根結(jié)點(diǎn)，若是根結(jié)點(diǎn)，則無(wú)兄弟；若不是根結(jié)點(diǎn)，則找到該結(jié)點(diǎn)的父親。接著判斷父親的兄弟是否都存在，如果都不存在，則無(wú)兄弟；如果都存在，對(duì)父親的孩子操作。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、("請(qǐng)輸入家譜名稱:"); getchar(); gets(filename); /輸入家譜名稱 while(filename0=NULL) printf("家譜名不能為空,請(qǐng)重新輸入:"); gets(filename); if(fp=fopen(filename,"w")=NULL) printf("%s家譜創(chuàng)建失敗!n",filename); return 0; printf("請(qǐng)輸入家譜內(nèi)容:n"); while (strlen(gets(str)>0) fputs(str,fp)

7、; /向文件寫(xiě)入字符串 putc('n',fp); fclose(fp); /關(guān)閉文件 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、 /構(gòu)造二叉樹(shù)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); /分配存儲(chǔ)空間 M=(BiTPNode *)malloc(sizeof(BiTPNode); N=(BiTPNode *)malloc(sizeof(BiTPNode); printf("請(qǐng)輸入家譜名:"); getchar(); gets(filename); while(filename0=NULL) printf("家譜名不能為空,請(qǐng)重新輸入:"); gets(filename); if(fp=fopen(filename,"r")=NULL) printf("%s家譜打開(kāi)失敗!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("%家譜打開(kāi)失敗!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; /構(gòu)建孩子 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;請(qǐng)輸入要添加到該家譜中的人的父親姓名:"); getchar(); gets(father); while(!loc(T,P,father) printf("%s不在該家譜中!請(qǐng)重新輸入:",father); gets(father); printf("請(qǐng)輸入要添加到該家譜中的人的姓名:"); 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("請(qǐng)輸

15、入要?jiǎng)h除的人的姓名:"); getchar(); gets(name); while(!loc(T,P,name) printf("%s不在該家譜中!請(qǐng)重新輸入:",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; /二叉樹(shù)的遍歷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("請(qǐng)輸入要查尋的人的姓名:"); getchar(); gets(name); while(!loc(T,P,name) printf("%s不在該家譜中!請(qǐng)重新輸入:

18、",name); gets(name); N=P; if(P=T) printf("%s的父親在該家譜中沒(méi)有記載!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沒(méi)有兄弟!n",P->data); else if(!P->rchild&&P->pa

19、rent->rchild!=P) printf("%s沒(méi)有兄弟!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的祖先在該家譜中沒(méi)有記載!n",name); else printf("%s的祖先是:%sn",name,T->data); N=P; if(!P->lchild) printf("%s沒(méi)有孩子!n",name); printf("%s沒(méi)有后代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("無(wú)此選項(xiàng),請(qǐng)重新選擇!(按任一鍵繼續(xù)!)"); getch(); return

24、 1; /家譜的存儲(chǔ)status Sav(BiPTree T) FILE *fp; char filename40; system("cls"); printf("請(qǐng)輸入新的文件名:"); getchar(); gets(filename); while(filename0=NULL) printf("家譜名不能為空,請(qǐng)重新輸入:"); 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(" 請(qǐng)選擇 n");printf(" 1.添加成員. n");