數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報(bào)告

1、鄭州輕工業(yè)學(xué)院課程設(shè)計(jì)任務(wù)書題目專業(yè)、班級(jí) 軟件外包11-01 學(xué)號(hào) 541107080145 姓名 周朱莉主要內(nèi)容、基本要求、主要參考資料等： 主要內(nèi)容:建立家族關(guān)系數(shù)據(jù)庫(kù)，實(shí)現(xiàn)對(duì)家族成員關(guān)系的相關(guān)查詢基本要求：（1）建立家族關(guān)系并能存儲(chǔ)到文件中；（2實(shí)現(xiàn)家族成員的添加。（3）可以查詢家族成員的雙親、祖先、兄弟、孩子和后代等信息。課程設(shè)計(jì)按照教學(xué)要求需要一周時(shí)間完成，總共要上機(jī)調(diào)試程序 10小時(shí) 對(duì)每個(gè)題目要有需求分析， 在需求分析中，將題目中要求的功能進(jìn)行敘述分析， 并且設(shè)計(jì)解決此問題的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)或敘述解決此問題的算法，描述算 法建議使用流程圖，進(jìn)行算法分析指明關(guān)鍵語(yǔ)句的時(shí)間復(fù)雜度

2、。給出實(shí)現(xiàn)功能 的一組或多組測(cè)試數(shù)據(jù)，程序調(diào)試后，將按照此測(cè)試數(shù)據(jù)進(jìn)行測(cè)試的結(jié)果列出 來。源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量， 重點(diǎn)功能部分要加上清晰的程序注釋。程序能夠運(yùn)行，要有基本的容錯(cuò)功能。盡量避免出現(xiàn)操作錯(cuò)誤時(shí)出現(xiàn)死循環(huán)；主要參考資料：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），在網(wǎng)上查詢的相關(guān)資料及部 分代碼完成期限：2013618-2013620指導(dǎo)教師簽名： 課程負(fù)責(zé)人簽名：2013年6 月 18日鄭州輕工業(yè)學(xué)院本科數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報(bào)告設(shè)計(jì)題目 ：家族關(guān)系查詢系統(tǒng) 學(xué)生姓名 ：周朱莉 系 別：計(jì)算機(jī)與通信工程 專 業(yè)：軟件外包 班 級(jí)： 11-01 學(xué) 號(hào)： 54110

3、7080145 指導(dǎo)教師 ：盧冰2013 年 6 月 20 日一、設(shè)計(jì)題目（任選其一）家族關(guān)系查詢系統(tǒng)二、運(yùn)行環(huán)境（軟、硬件環(huán)境）電腦及 Visual C+6.0三、算法設(shè)計(jì)的思想隨著社會(huì)發(fā)展，人們使用紙質(zhì)的家譜已經(jīng)非常不方便 而且不利于在家譜里進(jìn)行添加和修改。而用算法設(shè)計(jì)一個(gè) 家族關(guān)系查詢系統(tǒng)則可以解決這個(gè)問題。數(shù)據(jù)結(jié)構(gòu)的二叉 樹剛好滿足家譜的基本結(jié)構(gòu)。首先建立一個(gè)文件作為家譜，然后在文件中輸入字符 串，實(shí)現(xiàn)了在文件中按照數(shù)據(jù)的邏輯關(guān)系進(jìn)進(jìn)輸入便可建 立相應(yīng)的三叉鏈表。然后就是進(jìn)行數(shù)據(jù)的存儲(chǔ)、刪除及查 找工作。四、算法的流程圖家譜的創(chuàng)建:開始輸入家譜名稱輸入家族成員結(jié)束載入家譜:開始輸入家譜

4、名家譜是否存在?家譜打開失敗載入成功結(jié)束修改家譜:開始選擇刪除成員添加成員返回上一級(jí)結(jié)束輸入成員姓名成員是否存在?刪除成功成員查詢:開始輸入成員名成員是否存在?輸出成員信息結(jié)束五、算法設(shè)計(jì)分析本次設(shè)計(jì)研究的是建立家族關(guān)系，實(shí)現(xiàn)對(duì)家族成員 關(guān)系相關(guān)查詢的問題。在設(shè)計(jì)中使用的數(shù)據(jù)結(jié)構(gòu)為樹狀結(jié) 構(gòu)，樹狀結(jié)構(gòu)采用三叉鏈表實(shí)現(xiàn)。我們?cè)诮⒑眉易尻P(guān)系 后將其存儲(chǔ)在文件中，在文件中家族關(guān)系是以樹的形式存 儲(chǔ)，運(yùn)用樹的操作使家族關(guān)系得以準(zhǔn)確建立。家族關(guān)系查詢系統(tǒng)可分為六大模塊，分別是創(chuàng)建、修改、查詢、保 存、退出等。建立家族關(guān)系模塊，建立家族關(guān)系并存入文 件。建立時(shí)首先輸入家族關(guān)系的名稱，以此名稱為名建立 文

