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

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-04-02 格式：doc 頁數(shù)：28 大?。?40.04KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

已閱讀1頁，還剩27頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　1 課程設(shè)計(jì)介紹 　　1.1課程設(shè)計(jì)項(xiàng)目簡介 　　家譜是一種以表譜形式，記載一個(gè)以血緣關(guān)系為主體的家族世系繁衍和重要人物事跡的特殊圖書載體。家譜是中國特有的文化遺產(chǎn)，是中華民族的三大文獻(xiàn)之一，屬珍貴的人文資料，對于歷史學(xué)，民俗學(xué)，人口學(xué)，社會學(xué)和經(jīng)濟(jì)學(xué)的深入研究，均有不可替代的重要功能。本項(xiàng)目對

2、家譜管理進(jìn)行簡單的模擬，以實(shí)現(xiàn)查看祖先和子孫個(gè)人信息、插入家族成員等功能。 　　1.2課設(shè)題目分析　　本程序的實(shí)質(zhì)是完成對家譜成員信息的建立、查找、插入等功能?？梢允紫榷x家族成員的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。<

3、;p>　　本程序包含以下幾個(gè)模塊　　建立家族關(guān)系樹。此模塊將構(gòu)建一個(gè)家族關(guān)系，對數(shù)據(jù)初始化，構(gòu)造關(guān)系樹并錄入數(shù)據(jù)一遍后續(xù)程序使用。　　添加新成員。此模塊將添加一個(gè)新成員，實(shí)現(xiàn)對家族關(guān)系的修改。　　家族關(guān)系的查詢。此模塊將實(shí)現(xiàn)對家族不同關(guān)系的查詢　　主程序模塊。此模塊

4、實(shí)現(xiàn)整個(gè)程序的進(jìn)入和進(jìn)出，以及各種初始化處理。　　1.3課程題目原理與數(shù)據(jù)結(jié)構(gòu)　　因?yàn)榧易宓某蓡T之間存在一個(gè)對多個(gè)的層次結(jié)構(gòu)關(guān)系，所以不能用線性表來表示和實(shí)現(xiàn)。家譜從形狀上看像一顆倒長的樹，所以用樹結(jié)構(gòu)來表示比較合適。樹形結(jié)構(gòu)是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀看來樹是以分支關(guān)系定義的層次結(jié)構(gòu)。　　因此本課程設(shè)計(jì)

5、可以采用的數(shù)據(jù)結(jié)構(gòu)有樹狀結(jié)構(gòu)和隊(duì)列。樹狀結(jié)構(gòu)采用三叉鏈表來實(shí)現(xiàn)，隊(duì)列采用鏈?zhǔn)疥?duì)列實(shí)現(xiàn)。　　1.4功能分析說明圖　　2 分析與實(shí)現(xiàn) 　　2.1 基本數(shù)據(jù)結(jié)構(gòu)和棧隊(duì)的操作　　2.1.1 結(jié)點(diǎn)基本數(shù)據(jù)結(jié)構(gòu)和鏈隊(duì)的定義　　/*家族關(guān)系

6、樹實(shí)現(xiàn)*/　　#include <string.h>　　#include <malloc.h>　　#include<limits.h>　　#include<stdio.h>　　#in

7、clude<stdlib.h>　　#include<io.h>　　#include<math.h>　　#include<process.h>　　#define TRUE 1　　#de

8、fine FALSE 0　　#define OK 1　　#define ERROR -1　　#define INFEASIBLE -1　　typedef char DataType;　　#define MAXNUM 20</

9、p>　　typedef struct TriTNode/* 樹的三叉鏈表存儲結(jié)構(gòu)*/　　{ 　　DataType data[MAXNUM];　　struct TriTNode *parent;/* 雙親*/

10、　　struct TriTNode *lchild;/* 左孩子*/　　struct TriTNode *rchild;/* 右孩子*/　　}TriTree;　　typedef struct Node/* 隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)*/<b

11、>　　{ 　　TriTree *info;　　struct Node *next;　　}Node;　　typedef struct/* 鏈接隊(duì)列類型定義*/<

12、;b>　　{　　struct Node *front; /* 頭指針*/　　struct Node *rear; /* 尾指針*/　　}LinkQueue;　　DataType fname[MAXNUM],family[50]

