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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 身份證信息管理系統(tǒng) 學(xué)院：理學(xué)院專業(yè)：信息與計(jì)算科學(xué)班級(jí)：學(xué)號(hào)：3姓名：指導(dǎo)老師：姜俊坡需求分析 通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程，我們學(xué)習(xí)了很多存儲(chǔ)數(shù)據(jù)的方法，當(dāng)然不同的方法對(duì)于對(duì)數(shù)據(jù)的查找有不同的效率。本課題要求建立一個(gè)身份證信息管理系統(tǒng)，并使其能夠進(jìn)行身份證的錄入、查找、修改、刪除。身份證信息管理系統(tǒng)可以由多種方法構(gòu)造，如進(jìn)行散列表的建立、查找、打印等。但是由于身份證號(hào)碼的唯一性，考慮到查找的效率，采用二叉排序樹可以獲得較高的查找效率，所以我采用二叉排序樹進(jìn)行身份證信息的存儲(chǔ)。根據(jù)分析，本課題需要完成的具體功能有：（1） 能夠進(jìn)行身份證號(hào)碼及相關(guān)信息的錄入，相關(guān)信息包括姓名

2、、地址和手機(jī)號(hào)碼；（2） 能夠盡快進(jìn)行身份證號(hào)碼的查詢，并輸入出相關(guān)信息；（3） 可以修改身份證號(hào)碼對(duì)應(yīng)的其他信息，如姓名、地址；（4） 可以完成身份證信息的刪除。 總體設(shè)計(jì) 根據(jù)需求分析結(jié)果確定程序的總體設(shè)計(jì)，首先在每個(gè)功能中都有輸入和輸出，所以設(shè)計(jì)時(shí)需要采用交互方式。通過編寫一個(gè)主菜單功能來實(shí)現(xiàn)添加身份信息、修改身份證信息、刪除身份證信息、查詢身份證信息等各個(gè)功能模塊的調(diào)用，從而更好地協(xié)調(diào)各個(gè)功能模塊之間的關(guān)系。根據(jù)功能分析確定的系統(tǒng)功能模塊如下圖所示。 主界面 添加身份證信息刪除身份證信息 修改身份證信息查找身份證信息輸出全部信息退出系統(tǒng) 設(shè)計(jì)思路1. 利用到的知識(shí)點(diǎn)（1） 二叉排序樹的

3、建立；（2） 二叉排序樹的查找；（3） 二叉排序樹的刪除。2. 詳細(xì)的設(shè)計(jì)思想（1） 采用的數(shù)據(jù)結(jié)點(diǎn)和存儲(chǔ)結(jié)構(gòu)經(jīng)過分析，身份證相關(guān)信息需要包括身份證號(hào)、姓名、地址和電話。身份證號(hào)碼采用18位字符，姓名考慮采用10位字符，地址采用20位字符，電話不是必須填寫的，采用字符存儲(chǔ)。二叉排序樹或者是一顆空樹，或者是具有下列性質(zhì)的二叉樹： 如果左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； 如果右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； 它的左右子樹也分別為二叉排序樹。對(duì)于一個(gè)記錄集合，可以用一顆二叉排序樹來表示，樹中的一個(gè)結(jié)點(diǎn)對(duì)應(yīng)與集合中 的一個(gè)記錄，整棵樹表示該記錄集合。二叉排

4、序樹中每個(gè)結(jié)點(diǎn)所存儲(chǔ)的記錄，其關(guān)鍵字都大于它的左子樹上所有結(jié)點(diǎn)存儲(chǔ)的記錄的關(guān)鍵字，而小于它的右子樹上所有結(jié)點(diǎn)存儲(chǔ)的記錄的關(guān)鍵字。用二叉排序樹表示記錄集合時(shí)，不但容易進(jìn)行動(dòng)態(tài)查找，而且對(duì)二叉排序樹進(jìn)行中序遍歷時(shí)還可以得到記錄集合中各記錄的有序排列。 二叉排序樹的存儲(chǔ)結(jié)構(gòu)采用二叉鏈表存儲(chǔ)方式。本課題中存儲(chǔ)身份證信息時(shí)的結(jié)點(diǎn)和存儲(chǔ)結(jié)構(gòu)如下圖所示： 身份證號(hào)姓名住址電話 身份證號(hào)姓名住址電話身份證號(hào)姓名住址電話 （2）采用的算法查找算法。由于身份證號(hào)碼的唯一性，查找算法以身份證號(hào)碼為關(guān)鍵字進(jìn)行。a） 當(dāng)二叉排序樹為空時(shí)，查找失敗。b）如果二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字等于要查找的關(guān)鍵字時(shí)，則查找成功。c）如

