《面向对象程序设计(C)课程设计任务书及题目.doc》由会员分享，可在线阅读，更多相关《面向对象程序设计(C)课程设计任务书及题目.doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、上海电机学院课程设计任务书课程名称面向对象程序设计课程设计课程代码P1设计题目课程设计选题共24个（见附件）设计时间2014年6月16日2014年6月20日院（系）电子信息学院专业计算机科学与技术班级BX1203、BX1204一、课程设计任务1. 了解并掌握中小型综合应用程序的一般设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；5. 课题的代码要求达到一定工作量
2、，并具有一定的深度和难度；6. 根据课题程序的分析和设计过程，撰写课程设计报告。二、对课程设计成果的要求（包括课程设计说明书、图纸、图表、实物等软硬件要求）课程设计结束应提交程序源代码、课程设计报告的电子稿和打印稿，以作为整个课程设计评分的书面依据和存档材料。课程设计报告以规定的格式书写、打印并装订，排版及图、表要清楚、工整。课程设计报告的内容如下： 1封面：题目、班级、学号、姓名、指导教师和完成日期。2正文包括以下内容：（1）需求分析：以无歧义的陈述说明课题的目的及要求，重点描述清楚程序要做什么。（2）概要设计：根据程序需要完成的功能分析主程序的流程，并划分出各个功能模块、完成各程序模块之间
3、的层次(调用)关系设计。（3）详细设计：实现概要设计中划分出的各个模块。撰写报告时，对每个模块先用文字（可结合流程图）描述其实现思路，重点描述清楚程序要怎么做，再贴出关键部分的实现代码。（4）测试：列出测试结果，包括输入和输出。测试数据应该完整和严格。（5）总结和体会：程序编写和调试过程中遇到了哪些问题，是如何解决的，以及对设计与实现过程的回顾和分析；经验和体会等。（6）参考文献：列出参考的网址、期刊和书籍等相关资料。（7）考核：根据课程的出勤情况、课题的实现及答辩质量、课设报告的严谨和规范性等方面进行考核，注重过程考核和综合能力的测评，以确保教学质量。成绩 =平时成绩占（含出勤）20%课程设
4、计报告成绩占40课程设计作品成绩占40三、课程设计工作进度计划： 1布置任务与要求0.52整体设计和详细设计13编代码24调试和测试0.55设计论文书写0.56演示软件和答辩 0.5共计 5 四、主要参考资料 1 沈学东等.C+面向对象程序设计实用教程M上海交通大学出版社，20122 谭浩强等. C+程序设计M北京：清华大学出版社，2011指导教师（签名）：王中华 系主任（签名）：2014年5月20日 年 月 日附：课程设计题目1. 有理数运算问题描述有理数是一个可以化为一个分数的数，例如2/3，533/920，-12/49都是有理数，而就为无理数。在C+中，并没有预先定义有理数，需要时可以定
5、义一个有理数类，将有理数的分子和分母分别存放在两个整型变量中。对有理数的各种操作都可以用重载运算符来实现。基本要求定义并实现一个有理数类，通过重载运算符+、-、*、/对有理数进行算术运算，通过重载运算符=实现判定两个有理数是否相等。写一个优化函数，它的作用是使有理数约去公分母，也即是使保存的有理数分子和分母之间没有公约数（除去1以外）。此外，还要定义一个将有理数转换为实数的函数，再加上构造函数和有理数输出函数。测试数据在应用程序中，创建若干有理数对象，通过带参数的构造函数使得各有理数对象值各不相同，然后分别进行各类运算，输出运算结果，检验其正确性。实现提示设有两个有理数a/b和c/d，则有：（
6、1） 有理数相加 分子=a*d+b*c；分母=b*d（2） 有理数相减 分子=a*d-b*c；分母=b*d（3） 有理数相乘 分子=a*c； 分母=b*d（4） 有理数相除 分子=a*d； 分母=b*c优化函数在创建有理数对象时应执行，在执行其它各种运算之后也需执行它，这样可保证所存储的有理数随时都是最优的。对于判断两个有理数是否相等，由于在对有理数进行各种运算后都对其进行优化，所以判定两个有理数是否相等只需判定它们两个的分子和分母分别相等即可。选做内容重载插入（）运算符，使得对有理数可以直接输入输出。设有理数输入格式为：整数1 整数2 /整数1为分子，整数2为分母有理数输出格式为：分子/分母
7、2. 通讯录管理 问题描述编写一个简单的通讯录管理程序。通讯录记录有姓名，地址(省、市(县)、街道)，电话号码，邮政编码等四项。基本要求程序应提供的基本管理功能有：1） 添加：即增加一个人的记录到通信录中2） 显示：即在屏幕上显示所有通信录中的人员信息，应能分屏显示。3） 存储：即将通讯录信息保存在一个文件中。4） 装入：即将文件中的信息读入程序。5） 查询：可根据姓名查找某人的相关信息，若找到显示其姓名、地址、电话号码和邮政编码。6） 修改：可修改一个人的除姓名外其它信息。测试数据程序应输入不少于10个人员的通讯录信息，应考虑到人员可以同名的情况。实现提示程序可用一个单向链表来管理人员信息，
8、每个人员的姓名，地址，电话号码和邮政编码用一个类Cperson来实现，作为链表的值指针指向这些Cperson类对象，通过链表的遍历可以操作这些数据。选做内容为了加快数据定位查找的速度，采用常用优先的方法对链表的各个节点进行排序，即一旦操作了一个人员的数据，他的数据就将被调用到链表的链首。这样经过有限次操作，经常查阅的人员的信息就将排在链表的前端。虽然不能说链首的节点一定是最常用的，但常用的节点一定会排在较靠前的部分，链表查找时所要走的平均距离一定较短。3. 商品销售统计问题描述编写商品销售统计程序，商品的信息有：商品的名称，计量单位（重量或件），单价。所有商品的信息事先已存入计算机，屏幕上显示
9、所有商品的名称，选择商品名，输入商品计量单位(如重量，件数等)，根据单价算出总价。客户一次购物可能购买多种商品，程序应计算出客户应付的钱款数。基本要求程序分为两个部分：第一部分用于输入商品的信息并允许修改和删除；第二部分实现销售统计。程序运行时由用户选择进入哪一部分功能，并能在运行时在两部分之间切换。第二部分运行时，首先显示所有商品名称及代码（商品数目较多时，应考虑分屏显示），用户输入商品代码及商品重量或件数，用户一次操作可输入若干商品的购买信息，然后输入一个特殊的代码（如-1）表示本次购物结束。此时。程序计算出应付钱款数并显示。测试数据程序应输入不少于10种商品的信息，并进行模拟运行。实现提
10、示本程序的商品信息管理可采用与课程设计题目二类似的数据结构，既定义一个商品类，每种商品作为商品类的实例（对象）存储在链表节点中。选做内容程序在营业结束时统计每种商品的销售量，销售金额及总营业额。因此第二部分应有营业结束的选择，当用户选择此项时屏幕上显示当天营业的每种商品的销售量，销售金额及总营业额。注意，商品类的数据成员应增加有商品的销售量和销售金额。总营业额是所有商品的营业额之和，可用静态数据成员实现。或可由原商品类派生出一个特殊的类，增加上面的数据成员及相应的成员函数。4. 研究生初试录取问题描述研究生考试课程为4门，其中数学、外语、政治为统一命题，而专业基础课则根据不同的专业由招生学校自
11、行命题。国家对初试录取分数有总分要求（如某一年要求4门课总分应达到310分），另外还有对每门课的最低分数要求（如总分为100的试卷最低应达到40分，总分为150的试卷最低应达到65分）。编程统计初试合格的人数，并按总分由高到低的顺序输出合格考生的信息。基本要求程序运行时首先要求输入：考生姓名，准考证号，报考专业，是否应届生，4门课程（政治、数学、外语、专业基础课）成绩。这些原始数据应保存到一个文件中。然后输入：录取的总分要求，各课程的最低分数要求。输出要求：过线考生的姓名，准考证号，报考专业，是否应届生，4门课程（政治、数学、外语、专业基础课）成绩及总分，这些信息应存放到另一个文件中。测试数据
12、程序应输入不少于10名考生的信息，其中应届生和历届生分别有若干名，并且都有合格和不合格的情况。实现提示可定义一个考生类存放有关信息和实现相应的操作。分数线数据（总分要求和各门课程的要求）可定义另外的类来存放，但应能被考生类及其派生类直接访问。选做内容初试合格的考生应经过复试才能决定是否录取，复试成绩合格（大于给定分值）可以录取，否则被淘汰。而录取的顺序假设是按照专业基础课和复试成绩的平均值来确定的（因为这涉及到是计划内还是委培问题）。因此，应首先输入初试合格考生的复试成绩及复试的合格线分数，然后按上面要求排序输出并标明被淘汰的学生。5. 足球联赛积分问题描述足球联赛采用主客场双循环赛制，胜一场
13、得3分，平局各得1分，负一场得0分，联赛排名以积分多者在前，当两队（或多队）积分相同时，则净胜球（即进球数与失球数之差）多者在前，若净胜球相同，则进球数多者在前，若仍相同，则抽签或踢附加赛决定名次（这在联赛结束后进行，联赛未结束则两队名次并列，本程序不做这方面要求）。试编程序统计最近一轮比赛后，各队积分及排名。基本要求设积分表结构如下：队名（不超过15个字符），已比赛的场数，赢的场数，平的场数，负的场数，进球数，失球数，积分。积分表放在正文文件中。最近一轮的结果从键盘输入，其形式为：主队名（可用代码），客队名（可用代码），主队得分（即进球数），客队得分（即进球数）。程序应根据此轮结果修改各队的
14、积分和名次，所得的最新记分表仍在原积分文件中并同时在屏幕上显示。测试数据可选择我国当年的甲A或甲B联赛的数据输入，并检查与报章公布的数据是否一致。实现提示定义一个球队类，每个球队是均是此类的对象。由于联赛中参赛的队伍数是固定的，因此可用对象数组来实现（当然也可以用链表结构）。每输入两个队的比赛成绩，则相应的队的有关数据（比赛场数，赢的场数，平的场数，负的场数，进球数，失球数，积分等）即可进行修改，比赛成绩录入完成，调用联赛排序方法（对象数组作为参数）排出名次并输出。选做内容篮球联赛（如NBA）往往采用胜率来决定名次，胜率就是取胜的场数比赛场数之比。若胜率相同，再由净胜球及进球数来决定名次，通过
15、继承性完成上述要求。6. 银行账户管理程序问题描述设计一个银行账户管理程序，账户的信息有账号（唯一）、姓名、余额、身份证号码、单位、电话号码、地址等，允许用户进行如下操作：开户、销户、存款、取款、转账、查询，一个用户可以有多个户头，账户的数值没有上限。基本要求程序运行时，可以由用户选择进行何种操作，开户操作要求输入用户信息后自动获取账号，用户销户后账号被回收，并且该账号可以继续分配给其它账户，不允许用户透支，根据姓名或账号可以进行用户的信息查询，所有的账户信息应存放到一个文件中，可以随时的访问和更新。测试数据程序应输入不少于10人的账户信息，应考虑到人员同名的情况。实现提示可定义一个账户类存放
16、账户信息以及执行相应的操作，可以用一个链表类来管理账户。选做内容在上述程序的基础上，添加联名账户（一个联名账户有两个拥有者）的管理 。7. 模拟计算器程序问题描述设计一个程序来模拟一个简单的手持计算器。程序支持算术运算+、-、*、/、=、以及C（清除）、A（全清除）操作。基本要求程序运行时，显示一个窗口，等待用户输入，用户可以从键盘输入要计算的表达式，输入的表达式显示在窗口中，用户键入= 符号后，窗口显示出结果。测试数据程序输入不少于5种不同的表达式进行测试。实现提示可定义一个计算器类，该类包括两个组件对象，一个计算引擎和一个用户接口，用户接口对象处理接受的键盘输入信息，并显示答案，计算引擎对
17、象对给出的数据执行相应操作，并存储操作的结果。选做内容如果用户输入的表达式不合法，可以判别出来并给出相应的错误提示。8. 设计一个排课程序问题描述每位教师都有教学工作量，教师对他所希望讲授的课程表达为一个期望值，1，2，n，其中1位最高的期望值。课程也有优先级，1，2，n，用来决定将课程分给教师的顺序，其中1时最高的优先级。设计一个程序针对某些课程给某些教师进行排课。基本要求程序运行时，用户输入教师信息（姓名、教师号、工作量）、课程信息（课程名、课程号、周学时、总学时、优先级）、教师对所希望讲授课程的期望值以及教学工作量等相关信息，所有信息应保存在文件中，程序根据课程的优先级以及教师对课程的期
18、望值进行排课。为了公平起见，程序随机分配课程，如果10门课程都有优先级1，程序以随机的顺序将这些课程分给教师，如果10位教师对某门课程的期望值为1，程序应从10位教师中随机选择一个。最后输出排课情况，即某位老师上某门课程，以及某位老师的工作量。测试数据程序应能实现对不少于20门课和10个教师的排课，并且使每个教师的满意度达到最大，不存在工作量不满的教师以及未分配的课等情况。实现提示可定义一个教师类存放教师信息，所有教师的信息可以用链表存储；定义一个课程类存放课程信息，所有课程的信息可以用链表存储；定义一个排课类进行排课，排课类可以访问课程和教师信息。选做内容对两个同类班级安排一学期（20周）的
19、课程，程序应能处理某些限制，如一个老师不能同时给两个班上课。9. 设计一个Database类问题描述设计一个Database类。Database类是一个表的集合，而表又由行和列组成。例如，下面的雇员信息表包含三个记录，每个记录有四个字段（ Employee、Name、Department和Boss）。雇员姓名部门部门经理111-11-1234CruzACCWarder213-44-5649JohnstonMISMichaels321-88-7895TomFINBearskin基本要求能够完成对数据库的基本操作；包括创建数据库，实现对数据库里面的表的添加，删除；以及能够完成对表结构的修改（如添加
20、或删除字段），以及对表中的记录进行添加和删除；能够完成对使用适当的查询语言从一个或多个表中查找相关信息。测试数据可以选取高校人员（教师、学生、职工等）数据库作为测试数据实现提示Database 类的公有接口包含如下数据成员： 创建一个表。 通过增加或删除字段修改表结构。 删除一个表。 在表中增加一个记录。 从表中删除记录。 用适当的查询语言从一个或多个表中查找信息。选做内容高校人员信息通常保存在文件里面，可以从文件里面读取人员信息；然后完成上面操作。10. 电煤气管理系统问题描述设计一个水电管理信息系统，能够对高校的水电费用进行管理,包括了登记费用，查询费用，以及住户信息管理等。在设计时要考虑
21、到学生和教工在用水电时的不同，学生可以免费使用一定额度的水电，超过这个额度的随便以后必须自费使用，且自费部分水电费的价格标准要高于教工的收费标准（主要是节约资源）。基本要求l 实现对用户信息的录入l 实现水电煤气数据的录入l 计算并查询用户应缴费用l 查询未缴纳费用名单测试数据可选用小区物业管理部门的数据，也可采用手工输入不少于10个用户信息的数据。实现提示l 用户基本信息类，教工用户信息类，学生用户信息类 l 收费标准类，该类存储水电煤气标准单位的收费标准，如：煤气，1.0元/立方米；l 不同类型人员水、电、煤气信息类，这些类可以包括水表，电表，煤气表ID,抄表时间，上次抄表时间，本次抄表时
22、间，上次抄表度数，本次抄表度数，本次使用度数，费用，是否缴费标记等信息。l 在实现的时候考虑继承和多态技术的合理使用。选做内容实现用户查询系统能够找出该用户半年之内的交费记录和本次应交费的数据。11. 赛事管理系统参赛选手n人（n1），评委m人（m2），评委给每一选手打一个分数score（分数score为小于等于10的一个正实数）。选手的最后得分lastScore计算方法为（1）m9时，去掉一个最高分和一个最低分后另m-2个得分的平均值。（2）m9时，去掉两个最高分和两个最低分后另m-4个得分的平均值。假设事先已经建立了text型的数据文件f1.txt，其中依次记录着n个选手的编号（一个正整数
23、）、姓名（一个字符串）以及m个评委给出的得分。请编制程序，依次从数据文件f1.txt中读入n个选手的有关信息，而后按上述规定方法计算出每一个选手的最后得分，而且往屏幕上以及另一个text型文件f2.txt中同时输出如下形式的结果信息。假设参赛选手人数n=5，评委人数m=7，磁盘文件f1.txt中的初始数据为：1 zhangjin 8.8 9.3 7.9 8.7 8.9 9.7 9.22 lintao 8.9 8.2 8.6 8.8 8.5 9.1 9.33 guojian 8.9 8.4 8.7 8.6 8.6 8.4 8.64 maling 7.9 8.3 8.5 8.6 8.5 8.9 8
24、.35 liuyifan 9.5 9.1 9.8 9.2 9.0 9.5 8.9那么，程序执行后，屏幕显示结果以及磁盘文件f2.txt中的结果均应该为：- 参赛号 姓 名 最高分 最低分 累积分 最后得分- 1 zhangjin 9.7 7.9 44.9 8.98 2 lintao 9.3 8.2 43.9 8.78 3 guojian 8.9 8.4 42.9 8.58 4 maling 8.9 7.9 42.2 8.44 5 liuyifan 9.8 8.9 46.3 9.26-思考：可进一步考虑找出比赛的第1至第k名，也在屏幕以及f2.txt中同时输出相关的结果信息（k小于等于n，并规定
25、若多个选手最后得分相同时，则有效分（即已删除原来的最高分后）中最高分高者名次优先）。12. 学生学籍与成绩管理系统设计一个类CStudent，类中包含一个学生的基本数据如下：编号，姓名，性别，年龄，数学成绩，计算机成绩，外语成绩。并假设编号为整数，且从1号往后连续编码；姓名为字符串，性别为字符。如：1 LiPing m 18 89 98 94请采用binary文件形式，并使用随机读写处理方式，对自定义CStudent类的对象数据进行存储与读写处理（即是说，总按具有连续编码的编号num为“序”来对文件中的各对象数据进行随机读写处理）。并设计该类的成员函数，而且对输出运算符“”进行重载，使该运算符
26、能够完成将一个学生的信息输出到屏幕上。要求成员函数完成以下功能：（1） 从键盘输入一个学生的有关信息，并将它们存入到数据文件中（按编号来确定写出位置）。（2） 按编号对学生信息进行检索并将检索结果显示在屏幕上。（3） 按姓名对学生信息进行检索并将检索结果显示在屏幕上。（4） 计算某编号学生的总成绩与平均成绩。（5） 列出所有总成绩超过n分的性别为s同学的有关信息(n,s由用户从键盘输入)。思考：可进一步对上述程序进行扩充，如，添加学生基本数据（籍贯，专业，班级，其他各门成绩，奖惩记录等），并添加所需要的其他相关处理函数（如可通过咨询教学办公室管理人员后确立），进而将其编制成为一个简单而实用的小
27、型学籍与成绩管理软件。13. 日期时间显示（1）定义一个时间类Time，能提供时、分、秒组成的时间，并提供时间增加的方法（按秒）。（2）定义一个日期类Date，记录年、月、日，并提供日期增加的方法（按天）。（3）由类Time和日期类Date，派生出DateTime类，除具有年、月、日、时、分、秒外，还增加国名和与格林威治时间的差。编写一个应用程序，输入年、月、日、时、分、秒，在屏幕上模拟显示一电子计时器，不断输出下一秒的时间和日期，以及格林威治的日期和时间。注意，当对日期增加1天后，会涉及所谓的“进位”问题：首先算出本“日”所在的月份具有的天数N，若加1之后的“日”数值超过所在的月份具有的天数
28、N时，“进位”到月，而月份若超过12时还要“进位”到年。思考：可对该类增加你所考虑到的其他功能，如，对日期进行输入，计算二日期的间隔天数，计算某日期为星期几，打印对象当前数据的y年m月的月历，一次增加若干天，对两个日期进行其他比较运算等。14. 商品管理系统某商场有如下的几种货品：衬衣、鞋子、帽子、裤子、冰箱、电视、立柜、壁橱、沙发。每一种货物都有详细的说明信息。衬衣：布料、尺寸、单价、产地、库存量、所属货柜；鞋子：皮料、尺寸、单价、产地、库存量、所属货柜；帽子：布料、样式（平顶或尖顶）、尺寸、单价、产地、库存量、所属货柜；裤子：布料、尺寸、单价、产地、库存量、所属货柜；冰箱：制冷类型、样式（
29、二门或三门）、颜色、尺寸、单价、产地、库存量、重量、所属货柜；电视：样式（彩色或黑白）、颜色、尺寸、单价、产地、库存量、重量、所属货柜；立柜：木料、颜色、尺寸、单价、产地、库存量、所属货柜；壁橱：木料、颜色、尺寸、单价、产地、库存量、所属货柜；沙发：木料、皮料、颜色、尺寸、单价、产地、库存量、所属货柜；对这些商品的操作有：新商品的录入，商品的进库，商品的出库，商品的调价，所属货柜的管理，库存的统计，总价格的计算，产地的统计。要求自行设计数据结构，用类结构将上述的货品表示出来。在上一步的基础上，将上述的商品管理计算机化，完成操作要求的功能。15. 实现集合类MyVector 定义并实现一个集合类
30、MyVector，集合类中curSize表明当前集合中有几个元素，集合中最多含maxSize个元素，存放集合元素的数组是动态的。要求提供的方法有：（1）增加一个元素到集合中；（2）从集合中去掉一个元素；（3）判断一个元素是否在集合中；（4）重载运算符输出集合；（5）分别实现集合的交、并、差运算。16. 实现字符串类MyString设计一个简单的字符串类MyString，它包含设置字符串、返回字符串长度和显示内容等功能。能对字符串进行插入、替换、删除、查找和连接等操作。程序要求：（1）对字符串的操作采用下列菜单形式：1 生成字符串2 显 示3 求字符串长度4 字符串插入5 字符串替换6 字符串删
31、除7 字符串查找8 字符串的连接0 返回（2）调试1. 生成字符串 s=”ABCDBCEFGHTH”2. 求长度 len(s)=123. 字符串的插入t=”XYZ” insstr(s, 3, t)= ”ABXYZCDBCEFGHTH”4. 字符的替换 将字符串s中的所有p=”BC”替换为t=”LMN”;repl(s, p, t)= ”ALMNDLMNEFGHTH”5. 字符串的查找 p=”BC”:index(s, p)=26. 字符串的连接 将字符串p“”的字符串s连接：strcat(s, p)=”ABCDBCEFGHTH”17. 线性表操作定义一个线性表类(采用类模板)，实现下列操作：（1）
32、 生成线性表。（2） 做元素的插入、删除操作。（3） 元素的查找。（4） 线性表输出。（5） 二个多项式合并一个多项式。设计一个选择式菜单，以菜单方式选择上述操作。18. 考勤管理考勤管理信息记录了学生的缺课情况，它包括：缺课日期、第几节课、课程名称、学生姓名、缺课类型（迟到、早退、请假及旷课）。试设计一个考勤管理系统，使之能提供以下功能： （1） 录入学生的缺课记录； （2） 修改某个学生的缺课记录；（3） 查询某个学生的缺课情况； （4） 统计某段时间内，旷课学生姓名及旷课次数，按旷课次数由多到少排序；（5） 统计某段时间内，有学生旷课的课程及旷课人次，按旷课人次由多到少排序； （6） 系
33、统以菜单方式工作19. 学生成绩统计管理主要功能：1）输入一个班级的学生的基本信息（包括学好，姓名，性别，5门课程成绩）。2）按姓名或者学号查找、修改、删除和保存各个学生的信息。3）计算每个学生各门功课总分和平均分，按学号或总分排序输出每个学生的基本信息及总分、平均分和名次。4）计算全班各门功课的平均分，显示每门课程中低于平均分的每一个学生的学号，姓名，性别，科目，成绩。5）显示每门科目中，成绩在90分以上的学生信息，以及每门科目中不及格的学生信息。6）设置系统登陆密码，只有正确输入密码方可进入管理系统；可更改和保存登录密码。20. 用模板类实现中缀表达式转后缀并求值1设计目的（1）掌握栈“后
34、进先出”的特点。（2）掌握栈的典型应用中缀表达式转后缀、并利用后缀表达式求值。（3）掌握串或者数组的相关操作。（4）掌握C+模板类和STL的使用。2主要内容（1）中缀表达式转换为后缀。（a）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号），然后从中缀表达式中自左至右依次读入各个字符。（b）如果是第一次读入运算对象，则直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。（c）如
35、果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（d）如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，直到遇到一个开括号“（”为止。开括号“（”和闭括号“）”均不输出到后缀表达式。（e）重复（b）（c）（d）步，直到中缀表达式结束，然
36、后将栈中剩余的所有运算符依次出栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（f）给后缀表达式加上0作为字符串结束标志。（2）后缀表达式求值。（a）定义一个double型的运算数栈，将中缀表达式转换得到的后缀表达式字符串自左向右依次读入。（b）如果读入的是运算对象，则将该运算对象串（下一个逗号分隔符前的部分所构成的数字字符串）转换为对应的多位整数值，然后将该整数值（将自动类型转换为double型）直接进入运算数栈。（c）如果读入的是运算符，则立即从运算数栈中弹出两个运算数，计算两个运算数运算后的值（运算时先出栈的元素放在运算符后面，后出栈的元
37、素放在运算符前面），并将计算结果存回运算数栈。（d）重复（b）（c）步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表达式的计算结果。（e）和手工计算的结果进行比较，检验程序运行结果的正确性。假设输入中缀表达式为：转换后的后缀表达式为：后缀表达式求得的值为：523设计要求（1）运算对象存在多位整数。（2）遇到除数为0的情况，应能给出相应提示，并提醒重新输入中缀表达式。（3）%运算符左右遇到非整数时，应能自动对其进行取整；%运算符左右遇到负数时，应能给出相应提示，并提醒重新输入中缀表达式。（4）如果一个班级中有两个同学同时选中该课题，则要求学号在前的同学用模板类的方式自定义栈；学号在后面的
38、同学要求使用STL中提供的栈来实现。21. 马的遍历及其复杂性分析1设计目的（1）掌握栈的本质，灵活使用栈解决实际问题。（2）掌握求解问题时使用的回溯策略。（3）比较一般回溯方法和贪心算法的异同点，并尝试分析其时间和空间代价。2主要内容编写程序实现马对棋盘方格的遍历。一个棋盘有八行八列共64个方格，输入马的起始方格位置，从起始方格出发，一个马的移动必须跨越两行一列或是两列一行。设起始方格的次序为1，马跳过的下一个方格的次序是上一个方格的次序加1。马必须经过每个方格且仅经过一次，并且马的移动不能超越棋盘边界，求出马经过这64个方格的次序。例如，图12-25显示了坐标（5,3）位置上马的所有合法移
39、动位置（即K0K7）。图12-25 位置K上马的八个合法移动位置简化问题表述则为：从坐标（row，column）出发，依次尝试：（row-2，column+1）、（row-1，column+2）、（row+1，column+2）、（row+2，column+1）、（row+2，column-1）、（row+1，column-2）、（row-1，column-2）、（row-2，column-1）这八个方向。先将整个棋盘（实质就是一个二维数组）的所有方格初始化为-1。回溯法解决马遍历棋盘的步骤：（1）从起始位置开始，可将马的每次跳动抽象为一个栈结点，当马跳到下一个方格时就将起跳方格的信息压栈，并
40、在棋盘中标记好马经过该起跳方格的次序。（2）当马跳到某个方格发现无处可跳时，就出栈一个结点（相当于跳回到上一步，即回溯），并将该方格的次序恢复为初始值-1，然后尝试出栈结点对应方格的下一个跳跃方向。提示：某个方格无处可跳意味着该方格的八个方向要么是已经尝试过的“死路”，要么就是超出棋盘边界的，此时只能通过出栈方式回跳到上一个方格，从而进一步尝试上一个方格的其它方向是否存在遍历通路。（3）当某个方格次序为64时，代表所有方格都遍历完。（4）输出所有方格中的次序。栈结点的结构可以设置如图12-26：图12-26 栈的结点结构其中rowNo保存起跳方格的行号，colNo保存起跳方格的列号，direc
41、tion保存起跳方格的方向（int型，取值为0-7，对应K0-K7这八个方向）。通过当前方格位置及方向即可计算出下一个方格的行号和列号，便可进一步判断该方格是否越界或者马是否已经过该方格了。注意：对于用回溯法编出的程序，只能输入（0,0）等少数坐标进行测试，如果输入其它坐标作为马的起始位置，因为回溯次数太多，可能程序运行很久也得不到运行结果。假设输出马的起始位置为（0,0），则马遍历整个棋盘方格的次序如12-27所示。图12-27 初始位置为（0,0）的遍历次序图12-28 初始位置为（5,3）的遍历次序若用贪心算法实现该程序，假设马的起始位置为（5,3），则马遍历整个棋盘方格的次序如图12-
42、28所示。3设计要求（1）用回溯法编程，输入马的初始坐标为（0,0），输出马对整个棋盘的遍历次序。（2）输入马的初始坐标为其它方格坐标值，观察程序的运行时间并分析之。（3）查阅参考资料，了解贪心算法策略，并改用贪心算法实现该程序，输入马的初始坐标为棋盘64个坐标中的任意坐标，检验程序的运行结果，观察程序的运行时间。（4）分析一般回溯方法和贪心算法解决该问题的特点及其时间复杂度。（5）如果一个班级中有两个同学同时选中该课题，则要求学号在前的同学用模板类的方式自定义栈；学号在后面的同学要求使用STL中提供的栈来实现。22. Win32连连看游戏程序设计1设计目的（1）掌握Win32程序的实现方法。（2）参照视频提高自学能力。（3）熟悉C+开发实际项目的过程和方法。2课题要求用VC+6.0实现一个连连看游戏程序。23. Win32扫雷游戏程序设计1设计目的（1）掌握Win32程序的实现方法。（2）参照视频提高自学能力。（3）熟悉C+开发实际项目的过程和方法。2课题要求用VC+6.0实现一个类似于Windows附件中自带的扫雷游戏程序。24. Win32计算器程序设计1设计目的（1）掌握Win32程序的实现方法。（2）参照视频提高自学能力。（3）熟悉C+开发实际项目的过程和方法。2课题要求用VC+6.0实现一个类似于Windows附件中自带的计算器程序。