13、[MAXNUM];/* 全局變量*/　　2.1.2 鏈隊(duì)的基本操作　　LinkQueue *LQueueCreateEmpty( )/* 建立一個(gè)空隊(duì)列*/　　{ 　　LinkQueue *plqu=(LinkQueue *)mal

14、loc(sizeof(LinkQueue));　　if (plqu!=NULL)　　plqu->front=plqu->rear=NULL;　　else　　{&

15、lt;p>　　printf("內(nèi)存不足！\n");　　return NULL;　　}　　return plqu;　　}　　in

16、t LQueueIsEmpty(LinkQueue *plqu)/* 判斷鏈接表示隊(duì)列是否為空隊(duì)列*/ 　　{　　return(plqu->front==NULL);　　}　　void LQ

17、ueueEnQueue(LinkQueue *plqu,TriTree *x)/* 進(jìn)隊(duì)列*/　　{ 　　Node *p=(Node *)malloc(sizeof(Node));　　if(p==NULL)　　printf("

18、;內(nèi)存分配失??！\n");　　else　　{ 　　p->info=x;　　p->next=NULL;　　if(plqu->fr

19、ont==NULL)/* 原來為空隊(duì)*/　　plqu->front=p;　　else　　plqu->rear->next=p;　　plqu->rear=p;<b&

20、gt;　　}　　}　　int LQueueDeQueue(LinkQueue *plqu,TriTree *x)/* 出隊(duì)列*/　　{ 　　Node *p;&

21、lt;/b>　　if(plqu->front==NULL)　　{　　printf("隊(duì)列空！\n");　　return ERROR;　　}&l

22、t;/b>　　else　　{ 　　p=plqu->front;　　x=p->info;　　plqu->front=plqu->

23、;front->next;　　free(p);　　return OK;　　}　　}　　TriTree *LQu

24、eueGetFront(LinkQueue *plqu)/* 在非空隊(duì)列中求隊(duì)頭元素*/　　{ 　　return(plqu->front->info);　　}　　2.

25、2建立家族關(guān)系　　2.2.1 建立家族關(guān)系并存入文件 　　基本思想：首先輸入家族關(guān)系的名稱，以此名稱為文件名，建立文本文件接下來按層次輸入結(jié)點(diǎn)信息，輸入一個(gè)在文件中寫入一行同時(shí)將輸入的信息保存 　　到二位字符數(shù)組family中。字符數(shù)組family是全局變量，存儲

26、臨時(shí)信息 . 注意，輸入時(shí)每個(gè)結(jié)點(diǎn)信息占一行，一個(gè)結(jié)點(diǎn)有多個(gè)兄弟，以“@”作為兄弟結(jié)束標(biāo)志，結(jié)點(diǎn)若無孩子，直接以“@”代替。依次輸入各節(jié)點(diǎn)信息，以“#” 作為結(jié)束標(biāo)志。最后使用函數(shù)CreateTriTree建立家族關(guān)系樹.　　TriTree *Create(DataType familyname[MAXNUM])/* 建立家族關(guān)系并存入文件*/<b

27、>　　{　　int i=0; /* i控制family數(shù)組下標(biāo)*/　　DataType ch,str[MAXNUM]; /* ch存儲輸入的y或n，str存儲輸入的字符串*/　　TriTree *t;<

28、;b>　　FILE *fp;　　strcpy(fname,familyname); /* 以家族名為文本文件名存儲*/　　strcat(fname,".txt");　　fp=fopen(fname,"r"); /* 以讀取方式打開文件

29、*/ 　　if(fp) /* 文件已存在*/　　{　　fclose(fp);　　printf("%s 的家族關(guān)系已存在！重新建立請按“Y”,直接打開請按“N”\n",fami

30、lyname);　　ch=getchar();　　getchar(); /* 接收回車*/　　if(ch=='N'||ch=='n')　　{<p&g

31、t;　　t=Open(familyname);/* 直接打開*/　　return t;　　}　　}　　if(!fp||ch=='Y'||ch=

32、='y') /* 重新建立，執(zhí)行以下操作*/　　{　　fp=fopen(fname,"w"); /* 以寫入方式打開文件，不存在則新建*/　　printf("請按層次輸入結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)信息占一行\(zhòng)n")

33、;　　printf("兄弟輸入結(jié)束以“@”為標(biāo)志，結(jié)束標(biāo)志為“#”\n. ");　　gets(str);　　fputs(str,fp);　　fputc('\n',fp);　　strcpy(fam

34、ily[i],str); /* 將成員信息存儲到字符數(shù)組中*/　　i++; /* family數(shù)組下標(biāo)后移*/　　while(str[0]!='#') 　　{　　print

35、f(". "); /* 以點(diǎn)提示符提示繼續(xù)輸入*/　　gets(str);　　fputs(str,fp); /* 寫到文件中，每個(gè)信息占一行*/　　fputc('\n',fp);　　strcpy(family[i],s

36、tr);/* 將成員信息存儲到字符數(shù)組中*/　　i++; /* family數(shù)組下標(biāo)后移*/　　}　　fclose(fp); /* 關(guān)閉文件*/　　t=TriTreeCre

37、ate(); /* 根據(jù)family數(shù)組信息創(chuàng)建三叉樹*/　　printf("家族關(guān)系已成功建立！\n");　　return t; /* 返回樹*/　　}　　}&