5、果二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字小于要查找的關(guān)鍵字，則有同樣的方法繼續(xù)在根結(jié)點(diǎn)的右子樹上查找。d）如果二叉排序樹根結(jié)點(diǎn)的關(guān)鍵字大于要查找的關(guān)鍵字，則有同樣的方法繼續(xù)在根結(jié)點(diǎn)的左子樹上查找。 在根結(jié)點(diǎn)為p的二叉排序樹中，查找身份證號(hào)碼為id的結(jié)點(diǎn)，算法流程圖如下所示：開始 結(jié)束p=p-rchild p=p-lchild查找不成功，返回結(jié)點(diǎn)空指針p平PPPPP-KONGP指針P查找成功，返回結(jié)點(diǎn)指針pId大于所指的結(jié)點(diǎn)id的？p不空？ 否 id小于所指的結(jié)點(diǎn)id的？ 是 否 是 是對(duì)含有n個(gè)結(jié)點(diǎn)的二叉排序樹來說，在樹上查找結(jié)點(diǎn)的關(guān)鍵字等于某個(gè)給定值的過程走的是一條從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑，所需要做的比較次

6、數(shù)等于該結(jié)點(diǎn)所在的層數(shù)。因此，平均查找長(zhǎng)度不僅和結(jié)點(diǎn)的個(gè)數(shù)n有關(guān),更為重要的是樹的形態(tài)有關(guān)。在最好的情況下，二叉排序樹的形態(tài)和折半查找的判定樹相同，其平均查找長(zhǎng)度為0(log2n),在最壞的情況下(單枝樹)，平均查找長(zhǎng)度為(n+1)/2。所以在構(gòu)造二叉樹排序樹時(shí)的輸入順序也很重要，一般來說，輸入的順序越無序，構(gòu)造出的二叉樹排序樹越利于查找。 插入算法。在二叉排序樹中插入新的結(jié)點(diǎn)時(shí)，必須要保證插入后的二叉樹任然滿足二叉排序樹的定義。因此，插入時(shí)必須首先找出合適的插入位置。實(shí)際上，待插入結(jié)點(diǎn)的位置就會(huì)死在查找過程中所查找的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子，新插入的結(jié)點(diǎn)一定是葉子結(jié)點(diǎn)。因此，仍可采用上述

7、查找算法。當(dāng)查找失敗時(shí)，在二叉排序樹中插入關(guān)鍵字等于給定值的結(jié)點(diǎn)。插入的過程如下：a） 若二叉排序樹為空樹，則將新插入的結(jié)點(diǎn)作為根結(jié)點(diǎn)插入。b） 若二叉排序樹的根結(jié)點(diǎn)關(guān)鍵字值等于要插入的結(jié)點(diǎn)的關(guān)鍵字，則返回。c） 若要插入結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)關(guān)鍵字，則把要插入的結(jié)點(diǎn)插入到左子樹中。d） 若要插入結(jié)點(diǎn)的關(guān)鍵字大于根結(jié)點(diǎn)關(guān)鍵字，則把要插入的結(jié)點(diǎn)插入到右子樹中。 在子樹中插入的方法與在整棵樹中插入的方法是相同的，如此下去，直到把要插入的結(jié)點(diǎn)插入到二叉排序樹中或發(fā)現(xiàn)樹中已有此關(guān)鍵字為止。 刪除算法。與在二叉排序樹上做插入操作的要求一樣，從二叉排序樹中刪除一個(gè)結(jié)點(diǎn)，要保證刪除后的二叉樹仍然是一顆二叉排

