約瑟夫環(huán)圖書館數(shù)據(jù)庫

1、設(shè)計題目一 約瑟夫環(huán)問題1、設(shè)計內(nèi)容設(shè)計一個帶頭結(jié)點的循環(huán)單鏈表類，實現(xiàn)約瑟夫環(huán)問題；問題描述：設(shè)編號為1,2,，n(n0)個人按順時針方向圍坐-圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m從第一個人開始順時針方向自1起順序報數(shù)。報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù).如此下去，直到所有人全部出列為止。要求設(shè)計一個程序模擬此過程，并給出出列人的編號序列。 測試數(shù)據(jù)： n=7,7個人的密碼依次為3,1,7,2,4,8,4 初始報數(shù)上限值m=202、設(shè)計需求分析在數(shù)據(jù)結(jié)構(gòu)中，循環(huán)單鏈表的優(yōu)點就是在鏈表的任意結(jié)點處都可以

2、對整個鏈表進行掃描。本題目的是實現(xiàn)對順時針的一圈數(shù)據(jù)進行報數(shù)，第一次報數(shù)m值是給出的，值為20.以后每一次報數(shù)值m根據(jù)新的密碼所給定，這樣就決定了算法中必須有一個給報數(shù)m傳值的過程。要求報到m的人出列，而且出列的形式是顯示他的編號，而不是密碼本身，所以算法中必須有一個計數(shù)器，記錄編號，找到位置輸出編號，在把密碼給m，然后刪除密碼。依次循環(huán)，而且每一次循環(huán)計數(shù)器要從1開始計數(shù)，循環(huán)直到鏈表為空。3、概要設(shè)計（1）建立node存儲結(jié)構(gòu)要實現(xiàn)約瑟夫環(huán)的輸出，首先要對環(huán)內(nèi)是數(shù)字建立存儲結(jié)構(gòu)。對數(shù)字進行鏈表存儲。 如下：class node t hao; t data; node *next;frien

3、d class yuesefu; ; （2）將相關(guān)數(shù)據(jù)結(jié)構(gòu)放入類里進行定義定義如下： 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）每種算法的實現(xiàn) 以下是實現(xiàn)建立鏈表的算法： 用尾插法建立鏈表，為了讓數(shù)據(jù)正序存放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 ; /建立新節(jié)點s-data=ai; /尾插法插入數(shù)據(jù) s-hao=j;j+; rear-next=s; rear=s; rear-next=first; 程序結(jié)束之前釋放所建立的結(jié)點空間template yuesefu: yuesefu( ) node *p,*q;p=first-next; while (p!=first) q=p; p=p-next; delete q; delete first;顯示運行的結(jié)果template void yuesefu:printlist(

5、)node *p; p=first-next; while (p!=first) coutdatanext; coutendl;根據(jù)要求查找密碼，記錄編號直到循環(huán)結(jié)束找出所有密碼的編號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;/尾指針與頭節(jié)點連接形成單循環(huán)鏈表first=first-next;/刪除不帶數(shù)據(jù)的頭結(jié)點for(int i=1;in;i+)j=1;while(jnext;j+; /

6、查找到第x個節(jié)點r-next=first-next;/摘連，把第r個結(jié)點接到first的下一個結(jié)點 x=first-data;couthaonext;/連接成一個單循環(huán)鏈couthaoendl;4、詳細設(shè)計#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 ; /建立新節(jié)點s-data=ai; /尾插法插入數(shù)據(jù) 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、;/尾指針與頭節(jié)點連接形成單循環(huán)鏈表first=first-next;/刪除不帶數(shù)據(jù)的頭結(jié)點for(int i=1;in;i+)j=1;while(jnext;j+; /查找到第x個節(jié)點r-next=first-next;/摘連，把第r個結(jié)點接到first的下一個結(jié)點 x=first-data;couthaonext;/連接成一個單循環(huán)鏈couthaoendl;void main() int a10=3,1,7,2,4,8,4; yuesefu obj(a,7); obj.printlist(); obj.chazhao(7); 5、調(diào)試分析運行結(jié)果如下： 題目要求輸出編號，在找到密碼之前要利

10、用一個中間變量記錄密碼的編號，循環(huán)直到鏈表為空。 設(shè)計題目二 圖書管理系統(tǒng)1、 設(shè)計內(nèi)容設(shè)計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務(wù)。要求：（1）每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量；（2)對書號建立索引表（線性表）以提高查找效率；（3)系統(tǒng)主要功能如下：*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加；*借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量；*歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。2、 設(shè)計需求分析題目要求每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量，所以要對圖書建立結(jié)構(gòu)體類