5、本文件。接下來按層輸入成員姓名，輸入一個(gè)在文件中 寫入一個(gè)字符串，以回車鍵結(jié)束。打開一個(gè)家族關(guān)系。在界面輸入選項(xiàng)名，以家族關(guān)系名為文件名打開文件，如果家族關(guān)系不存在，返回空；如果存在，打開文件，讀取文件。向家族中添加一個(gè)新成員，添加的新成員要根據(jù)其父親確定其在家族中的位置。首先判斷該父親是否在此家族關(guān)系中，若存在，則查找其父親，將新節(jié)點(diǎn)插入其父親的最后一個(gè)孩子之后；若沒有孩子，直接作為左孩子插入。以寫入的方式打開文件，更新數(shù)組中的信息，然后將數(shù)組中的信息寫入文件保存，關(guān)閉文件。查找功能模塊，查找一個(gè)成員的所有祖先及其兄弟，查找一個(gè)成員的所有祖先路徑，需要從它的父親一直向上查找?guī)ЦY(jié)點(diǎn)。查找一個(gè)

6、成員的兄弟，一個(gè)成員的兄弟為其父親除了該結(jié)點(diǎn)以外的所有孩子。對(duì)于要操作的結(jié)點(diǎn)，先判斷它是否是根結(jié)點(diǎn)，若是根結(jié)點(diǎn)，則無兄弟；若不是根結(jié)點(diǎn)，則找到該結(jié)點(diǎn)的父親。接著判斷父親的兄弟是否都存在，如果都不存在， 則無兄弟；如果都存在，對(duì)父親的孩子操作。六、源代碼#include#include#include#includetypedefcharTElemType;typedefint status;typedefstructBiTPNodeTElemTypedata10;struct BiTPNode *parent,*lchild,*rchild; /父親及左 右孩子指針BiTPNode,*BiPT