8、序樹。根據(jù)二叉排序樹的結(jié)構(gòu)特征，可以分一下4種情況來考慮。a） 待刪除的結(jié)點(diǎn)都是葉結(jié)點(diǎn)。直接刪除該結(jié)點(diǎn)。b） 待刪除的結(jié)點(diǎn)只有左子樹，而無右子樹。根據(jù)二叉排序樹的特點(diǎn)，在這種情況下可以直接將其左子樹的根結(jié)點(diǎn)放到被刪除結(jié)點(diǎn)的位置。c） 待刪除的結(jié)點(diǎn)只有右子樹，而無左子樹。根據(jù)二叉排序樹的特點(diǎn)，在這種情況下可以直接將其右子樹的根結(jié)點(diǎn)放到被刪除結(jié)點(diǎn)的位置。 d）待刪除的結(jié)點(diǎn)同時(shí)有左、右子樹。根據(jù)二叉排序樹的特點(diǎn)，可以將其右子樹放到被刪除結(jié)點(diǎn)的位置上，再把被刪除的結(jié)點(diǎn)的左子樹鏈接到被刪除結(jié)點(diǎn)右子樹的最左子樹的左孩子結(jié)點(diǎn)上；也可以直接將被刪除結(jié)點(diǎn)的左孩子代替被刪除的結(jié)點(diǎn)，同時(shí)將被刪除的結(jié)點(diǎn)的右子樹收為被

9、刪除結(jié)點(diǎn)左子樹中序尾結(jié)點(diǎn)的右孩子。 程序代碼.數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)根據(jù)分析確定結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)包含4部分，即身份證號(hào)碼、姓名、地址和電話。typedef struct char id19; char name11; char address21; char phone12;Keytype;存儲(chǔ)時(shí)采用二叉排序樹，結(jié)點(diǎn)包含身份證系統(tǒng)的信息以及左子樹指針和右子樹指針。typedef struct BSNode Keytype key;struct BSNode*lchild;struct BSNode*rchild;bsnodetype;.功能函數(shù)設(shè)計(jì)btree bssearch(btree p,ch

10、ar *id) /二叉樹排序中查詢結(jié)點(diǎn)的查找算法void insert(btree *root,char*id) /插入算法void inorder(btree t) /按照中序遍歷的方式輸出二叉樹btree createbtree(void) /創(chuàng)建二叉樹的算法btree Delete(btree bt,char *id) /刪除結(jié)點(diǎn)的算法.程序?qū)崿F(xiàn)#include#include#includetypedef struct char id19; char name11; char address21; char phone12;Keytype;typedef struct BSNode K

