约瑟夫环图书馆数据库.doc

《约瑟夫环图书馆数据库.doc》由会员分享，可在线阅读，更多相关《约瑟夫环图书馆数据库.doc（25页珍藏版）》请在三一办公上搜索。

1、设计题目一 约瑟夫环问题1、设计内容设计一个带头结点的循环单链表类，实现约瑟夫环问题；问题描述：设编号为1,2,，n(n0)个人按顺时针方向围坐-圈，每人持有一个正整数密码。开始时任意给出一个报数上限值m从第一个人开始顺时针方向自1起顺序报数。报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1起顺序报数.如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，并给出出列人的编号序列。 测试数据： n=7,7个人的密码依次为3,1,7,2,4,8,4 初始报数上限值m=202、设计需求分析在数据结构中，循环单链表的优点就是在链表的任意结点处都可以

2、对整个链表进行扫描。本题目的是实现对顺时针的一圈数据进行报数，第一次报数m值是给出的，值为20.以后每一次报数值m根据新的密码所给定，这样就决定了算法中必须有一个给报数m传值的过程。要求报到m的人出列，而且出列的形式是显示他的编号，而不是密码本身，所以算法中必须有一个计数器，记录编号，找到位置输出编号，在把密码给m，然后删除密码。依次循环，而且每一次循环计数器要从1开始计数，循环直到链表为空。3、概要设计（1）建立Node存储结构要实现约瑟夫环的输出，首先要对环内是数字建立存储结构。对数字进行链表存储。 如下：class Node T hao; T data; Node *next;frien

3、d class yuesefu; ; （2）将相关数据结构放入类里进行定义定义如下： class yuesefu public: yuesefu( )first=new Node;first-next=first; yuesefu(T a , int n); yuesefu( ); void Printlist( ); void chazhao(int n);private: Node *first; ;（3）每种算法的实现 以下是实现建立链表的算法： 用尾插法建立链表，为了让数据正序存放yuesefu: yuesefu(T a , int n) int j=1; first=new Node

4、 ; Node *rear=first,*s; for (int i=0; in; i+) s=new Node ; /建立新节点s-data=ai; /尾插法插入数据 s-hao=j;j+; rear-next=s; rear=s; rear-next=first; 程序结束之前释放所建立的结点空间template yuesefu: yuesefu( ) Node *p,*q;p=first-next; while (p!=first) q=p; p=p-next; delete q; delete first;显示运行的结果template void yuesefu:Printlist(

5、)Node *p; p=first-next; while (p!=first) coutdatanext; coutendl;根据要求查找密码，记录编号直到循环结束找出所有密码的编号template void yuesefu:chazhao(int n) Node *p,*r;p=first-next; int j;int x=20;while(p-next!=first)p=p-next;p-next=first-next;/尾指针与头节点连接形成单循环链表first=first-next;/删除不带数据的头结点for(int i=1;in;i+)j=1;while(jnext;j+; /

6、查找到第X个节点r-next=first-next;/摘连，把第r个结点接到first的下一个结点 x=first-data;couthaonext;/连接成一个单循环链couthaoendl;4、详细设计#includetemplate class yuesefu;template class Node T hao; T data; Node *next;friend class yuesefu; ; template class yuesefu public: yuesefu( )first=new Node;first-next=first; yuesefu(T a , int n);

7、yuesefu( ); void Printlist( ); void chazhao(int n);private: Node *first; ;template yuesefu: yuesefu(T a , int n) int j=1; first=new Node ; Node *rear=first,*s; for (int i=0; in; i+) s=new Node ; /建立新节点s-data=ai; /尾插法插入数据 s-hao=j;j+; rear-next=s; rear=s; rear-next=first; template yuesefu: yuesefu( )

8、Node *p,*q;p=first-next; while (p!=first) q=p; p=p-next; delete q; delete first;template void yuesefu:Printlist( )Node *p; p=first-next; while (p!=first) coutdatanext; coutendl;template void yuesefu:chazhao(int n) Node *p,*r;p=first-next; int j;int x=20;while(p-next!=first)p=p-next;p-next=first-next

9、;/尾指针与头节点连接形成单循环链表first=first-next;/删除不带数据的头结点for(int i=1;in;i+)j=1;while(jnext;j+; /查找到第X个节点r-next=first-next;/摘连，把第r个结点接到first的下一个结点 x=first-data;couthaonext;/连接成一个单循环链couthaoendl;void main() int a10=3,1,7,2,4,8,4; yuesefu obj(a,7); obj.Printlist(); obj.chazhao(7); 5、调试分析运行结果如下： 题目要求输出编号，在找到密码之前要利

10、用一个中间变量记录密码的编号，循环直到链表为空。 设计题目二 图书管理系统1、 设计内容设计一个计算机管理系统完成图书管理基本业务。要求：（1）每种书的登记内容包括书号、书名、著作者、现存量和库存量；（2)对书号建立索引表（线性表）以提高查找效率；（3)系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。2、 设计需求分析题目要求每种书的登记内容包括书号、书名、著作者、现存量和库存量，所以要对图书建立结构体类