38、lt;/b>　　2.2.2建立家族關(guān)系樹　　基本思想：采用指針數(shù)組作為指針，保存輸入的結(jié)點(diǎn)地址。隊(duì)列的尾指針指向當(dāng)前結(jié)點(diǎn)。頭指針指向當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)。輸入的結(jié)點(diǎn)信息已存儲在字符數(shù)組family中。　　將信息復(fù)制到字符串?dāng)?shù)組“ch”中，如果"ch"不是“@”，則建立一個(gè)新結(jié)點(diǎn)。若新結(jié)點(diǎn)

39、是第一個(gè)結(jié)點(diǎn)，則它是根結(jié)點(diǎn)，將其入隊(duì)，指針tree指向這個(gè)根節(jié)點(diǎn)；如果不是根結(jié)點(diǎn)，則將當(dāng)前結(jié)點(diǎn)鏈接到雙親結(jié)點(diǎn)上，即當(dāng)前結(jié)點(diǎn)的雙親指針就是隊(duì)頭元素，然后將當(dāng)前結(jié)點(diǎn)入隊(duì)列。接著判斷flag的值，如果flag=0，表示當(dāng)前結(jié)點(diǎn)沒有左孩子，那么當(dāng)前結(jié)點(diǎn)就是雙親的左孩子。否則，當(dāng)前結(jié)點(diǎn)就是雙親的右孩子。用指針root指向剛剛?cè)腙?duì)的結(jié)點(diǎn)。繼續(xù)復(fù)制數(shù)組family的下個(gè)元素。如果“ch” 是@。則flag=0（因?yàn)椤癅”后面的第一個(gè)孩子為左孩子），同

40、時(shí)判斷“@”是否是第一次出現(xiàn)，如果是第一次，則令標(biāo)志star=1；如果不是第一次出現(xiàn)。則出隊(duì)列，root指向隊(duì)頭元素（實(shí)際上root總是指向雙親結(jié)點(diǎn)）。繼續(xù)復(fù)制family的下一個(gè)元素。知道遇到“#”結(jié)束。函數(shù)返回指針tree。　　/* 建立家族關(guān)系樹*/　　TriTree *TriTreeCreate()<

41、;b>　　{　　TriTree *t,*x=NULL,*tree,*root=NULL;　　LinkQueue *q=LQueueCreateEmpty();/* 建立一個(gè)空的隊(duì)列，存儲指向樹的指針*/　　int i=0,flag=0,start=0;<p&

42、gt;　　DataType str[MAXNUM]; /* 存放family數(shù)組中信息*/　　strcpy(str,family[i]); /* 復(fù)制*/　　i++; /* family數(shù)組下標(biāo)后移*/　　while(str[0

43、]!='#') /* 沒遇到結(jié)束標(biāo)志繼續(xù)循環(huán)*/　　{　　while(str[0]!='@') /* 沒遇到兄弟輸入結(jié)束標(biāo)志繼續(xù)*/　　{

44、;　　if(root==NULL) /* 空樹*/　　{　　root=(TriTree *)malloc(sizeof(TriTree));/* 申請空間*/　　strcpy(root->data,str);

45、　　root->parent=NULL;　　root->lchild=NULL;　　root->rchild=NULL;　　LQueueEnQueue(q,root); /* 將root存入隊(duì)列*/　　tree=r

46、oot;　　}　　else /* 不為空樹*/　　{　　t=(TriTree *)malloc(sizeof(TriTree)); /*

47、申請空間*/　　strcpy(t->data,str);　　t->lchild=NULL;　　t->rchild=NULL;　　t->parent=LQueueGetFront(q); /* 當(dāng)前結(jié)點(diǎn)的雙親為隊(duì)頭元素*/</p

48、>　　LQueueEnQueue(q,t); /* 入隊(duì)*/　　if(!flag) /* flag為，當(dāng)前結(jié)點(diǎn)沒有左孩子*/　　root->lchild=t;　　else /* flag為，當(dāng)前結(jié)點(diǎn)已有左孩子*/

49、　　root->rchild=t;　　root=t; /* root指向新的結(jié)點(diǎn)t */　　}　　flag=1; /* 標(biāo)記當(dāng)前結(jié)點(diǎn)已有左孩子*/　　st

50、rcpy(str,family[i]); 　　i++;　　}　　if(start!=0) /* 標(biāo)記不是第一次出現(xiàn)“@”*/　　{</b

51、>　　LQueueDeQueue(q,x); /* 出隊(duì)*/　　if(q->front!=NULL)　　root=LQueueGetFront(q);/* root為隊(duì)頭元素*/　　}</p

52、>　　start=1; /* 標(biāo)記已出現(xiàn)過“@”*/　　flag=0; /* “@”后面的結(jié)點(diǎn)一定為左孩子*/　　strcpy(str,family[i]);　　i++;<

53、/p>　　}　　return tree; /* 返回樹*/　　}　　2.3打開一個(gè)家族關(guān)系 　　首先輸入家族關(guān)系名，以

