數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目(程序?qū)崿F(xiàn)采用C語(yǔ)言)題目1：猴子選王（學(xué)時(shí)：3）一堆猴子都有編號(hào)，編號(hào)是1，2，3 .m，這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第n個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。要求：m及n要求從鍵盤輸入，存儲(chǔ)方式采用向量及鏈表兩種方式實(shí)現(xiàn)該問(wèn)題求解。 /鏈表#include #include / 鏈表節(jié)點(diǎn)typedef struct _RingNode int pos; struct _RingNode *next;RingNode, *RingNodePtr;/ 創(chuàng)建約瑟夫環(huán)，pHead:鏈表頭指針，count:鏈表元素個(gè)數(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; / 構(gòu)成環(huán)狀鏈表void KickFromRing(RingNodePtr pHead, int n) RingNodePtr pCurr, pPrev; int i = 1; / 計(jì)數(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) / 最后一個(gè) 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);/ 開(kāi)始出圈 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; /* 輸入猴子的個(gè)數(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; / 申請(qǐng)一個(gè)數(shù)組，表示所有的猴子； int counter = 0; /計(jì)數(shù)，當(dāng)計(jì)數(shù)為猴子個(gè)數(shù)時(shí)表示選到最后一個(gè)猴子了； int position = 0; / 位置，數(shù)組的下標(biāo)，輪流遍歷數(shù)組進(jìn)行報(bào)數(shù)； int token = 0; / 令牌，將報(bào)數(shù)時(shí)數(shù)到M的猴子砍掉； / 申請(qǐng)猴子個(gè)數(shù)大小的數(shù)組，把桌子擺上。 Monkeys = (int *)malloc(sizeof(int)* MonkeyNum); if (NULL = Monkeys) printf(So many monkeys, system error.n); return; / 將數(shù)組的所有內(nèi)容初始化為0，被砍掉的猴子設(shè)置為1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); / 循環(huán)，直到選中大王 while(counter != MonkeyNum) / 如果這個(gè)位置的猴子之前沒(méi)有砍掉，那么報(bào)數(shù)有效 if (Monkeysposition = 0) token+; / 成功報(bào)數(shù)一個(gè)，令牌+1，繼續(xù)報(bào)數(shù)直到等于M / 如果報(bào)數(shù)到M，那么將這個(gè)猴子砍去 if (token = CallNum) Monkeysposition = 1; / 設(shè)置為1，表示砍去 counter+; / 計(jì)數(shù)增加 token = 0; / 設(shè)置為0，下次重新報(bào)數(shù) / 如果是最后一個(gè)猴子，把它的位置打印，這個(gè)就是大王了 if (counter = MonkeyNum) printf(The king is the %d monkey.n, position+1); / 下一個(gè)猴子報(bào)數(shù) position = (position + 1)%MonkeyNum; / 釋放內(nèi)存，開(kāi)頭為所有猴子創(chuàng)建的桌子 free(Monkeys); return;題目2 ：字符逆轉(zhuǎn)（學(xué)時(shí)：3）從鍵盤讀入一個(gè)字符串，把它存入一個(gè)鏈表（每個(gè)結(jié)點(diǎn)存儲(chǔ)1個(gè)字符），并按相反的次序?qū)⒆址敵龅斤@示屏。#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 ：工資核算（學(xué)時(shí)：3）設(shè)有一個(gè)單位的人員工資有如下信息：name、department、 base pay、allowance、total?，F(xiàn)從鍵盤輸入一組人員工資數(shù)據(jù)并將它們存儲(chǔ)到名為paydata的文件中；再?gòu)膒aydata取出工資數(shù)據(jù)并給每個(gè)人的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(文件寫入出錯(cuò)n); fclose(fp); if(fp=fopen(paydata.dat,rb)=NULL) printf(Cant open filen); printf(修改過(guò)后的結(jié)果：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：滿足條件的有序表生成（學(xué)時(shí)：3）已知三個(gè)有序表A、B、C，它們皆由同一類元素構(gòu)成，現(xiàn)要求對(duì)于表A作以下運(yùn)算而獲得有序表D：排出A中所有的既在B中又在C中出現(xiàn)的元素。另外該任務(wù)要求具有建立有序表功能以及輸出有序表到屏幕的功能。#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：一元 多項(xiàng)式的減法（學(xué)時(shí)：6）設(shè)有兩個(gè)一元多項(xiàng)式A(x),B(x)，請(qǐng)完成運(yùn)算A(x)+B(x)、A(x)-B(x)，要求多項(xiàng)式采用鏈表進(jìn)行存儲(chǔ)。另外該任務(wù)要求具有建立多項(xiàng)式鏈表以及輸出多項(xiàng)式到屏幕的功能。#include struct Polynodeint coef;int exp;Polynode *next;Polynode,*Polylist;void Polycreate(Polylist head)Polynode *rear,*s;int c,e;rear=head;printf(請(qǐng)輸入多項(xiàng)式的系數(shù)項(xiàng)和指數(shù)項(xiàng));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：床位分配（學(xué)時(shí)：6）某客店有N個(gè)等級(jí)的房間，第k級(jí)客房有A（k）個(gè)，每個(gè)房間有B（k）個(gè)單人床，以菜單調(diào)用方式設(shè)計(jì)為單身旅客分配床位以及離店時(shí)收回床位的程序。要求分配成功時(shí)，印出旅客姓名、年齡、性別、到達(dá)日期、客房等級(jí)、房間號(hào)及床位號(hào)；分配不成功時(shí)，允許更改房間等級(jí)，若不更改等級(jí)，印出“滿客”提示。#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(請(qǐng)輸入性別（1為男，2為女）：);scanf(%d,&s);printf(nn 請(qǐng)輸入想入住的房間等級(jí)：);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訂單已下，請(qǐng)輸入客人信息: n); printf(名字:n); scanf(%s,name); printf(年齡 :n); scanf(%d,&age); printf(您的訂單3:n); printf(名字 年齡 性別 到達(dá)時(shí)間 房間等級(jí) 房間號(hào) 床位號(hào)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 請(qǐng)輸入房間號(hào)：);scanf(%d,&number);printf(nn 請(qǐng)輸入性別（1為男，0為女）：);scanf(%d,&s);printf(請(qǐng)輸入床位號(hào)：);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(所有等級(jí)房間空房); return;while(p-peoplenum!=NULL)if(p-sex=1)printf(n 房間號(hào)：%d，房間等級(jí)：%d，已住人數(shù)：%d，住房人性別：男,p-roomnum,p-roomlevel,p-peoplenum);elseprintf(n 房間號(hào)：%d，房間等級(jí)：%d，已住人數(shù)：%d，住房人性別：女,p-roomnum,p-roomlevel,p-peoplenum); while (ipeoplenum) if (p-bedi=1) printf(，已住床位號(hào)：%d,i+1); i+; printf(n);p=p-next;void main() int n,k=1,i,roomlevel,room10,bed10,sum=0; Room *head; printf(請(qǐng)輸入房間等級(jí)數(shù):n); printf(Roomlevel:); scanf(%d,&roomlevel); for (i=1; i=roomlevel; i+) printf(n %d等級(jí)房間數(shù):,i); scanf(%d,&roomi); printf(n %d房間內(nèi)床位數(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(請(qǐng)輸入您的選擇: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：文本文件單詞的檢索及計(jì)數(shù)（學(xué)時(shí)：6）要求編程建立一個(gè)文本文件，每個(gè)單詞不包括空格及跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫，完成以下功能：統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)、檢索輸出某單詞在文本文件中首次出現(xiàn)的行號(hào)及位置。#include#include#includetypedef struct StringWordchar ch100;SW;void CreatTextFile()char filename10,ch; FILE*fp; printf(請(qǐng)輸入所用的文件名:);scanf(n%s,filename);fp=fopen(filename,w); printf(請(qǐng)輸入一段文字，以$號(hào)結(jié)束: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)計(jì)計(jì)數(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)計(jì)計(jì)數(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：二叉樹(shù)的遍歷（學(xué)時(shí)：6）二叉樹(shù)以lson-rson鏈接方式存儲(chǔ)，以菜單方式設(shè)計(jì)并完成功能任務(wù)：建立并存儲(chǔ)樹(shù)、輸出前序遍歷結(jié)果、輸出中序遍歷結(jié)果、輸出后序遍歷結(jié)果、交換左右子樹(shù)、統(tǒng)計(jì)高度，其中對(duì)于中序、后序的遍歷運(yùn)算要求采用非遞歸方式。#include#include#define M 100typedef struct node/定義二叉樹(shù)結(jié)點(diǎn)char data;struct node *lchild,*rchild;BTNode;BTNode *CreatBTree()/創(chuàng)建二叉樹(shù) (先序遞歸)char ch;BTNode *b;scanf(%c,&ch);if(ch=#)/遞歸結(jié)束控制符b=NULL;elseb=(BTNode *)malloc(sizeof(BTNode);b-data=ch;b-lchild=CreatBTree();/遞歸先序建立左子樹(shù)b-rchild=CreatBTree();/遞歸先序建立右子樹(shù)return b;void PreOrder(BTNode *b)/遞歸先序遍歷二叉樹(shù)函數(shù) if(b!=NULL) printf(%c ,b-data); PreOrder(b-lchild); PreOrder(b-rchild); void InOrder(BTNode *b)/非遞歸中序遍歷二叉樹(shù)函數(shù)BTNode *stackM,*p;int top=-1;if(b!=NULL)p=b;while(top-1|p!=NULL)while(p!=NULL)/掃描p的所有左結(jié)點(diǎn)并入棧top+;stacktop=p;p=p-lchild;if(top-1)p=stacktop;/出棧訪問(wèn)結(jié)點(diǎn)top-;printf(%c ,p-data);p=p-rchild;/掃描p的右結(jié)點(diǎn)printf(n);void PostOrder(BTNode *b)/非遞歸后序遍歷二叉樹(shù)函數(shù)BTNode *stackM,*p;int sign,top=-1;if(b!=NULL)dowhile(b!=NULL)/ b所有左結(jié)點(diǎn)入棧 top+;stacktop=b;b=b-lchild;p=NULL; / p指向棧頂前一個(gè)已訪問(wèn)結(jié)點(diǎn)sign=1; /置b為已訪問(wèn)while(top!=-1 & sign)b=stacktop;/取出棧頂結(jié)點(diǎn)if(b-rchild=p) /右孩子不存在或右孩子已訪問(wèn)則訪問(wèn)bprintf(%c ,b-data);top-;p=b; /p指向被訪問(wèn)的結(jié)點(diǎn)elseb=b-rchild;/b指向右孩子結(jié)點(diǎn)sign=0;/置未訪問(wèn)標(biāo)記while(top!=-1);printf(n);void change(BTNode *b) /左右子樹(shù)交換(遞歸)BTNode *r;r=(BTNode *)malloc(sizeof(BTNode);int f1=0,f2=0;if(b=0) return ; /樹(shù)為空時(shí)，跳出 if(b-lchild) change(b-lchild); r-lchild=b-lchild; f1+; /有左子樹(shù)，符號(hào)位不為空 if(b-rchild) change(b-rchild); r-rchild=b-rchild; f2+; /有右子樹(shù)，符號(hào)位不為空if(f1=0) r-lchild=NULL; /否則，給中間變量賦空值if(f2=0) r-rchild=NULL;if(f1|f2) b-rchild=r-lchild; /左右子樹(shù)交換 b-lchild=r-rchild;int max(int m,int n)if(mn)return m;else return n;int count(BTNode *b) /計(jì)算樹(shù)高(遞歸)if(b=NULL)return 0;else re