数据结构课程设计修道士野人问题和西文图书管理系统

1、题号 题目 3、修道士与野人问题1、 需求分析n个修道士和n个野人渡河，只有一条小船，能容纳c人，两种人都会划船，建立过河方式。满足：野人无法侵犯修道士。这就要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。设计程序模拟该过程。程序的输入为修道士（野人）的个数以及每条船容纳人的个数。输出为判断是否可以安全渡河。如果能，则给出一个小船来回次数最少的最佳方案。要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0在目的岸，1在起始岸）。例如（5，3，0）表示起始岸上有5个修道士，3个野

2、人，小船在目的岸一边。（2）采用邻接表做为存储结构。最短路径搜索采用广度搜索法。（3）输出最优解若问题有解（能渡过河去），则输出一个最佳方案。用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态中间状态初始状态。 若问题无解，则给出“渡河失败”的信息。（4）求出所有的解。2、设计 2.1设计思想（1） 数据结构设计：根据题目要求，用图形结构，用邻接表来存储结点，以及结点之间的 关系，同时在广度优先遍历中利用到队列。（2） 算法设计：先定义一个图利用邻接表储存结构，再举出在船上修道士和野人的所有情况，然后判断其修道士是否处于安全的状态，如果安全则将该点添加到图中，点添加完后在看

3、两点之间是否连通如果连通则可将边添加到图中，这样就创建出了图，然后分别利用广度搜索和深度搜索来完成题目的要求。Printf1()DFS()2.2设计表示 （1） 函数调用关系图AdjLGraphMain() Printf()BroadFSearch()SeqCQueueCreat()Connect()Checking()（2） 函数接口规则说明int Search(AdjLGraph *G,int x,int y,int m ) /*查找起始和最后的结点，其中x,y,m分别表示起始岸修道士人数，野人人数和船的状态*/int Checking(DataType x) /*检查修道士是否安全,x表

4、示邻接表中的一个结点*/int Connect(AdjLGraph *G,int i,int j) /*将能走通的点连接起来，i，j为图中的两个结点*/void Creat(AdjLGraph *G) /*图的创建*/int Print(AdjLGraph G) /*从后向前打印最短路径*/int BroadFSearch(AdjLGraph G,int u,int v) /*用广度优先遍历搜索最短路径，u表示起始结点，v表示最后的结点*/void Print1(AdjLGraph G) /*打印输出所有最短路径*/void DFS(AdjLGraph G,int u,int v ,int v

5、isited) /*利用深度搜索找出所有最短路径，u表示起始结点，v表示最后的结点，visited用来标记结点是否被访问*/2.3详细设计首先是定义邻接表typedef struct int daoshi; /道士 int yeren; /野人 int ship; /船的位置DataType;typedef struct Node /边结点的结构体 int dest; /邻接边的弧头顶点序号 struct Node *next; /单链表的下一个结点指针Edge;typedef struct DataType data; /顶点数据元素 int source; /弧尾顶点序号 Edge *ad

6、j; /邻接边的头指针AdjLHeight;typedef struct AdjLHeight a200; /邻接表数组 int numOfVerts; /顶点个数 int numOfEdges; /边个数AdjLGraph; /邻接表结构体同时定义了几个全局变量，便于函数的直接利用int n,c;/修道士和野人人数为n，船能容纳人数为cint Path200; /保存结点的后驱结点int Path1200; /保存结点的前驱结点利用上述结构和相关函数可以构造出图，然后对图进行利用；然后在广度优先遍历搜索中用到了队列typedef structint queue200;int rear;int