54、家族名為文件名打開文件，如果家族關(guān)系不存在，返回空；如果存在，文件打開，讀取文件。將文件的每行信息依次存儲在數(shù)組family【】中。　　/* 打開一個(gè)家族關(guān)系*/　　TriTree *Open(DataType familyname[MAXNUM])　　{

55、　　int i=0,j=0;　　DataType ch;　　FILE *fp;　　TriTree *t;　　strcpy(fname,familyname); /* 以家族名為文本文件名存儲*/</p&g

56、t;　　strcat(fname,".txt");　　fp=fopen(fname,"r"); /* 以讀取方式打開文件*/ 　　if(fp==NULL) /* 文件不存在*/

57、;　　{　　printf("%s 的家族關(guān)系不存在！\n",familyname);　　return NULL;　　}　　else&

58、lt;p>　　{　　ch=fgetc(fp); /* 按字符讀取文件*/　　while(ch!=EOF) /* 讀到文件尾結(jié)束*/　　{

59、if(ch!='\n') /* ch不為一個(gè)結(jié)點(diǎn)信息的結(jié)尾*/　　{　　family[i][j]=ch; /* 將文件信息存儲到family數(shù)組中*/　　j++; <

60、;b>　　}　　else　　{　　family[i][j]='\0'; /* 字符串結(jié)束標(biāo)志*/　　i++; /* fa

61、mily數(shù)組行下標(biāo)后移*/　　j=0; /* family數(shù)組列下標(biāo)歸零*/　　}　　ch=fgetc(fp); /* 繼續(xù)讀取文件信息*/　　}<

62、;/p>　　fclose(fp); /* 關(guān)閉文件*/　　t=TriTreeCreate(family); /* 調(diào)用函數(shù)建立三叉鏈表*/　　printf("家族關(guān)系已成功打開！\n");　　return t;<

63、/b>　　}　　}　　2.4在家族關(guān)系中查找一個(gè)成員是否存在　　用遞歸算法實(shí)現(xiàn)。如果樹空，返回NULL。如果根節(jié)點(diǎn)就是要查找的成員，返回根節(jié)點(diǎn)；否則，遞歸查找它的左右子樹。

64、;　　/* 查找一個(gè)成員是否存在*/　　TriTree *Search(TriTree *t,DataType str[]) 　　{　　TriTree *temp;　　if(t==NULL)

65、 /* 如果樹空則返回NULL */　　return NULL;　　else if(strcmp(t->data,str)==0) /* 如果找到返回該成員指針*/　　return t; 　　else

66、 /* 如果沒找到遍歷左右子樹進(jìn)行查找*/　　{　　temp=Search(t->lchild,str); /* 遞歸查找*/　　if(temp) /* 結(jié)點(diǎn)不空則查找*/　　retu

67、rn(Search(t->lchild,str));　　else　　return(Search(t->rchild,str));　　}　　}<

