数据结构专业课程设计题目

《数据结构和算法分析》课程设计内容体系关键内容《数据结构课程设计》课程，可使学生深化了解书本知识，致力于用学过理论知识和上机取得实践经验，处理具体、复杂实际问题，培养软件工作者所需动手能力、独立处理问题能力。该课程设计侧重软件设计综合训练，包含问题分析、总体结构设计、用户界面设计、程序设计基础技能和技巧、多人合作，以至一整套软件工作规范训练和科学作风培养。课程设计要求学生必需仔细阅读《数据结构和算法分析》课程设计方案，认真主动完成课程设计要求。有问题立即主动经过多种方法和老师联络沟通。学生要发挥自主学习能力，充足利用时间，安排好课程设计时间计划，并在课程设计过程中不停检测自己计划完成情况，立即向老师汇报。课程设计根据教学要求需要两周时间完成，两周中天天（按每七天5天）最少要上3-4小时机来调试C语言设计程序，总共最少要上机调试程序30小时。数据结构课程设计具体内容此次课程设计完成以下模块（共9个模块，学生能够在其中最少挑选6个功效块完成，但有**号模块是必需要选择）（1）运动会分数统计**任务：参与运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不一样项目取前五名或前三名积分；取前五名积分分别为：7、5、3、2、1，前三名积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）功效要求：能够输入各个项目标前三名或前五名成绩；能统计各学校总分；能够按学校编号、学校总分、男女团体总分排序输出；能够按学校编号查询学校某个项目标情况；能够按项目编号查询取得前三或前五名学校。要求：输入数据形式和范围：20以内整数（假如做得愈加好能够输入学校名称，运动项目标名称）输出形式：有汉字提醒，各学校分数为整形界面要求：有合理提醒，每个功效能够设置菜单，依据提醒，能够完成相关功效要求。存放结构：学生自己依据系统功效要求自己设计，不过要求运动会相关数据要存放在数据文件中。（数据文件数据读写方法等相关内容在c语言程序设计书上，请自学处理）请在最终上交资料中指明你用到存放结构；测试数据：要求使用1、全部正当数据；2、整体非法数据；3、局部非法数据。进行程序测试，以确保程序稳定。测试数据及测试结果请在上交资料中写明；（2）订票系统任务：经过此系统能够实现以下功效：录入：能够录入航班情况（数据能够存放在一个数据文件中，数据结构、具体数据自定）查询：能够查询某个航线情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；能够输入起飞抵达城市，查询飞机航班情况；订票：能够订票（订票情况能够存在一个数据文件中，结构自己设定），假如该航班已经无票，能够提供相关可选择航班；退票：可退票，退票后修改相关数据文件；用户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变能够修改航班数据文件要求：依据以上功效说明，设计航班信息，订票信息存放结构，设计程序完成功效；（3）文章编辑**功效：输入一页文字，程序能够统计出文字、数字、空格个数。静态存放一页文章，每行最多不超出80个字符，共N行；要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现次数，并输出该次数；（3）删除某一子串，并将后面字符前移。（4）存放结构使用线性表，分别用多个子函数实现对应功效；输入数据形式和范围：能够输入大写、小写英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后文章；（4）约瑟夫环（Joseph）任务：编号是1，2，……,nn个人根据顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始次序报数，报到m时停止报数。报m人出列，将她密码作为新m值，从她在顺时针方向下一个人开始重新从1报数，如此下去，直到全部些人全部出列为止。设计一个程序来求出出列次序。要求：利用单向循环链表存放结构模拟此过程，根据出列次序输出各个人编号。测试数据：m初值为20，n=7,7个人密码依次为3，1，7，2，4，7，4，首先m=6,则正确输出是什么？输入数据：建立输入处理输入数据，输入m初值，n，输入每个人密码，建立单循环链表。输出形式：建立一个输出函数，将正确输出序列（5）猴子选大王**任务：一堆猴子全部有编号，编号是1，2，3...m,这群猴子（m个）根据1-m次序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这么依次下来，直到圈中只剩下最终一只猴子，则该猴子为大王。输入数据：输入m,nm,n为整数，n<m输出形式：汉字提醒根据m个猴子，数n个数方法，输出为大王猴子是几号，建立一个函数来实现此功效（6）建立二叉树，层序、先序遍历（用递归或非递归方法全部能够）**任务：要求能够输入树各个结点，并能够输出用不一样方法遍历遍历序列；分别建立建立二叉树存放结构输入函数、输出层序遍历序列函数、输出先序遍历序列函数；（7）赫夫曼树建立任务：建立建立最优二叉树函数要求：能够建立函数输入二叉树，并输出其赫夫曼树在上交资料中请写明：存放结构、基础算法（能够使用程序步骤图）、输入输出、源程序、测试数据和结果、算法时间复杂度、另外能够提出算法改善方法；（8）纸牌游戏**任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2倍数牌翻一次，直到最终一张牌；然后，从第3张开始，以3为基数，是3倍数牌翻一次，直到最终一张牌；然后…从第4张开始，以4为基数，是4倍数牌翻一次，直到最终一张牌；...再依次5倍数牌翻一次，6，7直到以52为基数翻过，输出：这时正面向上牌有哪些？（9）图建立及输出任务：建立图存放结构（图类型能够是有向图、无向图、有向网、无向网，学生能够任选两种类型），能够输入图顶点和边信息，并存放到对应存放结构中，以后输出图邻接矩阵。要求：给出图深度优先和广度优先遍历算法，并给出遍历过程动态演示效果上交相关内容要求上交结果内容必需由以下四个部分组成，缺一不可1．上交源程序：学生根据课程设计具体要求所开发全部源程序（应该放到一个文件夹中）；2．上交程序说明文件：（保留在.txt中）在说明文档中应该写明上交程序所在目录，上交程序主程序文件名，假如需要安装，要有程序安装使用说明；3．课程设计汇报：（保留在word文档中，文件名要求根据"姓名-学号-课程设计汇报"起名，如文件名为"张三-001-课程设计汇报".doc）根据课程设计具体要求建立功效模块，每个模块要求根据以下多个内容认真完成；其中包含:需求分析：在该部分中叙述，每个模块功效要求概要设计：在此说明每个部分算法设计说明（能够是描述算法步骤图），每个程序中使用存放结构设计说明（假如指定存放结构请写出该存放结构定义。具体设计：各个算法实现源程序，对每个题目要有对应源程序（能够是一组源程序，每个功效模块采取不一样函数实现）源程序要根据写程序规则来编写。要结构清楚，关键函数关键变量，关键功效部分要加上清楚程序注释。调试分析：测试数据，测试输出结果，时间复杂度分析，和每个模块设计和调试时存在问题思索（问题是哪些？问题怎样处理？），算法改善设想。4.课设总结：（保留在word文档中）总结能够包含:课程设计过程收获、碰到问题、碰到问题处理问题过程思索、程序调试能力思索、对数据结构这门课程思索、在课程设计过程中对《数据结构》课程认识等内容《数据结构和算法分析》――课程内容体系关键内容教学单元模块具体教学内容绪论绪论部分是全书预备知识，关键对ADL语言、数据结构和算法、算法分析基础、OOP、和C++做了简单介绍基础数据结构基础数据结构部分包含线性表、堆栈和队列、数组、字符串、整数集合类、树（包含AVL树、伸展树等）、图（包含网络流等问题讨论）、散列（Hash）等经典算法经典算法部分关键介绍了若干经典算法实现，并给出必需复杂性分析和比较过程，具体包含递归、排序、查找和内存管理等复杂数据结构复杂数据结构部分关键包含优先级队列、不相交集合类和文件结构等算法设计技巧经典算法设计技巧介绍，关键包含贪婪算法、分治算法、动态计划、回溯算法和随机化算法等应用应用部分是上述数据结构和经典算法部分应用示例，具体包含事件驱动模拟、等价类、残缺棋盘和图象压缩等问题讨论，在课时许可情况下还会介绍摊还分析、红黑树等