11、eytype key;struct BSNode*lchild;struct BSNode*rchild;bsnodetype;typedef bsnodetype *btree;btree bssearch(btree p,char *id)while(p)if(strcmp(id,p-key.id)lchild;else if(strcmp(id,p-key.id)0)p=p-rchild;elsereturn p; return p;void insert(btree *root,char*id) btree f,p;char name10,address20,phone11;f=NUL

12、L;p= *root;while(p) if(strcmp(id,p-key.id)=0)printf(該號(hào)碼已經(jīng)存在，不能插入n);return;f=p;p=(strcmp(id,p-key.id)lchild:p-rchild;p=(btree)malloc(sizeof(bsnodetype);strcpy(p-key.id,id);printf(請(qǐng)輸入10個(gè)字符之內(nèi)的姓名n);scanf(%s,name);strcpy(,name);printf(請(qǐng)輸入20個(gè)字符之內(nèi)的地址n);scanf(%s,address); strcpy(p-key.address,addr

13、ess);printf(請(qǐng)輸入11個(gè)字符之內(nèi)的電話n);scanf(%s,phone); strcpy(p-key.phone,phone);p-lchild=NULL;p-rchild=NULL;if(*root=NULL)*root=p;elseif(strcmp(id,)lchild=p;elsef-rchild=p;void inorder(btree t) if(t)inorder(t-lchild);printf(%s ,t-key.id); printf(%s ,); printf(%s ,t-key.address);printf(%sn

14、,t-key.phone);inorder(t-rchild);btree createbtree(void) btree root; char id19; root=NULL; printf(n如果輸入結(jié)束請(qǐng)輸入-1，如果要輸入，請(qǐng)輸入18位身份證號(hào)碼：n); scanf(%s,id); while(strcmp(id,-1)!=0) while(strlen(id)!=18) printf(身份證號(hào)碼不是18位，請(qǐng)重新輸入n);scanf(%s,id); insert(&root,id); printf(n如果輸入結(jié)束請(qǐng)輸入-1，如果要輸入，請(qǐng)輸入18位身份證號(hào)碼：n); scanf(%s

15、,id); return root;btree Delete(btree bt,char *id)btree p,q;if(strcmp(bt-key.id,id)=0)/該結(jié)點(diǎn)為要?jiǎng)h除的點(diǎn) if(bt-lchild=NULL&bt-rchild=NULL)/刪除的是葉結(jié)點(diǎn) free(bt); return NULL;else if(bt-lchild=NULL)/刪除的是無左子樹的結(jié)點(diǎn)p=bt-rchild; free(bt); return p; else if(bt-rchild=NULL)/刪除的是無左子樹的結(jié)點(diǎn)p=bt-lchild; free(bt); return p; else

16、 /刪除的是有左、右子樹的結(jié)點(diǎn)p=q=bt-rchild;while(q-lchild!=NULL) q=q-lchild;q-lchild=bt-lchild;free(bt);return p; else if(strcmp(bt-key.id,id)0&bt-lchild!=NULL)bt-lchild=Delete(bt-lchild,id);if(strcmp(bt-key.id,id)0&bt-rchild!=NULL)bt-rchild=Delete(bt-rchild,id);return bt;void main()btree position;int c,len;char

17、id18;btree root;char name11;char address21;char phone12;root=NULL;system(cls);do/顯示主菜單 printf(- Menu -n); printf(-n); printf(tt1.插入n); printf(tt2.刪除n); printf(tt3.顯示n); printf(tt4.查找n); printf(tt5.修改n); printf(tt6.錄入n); printf(tt7.退出n); printf(-n); printf(tt請(qǐng)按1-7數(shù)字選擇：n); scanf(%d,&c);switch(c) case

18、1:printf(請(qǐng)輸入要輸入要插入的身份證號(hào)碼：n); scanf(%d,id);len=strlen(id);if(len=18)insert(&root,id);elseprintf(輸入號(hào)碼不是18位，不能輸入，請(qǐng)重新選擇：n); break; case 2:if(root) printf(請(qǐng)輸入要輸入要?jiǎng)h除的身份證號(hào)碼：n); scanf(%d,id); len=strlen(id); if(len=18) position=bssearch(root,id); if(position) root=Delete(root,id); printf(刪除成功。n); else print

19、f(身份證號(hào)碼不存在，不能刪除，請(qǐng)重新選擇：n); else printf(輸入號(hào)碼不是18位，不能刪除，請(qǐng)重新選擇：n); else printf(目前沒有任何身份證信息，不能刪除，請(qǐng)重新選擇：n); break; case 3:if(root=NULL) printf(目前沒有任何身份證信息，請(qǐng)重新選擇：。n); else inorder(root); break; case 4:if(root=NULL) printf(目前沒有任何身份證信息，不能刪除，請(qǐng)重新選擇：n); else printf(請(qǐng)輸入需要查找的身份證號(hào)碼：n); scanf(%d,id); len=strlen(id)

20、; if(len=18) position=bssearch(root,id); if(position!=NULL) printf(要查找的信息是：n); printf(%s %s %s %sn,position-key.id,,position-key.address,position-key.phone); else printf(信息不存在：n); else printf(輸入號(hào)碼不是18位，不能查找，請(qǐng)重新選擇：n); break; case 5:if(root=NULL) printf(目前沒有任何身份證信息，請(qǐng)重新選擇：n); else printf(請(qǐng)輸入要修改信息的身份證號(hào)：n); scanf(%d,id); l