68、;/p>　　2.5 向家族中添加一個(gè)新成員　　基本思想：添加的新成員要根據(jù)其雙親確定其在家族中的位置。首先判斷該雙親是否在此家族關(guān)系中，若存在則查找其雙親，將新結(jié)點(diǎn)插入其雙親的最后一個(gè)孩子之后；若沒有孩子，則直接作為左孩子插入。以寫入的方式打開文件，如果成功打開，則更新family數(shù)組中的信息，并查找新成員的雙親所在位置和其對應(yīng)的“@”個(gè)數(shù)，如果“@”個(gè)數(shù)小于雙親位置

69、，則添加“@”實(shí)質(zhì)相等，新成員不插入到最后“@”之前。最后將family數(shù)組中信息寫入文件保存，關(guān)閉文件。　　/* 添加一個(gè)新成員*/　　void Append(TriTree *t)　　{　　int i=0,j,parpos=1,c

70、urpos,num,end=0,count=-1;　　DataType chi[MAXNUM],par[MAXNUM];/* 存儲輸入的孩子和其雙親結(jié)點(diǎn)*/　　TriTree *tpar,*temp;　　FILE *fp;　　prin

71、tf("請輸入要添加的成員和其父親，以回車分隔！\n. ");　　gets(chi);　　printf(". "); /* 以點(diǎn)提示符提示繼續(xù)輸入*/　　gets(par);　　tpar=Search(t,par);

72、 /* 查找雙親結(jié)點(diǎn)是否存在*/　　if(!tpar)　　printf("%s 該成員不存在！\n");　　else /* 存在則添加其孩子*/　　{</b&

73、gt;　　temp=(TriTree *)malloc(sizeof(TriTree));/* 申請空間*/　　temp->parent=tpar; 　　strcpy(temp->data,chi);　　temp->lchild

74、=NULL; /* 新結(jié)點(diǎn)左右孩子置空*/　　temp->rchild=NULL;　　if(tpar->lchild) /* 成員存在左孩子*/　　{　　tpar=tpar-

75、>lchild; /* 遍歷當(dāng)前成員左孩子的右子樹*/　　while(tpar->rchild) /* 當(dāng)前結(jié)點(diǎn)右孩子存在*/　　tpar=tpar->rchild; /* 繼續(xù)遍歷右孩子*/　　tpar->rchild=temp; /*

76、將新結(jié)點(diǎn)添加到所有孩子之后*/　　} 　　else /* 沒有孩子則直接添加*/　　tpar->lchild=temp;　　fp=fopen(fna

77、me,"w"); /* 以寫入方式打開文件*/　　if(fp)　　{　　while(strcmp(par,family[i])!=0&&family[i][0]!='#'

78、)　　{　　if(family[i][0]!='@') /* 查找雙親在數(shù)組中位置*/　　parpos++; /* parpos計(jì)數(shù)*/　　i++;

79、 /* family數(shù)組行下標(biāo)后移*/　　}　　i=0; /* family數(shù)組行下標(biāo)歸*/　　while(family[i][0]!='#')　　{&l

80、t;/b>　　if(family[i][0]=='@') /* 查找“@”的個(gè)數(shù)，第一個(gè)不計(jì)*/　　count++; /* count累加個(gè)數(shù)*/　　if(count==parpos) /* 說明此“@”與其前一個(gè)“@”之前

81、為par的孩子*/　　curpos=i; /* curpos計(jì)當(dāng)前位置*/　　i++; /* family數(shù)組行下標(biāo)后移*/　　}　　if(count<parpos)

82、 /* “@”數(shù)小于parpos數(shù)*/　　{　　num=parpos-count; /* 添加“@”個(gè)數(shù)為num */　　for(j=i;j<=i+num;j++) /* 從數(shù)組末尾添加“@”*/　　strcpy

83、(family[j],"@\0"); 　　strcpy(family[i+num+1],"#\0");/* “#”移到數(shù)組末尾*/ 　　strcpy(family[i+num-1],chi); /* 在最后一個(gè)“@”前添加新成員*/ 　　end=1;

84、 /* end為時(shí)標(biāo)記已添加*/ 　　}　　else　　{　　for(j=i;j>=curpos;j--) /* 當(dāng)前位置

85、到數(shù)組最后的全部信息后移一行*/　　strcpy(family[j+1],family[j]);　　strcpy(family[curpos],chi); /* 將新結(jié)點(diǎn)存儲到“@”的前一行*/　　}　　if(end==1) /*

86、若end為，則數(shù)組末尾下標(biāo)后移num位*/ 　　i=i+num;　　for(j=0;j<=i+1;j++) /* 將數(shù)組所有信息寫入文件*/　　{　　fputs(family[j],f

87、p);　　fputc('\n',fp); /* 一個(gè)信息存一行*/　　}　　fclose(fp); /* 關(guān)閉文件*/　　printf("添

88、加新成員成功！\n");　　}　　else　　printf("添加新成員失??！\n");　　}<p

89、>　　}　　2.6 家族成員關(guān)系的相關(guān)查詢　　2.6.1 查找一個(gè)家族的鼻祖　　判斷輸入的姓名是否在該家族中存在，如果存在，則返回該家族的根節(jié)點(diǎn)信息。　　/* 查找一個(gè)家族的祖先*/

90、void Ancesstor(TriTree *t) /* 返回樹的根結(jié)點(diǎn)信息*/　　{　　printf("該家族的祖先為%s\n",t->data);　　}<

91、p>　　2.6.2 查找一個(gè)成員的所有祖先路徑　　查找一個(gè)成員的所有祖先路徑，需要從它的雙親一直向上查找到根結(jié)點(diǎn)。　　基本思想：對與結(jié)點(diǎn)t，先判斷它是否是根結(jié)點(diǎn)（根節(jié)點(diǎn)的雙親是NULL），如果是根結(jié)點(diǎn)，直接輸出它本身；如果不是，查找它的雙親指針指向的結(jié)點(diǎn)，將雙親信息輸出。繼續(xù)查找，直到找到根結(jié)點(diǎn)。　　/*

92、查找一個(gè)成員的所有祖先*/　　void AncesstorPath(TriTree *t)　　{　　if(t->parent==NULL) /* 若該成員為祖先，則直接輸出*/　　printf("%s 無祖先！

93、\n",t->data);　　else /* 否則繼續(xù)查找祖先*/　　{　　printf("%s 所有祖先路徑：%s",t->data,t->data);

94、;　　while(t->parent!=NULL)/* 若當(dāng)前成員的雙親不是祖先，則繼續(xù)查找*/　　{　　printf(" --> %s",t->parent->data);/* 訪問當(dāng)前成員的雙親*/

95、t=t->parent; /* 繼續(xù)循環(huán)查找*/　　}　　printf("\n");　　}　　}

96、　　2.6.3 查找一個(gè)成員的雙親　　基本思想：先判斷結(jié)點(diǎn)t是否是根結(jié)點(diǎn)，過不是根結(jié)點(diǎn)，直接輸出該結(jié)點(diǎn)雙親指針的結(jié)點(diǎn)信息；若是根結(jié)點(diǎn)，輸出提示信息，結(jié)點(diǎn)無雙親。　　/* 查找一個(gè)成員的雙親*/　　void Parent(TriTree *t)<

97、;p>　　{　　if(t->parent!=NULL) /* 若該成員為祖先，則無雙親*/　　printf("%s 的雙親為%s\n",t->data,t->parent->data);　　else<

98、;/b>　　printf("%s 無雙親！\n",t->data);　　}　　2.6.4 確定一個(gè)成員是第幾代　　確定一個(gè)成員是第幾代，只要知道從它本身到根結(jié)點(diǎn)包括的祖先個(gè)數(shù)就可。因而對于跟結(jié)點(diǎn)t，從它

99、本身開始一直向上查找到根結(jié)點(diǎn)，查找的過程中用變量count（初值為1）計(jì)數(shù)，最后輸出 count。　　/* 確定一個(gè)成員是第幾代*/　　void Generation(TriTree *t)　　{　　int count=1;

100、 /* 計(jì)數(shù)*/　　DataType str[MAXNUM];　　strcpy(str,t->data); /* 存儲當(dāng)前信息*/　　while(t->parent!=NULL)/* 查找其雙親*/　　{<

101、/p>　　count++; /* 累加計(jì)數(shù)*/　　t=t->parent;　　}　　printf("%s 是第%d 代！\n",str,count);<b&

102、gt;　　}　　2.6.5 查找一個(gè)成員的兄弟　　一個(gè)成員的為其雙親除了該成員以外的所有孩子。　　基本思想：對于結(jié)點(diǎn)t，先判斷它是否是跟結(jié)點(diǎn)，若是根結(jié)點(diǎn)，則無兄弟；若不是根結(jié)點(diǎn)，則找到結(jié)點(diǎn)t的雙親。接著判斷雙親的左孩子和左孩子的兄弟是否都存在（若只有左孩子，左孩子就是要查找的這個(gè)成員），如果都

103、不存在，則無兄弟；如果都存在，對雙親的左孩子操作。若左孩子不是要查找的這個(gè)成員，則將結(jié)點(diǎn)信息輸出。接下來查找左孩子的右兄弟，判斷當(dāng)前結(jié)點(diǎn)是否是要查找的這個(gè)成員，若不是，則將結(jié)點(diǎn)信息輸出，繼續(xù)查找當(dāng)前結(jié)點(diǎn)的右兄弟，直到NULL為止。　　/* 查找一個(gè)成員的兄弟*/　　void Brothers(TriTree *t,DataType str[]) /

104、* 查找兄弟*/　　{ 　　if(t->parent!=NULL) /* 若該結(jié)點(diǎn)是祖先，則無兄弟*/　　{　　t=t->parent;

105、 /* 該結(jié)點(diǎn)的兄弟即為其雙親除該成員以外的所有孩子*/　　if(t->lchild&&t->lchild->rchild) /* 當(dāng)前結(jié)點(diǎn)的左孩子及其右孩子都存在*/　　{　　printf("%s 的所有兄弟有：

106、",str);　　t=t->lchild; 　　while(t) /* 遍歷當(dāng)前成員左孩子的右子樹*/　　{ 　　if(strcmp(t->data,str)!=

107、0) /* 遍歷右子樹，選擇輸出*/　　printf("%s ",t->data); /* 訪問當(dāng)前結(jié)點(diǎn)*/　　t=t->rchild;　　}　　printf("\n");<

108、;/p>　　}　　else　　printf("%s 無兄弟！\n",str);　　}　　el

109、se　　printf("%s 無兄弟！\n",str);　　}　　2.6.6 查找一個(gè)成員的堂兄弟　　一個(gè)成員的堂兄弟為其雙親的雙親結(jié)點(diǎn)的所有孩子的孩子（該成員除外）.

110、　　基本思想：如果結(jié)點(diǎn)t的雙親和雙親的雙親（爺爺）都存在，首先考慮爺爺?shù)淖蠛⒆?。如果爺爺?shù)淖蠛⒆硬皇墙Y(jié)點(diǎn)t的雙親，那么爺爺還有其他孩子。現(xiàn)對爺爺?shù)淖蠛⒆拥淖蠛⒆釉L問，如果不是結(jié)點(diǎn)t就輸出。同樣，對爺爺左孩子的左孩子的右孩子、右孩子的右孩子一直訪問下去，直到無右孩子為止。如果爺爺還有其他孩子，那么就對爺爺?shù)淖蠛⒆拥挠液⒆?、爺爺?shù)淖蠛⒆拥挠液⒆拥挠液⒆?-----即對爺爺?shù)钠渌⒆幼鱿嗤奶幚怼?lt;/p>&l

