數(shù)據(jù)結構課程設計題目(程序實現(xiàn)采用C語言)題目1：猴子選王（學時：3）一堆猴子都有編號，編號是1，2，3 .m，這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：m及n要求從鍵盤輸入，存儲方式采用向量及鏈表兩種方式實現(xiàn)該問題求解。 /鏈表#include #include / 鏈表節(jié)點typedef struct _RingNode int pos; struct _RingNode *next;RingNode, *RingNodePtr;/ 創(chuàng)建約瑟夫環(huán)，pHead:鏈表頭指針，count:鏈表元素個數(shù)void CreateRing(RingNodePtr pHead, int count) RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(-count 0) pCurr = (RingNodePtr)malloc(sizeof(RingNode); i+; pCurr-pos = i; pPrev-next = pCurr; pPrev = pCurr; pCurr-next = pHead; / 構成環(huán)狀鏈表void KickFromRing(RingNodePtr pHead, int n) RingNodePtr pCurr, pPrev; int i = 1; / 計數(shù) pCurr = pPrev = pHead; while(pCurr != NULL) if (i = n) / 踢出環(huán) printf(n%d, pCurr-pos); / 顯示出圈循序 pPrev-next = pCurr-next; free(pCurr); pCurr = pPrev-next; i = 1; pPrev = pCurr; pCurr = pCurr-next; if (pPrev = pCurr) / 最后一個 printf(nKing is %d, pCurr-pos); / 顯示出圈循序 free(pCurr); break; i+; int main() int n = 0, m = 0; RingNodePtr pHead = NULL; printf(M(person count) = ); scanf(%d, &m); printf(N(out number) = ); scanf(%d, &n); if(m = 0 | n pos = 1; pHead-next = NULL; CreateRing(pHead, m);/ 開始出圈 printf(nKick Order: ); KickFromRing(pHead, n); printf(n); system(pause); return 0;/數(shù)組做：#include#include#includevoid SelectKing(int MonkeyNum, int CallNum);void main() int MonkeyNum; int CallNum; /* 輸入猴子的個數(shù) */ printf(Monkey Num = ); scanf(%d, &MonkeyNum); /* 輸入M的值 */ printf(Call Num = ); scanf(%d, &CallNum); SelectKing(MonkeyNum, CallNum); void SelectKing(int MonkeyNum, int CallNum) int *Monkeys; / 申請一個數(shù)組，表示所有的猴子； int counter = 0; /計數(shù)，當計數(shù)為猴子個數(shù)時表示選到最后一個猴子了； int position = 0; / 位置，數(shù)組的下標，輪流遍歷數(shù)組進行報數(shù)； int token = 0; / 令牌，將報數(shù)時數(shù)到M的猴子砍掉； / 申請猴子個數(shù)大小的數(shù)組，把桌子擺上。 Monkeys = (int *)malloc(sizeof(int)* MonkeyNum); if (NULL = Monkeys) printf(So many monkeys, system error.n); return; / 將數(shù)組的所有內容初始化為0，被砍掉的猴子設置為1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); / 循環(huán)，直到選中大王 while(counter != MonkeyNum) / 如果這個位置的猴子之前沒有砍掉，那么報數(shù)有效 if (Monkeysposition = 0) token+; / 成功報數(shù)一個，令牌+1，繼續(xù)報數(shù)直到等于M / 如果報數(shù)到M，那么將這個猴子砍去 if (token = CallNum) Monkeysposition = 1; / 設置為1，表示砍去 counter+; / 計數(shù)增加 token = 0; / 設置為0，下次重新報數(shù) / 如果是最后一個猴子，把它的位置打印，這個就是大王了 if (counter = MonkeyNum) printf(The king is the %d monkey.n, position+1); / 下一個猴子報數(shù) position = (position + 1)%MonkeyNum; / 釋放內存，開頭為所有猴子創(chuàng)建的桌子 free(Monkeys); return;題目2 ：字符逆轉（學時：3）從鍵盤讀入一個字符串，把它存入一個鏈表（每個結點存儲1個字符），并按相反的次序將字符串輸出到顯示屏。#include #include struct node struct node *prev; char c; struct node *next;struct node *input(struct node *top);int main(void) struct node T,*top=&T,*bottom=&T,*p=NULL;T.prev=NULL;T.next=NULL;T.c=0;bottom=input(top);p=bottom-prev;while(p!=NULL) printf(%c,p-c); p=p-prev; return 0;struct node *input(struct node *top)struct node *t;char x;while(x=getchar()!=n) top-c=x; t=(struct node *)malloc(sizeof(struct node); top-next=t; t-prev=top; t-next=NULL; t-c=0; top=top-next;return top;題目3 ：工資核算（學時：3）設有一個單位的人員工資有如下信息：name、department、 base pay、allowance、total?，F(xiàn)從鍵盤輸入一組人員工資數(shù)據(jù)并將它們存儲到名為paydata的文件中；再從paydata取出工資數(shù)據(jù)并給每個人的base pay增加100元，增加后將工資數(shù)據(jù)顯示于屏幕(每行1人)。#include #include #define SIZE 2#define LENTH sizeof(struct stuff) struct stuff char name100; char department100; int basepay; int allowance; int total; stuffSIZE; main() FILE *fp; int i; printf(Please enter name department basepay allowance：n); for(i=0;iSIZE;i+) scanf(%s %s %f %f,&,&stuffi.department,&stuffi.basepay,&stuffi.allowance); if(fp=fopen(paydata.dat,wb)=NULL) printf(Cant open filen); return 0; for(i=0;iSIZE;i+) if(fwrite(&stuffi,LENTH,1,fp)!=1) printf(文件寫入出錯n); fclose(fp); if(fp=fopen(paydata.dat,rb)=NULL) printf(Cant open filen); printf(修改過后的結果：n); for(i=0;iSIZE;i+) fread(&stuffi,LENTH,1,fp); stuffi.total=stuffi.basepay+100+stuffi.allowance; printf(%-10s%-10s %f %f %fn,,stuffi.department,stuffi.basepay+100,stuffi.allowance,stuffi.total); fclose(fp); return 0; 題目4：滿足條件的有序表生成（學時：3）已知三個有序表A、B、C，它們皆由同一類元素構成，現(xiàn)要求對于表A作以下運算而獲得有序表D：排出A中所有的既在B中又在C中出現(xiàn)的元素。另外該任務要求具有建立有序表功能以及輸出有序表到屏幕的功能。#include void main() int a7,b5,c6,d7;int i,j,k,t,m;printf(nPlease enter 7 numbers of A:);for(i=0;i7;i+)scanf(%d,&ai);for(j=0;j6;j+)for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;printf(the sorted numbers：n);for(i=0;i7;i+)printf(%5d,ai); printf(nPlease enter 5 numbers of B:);for(i=0;i5;i+)scanf(%d,&bi);printf(n);for(j=0;j4;j+)for(i=0;ibi+1)t=bi;bi=bi+1;bi+1=t;printf(the sorted numbers:n);for(i=0;i5;i+)printf(%5d,bi); printf(nPlease enter 6 numbers of C:); for(i=0;i6;i+)scanf(%d,&ci); for(j=0;j5;j+)for(i=0;ici+1)t=ci;ci=ci+1;ci+1=t;printf(the sorted numbers：n);for(i=0;i6;i+)printf(%5d,ci);printf(n);for(i=0;i5;i+)for(j=0;j6;j+)if(bi=cj)for(k=0;k7;k+)if(bi=ak)ak=m;printf(n);k=0;for(i=0;i7;i+)if(ai!=m)dk=ai;k+;printf(生成的有序表d為 );for(i=0;ik;i+)printf(%4d,di);printf(n); 題目5：一元 多項式的減法（學時：6）設有兩個一元多項式A(x),B(x)，請完成運算A(x)+B(x)、A(x)-B(x)，要求多項式采用鏈表進行存儲。另外該任務要求具有建立多項式鏈表以及輸出多項式到屏幕的功能。#include struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;void Polycreate(Polylist head)Polynode *rear,*s;int c,e;rear=head;printf(請輸入多項式的系數(shù)項和指數(shù)項);scanf(%d,%d,&c,&e);while(c!=0)s=(Polynode*)malloc(sizeof(Polynode);s-coef=c;s-exp=e;rear-next=s;rear=s;scanf(%d,%d,&c,&e);rear-next=NULL;void Polyadd(Polylist polya,Polylist polyb)Polynode *p,*q,*tail,*temp;int sum;p=polya-next;q=polyb-next;tail=polya;while(p!=NULL&q!=NULL)if(p-expexp)tail-next=p;tail=p;p=p-next;else if(p-exp=q-exp)sum=p-coef+q-coef;if(sum!=0)p-coef=sum;tail-next=p;tail=p;p=p-next;temp=q;q=q-next;free(temp);elsetemp=p;p=p-next;free(temp);q=q-next;free(temp);elsetail-next=q;tail=q;q=q-next;if(p!=NULL)tail-next=p;elsetail-next=q;void Polysubstract(Polylist polya,Polylist polyb)Polylist h=polyb;Polylist p=pb-next;Polylist pd;while(p)p-coef*=-1;p=p-next;pd=Polyadd(pa,h);for(p=h-next;p;p=p-next)p-coef*=-1;return pd；void PrintPolyn(Polyn P)void printfPolyn(Polynode *head)Polynode *p=head-next;while(p)printf(%dx%d,p-coef,p-exp);if(p-next)printf(+);p=p-next;int main()Polynode *La,Lb;La=Polycreate();Lb=Polycreate();PrintPolyn(La);printf(/n);PrintPolyn(Lb);printf(/n);Polyadd(polya,polyb);printPolyn(polya);return 0;題目6：床位分配（學時：6）某客店有N個等級的房間，第k級客房有A（k）個，每個房間有B（k）個單人床，以菜單調用方式設計為單身旅客分配床位以及離店時收回床位的程序。要求分配成功時，印出旅客姓名、年齡、性別、到達日期、客房等級、房間號及床位號；分配不成功時，允許更改房間等級，若不更改等級，印出“滿客”提示。#include#include#include#include#define N 3typedef struct Roomint roomlevel;int roomnum;int bednum;int peoplenum;int bedN;int sex;char name10;struct Room *next;Room;Room *creat(int roomlevel,int room,int bed) Room *head,*p,*q; int i=1,j,h,num=1; head=(Room *)malloc(sizeof(Room);head-peoplenum=0;q=head;while (i=roomlevel) for(j=1; jroomlevel=i; p-roomnum=num+; p-peoplenum=0; p-sex=-1; for(h=0; hbedh=0; q-next=p; q=p; i+; p-next=NULL; return(head); void Init(Room *head)Room *p;int i;p=head;while(p!=NULL)p-peoplenum=0;p-sex=-1;for(i=0;ibedi=0;p=p-next;printf(nn 操作成功 n);void Getin(Room *head)Room *p;int i,s,lev,age;char name10;int number=0;int bednumber=0;printf(nn 歡迎使用訂房系統(tǒng) nn); printf(請輸入性別（1為男，2為女）：);scanf(%d,&s);printf(nn 請輸入想入住的房間等級：);scanf(%d,&lev);p=head-next;while(p!=NULL)if(p-roomlevel=lev)&(p-sex=s)|(p-sex=-1)for(i=0;ibedi=0)number=p-roomnum;bednumber=i+1;p-bedi=1;p-sex=s;p-peoplenum+;break;if(number!=0)break;p=p-next;if(number=0&bednumber=0)printf(n 滿客 n);else head-peoplenum+; printf(n訂單已下，請輸入客人信息: n); printf(名字:n); scanf(%s,name); printf(年齡 :n); scanf(%d,&age); printf(您的訂單3:n); printf(名字 年齡 性別 到達時間 房間等級 房間號 床位號n); if (s=1) printf(%s %d male 11-19 %d %d %dn,name,age,p-roomlevel,p-roomnum,bednumber); else printf(%s %d formale 11-19 %d %d %d n,name,age,p-roomlevel,p-roomnum,bednumber); printf(n); void Checkout(Room *head)Room *p;int number,bednumber,i,s;printf(歡迎使用退房系統(tǒng)：);printf(nn 請輸入房間號：);scanf(%d,&number);printf(nn 請輸入性別（1為男，0為女）：);scanf(%d,&s);printf(請輸入床位號：);scanf(%d,&bednumber);p=head-next;while(p!=NULL)if(p-roomnum=number)for(i=0;iroomlevel;i+)if(i+1=bednumber)p-bedi=0;p-peoplenum-;if(p-peoplenumpeoplenum=0;if(p-peoplenum=0)p-sex=-1;printf(您已退房，歡迎下次光臨);break;p=p-next;void Display(Room *head)Room *p;int i=0;p=head-next;printf(nn已訂房間查詢);if (head-peoplenum=NULL) printf(所有等級房間空房); return;while(p-peoplenum!=NULL)if(p-sex=1)printf(n 房間號：%d，房間等級：%d，已住人數(shù)：%d，住房人性別：男,p-roomnum,p-roomlevel,p-peoplenum);elseprintf(n 房間號：%d，房間等級：%d，已住人數(shù)：%d，住房人性別：女,p-roomnum,p-roomlevel,p-peoplenum); while (ipeoplenum) if (p-bedi=1) printf(，已住床位號：%d,i+1); i+; printf(n);p=p-next;void main() int n,k=1,i,roomlevel,room10,bed10,sum=0; Room *head; printf(請輸入房間等級數(shù):n); printf(Roomlevel:); scanf(%d,&roomlevel); for (i=1; i=roomlevel; i+) printf(n %d等級房間數(shù):,i); scanf(%d,&roomi); printf(n %d房間內床位數(shù):,i); scanf(%d,&bedi); sum+=roomi*bedi; head=creat(roomlevel,room,bed); while(k=1) printf( n歡迎光臨 :n); printf(1:訂房n2:退房n3:查詢n4:退出系統(tǒng)n); printf(請輸入您的選擇:n); scanf(%d,&n); switch(n) case 1: Getin(head); break; case 2: Checkout(head); break; case 3: Display(head);break; case 4: k=0; break; default : printf(Error! please input again:); break; 題目7：文本文件單詞的檢索及計數(shù)（學時：6）要求編程建立一個文本文件，每個單詞不包括空格及跨行，單詞由字符序列構成且區(qū)分大小寫，完成以下功能：統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)、檢索輸出某單詞在文本文件中首次出現(xiàn)的行號及位置。#include#include#includetypedef struct StringWordchar ch100;SW;void CreatTextFile()char filename10,ch; FILE*fp; printf(請輸入所用的文件名:);scanf(n%s,filename);fp=fopen(filename,w); printf(請輸入一段文字，以$號結束:n);scanf(%s,&ch); while(ch!=$) fwrite(&ch,sizeof(ch),1,fp); scanf(%c,&ch); fclose(fp);void CountWord() FILE *fp;SW S,T;char ch;char filename10; int i=0,number=0; printf(輸入文本文件名：); scanf(%s,filename);fp=fopen(filename,r); printf(輸入要統(tǒng)計計數(shù)的單詞：); scanf(%s,T.ch); while(!feof(fp) ch= fgetc(fp); if(ch= )if(i!=0)S.chi=0;i=0;if (strcmp(S.ch,T.ch)=0) number+;else if (ch=n) if (i!=0) S.chi=0; i=0; if (strcmp(S.ch,T.ch)=0)number+; else S.chi=ch; i+;if (number=0) printf(單詞不在文本中 n);elseprintf(單詞%s在文件%s中共出現(xiàn)了%d次:,T.ch,filename,number); fclose(fp);void SearchWord() FILE*fp;SW S,T;char filename10; int i,i_r,line,flag=0;char ch;printf(n輸入文本文件名：); scanf(%s,filename);fp=fopen(filename,r);printf(輸入要統(tǒng)計計數(shù)的單詞：); scanf(%s,T.ch); i=i_r=0;line=1;while(!feof(fp) ch=fgetc(fp); if (ch= ) if (i!=0) i_r+; S.chi=0;i=0;if (strcmp(T.ch,S.ch)=0)printf(%s單詞第一次出現(xiàn)是在 %d 行,%d列n,T.ch,line,i_r);flag=1;break; else if (ch=n) if (i!=0)i_r+; S.chi=0;if (strcmp(T.ch,S.ch)=0) printf(%s單詞第一次出現(xiàn)是在 %d 行,%d列n,T.ch,line,i_r); flag=1; break;i=0; i_r=0; line+;else line+; i_r=0; else S.chi=ch; i+; if (flag=0) printf(%s單詞不在文本中n,T.ch); fclose(fp); int main()CreatTextFile();CountWord();SearchWord();題目8：二叉樹的遍歷（學時：6）二叉樹以lson-rson鏈接方式存儲，以菜單方式設計并完成功能任務：建立并存儲樹、輸出前序遍歷結果、輸出中序遍歷結果、輸出后序遍歷結果、交換左右子樹、統(tǒng)計高度，其中對于中序、后序的遍歷運算要求采用非遞歸方式。#include#include#define M 100typedef struct node/定義二叉樹結點char data;struct node *lchild,*rchild;BTNode;BTNode *CreatBTree()/創(chuàng)建二叉樹 (先序遞歸)char ch;BTNode *b;scanf(%c,&ch);if(ch=#)/遞歸結束控制符b=NULL;elseb=(BTNode *)malloc(sizeof(BTNode);b-data=ch;b-lchild=CreatBTree();/遞歸先序建立左子樹b-rchild=CreatBTree();/遞歸先序建立右子樹return b;void PreOrder(BTNode *b)/遞歸先序遍歷二叉樹函數(shù) if(b!=NULL) printf(%c ,b-data); PreOrder(b-lchild); PreOrder(b-rchild); void InOrder(BTNode *b)/非遞歸中序遍歷二叉樹函數(shù)BTNode *stackM,*p;int top=-1;if(b!=NULL)p=b;while(top-1|p!=NULL)while(p!=NULL)/掃描p的所有左結點并入棧top+;stacktop=p;p=p-lchild;if(top-1)p=stacktop;/出棧訪問結點top-;printf(%c ,p-data);p=p-rchild;/掃描p的右結點printf(n);void PostOrder(BTNode *b)/非遞歸后序遍歷二叉樹函數(shù)BTNode *stackM,*p;int sign,top=-1;if(b!=NULL)dowhile(b!=NULL)/ b所有左結點入棧 top+;stacktop=b;b=b-lchild;p=NULL; / p指向棧頂前一個已訪問結點sign=1; /置b為已訪問while(top!=-1 & sign)b=stacktop;/取出棧頂結點if(b-rchild=p) /右孩子不存在或右孩子已訪問則訪問bprintf(%c ,b-data);top-;p=b; /p指向被訪問的結點elseb=b-rchild;/b指向右孩子結點sign=0;/置未訪問標記while(top!=-1);printf(n);void change(BTNode *b) /左右子樹交換(遞歸)BTNode *r;r=(BTNode *)malloc(sizeof(BTNode);int f1=0,f2=0;if(b=0) return ; /樹為空時，跳出 if(b-lchild) change(b-lchild); r-lchild=b-lchild; f1+; /有左子樹，符號位不為空 if(b-rchild) change(b-rchild); r-rchild=b-rchild; f2+; /有右子樹，符號位不為空if(f1=0) r-lchild=NULL; /否則，給中間變量賦空值if(f2=0) r-rchild=NULL;if(f1|f2) b-rchild=r-lchild; /左右子樹交換 b-lchild=r-rchild;int max(int m,int n)if(mn)return m;else return n;int count(BTNode *b) /計算樹高(遞歸)if(b=NULL)return 0;else re