数据结构经典题目及c语言代码.doc

数据结构课程设计题目(程序实现采用C语言)题目1：猴子选王（学时：3）一堆猴子都有编号，编号是1，2，3 .m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 /链表#include #include / 链表节点typedef struct _RingNode int pos; struct _RingNode *next;RingNode, *RingNodePtr;/ 创建约瑟夫环，pHead:链表头指针，count:链表元素个数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; / 构成环状链表void KickFromRing(RingNodePtr pHead, int n) RingNodePtr pCurr, pPrev; int i = 1; / 计数 pCurr = pPrev = pHead; while(pCurr != NULL) if (i = 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;/数组做：#include#include#includevoid SelectKing(int MonkeyNum, int CallNum);void main() int MonkeyNum; int CallNum; /* 输入猴子的个数 */ printf(Monkey Num = ); scanf(%d, &MonkeyNum); /* 输入M的值 */ printf(Call Num = ); scanf(%d, &CallNum); SelectKing(MonkeyNum, CallNum); void SelectKing(int MonkeyNum, int CallNum) int *Monkeys; / 申请一个数组，表示所有的猴子； int counter = 0; /计数，当计数为猴子个数时表示选到最后一个猴子了； int position = 0; / 位置，数组的下标，轮流遍历数组进行报数； int token = 0; / 令牌，将报数时数到M的猴子砍掉； / 申请猴子个数大小的数组，把桌子摆上。 Monkeys = (int *)malloc(sizeof(int)* MonkeyNum); if (NULL = Monkeys) printf(So many monkeys, system error.n); return; / 将数组的所有内容初始化为0，被砍掉的猴子设置为1 memset(Monkeys, 0, sizeof(int)*MonkeyNum); / 循环，直到选中大王 while(counter != MonkeyNum) / 如果这个位置的猴子之前没有砍掉，那么报数有效 if (Monkeysposition = 0) token+; / 成功报数一个，令牌+1，继续报数直到等于M / 如果报数到M，那么将这个猴子砍去 if (token = CallNum) Monkeysposition = 1; / 设置为1，表示砍去 counter+; / 计数增加 token = 0; / 设置为0，下次重新报数 / 如果是最后一个猴子，把它的位置打印，这个就是大王了 if (counter = MonkeyNum) printf(The king is the %d monkey.n, position+1); / 下一个猴子报数 position = (position + 1)%MonkeyNum; / 释放内存，开头为所有猴子创建的桌子 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。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行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，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。#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(请输入多项式的系数项和指数项);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 欢迎使用订房系统 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(欢迎使用退房系统：);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，已住人数：%d，住房人性别：男,p-roomnum,p-roomlevel,p-peoplenum);elseprintf(n 房间号：%d，房间等级：%d，已住人数：%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(请输入房间等级数:n); printf(Roomlevel:); scanf(%d,&roomlevel); for (i=1; i=roomlevel; i+) printf(n %d等级房间数:,i); scanf(%d,&roomi); printf(n %d房间内床位数:,i); scanf(%d,&bedi); sum+=roomi*bedi; head=creat(roomlevel,room,bed); while(k=1) printf( n欢迎光临 :n); printf(1:订房n2:退房n3:查询n4:退出系统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：文本文件单词的检索及计数（学时：6）要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。#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(输入要统计计数的单词：); 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中共出现了%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(输入要统计计数的单词：); 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单词第一次出现是在 %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单词第一次出现是在 %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链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。#include#include#define M 100typedef struct node/定义二叉树结点char data;struct node *lchild,*rchild;BTNode;BTNode *CreatBTree()/创建二叉树 (先序递归)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)/递归先序遍历二叉树函数 if(b!=NULL) printf(%c ,b-data); PreOrder(b-lchild); PreOrder(b-rchild); void InOrder(BTNode *b)/非递归中序遍历二叉树函数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)/非递归后序遍历二叉树函数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