111、t;p>　　/* 查找一個(gè)成員的堂兄弟*/　　void Consin(TriTree *t)　　{　　int flag=0;　　TriTree *ch=t;　　TriTree *temp

112、;　　if(t->parent&&t->parent->parent)/* 當(dāng)前結(jié)點(diǎn)的雙親及其雙親都存在*/　　{　　t=t->parent->parent->lchild;/* 當(dāng)前結(jié)點(diǎn)等于其祖先的第一個(gè)孩子*/</

113、p>　　while(t) /* 存在則繼續(xù)查找*/ 　　{ 　　if(strcmp(t->data,ch->parent->data)!=0)/* 不是同一結(jié)點(diǎn)*/<

114、;p>　　{　　if(t->lchild) /* 當(dāng)前結(jié)點(diǎn)存在左孩子*/　　{　　temp=t->lchild;　　while(temp)

115、 /* 遍歷當(dāng)前結(jié)點(diǎn)左孩子的右子樹*/　　{ 　　if(strcmp(temp->data,ch->data)!=0)　　{　　if(!flag)

116、 /* 第一次輸入時(shí)先輸出下句*/　　printf("%s 的所有堂兄弟有：",ch->data);　　printf("%s ",temp->data);/* 訪問當(dāng)前成員*/　　flag=1;&

117、lt;p>　　}　　temp=temp->rchild; /* 繼續(xù)遍歷右孩子*/　　}　　}　　}<

118、;/b>　　t=t->rchild; /* 繼續(xù)遍歷右孩子*/　　}　　printf("\n");　　}&

119、lt;p>　　if(!flag) /* 標(biāo)志沒有輸出結(jié)點(diǎn)*/　　printf("%s 無堂兄弟！\n",ch->data);　　}　　2.6.7 查找一個(gè)成員的所有孩子　　一個(gè)成員的所有孩