11、型，要求对书号建立索引表（线性表）以提高查找效率，所以要对书号进行索引，建立结构体代码如下：typedef struct Boro/借书行为 char BNum20;/借书的书号 char RetDate8;/归还日期 struct Boro *next;Bor;typedef struct LinkBook Bor *next; /该图书证的借书行为 char CNum20; /卡号 int Total; /借书的数量lendLIST_INIT_SIZE;/借书人数组/图书的结构体信息typedef struct LNode char CardNum20;/图书证号 struct LNode

12、 *next;LinkList; /借书人typedef struct book/每种图书需要登记的内容包括书号ISBN、书名、作者、出版社、总库存量和现库存量。 char num20;/书号 char name20;/书名 char auth20;/作者 char pub20;/出版社 int TotNum;/总库存 int NowNum;/现库存 LinkList *next;/借了该书的人ookMAXSIZE;3、 概要设计分为以下几个函数：void InitBo(ook &boo) /初始化图书信息void InitRe(lend &Lin) /初始化借阅者信息bool BinaryS

13、earch(ook boo,char SearchNum) /折半查找法查找比较书号void Menu() /菜单void Borrow(ook &boo,lend &Lin,char BorrowNum,char CaNum)/借阅：如果一种书的现库存量大于零，则借出一本书，将现库存量减1， /并登记借阅者的图书证号和归还期限。void Return(ook &boo,lend &Lin,char ReturnNum,char BorrowerNum)/4、 归还：注销对借阅者的登记，改变该书的现存量。void Buy(ook &boo, char BuyNum)/采编入库：新购入一种书，如

14、果该书在图书账目中已经存在，则将其库存量增加（包 /括总库存量和现库存量），如果该书不存在，则在图书账目中增加一种书，总库存量和现库存量均为1。4、 详细设计如下：#include#include #include #include #define MAXSIZE 100 /最大值定义为100#define LIST_INIT_SIZE 100/图书证使用者最大值定义为100/借书人的结构体typedef struct Boro/借书行为 char BNum20;/借书的书号 char RetDate8;/归还日期 struct Boro *next;Bor;typedef struct Li

15、nkBook Bor *next; /该图书证的借书行为 char CNum20; /卡号 int Total; /借书的数量lendLIST_INIT_SIZE;/借书人数组/图书的结构体信息typedef struct LNode char CardNum20;/图书证号 struct LNode *next;LinkList; /借书人typedef struct book/每种图书需要登记的内容包括书号ISBN、书名、作者、出版社、总库存量和现库存量。 char num20;/书号 char name20;/书名 char auth20;/作者 char pub20;/出版社 int

16、TotNum;/总库存 int NowNum;/现库存 LinkList *next;/借了该书的人ookMAXSIZE;int Retotal;/读者数量int total; /定义外部变量.书的种类数/结构体初始化void InitBo(ook &boo) /初始化图书信息 for(int i=0;iMAXSIZE;i+) booi.NowNum=0; booi.TotNum=0; booi.next=NULL; void InitRe(lend &Lin) /初始化借阅者信息 for(int i=0;iLIST_INIT_SIZE;i+) Lini.next=NULL;int mid=0