《数据结构和算法分析》课程实践内容体系关键内容实践教学单元模块实践教学基础要求实践教学具体内容趣味程序设计实践1.熟悉编程环境2.复习C语言程序设计基础内容1.开学第一、二周部署若干趣味程序设计题目，如奇数阶幻阵算法、万年历算法、迷宫算法等。并完成：2.随机产生n个整数，然后用一个排序算法将它们从小到大排序。3.试编一程序，用贪心法求解通常着色问题。链表应用试验1.熟悉链表结构2.掌握链表结构上多种操作3.学会利用链表结构求解问题1.试将本章介绍两种Josephus问题求解过程在计算机中实现，实现时要求输出不是整数，而是实际人名。2.设A和B分别为两个带有头结点有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表指针。请写出并在计算机上实现将这两个链表合并为一个带头结点有序循环链表算法。栈和队列应用试验1.熟悉栈和队列结构2.掌握栈和队列结构上多种操作3.学会利用栈和队列结构求解问题1.设计实现一个求解n阶Hanoi塔问题算法提醒：将n个圆盘由A依次移到C，B作为辅助塔座。当n=1时，能够直接完成。不然，将塔座A顶上n-1个圆盘移动到塔座B上，用塔座C作为辅助塔座；然后移第n个圆盘；最终将塔座B上n-1个圆盘移到塔座C上，并用塔座A作为辅助塔座。2.依据书中介绍思想，设计并实现一个对简化表示式求值系统。3.在计算机上模拟实现农夫过河问题解。文本文件检索试验1.熟悉字符串操作2.学会利用字符串操作进行文本检索和查询。1.依据课堂介绍设计实现KMP算法2.试设计一个简单文本编辑器，使之含有对字符串输入、输出、插入、删除、查找和替换等功效3.设计实现一个通用判定回文个数问题算法程序稀疏矩阵和广义表试验1．熟悉稀疏矩阵和广义表结构2．掌握稀疏矩阵和广义表结构上多种操作3．学会利用稀疏矩阵和广义表结构求解问题1.设计实现两个一般矩阵相乘算法2.实现用三元组表示法实现稀疏矩阵相加及转置算法3.设计实现两个N次一元多项式相加算法程序树结构试验1.熟悉树和二叉树结构2.掌握树和二叉树结构上多种操作3.学会利用树和二叉树结构求解问题1.设计一个程序，依据二叉树先根序列和对称序序列创建一棵用左右指针表示二叉树2.依据哈夫曼算法创建哈夫曼树，并求树中每个外部结点编码3.设计一个程序，把中缀表示式转换成一棵二叉树，然后经过后序遍历计算表示式值4.设计实现一个完成对BST树进行插入、删除、查找操作算法，并期望有部分同学能深入把该算法改写为针对AVL树相关算法图结构试验1.熟悉图结构2.掌握图结构上多种操作3.学会利用图结构求解问题采取两种不一样图表示方法，实现拓扑排序和关键路径求解过程。使用实现算法对于下图所表示AOE网，求出各活动可能最早开始时间和最晚开始时间。输出整个工程最短完成时间是多少?哪些活动是关键活动?说明哪项活动提升速度后能造成整个工程提前完成?分析不一样存放结构对于算法效率影响。散列表试验1.熟悉散列表结构2.掌握散列函数生成方法,掌握常规冲突处理措施3.学会利用散列结构求解问题试依据整年级学生姓名，结构一个散列表，选择合适散列函数和处理碰撞方法，设计并实现插入、删除和查找算法，统计碰撞发生次数。（用拉链法处理碰撞时负载因子取2，用开地址法时取1/2）航班信息查询和检索试验设计1.掌握查找和排序多种算法2.学会选择和设计实际问题所需查找和排序算法对于直接插入排序、直接选择排序、起泡排序、Shell排序、快速排序和堆排序等六种算法进行上机实习。要求：1.被排序对象由计算机随机生成，长度分别取20，100，500三种。2.算法中增加比较次数和移动次数统计功效。3.对实习结果做比较分析。4.设计实现一个航班信息查询和检索系统课程试验参考教材：魏开平等编著.数据结构教导和试验.清华大学出版社，第1版瞿有甜，《数据结构和算法分析》试验指导书，.9