120、子包括左孩子和左孩子的右孩子、左孩子的右孩子的右孩子----直到右孩子為空為止。　　基本思想：首先判斷結(jié)點(diǎn)t是否有左孩子，如果沒有，輸出沒有孩子；如果有左孩子，輸出左孩子的信息，然后判斷左孩子的右孩子是否為空，若不為空（存在右孩子），輸出左孩子的右孩子的信息，接著循環(huán)判斷結(jié)點(diǎn)是否有右孩子，有就輸出，直到右孩子為空。　　/* 查找一個(gè)成員的所有孩子*/&l

121、t;/p>　　void Children(TriTree *t) /* 遍歷左孩子*/　　{ 　　if(t->lchild) /* 當(dāng)前結(jié)點(diǎn)存在左孩子*/　　{</b&g

122、t;　　printf("%s 的所有孩子有：",t->data);　　t=t->lchild; /* 遍歷當(dāng)前成員左孩子的右子樹*/　　while(t) /* 不空*/ <

123、b>　　{ 　　printf("%s ",t->data);/* 訪問當(dāng)前成員*/　　t=t->rchild; 　　}　　printf("\n");

124、　　}　　else　　printf("%s 無孩子！\n",t->data);　　}　　/

125、* 中序遍歷一棵樹*/　　void InOrder(TriTree *t) 　　{　　if(t) /* 二叉樹存在*/　　{</p&g

126、t;　　InOrder(t->lchild); /* 中序遍歷左子樹*/　　printf("%s ",t->data);/* 訪問成員*/　　InOrder(t->rchild); /* 中序遍歷右子樹*/　　}</

127、b>　　}　　2.6.8 查找一個(gè)成員的子孫后代　　一個(gè)成員的子孫后代就是其左子樹上的所有結(jié)點(diǎn)，所以對其左子樹進(jìn)行中序遍歷即可。　　/* 查找一個(gè)成員的子孫后代*/ 　　void De