17、;/外部函数mid，用来返回查找到的位置bool BinarySearch(ook boo,char SearchNum) /折半查找法查找比较书号 /用bool函数，但由于函数不能有两个返回值,所以设置一个外部变量mid，用来返回查找到的位置 int low=0,high=total-1; int found=0; while(low=high) mid=(low+high)/2; /中间点 if(strcmp(boomid.num,SearchNum)=0) /书号相同 found=1; return true; /查找成功 if(strcmp(boomid.num,SearchNum)!

18、=0)/书号不同 high=mid-1; else low=mid+1; if(found=0) return false; /查找失败void Buy(ook &boo, char BuyNum)/采编入库：新购入一种书，如果该书在图书账目中已经存在，则将其库存量增加（包 /括总库存量和现库存量），如果该书不存在，则在图书账目中增加一种书，总库存量和现库存量均为1。 if(BinarySearch(boo,BuyNum) /如果书库中有此书 boomid.TotNum+; /总库存加1 boomid.NowNum+; /现库存加1 cout入库成功.; cout已更改书库中该书的信息。编号b

19、oomid.num的书boomid.name作者是boomid.auth出版社是boomid.pub目前的总库存是boomid.TotNum现库存是boomid.NowNum; coutmid&total;i-) /插在适合位置 保持有序 booi=booi-1; /空出插入位置 cout该书在书库中不存在。设立新书目，请补全书的详细信息。; coutendl; strcpy(booi.num,BuyNum); coutbooi.NowNum; booi.TotNum=booi.NowNum; coutbooi.name; coutbooi.auth; coutbooi.pub; booi.n