7、ree;BiPTreeP;BiPTreeT;/家譜的創(chuàng)建int Cre()system(cls);FILE *fp; /聲明指向文件的指針 char filename40,str10;printf(請(qǐng)輸入家譜名稱:)；getchar();gets(filename)；輸入家譜名稱 while(filename0=NULL)printfC喙譜名不能為空，請(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(strle

8、n(gets(str)0)fputs(str,fp)/向文件寫入字符串putc(n,fp);fclose(fp)/關(guān)閉文件printf(按任一鍵繼續(xù)!);getch();return 1; statusloc(BiPTreeT,BiPTree&P,TElemTypename10)if(T)P=T;/字符串的比較if(!strcmp(name,T-data)r)eturn 1;if(loc(T-lchild,P,name)r)eturn 1;if(loc(T-rchild,P,name)r)eturn 1;elsereturn 0;/構(gòu)造二叉樹statusinittree(BiPTree&T)T

9、=(BiTPNode*)malloc(sizeof(BiTPNode); if(T)return 0;T-lchild=NULL;T-rchild=NULL;T-parent=NULL;return 1;statusCrt(BiPTree&T)FILE *fp;BiPTreeQ,R,M,N; char filename40,name10;system(cls)/ 清屏R=(BiTPNode *)malloc(sizeof(BiTPNode)分配存 儲(chǔ)空間M=(BiTPNode*)malloc(sizeof(BiTPNode);N=(BiTPNode*)malloc(sizeof(BiTPNod

10、e); printf(請(qǐng)輸入家譜名:);getchar(); gets(filename);while(filename0=NULL)printfC喙譜名不能為空，請(qǐng)重新輸入:)； gets(filename); if(fp=fopen(filename,r)=NULL)printf(%s 家譜打開失敗!n,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(f

11、ilename,r)=NULL)printf(% 家譜打開失敗!n,filename);return 0;fscanf(fp,%s,name);while(!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;elseif(!loc(T,P,name)Q=(BiTPNode*)malloc(sizeof(BiTPNode);R=N

12、;R=R-lchild;while(R)M=R;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；statusin(BiPTree&T)char father10,name10;BiPTreeQ,M;system(cls);printf(請(qǐng)輸入要添加到該家譜中的人的父親姓名：);getchar();gets(father);while(!loc(T,P,father

13、)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-lchild=NULL;Q-rchild=NULL;if(!P-lchild)P-lchild=Q;Q-parent=P;elseP=P-lchild;while(P)M=P;P=P-rchild;M-rchild=Q;Q-parent=M;

14、printf(成員添加成功，按任一鍵繼續(xù)!);getch();return 1;/刪除成員 statusde(BiPTree&T)char name10;system(cls);printf(請(qǐng)輸入要?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;elseP-parent-rchild=NULL;free(P);elseif(P-rchild

15、)if(P-parent-lchild=P) P-parent-lchild=P-rchild;elseP-parent-rchild=P-rchild;free(P);printf(成員刪除成功，按任一鍵繼續(xù)!)；getch();return 1；statusShow(TElemTypee10)printf(%s ,e)；return 1;/二叉樹的遍歷 statuspre(BiPTreeT,status(*visit)(TElemType10) if(T) if (*visit)(T-data)if (pre(T-lchild,visit)if (pre(T-rchild,visit)re

16、turn 1;return 0;elsereturn 1;/家族成員查詢 statusSea(BiPTreeT) char name10; BiPTreeN; N=(BiTPNode*)malloc(sizeof(BiTPNode); system(cls);printf( 請(qǐng)輸入要查尋的人的姓名 :); getchar();gets(name);while(!loc(T,P,name)printf(%s 不在該家譜中 !請(qǐng)重新輸入 :,name); gets(name);N=P;if(P=T)printf(%s 的父親在該家譜中沒有記載 !n,P- data);elsewhile(N-par

17、ent-rchild=N) N=N-parent;printf(%s 的父親是:sn,P-data,N-parent-data);N=P;if(P=T)printf(%s 沒有兄弟!n,P-data);elseif(!P-rchild&P-parent-rchild!=P) printf(%s 沒有兄弟!n,P-data);elseprintf(%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-

18、parent;printf(n);if(P=T)printf(%s 的祖先在該家譜中沒有記載 !n,name);elseprintf(%s 的祖先是:sn,name,T-data);N=P;if(!P-lchild)printf(%s 沒有孩子!n,name);printf(%s 沒有后代n,name);elseprintf(%s 的孩子有:n,name);printf(%s ,P-lchild-data);N=N-lchild;while(N-rchild)printf(%s ,N-rchild-data);N=N-rchild;printf(n);printf(%s 的后代有:n,name

19、);pre(P-lchild,Show);printf(n);printf(按任一鍵繼續(xù)!);getch();return 1;/文件的創(chuàng)建statuswrite(BiPTreeT,charfilename40)FILE *fp;if(fp=fopen(filename,a+)=NULL)printf(%s 文件創(chuàng)建失敗!n,filename);return 0;fprintf(fp,%s ,T-data);THTvohi_d;whi_e(THfprin5fp=%s=TvdaET) 一THTvlxhi一d; fln5fp=一 IT)；葺圧 fc-ose(fp)； rauln 1;ssrf us

20、 prewrife(BipT ree Ta)Erfus(*.sio(BipTreeohal!42)ohml1enamet40x5T)宀if CRVohi一d)(*visio(TJi_ename)； prewrife(Tvohi-a.sFfi-ename)； prewrife(Tvrchi-dy.sFfi-ename)； raUITM; e-seraUITH;statuswrong()char a;scanf(%c,&a);printf(無此選項(xiàng),請(qǐng)重新選擇!(按任一鍵繼 續(xù)!);getch();return 1;/家譜的存儲(chǔ) statusSav(BiPTreeT)FILE *fp; charf

21、ilename40; system(cls);printf(請(qǐng)輸入新的文件名：);getchar(); gets(filename);while(filename0=NULL)printfC喙譜名不能為空，請(qǐng)重新輸入gets(filename);prewrite(T,write,filename);printf(%s家譜保存成功，按任一鍵繼續(xù)filename);getch();return 1;/修改家譜statusUpd() system(cls);intxz;while(1) system(cls);printf(nnnn);printf(*A A*)家族成員的添加與刪除操作(*A A*)

22、n);printf( (*A A*)請(qǐng)選擇(*a A*)n,1)；printf( (*A A*)1.添加成員 .(*a A*)n,1)；printf( (*A A*)2.刪除成員.(*A A*)n, );printf( (*a a*)3.返回上一級(jí).(*A A*)n, );printf(請(qǐng)選擇 :);scanf(%d,&xz); switch(xz)case1 : in(T);break;case2 : de(T);break;case3 : return 0; default: wrong();break;main()P=(BiTPNode*)malloc(sizeof(BiTPNode);int xz;while(1) system(cls);printf(nnnn);printf(*A 八*)家族關(guān)系查詢系統(tǒng)(*A A*)n);printf(*A A*)具體操作如下(*A A*)n);printf(*A a*)1.創(chuàng)建家譜.(*A A*)n);printf(*A A*)2.載入家譜.(*A A*)n);printf(*A A*)3.修改家譜.(*A A*)n);pri