數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)修道士野人問題和西文圖書管理系統(tǒng)

1、題號(hào) 題目 3、修道士與野人問題1、 需求分析n個(gè)修道士和n個(gè)野人渡河，只有一條小船，能容納c人，兩種人都會(huì)劃船，建立過河方式。滿足：野人無法侵犯修道士。這就要求無論在何處，修道士的個(gè)數(shù)不得少于野人的人數(shù)（除非修道士個(gè)數(shù)為0）。設(shè)計(jì)程序模擬該過程。程序的輸入為修道士（野人）的個(gè)數(shù)以及每條船容納人的個(gè)數(shù)。輸出為判斷是否可以安全渡河。如果能，則給出一個(gè)小船來回次數(shù)最少的最佳方案。要求：（1）用一個(gè)三元組（x1,x2,x3）表示渡河過程中各個(gè)狀態(tài)。其中，x1表示起始岸上修道士個(gè)數(shù)，x2表示起始岸上野人個(gè)數(shù)，x3表示小船位置（0在目的岸，1在起始岸）。例如（5，3，0）表示起始岸上有5個(gè)修道士，3個(gè)野

2、人，小船在目的岸一邊。（2）采用鄰接表做為存儲(chǔ)結(jié)構(gòu)。最短路徑搜索采用廣度搜索法。（3）輸出最優(yōu)解若問題有解（能渡過河去），則輸出一個(gè)最佳方案。用三元組表示渡河過程中的狀態(tài)，并用箭頭指出這些狀態(tài)之間的遷移：目的狀態(tài)中間狀態(tài)初始狀態(tài)。 若問題無解，則給出“渡河失敗”的信息。（4）求出所有的解。2、設(shè)計(jì) 2.1設(shè)計(jì)思想（1） 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：根據(jù)題目要求，用圖形結(jié)構(gòu)，用鄰接表來存儲(chǔ)結(jié)點(diǎn)，以及結(jié)點(diǎn)之間的 關(guān)系，同時(shí)在廣度優(yōu)先遍歷中利用到隊(duì)列。（2） 算法設(shè)計(jì)：先定義一個(gè)圖利用鄰接表儲(chǔ)存結(jié)構(gòu)，再舉出在船上修道士和野人的所有情況，然后判斷其修道士是否處于安全的狀態(tài)，如果安全則將該點(diǎn)添加到圖中，點(diǎn)添加完后在看

3、兩點(diǎn)之間是否連通如果連通則可將邊添加到圖中，這樣就創(chuàng)建出了圖，然后分別利用廣度搜索和深度搜索來完成題目的要求。Printf1()DFS()2.2設(shè)計(jì)表示 （1） 函數(shù)調(diào)用關(guān)系圖AdjLGraphMain() Printf()BroadFSearch()SeqCQueueCreat()Connect()Checking()（2） 函數(shù)接口規(guī)則說明int Search(AdjLGraph *G,int x,int y,int m ) /*查找起始和最后的結(jié)點(diǎn)，其中x,y,m分別表示起始岸修道士人數(shù)，野人人數(shù)和船的狀態(tài)*/int Checking(DataType x) /*檢查修道士是否安全,x表

4、示鄰接表中的一個(gè)結(jié)點(diǎn)*/int Connect(AdjLGraph *G,int i,int j) /*將能走通的點(diǎn)連接起來，i，j為圖中的兩個(gè)結(jié)點(diǎn)*/void Creat(AdjLGraph *G) /*圖的創(chuàng)建*/int Print(AdjLGraph G) /*從后向前打印最短路徑*/int BroadFSearch(AdjLGraph G,int u,int v) /*用廣度優(yōu)先遍歷搜索最短路徑，u表示起始結(jié)點(diǎn)，v表示最后的結(jié)點(diǎn)*/void Print1(AdjLGraph G) /*打印輸出所有最短路徑*/void DFS(AdjLGraph G,int u,int v ,int v

5、isited) /*利用深度搜索找出所有最短路徑，u表示起始結(jié)點(diǎn)，v表示最后的結(jié)點(diǎn)，visited用來標(biāo)記結(jié)點(diǎn)是否被訪問*/2.3詳細(xì)設(shè)計(jì)首先是定義鄰接表typedef struct int daoshi; /道士 int yeren; /野人 int ship; /船的位置DataType;typedef struct Node /邊結(jié)點(diǎn)的結(jié)構(gòu)體 int dest; /鄰接邊的弧頭頂點(diǎn)序號(hào) struct Node *next; /單鏈表的下一個(gè)結(jié)點(diǎn)指針Edge;typedef struct DataType data; /頂點(diǎn)數(shù)據(jù)元素 int source; /弧尾頂點(diǎn)序號(hào) Edge *ad

