课程设计内容体系主要内容
《数据结构课程设计》课程，可使学生深化理解书本知识，致力于用学过的理论知识和上机取得的实践经验，解决具体、复杂的实际问题，培养软件工作者所需的动手能力、独立解决问题的能力。该课程设计侧重软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧、多人合作，以至一整套软件工作规范的训练和科学作风的培养。
一、 课程设计要求
学生必须仔细阅读《数据结构与算法分析》课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。
学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时的向教师汇报。
课程设计按照教学要求需要两周时间完成，两周中每天（按每周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，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值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,n m,n 为整数，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.熟悉编程环1.开学第一、二周布置若干趣味程序设计题序设计实践 2.复习C语言程序设计的2.随机产生n个整数，然后用一种排序算法基本内容 将它们从小到大排序。 3.试编一程序，用贪心法求解一般的着色问题。 境 目，如奇数阶幻阵算法、万年历算法、迷宫算法等。并完成： 链表应1.熟悉链表结1.试将本章介绍的两种Josephus问题的求用实验 构 2.掌握链表结构上的各种2.设A与B分别为两个带有头结点的有序循解过程在计算机中实现，实现时要求输出的不是整数，而是实际的人名。 操作 3.学会运用链环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个表结构求解链表的指针。请写出并在计算机上实现将问题 这两个链表合并为一个带头结点的有序循环链表的算法。 栈与队1.熟悉栈和队1. 设计实现一个求解n阶Hanoi塔问题的算列应用实验 列结构 2.掌握栈和队列结构上的各种操作 3.学会运用栈和队列结构求解问题 座。 2. 根据书中介绍的思想，设计并实现一个对简化表达式求值的系统。 3. 在计算机上模拟实现农夫过河问题的解。 盘移到塔座C上，并用塔座A作为辅助塔第n个圆盘；最后将塔座B上的n-1个圆法 提示：将n个圆盘由A依次移到C，B作为辅助塔座。当n=1时，可以直接完成。否则，将塔座A顶上的n-1个圆盘移动到塔座B上，用塔座C作为辅助塔座；然后移文本文1.熟悉字符串1. 根据课堂介绍设计实现KMP算法 件检索实验 的操作 2.学会运用字符串的操作进行文本检索和查询。 的算法程序 2. 试设计一个简单的文本编辑器，使之具有对字符串的输入、输出、插入、删除、查找和替换等功能 3. 设计实现一个通用的判定回文个数问题稀疏矩1．熟悉稀疏矩1. 设计实现两个普通矩阵相乘的算法 阵和广义表实验 2．掌握稀疏矩3. 设计实现两个N次一元多项式相加的算阵和广义表结构上的各种操作 3．学会运用稀疏矩阵和广义表结构求解问题 阵和广义表2. 实现用三元组表示法实现稀疏矩阵相加结构 及转置算法 法程序 树结构1.熟悉树和二1. 设计一个程序，根据二叉树的先根序列和实验 叉树结构 2.掌握树和二对称序序列创建一棵用左右指针表示的二叉树 叉树结构上2. 根据哈夫曼算法创建哈夫曼树，并求树中的各种操作 每个外部结点的编码 3.学会运用树3. 设计一个程序，把中缀表达式转换成一棵和二叉树结构求解问题 二叉树，然后通过后序遍历计算表达式的值 4. 设计实现一个完成对BST树进行插入、删除、查找操作的算法，并希望有部分同学能进一步把该算法改写为针对AVL树的相关算法 图结构1.熟悉图结构 采用两种不同的图的表示方法，实现拓扑排实验 2.掌握图结构对于下图所示的AOE网，求出各活动的可能上的各种操作 的最早开始时间和最晚开始时间。输出整个工程的最短完成时间是多少 哪些活动是关3.学会运用图键活动 说明哪项活动提高速度后能导致整结构求解问个工程提前完成分析不同存储结构对于算法序和关键路径的求解过程。使用实现的算法题 效率的影响。 散列表1.熟悉散列表试根据全年级学生的姓名，构造一个散列表，实验 结构 2.掌握散列函数的生成方法,掌握常规冲突处理办法 3. 学会运用散列结构求解问题 选择适当的散列函数和解决碰撞方法，设计并实现插入、删除和查找算法，统计碰撞发生的次数。（用拉链法解决碰撞时负载因子取2，用开地址法时取1/2） 航班信1.掌握查找与对于直接插入排序、直接选择排序、起泡排息查询与检索排序的各种序、Shell排序、快速排序和堆排序等六种算法 算法进行上机实习。 实验设2.学会选用和要求： 计 设计实际问1. 被排序的对象由计算机随机生成，长度分题所需的查别取20，100，500三种。 找与排序算法 2. 算法中增加比较次数和移动次数的统计功能。 3. 对实习的结果做比较分析。 4. 设计实现一个航班信息查询与检索系统 课程实验参考教材： 魏开平等编著. 数据结构辅导与实验. 清华大学出版社，2006年第1版 瞿有甜，《数据结构与算法分析》实验指导书， 实验1 猴子选大王 任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 输入数据：输入m,n m,n 为整数，n 实验内容： 源程序： #include <> #include <> typedef struct node{ int data; struct node * next; }ListNode; typedef ListNode * LinkList; /*建立单循环链表函数*/ LinkList InitRing(int n,LinkList R) { ListNode *p,*q; int i; R=q=(ListNode *)malloc(sizeof(ListNode)); for(i=1;i p->data=n; p->next=R; R=p; return R; } /*选择函数*/ LinkList DeleteDeath(int n,int k,LinkList R) { int i,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\ if(i%10==0)printf(\"\\n\"); free(q); } R=p; return R; } /*输出函数*/ void OutRing(int n,LinkList R) { int i; ListNode *p; p=R; for(i=1;i<=n/2;i++,p=p->next) { printf(\"%4d\ if(i%10==0) printf(\"\\n\"); } printf(\"\\n\"); printf(\"猴大王的号码：\\n\"); printf(\"4%d\ } /*主函数*/ void main() { LinkList R; int n,k; LinkList InitRing(int n,LinkList R ); printf(\"猴子的总数N:\"); scanf(\"%d\ printf(\"报到要被淘汰数字 K:\"); scanf(\"%d\ printf(\"被淘汰的猴子：\\n\"); R=InitRing(n,R); R=DeleteDeath(n,k,R); printf(\"\\n\"); OutRing(n,R); } 实验结果：实验2 订票系统 任务：通过此系统可以实现如下功能： 录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况； 订票：可以订票（订票情况可以存在一个数据文件中，结构自己设定），如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息：当航班信息改变可以修改航班数据文件 要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 实验内容： 源程序： #include <> #include <> #include<> #include <> #include <> #include <> #include <> #define TRUE 1 #define FALSE 0 typedef int BOOL; #define NEW(type, size) size) typedef struct _date { /* int m_year; */ * (type*)malloc(sizeof(type) 日期 int m_month; int m_day; } DATE; typedef struct _time { /* 时间 */ int m_hour; int m_min; } TIME; typedef struct _flight { /* 航班数据 */ int m_fltno; /* 航班号，若此成员为-1，则表示此航班未使用 */ char m_szFrom[30]; /* 起飞港 */ char m_szPass[30]; /* 途经港 */ char m_szTo[30]; /* 到达港 */ TIME m_start; /* 起飞时间 */ TIME m_arrive; /* 到达时间 */ TIME m_fly; /* 飞行固定时间 */ int m_people; /* 乘客限额 */ } FLIGHT, *PFLIGHT; typedef struct _passengernode { /* 乘客数据 */ char m_szName[20]; /* 姓名 */ char m_szCorp[30]; /* 单位 */ char m_szNumber[19]; /* 身份证号，考虑到字母的情况，故使用字符串 */ DATE m_Date; /* 订票日期 */ int m_fltno; /* 航班号 */ int m_seatno; /* 座位号 */ } PASSENGER, *PPASSENGER; typedef struct _psgnode { /* 乘客结点 */ PASSENGER m_psg; struct _psgnode *next; } NODE, *PNODE; /* 清空键盘缓冲区 */ void ClearBuffer(void); /* 读取航班数据 */ void ReadFlight(FLIGHT fltlist[]); /* 读取乘客数据 */ void ReadPassenger(PNODE psglist); /* 添加航班 */ BOOL AddFlight(FLIGHT fltlist[], PFLIGHT fltdata); /* 删除航班 */ void DelFlight(FLIGHT fltlist[], int index); /* 添加乘客 */ void AddPassenger(PNODE psglist, PPASSENGER psgdata); /* 删除乘客 */ BOOL DelPassenger(PNODE psglist, int index); /* 清空乘客链表 */ void ClearPsgList(PNODE psglist); /* 取得乘客总数 */ unsigned int GetPsgCount(PNODE psglist); BOOL datecmp(DATE* date1, DATE* date2); void Book(FLIGHT fltlist[], PNODE psglist); void query(FLIGHT fltlist[], PNODE psglist); void fltnumber(FLIGHT fltlist[]); void psgname (PNODE psglist); void fromto (FLIGHT fltlist[]); void fltdat(FLIGHT fltlist[], PNODE psglist); /* 保存航班数据 */ void SaveFlight(FLIGHT fltlist[]); /* 保存乘客数据 */ void SavePassenger(PNODE psglist); /* 退出 */ void Quit(FLIGHT fltlist[], PNODE psglist); BOOL datecmp(DATE* date1, DATE* date2) { return (date1->m_year == date1->m_month == date2->m_month date2->m_year && && date1->m_day == date2->m_day); } BOOL timecmp(TIME* time1, TIME* time2) { return (time1->m_hour == time2->m_hour && time1->m_min == time2->m_min); } void ClearBuffer(void) { getchar(); } void ReadFlight(FLIGHT fltlist[]) { FILE *fp; if ((fp = fopen(\"\ fread(fltlist, sizeof(FLIGHT), 40, fp); else { int i; for (i = 0; i < 40; i++) fltlist[i].m_fltno = -1; } fclose(fp); } void ReadPassenger(PNODE psglist) { FILE *fp; if ((fp = fopen(\"\ psglist->next = NULL; else { int i, n; fread(&n, sizeof(int), 1, fp); for (i = 0; i < n; i++) { PASSENGER psg; fread(&psg, sizeof(PASSENGER), 1, fp); AddPassenger(psglist, &psg); } } } BOOL AddFlight(FLIGHT fltlist[], PFLIGHT fltdata) { int i; BOOL bResult = FALSE; for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno == -1) { memcpy(&fltlist[i], fltdata, sizeof(FLIGHT)); bResult = TRUE; break; } } return bResult; } void DelFlight(FLIGHT fltlist[], int index) { fltlist[index].m_fltno = -1; } void AddPassenger(PNODE psglist, PPASSENGER psgdata) { PNODE p, 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; } BOOL DelPassenger(PNODE psglist, int index) { int i = 0; PNODE p, 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); return TRUE; } else return FALSE; } void ClearPsgList(PNODE psglist) { PNODE p = psglist->next, q; while (p != NULL && p->next != NULL) { q = p; p = p->next; free(q); } } unsigned int GetPsgCount(PNODE psglist) { PNODE p; unsigned int s = 0; for (p = psglist->next; p != NULL; p = p->next) s++; return s; } void Book(FLIGHT fltlist[], PNODE psglist) { char c = 'y'; BOOL b; while (c == 'y' || c == 'Y') { int i; PASSENGER psg; printf(\"请输入航班号：\"); scanf(\"%d\ while >= 10000 || < 0) { printf(\"请重新输入：\"); scanf(\"%d\ } for(i = 0; i < 40; i++) { if(fltlist[i].m_fltno == { PNODE p; BOOL *q; int j; printf(\"请输入订票日期：(yyyy,mm,dd)\"); scanf(\"%d,%d,%d\ & q fltlist[i].m_people); = NEW(int, for (j = 0; j < fltlist[i].m_people; j++) q[j] = FALSE; for (p = psglist->next; p != NULL; p = p->next) { if(datecmp(&p->, & && == p-> q[p-> - 1] = TRUE; } printf(\"以下座位尚未有人订：\"); for (j=0; j < fltlist[i].m_people; j++) { if (!q[j]) printf(\"%d \ } printf(\"\\n请输入订票座位号：\"); scanf(\"%d\ b = FALSE; do { int k; if > 0 && <= fltlist[i].m_people + 1) { if (!q[ - 1]) { b = TRUE; break; } else printf(\"这个座位有人了！\"); } else printf(\"数据非法！\"); scanf(\"%d\ } while (!b); printf(\"请输入乘客姓名：\") ; scanf(\"%s\ printf(\"请输入乘客单位：\"); scanf(\"%s\ printf(\"请输入乘客身份证号： scanf(\"%s\ \"); AddPassenger(psglist, &psg); printf(\"您的订票已成功。\"); free(q); } } c = getchar(); } } void query(FLIGHT fltlist[], PNODE psglist) { for (;;) { char c; 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; } } void fltnumber(FLIGHT fltlist[]) { char c = 'y'; while (c == 'y' || c == 'Y') { BOOL b = FALSE; int fltno, i; printf(\"可以查询的航班号：\"); for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno != -1) { b = TRUE; printf(\"%d \ } } if (!b) { printf(\"无\\n按任意键返回。\"); getch(); return; } printf(\"\\n请输入要查询的航班号：\"); scanf(\"%d\ for(i = 0; i < 40; i++) { if (fltlist[i].m_fltno == fltno) { printf(\"%s--%s--%s\\n\fltlist[i].m_szPass, fltlist[i].m_szTo); printf(\"起飞时间：%2d:%02d 到达时间：%2d:%02d 飞行固定时间：%2d:%02d\\n\ fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i].; printf(\"乘客限额：%d\\n\ break; } } printf(\"继续查询吗(y/n)\"); ClearBuffer(); fltlist[i].m_szFrom, c = getchar(); } } void psgname(PNODE psglist) { char c = 'y'; while (c == 'y' || c == 'Y') { char name[20]; PNODE p; BOOL b = FALSE; printf(\"请输入乘客姓名：\"); scanf(\"%s\ for (p = psglist->next; p != NULL; p = p->next) { if(strcmp(p->, name) == 0) { b = TRUE; printf(\"姓名：%s 单位：%s 身份证号：%s\\n\ p->, p->; printf(\"订票日期：%d-%d-%d \ p-> printf(\"航班号：%d 座位号：%d\ p-> } } if (!b) { printf(\"查无此人，按任意键退出\"); getch(); return; } printf(\"是否继续查询(y/n)\"); ClearBuffer(); c = getchar(); } } void fromto (FLIGHT fltlist[]) { char c = 'y'; while (c == 'y' || c == 'Y') { BOOL b = FALSE; char from[30], to[30]; int i; printf(\"请输入起飞港：\"); scanf(\"%s\ printf(\"请输入到达港：\"); scanf(\"%s\ 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\ass,fltlist[i].m_szTo); printf(\"起飞时间：%2d:%02d 到达时间：%2d:%02d 飞行固定时间：%2d:%02d\\n[i].,fltlist[i].,fltlist[i].; printf(\"乘客限额：%d\ } else printf(\"无此飞机\"); getch(); printf(\"是否继续查询\"); ClearBuffer(); c = getchar(); } } void fltdat(FLIGHT fltlist[], PNODE psglist) { int people[40], i; DATE date; PNODE p; for (i = 0; i < 40; i++) people[i] = 0; printf(\"请输入您要查询的日期(yyyy,mm,dd)：\"); scanf(\"%d,%d,%d\ for (p = psglist->next; p != NULL; p=p->next) { if (datecmp(&date, &p->) { for(i=0;i<40;i++) { if(fltlist[i].m_fltno==p-> people[i]++; } } } for (i = 0; i < 40; i++) { if (people[i] > 0) { printf(\"%d %s--%s--%s 人fltlist[i].m_fltno, fltlist[i].m_szFrom, fltlist[i].m_szPass, people[i]); } } getch(); } void Add(FLIGHT fltlist[]) { 数 ： %d\ fltlist[i].m_szTo, char c = 'y'; while (c == 'y' || c == 'Y') { FLIGHT flt; BOOL b; printf(\"请输入航班号(1 - 10000)：\"); scanf(\"%d\ printf(\"请输入起飞港：\"); scanf(\"%s\ printf(\"请输入途经港：\"); scanf(\"%s\ printf(\"请输入到达港：\"); scanf(\"%s\ printf(\"请输入起飞时间(hh:mm)：\"); scanf(\"%d:%d\& & printf(\"请输入到达时间(hh:mm)：\"); scanf(\"%d:%d\请输入飞行固定时间(hh:mm)：\"); scanf(\"%d:%d\请输入乘客限额：\"); scanf(\"%d\ ClearBuffer(); if (AddFlight(fltlist, &flt)) printf(\"添加成功，\"); else printf(\"添加失败，\"); printf(\"继续添加航班吗(Y/N)\"); c = getchar(); } } void Del(FLIGHT fltlist[]) { BOOL b = FALSE; int i, fltno; char c = 'y'; while (c == 'y' || c == 'Y') { printf(\"可以取消的航班号：\"); for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno != -1) { b = TRUE; printf(\"%d \ } } if (!b) { printf(\"无\\n按任意键返回。\"); getch(); return; } printf(\"\\n请输入要取消的航班号：\"); scanf(\"%d\ for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno == fltno) { DelFlight(fltlist, i); break; } } printf(\"继续删除吗(y/n)\"); ClearBuffer(); c = getchar(); } } void Query(FLIGHT fltlist[]) { char c = 'y'; while (c == 'y' || c == 'Y') { BOOL b = FALSE; int i, fltno; printf(\"可以查询的航班号：\"); for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno != -1) { b = TRUE; printf(\"%d \ } } if (!b) { printf(\"无\\n按任意键返回。\"); getch(); return; } printf(\"\\n请输入要查询的航班号：\"); scanf(\"%d\ for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno == fltno) { printf(\"%s--%s--%s fltlist[i].m_szFrom, 乘 客 限 额 ： %d\\n\ fltlist[i].m_szPass, fltlist[i].m_people); fltlist[i].m_szTo, printf(\"起飞时间：%2d:%02d 到达时间：%2d:%02d 飞行固定时间：%2d:%02d\\n\ fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i]., fltlist[i].; break; } } printf(\"继续查询吗(y/n)\"); ClearBuffer(); c = getchar(); } } void OneDay(FLIGHT fltlist[], PNODE psglist) { char c = 'y'; while (c == 'y' || c == 'Y') { DATE date; int people[40], i; PNODE p; for (i = 0; i < 40; i++) people[i] = 0; printf(\"请输入您要管理的日期(yyyy,mm,dd)：\"); scanf(\"%d,%d,%d\ for (p = psglist->next; p != NULL; p = p->next) { if (datecmp(&p->, &date)) { for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno == p-> 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_szTo, people[i]); } } printf(\"继续管理吗(y/n)\"); ClearBuffer(); c = getchar(); } } void MultiDay(FLIGHT fltlist[], PNODE psglist) { char c = 'y'; while (c == 'y' || c == 'Y') { DATE date[7]; int n, i, j; fltlist[i].m_szPass, int people[40][7]; PNODE p; printf(\"请输入要查询的天数(1-7)：\"); do { scanf(\"%d\ if (n > 7 || n < 1) printf(\"输入非法，请重新输入：\"); } while (n > 7 || n < 1); for (i = 0; i < n; i++) { printf(\"请输入第%d个日期(yyyy,mm,dd)：\ scanf(\"%d,%d,%d\ &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++) { &date[i].m_year, if (datecmp(&date[j], &p->) { for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno == p-> people[i][j]++; } } } } for (i = 0; i < 40; i++) { if (fltlist[i].m_fltno != -1) { printf(\"%d %s--%s--%s fltlist[i].m_szFrom, \ fltlist[i].m_fltno, fltlist[i].m_szPass, fltlist[i].m_szTo); for (j = 0; j < n; j++) printf(\"%d \ printf(\"\\n\"); } } printf(\"继续查询吗(y/n)\"); ClearBuffer(); c = getchar(); } } void Manage(FLIGHT fltlist[], PNODE psglist) { for (;;) { char c; 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; } } void SaveFlight(FLIGHT fltlist[]) { FILE *fp; if ((fp = fopen(\"\ { printf(\"不能打开文件，航班数据无法保存。\\n\"); fclose(fp); return; } fwrite(&fltlist[0], sizeof(FLIGHT), 40, fp); fclose(fp); printf(\"航班数据已保存至文件。\\n\"); } void SavePassenger(PNODE psglist) { FILE *fp; PNODE p; int n = GetPsgCount(psglist); unlink(\"\"); if (n == 0) return; if ((fp = fopen(\"\ { printf(\"不能打开文件，乘客数据无法保存。\\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(\"乘客数据已保存至文件。\\n\"); } void Quit(FLIGHT fltlist[], PNODE psglist) { SaveFlight(fltlist); SavePassenger(psglist); } void main(void) { FLIGHT fltlist[40]; NODE psglist; ReadFlight(fltlist); ReadPassenger(&psglist); for (;;) { char c; 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，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么 输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 输出形式：建立一个输出函数，将正确的输出序列 实验内容: 实验源程序: #include using namespace std; #define N 7 typedef struct node { int data; int sercet; struct node *next; }ListNode; typedef ListNode *LinkList; .再依次5的倍数的 牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些 实验内容: 实验源程序: #include void Pcout1(int i,int j) { switch(i) { case 0:cout<<\" 3 \"; break; case 1:cout<<\" 4 \"; break; case 2:cout<<\" 5 \"; break; case 3:cout<<\" 6 \"; break; case 4:cout<<\" 7 \"; break; case 5:cout<<\" 8 \"; break; case 6:cout<<\" 9 \"; break; case 7:cout<<\" 10 \"; break; case 8:cout<<\" J \"; break; case 9:cout<<\" Q \"; break; case 10:cout<<\" K \"; break; case 11:cout<<\" A \"; break; case 12:cout<<\" 2 \"; break; } switch(j) { case 0:cout<<\"草花\"< { int t=1,x=2; int i,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这时正面向上的牌有：for(i=0;i<13;i++) { for(j=0;j<4;j++) if(a[i][j]==1) Pcout1(i,j); } \"< 要求：可以建立函数输入二叉树，并输出其赫夫曼树 在上交资料中请写明：存储结构、 基本算法（可以使用程序流程图） 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 实验内容： 源程序： include<> #include <> #include <> #define m 100 struct ptree /* define the type of banary tree*/ { int w; struct ptree * lchild; struct ptree * rchild; }; struct pforest /*define the type of chain belt*/ { struct pforest *link; struct ptree *root; }; int WTL=0; void main() { struct ptree *hafm(int w[m],int n ); void travel(struct ptree *head,int n ); struct ptree *head; int n,i,w[m]; printf(\"please input the sum of node\\n\"); scanf(\"%d\ printf(\"please input weight of every node\\n\"); for(i=1;i<=n;i++) scanf(\"%d\ head=hafm(w,n); travel(head,0); printf(\"The length of the best path is WTL=%d\ } void travel(struct ptree *head,int n) { struct ptree *p; p=head; if (p!=NULL) { if((p->lchild)==NULL&&(p->rchild)==NULL) { printf(\" %d\ printf(\" the hops of the node is: %d\\n\ WTL=WTL+n*(p->w); } travel(p->lchild,n+1); travel(p->rchild,n+1); } } struct ptree *hafm(int w[m],int n) { struct pforest *inforest(struct pforest *f, struct ptree *t ); struct pforest *p1,*p2,*f; struct ptree *ti,*t,*t1,*t2; int i; f=(struct pforest*)malloc(sizeof(struct pforest)); f->link=NULL; for (i=1;i<=n;i++) /*produce n trees that have only rootnode*/ { ti=(struct ptree *)malloc(sizeof(struct ptree)); ti->w=w[i]; ti->lchild=NULL; ti->rchild=NULL; f=inforest (f,ti); } while(((f->link)->link)!=NULL) /* at least have two binary trees*/ { p1=f->link; p2=p1->link; f->link=p2->link; /*take out frontal two trees*/ t1=p1->root; t2=p2->root; free(p1); free(p2); t=(struct ptree *)malloc (sizeof(struct ptree)); t->w=t1->w+t2->w; /*weight be added */ t->lchild=t1; t->rchild=t2; /*produce the new binary tree */ f=inforest(f,t); } p1=f->link; t=p1->root; return(t); } struct pforest * inforest(struct pforest *f, struct ptree *t) { struct pforest *p, *q, *r; struct ptree *ti; r=(struct pforest *) malloc(sizeof(struct pforest)); r->root=t; q=f; p=f->link; while (p!=NULL) /*look for the position to be inserted*/ { ti=p->root; if( t->w>ti->w ) { q=p; p=p->link; } else p=NULL; /*force exit the cycle*/ } r->link=q->link; q->link=r; return (f); } 实验结果： 1． 2． 实验6 二叉树的建立与遍厉 任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； 实验内容: 实验源程序: #include<> struct TREE #include<> { int data; TREE *L,*R; }; void NewNode(int value); void Insert(TREE *&Root,TREE *Node); void preorder(TREE *Node); void inorder(TREE *Node); void postorder(TREE *Node); void floororder(TREE *Node); TREE *pRoot; x0=strlen(p[i].Name); } else { ame[0]!='#') < 择 的 \"<<\"(1---\"< 项 ： p[4].Name=\"学校查询\"; p[5].Name=\"项目查询\"; p[6].Name=\"返回 \"; SCHOOLSTRUCT *h,*head,*SchoolTable;ame,Student_name); tem=XM_ID ;ount=xm_T[XM_ID].count+1; ange=range;core=score;ex=sex; core; ex==0)womenscore=womenscore+p->students[i].score;core;tem; if(xm_T[item_i].count>=5){ ange==1)jf=jf+7; else if(p->students[i].range==2)jf=jf+5; else if(p->students[i].range==3)jf=jf+3; else if(p->students[i].range==4)jf=jf+2; else if(p->students[i].range==5)jf=jf+1; } if(xm_T[item_i].count<5){ ange==1)jf=jf+5; else if(p->students[i].range==2)jf=jf+3; else if(p->students[i].range==3)jf=jf+2; } ange:\"< cout<<\"学校：\"< void Find_School_Xm(SCHOOLSTRUCT * &head,int School_ID,int XM_ID){tem==XM_ID){ cout<<\"查询结果如下：\"< else { cout<<\"性别： 男\\n\"; } cout<<\"项目编号：\"< if(h->students[i].sex==0)xm_item=xm_item+20; ame<<\" \"; cout<<\"得分\"< cout<<\"\\n--------------------------------------\\n\"; h=h->next; tem<<\" 名称 \"< cout<<\"编号 \"< void _SetArgs(){ tem=i; ount=0; ame; tem=i; ame; //项目名称 } } void AddStudent(SCHOOLSTRUCT *&SchoolTable){ //添加学生数据 int ANW; Loop_4: Add_Student_link(SchoolTable); //添加学生数据 cout<<\"\\n是否继续添加学生数据[0=No 1=Yes]\\n\"; cin>>ANW; if(ANW==1)goto Loop_4; } 实验结果: 因篇幅问题不能全部显示，请点此查看更多更全内容