20、ext=NULL; total+;/总量+1 cout已增加该书的信息。编号boomid.num的书boomid.name作者是boomid.auth出版社是boomid.pub目前的总库存是boomid.TotNum现库存是boomid.NowNum; cout入库成功.; void Borrow(ook &boo,lend &Lin,char BorrowNum,char CaNum)/借阅：如果一种书的现库存量大于零，则借出一本书，将现库存量减1， /并登记借阅者的图书证号和归还期限。 Bor *p,*q; LinkList *m,*n; if(!BinarySearch(boo,Bor

21、rowNum)|total=0) /如果没有找到此书 cout0) /看现库存是否大于0 boomid.NowNum-;/借出一本，少1 if(boomid.next=NULL) /若该书信息下显示该种书还没被人借过 m=(LinkList *)malloc(sizeof(LNode);/分配 boomid.next=m;/该图书信息中的链表的第一个结点 strcpy(m-CardNum,CaNum); m-next=NULL;/后一个结点为空 else /如果已经有人在借这书了 m=boomid.next; while(m-next) /遍历到最后一个结点 m=m-next; n=(Link

22、List *)malloc(sizeof(LNode);/分配空间，增加1个结点 m-next=n; strcpy(n-CardNum,CaNum);/记录证号 n-next=NULL; int i=0; for(i=0;inext)p=p-next;/遍历到最后一个结点 q=(Bor *)malloc(sizeof(Boro);/分配空间 p-next=q; strcpy(q-BNum,BorrowNum); /记录书号coutq-RetDate; q-next=NULL;cout借阅成功.;coutBNum,BorrowNum); cout输入归还日期:; coutp-RetDate; p

23、-next=NULL; Retotal+; /借阅证号信息总数加1 cout借阅成功.; coutendl; else cout借阅失败.该书现在库存为0.; coutendl; void Return(ook &boo,lend &Lin,char ReturnNum,char BorrowerNum)/4、 归还：注销对借阅者的登记，改变该书的现存量。 Bor *p,*q; LinkList *m,*n; int flag=0;/设置一个参数 if(!BinarySearch(boo,ReturnNum)|!total) /没书 cout书库中无此书.; coutCardNum,Borro

24、werNum) /如果是第一个借的人还的 boomid.NowNum+; /现库存加1 boomid.next=m-next; /删除结点 free(m); /释放该结点的空间空间 else while(m-next) /查找归还者的借阅者结点 if(!strcmp(m-next-CardNum,BorrowerNum) /如果找到 n=m-next; /n为归还者的借阅结点 m-next=n-next; /m指向归还者的借阅结点的下一结点 free(n); /释放空间 boomid.NowNum+; /现库存加1 break; m=m-next; /在借阅者表里查找借阅者信息 for(int

25、 i=0;iBNum,ReturnNum) /如果是归还的是借的第一本书 Lini.next=p-next; /指向下一借书结点 free(p); /释放结点空间 cout成功归还该书.; coutnext) /找到归还书的借书结点 if(!strcmp(p-next-BNum,ReturnNum) /如果找到 q=p-next; /q为归还书的借书结点 p-next=q-next; /p指向下一借书结点 free(q); /释放空间 cout成功归还该书.; coutnext; for(int k=0;kRetotal;k+) if(!Link.next) int j; for(j=k;jR

26、etotal;j+) Linj=Linj+1; /其后都往前移一位，覆盖掉当前信息 strcpy(Linj.CNum, ); /删除图书证号 Retotal-; /图书证数减1 /删除当前状态下没借书的图书证的信息，节省空间 if(flag=0) printf(无该证信息.n);void SearchByNum(ook &boo,char SeaNum)/BY NUM 根据书号查找 LinkList *p; p=boomid.next; if(BinarySearch(boo,SeaNum)=false) cout对不起，未找到您想查找的书。; coutendl; else/找到了的话 cou

27、t 书号 书名 作者 出版社 现库存 总库存 endl; cout boomid.num boomid.name boomid.auth boomid.pub boomid.NowNum boomid.TotNumendl; if(boomid.next!=NULL) cout 已借该书的 endl; cout 图书证号 endl; while(p) coutCardNumnext; while(p) coutCardNumnext; coutendl; /显示查找的书籍的信息void Menu() /菜单cout-M E N U-; coutendl; cout ; coutendl; co

28、ut 1. 采编入库：新购入一种书，如果该书在图书账目中已经存在， ; coutendl; cout 则将其库存量增加(包括总库存量和现库存量)。 ; coutendl; cout 如果该书不存在，则在图书账目中增加一种书， ; coutendl; cout 总库存量和现库存量均为输入的数字。 ; coutendl; cout 3. 借阅：如果一种书的现库存量大于零，则借出一本书，将现库存量减1， ; coutendl; cout 并登记借阅者的图书证号和归还期限。 ; coutendl; cout 4. 归还：注销对借阅者的登记，改变该书的现存量。 ; coutendl; cout 5. 按

29、书号查找。 ; coutendl; cout ; coutendl; cout-请 选 择 你 需 要 的 操 作-; coutendl; void main() ook Bo; lend Lin; char BNum20; char CNum20; cout-欢 迎 进 入 图 书 管 理 系 统!-; coutendl; Menu(); int choice=10; int SearchCho=10,ViewCho=10; while(choice!=0) cout-请 选 择 你 需 要 的 操 作-; coutchoice; switch(choice) case 1:/采编入库 co

30、utBNum; Buy(Bo,BNum); break; case 2:/借阅 cout请输入想要借阅的书的书号:; coutBNum; coutCNum; Borrow(Bo,Lin,BNum,CNum); break; case 3:/归还 cout请输入想要归还的书的书号:; coutBNum; coutCNum;待添加的隐藏文字内容3 Return(Bo,Lin,BNum,CNum); break; case 4:/查找/根据书号查找 coutBNum; SearchByNum(Bo,BNum); break; case 5:/查找/根据书号查找 coutBNum; SearchByNum(Bo,BNum); break; case 0:/退出系统 exit(0);break; default:cout输入错误!endl; exit(0); break;