11、型，要求對書號建立索引表（線性表）以提高查找效率，所以要對書號進行索引，建立結(jié)構(gòu)體代碼如下：typedef struct boro/借書行為 char bnum20;/借書的書號 char retdate8;/歸還日期 struct boro *next;bor;typedef struct linkbook bor *next; /該圖書證的借書行為 char cnum20; /卡號 int total; /借書的數(shù)量lendlist_init_size;/借書人數(shù)組/圖書的結(jié)構(gòu)體信息typedef struct lnode char cardnum20;/圖書證號 struct lnode

12、 *next;linklist; /借書人typedef struct book/每種圖書需要登記的內(nèi)容包括書號isbn、書名、作者、出版社、總庫存量和現(xiàn)庫存量。 char num20;/書號 char name20;/書名 char auth20;/作者 char pub20;/出版社 int totnum;/總庫存 int nownum;/現(xiàn)庫存 linklist *next;/借了該書的人ookmaxsize;3、 概要設(shè)計分為以下幾個函數(shù)：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)/借閱：如果一種書的現(xiàn)庫存量大于零，則借出一本書，將現(xiàn)庫存量減1， /并登記借閱者的圖書證號和歸還期限。void return(ook &boo,lend &lin,char returnnum,char borrowernum)/4、 歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。void buy(ook &boo, char buynum)/采編入庫：新購入一種書，如

14、果該書在圖書賬目中已經(jīng)存在，則將其庫存量增加（包 /括總庫存量和現(xiàn)庫存量），如果該書不存在，則在圖書賬目中增加一種書，總庫存量和現(xiàn)庫存量均為1。4、 詳細設(shè)計如下：#include#include #include #include #define maxsize 100 /最大值定義為100#define list_init_size 100/圖書證使用者最大值定義為100/借書人的結(jié)構(gòu)體typedef struct boro/借書行為 char bnum20;/借書的書號 char retdate8;/歸還日期 struct boro *next;bor;typedef struct li

15、nkbook bor *next; /該圖書證的借書行為 char cnum20; /卡號 int total; /借書的數(shù)量lendlist_init_size;/借書人數(shù)組/圖書的結(jié)構(gòu)體信息typedef struct lnode char cardnum20;/圖書證號 struct lnode *next;linklist; /借書人typedef struct book/每種圖書需要登記的內(nèi)容包括書號isbn、書名、作者、出版社、總庫存量和現(xiàn)庫存量。 char num20;/書號 char name20;/書名 char auth20;/作者 char pub20;/出版社 int