7、 front;int count;SeqCQueue;最后通过主函数main调用各函数得到相关信息int main() AdjLGraph G; int visited200; /标记结点是否被访问printf("输入小船可装的人数:n");while(scanf("%d",&c)!=EOF)memset(Path,0,sizeof(0);memset(visited,0,sizeof(visited);memset(Path1,0,sizeof(Path1);N=0;printf("输入野人或修道士的个数: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("输入小船可装的人数:n"); return 0; 3、调试

9、分析在进行运行的时候，曾出现了打印输出错误，经过一步一步调试，发现在插入结点的时候出现了插入错误，即没有考虑到结点后驱的改变，通过改正，重新运行检测，运行结果正确，在排版时通过一步步调试，能够使输出结果很明显的表示的船的方案。4、 用户手册在VC下运行，很简单的输入，只需输入野人和道士的人数N和船能承载的人的个数C即可。5、测试数据及测试结果（1）输入修道士和野人的人数n=6，船能容纳的人c=2,；不能安全渡河；测试结果：（2） 输入修道士和野人人数为n=3，船能容纳的人c=2；渡河成功测试结果：输出一种最短路径输出所有最短路径输出最短路径数目：6、 源程序清单#include <std

10、io.h>#include <stdlib.h>#include <string.h>#include <malloc.h>int n,c;/修道士和野人人数为n，船能容纳人数为cint Path200;/保存结点的后驱结点int Path1200;/保存结点的前驱结点typedef struct int daoshi; /道士 int yeren; /野人 int ship; /船的位置DataType;typedef struct Node /边结点的结构体 int dest; /邻接边的弧头顶点序号 struct Node *next; /单链表

11、的下一个结点指针Edge;typedef struct DataType data; /顶点数据元素 int source; /弧尾顶点序号 Edge *adj; /邻接边的头指针AdjLHeight;typedef struct AdjLHeight a200; /邻接表数组 int numOfVerts; /顶点个数 int numOfEdges; /边个数AdjLGraph; /邻接表结构体void AdjInitiate(AdjLGraph *G) /初始化 int i; G->numOfEdges=0; /图的边数 G->numOfVerts=0; /顶点数 for(i=

12、0;i<200;i+) G->ai.source=i; G->ai.adj=NULL; void InsertVertex(AdjLGraph *G,int i,DataType x) /插入顶点 if (i>=0&&i<200) G->ai.data.daoshi=x.daoshi;/修道士人数 G->ai.data.yeren=x.yeren;/野人人数 G->ai.data.ship=x.ship;/船的状态 G->numOfVerts+; else printf("顶点越界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("参数i或j越界出错!n"); return; p=(Edge*)malloc(sizeof(Edge);/申请邻接边单链表结点空间 p->dest=j;/置邻接边弧头序号 p->next=G->ai.adj;/ G->ai.adj=p; G->numOfEdges+;void AdjDestroy(AdjLG

14、raph *G)/释放指针内存空间 int i; Edge *p,*q; for(i=0;i<G->numOfVerts;i+) /依次释放内存空间 p=G->ai.adj; while(p!=NULL) q=p->next; free(p); p=q; /队列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;/入队列int QueueAppend(SeqCQueue *Q,int x)if(Q->count>0&&Q->rear=Q->front)printf("队列已满无法插入！n");return 0;elseQ->queueQ->rear=x;Q->rear=(Q->rear+1)%200;Q->count+;return 1;/出队列int QueueDelete(SeqCQueue

16、*Q,int *d)if(Q->count=0)printf("队列已空无数据元素出队列！n");return 0;else*d=Q->queueQ->front;Q->front=(Q->front+1)%200;Q->count-;return 1;/取队头数据元素int QueueGet(SeqCQueue Q,int *d)if(Q.count=0)printf("队列已空无数据元素可取！n");return 0;else*d=Q.queueQ.front;return 1;/查找起始和最后的结点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;/将能走通的点连接起来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; /两个结点都在此岸或都在对岸，不连通 else if(G->ai.data.ship=1&&G->aj.data.ship=0) /从起始岸到目的岸人数要减少 if(G->aj.data.daoshi>G->ai.data.daoshi|G->aj.data.yeren>G->ai.data.yeren) /-如果J结点的道士或野人的个数比开始船没从I开到J时还大

20、时 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) /-从终点到起始最后人应该有所增加 if(G->aj.data.daoshi<G->ai.data.daoshi|G->aj.data.yeren

21、<G->ai.data.yeren) /-如果J结点的道士或野人的个数比开始船没从I开到J时还小时 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;/创建图void Creat(AdjLGraph *G)int i,j,k,m;m=0;DataType x;for(k=0;k<=1;k+)/船有两

22、种情况,在对岸和在起始岸 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; /渡河成功的总次数int M; /最短路径int v1; /起始点int v2; /终点/从后向前打印最短路径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;/用广度优先遍历搜索最短路径 int BroadFSearch(AdjLGraph G,int u,int v) Edge *p; int visit200;/标记点是否被访问 int w,z; memset(visit,0,sizeof(visit); /对数组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;/-保存前驱printf("输出一种最短路径的情况n");M=Print(G);return 1; else if(!visitz) /结点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;/-记下当前结点的后驱Print1(G);else if(visitedw=0) Pathu=w; /找后驱，保存下来 DFS(G,w,v,visited); p=p->next; visitedu=0; int main() AdjLGraph G; int vi

28、sited200; /标记结点是否被访问 printf("输入小船可装的人数:n"); while(scanf("%d",&c)!=EOF) memset(Path,0,sizeof(0); memset(visited,0,sizeof(visited); memset(Path1,0,sizeof(Path1); N=0; printf("输入野人或修道士的个数: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("输入小船可装的人数:n"); return 0; 题号 题目 6、西文图书管理系统1、 需求分析图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系

30、统，将上述业务活动借助于计算机系统完成。要求：（1）每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。（2）作为演示系统，不必使用文件，全部数据可以都在内存存放。要用B-树（4阶树）对书号建立索引，以获得高效率。（3）系统应有以下功能：采编入库、清除库存、借阅、归还、显示（以凹入表的形式显示）等。2、设计 2.1设计思想（1） 数据结构设计：本题要求用B_树来进行存储，其逻辑结构为树形结构，B_树有利于关键字的查找，是一种平衡多叉排序树。（2） 算法设计：将比关键字小的元素插到该关键字的左孩子结点中，比关键字大的的元素插到该关键字的右孩子结点中，当一个结点中关键字的个数超过规定

31、的个数时，该节点要进行分裂，并且保证所有的叶子结点都在同一层。2.2设计表示（1） 函数调用关系图InsertNode()B-树Inputku()SearchBTree() Lookku()Lend()Main（）Returnbook()Exit(0)Clearku()Output()（2）函数接口规则说明void SetNull(BTree &p) /*设结点中的指针向量为空*/int SearchNode(BTree p,KeyType *k) /*在结点中查找关键字，k为所要查找的关键字*/Result SearchBTree(BTree t,KeyType *k) /*在B-树

32、中查找关键字k，返回值是该关键字的状态*/void cpy(KeyType *p,KeyType *q) /*将q的值赋给p*/void InsertInNode(BTree &q,int i,KeyType *k,BTree pt) /*在结点q中插入关键字k和指针pt*/void Split(BTree p,BTree &q) /*分裂结点p，将新结点存放在q中*/void InsertBTree(BTree &t,KeyType *k,BTree q,int i) /*在树t中的q结点的第i个位置插入关键字k*/void InsertNode(BTree &

33、;t,KeyType *key) /*在树t中插入关键字*/ 2.3详细设计此处难点在于B_树的结点的分裂，当插入结点时，判断结点中关键字的个数是否 > 规定的个数，如果大于则要对此结点进行分裂，在分裂时，要改变孩子结点的parent指针，并且把分裂出的关键字放到该关键字的parent结点中，然后继续判断是否要分裂，一直到符合要求。在输出B_树时，用凹入法打印输出，将编号的B_树用以存储图书即可。主要用到的结构体是下面三个首先是用一个结构来存储关键字的信息typedef struct char name20; /书名 char auther30; /作者 long booknum; /书

34、号 int allstore; /书的库存 int sign; /用以计算是否借出的标志book; /书的结构体然后定义B-树typedef struct BTNode int keynum; /结点中关键字的个数 struct BTNode *parent; /结点的双亲结点 KeyType keym+1; /结点中的关键字 struct BTNode *ptrm+1; /孩子结点数组BTNode,*BTree; /B_树结构体再用一个结构体来表示关键字的各种状态typedef struct BTNode *pt; int i; /表示关键字位置 int tag; /判断关键字是否存在Res

35、ult; /用以记录结果的结构接着是与这些结构相关的函数，通过这些函数可以实现题目要求的相关功能。3、调试分析在进行检测时，出现了分裂时的错误，就是没有考虑到在分裂结点时，该结点的孩子结点的parent指针的改变，通过调试和改正，测试正确。4、用户手册在VC下运行，输入数据时按照提示的内容进行输入即可。5、 测试数据及测试结果（1） 运行时，初始显示数据（2） 输入1时，进行图书入库操作（3） 输入2时查询图书库存（4）输入3借阅图书（5） 输入4归还图书（6） 输入5显示所有图书（6） 输入6清除库存（7） 输入0退出；6、 源程序清单#include <stdio.h>#inc

36、lude <malloc.h>#include <string.h>typedef struct char name20; /书名 char auther30; /作者 long booknum; /书号 int allstore; /书的库存 int sign; /用以计算是否借出的标志book; /书的结构体typedef book KeyType;#define FALSE 0#define TRUE 1#define m 4typedef struct BTNode int keynum; /结点中关键字的个数 struct BTNode *parent; /结

37、点的双亲结点 KeyType keym+1; /结点中的关键字 struct BTNode *ptrm+1; /孩子结点数组BTNode,*BTree; /B_树结构体 typedef struct BTNode *pt; int i; /表示关键字位置 int tag; /判断关键字是否存在Result; /用以记录结果的结构体/设结点中的指针向量为空void SetNull(BTree &p) int i=0; while(i<=p->keynum) p->ptri=NULL; i+; /在结点中查找关键字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_树中查找关键字kResult SearchBTree(BTree t,KeyType *k) BTree p=t,q=NULL; bool found=FALSE;/表示是否找到关键字 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;/赋值函数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;/在结点中插入新的关键字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);/大于要插入关键字的关键字向后移 cpy(&(q->keyj+1),k); /将关键字k插入i+1的位置 for(j=q->keynum;j>i;j-) /

41、关键字位置变化的同时其指针的值也发生改变 q->ptrj+1=q->ptrj; q->ptrj+1=pt; /孩子结点也随之改变 if(pt) pt->parent=q; q->keynum+;/分裂结点p，q用来存放新结点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+)/分裂成独立的结点 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结点第i个位置插入关键字void InsertBTree(BTree &t,KeyType *k,BTree q,int i) BTree ap=NULL,root; /ap表示分裂出来的结点 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结点有m-1个关键字 s=m%2=0?m/2:m/2+1; Split(q,ap); cpy(x,&(q->keys);/中间数据元素向上插入到双亲结点中 q=q->parent; if(q) i=SearchNode(q,x);/查找中间元素插入的位置 if(!finish) /进行

44、到了根结点的分裂 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_树中插入一个关键字void InsertNode(BTree &t,KeyType *key) Result result; resul

45、t=SearchBTree(t,key); if(!result.tag) /关键字不存在，插入 InsertBTree(t,key,result.pt,result.i); /图书采编入库void Inputku(BTree *r) book b; Result re; printf("按照书号 书名 作者 库存量的顺序输入书的信息,当输入书号-1时结束: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("输入所借书的书号:");scanf("

47、;%d",&b.booknum); if(b.booknum<0)printf("输入错误!n");return ;printf("输入所借书的数量:");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、该书库存不够!n"); if(re.pt->keyre.i.sign=0)printf("此书以清除库存,请采编入库!n");if(re.pt->keyre.i.allstore>=0&&re.pt->keyre.i.sign>0)printf("借书成功n"); /查看库存void lookku(BTree r) book b; Result re; printf("请输入你要查找的书的信息(书号，名字，作者):"); scanf("%d",&b.booknum); if(b.booknum<0)printf("输入错误!n");return ;scanf("%s %s",&a