试验1猴子选大王任务：一堆猴子全部有编号，编号是1，2，3...m,这群猴子（m个）根据1-m次序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这么依次下来，直到圈中只剩下最终一只猴子，则该猴子为大王。输入数据：输入m,nm,n为整数，n<m输出形式：汉字提醒根据m个猴子，数n个数方法，输出为大王猴子是几号，建立一个函数来实现此功效。试验内容：源程序：#include<stdio.h>#include<stdlib.h>typedefstructnode{ intdata; structnode*next;}ListNode;typedefListNode*LinkList;/*建立单循环链表函数*/LinkListInitRing(intn,LinkListR){ ListNode*p,*q; inti; R=q=(ListNode*)malloc(sizeof(ListNode)); for(i=1;i<n;i++){ p=(ListNode*)malloc(sizeof(ListNode)); q->data=i; q->next=p;q=p; } p->data=n; p->next=R; R=p; returnR;}/*选择函数*/LinkListDeleteDeath(intn,intk,LinkListR){ inti,j; ListNode*p,*q; p=R; for(i=1;i<=n/2;i++) { for(j=1;j<=k-1;j++) p=p->next; q=p->next; p->next=q->next; printf("%4d",q->data); if(i%10==0)printf("\n"); free(q); } R=p; returnR;}/*输出函数*/voidOutRing(intn,LinkListR){ inti; ListNode*p; p=R; for(i=1;i<=n/2;i++,p=p->next) {printf("%4d",p->data); if(i%10==0)printf("\n"); } printf("\n"); printf("猴大王号码：\n");printf("4%d",p->next); }/*主函数*/voidmain(){ LinkListR; intn,k; LinkListInitRing(intn,LinkListR); printf("猴子总数N:"); scanf("%d",&n); printf("报到要被淘汰数字K:"); scanf("%d",&k); printf("被淘汰猴子：\n"); R=InitRing(n,R); R=DeleteDeath(n,k,R); printf("\n");OutRing(n,R);} 试验结果：试验2订票系统任务：经过此系统能够实现以下功效：录入：能够录入航班情况（数据能够存放在一个数据文件中，数据结构、具体数据自定）查询：能够查询某个航线情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；能够输入起飞抵达城市，查询飞机航班情况；订票：能够订票（订票情况能够存在一个数据文件中，结构自己设定），假如该航班已经无票，能够提供相关可选择航班；退票：可退票，退票后修改相关数据文件；用户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变能够修改航班数据文件要求：依据以上功效说明，设计航班信息，订票信息存放结构，设计程序完成功效；试验内容：源程序：#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<io.h>#include<math.h>#include<string.h>#include<ctype.h>#defineTRUE1#defineFALSE0typedefintBOOL;#defineNEW(type,size)(type*)malloc(sizeof(type)*size)typedefstruct_date{/*日期*/intm_year;intm_month;intm_day;}DATE;typedefstruct_time{/*时间*/intm_hour;intm_min;}TIME;typedefstruct_flight{/*航班数据*/intm_fltno;/*航班号，若此组员为-1，则表示此航班未使用*/charm_szFrom[30];/*起飞港*/charm_szPass[30];/*途经港*/charm_szTo[30];/*抵达港*/TIMEm_start;/*起飞时间*/TIMEm_arrive;/*抵达时间*/TIMEm_fly;/*飞行固定时间*/intm_people;/*乘客限额*/}FLIGHT,*PFLIGHT;typedefstruct_passengernode{/*乘客数据*/charm_szName[20];/*姓名*/charm_szCorp[30];/*单位*/charm_szNumber[19];/*身份证号，考虑到字母情况，故使用字符串*/DATEm_Date;/*订票日期*/intm_fltno;/*航班号*/intm_seatno;/*座位号*/}PASSENGER,*PPASSENGER;typedefstruct_psgnode{/*乘客结点*/PASSENGERm_psg;struct_psgnode*next;}NODE,*PNODE;/*清空键盘缓冲区*/voidClearBuffer(void);/*读取航班数据*/voidReadFlight(FLIGHTfltlist[]);/*读取乘客数据*/voidReadPassenger(PNODEpsglist);/*添加航班*/BOOLAddFlight(FLIGHTfltlist[],PFLIGHTfltdata);/*删除航班*/voidDelFlight(FLIGHTfltlist[],intindex);/*添加乘客*/voidAddPassenger(PNODEpsglist,PPASSENGERpsgdata);/*删除乘客*/BOOLDelPassenger(PNODEpsglist,intindex);/*清空乘客链表*/voidClearPsgList(PNODEpsglist);/*取得乘客总数*/unsignedintGetPsgCount(PNODEpsglist);BOOLdatecmp(DATE*date1,DATE*date2);voidBook(FLIGHTfltlist[],PNODEpsglist);voidquery(FLIGHTfltlist[],PNODEpsglist);voidfltnumber(FLIGHTfltlist[]);voidpsgname(PNODEpsglist);voidfromto(FLIGHTfltlist[]);voidfltdat(FLIGHTfltlist[],PNODEpsglist);/*保留航班数据*/voidSaveFlight(FLIGHTfltlist[]);/*保留乘客数据*/voidSavePassenger(PNODEpsglist);/*退出*/voidQuit(FLIGHTfltlist[],PNODEpsglist);BOOLdatecmp(DATE*date1,DATE*date2){return(date1->m_year==date2->m_year&&date1->m_month==date2->m_month&&date1->m_day==date2->m_day);}BOOLtimecmp(TIME*time1,TIME*time2){return(time1->m_hour==time2->m_hour&&time1->m_min==time2->m_min);}voidClearBuffer(void){getchar();}voidReadFlight(FLIGHTfltlist[]){FILE*fp;if((fp=fopen("flight.dat","rb"))!=NULL)fread(fltlist,sizeof(FLIGHT),40,fp);else{inti;for(i=0;i<40;i++)fltlist[i].m_fltno=-1;}fclose(fp);}voidReadPassenger(PNODEpsglist){FILE*fp;if((fp=fopen("psg.dat","rb"))==NULL)psglist->next=NULL;else{inti,n;fread(&n,sizeof(int),1,fp);for(i=0;i<n;i++){PASSENGERpsg;fread(&psg,sizeof(PASSENGER),1,fp);AddPassenger(psglist,&psg);}}}BOOLAddFlight(FLIGHTfltlist[],PFLIGHTfltdata){inti;BOOLbResult=FALSE;for(i=0;i<40;i++){if(fltlist[i].m_fltno==-1){memcpy(&fltlist[i],fltdata,sizeof(FLIGHT));bResult=TRUE;break;}}returnbResult;}voidDelFlight(FLIGHTfltlist[],intindex){fltlist[index].m_fltno=-1;}voidAddPassenger(PNODEpsglist,PPASSENGERpsgdata){PNODEp,q;for(p=psglist;p->next!=NULL;p=p->next);q=NEW(NODE,1);memcpy(&q->m_psg,psgdata,sizeof(PASSENGER));q->next=NULL;p->next=q;}BOOLDelPassenger(PNODEpsglist,intindex){inti=0;PNODEp,q;for(p=psglist->next;p->next!=NULL;p=p->next)i++;if(p!=NULL&&i==index-1){q=p->next;p->next=q->next;free(q);returnTRUE;}elsereturnFALSE;}voidClearPsgList(PNODEpsglist){PNODEp=psglist->next,q;while(p!=NULL&&p->next!=NULL){q=p;p=p->next;free(q);}}unsignedintGetPsgCount(PNODEpsglist){PNODEp;unsignedints=0;for(p=psglist->next;p!=NULL;p=p->next)s++;returns;}voidBook(FLIGHTfltlist[],PNODEpsglist){charc='y';BOOLb;while(c=='y'||c=='Y'){inti;PASSENGERpsg;printf("请输入航班号：");scanf("%d",&psg.m_fltno);while(psg.m_fltno>=10000||psg.m_fltno<0){printf("请重新输入：");scanf("%d",&psg.m_fltno);}for(i=0;i<40;i++){if(fltlist[i].m_fltno==psg.m_fltno){ PNODEp; BOOL*q; intj; printf("请输入订票日期：(yyyy,mm,dd)"); scanf("%d,%d,%d",&psg.m_Date.m_year,&psg.m_Date.m_month, &psg.m_Date.m_day); q=NEW(int,fltlist[i].m_people); for(j=0;j<fltlist[i].m_people;j++) q[j]=FALSE; for(p=psglist->next;p!=NULL;p=p->next) { if(datecmp(&p->m_psg.m_Date,&psg.m_Date)&& psg.m_fltno==p->m_psg.m_fltno) q[p->m_psg.m_seatno-1]=TRUE; } printf("以下座位还未有些人订："); for(j=0;j<fltlist[i].m_people;j++) { if(!q[j]) printf("%d",j+1); } printf("\n请输入订票座位号："); scanf("%d",&psg.m_seatno); b=FALSE; do { intk; if(psg.m_seatno>0&&psg.m_seatno<=fltlist[i].m_people+1) { if(!q[psg.m_seatno-1]) { b=TRUE; break; } else printf("这个座位有些人了！"); } else printf("数据非法！"); scanf("%d",&psg.m_seatno); }while(!b); printf("请输入乘客姓名：");scanf("%s",psg.m_szName);printf("请输入乘客单位："); scanf("%s",psg.m_szCorp);printf("请输入乘客身份证号："); scanf("%s",psg.m_szNumber);AddPassenger(psglist,&psg); printf("您订票已成功。"); free(q);}}c=getchar();}}voidquery(FLIGHTfltlist[],PNODEpsglist){for(;;){charc;system("cls");printf("航班查询\n");printf("~~~~~~~~\n");printf("1.按航班号查询\n");printf("2.按姓名查询乘客\n");printf("3.按起飞、抵达港查询\n");printf("4.按日期查询航班情况\n");printf("5.返回\n");printf("\n请选择1-5：");c=getchar();switch(c){case'1': fltnumber(fltlist); break;case'2': psgname(psglist); break;case'3': fromto(fltlist); break;case'4': fltdat(fltlist,psglist); break;case'5': break;default: continue;}if(c=='5')break;}}voidfltnumber(FLIGHTfltlist[]){charc='y';while(c=='y'||c=='Y'){BOOLb=FALSE;intfltno,i;printf("能够查询航班号：");for(i=0;i<40;i++){if(fltlist[i].m_fltno!=-1){ b=TRUE; printf("%d",fltlist[i].m_fltno);}}if(!b){printf("无\n按任意键返回。");getch();return;}printf("\n请输入要查询航班号：");scanf("%d",&fltno);for(i=0;i<40;i++){if(fltlist[i].m_fltno==fltno){ printf("%s--%s--%s\n",fltlist[i].m_szFrom,fltlist[i].m_szPass, fltlist[i].m_szTo); printf("起飞时间：%2d:%02d抵达时间：%2d:%02d飞行固定时间：%2d:%02d\n", fltlist[i].m_start.m_hour,fltlist[i].m_start.m_min, fltlist[i].m_arrive.m_hour,fltlist[i].m_arrive.m_min, fltlist[i].m_fly.m_hour,fltlist[i].m_fly.m_min); printf("乘客限额：%d\n",fltlist[i].m_people); break;}}printf("继续查询吗？(y/n)");ClearBuffer();c=getchar();}}voidpsgname(PNODEpsglist){charc='y';while(c=='y'||c=='Y'){charname[20];PNODEp;BOOLb=FALSE;printf("请输入乘客姓名：");scanf("%s",name);for(p=psglist->next;p!=NULL;p=p->next){if(strcmp(p->m_psg.m_szName,name)==0){ b=TRUE; printf("姓名：%s单位：%s身份证号：%s\n",p->m_psg.m_szName, p->m_psg.m_szCorp,p->m_psg.m_szNumber); printf("订票日期：%d-%d-%d",p->m_psg.m_Date.m_year, p->m_psg.m_Date.m_month,p->m_psg.m_Date.m_day); printf("航班号：%d座位号：%d",p->m_psg.m_fltno,p->m_psg.m_seatno);break;}}if(!b){printf("查无此人，按任意键退出");getch();return;}printf("是否继续查询？(y/n)");ClearBuffer();c=getchar();}}voidfromto(FLIGHTfltlist[]){charc='y';while(c=='y'||c=='Y'){BOOLb=FALSE;charfrom[30],to[30];inti;printf("请输入起飞港：");scanf("%s",from);printf("请输入抵达港：");scanf("%s",to);for(i=0;i<40;i++){if(strcmp(fltlist[i].m_szFrom,from)==0){ if(strcmp(fltlist[i].m_szTo,to)==0) { b=TRUE; break; }}}if(b){printf("%s--%s--%s\n",fltlist[i].m_szFrom,fltlist[i].m_szPass,fltlist[i].m_szTo);printf("起飞时间：%2d:%02d抵达时间：%2d:%02d飞行固定时间：%2d:%02d\n",fltlist[i].m_start.m_hour,fltlist[i].m_start.m_min,fltlist[i].m_arrive.m_hour,fltlist[i].m_arrive.m_min,fltlist[i].m_fly.m_hour,fltlist[i].m_fly.m_min);printf("乘客限额：%d",fltlist[i].m_people);}elseprintf("无此飞机");getch();printf("是否继续查询？");ClearBuffer();c=getchar();}}voidfltdat(FLIGHTfltlist[],PNODEpsglist){intpeople[40],i;DATEdate;PNODEp;for(i=0;i<40;i++)people[i]=0;printf("请输入您要查询日期(yyyy,mm,dd)：");scanf("%d,%d,%d",&date.m_year,&date.m_month,&date.m_day);for(p=psglist->next;p!=NULL;p=p->next){if(datecmp(&date,&p->m_psg.m_Date)){for(i=0;i<40;i++){ if(fltlist[i].m_fltno==p->m_psg.m_fltno) people[i]++;}}}for(i=0;i<40;i++){if(people[i]>0){printf("%d%s--%s--%s人数：%d",fltlist[i].m_fltno,fltlist[i].m_szFrom,fltlist[i].m_szPass,fltlist[i].m_szTo,people[i]);}}getch();}voidAdd(FLIGHTfltlist[]){charc='y';while(c=='y'||c=='Y'){FLIGHTflt;BOOLb;printf("请输入航班号(1-10000)：");scanf("%d",&flt.m_fltno);printf("请输入起飞港：");scanf("%s",flt.m_szFrom);printf("请输入途经港：");scanf("%s",flt.m_szPass);printf("请输入抵达港：");scanf("%s",flt.m_szTo);printf("请输入起飞时间(hh:mm)：");scanf("%d:%d",&flt.m_start.m_hour,&flt.m_start.m_min);printf("请输入抵达时间(hh:mm)：");scanf("%d:%d",&flt.m_arrive.m_hour,&flt.m_arrive.m_min);printf("请输入飞行固定时间(hh:mm)：");scanf("%d:%d",&flt.m_fly.m_hour,&flt.m_fly.m_min);printf("请输入乘客限额：");scanf("%d",&flt.m_people);ClearBuffer();if(AddFlight(fltlist,&flt))printf("添加成功，");elseprintf("添加失败，");printf("继续添加航班吗(Y/N)？");c=getchar();}}voidDel(FLIGHTfltlist[]){BOOLb=FALSE;inti,fltno;charc='y';while(c=='y'||c=='Y'){printf("能够取消航班号：");for(i=0;i<40;i++){if(fltlist[i].m_fltno!=-1){ b=TRUE; printf("%d",fltlist[i].m_fltno);}}if(!b){printf("无\n按任意键返回。");getch();return;}printf("\n请输入要取消航班号：");scanf("%d",&fltno);for(i=0;i<40;i++){if(fltlist[i].m_fltno==fltno){ DelFlight(fltlist,i); break;}}printf("继续删除吗(y/n)？");ClearBuffer();c=getchar();}}voidQuery(FLIGHTfltlist[]){charc='y';while(c=='y'||c=='Y'){BOOLb=FALSE;inti,fltno;printf("能够查询航班号：");for(i=0;i<40;i++){if(fltlist[i].m_fltno!=-1){ b=TRUE; printf("%d",fltlist[i].m_fltno);}}if(!b){printf("无\n按任意键返回。");getch();return;}printf("\n请输入要查询航班号：");scanf("%d",&fltno);for(i=0;i<40;i++){if(fltlist[i].m_fltno==fltno){ printf("%s--%s--%s乘客限额：%d\n",fltlist[i].m_szFrom, fltlist[i].m_szPass,fltlist[i].m_szTo,fltlist[i].m_people); printf("起飞时间：%2d:%02d抵达时间：%2d:%02d飞行固定时间：%2d:%02d\n", fltlist[i].m_start.m_hour,fltlist[i].m_start.m_min, fltlist[i].m_arrive.m_hour,fltlist[i].m_arrive.m_min, fltlist[i].m_fly.m_hour,fltlist[i].m_arrive.m_min); break;}}printf("继续查询吗(y/n)？");ClearBuffer();c=getchar();}}voidOneDay(FLIGHTfltlist[],PNODEpsglist){charc='y';while(c=='y'||c=='Y'){DATEdate;intpeople[40],i;PNODEp;for(i=0;i<40;i++)people[i]=0;printf("请输入您要管理日期(yyyy,mm,dd)：");scanf("%d,%d,%d",&date.m_year,&date.m_month,&date.m_day);for(p=psglist->next;p!=NULL;p=p->next){if(datecmp(&p->m_psg.m_Date,&date)){ for(i=0;i<40;i++) { if(fltlist[i].m_fltno==p->m_psg.m_fltno) people[i]++; }}}for(i=0;i<40;i++){if(fltlist[i].m_fltno!=-1){ printf("%d%s--%s--%s人数：%d\n",fltlist[i].m_fltno, fltlist[i].m_szFrom,fltlist[i].m_szPass,fltlist[i].m_szTo, people[i]);}}printf("继续管理吗？(y/n)");ClearBuffer();c=getchar();}}voidMultiDay(FLIGHTfltlist[],PNODEpsglist){charc='y';while(c=='y'||c=='Y'){DATEdate[7];intn,i,j;intpeople[40][7];PNODEp;printf("请输入要查询天数(1-7)：");do{scanf("%d",&n);if(n>7||n<1) printf("输入非法，请重新输入：");}while(n>7||n<1);for(i=0;i<n;i++){printf("请输入第%d个日期(yyyy,mm,dd)：",i);scanf("%d,%d,%d",&date[i].m_year,&date[i].m_month,&date[i].m_day);}for(i=0;i<40;i++)for(j=0;j<7;j++) people[i][j]=0;for(p=psglist->next;p!=NULL;p=p->next){for(j=0;j<n;j++){ if(datecmp(&date[j],&p->m_psg.m_Date)) { for(i=0;i<40;i++) { if(fltlist[i].m_fltno==p->m_psg.m_fltno) people[i][j]++; } }}}for(i=0;i<40;i++){if(fltlist[i].m_fltno!=-1){ printf("%d%s--%s--%s",fltlist[i].m_fltno,fltlist[i].m_szFrom, fltlist[i].m_szPass,fltlist[i].m_szTo); for(j=0;j<n;j++) printf("%d",people[i][j]); printf("\n");}}printf("继续查询吗？(y/n)");ClearBuffer();c=getchar();}}voidManage(FLIGHTfltlist[],PNODEpsglist){for(;;){charc;system("cls");printf("航班管理\n");printf("~~~~~~~~\n");printf("1.查询航班基础情况\n");printf("2.对某天航班飞行情况管理\n");printf("3.近期航班飞行情况管理\n");printf("4.取消航班\n");printf("5.新增航班\n");printf("6.返回\n");printf("\n请选择1-6：");c=getchar();switch(c){case'1': Query(fltlist); break;case'2': OneDay(fltlist,psglist); break;case'3': MultiDay(fltlist,psglist); break;case'4': Del(fltlist); break;case'5': Add(fltlist); break;case'6': break;default: continue;}if(c=='6')break;}}voidSaveFlight(FLIGHTfltlist[]){FILE*fp;if((fp=fopen("flight.dat","wb"))==NULL){printf("不能打开flight.dat文件，航班数据无法保留。\n");fclose(fp);return;}fwrite(&fltlist[0],sizeof(FLIGHT),40,fp);fclose(fp);printf("航班数据已保留至flight.dat文件。\n");}voidSavePassenger(PNODEpsglist){FILE*fp;PNODEp;intn=GetPsgCount(psglist);unlink("psg.dat");if(n==0)return;if((fp=fopen("psg.dat","wb"))==NULL){printf("不能打开psg.dat文件，乘客数据无法保留。\n");fclose(fp);return;}fwrite(&n,sizeof(int),1,fp);for(p=psglist->next;p!=NULL;p=p->next)fwrite(&p->m_psg,sizeof(PASSENGER),1,fp);fclose(fp);printf("乘客数据已保留至psg.dat文件。\n");}voidQuit(FLIGHTfltlist[],PNODEpsglist){SaveFlight(fltlist);SavePassenger(psglist);}voidmain(void){FLIGHTfltlist[40];NODEpsglist;ReadFlight(fltlist);ReadPassenger(&psglist);for(;;){charc;system("cls");printf("飞机订票系统\n");printf("~~~~~~~~~~~~\n");printf("---主菜单---\n");printf("1.订票\n");printf("2.退票\n");printf("3.航班管理\n");printf("4.查询\n");printf("5.退出\n");printf("\n请选择1-5：");c=getchar();switch(c){case'1': Book(fltlist,&psglist); break;case'2': /*c_ticket(fltlist,&psglist);*/ break;case'3': Manage(fltlist,&psglist); break;case'4': query(fltlist,&psglist); break;case'5': Quit(fltlist,&psglist); break;default: continue;}if(c=='5')break;}ClearPsgList(&psglist);}试验3约瑟夫环（Joseph）任务：编号是1，2，……,nn个人根据顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始次序报数，报到m时停止报数。报m人出列，将她密码作为新m值，从她在顺时针方向下一个人开始重新从1报数，如此下去，直到全部些人全部出列为止。设计一个程序来求出出列次序。要求：利用单向循环链表存放结构模拟此过程，根据出列次序输出各个人编号。测试数据：m初值为20，n=7,7个人密码依次为3，1，7，2，4，7，4，首先m=6,则正确输出是什么？输入数据：建立输入处理输入数据，输入m初值，n，输入每个人密码，建立单循环链表。输出形式：建立一个输出函数，将正确输出序列试验内容:试验源程序:#include<iostream>usingnamespacestd;#defineN7typedefstructnode{ intdata; intsercet; structnode*next;}ListNode;typedefListNode*LinkList;//建立单循环链表函数LinkListInitRing(intn,LinkListR,inta[N]){ ListNode*p,*q; inti; R=q=(ListNode*)malloc(sizeof(ListNode)); for(i=0;i<n-1;i++) { p=(ListNode*)malloc(sizeof(ListNode)); q->data=i+1;q->sercet=a[i]; q->next=p; q=p; } p->data=n; p->sercet=a[n-1]; p->next=R; R=p; returnR;}//删除被数到人LinkListDelete(intn,LinkListR,intk){ inti,j; ListNode*p,*q; p=R; for(i=1;i<n;i++) { for(j=1;j<k;j++) p=p->next; q=p->next; p->next=q->next; cout<<q->data<<''; k=q->sercet; free(q); } R=p; cout<<"thelastis:"<<p->data; returnR;}voidmain(){ LinkListR; intn,i,m; cout<<"inputthenumberoftheman:"; cin>>n;cout<<"inputm:"; cin>>m; inta[N]; cout<<"inputtheserect:"<<endl; for(i=0;i<n;i++) cin>>a[i]; cout<<"被删除次序是："; R=InitRing(n,R,a); R=Delete(n,R,m); cout<<endl;}试验结果:试验4纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2倍数牌翻一次，直到最终一张牌；然后，从第3张开始，以3为基数，是3倍数牌翻一次，直到最终一张牌；然后…从第4张开始，以4为基数，是4倍数牌翻一次，直到最终一张牌；...再依次5倍数牌翻一次，6，7直到以52为基数翻过，输出：这时正面向上牌有哪些？试验内容:试验源程序:#include<iostream>usingnamespacestd;voidPcout1(inti,intj){ switch(i) { case0:cout<<"3"; break; case1:cout<<"4"; break; case2:cout<<"5"; break; case3:cout<<"6"; break; case4:cout<<"7"; break; case5:cout<<"8"; break; case6:cout<<"9"; break; case7:cout<<"10"; break; case8:cout<<"J"; break; case9:cout<<"Q"; break; case10:cout<<"K"; break; case11:cout<<"A"; break; case12:cout<<"2"; break; }switch(j) { case0:cout<<"草花"<<endl; break; case1:cout<<"黑桃"<<endl; break; case2:cout<<"红心"<<endl; break; case3:cout<<"方块"<<endl; break; }}intmain(){ intt=1,x=2; inti,j,a[13][4]; for(i=0;i<13;i++) for(j=0;j<4;j++) a[i][j]=t; while(x<53) { for(i=0;i<13;i++) { for(j=0;j<4;j++) if((i*4+j+1)%x==0) { if(t==1) t=0; else t=1; a[i][j]=t; } } x++; } cout<<"\n\n这时正面向上牌有："<<endl; for(i=0;i<13;i++) { for(j=0;j<4;j++) if(a[i][j]==1) Pcout1(i,j); }}试验结果(分三次截图):试验5赫夫曼树建立任务：建立建立最优二叉树函数要求：能够建立函数输入二叉树，并输出其赫夫曼树在上交资料中请写明：存放结构、基础算法（能够使用程序步骤图）、输入输出、源程序、测试数据和结果、算法时间复杂度、另外能够提出算法改善方法；试验内容：源程序：include<stdio.h>#include<stdlib.h>#include<malloc.h>#definem100structptree/*definethetypeofbanarytree*/{intw;structptree*lchild;structptree*rchild;};structpforest/*definethetypeofchainbelt*/{structpforest*link;structptree*root;};intWTL=0;voidmain(){structptree*hafm(intw[m],intn);voidtravel(structptree*head,intn);structptree*head;intn,i,w[m];printf("pleaseinputthesumofnode\n");scanf("%d",&n);printf("pleaseinputweightofeverynode\n");for(i=1;i<=n;i++)scanf("%d",&w[i]);head=hafm(w,n);travel(head,0);printf("ThelengthofthebestpathisWTL=%d",WTL);}voidtravel(structptree*head,intn){structptree*p;p=head;if(p!=NULL) {if((p->lchild)==NULL&&(p->rchild)==NULL) {printf("%d",p->w); printf("thehopsofthenodeis:%d\n",n); WTL=WTL+n*(p->w); } travel(p->lchild,n+1); travel(p->rchild,n+1); }}structptree*hafm(intw[m],intn){structpforest*inforest(structpforest*f,structptree*t);structpforest*p1,*p2,*f;structptree*ti,*t,*t1,*t2;inti;f=(structpforest*)malloc(sizeof(structpforest));f->link=NULL;for(i=1;i<=n;i++)/*producentreesthathaveonlyrootnode*/{ti=(structptree*)malloc(sizeof(structptree));ti->w=w[i];ti->lchild=NULL;ti->rchild=NULL;f=inforest(f,ti);}while(((f->link)->link)!=NULL)/*atleasthavetwobinarytrees*/{p1=f->link;p2=p1->link;f->link=p2->link;/*takeoutfrontaltwotrees*/t1=p1->root;t2=p2->root;free(p1);free(p2);t=(structptree*)malloc(sizeof(structptree));t->w=t1->w+t2->w;/*weightbeadded*/t->lchild=t1;t->rchild=t2;/*producethenewbinarytree*/f=inforest(f,t);}p1=f->link;t=p1->root;return(t);}structpforest*inforest(structpforest*f,structptree*t){structpforest*p,*q,*r;structptree*ti;r=(structpforest*)malloc(sizeof(structpforest));r->root=t;q=f;p=f->link;while(p!=NULL)/*lookforthepositiontobeinserted*/{ ti=p->root; if(t->w>ti->w) {q=p; p=p->link; }elsep=NULL;/*forceexitthecycle*/}r->link=q->link;q->link=r;return(f);}试验结果：1．2．试验6二叉树建立和遍厉任务：要求能够输入树各个结点，并能够输出用不一样方法遍历遍历序列；分别建立建立二叉树存放结构输入函数、输出层序遍历序列函数、输出先序遍历序列函数；试验内容:试验源程序:#include<malloc.h