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

1、数据结构课程设计题目(程序实现采用 C 语言)题目 1：猴子选王（学时：3）一堆猴子都有编号，编号是 1，2，3 .m ，这群猴子（ m个）按照 1-m 的顺序围坐一圈，从第 1 开始数，每数到第 n 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求： m及 n 要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。/ 链表#include #include / 链表节点typedef struct _RingNodeint pos;struct _RingNode *next;RingNode, *RingNodePtr;/ 创建约瑟夫环 ， p

2、Head: 链表头指针 ， 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

3、 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);br

4、eak;/显示出圈循 序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;/ 数组做：#in

5、clude#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; /申请一

6、个数组，表示所有的猴子；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 ，被砍掉的猴子设置为1memset(Monkeys

7、, 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 = Monk

8、eyNum)printf(The king is the %d monkey.n, position+1);/ 下一个猴子报数position = (position + 1)%MonkeyNum;/ 释放内存，开头为所有猴子创建的桌子free(Monkeys);return;题目 2 ：字符逆转（学时： 3）从键盘读入一个字符串， 把它存入一个链表 （每个结点存储 1 个字符），并按相反的次序将字符串输出到显示屏。#include #include struct nodestruct node *prev;char c;struct node *next;struct node *input

9、(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

10、(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 s

11、izeof(struct stuff)struct stuffchar name100;char department100;int basepay;int allowance;int total;stuffSIZE;main()FILE *fp;int i;printf(Please enter name department basepay allowance for(i=0;iSIZE;i+)： n);scanf(%s %s %f %f,&,&stuffi.department,&stuffi.basepay,&stuffi. allowance);if(fp=fo

12、pen(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.allowa

13、nce;printf(%-10s%-10s %f %f %fn,,stuffi.department,stuffi.basepay+1 00,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

14、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 numbersfor(i=0;i7;i+)printf(%5d,ai);： n);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;

15、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 numbersfor(i=0;i6;i+)printf(%5d,ci);： n);printf(n);for(i=0;i5;i+)for(j=0;j6;j+)if(bi=cj)for(k=0;k7;k+)i

16、f(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,*Polyl

17、ist;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;

18、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-n

19、ext;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=h

20、ead-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）个单人床，以菜单调用方式设计

21、为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。#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

22、)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;

23、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=

24、-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);elsehead-peoplenum+;printf(n订单已下，请输入客人信息: n);printf( 名字 :n); scanf(%s,name);printf( 年龄 :n); scanf(%d,&age);printf( 您的订单 3:n);printf( 名字年龄性别到达时间房间等级房间

25、号床位号 n);if (s=1)printf(%s%dmale11-19%d%d%dn,name,age,p-roomlevel,p-roomnum,bednumber);elseprintf(%s%dformale11-19%d%d%dn,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请输入性

26、别（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

27、=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 (

28、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;he

29、ad=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：文本文件单词的检索

30、及计数（学时： 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( 请输入一段文字，以$ 号结束

31、: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

32、=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+;elseS.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

33、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;

34、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+;elseline+; i_r=0;elseS.chi=ch; i+; if (flag=0)printf(%s单词不在文本中n,T.ch);fclose(fp);int main()CreatTextFile();CountWord();SearchWord();题目 8：二叉树的遍历（学时： 6）二叉树以 lson-rson 链接方式存储，以菜单方式设计并完成功能任务： 建立并存储树、

35、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。#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;

36、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 的所有

37、左结点并入栈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=(BTNo