约瑟夫环图书馆数据库

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.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.auth; coutbooi.pub; booi.n

20、ext=null; total+;/总量+1 cout已增加该书的信息。编号boomid.num的书作者是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.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; return(bo,lin,bnum,cnum); break; case 4:/查找/根据书号查找 coutbnum; searchbynum(bo,bnum); break; case 5:/查找/根据书号查找 coutbnum; searchbynum(bo,bnum)

31、; break; case 0:/退出系统 exit(0);break; default:cout输入错误!endl; exit(0); break; 5、 调试分析运行结果如下：可选择的菜单：选择的结果：设计题目三 一元多项式加法计算1、设计内容1、任务：预先给出两个一元多项式，并且按照指数非递减的，将其用链表结构存储。2、设计要求： 1）输入并建立多项式;2）输出多项式;3）两个多项式相加,并建立输出多项式.2、需求分析一元多项式分为指数、系数两部分，所以用链表存储时要定义指数和系数两个变量，在输出之前要对输入的多项式进行排序，按照指数非递减的顺序存放，用冒泡法对其排序，指数和系数要全部交

32、换。之后加和。3、概要设计存储结构如下：typedef struct node / 定义多项式的每一项 float c; /多项式的系数 int e; /多项式的指数 struct node *next;/指向下一项dainode;分为以下函数：dainode * jiafa(dainode *a,dainode *b)/多项式加法计算void jiaohuan(dainode *p,dainode *q)/交换p，q指针所指的系数和指数void maopao(dainode *h)/采用冒泡法对链表每一项排序void show(dainode * h)/显示结果dainode * creat

33、() /用链表存放多项式（带头结点）4、详细设计代码如下：#include#define null0typedef struct node / 定义多项式的每一项 float c; /多项式的系数 int e; /多项式的指数 struct node *next;/指向下一项dainode;dainode * creat() /用链表存放多项式（带头结点） dainode *h,*p; int e,i,n; /n为多项式的项数 float c; h=new dainode; h-next=null; do /当n小于1，重新输入 coutn; while(n1); for(i=1;i=n;i+

34、) cout第i项的系数和ce; p=new dainode; p-c=c;p-e=e; p-next=h-next;/用头插法建立链表 h-next=p; return h;void jiaohuan(dainode *p,dainode *q)/交换p，q指针所指的系数和指数float temp;/交换指数的变量 int temp1;/交换系数的变量 temp1=p-e;p-e=q-e;q-e=temp1; temp=p-c;p-c=q-c;q-c=temp;void maopao(dainode *h)/采用冒泡法对链表每一项排序 dainode *pi,*p1,*p,*q; p=h-n

35、ext; while(p-next!=null) p=p-next; pi=p; /pi指向最后一次交换的位置，初值为表尾 while(pi!=h-next)/对h的所有结点排序 p1=h-next; for(p=h-next;p!=pi;p=p-next)/排好一趟在从第一个开始排，pi控制排序次数，减少不必要的排序q=p-next;if(p-eq-e)jiaohuan(p,q); p1=p;pi=p1; dainode * jiafa(dainode *a,dainode *b)/多项式加法计算 float x; dainode *p1,*p2,*p,*t;/t为结果链表的表头 t=new dainode; t-next=null; p1=a-next;p2=b-next; while(p1&p2) if(p1-ep2-e) p=new