128、scendants(TriTree *t) /* 遍歷左孩子*/　　{ 　　if(t->lchild) /* 當(dāng)前結(jié)點(diǎn)存在左孩子*/　　{　　printf(&q

129、uot;%s 的所有子孫后代有：",t->data);　　InOrder(t->lchild); /* 中序遍歷當(dāng)前結(jié)點(diǎn)的左右子樹*/　　printf("\n");　　}

130、　　else　　printf("%s 無后代！\n",t->data);　　}　　2.7 各軟件之間的調(diào)用方式　　該軟件各個(gè)模塊的調(diào)用主要是通過聲明函數(shù)，和定義函數(shù) 再通過主函數(shù)調(diào)用實(shí)現(xiàn)的

131、。　　主函數(shù)：　　/* 主控函數(shù)*/　　int main(int argc,char* argv[])　　{　　Da

132、taType str[MAXNUM]="\0",input[40];　　int i,j,flag,start=0,pos,tag1,tag2;　　TriTree *temp,*tree=NULL;　　while(1)

133、;　　{　　printf("\t歡迎使用家族關(guān)系查詢系統(tǒng)！\n");　　printf("\t請輸入與之匹配的函數(shù)和參數(shù)，如parent(C)\n");　　printf("\t 1.新建一個(gè)家庭關(guān)系： Create(fa

134、milyname) 參數(shù)為字符串\n");　　printf("\t 2.打開一個(gè)家庭關(guān)系： Open(familyname) 參數(shù)為字符串\n");　　printf("\t 3.添加新成員的信息： Append() 無參數(shù)\n");

135、　　printf("\t 4.查找一個(gè)成員的祖先： Ancesstor(name) 參數(shù)為字符串\n");　　printf("\t 5.查找一個(gè)成員的祖先路徑：AncesstorPath(name) 參數(shù)為字符串\n");　　printf("\t 6.確定一個(gè)成員是第幾

136、代： Generation(name) 參數(shù)為字符串\n");　　printf("\t 7.查找一個(gè)成員的雙親： Parent(name) 參數(shù)為字符串\n");　　printf("\t 8.查找一個(gè)成員的兄弟： Brothers(name) 參數(shù)為字符串\n"

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載