6、j; /鄰接邊的頭指針AdjLHeight;typedef struct AdjLHeight a200; /鄰接表數(shù)組 int numOfVerts; /頂點(diǎn)個(gè)數(shù) int numOfEdges; /邊個(gè)數(shù)AdjLGraph; /鄰接表結(jié)構(gòu)體同時(shí)定義了幾個(gè)全局變量，便于函數(shù)的直接利用int n,c;/修道士和野人人數(shù)為n，船能容納人數(shù)為cint Path200; /保存結(jié)點(diǎn)的后驅(qū)結(jié)點(diǎn)int Path1200; /保存結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)利用上述結(jié)構(gòu)和相關(guān)函數(shù)可以構(gòu)造出圖，然后對(duì)圖進(jìn)行利用；然后在廣度優(yōu)先遍歷搜索中用到了隊(duì)列typedef structint queue200;int rear;int

7、 front;int count;SeqCQueue;最后通過主函數(shù)main調(diào)用各函數(shù)得到相關(guān)信息int main() AdjLGraph G; int visited200; /標(biāo)記結(jié)點(diǎn)是否被訪問printf("輸入小船可裝的人數(shù):n");while(scanf("%d",&c)!=EOF)memset(Path,0,sizeof(0);memset(visited,0,sizeof(visited);memset(Path1,0,sizeof(Path1);N=0;printf("輸入野人或修道士的個(gè)數(shù):n");scanf

8、("%d",&n);AdjInitiate(&G);Creat(&G);v1=Search(&G,n,n,1);v2=Search(&G,0,0,0);if(BroadFSearch( G,v1, v2)=0)printf("渡河失敗n");elseprintf("輸出所有最短路徑的情況:n"); DFS(G,v1,v2,visited);printf("共有%d種情況n",N); printf("輸入小船可裝的人數(shù):n"); return 0; 3、調(diào)試

9、分析在進(jìn)行運(yùn)行的時(shí)候，曾出現(xiàn)了打印輸出錯(cuò)誤，經(jīng)過一步一步調(diào)試，發(fā)現(xiàn)在插入結(jié)點(diǎn)的時(shí)候出現(xiàn)了插入錯(cuò)誤，即沒有考慮到結(jié)點(diǎn)后驅(qū)的改變，通過改正，重新運(yùn)行檢測(cè)，運(yùn)行結(jié)果正確，在排版時(shí)通過一步步調(diào)試，能夠使輸出結(jié)果很明顯的表示的船的方案。4、 用戶手冊(cè)在VC下運(yùn)行，很簡(jiǎn)單的輸入，只需輸入野人和道士的人數(shù)N和船能承載的人的個(gè)數(shù)C即可。5、測(cè)試數(shù)據(jù)及測(cè)試結(jié)果（1）輸入修道士和野人的人數(shù)n=6，船能容納的人c=2,；不能安全渡河；測(cè)試結(jié)果：（2） 輸入修道士和野人人數(shù)為n=3，船能容納的人c=2；渡河成功測(cè)試結(jié)果：輸出一種最短路徑輸出所有最短路徑輸出最短路徑數(shù)目：6、 源程序清單#include <std

10、io.h>#include <stdlib.h>#include <string.h>#include <malloc.h>int n,c;/修道士和野人人數(shù)為n，船能容納人數(shù)為cint Path200;/保存結(jié)點(diǎn)的后驅(qū)結(jié)點(diǎn)int Path1200;/保存結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)typedef struct int daoshi; /道士 int yeren; /野人 int ship; /船的位置DataType;typedef struct Node /邊結(jié)點(diǎn)的結(jié)構(gòu)體 int dest; /鄰接邊的弧頭頂點(diǎn)序號(hào) struct Node *next; /單鏈表

11、的下一個(gè)結(jié)點(diǎn)指針Edge;typedef struct DataType data; /頂點(diǎn)數(shù)據(jù)元素 int source; /弧尾頂點(diǎn)序號(hào) Edge *adj; /鄰接邊的頭指針AdjLHeight;typedef struct AdjLHeight a200; /鄰接表數(shù)組 int numOfVerts; /頂點(diǎn)個(gè)數(shù) int numOfEdges; /邊個(gè)數(shù)AdjLGraph; /鄰接表結(jié)構(gòu)體void AdjInitiate(AdjLGraph *G) /初始化 int i; G->numOfEdges=0; /圖的邊數(shù) G->numOfVerts=0; /頂點(diǎn)數(shù) for(i=

12、0;i<200;i+) G->ai.source=i; G->ai.adj=NULL; void InsertVertex(AdjLGraph *G,int i,DataType x) /插入頂點(diǎn) if (i>=0&&i<200) G->ai.data.daoshi=x.daoshi;/修道士人數(shù) G->ai.data.yeren=x.yeren;/野人人數(shù) G->ai.data.ship=x.ship;/船的狀態(tài) G->numOfVerts+; else printf("頂點(diǎn)越界n");void Ins

13、ertEdge(AdjLGraph *G,int i,int j) /插入邊 Edge *p; if(i<0|i>=G->numOfVerts|j<0|j>=G->numOfVerts) printf("參數(shù)i或j越界出錯(cuò)!n"); return; p=(Edge*)malloc(sizeof(Edge);/申請(qǐng)鄰接邊單鏈表結(jié)點(diǎn)空間 p->dest=j;/置鄰接邊弧頭序號(hào) p->next=G->ai.adj;/ G->ai.adj=p; G->numOfEdges+;void AdjDestroy(AdjLG

14、raph *G)/釋放指針內(nèi)存空間 int i; Edge *p,*q; for(i=0;i<G->numOfVerts;i+) /依次釋放內(nèi)存空間 p=G->ai.adj; while(p!=NULL) q=p->next; free(p); p=q; /隊(duì)列typedef structint queue200;int rear;int front;int count;SeqCQueue;/初始化void QueueInitiate(SeqCQueue *Q)Q->rear=0;Q->front=0;Q->count =0;/非空否int Queue

15、NotEmpty(SeqCQueue Q)if(Q.count!=0) return 1;else return 0;/入隊(duì)列int QueueAppend(SeqCQueue *Q,int x)if(Q->count>0&&Q->rear=Q->front)printf("隊(duì)列已滿無法插入！n");return 0;elseQ->queueQ->rear=x;Q->rear=(Q->rear+1)%200;Q->count+;return 1;/出隊(duì)列int QueueDelete(SeqCQueue

16、*Q,int *d)if(Q->count=0)printf("隊(duì)列已空無數(shù)據(jù)元素出隊(duì)列！n");return 0;else*d=Q->queueQ->front;Q->front=(Q->front+1)%200;Q->count-;return 1;/取隊(duì)頭數(shù)據(jù)元素int QueueGet(SeqCQueue Q,int *d)if(Q.count=0)printf("隊(duì)列已空無數(shù)據(jù)元素可?。");return 0;else*d=Q.queueQ.front;return 1;/查找起始和最后的結(jié)點(diǎn)int Sea

17、rch(AdjLGraph *G,int x,int y,int m )int i;for(i=0;i<G->numOfVerts;i+)if(G->ai.data.daoshi=x&&G->ai.data.yeren=y&&G->ai.data.ship=m)return i; return -1;int Checking(DataType x)/檢查修道士是否安全if(x.daoshi>=x.yeren|x.daoshi =0)&&(n-x.daoshi)>=(n-x.yeren)|x.daoshi

18、=n)&&x.daoshi >=0&&x.daoshi <=n&&x.yeren >=0&&x.yeren<=n) return 1;else return 0;/將能走通的點(diǎn)連接起來int Connect(AdjLGraph *G,int i,int j) int m;m=(G->ai.data.daoshi-G->aj.data.daoshi)+(G->ai.data.yeren-G->aj.data.yeren); if(G->ai.data.ship=0&&am

19、p;G->aj.data.ship=0|G->ai.data.ship=1&&G->aj.data.ship=1) return 0; /兩個(gè)結(jié)點(diǎn)都在此岸或都在對(duì)岸，不連通 else if(G->ai.data.ship=1&&G->aj.data.ship=0) /從起始岸到目的岸人數(shù)要減少 if(G->aj.data.daoshi>G->ai.data.daoshi|G->aj.data.yeren>G->ai.data.yeren) /-如果J結(jié)點(diǎn)的道士或野人的個(gè)數(shù)比開始船沒從I開到J時(shí)還大

20、時(shí) return 0; if(G->aj.data.daoshi=G->ai.data.daoshi&&G->aj.data.yeren=G->ai.data.yeren) return 0; if(m>c)return 0;/-船上的人超重 return 1; else if(G->ai.data.ship=0&&G->aj.data.ship=1) /-從終點(diǎn)到起始最后人應(yīng)該有所增加 if(G->aj.data.daoshi<G->ai.data.daoshi|G->aj.data.yeren

21、<G->ai.data.yeren) /-如果J結(jié)點(diǎn)的道士或野人的個(gè)數(shù)比開始船沒從I開到J時(shí)還小時(shí) return 0; if(G->aj.data.daoshi=G->ai.data.daoshi&&G->aj.data.yeren=G->ai.data.yeren) return 0; if(-1)*m>n)return 0;/-船上的人超重 return 1; return 0;/創(chuàng)建圖void Creat(AdjLGraph *G)int i,j,k,m;m=0;DataType x;for(k=0;k<=1;k+)/船有兩

22、種情況,在對(duì)岸和在起始岸 for(i=0;i<=n;i+) for(j=0;j<=n;j+) x.daoshi=i; x.yeren=j; x.ship=k; if(Checking(x)=1) InsertVertex(G,m,x); m+; for(i=0;i<G->numOfVerts;i+)for(j=0;j<G->numOfVerts;j+)if(Connect(G,i,j)InsertEdge(G,i,j);int N; /渡河成功的總次數(shù)int M; /最短路徑int v1; /起始點(diǎn)int v2; /終點(diǎn)/從后向前打印最短路徑int Prin

23、t(AdjLGraph G)int k,i=0;printf("(%d %d %d)<-",G.av2.data.daoshi,G.av2.data.yeren,G.av2.data.ship);for(k=Path1v2;k!=v1;k=Path1k)i+;printf("(%d %d %d)<-",G.ak.data.daoshi,G.ak.data.yeren,G.ak.data.ship); printf("(%d %d %d)n",G.av1.data.daoshi,G.av1.data.yeren,G.av1.

24、data.ship);return i;/用廣度優(yōu)先遍歷搜索最短路徑 int BroadFSearch(AdjLGraph G,int u,int v) Edge *p; int visit200;/標(biāo)記點(diǎn)是否被訪問 int w,z; memset(visit,0,sizeof(visit); /對(duì)數(shù)組visit200清零 SeqCQueue Q; visitu=1; QueueInitiate(&Q); QueueAppend(&Q,u); while(QueueNotEmpty(Q) QueueDelete(&Q,&w); p=G.aw.adj; while

25、(p!=NULL) z=p->dest; if(z=v) Path1z=w;/-保存前驅(qū)printf("輸出一種最短路徑的情況n");M=Print(G);return 1; else if(!visitz) /結(jié)點(diǎn)j未被訪問過 Path1z=w;visitz=1; QueueAppend(&Q,z);p=p->next; return 0;void Print1(AdjLGraph G)int k,j;int i=0;DataType a1200; memset(a1,0,sizeof(a1);for(k=Pathv1;k!=v2;k=Pathk) a

26、10=G.av1.data;a1i+1=G.ak.data;i+;if(i=M) a1i+1=G.av2.data;N+;printf("(%d %d %d)",G.av1.data.daoshi,G.av1.data.yeren,G.av1.data.ship);for(j=1;j<=M+1;j+)printf("->(%d %d)->(%d %d %d)",abs(a1j.daoshi-a1j-1.daoshi),abs(a1j.yeren-a1j-1.yeren),a1j.daoshi,a1j.yeren,a1j.ship);pr

27、intf("n");/利用深度搜索找出所有最短路徑 void DFS(AdjLGraph G,int u,int v ,int visited)Edge *p;int w;visitedu=1; p=G.au.adj; while(p!=NULL) w=p->dest; if(w=v)Pathu=w;/-記下當(dāng)前結(jié)點(diǎn)的后驅(qū)Print1(G);else if(visitedw=0) Pathu=w; /找后驅(qū)，保存下來 DFS(G,w,v,visited); p=p->next; visitedu=0; int main() AdjLGraph G; int vi

28、sited200; /標(biāo)記結(jié)點(diǎn)是否被訪問 printf("輸入小船可裝的人數(shù):n"); while(scanf("%d",&c)!=EOF) memset(Path,0,sizeof(0); memset(visited,0,sizeof(visited); memset(Path1,0,sizeof(Path1); N=0; printf("輸入野人或修道士的個(gè)數(shù):n"); scanf("%d",&n); AdjInitiate(&G); Creat(&G); v1=Search(

29、&G,n,n,1); v2=Search(&G,0,0,0); if(BroadFSearch( G,v1, v2)=0)printf("渡河失敗n");elseprintf("輸出所有最短路徑的情況:n"); DFS(G,v1,v2,visited); printf("共有%d種情況n",N); printf("輸入小船可裝的人數(shù):n"); return 0; 題號(hào) 題目 6、西文圖書管理系統(tǒng)1、 需求分析圖書管理基本業(yè)務(wù)活動(dòng)包括：對(duì)一本書的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系

30、統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。要求：（1）每種書的登記內(nèi)容至少包括書號(hào)、書名、著者、現(xiàn)存量和總庫(kù)存量等五項(xiàng)。（2）作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。要用B-樹（4階樹）對(duì)書號(hào)建立索引，以獲得高效率。（3）系統(tǒng)應(yīng)有以下功能：采編入庫(kù)、清除庫(kù)存、借閱、歸還、顯示（以凹入表的形式顯示）等。2、設(shè)計(jì) 2.1設(shè)計(jì)思想（1） 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：本題要求用B_樹來進(jìn)行存儲(chǔ)，其邏輯結(jié)構(gòu)為樹形結(jié)構(gòu)，B_樹有利于關(guān)鍵字的查找，是一種平衡多叉排序樹。（2） 算法設(shè)計(jì)：將比關(guān)鍵字小的元素插到該關(guān)鍵字的左孩子結(jié)點(diǎn)中，比關(guān)鍵字大的的元素插到該關(guān)鍵字的右孩子結(jié)點(diǎn)中，當(dāng)一個(gè)結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)超過規(guī)定

31、的個(gè)數(shù)時(shí)，該節(jié)點(diǎn)要進(jìn)行分裂，并且保證所有的葉子結(jié)點(diǎn)都在同一層。2.2設(shè)計(jì)表示（1） 函數(shù)調(diào)用關(guān)系圖InsertNode()B-樹Inputku()SearchBTree() Lookku()Lend()Main（）Returnbook()Exit(0)Clearku()Output()（2）函數(shù)接口規(guī)則說明void SetNull(BTree &p) /*設(shè)結(jié)點(diǎn)中的指針向量為空*/int SearchNode(BTree p,KeyType *k) /*在結(jié)點(diǎn)中查找關(guān)鍵字，k為所要查找的關(guān)鍵字*/Result SearchBTree(BTree t,KeyType *k) /*在B-樹

32、中查找關(guān)鍵字k，返回值是該關(guān)鍵字的狀態(tài)*/void cpy(KeyType *p,KeyType *q) /*將q的值賦給p*/void InsertInNode(BTree &q,int i,KeyType *k,BTree pt) /*在結(jié)點(diǎn)q中插入關(guān)鍵字k和指針pt*/void Split(BTree p,BTree &q) /*分裂結(jié)點(diǎn)p，將新結(jié)點(diǎn)存放在q中*/void InsertBTree(BTree &t,KeyType *k,BTree q,int i) /*在樹t中的q結(jié)點(diǎn)的第i個(gè)位置插入關(guān)鍵字k*/void InsertNode(BTree &

33、;t,KeyType *key) /*在樹t中插入關(guān)鍵字*/ 2.3詳細(xì)設(shè)計(jì)此處難點(diǎn)在于B_樹的結(jié)點(diǎn)的分裂，當(dāng)插入結(jié)點(diǎn)時(shí)，判斷結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)是否 > 規(guī)定的個(gè)數(shù)，如果大于則要對(duì)此結(jié)點(diǎn)進(jìn)行分裂，在分裂時(shí)，要改變孩子結(jié)點(diǎn)的parent指針，并且把分裂出的關(guān)鍵字放到該關(guān)鍵字的parent結(jié)點(diǎn)中，然后繼續(xù)判斷是否要分裂，一直到符合要求。在輸出B_樹時(shí)，用凹入法打印輸出，將編號(hào)的B_樹用以存儲(chǔ)圖書即可。主要用到的結(jié)構(gòu)體是下面三個(gè)首先是用一個(gè)結(jié)構(gòu)來存儲(chǔ)關(guān)鍵字的信息typedef struct char name20; /書名 char auther30; /作者 long booknum; /書

34、號(hào) int allstore; /書的庫(kù)存 int sign; /用以計(jì)算是否借出的標(biāo)志book; /書的結(jié)構(gòu)體然后定義B-樹typedef struct BTNode int keynum; /結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù) struct BTNode *parent; /結(jié)點(diǎn)的雙親結(jié)點(diǎn) KeyType keym+1; /結(jié)點(diǎn)中的關(guān)鍵字 struct BTNode *ptrm+1; /孩子結(jié)點(diǎn)數(shù)組BTNode,*BTree; /B_樹結(jié)構(gòu)體再用一個(gè)結(jié)構(gòu)體來表示關(guān)鍵字的各種狀態(tài)typedef struct BTNode *pt; int i; /表示關(guān)鍵字位置 int tag; /判斷關(guān)鍵字是否存在Res

35、ult; /用以記錄結(jié)果的結(jié)構(gòu)接著是與這些結(jié)構(gòu)相關(guān)的函數(shù)，通過這些函數(shù)可以實(shí)現(xiàn)題目要求的相關(guān)功能。3、調(diào)試分析在進(jìn)行檢測(cè)時(shí)，出現(xiàn)了分裂時(shí)的錯(cuò)誤，就是沒有考慮到在分裂結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)的孩子結(jié)點(diǎn)的parent指針的改變，通過調(diào)試和改正，測(cè)試正確。4、用戶手冊(cè)在VC下運(yùn)行，輸入數(shù)據(jù)時(shí)按照提示的內(nèi)容進(jìn)行輸入即可。5、 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果（1） 運(yùn)行時(shí)，初始顯示數(shù)據(jù)（2） 輸入1時(shí)，進(jìn)行圖書入庫(kù)操作（3） 輸入2時(shí)查詢圖書庫(kù)存（4）輸入3借閱圖書（5） 輸入4歸還圖書（6） 輸入5顯示所有圖書（6） 輸入6清除庫(kù)存（7） 輸入0退出；6、 源程序清單#include <stdio.h>#inc

36、lude <malloc.h>#include <string.h>typedef struct char name20; /書名 char auther30; /作者 long booknum; /書號(hào) int allstore; /書的庫(kù)存 int sign; /用以計(jì)算是否借出的標(biāo)志book; /書的結(jié)構(gòu)體typedef book KeyType;#define FALSE 0#define TRUE 1#define m 4typedef struct BTNode int keynum; /結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù) struct BTNode *parent; /結(jié)

37、點(diǎn)的雙親結(jié)點(diǎn) KeyType keym+1; /結(jié)點(diǎn)中的關(guān)鍵字 struct BTNode *ptrm+1; /孩子結(jié)點(diǎn)數(shù)組BTNode,*BTree; /B_樹結(jié)構(gòu)體 typedef struct BTNode *pt; int i; /表示關(guān)鍵字位置 int tag; /判斷關(guān)鍵字是否存在Result; /用以記錄結(jié)果的結(jié)構(gòu)體/設(shè)結(jié)點(diǎn)中的指針向量為空void SetNull(BTree &p) int i=0; while(i<=p->keynum) p->ptri=NULL; i+; /在結(jié)點(diǎn)中查找關(guān)鍵字int SearchNode(BTree p,KeyTyp

38、e *k) int i=1; while(i<=p->keynum) if(k->booknum<p->keyi.booknum) return i-1; i+; return i-1;/在B_樹中查找關(guān)鍵字kResult SearchBTree(BTree t,KeyType *k) BTree p=t,q=NULL; bool found=FALSE;/表示是否找到關(guān)鍵字 int i=0; Result result; while(p&&!found) i=SearchNode(p,k); if(i>0&&p->ke

39、yi.booknum=k->booknum) found=TRUE; else q=p; p=p->ptri; if(found) result.pt=p; result.i=i; result.tag=1; else result.pt=q; result.i=i; result.tag=0; return result;/賦值函數(shù)void cpy(KeyType *p,KeyType *q) p->allstore=q->allstore; strcpy(p->auther,q->auther); p->booknum=q->booknum;

40、 strcpy(p->name,q->name); p->sign=q->sign;/在結(jié)點(diǎn)中插入新的關(guān)鍵字k和指針ptvoid InsertInNode(BTree &q,int i,KeyType *k,BTree pt) int j; for(j=q->keynum;j>i;j-) cpy(&(q->keyj+1),&(q->keyj);/大于要插入關(guān)鍵字的關(guān)鍵字向后移 cpy(&(q->keyj+1),k); /將關(guān)鍵字k插入i+1的位置 for(j=q->keynum;j>i;j-) /

41、關(guān)鍵字位置變化的同時(shí)其指針的值也發(fā)生改變 q->ptrj+1=q->ptrj; q->ptrj+1=pt; /孩子結(jié)點(diǎn)也隨之改變 if(pt) pt->parent=q; q->keynum+;/分裂結(jié)點(diǎn)p，q用來存放新結(jié)點(diǎn)void Split(BTree p,BTree &q) int s=m%2=0?m/2-1:m/2,i,j=0,t; p->keynum=s; q=(BTree)malloc(sizeof(BTNode); SetNull(q); for(i=s+2;i<=m;i+)/分裂成獨(dú)立的結(jié)點(diǎn) q->ptrj=p->p

42、tri-1; cpy(&(q->key+j),&(p->keyi); q->ptrj=p->ptri-1; q->keynum=j; for(t=s+1;t<=m;t+) if(p->ptrt!=NULL)p->ptrt->parent=q; /在q結(jié)點(diǎn)第i個(gè)位置插入關(guān)鍵字void InsertBTree(BTree &t,KeyType *k,BTree q,int i) BTree ap=NULL,root; /ap表示分裂出來的結(jié)點(diǎn) bool finish=FALSE; /表示是否插入成功 int s; Key

43、Type *x; x=(KeyType*)malloc(sizeof(KeyType); cpy(x,k); while(q&&!finish) InsertInNode(q,i,x,ap); if(q->keynum<m) finish=TRUE; else /q結(jié)點(diǎn)有m-1個(gè)關(guān)鍵字 s=m%2=0?m/2:m/2+1; Split(q,ap); cpy(x,&(q->keys);/中間數(shù)據(jù)元素向上插入到雙親結(jié)點(diǎn)中 q=q->parent; if(q) i=SearchNode(q,x);/查找中間元素插入的位置 if(!finish) /進(jìn)行

44、到了根結(jié)點(diǎn)的分裂 root=(BTree)malloc(sizeof(BTNode); SetNull(root); cpy(&(root->key1),x); root->ptr0=t; root->ptr1=ap; root->keynum=1; root->parent=NULL; if(t) t->parent=root; if(ap) ap->parent=root; t=root; /在B_樹中插入一個(gè)關(guān)鍵字void InsertNode(BTree &t,KeyType *key) Result result; resul

45、t=SearchBTree(t,key); if(!result.tag) /關(guān)鍵字不存在，插入 InsertBTree(t,key,result.pt,result.i); /圖書采編入庫(kù)void Inputku(BTree *r) book b; Result re; printf("按照書號(hào) 書名 作者 庫(kù)存量的順序輸入書的信息,當(dāng)輸入書號(hào)-1時(shí)結(jié)束:n"); while (1) scanf("%d",&b.booknum); if(b.booknum<0)break;scanf("%s %s %d",&b

46、.name,&b.auther,&b.allstore); b.sign=b.allstore; / 表示該書沒有被借出 re=SearchBTree(*r,&b); if(re.tag=0)InsertNode(*r,&b); else re.pt->keyre.i.allstore+=b.allstore; re.pt->keyre.i.sign+=b.sign; /借閱圖書void lend(BTree *r) book b; int k; Result re; printf("輸入所借書的書號(hào):");scanf("

47、;%d",&b.booknum); if(b.booknum<0)printf("輸入錯(cuò)誤!n");return ;printf("輸入所借書的數(shù)量:");scanf("%d",&k); re=SearchBTree(*r,&b); if(re.tag=0)printf("抱歉，沒有此書!n"); else if(re.pt->keyre.i.allstore>=k)re.pt->keyre.i.allstore-=k; else printf("

48、該書庫(kù)存不夠!n"); if(re.pt->keyre.i.sign=0)printf("此書以清除庫(kù)存,請(qǐng)采編入庫(kù)!n");if(re.pt->keyre.i.allstore>=0&&re.pt->keyre.i.sign>0)printf("借書成功n"); /查看庫(kù)存void lookku(BTree r) book b; Result re; printf("請(qǐng)輸入你要查找的書的信息(書號(hào)，名字，作者):"); scanf("%d",&b.booknum); if(b.booknum<0)printf("輸入錯(cuò)誤!n");return ;scanf("%s %s",&a