16、totnum;/總庫存 int nownum;/現(xiàn)庫存 linklist *next;/借了該書的人ookmaxsize;int retotal;/讀者數(shù)量int total; /定義外部變量.書的種類數(shù)/結(jié)構(gòu)體初始化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、;/外部函數(shù)mid，用來返回查找到的位置bool binarysearch(ook boo,char searchnum) /折半查找法查找比較書號 /用bool函數(shù)，但由于函數(shù)不能有兩個返回值,所以設(shè)置一個外部變量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)/采編入庫：新購入一種書，如果該書在圖書賬目中已經(jīng)存在，則將其庫存量增加（包 /括總庫存量和現(xiàn)庫存量），如果該書不存在，則在圖書賬目中增加一種書，總庫存量和現(xiàn)庫存量均為1。 if(binarysearch(boo,buynum) /如果書庫中有此書 boomid.totnum+; /總庫存加1 boomid.nownum+; /現(xiàn)庫存加1 cout入庫成功.; cout已更改書庫中該書的信息。編號b

19、oomid.num的書作者是boomid.auth出版社是boomid.pub目前的總庫存是boomid.totnum現(xiàn)庫存是boomid.nownum; coutmid&total;i-) /插在適合位置 保持有序 booi=booi-1; /空出插入位置 cout該書在書庫中不存在。設(shè)立新書目，請補全書的詳細信息。; 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現(xiàn)庫存是boomid.nownum; cout入庫成功.; void borrow(ook &boo,lend &lin,char borrownum,char canum)/借閱：如果一種書的現(xiàn)庫存量大于零，則借出一本書，將現(xiàn)庫存量減1， /并登記借閱者的圖書證號和歸還期限。 bor *p,*q; linklist *m,*n; if(!binarysearch(boo,bor

21、rownum)|total=0) /如果沒有找到此書 cout0) /看現(xiàn)庫存是否大于0 boomid.nownum-;/借出一本，少1 if(boomid.next=null) /若該書信息下顯示該種書還沒被人借過 m=(linklist *)malloc(sizeof(lnode);/分配 boomid.next=m;/該圖書信息中的鏈表的第一個結(jié)點 strcpy(m-cardnum,canum); m-next=null;/后一個結(jié)點為空 else /如果已經(jīng)有人在借這書了 m=boomid.next; while(m-next) /遍歷到最后一個結(jié)點 m=m-next; n=(link

22、list *)malloc(sizeof(lnode);/分配空間，增加1個結(jié)點 m-next=n; strcpy(n-cardnum,canum);/記錄證號 n-next=null; int i=0; for(i=0;inext)p=p-next;/遍歷到最后一個結(jié)點 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+; /借閱證號信息總數(shù)加1 cout借閱成功.; coutendl; else cout借閱失敗.該書現(xiàn)在庫存為0.; coutendl; void return(ook &boo,lend &lin,char returnnum,char borrowernum)/4、 歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。 bor *p,*q; linklist *m,*n; int flag=0;/設(shè)置一個參數(shù) if(!binarysearch(boo,returnnum)|!total) /沒書 cout書庫中無此書.; coutcardnum,borro

24、wernum) /如果是第一個借的人還的 boomid.nownum+; /現(xiàn)庫存加1 boomid.next=m-next; /刪除結(jié)點 free(m); /釋放該結(jié)點的空間空間 else while(m-next) /查找歸還者的借閱者結(jié)點 if(!strcmp(m-next-cardnum,borrowernum) /如果找到 n=m-next; /n為歸還者的借閱結(jié)點 m-next=n-next; /m指向歸還者的借閱結(jié)點的下一結(jié)點 free(n); /釋放空間 boomid.nownum+; /現(xiàn)庫存加1 break; m=m-next; /在借閱者表里查找借閱者信息 for(int

25、 i=0;ibnum,returnnum) /如果是歸還的是借的第一本書 lini.next=p-next; /指向下一借書結(jié)點 free(p); /釋放結(jié)點空間 cout成功歸還該書.; coutnext) /找到歸還書的借書結(jié)點 if(!strcmp(p-next-bnum,returnnum) /如果找到 q=p-next; /q為歸還書的借書結(jié)點 p-next=q-next; /p指向下一借書結(jié)點 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; /其后都往前移一位，覆蓋掉當(dāng)前信息 strcpy(linj.cnum, ); /刪除圖書證號 retotal-; /圖書證數(shù)減1 /刪除當(dāng)前狀態(tài)下沒借書的圖書證的信息，節(jié)省空間 if(flag=0) printf(無該證信息.n);void searchbynum(ook &boo,char seanum)/by num 根據(jù)書號查找 linklist *p; p=boomid.next; if(binarysearch(boo,seanum)=false) cout對不起，未找到您想查找的書。; coutendl; else/找到了的話 cou

27、t 書號 書名 作者 出版社 現(xiàn)庫存 總庫存 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. 采編入庫：新購入一種書，如果該書在圖書賬目中已經(jīng)存在， ; coutendl; cout 則將其庫存量增加(包括總庫存量和現(xiàn)庫存量)。 ; coutendl; cout 如果該書不存在，則在圖書賬目中增加一種書， ; coutendl; cout 總庫存量和現(xiàn)庫存量均為輸入的數(shù)字。 ; coutendl; cout 3. 借閱：如果一種書的現(xiàn)庫存量大于零，則借出一本書，將現(xiàn)庫存量減1， ; coutendl; cout 并登記借閱者的圖書證號和歸還期限。 ; coutendl; cout 4. 歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。 ; coutendl; cout 5. 按

29、書號查找。 ; coutendl; cout ; coutendl; cout-請 選 擇 你 需 要 的 操 作-; coutendl; void main() ook bo; lend lin; char bnum20; char cnum20; cout-歡 迎 進 入 圖 書 管 理 系 統(tǒng)!-; 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:/查找/根據(jù)書號查找 coutbnum; searchbynum(bo,bnum); break; case 5:/查找/根據(jù)書號查找 coutbnum; searchbynum(bo,bnum)

31、; break; case 0:/退出系統(tǒng) exit(0);break; default:cout輸入錯誤!endl; exit(0); break; 5、 調(diào)試分析運行結(jié)果如下：可選擇的菜單：選擇的結(jié)果：設(shè)計題目三 一元多項式加法計算1、設(shè)計內(nèi)容1、任務(wù)：預(yù)先給出兩個一元多項式，并且按照指數(shù)非遞減的，將其用鏈表結(jié)構(gòu)存儲。2、設(shè)計要求： 1）輸入并建立多項式;2）輸出多項式;3）兩個多項式相加,并建立輸出多項式.2、需求分析一元多項式分為指數(shù)、系數(shù)兩部分，所以用鏈表存儲時要定義指數(shù)和系數(shù)兩個變量，在輸出之前要對輸入的多項式進行排序，按照指數(shù)非遞減的順序存放，用冒泡法對其排序，指數(shù)和系數(shù)要全部交

32、換。之后加和。3、概要設(shè)計存儲結(jié)構(gòu)如下：typedef struct node / 定義多項式的每一項 float c; /多項式的系數(shù) int e; /多項式的指數(shù) struct node *next;/指向下一項dainode;分為以下函數(shù)：dainode * jiafa(dainode *a,dainode *b)/多項式加法計算void jiaohuan(dainode *p,dainode *q)/交換p，q指針所指的系數(shù)和指數(shù)void maopao(dainode *h)/采用冒泡法對鏈表每一項排序void show(dainode * h)/顯示結(jié)果dainode * creat

33、() /用鏈表存放多項式（帶頭結(jié)點）4、詳細設(shè)計代碼如下：#include#define null0typedef struct node / 定義多項式的每一項 float c; /多項式的系數(shù) int e; /多項式的指數(shù) struct node *next;/指向下一項dainode;dainode * creat() /用鏈表存放多項式（帶頭結(jié)點） dainode *h,*p; int e,i,n; /n為多項式的項數(shù) float c; h=new dainode; h-next=null; do /當(dāng)n小于1，重新輸入 coutn; while(n1); for(i=1;i=n;i+

34、) cout第i項的系數(shù)和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指針所指的系數(shù)和指數(shù)float temp;/交換指數(shù)的變量 int temp1;/交換系數(shù)的變量 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的所有結(jié)點排序 p1=h-next; for(p=h-next;p!=pi;p=p-next)/排好一趟在從第一個開始排，pi控制排序次數(shù)，減少不必要的排序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為結(jié)果鏈表的表頭 t=new dainode; t-next=null; p1=a-next;p2=b-next; while(p1&p2) if(p1-ep2-e) p=ne